１ 引 言
聚類分析是數(shù)據(jù)挖掘領(lǐng)域中的一項重要的研究課題，高維數(shù)據(jù)對象的聚類又是聚類分析的重要研究課題，也是涉及到聚類算法是否能夠有效地應用于各個領(lǐng)域，例如多屬性（高維）流數(shù)據(jù)的聚類分析。高維數(shù)據(jù)的特點表現(xiàn)為：①高維數(shù)據(jù)集中存在大量無關(guān)的屬性使得在所有維中存在簇的可能性幾乎為零；②高維空間中數(shù)據(jù)比低維空間中數(shù)據(jù)分布稀疏，其中數(shù)據(jù)間距離幾乎相等是普遍現(xiàn)象。目前，對高維數(shù)據(jù)的聚類主要有3種方法：屬性轉(zhuǎn)換、子空間聚類、協(xié)同聚類、屬性轉(zhuǎn)換是通過創(chuàng)建新屬性，將一些舊屬性合并在一起來降低數(shù)據(jù)集的維度的方法。目前，主成分分析方法（ＰＣＡ）、自組織特征映射（ＳＯＭ）、多維縮放（ＭＤＳ）、小波分析等是普遍應用的降維方法。雖然采用降維技術(shù)使得數(shù)據(jù)的維度大大降低，但數(shù)據(jù)的可理解性和可解釋性變得較差，一些對聚類有用的信息也可能會隨之丟失，很難準確地表達和理解結(jié)果。在處理高維數(shù)據(jù)時，采用屬性轉(zhuǎn)換的方法得到的聚類效果并不是很理想，有一定的局限性，不能滿足當前高維聚類算法發(fā)展的需要。
子空間聚類算法對特征選擇的任務進行了拓展，它是在同一個數(shù)據(jù)集的不同子空間上進行聚類。子空間聚類和特征選擇一樣使用搜索策略和評測標準來篩選出需要聚類的簇，因為不同的子空間上存在不同的簇，因此我們要對評測標準設置一些條件。
協(xié)同聚類在數(shù)據(jù)點聚類和屬性聚類之間達到了一種平衡。因為它從對象―屬性兩個角度同時進行聚類操作。假設Ｘ是由數(shù)據(jù)對象和數(shù)據(jù)屬性構(gòu)成的矩陣，一般被叫做關(guān)系矩陣、可能性矩陣、影響矩陣、頻率矩陣等。一般被應用于反映基因響應的強度、一個Ｗeb頁面的點擊率，或一個倉庫里各項商品的銷售數(shù)量等。Ｇｏｖａｅｒｔ于１９９５提出了可能性矩陣表中行列塊的同時聚類算法。Ｄｈｉｌｌｏｎ于２００１年提出了一種協(xié)同代數(shù)聚類算法，它與文本挖掘相關(guān)，是基于二部圖和它們的最小切割的。Ｏｙａｎａｇｉ等人于２００１年提出了一種簡單的Ｐｉｎｇ－Ｐｏｎｇ算法，它能在稀疏二元矩陣中發(fā)現(xiàn)相應區(qū)域，該算法能建立矩陣元素的橫向聯(lián)系，并用此來重新分布列對行的影響，并反過來進行。
本文在對數(shù)據(jù)對象間的最大距離和平均距離隨維數(shù)增加的變化趨勢實驗基礎上，通過實驗研究了聚類算法的聚類精度隨數(shù)據(jù)對象維度的變化特征。同時，提出了利用復相關(guān)系數(shù)倒數(shù)閾值實現(xiàn)降維的方法。
?。?數(shù)據(jù)對象離散度與維度的關(guān)系
?。玻?實驗數(shù)據(jù)
實驗中所用的數(shù)據(jù)集均來自ＵＣＩ數(shù)據(jù)庫，數(shù)據(jù)集包括Ｉｒｉｓ，Ｗｉｎｅ，Ｗｉｓｃｏｎｓｉｎ Ｄｉａｇｎｏｓｔｉｃ Ｂｒｅａｓｔ Ｃａｎｃｅｒ，ＳＰＥＣＴ Ｈｅａｒｔ和Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ。數(shù)據(jù)集的詳細描述見表１。
?。玻?相關(guān)定義
為了確定數(shù)據(jù)對象隨維度變化規(guī)律，我們定義了數(shù)據(jù)對象間的最大距離和平均距離來定量確定數(shù)據(jù)對象間的離散度。
最大距離：假設數(shù)據(jù)集D有n個數(shù)據(jù)對象，每個數(shù)據(jù)對象有ｄ個屬性（維），即Ｘｉ＝｛ｘｋ，ｋ＝１，…，ｄ｝，ｉ＝１，…，n。數(shù)據(jù)對象間的最大距離被定義為：
?。玻?實驗結(jié)果
為了研究維數(shù)對聚類精度的影響，有必要研究對象間的距離隨維數(shù)增高的變化趨勢。根據(jù)上面定義的公式（１）和公式（２），數(shù)據(jù)對象間的最大距離和平均距離隨維數(shù)的增加而增大。我們使用ＵＣＩ數(shù)據(jù)庫中的Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ數(shù)據(jù)集，先對數(shù)據(jù)集進行最小―最大標準化處理，然后計算此數(shù)據(jù)集中數(shù)據(jù)對象間隨維數(shù)增高的最大距離和平均距離。實驗結(jié)果分別顯示在圖１和圖２中。
如圖１和圖２所示，隨著維數(shù)的增加，數(shù)據(jù)對象間的最大距離和平均距離逐漸增大。表明數(shù)據(jù)對象在高維數(shù)據(jù)空間變得比較稀疏，很可能導致數(shù)據(jù)空間中客觀簇的消失，使得基于距離的聚類算法往往不能夠取得良好的聚類效果。因此，為了獲得有效的聚類結(jié)果，基于距離、密度和密度可達的聚類算法有必要進行改進或降維。
３ 維數(shù)對算法聚類精度的影響
?。常?直接聚類
我們給出了確定聚類效果的準確度公式。假設數(shù)據(jù)集Ｄ中有ｋ個類，即Ｃｉ（ｉ＝１，…，ｋ），Oｉｐ（ｐ＝１，…，ｍｐ）是類Ci中的數(shù)據(jù)對象。數(shù)據(jù)集Ｄ經(jīng)過聚類后，出現(xiàn)了ｋ個類Ｃｉ′（ｉ＝１，…，ｋ），Ｏｉｐ′（ｐ＝１，…，ｍｐ′）是Ci′類中的數(shù)據(jù)對象，準確度被定義為：
?。茫搿桑茫椤洌峭瑫r屬于類Ｃｉ和Ｃｉ′的數(shù)據(jù)對象Ｏｉｐ（ｐ＝１，…，ｍｐ）和Oip′（ｐ＝１，…，ｍｐ′）的個數(shù)；|D|是數(shù)據(jù)集D中的數(shù)據(jù)對象的個數(shù)。
為了研究維數(shù)對算法聚類精度的影響，我們分別用Ｋ－ｍｅａｎｓ和層次聚類算法對以上５個不同維數(shù)的數(shù)據(jù)集進行聚類分析，聚類結(jié)果如圖３所示。當數(shù)據(jù)集的維數(shù)小于３０的時候，兩種聚類算法的性能較好，當數(shù)據(jù)集的維數(shù)大于３０的時候，聚類算法的精度隨維數(shù)的增高而降低。實驗結(jié)果在一定程度上表明，當數(shù)據(jù)集的維數(shù)小于３０的時候，傳統(tǒng)的聚類算法，如Ｋ－ｍｅａｎｓ和層次聚類算法，這種基于距離的聚類算法是有效的，但是當維數(shù)大于３０的時候它們的聚類結(jié)果很不理想。
?。常?ＰＣＡ降維聚類
?。祝椋睿鍞?shù)據(jù)集有１３維，經(jīng)過主成分分析（ＰＣＡ）降維后，原有的１３維變成了３維，為了比較ＰＣＡ降維前和降維后的效果，我們用Ｋ－ｍｅａｎｓ和層次聚類算法對原有的數(shù)據(jù)集和經(jīng)過降維后的數(shù)據(jù)集進行聚類，結(jié)果如圖４所示。
對數(shù)據(jù)集降維后，Ｋ－ｍｅａｎｓ和層次聚類算法的聚類精度有所提高，但是效果不是很明顯。此結(jié)果也說明了 Ｋ－ｍｅａｎｓ和層次聚類對３０維以內(nèi)的數(shù)據(jù)集的聚類精度比較高。
Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ數(shù)據(jù)集有９０維，經(jīng)過ＰＣＡ降維后變成了１０維，降維前和降維后的聚類結(jié)果如圖５所示。
降維前和降維后Ｋ－ｍｅａｎｓ和層次聚類算法的聚類精度都很低，結(jié)果表明：①以上兩種聚類算法不能有效地處理高維數(shù)據(jù)；②ＰＣＡ降維對聚類算法不總是有效的；③此數(shù)據(jù)集包含１５個類，對于高維、多類的數(shù)據(jù)集，聚類算法不能很好地辨別存在的類（簇）。
?。?基于復相關(guān)系數(shù)倒數(shù)降維
?。矗?復相關(guān)系數(shù)倒數(shù)加權(quán)
復相關(guān)系數(shù)的倒數(shù)賦權(quán)法是在方差倒數(shù)賦權(quán)法的基礎上提出來的。假設數(shù)據(jù)對象的某一屬性為Xk，則它的復相關(guān)系數(shù)記為ρk。ρk越大，表明Xk與其余的屬性越相關(guān)，越能被非Xk代替，也就是說Xk屬性對聚類的作用越??；反之，ρk越小，Xk與其余的屬性越不相關(guān)，Xk屬性對聚類的作用越大。所以可以用|ρi|-1計算數(shù)據(jù)對象屬性權(quán)重系數(shù)wk。
４．２ 降維實驗
我們也可以采用復相關(guān)系數(shù)的倒數(shù)賦權(quán)法作為一種特征選擇方法，對數(shù)據(jù)集中數(shù)據(jù)對象的每個屬性加權(quán)后，得到了每個屬性的權(quán)值，然后根據(jù)權(quán)值的大小，我們設定一個閾值參數(shù)σ，選擇權(quán)值大于σ的屬性，從而實現(xiàn)了對數(shù)據(jù)集的降維，然后對降維后數(shù)據(jù)集進行聚類。為了說明此方法的有效性，采用ｋ－ｍｅａｎｓ算法、層次聚類算法、ＣＡＤＤ （基于密度和密度可達聚類算法）算法對ＷＤＢＣ數(shù)據(jù)集和ＳＰＥＣＴ Ｈｅａｒｔ數(shù)據(jù)集進行聚類，來對比降維前和降維后的結(jié)果。
?。祝模拢脭?shù)據(jù)集有３０個屬性，取權(quán)值σ≥0.036時，該數(shù)據(jù)集降為３維；取權(quán)值大于０．０３４時，該數(shù)據(jù)集降為６維；取權(quán)值大于０．０３３時，該數(shù)據(jù)集降為１５維。降為３維、６維、１５維的數(shù)據(jù)集和原數(shù)據(jù)集的聚類精度如圖６所示，實驗結(jié)果表明該數(shù)據(jù)集降為６維時聚類效果最好。
?。樱校牛茫?Ｈｅａｒｔ數(shù)據(jù)集有４４個屬性，取權(quán)值大于０．０２４時，該數(shù)據(jù)集降為５維；取權(quán)值大于０．０２３時，該數(shù)據(jù)集降為１８維；取權(quán)值大于０．０２２時，該數(shù)據(jù)集降為２８維。降為５維、１８維、２８維的數(shù)據(jù)集和原數(shù)據(jù)集的聚類精度如圖７所示，實驗結(jié)果表明該數(shù)據(jù)集降為１８維時聚類效果最好。
?。蹋椋猓颍幔?Ｍｏｖｅｍｅｎｔ數(shù)據(jù)集有９０個屬性，取權(quán)值大于０．０１１ １１３時，該數(shù)據(jù)集降為１０維；取權(quán)值大于０．０１１ １１１時，該數(shù)據(jù)集降為３４維；取權(quán)值大于０．０１１ １１０時，該數(shù)據(jù)集降為４７維。降為１０維、３４維、４７維的數(shù)據(jù)集和原數(shù)據(jù)集的聚類精度如圖８所示。實驗結(jié)果表明聚類算法對該數(shù)據(jù)集的聚類效果較差，原因是此數(shù)據(jù)集包含１５個類，類比較多，聚類算法不能很好地識別，但是該數(shù)據(jù)集降為４７維時聚類效果有所提高，仍能體現(xiàn)出本文降維方法的有效性，ＣＡＤＤ算法的聚類效果相對好一些，從而體現(xiàn)了ＣＡＤＤ算法的優(yōu)越性。
由以上實驗結(jié)果表明：①采用復相關(guān)系數(shù)的倒數(shù)賦權(quán)法作為一種屬性選擇方法是有效的，并且計算量較小，適合處理高維數(shù)據(jù)；②降維要降到合適的維度，如果維數(shù)太少，則會丟失對聚類重要的屬性信息，如果維數(shù)太多，則會產(chǎn)生“噪聲”，影響聚類結(jié)果；③一般的聚類算法不能很好地處理高維且類比較多的數(shù)據(jù)集，因此有待于進一步研究能處理高維且類比較多的數(shù)據(jù)集的聚類算法。
?。?結(jié) 論
對于傳統(tǒng)的基于距離的聚類算法，當數(shù)據(jù)對象的維數(shù)小于或等于３０時，聚類分析往往能夠取得良好的聚類效果；維數(shù)高于３０時，聚類效果不佳。甚至使用ＰＣＡ降維后，聚類算法對高維數(shù)據(jù)的聚類效果的改進也不是很明顯。用復相關(guān)系數(shù)的倒數(shù)賦權(quán)法為差異度加權(quán)，并且把復相關(guān)系數(shù)的倒數(shù)賦權(quán)法用作一種屬性選擇方法，通過設定屬性加權(quán)系數(shù)的閾值參數(shù)對數(shù)據(jù)對象進行降維也能取得較好的聚類結(jié)果。
