基于特征間隙檢測簇數(shù)的譜聚類算法研究.pdf

1、譜聚是聚類的一個重要分支。譜聚類算法不同于其他傳統(tǒng)聚類算法，它將聚類問題轉(zhuǎn)化成圖的最優(yōu)劃分問題。譜聚類算法不關(guān)心數(shù)據(jù)集的形狀，能處理復(fù)雜、高維非球形的數(shù)據(jù)樣本。同時，譜聚類算法實現(xiàn)簡單，計算復(fù)雜度小，非常適合處理大型數(shù)據(jù)集，可應(yīng)用到分布式系統(tǒng)中去，并能獲得全局最優(yōu)解，改善聚類效果。
　　譜聚類算法的難點之一是聚類簇數(shù)k值的檢測。大多數(shù)聚類算法都需要人工提前來設(shè)定聚類簇數(shù)，而不合適的聚類簇數(shù)會導(dǎo)致不理想的聚類效果，甚至?xí)咕垲愡^程失

2、去意義。另外，譜聚類算法的另一個研究熱點是分布式譜聚。集中式的譜聚類算法不能直接適用于分布式系統(tǒng)。對此，本文對傳統(tǒng)的譜聚類算法作出了如下改進(jìn)：
　　首先，本文提出了一種基于特征間隙的簇數(shù)檢測（Identifying Clustering Number based on Eigengap,ICNE）算法。通過構(gòu)建基于鄰接矩陣的規(guī)范拉普拉斯矩陣，順序求解拉普拉斯矩陣的特征解，計算矩陣相鄰特征值的間隙，判斷出特征間隙的所在位置，確定簇數(shù)

3、k，ICNE方法只需求解出前k個特征解，從而減少了特征求解的計算量，實現(xiàn)了快速有效地確定聚類簇數(shù)k。
　　其次，提出了一種基于ICNE方法的分布式譜聚類(Decentralized Spectral Clustering with Identifying Clustering Number based on Eigengap,DSC-ICNE)方法，以分布式方式完成自動譜聚類，使得譜聚類方法可以應(yīng)用于分布式系統(tǒng)，提高譜聚類算法的可

4、擴(kuò)展性。
　　最后，提出了基于特征間隙檢測簇數(shù)的譜聚類（Spectral Clustering withIdentifying Clustering Number based on Eigengap,SC-ICNE）算法，在ICNE算法的基礎(chǔ)上快速有效地確定聚類簇數(shù)k，完成譜聚類算法。并對SC-ICNE算法在UCI數(shù)據(jù)庫上進(jìn)行了仿真，仿真結(jié)果表明，SC-ICNE算法能夠快速有效地實現(xiàn)聚類，而且相對于k-means算法，SC-ICN