譜聚類(lèi)算法及其研究進(jìn)展

《譜聚類(lèi)算法及其研究進(jìn)展》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、譜聚類(lèi)算法及其研究進(jìn)展　　摘要：譜聚類(lèi)具有良好的理論基礎(chǔ)，被廣泛應(yīng)用于科學(xué)研究與工程應(yīng)用的各個(gè)領(lǐng)域，成為聚類(lèi)分析領(lǐng)域重要的新興分支，受到越來(lái)越多的研究者的重視。然而，國(guó)內(nèi)相關(guān)文獻(xiàn)較少，該文從譜聚類(lèi)算法的產(chǎn)生、研究進(jìn)展、基礎(chǔ)理論及代表算法等方面對(duì)譜聚類(lèi)算法作簡(jiǎn)要綜述，有望使讀者對(duì)該領(lǐng)域形成初步認(rèn)識(shí)。　　關(guān)鍵詞：譜聚類(lèi)；聚類(lèi)；圖劃分　　中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044（2016）19-0159-03　　SpectralClusteringanditsResearchProgress　　XINGJ

2、ie-qing，F(xiàn)UChuan-yi　?。―epartmentofModernEducationTechnology，QiongtaiNormalCollege，Haikou571100，China）　　Abstract：Spectralclusteringhasgoodtheoreticfoundation，andhasbeenappliedinvariousscienceresearchandengineeringfields.Itbecomesanimportantnewpopulartoolforclusterin

3、ganalysis.Withitsdevelopment，spectralclusteringattractsmuchmoreattentionfromresearchers.However，therearefewliteraturesonit.Thispapergivesabriefreviewaboutthecreation，development，theoreticanalysisandclassicalmethodsofspectral10clustering.　　Keywords：spectralclusteri

4、ng；clustering；graphpartition　　聚類(lèi)作為無(wú)監(jiān)督學(xué)習(xí)方法，廣泛地應(yīng)用于統(tǒng)計(jì)科學(xué)、計(jì)算機(jī)科學(xué)、生物學(xué)、社會(huì)學(xué)以及心理學(xué)等，成為應(yīng)用最多的數(shù)據(jù)分析技術(shù)之一。其中，基于譜圖劃分理論的聚類(lèi)方法――譜聚類(lèi)，是目前研究較多、有深厚理論基礎(chǔ)、應(yīng)用廣泛的聚類(lèi)方法。與傳統(tǒng)的方法（如k-means，EM等）相比，它不對(duì)樣本空間的整體結(jié)構(gòu)做任何假設(shè)，能夠識(shí)別樣本點(diǎn)在空間上的非凸分布。因此，譜聚類(lèi)方法適用于具有任何分布形狀的樣本空間，從而求解到全局最優(yōu)解。此外，譜聚類(lèi)使得聚類(lèi)算法的研究得到很大的拓展，適用于許多現(xiàn)實(shí)應(yīng)用問(wèn)

5、題，已成功地應(yīng)用于文本分析、語(yǔ)音分析、圖像分割、機(jī)器視覺(jué)、商業(yè)分析、市場(chǎng)營(yíng)銷(xiāo)、計(jì)算生物學(xué)等等[1-3]。目前，譜聚類(lèi)方法的應(yīng)用還擴(kuò)展到醫(yī)學(xué)診斷[6]、DNA和蛋白質(zhì)等生物信息挖掘[5]、文本主題分析[4]等領(lǐng)域。對(duì)譜聚類(lèi)算法的研究具有科學(xué)意義和現(xiàn)實(shí)意義。同時(shí)，譜聚類(lèi)算法在實(shí)現(xiàn)上僅涉及標(biāo)準(zhǔn)的線性代數(shù)方法，易于實(shí)現(xiàn)?！　∽V聚類(lèi)算法是以圖論當(dāng)中的譜圖理論為基礎(chǔ)，重點(diǎn)在于設(shè)計(jì)合適的距離度量，計(jì)算待聚類(lèi)的數(shù)據(jù)點(diǎn)之間的距離或相似性，構(gòu)造鄰接圖，最后將聚類(lèi)任務(wù)轉(zhuǎn)化為鄰接有向圖的最優(yōu)劃分問(wèn)題。本文旨在從基礎(chǔ)理論、代表算法、比較分析等方面向

6、讀者介紹這種新型的聚類(lèi)算法。　　1譜聚類(lèi)算法研究進(jìn)展　　譜聚類(lèi)的誕生可以追溯到1973年，Donath和Hoffman10首次基于鄰接矩陣構(gòu)造了圖的劃分[7]。在同一年，F(xiàn)ieldler發(fā)現(xiàn)圖的二劃分與Laplacian圖的第二小特征向量有密切關(guān)系，并且建議使用該特征向量進(jìn)行圖的劃分[8]。從此以后，許多研究者加入到譜聚類(lèi)方法的研究隊(duì)伍中，例如，Pothen，Simon，andLiou[9]、Bolla[10]、HagenandKahng[11]、HendricksonandLeland[12]、VanDriesschea

7、ndRoose[13]和GuatteryandMiller[14]等。　　譜聚類(lèi)逐漸成為流行的聚類(lèi)方法[1-6]。在算法擴(kuò)展和理論分析方面涌現(xiàn)了大量的研究成果。Dhillon等人將譜聚類(lèi)應(yīng)用于聯(lián)合聚類(lèi)問(wèn)題[14]，并分析了譜聚類(lèi)與加權(quán)k-means的關(guān)系[19]。Bach等人利用譜聚類(lèi)輔助學(xué)習(xí)相似性函數(shù)[9]。Kempe等人分析了再分布式環(huán)境下的譜聚類(lèi)[21]。Perez等人提出了稀疏核譜聚類(lèi)并應(yīng)用于大尺度數(shù)據(jù)集[17]。Jia等人將集成學(xué)習(xí)方法應(yīng)用于譜聚類(lèi)[22]。Zhang等人設(shè)計(jì)了基于邊界的多路譜聚類(lèi)方法[14]。最

8、近，王春騰等分析了維數(shù)約簡(jiǎn)與譜聚類(lèi)的關(guān)系，提出了基于維數(shù)約簡(jiǎn)的譜聚類(lèi)方法：基于非負(fù)約束的譜聚類(lèi)算法（NMFSC）[15]和基于獨(dú)立成分分析的譜聚類(lèi)（ICASC）[16]?！　√貏e地，聚類(lèi)方法在圖像分割任務(wù)的應(yīng)用中，傳統(tǒng)的做法提取各像素點(diǎn)的特征向量，利用k-means等聚類(lèi)方法對(duì)像素點(diǎn)進(jìn)行聚類(lèi)。這類(lèi)方法固