affinitypropagation聚類算法的擴展及改進研究

《affinitypropagation聚類算法的擴展及改進研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、AffinityPropagation聚類算法的擴展及改進研究AffinityPropagation聚類算法的擴展及改進研究陳新泉上饒師范學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院，江西上饒（334001）摘要當(dāng)前在有限區(qū)域內(nèi)分布的稀疏不均的、具有一定分布結(jié)構(gòu)的海量數(shù)據(jù)點集的聚類分析是一個尚未圓滿解決的難題，針對AffinityPropagation(AP)聚類算法的不足之處，提出了兩個擴展及改進型的聚類算法。在這兩個算法中，基于“單元網(wǎng)格”的AP聚類算法是在“單元網(wǎng)格”層次上對AP聚類算法的一種擴展，而基于近鄰點集的AP聚類算法是試圖在時間上對AP聚類算法做一些改進。為實現(xiàn)這兩個算法

2、介紹了“單元網(wǎng)格”、近鄰點集等幾個比較重要的概念及思想方法。最后給出了一點頗有價值的研究方向。關(guān)鍵詞：相似性度量；AffinityPropagation;單元網(wǎng)格；近鄰點集中圖分類號：TP1811.引言當(dāng)前，高維、噪聲、孤立點、大小形狀不一、數(shù)據(jù)點的空間分布不均的海量數(shù)據(jù)集的聚類分析仍未獲得圓滿的解決。AffinityPropagation聚類算法是B.J.Frey等[1]于2007年發(fā)表在science上的一種聚類方法。盡管該文稱其聚類效果很好，計算速度也很快，但它也有幾個缺點。第一，它也需要事先定義一個相似性度量，從而計算出數(shù)據(jù)點集之間的相似性矩陣來，這在時間和空

3、間上就需要O(n2)。第二，迭代次數(shù)需要人工設(shè)定，而且聚類結(jié)果對此也較敏感。第三，獲得聚類結(jié)果后，不能獲得聚類分布的層次性，有時這是不夠的?；诿芏鹊木垲愃惴ǎ饕蠩ster等[2]提出的DBSCAN算法和Ertoz等[3]提出的SNN算法。DBSCAN算法最初的時間復(fù)雜度為O(n2)。后續(xù)的研究者設(shè)計出支持區(qū)域查詢的空間索引結(jié)構(gòu)，宣稱將時間復(fù)雜度降低到O(nlogn)。我們認為，具有這種時間復(fù)雜度的算法能滿足海量數(shù)據(jù)集的聚類分析，但未必適合于高維情形下的聚類分析。因為這種建立在樹型存儲結(jié)構(gòu)上的改進式算法忽略了維數(shù)對存儲空間及時間復(fù)雜度的影響。本文針對在m維有限區(qū)域

4、內(nèi)分布的海量數(shù)據(jù)點集，構(gòu)造出一種與相應(yīng)數(shù)據(jù)結(jié)構(gòu)相匹配的能改善時間及空間復(fù)雜度的高效聚類算法。該算法既有DBSCAN聚類算法的一點思想，也具有AffinityPropagation算法的一些方法，還具有多維網(wǎng)格劃分法的一些優(yōu)化改進方面的實現(xiàn)技術(shù)。本文第2節(jié)描述了“單元網(wǎng)格”層次上的聚類分析的概念及相關(guān)定義，第3節(jié)介紹了基于“單元網(wǎng)格”的AP聚類算法，第4節(jié)介紹了基于近鄰點集的AP聚類算法，最后對本文作簡要的總結(jié)并指出進一步的研究方向。2.“單元網(wǎng)格”層次上的聚類分析2.1問題描述設(shè)數(shù)據(jù)點集},,,{21nXXXSL=位于m維有序?qū)傩钥臻g)(1mAA××L的某個區(qū)域內(nèi)。如

5、果數(shù)據(jù)點集分布非常密集，數(shù)據(jù)點數(shù)目也非常多，則可采用多維網(wǎng)格劃分法來統(tǒng)計具有一定數(shù)據(jù)點數(shù)目的“單元網(wǎng)格”，從而將對數(shù)據(jù)點集的聚類分析轉(zhuǎn)換為有效“單元網(wǎng)格”的空間結(jié)1//.paper.edu中國科技論文在線構(gòu)分布分析，這樣可以提高算法的效率。以“單元網(wǎng)格”的數(shù)據(jù)點數(shù)目來描述該“單元網(wǎng)格”，就有點基于密度聚類的思想。以一個“單元網(wǎng)格”代替某個小區(qū)域的“數(shù)據(jù)點”作為一個小整體來進行聚類分析，這就是“單元網(wǎng)格”層次的近似聚類分析。2.2幾個定義定義1：“單元網(wǎng)格”的定義：數(shù)據(jù)點集經(jīng)過多維網(wǎng)格劃分后得到一個個相連接的單個網(wǎng)格，就被稱為“單元網(wǎng)格”。若某個“單元網(wǎng)格”所包含的數(shù)據(jù)

6、點數(shù)目超過某個閾值，它就被稱為有效“單元網(wǎng)格”?！皢卧W(wǎng)格”的數(shù)據(jù)結(jié)構(gòu)定義為：DS(g)=(Grid_Label,Grid_Position,Grid_Range,Point_Number)(1)式(1)中，Grid_Label:記錄“單元網(wǎng)格”的標號；Grid_Position:記錄“單元網(wǎng)格”的中心位置，它為m維向量，即),,(1mppPL=；Grid_Range:記錄“單元網(wǎng)格”所包含的區(qū)域范圍，它為m維的有序局部區(qū)間，即：])2/,2/[,],2/,2/([1111mmmmrprprprpR+??+??=L(2)式(2)中，為“單元網(wǎng)格”在第i維的區(qū)間長度；)

7、,,1(miriL=Point_Number:記錄“單元網(wǎng)格”所包含的數(shù)據(jù)點數(shù)目。這樣，原來對n個數(shù)據(jù)點的聚類分析就可以轉(zhuǎn)換為N個“單元網(wǎng)格”的空間拓撲結(jié)構(gòu)分析了。定義2：“單元網(wǎng)格”間的相似性度量設(shè)有效“單元網(wǎng)格”集為},,,{)(21NgggSGridL=，當(dāng)jigg≠時，借鑒萬有引力定律及庫侖定律，定義一種相似性度量為),(1)()(),(??jijijiggdgcgcggs+??=(3)式(3)中，采用“單元網(wǎng)格”g),(jiggdi和gj的中心點之間的距離來作為它們的相異性度量，c(gi)為有效“單元網(wǎng)格”gi所含數(shù)據(jù)點的個數(shù)。對歸一化，得