譜聚類算法及其應用研究.pdf

1、聚類分析是一種研究樣本分類的統(tǒng)計方法,也是一種數(shù)據(jù)挖掘的方法,可以有效地實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的探測,在國際上已成近年機器學習領(lǐng)域的研究熱點。譜聚類算法作為聚類算法的一個分支是一個重要的研究方向,以圖論作為理論基礎(chǔ),基本思想是將聚類問題轉(zhuǎn)化為圖論中的對無向加權(quán)圖的最優(yōu)分割問題。與現(xiàn)有的其他典型的聚類分析算法相比較而言,譜聚類算法在聚類的過程中降低了對樣本空間形狀的要求,同時譜聚類算法還可以有效的克服一些經(jīng)典聚類算法易收斂于局部最優(yōu)解的缺點,可以得

2、到收斂于全局的最優(yōu)解。
　　本文在對前人研究譜聚類算法所取得的現(xiàn)有成果進行了系統(tǒng)的學習,對已有的相關(guān)算法進行了部分改進。具體的工作內(nèi)容概括如下:
　　1)首先介紹了關(guān)于聚類算法特別是譜聚類算法的基本概念以及理論基礎(chǔ),分析了譜聚類算法中的一些相關(guān)技術(shù)的已有的研究成果以及應用的現(xiàn)狀,然后對譜聚類研究領(lǐng)域中所涉及的幾個關(guān)鍵性問題進行了總結(jié),歸納了譜聚類算法未來的幾個關(guān)鍵的研究方向。
　　2)針對傳統(tǒng)的譜聚類算法中的兩個基本的

3、難點:相似矩陣的構(gòu)造以及自動確定類的數(shù)目問題,本文通過定義的一種新的距離度量—密度敏感的距離和引入的特征間隙兩個概念,提出了一種基于密度敏感的自適應譜聚類算法。新提出算法的有效性在模擬數(shù)據(jù)集以及UCI數(shù)據(jù)集上的實驗中都得到了較好的驗證,同時本文還計算了該算法與傳統(tǒng)的SC算法的分類正確率,比較結(jié)果顯示新算法的聚類性明顯優(yōu)于SC算法。
　　3)針對IPCM算法對稀疏程度不同的樣本集的聚類效果不理想,而且需要人工手動輸入聚類數(shù)目的缺點,

4、本文通過引入密度敏感的距離與特征間隙兩個概念,提出一種基于譜聚類的自適應IPCM算法,該算法用密度敏感的距離代替?zhèn)鹘y(tǒng)的歐氏距離,并通過特征間隙的性質(zhì)準確地計算出聚類數(shù)目。通過數(shù)據(jù)實驗,證明了改進后的算法的有效性以及正確率都有所提高,同時該算法能夠有效的彌補IPCM算法及譜聚類算法在各自單獨聚類時所存在的缺點。
　　4)將本文所提的密度敏感相似性度量引入到判別割算法中,代替原有的歐氏距離,以此對判別割算法進行改進,在此基礎(chǔ)上提出了一