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

哈爾濱理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150080

1 引言

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

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

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

2 基本定義與說明

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

屬性空間與數(shù)據(jù)空間的區(qū)別在于屬性空間中的點(diǎn)是抽象屬性的具象化，也就是說屬性成為了空間中的點(diǎn)。這樣做可以更加直觀地看到各屬性間的分布情況，屬性空間的理論與數(shù)據(jù)空間到屬性空間的轉(zhuǎn)換方法在3.1 節(jié)有詳細(xì)的解釋。

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

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

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

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

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

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

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

協(xié)方差矩陣求解后特征值與映射到此特征數(shù)據(jù)的方差一一對應(yīng)并且可排序，于是用特征值的和代替方差可以反映數(shù)據(jù)的方差情況。λ1和λ2為經(jīng)驗(yàn)參數(shù)，實(shí)際應(yīng)用中根據(jù)方差和信息熵的比例而調(diào)節(jié)。

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

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

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

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

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

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

針對以上問題，本文在方差最大化理論的基礎(chǔ)上拓展信息熵理論，基于PCA 算法構(gòu)造新的降維標(biāo)準(zhǔn)，使其能更好地適應(yīng)高維數(shù)據(jù)降維后聚類的需求。本章首先給出數(shù)據(jù)空間轉(zhuǎn)換到屬性空間的基本理論方法，緊接著提出了新的降維標(biāo)準(zhǔn)并給出了具體的算法和時間復(fù)雜度分析。

3.1 數(shù)據(jù)空間到屬性空間

與屬性空間相對的數(shù)據(jù)空間以屬性為坐標(biāo)度量，空間中的點(diǎn)為數(shù)據(jù)對象。而本文提出的屬性空間將數(shù)據(jù)對象作為坐標(biāo)度量，屬性為空間中的點(diǎn)，屬性點(diǎn)的集合構(gòu)成了屬性空間。從數(shù)據(jù)空間轉(zhuǎn)換到屬性空間就是將數(shù)據(jù)對象作為空間中的坐標(biāo)尺度，屬性成為空間中的點(diǎn)，坐標(biāo)為對應(yīng)坐標(biāo)軸上數(shù)據(jù)在此屬性上的值。

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

Fig.2 Data space to attribute space圖2 數(shù)據(jù)空間到屬性空間

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

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

3.2 新的降維算法

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

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

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

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

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

何守二一聽這個，知道權(quán)箏媽不是善茬兒，態(tài)度變緩：“放心，我不會跟何東說的，跟他父母也不會提?！毙睦镌挘艺羞@事干嘛？

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

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

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

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

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

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

于是對這個極值表達(dá)式求導(dǎo)后得到：

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

于是為了得到稀疏的主成分，本文在嶺回歸的基礎(chǔ)上，施加了l1范數(shù)的約束條件，通過加入l1范數(shù)約束，使各系數(shù)的絕對值之和小于某一常數(shù)，由于l1范數(shù)約束的自然屬性，使添加了l1范數(shù)的模型得出的結(jié)果中有的系數(shù)會為0，因此可以得到稀疏的主成分。綜上所述在嶺回歸約束的基礎(chǔ)上添加l1范數(shù)約束會將稀疏屬性帶到約束模型中，同時嶺回歸分析的穩(wěn)定性也為稀疏化提供了保障。因?yàn)槿绻麅H存在l1范數(shù)，當(dāng)數(shù)據(jù)矩陣的特征數(shù)大于降維后數(shù)據(jù)矩陣時，會導(dǎo)致結(jié)果過于稀疏，大量信息會因此損失。

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

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

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

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

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

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

5 基于遺傳算法聚類的改進(jìn)算法GKA++

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

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

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

定理2適應(yīng)度函數(shù)是反映種群聚類質(zhì)量的標(biāo)準(zhǔn)。

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

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

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

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

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

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

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

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

Fig.3 Clustering process after data reduction圖3 數(shù)據(jù)降維后聚類流程

6 實(shí)驗(yàn)

為了驗(yàn)證文章算法的有效性，實(shí)驗(yàn)分析在Intel Core i5 2.5 GHz 和8 GB 內(nèi)存的PC 機(jī)上進(jìn)行，操作系統(tǒng)為Windows 10，實(shí)驗(yàn)程序采用Python 語言編寫。數(shù)據(jù)集采用UCI數(shù)據(jù)集，詳情如表1 所示。

Table 1 UCI data set表1 UCI數(shù)據(jù)集

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

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

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

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

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

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

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

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

圖7 也揭示了隨著特征數(shù)的增加E(C) 在ENPCA 和GKA++算法上影響最小?？梢钥吹剑捎诰S災(zāi)的影響，Euclid 算法隨著特征數(shù)的增加，聚類效果呈大幅下滑。

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

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

Fig.8 Effect of feature number on accuracy圖8 特征數(shù)對準(zhǔn)確率的影響

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

Fig.9 Effect of sample number on accuracy圖9 樣本數(shù)對準(zhǔn)確率的影響

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

Fig.10 Effect of feature number on CPU runtime圖10 特征數(shù)對CPU 運(yùn)行時間影響

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

7 結(jié)束語

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