P2P系統(tǒng)中聚類算法的研究.pdf

1、隨著 P2P技術(shù)的不斷發(fā)展,P2P系統(tǒng)已經(jīng)成為儲(chǔ)存海量數(shù)據(jù)的容器,如何在這樣一個(gè)包含豐富數(shù)據(jù)的容器中發(fā)現(xiàn)知識(shí)成為越來(lái)越多的學(xué)者研究的內(nèi)容。P2P技術(shù)最大的特點(diǎn)是沒(méi)有中心節(jié)點(diǎn),系統(tǒng)完全分布,這雖然使得P2P系統(tǒng)具有健壯性和可擴(kuò)展性,但也加大了設(shè)計(jì)適用于P2P系統(tǒng)的數(shù)據(jù)挖掘算法的難度。
　　聚類是一種常用的數(shù)據(jù)挖掘技術(shù)。本文在分析了不同 P2P拓?fù)浣Y(jié)構(gòu)特點(diǎn)的基礎(chǔ)上,通過(guò)深入研究了不同聚類算法的聚類過(guò)程,總結(jié)了 P2P系統(tǒng)中的聚類算法需

2、要滿足的條件,并在此基礎(chǔ)上設(shè)計(jì)了 KIPN(K-mean In P2p Networks)聚類算法和SOC(Structure Overlay Clustering)聚類算法分別用于非結(jié)構(gòu)化拓和結(jié)構(gòu)化拓?fù)銹2P系統(tǒng)的聚類。
　　KIPN算法是一個(gè)非結(jié)構(gòu)化拓?fù)銹2P系統(tǒng)的k-mean算法,通過(guò)擴(kuò)展經(jīng)典k-mean算法的迭代過(guò)程,在每個(gè)節(jié)點(diǎn)只與其直接相鄰節(jié)點(diǎn)交換信息的情況下通過(guò)有限次迭代使每個(gè)節(jié)點(diǎn)上的局部數(shù)據(jù)在全局視圖下聚類。經(jīng)實(shí)驗(yàn)數(shù)

3、據(jù)分析驗(yàn)證KIPN算法可以適應(yīng)P2P系統(tǒng)中的節(jié)點(diǎn)動(dòng)態(tài)變化,并與集中式聚類算法有相似的聚類結(jié)果。
　　SOC算法利用結(jié)構(gòu)化CAN系統(tǒng)中數(shù)據(jù)嚴(yán)格按照規(guī)律分布的特點(diǎn),將系統(tǒng)坐標(biāo)空間與聚類數(shù)據(jù)空間重疊,使相鄰數(shù)據(jù)存儲(chǔ)在同一(或相鄰)節(jié)點(diǎn)上。用系統(tǒng)坐標(biāo)空間劃分的逆過(guò)程進(jìn)行凝聚型層次聚類,使CAN系統(tǒng)數(shù)據(jù)聚類達(dá)到與集中式聚類算法相同的結(jié)果。通過(guò)分析 SOC算法的聚類過(guò)程得到在數(shù)據(jù)維數(shù)一定的情況下算法的時(shí)間復(fù)雜度與系統(tǒng)中的節(jié)點(diǎn)數(shù)呈線性關(guān)系。