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

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

1、譜聚類算法及其研究進(jìn)展　　摘要：譜聚類具有良好的理論基礎(chǔ)，被廣泛應(yīng)用于科學(xué)研究與工程應(yīng)用的各個領(lǐng)域，成為聚類分析領(lǐng)域重要的新興分支，受到越來越多的研究者的重視。然而，國內(nèi)相關(guān)文獻(xiàn)較少，該文從譜聚類算法的產(chǎn)生、研究進(jìn)展、基礎(chǔ)理論及代表算法等方面對譜聚類算法作簡要綜述，有望使讀者對該領(lǐng)域形成初步認(rèn)識?！　￡P(guān)鍵詞：譜聚類；聚類；圖劃分　　中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：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　　聚類作為無監(jiān)督學(xué)習(xí)方法，廣泛地應(yīng)用于統(tǒng)計科學(xué)、計算機(jī)科學(xué)、生物學(xué)、社會學(xué)以及心理學(xué)等，成為應(yīng)用最多的數(shù)據(jù)分析技術(shù)之一。其中，基于譜圖劃分理論的聚類方法――譜聚類，是目前研究較多、有深厚理論基礎(chǔ)、應(yīng)用廣泛的聚類方法。與傳統(tǒng)的方法（如k-means，EM等）相比，它不對樣本空間的整體結(jié)構(gòu)做任何假設(shè)，能夠識別樣本點(diǎn)在空間上的非凸分布。因此，譜聚類方法適用于具有任何分布形狀的樣本空間，從而求解到全局最優(yōu)解。此外，譜聚類使得聚類算法的研究得到很大的拓展，適用于許多現(xiàn)實應(yīng)用問

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

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

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

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