譜聚類算法及其應(yīng)用研究.pdf

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

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

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

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