基于參考點(diǎn)的演化聚類(lèi)算法研究.pdf

1、隨著互聯(lián)網(wǎng)的蓬勃發(fā)展和人們采集數(shù)據(jù)能力的增強(qiáng)，實(shí)際生活中出現(xiàn)了越來(lái)越多的隨時(shí)間變化的數(shù)據(jù)，我們稱(chēng)這類(lèi)數(shù)據(jù)為演化數(shù)據(jù)(Evolutionary Data)。近年來(lái)，演化數(shù)據(jù)的聚類(lèi)問(wèn)題引起了很多研究者的興趣。一般地，演化聚類(lèi)的要求有兩個(gè)方面:1）每個(gè)時(shí)刻發(fā)現(xiàn)的聚類(lèi)結(jié)構(gòu)要盡可能好地劃分當(dāng)前時(shí)刻的快照數(shù)據(jù);2）每個(gè)時(shí)刻發(fā)現(xiàn)的聚類(lèi)結(jié)構(gòu)要盡可能保持時(shí)間平滑性，即和上個(gè)時(shí)刻相比，當(dāng)前時(shí)刻發(fā)現(xiàn)的聚類(lèi)結(jié)構(gòu)盡量不發(fā)生太大的變化。演化數(shù)據(jù)聚類(lèi)有很廣泛的應(yīng)用背

2、景，其研究有著很重要的意義。
　　本文從核心節(jié)點(diǎn)和參考點(diǎn)的角度來(lái)研究演化聚類(lèi)。本文的主要內(nèi)容包括三個(gè)方面。
　　1)受靜態(tài)社區(qū)發(fā)現(xiàn)算法Top Leaders啟發(fā)，我們提出一個(gè)基于核心節(jié)點(diǎn)(LeaderNodes)的演化社區(qū)發(fā)現(xiàn)算法(EvoLeaders)。首先，我們基于結(jié)合時(shí)間信息的更新策略來(lái)得到每個(gè)時(shí)刻的初始核心節(jié)點(diǎn)。通過(guò)保持發(fā)現(xiàn)的初始核心節(jié)點(diǎn)集合與上個(gè)時(shí)刻核心節(jié)點(diǎn)集合的時(shí)間平滑性，來(lái)保證由這些核心節(jié)點(diǎn)發(fā)現(xiàn)的社區(qū)跟以前的結(jié)

3、構(gòu)盡量保持平滑。然后，通過(guò)一組分裂合并操作提高社區(qū)質(zhì)量。在兩個(gè)實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，EvoLeaders算法比Top Leaders算法效果更好。該工作表明了從核心節(jié)點(diǎn)的角度進(jìn)行演化社區(qū)發(fā)現(xiàn)的可行性。
　　2) Top Leaders算法的主要缺點(diǎn)是需要人工輸入社區(qū)數(shù)目。基于網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)之間度的關(guān)系，以及節(jié)點(diǎn)之間共同鄰居的重疊程度，我們改進(jìn)了Top Leaders算法，并提出了能夠自動(dòng)發(fā)現(xiàn)社區(qū)數(shù)目的AutoLe

4、aders算法。在三個(gè)經(jīng)典數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，AutoLeaders算法不僅能夠發(fā)現(xiàn)合理的社區(qū)數(shù)目，還能夠發(fā)現(xiàn)合理的社區(qū)結(jié)構(gòu)。進(jìn)一步，基于兩種時(shí)間平滑性策略，我們提出了在動(dòng)態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)的新的解決方案，即EvoAutoLeaders算法。在兩個(gè)實(shí)際數(shù)據(jù)集上的結(jié)果表明EvoAutoLeaders算法的效果比較好。
　　3)我們從參考點(diǎn)的角度來(lái)處理演化聚類(lèi)問(wèn)題。首先，我們引入了三種不同的參考點(diǎn)，以及相應(yīng)的計(jì)算個(gè)體到參考點(diǎn)距離的策