黃白梅，章 政

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

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

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

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

1 子空間聚類概述

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

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

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

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

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

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

2.1 編碼與初始化

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

初始種群隨機(jī)生成的方案如下：隨機(jī)的在數(shù)據(jù)對象集中選取m個特征維的編號和n個數(shù)據(jù)對象的編號來進(jìn)行編碼，構(gòu)成初始染色體。例如某數(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ù)組成，兩部分共同構(gòu)成了一個染色體。通過編碼即完成了染色體的構(gòu)造。

2.2 適應(yīng)度函數(shù)的設(shè)計(jì)

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

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

假設(shè)某子空間中含有 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個類的中心點(diǎn)的第j維值，表示第n個類內(nèi)第n個數(shù)據(jù)對象的第j維值。

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

故維j對類i的貢獻(xiàn)率為：

維j對此子空間聚類的貢獻(xiàn)率：

染色體（特征子空間）的適應(yīng)度值：

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

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

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

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

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

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

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

3 實(shí)驗(yàn)對比與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[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]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].國防工業(yè)出版社，1999.

[8]孫浩軍，熊瑯環(huán).一種高維數(shù)據(jù)聚類遺傳算法[J].計(jì)算機(jī)科學(xué)與工程，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]潘正君，康立山，陳毓屏.演化計(jì)算[M].北京：清華大學(xué)出版社，1998.

[10]何宏，譚永紅.一種基于動態(tài)遺傳算法的聚類新方法[J].電子學(xué)報，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.