黃白梅，章 政

（武漢科技大學 信息科學與工程學院，湖北 武漢 430081）

在現(xiàn)實世界中，高維數(shù)據(jù)占據(jù)著主導地位，例如文檔數(shù)據(jù)、WEB數(shù)據(jù)、基因微陣列數(shù)據(jù)、網(wǎng)絡通信數(shù)據(jù)等數(shù)據(jù)經(jīng)常達到上千維甚至更高。在對高維數(shù)據(jù)進行聚類時，由于受到“維數(shù)災難效應”[1-2]的影響，同時高維數(shù)據(jù)空間中的一些不相關屬性維掩蓋了要尋找的目標簇，使得傳統(tǒng)的聚類算法在高維數(shù)據(jù)空間上進行聚類分析時失效。因此需要高維降維去掉不相關屬性維，通過對解空間中的全部屬性子集進行搜索，進而找到最密集的優(yōu)良子集，再在低維空間中進行聚類分析。

傳統(tǒng)的搜索算法諸如貪婪算法等，在對其進行聚類分析時非常容易陷入局部最優(yōu)解的困境而達不到理想的要求。遺傳算法是一種自適應全局優(yōu)化的概率搜索算法，它在理論上可以克服局部最優(yōu)解而搜索到全局最優(yōu)解，因此被廣泛的應用于解決復雜的優(yōu)化問題。

文中針對高維數(shù)據(jù)的特點，為了降低“維數(shù)災難效應”對聚類結果的影響，構建了一個基于遺傳算法進行高維數(shù)據(jù)聚類的框架，利用遺傳算法的全局搜索能力，挖掘高維數(shù)據(jù)空間中密集度高的數(shù)據(jù)子集，然后再在這個子集上進行聚類分析。

1 子空間聚類概述

目前對高維數(shù)據(jù)進行聚類的方法主要還是基于子空間聚類和全空間降維這兩個方面。

子空間聚類的方法（Sub-space Clustering）[2-5]是屬性子集選擇的一種擴展，在高維聚類方面顯示出了其獨有的優(yōu)勢。它的基本思想是基于不同子空間可能包含不同的、有意義的類或簇，它在相同的數(shù)據(jù)集的不同子空間中搜索類或簇群，因此可以通過抽取出存在于子空間的類或簇來進行聚類分析。子空間聚類為每個類或簇搜索出其對應的子空間。根據(jù)搜索策略的不同，可以將子空間聚類方法劃分成為兩大類：自底向上的搜索方法（如 CLIQUE算法[3]）和自頂向下的搜索方法（如PROCLUS算法[4]）。也有一些算法結合自底向上的搜索方法和自頂向下的搜索方法（如 DOC算法[5]）。子空間聚類方法對于處理不同類或簇存在于不同子空間里的高維數(shù)據(jù)結構模型比較有效，不過這類方法的計算復雜性非常高。

全空間降維則是通過縮減維數(shù)將高維數(shù)據(jù)空間歸約到較低維數(shù)據(jù)空間，然后再通過傳統(tǒng)的方法進行聚類分析，這類方法是在一個特征子空間里面尋找所有的類或簇，但是忽略了在高維數(shù)據(jù)空間里面不同的類或簇可能有不同的特征子空間。

這兩種聚類方法都有其優(yōu)點與不足，目前尚沒有一種算法能夠適用于所有的情況，在實際應用中，我們應該根據(jù)具體問題的特點來選擇合適的聚類算法。同時由于在處理大規(guī)模高維數(shù)據(jù)時，容易陷入局部最優(yōu)解的狀況。因此經(jīng)常采用將各種全局優(yōu)化搜索算法，如遺傳算法，粒子群算法，蟻群算法等，結合子空間聚類或者降維來處理的策略，達到最終尋找到最優(yōu)解。遺傳算法（GA）[6]，是通過模擬孟德爾.摩根的群體遺傳學說、達爾文的生物進化論的自然選擇和遺傳學機理的生物進化過程而形成的一種自適應全局優(yōu)化概率搜索算法。它是一種高效的全局優(yōu)化搜索算法，已被許多研究者應用到聚類分析中。

2 基于遺傳算法的子空間聚類算法

基于遺傳算法進行高維聚類的新算法利用遺傳算法的全局搜索能力對高維數(shù)據(jù)的特征空間進行搜索，因此其基本流程跟傳統(tǒng)的遺傳算法大致相同[7]。組成種群的個體由特征維和類中心點兩部分經(jīng)過編碼后組成，每個個體對應著一個特征子空間；適應度值是遺傳算法對搜索進行評估的唯一依據(jù)，新算法中的適應度值表示個體所代表的特征子空間進行聚類的效果，適應度值越大，表明子空間數(shù)據(jù)對象的密集性越強，聚類越好。

2.1 編碼與初始化

常用的編碼方式有二進制編碼和實數(shù)編碼等，由于二進制編碼的染色體長度相對較長，且編碼的種群穩(wěn)定性比實數(shù)編碼要差，文中選取實數(shù)編碼。個體的編碼空間[8]由（SUB，CEN）這兩部分組成，其中SUB代表特征子空間的實數(shù)編碼串，CEN代表類中心的實數(shù)編碼串。初始種群我們采用隨機生成的策略。隨機的選?。ㄗ畲蟮奶卣骶S數(shù)目）個特征維和（最大的類數(shù)目）個數(shù)據(jù)對象進行編碼組成個體，然后迭代（預設的初始種群的規(guī)模）次，即完成初始種群的產(chǎn)生。

初始種群隨機生成的方案如下：隨機的在數(shù)據(jù)對象集中選取m個特征維的編號和n個數(shù)據(jù)對象的編號來進行編碼，構成初始染色體。例如某數(shù)據(jù)對象集有10維，由150個數(shù)據(jù)對象組成。取m=4，n=3，則一個染色體的基因即由4個特征維的編號和3個數(shù)據(jù)對象的編號組成。染色體的左部分基因表示由第5，8，3，2等4個特征維組成，染色體的右部分基因表示由該數(shù)據(jù)集的第32，12，50個數(shù)據(jù)組成，兩部分共同構成了一個染色體。通過編碼即完成了染色體的構造。

2.2 適應度函數(shù)的設計

適應度值是遺傳算法進行搜索的唯一依據(jù)，因此適應度函數(shù)設計的好壞直接影響著算法的搜索方向及收斂程度。本文基于類內距離，類間距離和信息熵提出了一種新的適應度評估函數(shù)。

在高維數(shù)據(jù)聚類中，目標簇通常只跟某些特征維有關，為了考察特征維在子空間聚類中所表現(xiàn)出來的性能，本文提出用特征維對子空間聚類的貢獻率來表征。

假設某子空間中含有 K個以{C1，C2，…，CK}為中心的類{A1，A2，…，AK}，對每一個類 Ai（i=1，2，…，K），考慮 3 個函數(shù)：

在這里，T表示數(shù)據(jù)集的數(shù)據(jù)對象個數(shù)，Ti表示數(shù)據(jù)集的第i個類的數(shù)據(jù)對象的個數(shù)，表示第i個類的中心點的第j維值，表示第n個類內第n個數(shù)據(jù)對象的第j維值。

fitness1ji體現(xiàn)了第j維對類 Ai的類內貢獻率-越小，表示第i類內某個數(shù)據(jù)對象的第j維值與中心點的第j維值距離越接近，fitness1ji就越大。則類Ai在特征維j上是稠密的，即稱維j對類i的貢獻大，反之，稱維j對類的貢獻小。

故維j對類i的貢獻率為：

維j對此子空間聚類的貢獻率：

染色體（特征子空間）的適應度值：

其中max_cennumber表示最大的特征維數(shù)目，max_cennumber表示最大的類數(shù)目a，b，c。為常數(shù)（在這里根據(jù)先驗知識取 a=1，b=-0.5，c=0.8）。

2.3 遺傳算子及控制參數(shù)

遺傳操作是遺傳算法的核心部分，遺傳操作有3個操作算子：選擇算子、交叉算子和變異算子，父代種群通過遺傳操作產(chǎn)生出子代種群來繁衍和進化[9]。

選擇算子：文中依據(jù)上述適應度函數(shù)作為選擇的依據(jù)，保留部分適應度函數(shù)值高的優(yōu)良個體（根據(jù)先驗知識預先設定），進入到子代進行繁殖，然后采取輪盤賭選擇法，根據(jù)適應度函數(shù)值的大小選擇剩下的個體[8]。

交叉算子：交叉算子的主要參數(shù)是交叉概率pc，取pc?[0.4，0.9]，根據(jù)pc對父代個體進行單點交叉操作[8]，在基因位上通過互換基因，生成兩個新的子代個體。

變異算子：文中取基本位變異法[9]，按照預設的變異概率pm進行變異操作，在基因位上對原基因值進行突變替換。pm取 0.01～0.2

迭代終止條件：采用世代數(shù)是否超過預設的參數(shù)值[11]的方法來作為遺傳算法終止的條件。

3 實驗對比與分析

為了驗證文中提出的基于遺傳算法進行高維聚類的新算法的聚類效果和性能，采用了一組真實數(shù)據(jù)集來進行實驗。在實驗中我們選取了經(jīng)典的聚類算法k-means算法，子空間聚類算法PROCLUS[11]算法以及基于遺傳算法進行高維數(shù)據(jù)數(shù)據(jù)聚類的降維算法GA-HDclustering算法[8]與本文提出的算法進行了比較。通過比較錯誤率 （Error_degree），熵（Entropy）值，純度（Purity）值，Rand 統(tǒng)計量（RI）值這幾項指標的評判值來對其聚類結果進行評估和比較。

為了檢驗文中算法在實際高維數(shù)據(jù)中的有效性，選取了一組真實的數(shù)據(jù)集來進行實驗。數(shù)據(jù)集來自UCI機器學習的數(shù)據(jù)集（http://archive.ics.uci.edu/ml/），如表 1。

表1 真實數(shù)據(jù)集Tab.1 Real data set

該數(shù)據(jù)集最初是用來對乳腺癌病進行預測和診斷的。wdbc數(shù)據(jù)集記錄了569位女性的乳房腫塊的30個特征值，這些特征值是通過乳房腫塊的細針抽取數(shù)字圖像而計算出來的，它們體現(xiàn)了圖像中細胞核的特征。根據(jù)這30個特征值，可以將這569位女性分為兩類，一類患有乳腺癌者，共有212人；另一類未患乳腺癌者，共有357人。數(shù)據(jù)集客觀上分為兩類。

對于wdbc數(shù)據(jù)集，對其使用k-means算法、PROCLUS算法、GA-HDclustering算法以及文中提出的基于遺傳算法進行高維聚類的新算法分別進行實驗。運行GA-HDclustering算法和基于遺傳算法進行高維聚類的新算法時，為了便于比較，將需要設定的相關參數(shù)，此處取pc=0.8，pc=0.02，max_subnumber=25，max_cennunber=2，popsize=80，max_gen=350。

對這組數(shù)據(jù)集分別運行k-means算法、PROCLUS算法、GA-HDclustering算法以及基于遺傳算法進行高維聚類的新算法，計算各自的錯誤率并統(tǒng)計熵值、純度值以及Rand統(tǒng)計量值這3個有效性衡量指標，具體的實驗結果與分析如下。

數(shù)據(jù)集客觀上分為兩類，共有569個數(shù)據(jù)對象，每個數(shù)據(jù)對象有30維，各類分布如下：（各類數(shù)據(jù)對象數(shù)目）Class1:357，Class2:212。

各算法在對wdbc數(shù)據(jù)集聚類對應的特征子空間如表2所示。

表2 數(shù)據(jù)集的聚類特征子空間Tab.2 Clustering feature sub-space of

我們將每個算法的錯誤率標記為Error。k-means算法，PROCLUS算法，GA-HDclustering算法和基于遺傳算法進行高維聚類的新算法的錯誤率如表3所示。

表3 各個算法的錯誤率Tab.3 Error rate of each algorithm

通過上面4個算法對數(shù)據(jù)的聚類結果，看到基于遺傳算法進行高維聚類的新算法的錯誤率為0.143 2，比K-means算法的0.151 6和PROCLUS算法的0.153 4這兩個經(jīng)典算法的總錯誤率要小得多，比GA-HDclustering算法的總錯誤率0.151 2也明顯偏小，聚類的精確性最高。

各算法在對該數(shù)據(jù)集進行聚類時，對應的熵值，純度，RAND統(tǒng)計量如表4所示。

表4 各個算法對應的熵值、純度和RAND值Tab.4 Entropy，purity and RI of each algorithm

實驗結果說明，K－means算法和PROCLUS算法的熵值優(yōu)于GA－HDclustering算法，K－means算法的純度和 RI值比PROCLUS算法和GA－HDclustering算法也略高。而基于遺傳算法進行高維聚類的新算法的熵值比這3個算法大幅度降低，純度和RI值也比這3個算法明顯提高。

4 結束語

文中提出的算法能夠高效地對高維數(shù)據(jù)進行降維，找到有效的特征子空間進行聚類；并且對數(shù)據(jù)進行聚類結果的錯誤率和評估指標Entropy值、purity值及RI值與其他算法相比，精確性和魯棒性更強；綜上所述，文中提出的算法能夠有效地進行高維數(shù)據(jù)聚類，降低“維數(shù)災難效應”的影響，是一種行之有效的高維數(shù)據(jù)聚類方法。但同時也存在一些問題值得進一步深入研究，文中提出的算法中的各個參數(shù)一般都是根據(jù)經(jīng)驗及多次試驗進行設定的，下一步考慮研究各參數(shù)及其自動設置，另外該算法在對非特定的真實數(shù)據(jù)進行聚類時的魯棒性仍有待提高。

[1]Donoho D L.High-dimensional data analysis:the curses and blessings of dimensionality[C]//Aide-Memoire of a Lecture at AMS Conference on Math Challenges of 21st Century，2000.

[2]Parsons L，Haque E，Liu H.Subspace clustering for high dimensional data:a review[J].SIGKDD Explorations，2004，6（1）:90－105.

[3]Agrawal R，Gehrke J，Gunopulos D.Automatic subspace clustering ofhigh dimensionaldata fordata mining applications[J].In Proc.ACM－SIGMOD Int.Conf.Management of Data （SIGMOD'98），（Seattle， WA），1998:94－105.

[4]Aggarwal C C，Procopiuc C.Fast algorithms for projected clustering[Z].In Proc.of ACM SIGMOD，1999.

[5]Procopiuc C M，Jones M，Agarwal P K，et al.A monte carlo algorithm for fast projective clustering[Z].Proc.ACM SIGMOD，2002.

[6]Galletly J E.An overview of genetic algorithms[J].Kybernetics，1992， 21（6）:26－30.

[7]周明，孫樹棟.遺傳算法原理及應用[M].國防工業(yè)出版社，1999.

[8]孫浩軍，熊瑯環(huán).一種高維數(shù)據(jù)聚類遺傳算法[J].計算機科學與工程，2010，32（8）:94－98.

SUN Hao-jun，XIONG Lang-huan.A genetic algorithm for hign-domensional data clustering[J].Computer Science and Engineering，2010，32（8）:94－98.

[9]潘正君，康立山，陳毓屏.演化計算[M].北京：清華大學出版社，1998.

[10]何宏，譚永紅.一種基于動態(tài)遺傳算法的聚類新方法[J].電子學報，2012，2（2）:254－260.

HE Hong，TAN Yong-hong.A novel clustering method based ondynamicgeneticalgorithm[J].ChineseJournalofElectronics，2012，2（2）:254－260.

[11]Aggarwal C C，Procopiuc C.Fast algorithms for projected clustering[Z].In Proc.of ACM SIGMOD，2004.