高維數(shù)據(jù)對(duì)象聚類算法效果分析

郝媛 高學(xué)東 孟海東

［摘要］ 雖然經(jīng)典聚類算法能夠有效地處理維度較低的數(shù)據(jù)對(duì)象，但隨著維度的增加，算法的性能和效率就會(huì)明顯下降。本文在對(duì)數(shù)據(jù)對(duì)象間的最大距離和平均距離隨維數(shù)增加的變化趨勢(shì)實(shí)驗(yàn)基礎(chǔ)上，對(duì)聚類算法的聚類精度隨數(shù)據(jù)對(duì)象維度增加的變化特征進(jìn)行了實(shí)驗(yàn)研究。同時(shí)，利用復(fù)相關(guān)系數(shù)的倒數(shù)對(duì)屬性進(jìn)行加權(quán)，提出了利用復(fù)相關(guān)系數(shù)倒數(shù)閾值實(shí)現(xiàn)降維的方法，并取得了良好的實(shí)驗(yàn)結(jié)果。

［關(guān)鍵詞］ 高維數(shù)據(jù)；聚類效果；復(fù)相關(guān)系數(shù)；降維

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 08. 035

［中圖分類號(hào)］F270.7；TP301［文獻(xiàn)標(biāo)識(shí)碼］A［文章編號(hào)］1673 - 0194（2012）08- 0051- 03

１引言

聚類分析是數(shù)據(jù)挖掘領(lǐng)域中的一項(xiàng)重要的研究課題，高維數(shù)據(jù)對(duì)象的聚類又是聚類分析的重要研究課題，也是涉及到聚類算法是否能夠有效地應(yīng)用于各個(gè)領(lǐng)域，例如多屬性（高維）流數(shù)據(jù)的聚類分析。高維數(shù)據(jù)的特點(diǎn)表現(xiàn)為：①高維數(shù)據(jù)集中存在大量無(wú)關(guān)的屬性使得在所有維中存在簇的可能性幾乎為零；②高維空間中數(shù)據(jù)比低維空間中數(shù)據(jù)分布稀疏，其中數(shù)據(jù)間距離幾乎相等是普遍現(xiàn)象。目前，對(duì)高維數(shù)據(jù)的聚類主要有3種方法：屬性轉(zhuǎn)換、子空間聚類、協(xié)同聚類、屬性轉(zhuǎn)換是通過(guò)創(chuàng)建新屬性，將一些舊屬性合并在一起來(lái)降低數(shù)據(jù)集的維度的方法。目前，主成分分析方法（ＰＣＡ）、自組織特征映射（ＳＯＭ）、多維縮放（ＭＤＳ）、小波分析等是普遍應(yīng)用的降維方法。雖然采用降維技術(shù)使得數(shù)據(jù)的維度大大降低，但數(shù)據(jù)的可理解性和可解釋性變得較差，一些對(duì)聚類有用的信息也可能會(huì)隨之丟失，很難準(zhǔn)確地表達(dá)和理解結(jié)果。在處理高維數(shù)據(jù)時(shí)，采用屬性轉(zhuǎn)換的方法得到的聚類效果并不是很理想，有一定的局限性，不能滿足當(dāng)前高維聚類算法發(fā)展的需要。

子空間聚類算法對(duì)特征選擇的任務(wù)進(jìn)行了拓展，它是在同一個(gè)數(shù)據(jù)集的不同子空間上進(jìn)行聚類。子空間聚類和特征選擇一樣使用搜索策略和評(píng)測(cè)標(biāo)準(zhǔn)來(lái)篩選出需要聚類的簇，因?yàn)椴煌淖涌臻g上存在不同的簇，因此我們要對(duì)評(píng)測(cè)標(biāo)準(zhǔn)設(shè)置一些條件。

協(xié)同聚類在數(shù)據(jù)點(diǎn)聚類和屬性聚類之間達(dá)到了一種平衡。因?yàn)樗鼜膶?duì)象—屬性兩個(gè)角度同時(shí)進(jìn)行聚類操作。假設(shè)Ｘ是由數(shù)據(jù)對(duì)象和數(shù)據(jù)屬性構(gòu)成的矩陣，一般被叫做關(guān)系矩陣、可能性矩陣、影響矩陣、頻率矩陣等。一般被應(yīng)用于反映基因響應(yīng)的強(qiáng)度、一個(gè)Ｗeb頁(yè)面的點(diǎn)擊率，或一個(gè)倉(cāng)庫(kù)里各項(xiàng)商品的銷售數(shù)量等。Ｇｏｖａｅｒｔ于１９９５提出了可能性矩陣表中行列塊的同時(shí)聚類算法。Ｄｈｉｌｌｏｎ于２００１年提出了一種協(xié)同代數(shù)聚類算法，它與文本挖掘相關(guān)，是基于二部圖和它們的最小切割的。Ｏｙａｎａｇｉ等人于２００１年提出了一種簡(jiǎn)單的Ｐｉｎｇ－Ｐｏｎｇ算法，它能在稀疏二元矩陣中發(fā)現(xiàn)相應(yīng)區(qū)域，該算法能建立矩陣元素的橫向聯(lián)系，并用此來(lái)重新分布列對(duì)行的影響，并反過(guò)來(lái)進(jìn)行。

本文在對(duì)數(shù)據(jù)對(duì)象間的最大距離和平均距離隨維數(shù)增加的變化趨勢(shì)實(shí)驗(yàn)基礎(chǔ)上，通過(guò)實(shí)驗(yàn)研究了聚類算法的聚類精度隨數(shù)據(jù)對(duì)象維度的變化特征。同時(shí)，提出了利用復(fù)相關(guān)系數(shù)倒數(shù)閾值實(shí)現(xiàn)降維的方法。

２數(shù)據(jù)對(duì)象離散度與維度的關(guān)系

２．１ 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)中所用的數(shù)據(jù)集均來(lái)自ＵＣＩ數(shù)據(jù)庫(kù)，數(shù)據(jù)集包括Ｉｒｉｓ，Ｗｉｎｅ，Ｗｉｓｃｏｎｓｉｎ Ｄｉａｇｎｏｓｔｉｃ Ｂｒｅａｓｔ Ｃａｎｃｅｒ，ＳＰＥＣＴ Ｈｅａｒｔ和Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ。數(shù)據(jù)集的詳細(xì)描述見表１。

２．２ 相關(guān)定義

為了確定數(shù)據(jù)對(duì)象隨維度變化規(guī)律，我們定義了數(shù)據(jù)對(duì)象間的最大距離和平均距離來(lái)定量確定數(shù)據(jù)對(duì)象間的離散度。

最大距離：假設(shè)數(shù)據(jù)集D有n個(gè)數(shù)據(jù)對(duì)象，每個(gè)數(shù)據(jù)對(duì)象有ｄ個(gè)屬性（維），即Ｘｉ＝｛ｘｋ，ｋ＝１，…，ｄ｝，ｉ＝１，…，n。數(shù)據(jù)對(duì)象間的最大距離被定義為：

２．３ 實(shí)驗(yàn)結(jié)果

為了研究維數(shù)對(duì)聚類精度的影響，有必要研究對(duì)象間的距離隨維數(shù)增高的變化趨勢(shì)。根據(jù)上面定義的公式（１）和公式（２），數(shù)據(jù)對(duì)象間的最大距離和平均距離隨維數(shù)的增加而增大。我們使用ＵＣＩ數(shù)據(jù)庫(kù)中的Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ數(shù)據(jù)集，先對(duì)數(shù)據(jù)集進(jìn)行最小—最大標(biāo)準(zhǔn)化處理，然后計(jì)算此數(shù)據(jù)集中數(shù)據(jù)對(duì)象間隨維數(shù)增高的最大距離和平均距離。實(shí)驗(yàn)結(jié)果分別顯示在圖１和圖２中。

如圖１和圖２所示，隨著維數(shù)的增加，數(shù)據(jù)對(duì)象間的最大距離和平均距離逐漸增大。表明數(shù)據(jù)對(duì)象在高維數(shù)據(jù)空間變得比較稀疏，很可能導(dǎo)致數(shù)據(jù)空間中客觀簇的消失，使得基于距離的聚類算法往往不能夠取得良好的聚類效果。因此，為了獲得有效的聚類結(jié)果，基于距離、密度和密度可達(dá)的聚類算法有必要進(jìn)行改進(jìn)或降維。

３維數(shù)對(duì)算法聚類精度的影響

３．１ 直接聚類

我們給出了確定聚類效果的準(zhǔn)確度公式。假設(shè)數(shù)據(jù)集Ｄ中有ｋ個(gè)類，即Ｃｉ（ｉ＝１，…，ｋ），Oｉｐ（ｐ＝１，…，ｍｐ）是類Ci中的數(shù)據(jù)對(duì)象。數(shù)據(jù)集Ｄ經(jīng)過(guò)聚類后，出現(xiàn)了ｋ個(gè)類Ｃｉ′（ｉ＝１，…，ｋ），Ｏｉｐ′（ｐ＝１，…，ｍｐ′）是Ci′類中的數(shù)據(jù)對(duì)象，準(zhǔn)確度被定義為：

｜Ｃｋ∩Ｃｉ′｜是同時(shí)屬于類Ｃｉ和Ｃｉ′的數(shù)據(jù)對(duì)象Ｏｉｐ（ｐ＝１，…，ｍｐ）和Oip′（ｐ＝１，…，ｍｐ′）的個(gè)數(shù)；|D|是數(shù)據(jù)集D中的數(shù)據(jù)對(duì)象的個(gè)數(shù)。

為了研究維數(shù)對(duì)算法聚類精度的影響，我們分別用Ｋ－ｍｅａｎｓ和層次聚類算法對(duì)以上５個(gè)不同維數(shù)的數(shù)據(jù)集進(jìn)行聚類分析，聚類結(jié)果如圖３所示。當(dāng)數(shù)據(jù)集的維數(shù)小于３０的時(shí)候，兩種聚類算法的性能較好，當(dāng)數(shù)據(jù)集的維數(shù)大于３０的時(shí)候，聚類算法的精度隨維數(shù)的增高而降低。實(shí)驗(yàn)結(jié)果在一定程度上表明，當(dāng)數(shù)據(jù)集的維數(shù)小于３０的時(shí)候，傳統(tǒng)的聚類算法，如Ｋ－ｍｅａｎｓ和層次聚類算法，這種基于距離的聚類算法是有效的，但是當(dāng)維數(shù)大于３０的時(shí)候它們的聚類結(jié)果很不理想。

３．２ ＰＣＡ降維聚類

Ｗｉｎｅ數(shù)據(jù)集有１３維，經(jīng)過(guò)主成分分析（ＰＣＡ）降維后，原有的１３維變成了３維，為了比較ＰＣＡ降維前和降維后的效果，我們用Ｋ－ｍｅａｎｓ和層次聚類算法對(duì)原有的數(shù)據(jù)集和經(jīng)過(guò)降維后的數(shù)據(jù)集進(jìn)行聚類，結(jié)果如圖４所示。

對(duì)數(shù)據(jù)集降維后，Ｋ－ｍｅａｎｓ和層次聚類算法的聚類精度有所提高，但是效果不是很明顯。此結(jié)果也說(shuō)明了 Ｋ－ｍｅａｎｓ和層次聚類對(duì)３０維以內(nèi)的數(shù)據(jù)集的聚類精度比較高。

Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ數(shù)據(jù)集有９０維，經(jīng)過(guò)ＰＣＡ降維后變成了１０維，降維前和降維后的聚類結(jié)果如圖５所示。

降維前和降維后Ｋ－ｍｅａｎｓ和層次聚類算法的聚類精度都很低，結(jié)果表明：①以上兩種聚類算法不能有效地處理高維數(shù)據(jù)；②ＰＣＡ降維對(duì)聚類算法不總是有效的；③此數(shù)據(jù)集包含１５個(gè)類，對(duì)于高維、多類的數(shù)據(jù)集，聚類算法不能很好地辨別存在的類（簇）。

４基于復(fù)相關(guān)系數(shù)倒數(shù)降維

４．１ 復(fù)相關(guān)系數(shù)倒數(shù)加權(quán)

復(fù)相關(guān)系數(shù)的倒數(shù)賦權(quán)法是在方差倒數(shù)賦權(quán)法的基礎(chǔ)上提出來(lái)的。假設(shè)數(shù)據(jù)對(duì)象的某一屬性為Xk，則它的復(fù)相關(guān)系數(shù)記為ρk。ρk越大，表明Xk與其余的屬性越相關(guān)，越能被非Xk代替，也就是說(shuō)Xk屬性對(duì)聚類的作用越??；反之，ρk越小，Xk與其余的屬性越不相關(guān)，Xk屬性對(duì)聚類的作用越大。所以可以用|ρi|-1計(jì)算數(shù)據(jù)對(duì)象屬性權(quán)重系數(shù)wk。

４．２ 降維實(shí)驗(yàn)

我們也可以采用復(fù)相關(guān)系數(shù)的倒數(shù)賦權(quán)法作為一種特征選擇方法，對(duì)數(shù)據(jù)集中數(shù)據(jù)對(duì)象的每個(gè)屬性加權(quán)后，得到了每個(gè)屬性的權(quán)值，然后根據(jù)權(quán)值的大小，我們?cè)O(shè)定一個(gè)閾值參數(shù)σ，選擇權(quán)值大于σ的屬性，從而實(shí)現(xiàn)了對(duì)數(shù)據(jù)集的降維，然后對(duì)降維后數(shù)據(jù)集進(jìn)行聚類。為了說(shuō)明此方法的有效性，采用ｋ－ｍｅａｎｓ算法、層次聚類算法、ＣＡＤＤ （基于密度和密度可達(dá)聚類算法）算法對(duì)ＷＤＢＣ數(shù)據(jù)集和ＳＰＥＣＴ Ｈｅａｒｔ數(shù)據(jù)集進(jìn)行聚類，來(lái)對(duì)比降維前和降維后的結(jié)果。

ＷＤＢＣ數(shù)據(jù)集有３０個(gè)屬性，取權(quán)值σ≥0.036時(shí)，該數(shù)據(jù)集降為３維；取權(quán)值大于０．０３４時(shí)，該數(shù)據(jù)集降為６維；取權(quán)值大于０．０３３時(shí)，該數(shù)據(jù)集降為１５維。降為３維、６維、１５維的數(shù)據(jù)集和原數(shù)據(jù)集的聚類精度如圖６所示，實(shí)驗(yàn)結(jié)果表明該數(shù)據(jù)集降為６維時(shí)聚類效果最好。

ＳＰＥＣＴ Ｈｅａｒｔ數(shù)據(jù)集有４４個(gè)屬性，取權(quán)值大于０．０２４時(shí)，該數(shù)據(jù)集降為５維；取權(quán)值大于０．０２３時(shí)，該數(shù)據(jù)集降為１８維；取權(quán)值大于０．０２２時(shí)，該數(shù)據(jù)集降為２８維。降為５維、１８維、２８維的數(shù)據(jù)集和原數(shù)據(jù)集的聚類精度如圖７所示，實(shí)驗(yàn)結(jié)果表明該數(shù)據(jù)集降為１８維時(shí)聚類效果最好。

Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ數(shù)據(jù)集有９０個(gè)屬性，取權(quán)值大于０．０１１ １１３時(shí)，該數(shù)據(jù)集降為１０維；取權(quán)值大于０．０１１ １１１時(shí)，該數(shù)據(jù)集降為３４維；取權(quán)值大于０．０１１ １１０時(shí)，該數(shù)據(jù)集降為４７維。降為１０維、３４維、４７維的數(shù)據(jù)集和原數(shù)據(jù)集的聚類精度如圖８所示。實(shí)驗(yàn)結(jié)果表明聚類算法對(duì)該數(shù)據(jù)集的聚類效果較差，原因是此數(shù)據(jù)集包含１５個(gè)類，類比較多，聚類算法不能很好地識(shí)別，但是該數(shù)據(jù)集降為４７維時(shí)聚類效果有所提高，仍能體現(xiàn)出本文降維方法的有效性，ＣＡＤＤ算法的聚類效果相對(duì)好一些，從而體現(xiàn)了ＣＡＤＤ算法的優(yōu)越性。

由以上實(shí)驗(yàn)結(jié)果表明：①采用復(fù)相關(guān)系數(shù)的倒數(shù)賦權(quán)法作為一種屬性選擇方法是有效的，并且計(jì)算量較小，適合處理高維數(shù)據(jù)；②降維要降到合適的維度，如果維數(shù)太少，則會(huì)丟失對(duì)聚類重要的屬性信息，如果維數(shù)太多，則會(huì)產(chǎn)生“噪聲”，影響聚類結(jié)果；③一般的聚類算法不能很好地處理高維且類比較多的數(shù)據(jù)集，因此有待于進(jìn)一步研究能處理高維且類比較多的數(shù)據(jù)集的聚類算法。

５結(jié)論

對(duì)于傳統(tǒng)的基于距離的聚類算法，當(dāng)數(shù)據(jù)對(duì)象的維數(shù)小于或等于３０時(shí)，聚類分析往往能夠取得良好的聚類效果；維數(shù)高于３０時(shí)，聚類效果不佳。甚至使用ＰＣＡ降維后，聚類算法對(duì)高維數(shù)據(jù)的聚類效果的改進(jìn)也不是很明顯。用復(fù)相關(guān)系數(shù)的倒數(shù)賦權(quán)法為差異度加權(quán)，并且把復(fù)相關(guān)系數(shù)的倒數(shù)賦權(quán)法用作一種屬性選擇方法，通過(guò)設(shè)定屬性加權(quán)系數(shù)的閾值參數(shù)對(duì)數(shù)據(jù)對(duì)象進(jìn)行降維也能取得較好的聚類結(jié)果。

主要參考文獻(xiàn)

［１］馮永，吳開貴，熊忠陽(yáng)，等．一種有效的并行高維聚類算法［Ｊ］．計(jì)算機(jī)科學(xué)，２００５，３２（３）：２１６－２１８．

［２］王永卿．高維海量數(shù)據(jù)聚類算法研究［Ｄ］．南寧：廣西大學(xué)，２００７．

［３］［加］Ｊｉａｗｅｉ Ｈａｎ，［加］ Ｍｉｃｈｅｌｉｎｅ Ｋａｍｂｅｒ． 數(shù)據(jù)挖掘概念與技術(shù)［Ｍ］．北京：機(jī)械工業(yè)出版社，２００１．

［４］Ｇ Ｇｏｖａｅｒｔ．Ｓｉｍｕｌｔａｎｅｏｕｓ Ｃｌｕｓｔｅｒｉｎｇ ｏｆ Ｒｏｗｓ ａｎｄ Ｃｏｌｕｍｎｓ［Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ Ｃｙｂｅｒｙｒｅｔｉｃｓ，１９９５，２４（4）：４３７－４５８．

［５］Inderjit S Dhillon． Ｃｏ－ｃｌｕｓｔｅｒｉｎｇ Ｄｏｃｕｍｅｎｔｓ ａｎｄ Ｗｏｒｄｓ Ｕｓｉｎｇ Ｂｉｐａｒｔｉｔｅ Ｓｐｅｃｔｒａｌ Ｇｒａｐｈ Ｐａｒｔｉｔｉｏｎｉｎｇ［Ｃ］//Ｐｒｏｃｅｅｄｉｎｇｓ ａｎｄ ｔｈｅ ７ｔｈ ＡＣＭ ＳＩＧＫＤＤ， Ｎｅｗ Ｙｏｒｋ，ＮＹ，２００１．

［６］Shigeru Oyanagi,Kazuto Kubota,Ahihiko Nakase． Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Mａｔｒｉｘ Cｌｕｓｔｅｒｉｎｇ ｔｏ Ｗｅｂ Lｏｇ Aｎａｌｙｓｉｓ ａｎｄ Aｃｃｅｓｓ Pｒｅｄｉｃｔｉｏｎ［Ｃ］//７ｔｈ ＡＣＭ ＳＩＧＫＤＤ， Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＣＡ，2001.

［7］宋宇辰，張玉英，孟海東．一種基于加權(quán)歐氏距離聚類方法的研究［Ｊ］．計(jì)算機(jī)工程與應(yīng)用，２００７，４３（４）：１７９－１８０．

［8］孟海東，宋飛燕，宋宇辰．面向復(fù)雜簇的聚類算法研究與實(shí)現(xiàn)［Ｊ］．計(jì)算機(jī)應(yīng)用與軟件，２００８，２５（１０）：３２－３４．