新的降維標準下的高維數據聚類算法*

萬 靜，吳 凡，何云斌，李 松

哈爾濱理工大學 計算機科學與技術學院，哈爾濱150080

1 引言

高維數據聚類是在圖像分析和基因探索等領域常見的課題[1]，它的主要目的是對大量未標注的數據集按照數據的內在相似性劃分簇，使簇內相似度盡可能大，簇間相似度盡可能小[2-3]。目前高維數據對聚類算法提出了兩個挑戰：首先不相關的特征和噪聲數據會對聚類算法產生誤導；其次受維災的影響，使高維數據點變得稀疏，從而很難在數據中發現任何結構[4-5]。現在針對這個問題的解決方案主要包括子空間聚類和降維技術[6]。子空間聚類方法是有效地抽取出存在于子空間的簇，經典算法有投影尋蹤聚類（projected clustering，PROCLUS）算法[7]、熵加權軟子空間聚類（entropy weighting subspace clustering，EWSC）算法[8]和聚類高維空間（clustering in quest，CLIQUE）算法[9]。降維技術是通過特征選擇或者特征變換將高維數據空間歸約到低維空間，主要算法有主成分分析（principal component analysis，PCA）[10]算法等。

國內外學者針對高維數據聚類做了一系列的研究。Azizyan 等人[11]在過濾式特征選擇的基本框架下提出了新的篩選步驟來消除信息不足的特征，并在此基礎上進行了特征密度的模式聚類，從而得到了聚類結果。新的篩選方法為多模態測試，對每個特征的邊緣分布進行測試從而確定特征的信息量。該算法的理論證明較為清晰，算法通用性較強，時間復雜度較低，可以處理大規模數據。但是由于篩選標準脫離聚類算法導致算法的準確率難以保證。Ge 等人[12]將數據歸一化后構造最近鄰矩陣，計算評估數據最近鄰數的逆近鄰指數，將PCA 算法的最大方差標準改為通過逆近鄰指數構造的偏度標準，最終在降維后采用hub 聚類法。這個方法消除了hub 聚類算法對噪聲和冗余數據的敏感性，增加了聚類算法的準確性。但是當數據維數很高時受維災的影響導致鄰矩陣的生成是非常不準確的。Dash 等人[13]在面對高維數據聚類時將數據分為數字數據和屬性數據，前者采用歐式距離，后者采用海明距離，得到距離結果后與信息熵結合構造出新的特征評價函數，評價某一維的信息量來消除冗余特征后再聚類，最后通過隨機樣本的方法改進算法的伸縮性，這個方法能夠在最大限度保留數據信息的基礎上完成數據的降維和聚類。Tinós 等人[14]提出了一種用于聚類的NK混合遺傳算法，混合算法采用NK聚類驗證準則2（NKclustering validation criterion 2，NKCV2），NKCV2使用N個小對象組的配置信息，每個組由數據集的K+1 個對象組成，在NKCV2 中，使用固定的k可以識別基于密度的區域，算法給出了決策變量之間的關系、變異因子、分塊交叉（partition crossover，PX）和局部搜索策略。在PX 中，將評價函數分解為q個獨立的分量，PX 確定地返回后代中可能的最佳值，NK混合算法可以檢測到任意形狀的簇，并且能自動評估簇。算法提高了聚類的應用范圍，但是遺傳算法固有的時間復雜度過高問題依舊沒有解決。

本文針對高維數據，將PCA 算法中映射到低維空間的方差最大化[15]標準改進為一種基于新的特征度量的信息熵[16]標準，使降維后的數據有更好的分布特性，使其更利于聚類算法，實驗證明新算法執行后再聚類結果的準確率比PCA 算法有明顯的提升。由于降維結果中參數非零值過多而導致解釋性變差的問題，提出了基于嶺回歸[17]的稀疏主成分算法[18]，并通過坐標下降法得出了算法的解。最后通過改進的遺傳算法[19]對數據進行聚類，算法改進交叉等操作[20]降低了算法的時間復雜度，并且具有較高的精度。

2 基本定義與說明

定義1（屬性空間）給出包含維度為p的n個數據點的高維數據集D={x1j,x2j,…,xij,…,xnj},0 ＜j≤p,0 ＜i≤n。對數據集D轉換后，將包含p個屬性對象的集合稱作屬性空間，記為T，T={t1i,t2i,…,tji},0 ＜j≤p,0 ＜i≤n，其中每個屬性對象與屬性特征一一對應。

屬性空間與數據空間的區別在于屬性空間中的點是抽象屬性的具象化，也就是說屬性成為了空間中的點。這樣做可以更加直觀地看到各屬性間的分布情況，屬性空間的理論與數據空間到屬性空間的轉換方法在3.1 節有詳細的解釋。

定義2（屬性距離）根據定義1，給出特征對象t1=(t11,t12,…,t1n)與特征對象t2=(t21,t22,…,t2n)，則兩個特征對象的屬性距離為：

通過屬性空間，可以很容易看到屬性的遠近程度，而屬性距離可以具體測量出屬性間的遠近。

定義3（屬性相似度）給出兩個特征對象t1和t2的屬性距離，則可以得到兩特征之間的屬性相似度，記為。

屬性相似度建立在屬性距離的基礎上，α通過自動計算，其中是特征距離的平均值，而與定義4 有關，當屬性相似度為時，屬性空間信息熵最大，此時，于是，α的作用是防止屬性距離波動過大對屬性相似度造成不良的影響。例如當特征距離過小時，α的存在防止屬性相似度分布過于陡峭，使屬性相似度在區間(0,e-α]內均勻分布。

定義4（屬性空間信息熵）給定一個屬性空間T={t1i,t2i,…,tji}，0 ＜j≤p,0 ＜i≤n,則可以得到屬性空間信息熵，其定義為：

其中，t1和t2為屬性空間中的任一特征對象。

定義5（entropy-variance，E-VAR 標準）給定一個屬性空間T={t1i,t2i,…,tji},0 ＜j≤p,0 ＜i≤n，則E-VAR標準定義為，其中ET為選取的部分屬性特征集合的屬性空間信息熵，var是集合中特征對應的特征值的和。

協方差矩陣求解后特征值與映射到此特征數據的方差一一對應并且可排序，于是用特征值的和代替方差可以反映數據的方差情況。λ1和λ2為經驗參數，實際應用中根據方差和信息熵的比例而調節。

定義6（總類內相似度）給出n個存在類標簽的數據，類總數為K，任選其中一個類，編號為k，類中心記為ck，則對于所有數據中的任一數據點xi，0 ＜i≤n來說，存在成立，1 代表數據點在類k內，0 代表不在。于是類k的類內相似度記為Sk，，進一步得到總類內相似度為T(Sk)=。

定義7（選擇函數）給出總類內相似度T(S)，可以得到選擇函數，記為F(S)，其公式為。

定義8（CM 操作（cluster manipulate））給出的染色體串s={k1,k2,…,kn}，ki∈{1,2,…,K}，其中ki表示聚類中心，表示第i個類中數據量的大小，數據點xi∈ki，則CM 操作定義為對s重新計算聚類中心，即每個。

3 面向聚類的PCA 降維方法EN-PCA

PCA 算法根據方差最大化理論使得投影后方差最大，從而使得映射到低維空間的數據點之間較為分散，與此同時也導致降維后數據的聚類精度有所下降，不能獲得好的聚類效果。例如當數據點分布如圖1 所示時，圖中有9 個數據點記為{x1,x2,…,x9},投影到x軸的坐標記為，投影到y軸的坐標記為，如果存在降維需求時，投影到y軸的數據方差，同時得到映射到x軸的數據方差var(x)≈1.58，可以看到var(y)＞var(x)。根據PCA 算法降維理論，數據點應該映射到y軸，但是圖中可以明顯看到只有當數據點映射到x軸后才能獲得更好的聚類效果，組成簇集C1、C2和C3。

Fig.1 Clustering effect after dimensionality reduction圖1 降維后聚類效果

針對以上問題，本文在方差最大化理論的基礎上拓展信息熵理論，基于PCA 算法構造新的降維標準，使其能更好地適應高維數據降維后聚類的需求。本章首先給出數據空間轉換到屬性空間的基本理論方法，緊接著提出了新的降維標準并給出了具體的算法和時間復雜度分析。

3.1 數據空間到屬性空間

與屬性空間相對的數據空間以屬性為坐標度量，空間中的點為數據對象。而本文提出的屬性空間將數據對象作為坐標度量，屬性為空間中的點，屬性點的集合構成了屬性空間。從數據空間轉換到屬性空間就是將數據對象作為空間中的坐標尺度，屬性成為空間中的點，坐標為對應坐標軸上數據在此屬性上的值。

如圖2 所示，在三維數據空間中存在兩個數據點x1=(5,5,1)，x2=(4,5,4)，x1和x2分別有3 個特征，分別記為x、y和z。將圖2（a）的數據空間轉換成一個屬性空間：首先將x1和x2作為屬性空間的橫縱坐標軸，屬性空間中的點分別為x、y和z，則特征屬性x的坐標為(5,4)，y的坐標為(5,5)，z的坐標為(1,4)，于是可以得到圖2（a）的屬性空間為圖2（b）。通過對比圖2（a）和圖2（b）可以發現，在數據空間圖2（a）中很難發現屬性間的遠近關系，但是轉換到屬性空間圖2（b）后，可以很直觀地看到屬性x與y距離較近，而它們都與z距離較遠。如果存在屬性約簡需求，x與y的組合并不能很好地區分數據，而屬性z與x和y中任一屬性的組合都可以反映數據間的區別性。

Fig.2 Data space to attribute space圖2 數據空間到屬性空間

將數據空間轉換到屬性空間存在兩個直觀的問題，首先由于屬性的量綱不同而導致屬性點在屬性空間中分布不均勻，這樣就不能很好地反映屬性間的關系，也不能度量屬性的相似度。其次當數據量很大時，屬性空間維度也會變大，從而引發一系列高維問題。

針對問題一可采用歸一化的處理方式，將各個特征量化到統一的區間，運用標準化的方法，其中pi和表示歸一化前和后的特征，μ表示特征的均值，δ表示特征的標準差。經過標準化后特征將分布在[-1,1]區間內，并且服從標準正態分布，為了讓屬性點分布得更加均勻，可以將特征分布區間擴大n倍，得到新的特征分布區間為[-n,n]。針對第二個問題的解決方法是抽取部分數據參與屬性空間的建立，抽取方案為選擇典型數據點。具體做法有兩種：第一種是按比例選取數據點，但顯然這樣的選取方式并不能確保數據的典型性；第二種方法中數據點的選取方式為在第一種方法的基礎上加入剔除特征為0 值過多的數據點，具體做法為當為0 的特征值數量占總特征的比例大于預設閾值則剔除此數據點。

3.2 新的降維算法

屬性空間是對屬性特征的具象化，能更加直觀地觀察出屬性的分布情況以及屬性間的相似度，但是屬性相似度是度量兩個特征間相似程度的工具。當需要度量整個屬性空間的分布情況時，需要有更好的度量方式，于是信息熵是本文的解決方案。由于信息熵是通過數據的概率分布情況來反映數據不確定性的一種手段，那么對于屬性點來說，通過信息熵依舊可以反映出特征屬性的不確定性，而不確定性又決定了特征屬性的價值。

為信息熵的初始定義，其中p(f1,f2,…,fm) 是在點(f1,f2,…,fm)的概率。由于并沒有分布的先驗信息導致概率分布不能直接得到，于是本文將屬性相似度引入到信息熵中得到屬性空間信息熵，如定義4 所示，其分布與單調情況和信息熵的初始定義近似。通過信息熵理論可知，屬性空間信息熵可以反映特征的相似情況，比僅考慮方差對于特征的分布情況描述得會更加準確。

如果僅將屬性空間信息熵作為PCA 算法的降維標準，有時在得到降維數據后再聚類雖然可以獲得較好的聚類結果，但是當降維屬性不能很好地反映原數據的分布情況或者信息時，聚類結果的意義就會減弱。于是為了讓降維后的數據可以更好地服務于聚類算法，并且聚類結果依然能反映出原高維數據真實的分布情況，定義4 構建了新的降維標準EVAR，新的標準融合了屬性空間信息熵的同時也將反映數據分布情況的方差度量加入其中，使E-VAR 標準成為一個較為完善的降維標準。

基于以上的理論分析，算法的主要過程和計算步驟可以得出：輸入數據矩陣An×p，包含了n個p維的數據，矩陣的每一個元素表示為aij（0 ＜j≤p，0 ＜i≤n)。首先需要對數據矩陣的列去中心化處理，消除特征之間的量綱，具體做法為矩陣的每一個元素減去列的均值：固定j，得到，其中。去中心化處理后，計算A的協方差矩陣，，由于Dcov為方陣，于是選擇公式法求解得到Dcov的特征值為λ1,λ2,…,λn，對應的特征向量分別為α1,α2,…,αn，對特征值排序得到由大到小的特征值序列為。由于特征值與方差一一對應，根據特征值選擇降維后特征數量k的大小，保證（經驗參數）前提下的k值。EN-PCA 算法是在p個特征中選擇k個特征，k個特征必須滿足E-VAR 最大才能獲得好的降維效果，于是算法在p個特征中遍歷計算，在得到最大E-VAR標準時選擇對應的特征向量。最后將矩陣A與矩陣相乘得到降維后的數據矩陣。具體算法如算法1 所示。

算法的時間復雜度分析：算法在第2 步去中心化處理，需要計算n次，此步的時間復雜度為O(n)。在第3 步計算協方差矩陣時間復雜度為O(p2n)，步驟4在進行特征值分解時需要p3次運算，時間復雜度為O(p3)，在6～10 步遍歷選擇特征值及計算E-VAR 的值，獲得最大值最多需要遍歷n次，每次計算E-VAR 值p2次，故時間復雜度為O(p2n)，最后求得降維后矩陣W，因此算法的總時間復雜度為O(p2n)。與經典PCA算法時間復雜度一致，但是由于新的降維標準存在額外操作，EN-PCA算法會比PCA算法時間消耗多一些。

何守二一聽這個，知道權箏媽不是善茬兒，態度變緩：“放心，我不會跟何東說的，跟他父母也不會提。”心里話，我招這事干嘛？

4 基于嶺回歸的稀疏主成分算法ESPCA

EN-PCA 算法得到的主成分間互不相關，是原特征的線性組合，線性組合中的因子載荷往往是非零的，這些非零因子載荷使得降維特征很難被解釋。針對這個問題，本文提出了基于主成分結果的稀疏主成分算法（sparse principal component algorithm based on ridge regression，ESPCA）。算法在嶺回歸的基礎上，對回歸方程施加l1范數約束，通過使系數向0 收縮[21]的方式，獲得稀疏主成分結果，增加主成分結果的可解釋性。

嶺回歸是對不適定問題進行回歸分析時最常用的一種正則化方法，其極值求解函數表達形式為，其中λ是控制收縮量的參數，λ值越大，收縮量越大，系數越向0 收縮[22]。

下面定理1 證明了主成分結果與嶺回歸結合的正確性。

定理1給出數據矩陣Xn×p,令Yi=UiDi,Yi為第i個主成分，存在嶺回歸，其中V={vi}，是解的集合。

證明首先明確0 ＜λ時嶺回歸有效，對X矩陣分解后可得到XXT=VD2VT，且VVT=I，將嶺回歸的表達式寫成矩陣形式為：

于是對這個極值表達式求導后得到：

通過定理1 證明了將回歸方法與主成分聯系起來的正確性，但是定理1 的輸入為數據矩陣，從而直接得到稀疏結果，但是對于ESPCA 算法來說需要輸入的是主成分降維后的結果，于是得到其回歸表達式為，其中Y是輸入的降維矩陣，X為數據矩陣，λ是控制V收縮的非負參數，λ值越大，系數越會趨向0，于是將稀疏問題轉換為變量選擇問題。但是通過嶺回歸的特性得知：其主要用于解釋自變量與因變量之間的數量關系，并且當輸入中存在多個相關變量時，它們的系數確定性會變差，并且呈現高方差性，嶺回歸可以避免這種情況。

于是為了得到稀疏的主成分，本文在嶺回歸的基礎上，施加了l1范數的約束條件，通過加入l1范數約束，使各系數的絕對值之和小于某一常數，由于l1范數約束的自然屬性，使添加了l1范數的模型得出的結果中有的系數會為0，因此可以得到稀疏的主成分。綜上所述在嶺回歸約束的基礎上添加l1范數約束會將稀疏屬性帶到約束模型中，同時嶺回歸分析的穩定性也為稀疏化提供了保障。因為如果僅存在l1范數，當數據矩陣的特征數大于降維后數據矩陣時，會導致結果過于稀疏，大量信息會因此損失。

ESPCA 算法輸入的k個主成分表示為，i=1,2,…,k，為了得到稀疏主成分，利用施加l1范數的嶺回歸可以使系數自動縮減為0 的特點，用稀疏主成分Xvi擬合主成分可以得到k個獨立的嶺回歸問題：

可以看出只要分別求解k個嶺回歸問題就可以得到稀疏載荷解V=(v1,v2,…,vk)，于是接下來在求解（1）問題時采用坐標下降法。

坐標下降法在當前點沿某一坐標方向進行一維搜索，同時固定其他坐標方向，從而求解函數的極小值。對于任意的α∈R,λ＞0,代表函數-αx+λ|x|的最小值點，其中lλ(α)的值取決于α和λ值的大小，即：

對于問題（1）而言，運用坐標下降法對第i個分量vi求解時，需要固定vj(j≠i)的值不變，于是相當于求解，其中，則根據式（2）的劃分得到vi的解為：

基于以上分析，兩階段算法的第一段獲取主成分結果可以在EN-PCA 算法降維后得到，再根據嶺回歸函數施加對k成分的約束后得到k個獨立的嶺回歸問題，對于每個問題的解可以通過解（3）得到稀疏結果，循環k次后得到k個主成分的稀疏解，最后標準化每個解后返回結果。如算法2 所示：

算法時間復雜度分析：第2 步算法對k個主成分進行稀疏化處理，時間復雜度是O(n)，第3～4 步算法求解約束函數，對于每一個主成分梯度下降的運算次數是p次，時間復雜度是O(p)，于是求解k個主成分的稀疏化算法時間復雜度是O(np)，第5 步標準化vi執行k次，時間復雜度是O(n)，因此ESPCA 算法的時間復雜度是O(np)。因為ESPCA 具有不需要迭代的特點，所以與其他稀疏主成分算法相比時間消耗要低。

5 基于遺傳算法聚類的改進算法GKA++

上文通過改進PCA 算法將高維數據進行了降維處理，并稀疏化了主成分結果，接下來需要對降維后數據進行聚類。本文提出了一種新的基于遺傳的聚類方法。由于初始種群選擇是隨機生成的，并且選擇和變異操作是基于概率式的選擇，在選擇操作時采用的輪盤法并不能保證最優個體一定會被選擇到，因此當遺傳算法中數據量很大時，可能會導致算法的耗時過大。

GKA++算法對選擇操作進行了改進，并保留了最優個體，使其始終參與進化，改進了變異操作，對離某聚類中心較近，但是還未在類內點的個體賦予較大的變異概率，使其變異為此類內點，最后去除了遺傳算法中復雜的交叉操作，改進為重新計算聚類中心（CM 操作），更新染色體，使其更加適用于聚類算法。

算法首先論證了遺傳算法中核心的適應度函數的正確性，接著詳細介紹了算法的編碼、初始化、選擇、變異和CM 操作，最后給出了算法流程。

定理2適應度函數是反映種群聚類質量的標準。

證明當類內的數據點i與當前聚類中心的距離lki（k代表類編號，i代表數據編號）大于到其他聚類中心k′(k′≠k)的距離lk′i時，數據i一定屬于類k，即lki

對全體對象編碼，這會讓算法的計算更加方便。其中編碼方式分為浮點數編碼和二進制編碼。如果是二進制編碼，那么染色體的長度會隨著維數的增加或者精度的提高而顯著上升，這樣做會使搜索空間變得很大，于是本文采用浮點數編碼。給出數據對象集合X，元素為xi，并且聚類數目為K的集合來說，染色體結構為s={k1,k2,…,kn}，ki∈{1,2,…,K}，其中s是包含n個元素的數組，每一個元素在數組中的位置代表數據的標號，元素ki的值是數據所屬的類標號k。

種群初始化：由于遺傳算法對初始點不敏感，算法采用隨機選擇初始點，初始種群記為p(0)，，將初始種群的每一個個體基因隨機賦值為類標號，并且不允許有類內數據為空，即。

選擇操作：定理2 證明F(S)選擇函數的正確性，個體適應度越高，參與后代繁殖的概率就越大。算法在選擇個體的時候采用了輪盤的方法，為了防止最優個體沒有被選擇到，選擇操作加入了最優策略保存法，具體操作如下：首先計算當前種群中個體的適應度，保存適應度最大的個體，計算個體被選擇的概率，再根據個體被選擇的概率，使用輪盤法選出下一代個體，最后當下一代個體進行完交叉、變異后，用保存的最優個體替換掉下一代的最差個體。

變異：經典的遺傳算法變異是隨機方向的變異，但是在GKA++算法中，變異是朝著結果的變異，于是變異操作根據每個數據對象與聚類中心的距離對個體中相應的基因值進行改變。如果一個對象距離某個聚類中心比較近，那么對象對應的個體基因變異為這個類的編號的概率就比較高，這樣可以使種群向更優的方向進化，提高算法的效率。于是對于對象i，對應的基因表示為G(i)，變異概率記為pi，dmax表示到所有中心點最大的距離，dj表示i到某個聚類中心j的距離，則變異概率，其中c為大于1 的常量，pi∈(0,1)。

基于以上理論，GKA++算法如算法3 所示。

算法時間復雜度分析：在第1 步初始化時對n個對象隨機賦予基因編號，時間復雜度O(n)。第2 步為算法的整體循環。第3～8 步為選擇操作，對每一個對象計算適應度函數值和選擇概率n次，并選擇出M個下一代遺傳個體，時間復雜度為O(n)。第9～12 步為變異操作，K個聚類中心計算變異概率最大的點k次，對于每一個中心需要遍歷n個點，則時間復雜度為O(Kn)。第13～17 步為CM 操作，n個點重新計算中心需要n×K次操作，時間復雜度也是O(Kn)，最后結束迭代次數循環，最大的循環次數為GKn，于是基于以上分析，算法的時間復雜度為O(GKn)。

本文通過EN-PCA 算法完成了對高維數據的降維操作，使降維后的數據更加適用于聚類算法。ESPCA 算法通過稀疏主成分的解，解決了降維后數據可解釋差的問題，通過前兩個算法的處理得到了較好的降維數據，GKA++改進了基于遺傳算法的聚類算法，使其更加高效，更加準確。圖3 為本文的算法設計思路。

Fig.3 Clustering process after data reduction圖3 數據降維后聚類流程

6 實驗

為了驗證文章算法的有效性，實驗分析在Intel Core i5 2.5 GHz 和8 GB 內存的PC 機上進行，操作系統為Windows 10，實驗程序采用Python 語言編寫。數據集采用UCI數據集，詳情如表1 所示。

Table 1 UCI data set表1 UCI數據集

實驗主要反映了當樣本數、特征數變化時，CPU運行時間以及聚類準確率等方面的變化情況，并加入了聚類純凈度P(C)和聚類熵E(C)的質量評價指標[23]。由于數據集為分類數據，可以通過結果與分類標簽對比來計算準確率。

實驗選擇PCA 降維算法加K-means 聚類算法、基于歐式距離的降維算法加K-means 聚類算法與本文的EN-PCA 降維算法加GKA++聚類算法的組合互相對比聚類結果，以此來驗證EN-PCA 算法的有效性和效率，驗證結果均已給出。

如圖4 所示，算法聚類純凈度隨著樣本數的增加而緩慢減少。可以看到，數據量對算法的影響并不大，其中PCA 降維后對聚類的效果最差，對后續聚類操作影響最大，而EN-PCA 算法和GKA++算法均可以獲得較好的聚類純凈度。

Fig.4 Effect of sample number on P(C) value圖4 樣本數對P(C)值的影響

Fig.5 Effect of sample number on E(C) value圖5 樣本數對E(C)值影響

圖5 顯示了聚類熵隨著樣本數增加的變化情況，聚類熵越接近0，則表示聚類簇越均勻分布。從實驗圖可以看到EN-PCA 與GKA++算法的組合隨著數據量的增加，E(C)值始終在Euclid 和K-means，PCA 和K-means 算法之上，表現了良好的降維和聚類的穩定性，并且由于GKA++算法的全局能力，E(C)值隨著數據量的增加而保持穩定。

如圖6 所示，實驗圖表示的是特征數對聚類純凈度的影響，可以看到在高維數據下，EN-PCA 算法隨著特征數的增加并沒有出現明顯的下滑，保持了對高維數據降維和聚類的有效性。

Fig.6 Effect of feature number on P(C) value圖6 特征數對P(C)值的影響

圖7 也揭示了隨著特征數的增加E(C) 在ENPCA 和GKA++算法上影響最小。可以看到，由于維災的影響，Euclid 算法隨著特征數的增加，聚類效果呈大幅下滑。

如圖8 所示，折線圖顯示了當特征數量變化時，降維后再聚類結果的準確率。從圖中可以看到，隨著特征數的上升，EN-PCA 和GKA++算法、PCA 和Kmeans 算法與Euclid 和K-means 算法的準確率都有所下降，但是由于EN-PCA 算法是針對聚類的降維，因此準確率一直居于首位。

Fig.7 Effect of feature number on E(C)value圖7 特征數對E(C)值的影響

Fig.8 Effect of feature number on accuracy圖8 特征數對準確率的影響

從圖9 可以看出，樣本數的增大對聚類的準確率有很大的影響。EN-PCA 算法與GKA++算法的組合具有很高的準確率，但是隨著樣本數的增加準確率也有所下降，Euclid 與K-means 算法由于算法的缺陷導致隨著樣本數的增加，準確率急劇下降。

Fig.9 Effect of sample number on accuracy圖9 樣本數對準確率的影響

圖10 顯示了當特征數量上升的時候，CPU 運行時間的變化情況。從中可以看到EN-PCA 算法的運行時間比PCA 算法的運行時間會多一些，并且都隨著特征數量的增加而持續上升，其中Euclid 算法的運行時間隨著特征數量的增加運行時間呈指數上升。

Fig.10 Effect of feature number on CPU runtime圖10 特征數對CPU 運行時間影響

綜上所述，樣本數量和特征數量都對聚類結果產生了很大的影響。本文提出的EN-PCA 算法和GKA++算法在聚類純凈度和聚類熵的標準下，實驗表現要優于其他兩個算法組合。由于EN-PCA 算法在標準中引入了信息熵的降維標準，使得算法在樣本數增加和特征數增加的情況下依然可以保持良好的降維效果，同時GKA++聚類算法消除了遺傳聚類算法在種群初始化、選擇、變異等操作的問題，并且有更好的聚類效果。

7 結束語

隨著新技術層出不窮的發展，高維數據越來越成為聚類算法的難點，本文針對高維數據聚類將經典的PCA 算法中方差最大化標準改為E-VAR 標準，提高了降維的準確性，使降維后數據能更好地聚類。同時針對降維后數據線性組合參數過多的問題，本文提出了基于嶺回歸的稀疏算法，對約束采用梯度下降法求解，使其可解釋增強。最后在遺傳算法的基礎上，針對收斂問題提出了新的聚類算法，該算法為以后應用遺傳算法聚類提供了參考。