汪宏海，吳 櫻

基于自表示的雙圖規(guī)格化特征選擇聚類

*汪宏海1,2，吳 櫻1,2

（1.浙江省文化和旅游發(fā)展研究院，浙江，杭州 311231；2.浙江旅游職業(yè)學院，浙江，杭州 311231）

特征選擇得到的識別特征可以用于聚類分析，提高聚類分析的質量。受數(shù)據(jù)自表示特性和雙圖規(guī)則化學習的啟發(fā)，提出了一種新的特征選擇聚類算法。利用數(shù)據(jù)和特征的自表示特性，不僅保留了數(shù)據(jù)的流形信息，而且保留了特征空間的流形信息。此外，為了充分發(fā)揮雙圖模型的作用和鑒別局部聚類的效果，加入局部判別特征選擇聚類，大大提高了聚類的有效性和魯棒性。

特征選擇；自表示；雙圖規(guī)格化；聚類

0 引言

大數(shù)據(jù)中存在著高維數(shù)據(jù)。這些高維的數(shù)據(jù)不僅數(shù)據(jù)維度非常大，冗余的數(shù)據(jù)也非常多。數(shù)據(jù)降維可以降低數(shù)據(jù)的維度，排除一些冗余復雜的噪聲數(shù)據(jù)集[1]。數(shù)據(jù)降維的方法主要有兩種：特征選擇和特征提取。特征選擇是從原始的眾多特征中，選擇出具有代表性質的特征，由于是從原始的特征集合中篩選出來的特征集，所以不會破壞原有的數(shù)據(jù)，并且具有解釋性強的優(yōu)點[2]。本研究主要關注特征選擇。特征選擇按照使用標簽信息的方式，可分為監(jiān)督、半監(jiān)督、非監(jiān)督算法。由于現(xiàn)實中很多數(shù)據(jù)沒有標簽信息，因此，非監(jiān)督特征選擇具有更廣泛的應用[3-4]。

在特征選擇領域中，根據(jù)選擇思想的不同，選擇方法可以分為過濾法(filter)、包裹式(wrapper)、嵌入式(embedding)[5]。Embedding方法由于結合了機器學習的思想，具有較好的效果[6]。很多非監(jiān)督特征選擇算法用來做聚類，由于在選擇后獲得表示特征用于聚類，因此，聚類質量得到了加強[7]。在Embedding方法的研究中，目前較為成熟且較為廣泛使用的方法，基本上都是基于將流形學習與NMF思想結合的算法，比如拉普拉斯評分（Laplacianscore：LapScore）[8]、譜特征選擇（SPEC： spectral feature selection[9]，多類簇特征選擇（MCFS：Feature Selection For Multi-cluster Data）[10]，最小冗余譜特征選擇算法(MRSF:Spectral Feature Selection with Minimum Redundancy)[11]，聯(lián)合嵌入式學習和稀疏回歸的特征選擇(JELSR:Joint embedding Learning and Sparse)[12]，局部性和相似性保留嵌入特征選擇(LSPE：locality and similarity preserving embedding feature selection)[13]。

已有的算法中，LapScore只保留數(shù)據(jù)流形的位置，但是沒有學習機制和迭代更新機制；SPEC可以看作是LapScore的擴展，但主要用于監(jiān)督特性選擇，并不適用于無監(jiān)督特征選擇；考慮到不同集群之間的關系，MCFS保留了數(shù)據(jù)集的多集群結構。JELSR將嵌入式學習和稀疏回歸統(tǒng)一到一個無監(jiān)督的特征選擇框架中，利用學習后的稀疏投影矩陣進行特征選擇。MRSF是基于稀疏多輸出模型來最小化冗余特性的。LSPE將嵌入式學習和特征選擇集成在一個聯(lián)合框架中?？傊?，上述特征選擇算法都是在數(shù)據(jù)流形空間中進行的，有些保持局部信息，有些保持相似性以提高學習性能，都缺少了對數(shù)據(jù)表示特征的有效使用。

基于此，受自表示特性和雙圖規(guī)則化學習的啟發(fā)，提出一種新的特征選擇聚類算法。本算法不使用投影矩陣，而是利用數(shù)據(jù)和特征的自表示特性，在數(shù)據(jù)空間中使用自表示系數(shù)矩陣作為特征自表示構造的重要度量，利用數(shù)據(jù)空間中的自表示系數(shù)矩陣對特征進行排序。不僅保留了數(shù)據(jù)的流形信息，而且保留了特征空間的流形信息。此外，加入局部判別特征選擇聚類，可以大大提高聚類的有效性和魯棒性。

2 本文算法

圖1 數(shù)據(jù)處理過程

2.1 關鍵技術

本算法中，數(shù)據(jù)點和特征是通過利用自表示來表示的。對于每個向量x，通過自表示屬性，可以由中的所有特征表示，即1;2; …;x來表示?？梢缘贸觯?/p>

(2)

類似的，在數(shù)據(jù)空間，可以得到：

XT=XTP+H (3)

將自表示重構誤差最小化，即解決如下問題：

其中，參數(shù)（≥0）平衡這兩個自表示的錯誤項。

在數(shù)據(jù)空間和特征空間中構造兩個鄰域圖來保存局部幾何信息，即數(shù)據(jù)圖和特征圖。在數(shù)據(jù)空間中構造最近的鄰域圖G，圖中的每個節(jié)點對應一個數(shù)據(jù)點。如果兩個數(shù)據(jù)點位于個最近的鄰域內，則設置一條邊。兩個數(shù)據(jù)點之間的相似性作為邊緣權重。選擇0-1加權方案作為權重函數(shù)。

0-1權重方案定義如下：

特征圖的拉普拉斯算子矩陣是L=D-W，其中D是一個對角矩陣，并且

X=11i+22i+…+XS

X=11j+22j+…+XS

把的第列和第列表示為

S=[1i,2i,…,S]

S=[1j,2j,…,S]

同樣，考慮到數(shù)據(jù)空間的自表示矩陣和相似矩陣W，可以得到以下的數(shù)據(jù)表示平滑度：

在上述數(shù)據(jù)圖和特征圖的基礎上，利用自表示特性，同時考慮數(shù)據(jù)空間和特征空間的多種信息，尋求一個在數(shù)據(jù)空間和特征空間中都具有的準確表示。因此，本算法解決以下最小化問題：

,≥0 (9)

上式中，>0,1>=0,2>0。為了簡單和方便，讓1=1=，這樣，目標函數(shù)就可以改寫為：

,≥ 0 (10)

因此，本問題即是：

≥ 0 (11)

參數(shù)λ（λ ≥ 0）平衡最后稀疏的項目。此式子通過迭代的方式進行求解。

2.2 融入LDC（local density clustering）的聚類算法

根據(jù)預先設置的聚類數(shù)，將聚類分為若干部分，使同一類元素的相似性盡可能大，使不同類元素的相似性盡可能小。在上面的算法中，根據(jù)||P||的值按降序選取數(shù)據(jù)集的前個特征，從而在特征選取后得到矩陣X= [1,2，…，]∈×。然后，對數(shù)據(jù)集X進行聚類。將數(shù)據(jù)集X劃分為聚類簇，得到標記矩陣= [1,2，…，m]∈{0,1}×c。m的第個元素是m，如果X∈C，則m= 1，否則為0。

首先定義一個矩陣Z：

其中Z為數(shù)據(jù)向量習的聚類賦值向量。由于MM是一個對角矩陣，可以很容易地得出結論：

定義簇間散射矩陣S、簇內散射矩陣S和總散射矩陣S如下：

．>0 (17)

由于式(13)中ZZ = I，可以通過最小化以下目標得到最佳的聚類分配矩陣Zbest功能：

> 0 (18)

由于數(shù)據(jù)的局部流形信息類似于線性，采用由數(shù)據(jù)點x的個最近鄰組成的局部團N(x)，其中包含數(shù)據(jù)點x本身及其(- 1)個最近鄰。因此，建立了一個局部線性判別模型來評價聚類結果。

定義一個矩陣X= [x1,x2，…，x]，其中包含局部分N(x)中的所有數(shù)據(jù)點，并將對應的索引集定義為= {1,2，…,i}。同樣，根據(jù)局部線性判別模型，定義1= [11,12，…，1k]∈×，由矩陣簇Z按照下式計算得到：

> 0 (20)

> 0 (21)

因為：

因此，公式（21）就可以轉化為：

> 0 (23)

把上式改為：

其中：

定義

那么上式就可以寫作：

2.3 具體算法流程

本文算法分為以下10個步驟：

Step1．加載數(shù)據(jù)矩陣。

Step2．計算出數(shù)據(jù)矩陣的特征空間的非負矩陣因子，數(shù)據(jù)空間的非負矩陣因子，初始化矩陣，，。

Step3.根據(jù)迭代更新規(guī)則（5），(9)和（10）更新矩陣，和。

Step 4.根據(jù)||P||2的值按降序選取前個特征。

Step 5.構造每個數(shù)據(jù)點的局部小圈子。

Step 6.根據(jù)式(24)計算L，通過全局積分求解式(26)中的拉普拉斯矩陣。

Step 9．通過連續(xù)迭代優(yōu)化得到二值聚類分配矩陣M。

Step 10．最后，通過評價指標計算出ACC和NMI輸出結果。

3 實驗及數(shù)據(jù)分析

3.1 數(shù)據(jù)集及參數(shù)設置

實驗中驗證了在5個數(shù)據(jù)集上，本文算法和其他特征選擇算法的比較結果，并對結果進行了分析。5個數(shù)據(jù)集分別為：UMIST圖像集，包括20個人共575幅圖像，每個人具有不同角度、不同姿態(tài)的多幅圖像；ORL圖像集包括40人，共400張面部圖像；BC數(shù)據(jù)集包括2類569個數(shù)據(jù)；Ionosphere是一個經典的二元分類問題，共有351個觀測值，34個輸入變量；Dbworld_bodies包含2類64個數(shù)據(jù)。實驗比較的算法包括LapScore[8]、SPEC[9]、MCFS[10]、MRSF[11]、JELSR[12]、LSPE[13]。

表1 數(shù)據(jù)集

Table 1 Data set

數(shù)據(jù)集維度大小類數(shù) UMIST64457520 ORL102440040 BC305692 Ionosphere343512 Dbworld_bodies4702642

實驗中參數(shù)的設置如下：LSPE、LapScore、SPEC和MCF，鄰居數(shù)選自{3,5,10,15}，σ的內核權重選自{1,103,105}。本算法的正則參數(shù)α選自{0.01,0.1,0.5,1.0,5.0,9.0,13.0,17.0}，β選自{100, 1000}，λ選自{300,800,2000,4000,6000,8000}。常規(guī)參數(shù)α選自{0.01,0.1,0.5,1.0,5.0,9.0,13.0,17.0}，β和θ選自{300,800,2000,4000,6000,8000}，μ選自{10?8,10?6,10?4,10?2,100,102,104,106,108}。

3.2 評價指標

用兩個廣泛使用的評價矩陣來評價聚類的性能。聚類精度(ACC)，歸一化互信息(NMI)。ACC和NMI值越大，說明性能越好。

給定數(shù)據(jù)點，c和g分別為的聚類標簽和有效真實標簽。

ACC的定義如下：

NMI的定義如下：

NMI是評價聚類標簽之間的相似性程度的一種外部準則，它評估了聚類標簽和基本真實標簽之間的相似程度。ACC和NMI是兩個聚類評估標準，它們可能無法同時在一個數(shù)據(jù)集中獲得最佳效果。

3.3 實驗結果

實驗記錄了最優(yōu)參數(shù)的最佳聚類結果。表2顯示了5個數(shù)據(jù)集的平均ACC和標準偏差，用粗體突出顯示最佳結果。

3.3.1 本文算法實驗結果

表2 相關算法ACC

Table 2 ACC of related algorithms

算法UmistORLIonosphereBCDbworld_bodies LapScore37.30 ± 0.9344.50 ± 0.7366.94 ± 2.2070.17 ± 0.3673.47 ± 1.16 SPEC42.56 ± 1.2049.88 ± 0.2367.70 ± 2.3374.00 ± 0.2377.94 ± 1.85 MCFS46.55 ± 1.0049.40 ± 0.9357.26 ± 3.0071.00 ± 0.5891.13 ± 1.04 JELSR48.90 ± 1.0350.02 ± 0.5667.90 ± 2.8174.20 ± 0.3090.63 ± 0.00 MRSF48.38 ± 1.0549.78 ± 0.6963.00 ± 2.3072.9 ± 0.2285.02 ± 1.59 LSPE49.26 ± 1.1250.25 ± 0.8070.00 ± 2.6675.86 ± 0.2493.75 ± 0.00 本文算法61.21 ± 2.2560.71 ± 1.5188.79 ± 2.3775.55 ± 0.0095.68 ± 0.014

表3顯示了5個數(shù)據(jù)集的NMI，用粗體突出顯示最佳結果。

表3 相關算法NMI

Table 3 NMI of related algorithms

算法UmistORLIonosphereBCDbworld_bodies LapScore56.32 ± 1.5267.80 ± 1.76 8.16 ± 0.0016.79 ± 0.0023.82 ± 1.01 SPEC57.04 ± 1.2470.26 ± 1.65 8.33 ± 0.0018.83 ± 0.0025.20 ± 1.62 MCFS69.20 ± 1.3170.98 ± 1.78 1.01 ± 0.7717.32 ± 0.0067.88 ± 1.62 JELSR70.18 ± 1.6470.20 ± 1.72 7.84 ± 1.2118.86 ± 0.0054.89 ± 0.00 MRSF66.67 ± 1.4370.50 ± 1.81 3.82 ± 0.0017.32 ± 0.0056.79 ± 2.39 LSPE70.01 ± 1.5071.04 ± 1.1113.10 ± 0.4918.83 ± 0.0068.09 ± 0.00 本文算法70.51 ± 1.5275.25 ± 1.3323.12 ± 0.5730.99 ± 0.0059.99 ± 1.27

從表2和表3中，可以看到：本文算法優(yōu)于其他算法，在幾乎所有數(shù)據(jù)集的聚類精度方面都取得了較好的結果，尤其是在處理面部數(shù)據(jù)的時候。與其他特征選擇算法相比，本算法的主要改進之處在于它利用了特征空間的自表示特性，特征空間中的信息對于聚類是非常重要的。SPEC, MCFS和MRSF是兩階段的特征選擇算法，而JELSR，LSPE和本文算法同時集成多種策略。JELSR將嵌入式學習和稀疏回歸相結合，LSPE將嵌入式學習和特征選擇相結合，本算法將自表示、流形嵌入和特征選擇相結合?？傮w上，JELSR、LSPE的聚類質量優(yōu)于其他算法，說明同時求解多個問題優(yōu)于按順序求解。LSPE是實驗中第二好的算法，也說明了將嵌入學習和特征選擇結合起來進行特征選擇是一種較好的方法。

3.3.2 沒有加入局部判別的算法效果

為了更清楚的體現(xiàn)局部判別的對算法結果的影響，在不加入局部判別的情況做了相關實驗，表4顯示了5個數(shù)據(jù)集ACC結果，表5顯示了5個數(shù)據(jù)集NMI結果。

表4 相關算法ACC（無局部判別）

Table 4 ACC of related algorithms （without local discrimination）

算法UmistORLIonosphereBCDbworld_bodies LapScore37.30 ± 0.9344.50 ± 0.7366.94 ± 2.2070.17 ± 0.3673.47±1.16 SPEC42.56 ± 1.2049.88 ± 0.2367.70 ± 2.3374.00 ± 0.2377.94±1.85 MCFS46.55 ± 1.0049.40 ± 0.9357.26 ± 3.0071.00 ± 0.5891.13±1.04 JELSR48.90 ± 1.0350.02 ± 0.5667.90 ± 2.8174.20 ± 0.3090.63±0.00 MRSF48.38 ± 1.0549.78 ± 0.6963.00 ± 2.3072.9 ± 0.2285.02±1.59 LSPE49.26 ± 1.1250.25 ± 0.8070.00 ± 2.6675.86 ± 0.2493.75±0.00 本文算法58.68 ± 2.6957.64 ± 1.8485.45 ± 2.5875.24 ± 0.0994.70±.021

表5 相關算法NMI（無局部判別）

Table 5 NMI of related algorithms（without local discrimination）

算法UmistORLIonosphereBCDbworld_bodies LapScore56.32 ± 1.5267.80 ± 1.76 8.16 ± 0.0016.79 ± 0.0023.82 ± 1.01 SPEC57.04 ± 1.2470.26 ± 1.65 8.33 ± 0.0018.83 ± 0.0025.20 ± 1.62 MCFS69.20 ± 1.3170.98 ± 1.78 1.01 ± 0.7717.32 ± 0.0067.88 ± 1.62 JELSR70.18 ± 1.6470.20 ± 1.72 7.84 ± 1.2118.86 ± 0.0054.89 ± 0.00 MRSF66.67 ± 1.4370.50 ± 1.81 3.82 ± 0.0017.32 ± 0.0056.79 ± 2.39 LSPE70.01 ± 1.5071.04 ± 1.1113.10 ± 0.4918.83 ± 0.0068.09 ± 0.00 本文算法70.36 ± 1.6574.14 ± 1.4521.76 ± 0.7330.13 ± 0.0858.24 ± 1.38

從表4和表5的結果可以看出，本文提出的算法即使在沒有局部判別信息的情況下，總體效果也優(yōu)于相關算法。但與加入局部判別信息的本最終算法比較，效果略微差一些，方差變大。因此，說明了加入局部判別，可以提高聚類的有效性和魯棒性。

4 結論

本研究提出了一種自表示的雙圖規(guī)格化特征選擇聚類算法，不僅保留了數(shù)據(jù)的流形信息，而且保留了特征空間的流形信息。此外，加入局部判別特征選擇聚類，可以大大提高聚類的有效性和魯棒性。

[1] 機器學習中的特征選擇方法研究及展望[J].北京郵電大學學報, 2018(1):1-12.

[2] 謝娟英,丁麗娟,王明釗.基于譜聚類的無監(jiān)督特征選擇算法[J].軟件學報,2020,56(1):20-32.

[3] Meng Y,Shang R,Jiao L,et al.Feature selection based dual-graph sparse non-negative matrix factorization for local discriminative clustering[J].Neurocomputing,2018，32(3)：1783-1796.

[4] Shang R,Wang W,Stolkin R,et al.Non-Negative Spectral Learning and Sparse Regression-Based Dual-Graph Regularized Feature Selection[J]. IEEE Transactions on Cybernetics,2017,45(6):1-14.

[5] Meng Y,Shang R,Jiao L,et al.Dual-graph regularized non-negative matrix factorization with sparse and orthogonal constraints[J].Engineering Applications of Artificial Intelligence,2018, 69:24-35.

[6] Hou C, Nie F, Li X, et al. Wu,Joint embedding learning and sparse regression:a framework for unsupervised feature selection[J]. IEEE Trans on Cybernetics, 2014,44 (6):793-804.

[7] Zhu X Y. Improved Algorithm Based on Non-negative Low Rank and Sparse Graph for Semi-supervised Learning[J].Journal of Electronics & Information Technology,2017,10(4):1123-1128.

[8] Tian S,Zhang Y,Yan Y.?1/2-norm regularized nonnegative low-rank and sparse affinity graph for remote sensing image segmentation[J].Journal of Applied Remote Sensing,2016,10(4):042008.

[9] Zhao Z, Wang L, Liu H. Efficient spectral feature selection with minimum redundancy[C]. Proceedings of 24th AAAI Conference on Artificial Intelligence, 2010:673-678.

[10] Zhao Z, Liu H.Spectral feature selection for supervised and unsupervised learning[C]. Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007),2007.

[11] Cai D, Zhang C, He X. Unsupervised feature selection for multi-cluster data[C]. Acm Sigkdd International Conference on Knowledge Discovery & Data Mining, ACM, 2010.

[12] Li Z,Tang J.Unsupervised Feature Selection via Nonnegative Spectral Analysis and Redundancy Control[J].IEEE Transactions on Image Processing,2015, 24(12):5343-5355.

[13] Fang Y,Xu X,Li Z.Locality and similarity preserving embedding for feature selection[J]. Neurocomputing, 2014,128:304-315.

[14] Zhu X Y, Wang Y, Li Y B. A new unsupervised feature selection algorithm using similarity-based feature clustering.[J] Computational Intelligence,2019, 47(1):161-173.

[15] 方佳艷,劉嶠.具有同步化特征選擇的迭代緊湊非平行支持向量聚類算法[J].電子學報,2020，56(1):20-32.

[16] Yang Y, Xu D, Nie F, et al. Image clustering using local discriminant models and global integration[J].IEEE Trans. Image Process. 2010,19(10): 2761-2773.

[17] Wu S S, Hou M X, Feng C M. LJELSR: A Strengthened Version of JELSR for Feature Selection and Clustering[J]. International journal of molecular sciences,2018, 22(8):888-905.

[18] Ahmad AliyuUsman,Starkey Andrew.Application of feature selection methods for automated clustering analysis:a review on synthetic datasets[J].Neural computing and applications,2018,56(3):115-119.

FEATURE SELECTION CLUSTERING BASED ON SELF-REPRESENTING DOUBLE GRAPH NORMALIZATION

*WANG Hong-hai1,2，WU Ying1,2

(1. Zhejiang Institute of Culture and Tourism Development, Hangzhou, Zhejiang 311231, China; 2. Tourism College of Zhejiang, Hangzhou, Zhejiang 311231, China)

The recognition features obtained through feature selection can be used in cluster analysis to improve the quality. Inspired by the self-representation characteristics of data and regular learning of double graphs, a new feature selection clustering algorithm was proposed. Utilizing the self-representation characteristics of data and features, not only the manifold information of the data but also the manifold information of the feature space was retained. In addition, in order to make the dual graph model work at full capacity, and identify the effects of local clusters, we added the local discriminative features for clustering, which had greatly improved the effectiveness and robustness of clustering.

feature selection; self-representation; double graph normalization; clustering

TP18

A

10.3969/j.issn.1674-8085.2021.02.013

1674-8085(2021)02-0076-07

2020-09-23；

2020-11-09

*汪宏海(1977-），男，江西樟樹人，副教授，碩士，主要從事算法優(yōu)化、圖像處理等方面的研究(E-mail:redsea54@163.com);

吳 櫻(1980-），女，浙江杭州人，講師，碩士，主要從事酒店人力資源管理、酒店數(shù)字化運營等方面的研究(E-mail:652348105@qq.com).