基于聚類的分層降維框架

陳新元，謝晟祎

計算機科學與自動化技術

基于聚類的分層降維框架

陳新元1,2，謝晟祎3

（1. 閩江學院 計算機與控制工程學院，福建 福州 350121；2. 福州墨爾本理工職業學院 信息工程系，福建 福州 350121；3. 福建農業職業技術學院 實驗實訓中心，福建 福州 350181）

在分析、驗證主流降維算法性能的基礎上，設計了基于聚類的分層降維框架，將聚類和降維結合，實現了類內和類間分別降維的處理機制。實驗結果表明，隨著數據集規模增長，分層降維框架的時間效率逐漸體現出優勢。

高維數據；降維；聚類；分層；分類準確率

1 引言

近年來，隨著我國經濟的高速發展，行業數據采集、存儲和統計分析等方面的需求日益增長。在計算機和物聯網等產業的技術支撐下，數據量激增，從大規模數據中提取有效信息并輔助生產，對行業發展具有重大意義。

行業大數據具有維數巨大，復雜度較高等特點，導致識別和處理難度提高；高維數據和稀疏矩陣給計算能力帶來了新的挑戰。為快速提取信息，人們常根據人工經驗和先驗信息對維度特征進行篩選，或使用降維算法在盡可能保留數據結構的前提下將數據從高維空間映射至低維，從而降低計算復雜度。

降維算法可依不同標準分為線性和非線性算法，如PCA和KPCA；全局和局部算法，MDS和LLE；監督、無監督和半監督算法，如LDA（監督）和k-means（無監督）等。閆德勤等[1]針對局部線性嵌入算法的局限性，通過統計信息確定稀疏數據的局部可線性化范圍，改善高維數據的降維表現；趙孝禮等[2]則將KPCA與正交化局部敏感判別分析方法（OLSDA）結合，先使用KPCA消除冗余屬性，保留全局非線性結構，再使用OLSDA挖掘局部的流行結構以避免降維失真，最后通過近鄰分類器的識別率和聚類間距驗證算法；唐科威等[3]將洛倫茲投影判別法推廣到張量空間中，利用二階張量形式的灰度矩陣進行圖像降維以保留局部結構；劉勝藍等[4]通過改進的協方差陣更新方式解決噪音造成的子空間偏離問題；李海林等[5]使用正交多項式回歸模型對時間序列進行特征提取，運用奇異值分解實現特征降維；Lotlikar R等[6]在LDA算法的基礎上進行局部切割，通過增量計算流程提高每個子空間內權值計算的準確率；Jun Shi等[7]同樣將遞歸分治結構應用于基于瑞麗熵結構的KECA算法；Miguel Sim?o等[8]將雙三次插值算法與PCA結合，通過重采樣及降維提高不完整動態手勢的識別率；Fan M等[9]則引入流形回歸框架，通過復雜度和平滑度指標衡量降維表現，同時設計了基于流形回歸和最小二乘法的MR-KLS算法以進行特征映射和降維。

降維標準的選擇也是熱門方向。鑒于許多高維數據映射至2-3維（用于可視化）時壓縮率過大，數據結構丟失，聚類/分類等指標常被用于判斷降維效果。聚類常被用于目標群體劃分或樣本篩選，如曾蔚等[11]實現基于品牌忠誠度的用戶分類；王森等[12]使用聚類篩除離群的專家權重樣本；詹勝等[13]應用不同的距離標準取得精確的連鑄胚定重數據等。在降維相關研究中，Ding Chris等[10]將LDA和k-means算法結合，在特征選擇的基礎上進行聚類，并將聚類表現作為該方案的性能度量；Antoniadis A等[13]將降維與非參數判別結合，通過分類性能進行驗證；Laohakiat S等[14]將降維融入聚類框架，通過LDA降維尋找子空間，最后驗證了方案在提高聚類性能的同時縮短了處理時間。鑒于聚類與降維，特別是K-means與PCA存在密切的內在聯系，且降維往往是為了進一步聚類或分類，本文嘗試將兩者結合。

許多研究側重于降維準確率的改進，但對于大規模的行業數據，改進算法往往意味著更高的計算復雜度。本文目標是在不增加復雜度的前提下，提高降維處理效率，因此分析、比較了多種基礎降維算法、聚類算法，并在此基礎上設計并實現了分層降維框架，結合降維算法和聚類算法，先對高維數據進行聚類，根據維度間相似度進行分類，在類內降維、降低冗余的基礎上對合并的類間數據進行二次降維，從而減小計算復雜度，提高降維效率，實驗階段驗證了降維對分類準確率的影響。

2 分層降維框架

系統框架圖如圖1所示，使用k-means、層次聚類、SOM神經網絡等算法實現數據聚類，并將聚類結果應用于分層降維框架，使用PCA、LDA等算法分別實現類內降維和類間降維，使用SVM進行方案驗證。

圖1 系統框架圖

2.1 降維算法

2.1.1 線性降維算法

PCA：通過max方差或min誤差的思路構建高維數據至低維數據的轉換矩陣以盡可能保留有效信息。其主要過程包括：對矩陣進行中心化，以表示，計算T，分解矩陣并排序特征向量，將最大的個特征值構成的向量作為高維和低維的關聯矩陣，輸出=*。

LDA：監督降維算法，根據樣本數據分類標簽計算類別樣本均值和所有樣本均值，計算得到類間散度矩陣和類內散度矩陣，以此計算表示空間距離條件的投影矩陣，使同類數據的距離較小，異類數據的間距較大，最后輸出=T。

2.1.2 非線性降維算法

KPCA：將PCA算法擴展到非線性空間，主要過程如下：尋找合適的核函數，代入數據后計算核矩陣并進行標準化處理，最后分解特征值并排序輸出最大值對應的向量。算法將數據映射到高維空間，實現數據的線性可分。

LLE：局部算法，假定樣本數據與其近鄰滿足帶權線性關系，計算中在鄰域判定的基礎上保證近鄰點位置在空間轉換的過程中保持穩定，進而保留整體數據結構。其過程如圖1所示。

利用k-means等算法求近鄰，構建權值矩陣，計算中間矩陣并進行特征分解，選擇最小的d個特征值輸出。

MDS：全局降維算法，基于流形學習，假定所有樣本在低維空間都有對應的流形結構，構造局部結構并拓展到全局結構完成映射。算法思路是將樣本點從高維轉換至低維后，保持原有距離，因此需要計算高維數據的距離矩陣（基于歐式距離）并根據中間參數進行轉換，最后將距離矩陣進行譜分解，選擇特征值最大的d個向量構成對角矩陣并處理輸出。

ISOMAP：可視為MDS的改進版本，算法執行中先判定鄰域，對于鄰域外的樣本，使用測地距離替換歐式距離以保留流形結構，得到距離矩陣后采用MDS算法得到輸出。

SNE：該算法引入了條件概率以判斷相似度，概率值接近時表示降維前后樣本關系基本得以保存，過程中使用梯度下降算法最小化損失函數。通過設定方差，算法對于局部最小值陷阱有一定的規避能力。

t-SNE：SNE的改進算法，但計算復雜度較高。該算法使用聯合概率取代條件概率，同時用柯西分布代替高斯分布以解決異類數據重疊的問題。

鑒于傳統降維算法存在矩陣稀疏難以分解、存儲計算資源開銷大、數據映射過程難以監控等問題，因此本文希望結合聚類算法降低降維的復雜度。

2.2 聚類算法

2.2.1 層次聚類

該算法將維度定義為類別，每維度為一類，將距離最小的兩個類合并為一類，多次循環直到類別數滿足預設值；其關鍵在于距離公式的定義，可分為最小距離、最大距離和平均距離等。

2.2.2 k-means聚類

迭代算法，初始時隨機選取k個樣本作為聚類中心，將維度相似的數據分為同一類別，通過多次迭代不斷更新聚類中心，直到收斂。

2.2.3 SOM神經網絡

無監督聚類方法，無需輸入參數，訓練后由輸出層計算聚類數。SOM的結構中，輸入層神經元個數與維度或樣本數相關，最大為屬性數。算法結果受到輸入數據順序的影響。其主要過程為：先進行數據歸一化處理，將距離輸入最近的輸出層神經元選為優勝，更新其權值和學習率，直到預設條件滿足位置。

3 實驗與結果分析

本文將分類性能作為標準驗證降維算法的有效性，使用SVM作為分類算法。采用Matlab的Heart Scale與UCI的VOTE、GERMAN數據集，尺寸分別為270*13，453*16和1 000*24，均攜帶標簽。實驗中采用了分層降維框架，在聚類的基礎上先進行第1次類內降維，降維后合并數據，維度增加，再進行第2次類間降維。降維方法包括：PCA、LDA、KPCA、MDS、ISOMAP、SNE和t-SNE；聚類方法包括k-means和層次聚類。LLE算法的分類準確率偏低，故實驗中舍棄。方案性能取10折驗證的平均結果。

表1為Heart Scale數據集上的分類結果，可見LDA與聚類結合的方案相比原有降維方案，準確率有明顯提高；對SNE和t-SNE算法而言，由于部分維度在聚類過程中合并丟棄，精度略有降低。在Heart Scale這一數據間線性關系明顯的數據集上，k-means+PCA的分類準確率最高。

表2為VOTE數據集分類結果，由于數據存在流形結構，部分非線性降維算法在結合聚類方法后準確率一定提高，如SNE和t-SNE。同時可觀察到，聚類算法，以及分層降維的操作對降維用時的影響相比表1有所降低。在VOTE數據集上，層次聚類+KPCA的表現較好。

表3為GERMAN數據集分類結果，可以看到幾種方案的分類準確率相比單獨的降維算法都有一定的提高，且分層降維的用時影響進一步減小，部分方案的時間甚至少于原始降維方案；可以初步判斷，若未來數據集進一步增長，分層降維框架有助于減少降維的總時間開銷。在GERMAN數據集上，層次聚類+ISOMAP取得了最高的分類準確率。

表1 Heart Scale數據集分類結果

表2 VOTE數據集分類結果

表3 GERMAN數據集分類結果

此外，本文使用自組織映射神經網絡對聚類參數進行預估，用于后續的k-means和層次聚類，用以解決傳統聚類參數無法自適應的問題；但實驗結果表明，算法穩定性略微提高，但處理效率大大下降，不符合本文初衷，故放棄此方案。

4 結論

降維算法是解決維數災難的關鍵，可分為線性和非線性降維。本文分析并驗證了主流降維算法的性能，通過分類準確率驗證數據結構在降維中的保留程度。提出了基于聚類的分層降維框架，結合聚類和降維算法，分層實現類內降維和類間降維。實驗結果表明，當數據集規模較大時，盡管聚類算法會帶來額外的時間開銷，分層降維框架的總用時仍然接近或低于未采用聚類時的降維用時。

未來的研究方向包括：（1）數據集規模進一步增加時，或流形結構復雜度提高時該框架的適用性；（2）如何改善聚類算法參數的穩定性；（3）可考慮針對行業不斷增加的數據規模設計增量處理機制。

[1] 閆德勤,劉勝藍,李燕燕.一種基于稀疏嵌入分析的降維方法[J].自動化學報,2011,37(11):1306-1312.

[2] 趙孝禮,趙榮珍.全局與局部判別信息融合的轉子故障數據集降維方法研究[J].自動化學報,2017,43(4):560- 567.

[3] 唐科威,劉日升,杜慧,等.一種基于張量和洛侖茲幾何的降維方法[J].自動化學報,2011,37(9):1151-1156.

[4] 劉勝藍,閆德勤.一種新的全局嵌入降維算法[J].自動化學報,2011,37(7):828-835.

[5] 李海林,楊麗彬.時間序列數據降維和特征表示方法[J].控制與決策,2013,28(11):1718-1722.

[6] Lotlikar R, Kothari R. Fractional-step dimensionality reduction[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2016, 22(6): 623-627.

[7] Shi J, Jiang Q, Zhang Q, et al. Sparse kernel entropy component analysis for dimensionality reduction of biomedical data[J]. Conf Proc IEEE Eng Med Biol Soc, 2015, 168(C): 930-940.

[8] Sim? O M, Neto P, Gibaru O. Using data dimensionality reduction for recognition of incomplete dynamic gestures[J]. Pattern Recognition Letters, 2017, 11(25): 32-38.

[9] Fan, Mingyu, Gu, Nannan, Qiao, et al. Dimensionality reduction: An interpretation from manifold regularization perspective[J]. Information Sciences, 2014, 277(8): 694-714.

[10] Ding C, Berkeley L, Li T. Adaptive Dimension Reduct- ion Using Discriminant Analysis and K -means Clustering[A]. ACM. Poceedings of the 24th Inter- national Conference on Machine Learning[C]. Corvallis, OR: ACM, 2007: 522-528.

[11] 曾蔚.基于用戶行為聚類的個性化推薦算法研究[J].唐山師范學院學報,2016,38(5):81-84.

[12] 王森,魏旭穎.網絡社會場系統的安全評估中專家權重樣本的處理方法[J].唐山師范學院學報,2017,39(2): 11-14,27.

[13] 詹勝,周樹功,母景琴.聚類分析方法在基于分布式PLC數據采集的連鑄坯定尺定重切割中的應用[J].唐山師范學院學報,2013,35(5):33-36.

[14] Antoniadis A, Lambert-Lacroix S, Leblanc F. Effective dimension reduction methods for tumor classification using gene expression data[J]. Bioinformatics, 2015, 4(18): 21-29.

[15] Laohakiat S, Phimoltares S, Lursinsap C. A clustering algorithm for stream data with LDA-based unsuper- vised localized dimension reduction[J]. Information Sciences, 2017, 381(3): 104-123.

Hierarchical Dimension Reduction FrameworkBased on Clustering

CHEN Xin-yuan1,2, XIE Sheng-yi3

(1. College of Computer and Control Engineering, Minjiang University, Fuzhou 350121, China; 2. Department of Information Engineering, Fuzhou Melbourne Polytechnic, Fuzhou 350121, China; 3. Experimental Training Center, Fujian Vocational College of Agriculture, Fuzhou 350181, China)

By analyzing and verifying the performance of mainstream dimension reduction algorithms, a hierarchical dimension reduction framework based on clustering algorithms was proposed, which combined clustering and dimensionality reduction to realize the processing mechanism of dimensionality reduction within and between classes respectively. Experimental results of time efficiency show that this framework bears some advantages over the original dimension reduction scheme as data volume increases.

multiple dimensional data; dimension reduction; clustering; stratification; classification accuracy

TP18

A

1009-9115(2020)03-0078-05

10.3969/j.issn.1009-9115.2020.03.019

福建省中青年教師教育科研項目（JAT160316）

2020-01-03

2020-04-04

陳新元（1984-），男，福建福州人，碩士，講師，研究方向為機器學習、知識圖譜。

（責任編輯、校對：田敬軍）