面向高維數(shù)據(jù)的PCA-Hub聚類方法研究.pdf

1、傳統(tǒng)的聚類分析算法往往可以在低維數(shù)據(jù)空間中取得不錯的聚類效果，然而在高維數(shù)據(jù)空間中卻表現(xiàn)很差，這主要是由高維數(shù)據(jù)空間中的維數(shù)災難所引起的。維數(shù)災難造成的影響之一是距離集中，Hinneburg和 Aggarwal等人已經(jīng)對高維數(shù)據(jù)中的距離集中和無意義的最近鄰作了深入的研究。維數(shù)災難造成的另一方面影響是hubness現(xiàn)象，本文將會從這個新的方向進行深入分析。Hubness這一概念最初是在2010年由Milos Radovanovic等人提出

2、的，hubness描述的是這樣一種現(xiàn)象：在 k近鄰列表中某些對象趨向于高頻率地出現(xiàn)在其它對象的最近鄰居列表中。Milos Radovanovic等人利用這一屬性提出了四種hub聚類分析算法。Hub聚類算法雖然可以在高維數(shù)據(jù)空間中進行聚類分析，但是它卻忽略了高維數(shù)據(jù)空間中的冗余和噪聲數(shù)據(jù)，從而無法獲得更優(yōu)的簇結構以及更快的聚類收斂速度。
　　本文針對hub聚類分析算法的上述問題，提出了一種基于逆近鄰數(shù)偏度降維的PCA-Hub聚類分析

3、算法，此算法可以解決高維數(shù)據(jù)空間中的冗余和噪聲數(shù)據(jù)，并且能夠獲得更好的簇結構和更快的聚類收斂速度。實驗結果表明，PCA-Hub聚類算法相比之前的聚類算法在輪廓系數(shù)上平均提高了15％；當數(shù)據(jù)集的維數(shù)或者逆近鄰數(shù)的偏度較高時，PCA-Hub聚類算法對近鄰數(shù)k的選擇未表現(xiàn)出強烈的相關性；在實驗環(huán)境和聚類參數(shù)一致的情況下，PCA-Hub聚類算法的結果在很大程度上具有一致性。
　　PCA-Hub聚類算法雖然可以很好地解決高維數(shù)據(jù)空間中的冗余

4、和噪聲特征，然而隨著數(shù)據(jù)集樣本數(shù)和數(shù)據(jù)集維數(shù)的不斷增加，PCA-Hub聚類算法的時間復雜度將會變得越來越嚴重甚至不可接受。因此，本文提出了一種Quick PCA-Hub聚類分析算法從快速搜索前k個理想的主成分來加快PCA-Hub算法的聚類分析速度。實驗結果表明，Quick PCA-Hub聚類算法相比之前的聚類算法在輪廓系數(shù)上平均提高了8%；Quick PCA-Hub在高維數(shù)據(jù)空間中搜索理想的前k個主成分時表現(xiàn)出了巨大的優(yōu)勢。