高維數據對象聚類算法效果分析

郝媛 高學東 孟海東

［摘要］ 雖然經典聚類算法能夠有效地處理維度較低的數據對象，但隨著維度的增加，算法的性能和效率就會明顯下降。本文在對數據對象間的最大距離和平均距離隨維數增加的變化趨勢實驗基礎上，對聚類算法的聚類精度隨數據對象維度增加的變化特征進行了實驗研究。同時，利用復相關系數的倒數對屬性進行加權，提出了利用復相關系數倒數閾值實現降維的方法，并取得了良好的實驗結果。

［關鍵詞］ 高維數據；聚類效果；復相關系數；降維

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

［中圖分類號］F270.7；TP301［文獻標識碼］A［文章編號］1673 - 0194（2012）08- 0051- 03

１引言

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

子空間聚類算法對特征選擇的任務進行了拓展，它是在同一個數據集的不同子空間上進行聚類。子空間聚類和特征選擇一樣使用搜索策略和評測標準來篩選出需要聚類的簇，因為不同的子空間上存在不同的簇，因此我們要對評測標準設置一些條件。

協同聚類在數據點聚類和屬性聚類之間達到了一種平衡。因為它從對象—屬性兩個角度同時進行聚類操作。假設Ｘ是由數據對象和數據屬性構成的矩陣，一般被叫做關系矩陣、可能性矩陣、影響矩陣、頻率矩陣等。一般被應用于反映基因響應的強度、一個Ｗeb頁面的點擊率，或一個倉庫里各項商品的銷售數量等。Ｇｏｖａｅｒｔ于１９９５提出了可能性矩陣表中行列塊的同時聚類算法。Ｄｈｉｌｌｏｎ于２００１年提出了一種協同代數聚類算法，它與文本挖掘相關，是基于二部圖和它們的最小切割的。Ｏｙａｎａｇｉ等人于２００１年提出了一種簡單的Ｐｉｎｇ－Ｐｏｎｇ算法，它能在稀疏二元矩陣中發現相應區域，該算法能建立矩陣元素的橫向聯系，并用此來重新分布列對行的影響，并反過來進行。

本文在對數據對象間的最大距離和平均距離隨維數增加的變化趨勢實驗基礎上，通過實驗研究了聚類算法的聚類精度隨數據對象維度的變化特征。同時，提出了利用復相關系數倒數閾值實現降維的方法。

２數據對象離散度與維度的關系

２．１ 實驗數據

實驗中所用的數據集均來自ＵＣＩ數據庫，數據集包括Ｉｒｉｓ，Ｗｉｎｅ，Ｗｉｓｃｏｎｓｉｎ Ｄｉａｇｎｏｓｔｉｃ Ｂｒｅａｓｔ Ｃａｎｃｅｒ，ＳＰＥＣＴ Ｈｅａｒｔ和Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ。數據集的詳細描述見表１。

２．２ 相關定義

為了確定數據對象隨維度變化規律，我們定義了數據對象間的最大距離和平均距離來定量確定數據對象間的離散度。

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

２．３ 實驗結果

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

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

３維數對算法聚類精度的影響

３．１ 直接聚類

我們給出了確定聚類效果的準確度公式。假設數據集Ｄ中有ｋ個類，即Ｃｉ（ｉ＝１，…，ｋ），Oｉｐ（ｐ＝１，…，ｍｐ）是類Ci中的數據對象。數據集Ｄ經過聚類后，出現了ｋ個類Ｃｉ′（ｉ＝１，…，ｋ），Ｏｉｐ′（ｐ＝１，…，ｍｐ′）是Ci′類中的數據對象，準確度被定義為：

｜Ｃｋ∩Ｃｉ′｜是同時屬于類Ｃｉ和Ｃｉ′的數據對象Ｏｉｐ（ｐ＝１，…，ｍｐ）和Oip′（ｐ＝１，…，ｍｐ′）的個數；|D|是數據集D中的數據對象的個數。

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

３．２ ＰＣＡ降維聚類

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

對數據集降維后，Ｋ－ｍｅａｎｓ和層次聚類算法的聚類精度有所提高，但是效果不是很明顯。此結果也說明了 Ｋ－ｍｅａｎｓ和層次聚類對３０維以內的數據集的聚類精度比較高。

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

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

４基于復相關系數倒數降維

４．１ 復相關系數倒數加權

復相關系數的倒數賦權法是在方差倒數賦權法的基礎上提出來的。假設數據對象的某一屬性為Xk，則它的復相關系數記為ρk。ρk越大，表明Xk與其余的屬性越相關，越能被非Xk代替，也就是說Xk屬性對聚類的作用越小；反之，ρk越小，Xk與其余的屬性越不相關，Xk屬性對聚類的作用越大。所以可以用|ρi|-1計算數據對象屬性權重系數wk。

４．２ 降維實驗

我們也可以采用復相關系數的倒數賦權法作為一種特征選擇方法，對數據集中數據對象的每個屬性加權后，得到了每個屬性的權值，然后根據權值的大小，我們設定一個閾值參數σ，選擇權值大于σ的屬性，從而實現了對數據集的降維，然后對降維后數據集進行聚類。為了說明此方法的有效性，采用ｋ－ｍｅａｎｓ算法、層次聚類算法、ＣＡＤＤ （基于密度和密度可達聚類算法）算法對ＷＤＢＣ數據集和ＳＰＥＣＴ Ｈｅａｒｔ數據集進行聚類，來對比降維前和降維后的結果。

ＷＤＢＣ數據集有３０個屬性，取權值σ≥0.036時，該數據集降為３維；取權值大于０．０３４時，該數據集降為６維；取權值大于０．０３３時，該數據集降為１５維。降為３維、６維、１５維的數據集和原數據集的聚類精度如圖６所示，實驗結果表明該數據集降為６維時聚類效果最好。

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

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

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

５結論

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

主要參考文獻

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

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

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

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

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

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

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

［8］孟海東，宋飛燕，宋宇辰．面向復雜簇的聚類算法研究與實現［Ｊ］．計算機應用與軟件，２００８，２５（１０）：３２－３４．