affinitypropagation聚類算法的擴(kuò)展及改進(jìn)研究

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

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

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

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

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

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

6、點(diǎn)數(shù)目超過(guò)某個(gè)閾值，它就被稱為有效“單元網(wǎng)格”。“單元網(wǎng)格”的數(shù)據(jù)結(jié)構(gòu)定義為：DS(g)=(Grid_Label,Grid_Position,Grid_Range,Point_Number)(1)式(1)中，Grid_Label:記錄“單元網(wǎng)格”的標(biāo)號(hào)；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ū)間長(zhǎng)度；)

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