１ 引 言
聚類分析是數(shù)據(jù)挖掘領(lǐng)域中的一項(xiàng)重要的研究課題，高維數(shù)據(jù)對(duì)象的聚類又是聚類分析的重要研究課題，也是涉及到聚類算法是否能夠有效地應(yīng)用于各個(gè)領(lǐng)域，例如多屬性（高維）流數(shù)據(jù)的聚類分析。高維數(shù)據(jù)的特點(diǎn)表現(xiàn)為：①高維數(shù)據(jù)集中存在大量無關(guān)的屬性使得在所有維中存在簇的可能性幾乎為零；②高維空間中數(shù)據(jù)比低維空間中數(shù)據(jù)分布稀疏，其中數(shù)據(jù)間距離幾乎相等是普遍現(xiàn)象。目前，對(duì)高維數(shù)據(jù)的聚類主要有3種方法：屬性轉(zhuǎn)換、子空間聚類、協(xié)同聚類、屬性轉(zhuǎn)換是通過創(chuàng)建新屬性，將一些舊屬性合并在一起來降低數(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)來篩選出需要聚類的簇，因?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頁面的點(diǎn)擊率，或一個(gè)倉庫里各項(xiàng)商品的銷售數(shù)量等。Ｇｏｖａｅｒｔ于１９９５提出了可能性矩陣表中行列塊的同時(shí)聚類算法。Ｄｈｉｌｌｏｎ于２００１年提出了一種協(xié)同代數(shù)聚類算法，它與文本挖掘相關(guān)，是基于二部圖和它們的最小切割的。Ｏｙａｎａｇｉ等人于２００１年提出了一種簡單的Ｐｉｎｇ－Ｐｏｎｇ算法，它能在稀疏二元矩陣中發(fā)現(xiàn)相應(yīng)區(qū)域，該算法能建立矩陣元素的橫向聯(lián)系，并用此來重新分布列對(duì)行的影響，并反過來進(jìn)行。
本文在對(duì)數(shù)據(jù)對(duì)象間的最大距離和平均距離隨維數(shù)增加的變化趨勢(shì)實(shí)驗(yàn)基礎(chǔ)上，通過實(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ù)集均來自ＵＣＩ數(shù)據(jù)庫，數(shù)據(jù)集包括Ｉｒｉｓ，Ｗｉｎｅ，Ｗｉｓｃｏｎｓｉｎ Ｄｉａｇｎｏｓｔｉｃ Ｂｒｅａｓｔ Ｃａｎｃｅｒ，ＳＰＥＣＴ Ｈｅａｒｔ和Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ。數(shù)據(jù)集的詳細(xì)描述見表１。
２．２ 相關(guān)定義
為了確定數(shù)據(jù)對(duì)象隨維度變化規(guī)律，我們定義了數(shù)據(jù)對(duì)象間的最大距離和平均距離來定量確定數(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ù)庫中的Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ數(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)過聚類后，出現(xiàn)了ｋ個(gè)類Ｃｉ′（ｉ＝１，…，ｋ），Ｏｉｐ′（ｐ＝１，…，ｍｐ′）是Ci′類中的數(shù)據(jù)對(duì)象，準(zhǔn)確度被定義為：
?。茫搿桑茫椤洌峭瑫r(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)過主成分分析（ＰＣＡ）降維后，原有的１３維變成了３維，為了比較ＰＣＡ降維前和降維后的效果，我們用Ｋ－ｍｅａｎｓ和層次聚類算法對(duì)原有的數(shù)據(jù)集和經(jīng)過降維后的數(shù)據(jù)集進(jìn)行聚類，結(jié)果如圖４所示。
對(duì)數(shù)據(jù)集降維后，Ｋ－ｍｅａｎｓ和層次聚類算法的聚類精度有所提高，但是效果不是很明顯。此結(jié)果也說明了 Ｋ－ｍｅａｎｓ和層次聚類對(duì)３０維以內(nèi)的數(shù)據(jù)集的聚類精度比較高。
?。蹋椋猓颍幔?Ｍｏｖｅｍｅｎｔ數(shù)據(jù)集有９０維，經(jīng)過ＰＣＡ降維后變成了１０維，降維前和降維后的聚類結(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ǔ)上提出來的。假設(shè)數(shù)據(jù)對(duì)象的某一屬性為Xk，則它的復(fù)相關(guān)系數(shù)記為ρk。ρk越大，表明Xk與其余的屬性越相關(guān)，越能被非Xk代替，也就是說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)行聚類。為了說明此方法的有效性，采用ｋ－ｍｅａｎｓ算法、層次聚類算法、ＣＡＤＤ （基于密度和密度可達(dá)聚類算法）算法對(duì)ＷＤＢＣ數(shù)據(jù)集和ＳＰＥＣＴ Ｈｅａｒｔ數(shù)據(jù)集進(jìn)行聚類，來對(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)法用作一種屬性選擇方法，通過設(shè)定屬性加權(quán)系數(shù)的閾值參數(shù)對(duì)數(shù)據(jù)對(duì)象進(jìn)行降維也能取得較好的聚類結(jié)果。
