基于鄰域信息的聚類算法和社區(qū)發(fā)現(xiàn)算法研究.pdf

1、隨著數(shù)據(jù)挖掘技術(shù)在各行各業(yè)的廣泛應(yīng)用，人們對這一領(lǐng)域的相關(guān)技術(shù)越來越關(guān)注。數(shù)據(jù)聚類和社區(qū)發(fā)現(xiàn)是數(shù)據(jù)挖掘領(lǐng)域中十分重要的兩個(gè)課題，它們之間也有一些共性。聚類是指將數(shù)據(jù)對象分為若干個(gè)簇，使得簇內(nèi)的對象關(guān)系緊密，而簇之間的對象關(guān)系疏遠(yuǎn)。社區(qū)發(fā)現(xiàn)可以認(rèn)為是聚類思想在網(wǎng)絡(luò)數(shù)據(jù)中的延伸，它是指將網(wǎng)絡(luò)中的節(jié)點(diǎn)指派給若干個(gè)社區(qū)，使得同一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)聯(lián)系緊密，而來自不同社區(qū)的節(jié)點(diǎn)間聯(lián)系比較疏遠(yuǎn)。目前已有大量的關(guān)于聚類算法和社區(qū)發(fā)現(xiàn)算法的研究工作。本文針

2、對已有的經(jīng)典聚類算法FDP中存在的不足，探索了鄰域信息在聚類中的作用，然后提出了一種新的聚類算法NIDD。接著，將NIDD的思想推廣到社交網(wǎng)絡(luò)中，在引入基于鄰域信息的模糊中心度和模糊隸屬度的基礎(chǔ)上，提出了一個(gè)新的社區(qū)發(fā)現(xiàn)算法FCFM。最后，將聚類算法FDP的核心思想推廣到社區(qū)發(fā)現(xiàn)中，研究了基于鄰域信息的模糊關(guān)系及其作用，提出了基于模糊關(guān)系的社區(qū)發(fā)現(xiàn)算法CDFR。
　　具體來說，本文工作主要包括以下3個(gè)方面。
　　(1)提出了

3、基于鄰域交集和密度差異的聚類算法NIDD。在分析聚類算法FDP的過程中，發(fā)現(xiàn)它在某些數(shù)據(jù)集上的效果并不理想。針對FDP的一些不足，提出了聚類算法NIDD。該算法的思想是:第一，在簇的擴(kuò)展過程中會選擇一個(gè)內(nèi)部點(diǎn)作為參考點(diǎn)，然后考察參考點(diǎn)鄰域內(nèi)的所有點(diǎn);如果參考點(diǎn)和待擴(kuò)展點(diǎn)的密度變化較小，那么它們屬于同一個(gè)簇，并且該待擴(kuò)展點(diǎn)還可以繼續(xù)擴(kuò)展;反之，如果參考點(diǎn)和待擴(kuò)展點(diǎn)的密度變化相對較大，那么該待擴(kuò)展點(diǎn)被歸為當(dāng)前簇，但是該數(shù)據(jù)點(diǎn)不可以繼續(xù)擴(kuò)展。

4、第二，如果參考點(diǎn)和待擴(kuò)展點(diǎn)之間的k最近鄰交集率很小，說明它們之間的公共鄰居占據(jù)的比例很小，此時(shí)不管它們密度是否相似，它們會被劃分在不同的簇中。實(shí)驗(yàn)結(jié)果表明了NIDD算法的有效性。
　　(2)提出了基于模糊中心度和模糊隸屬度的非重疊社區(qū)發(fā)現(xiàn)算法FCFM。FCFM是一種無參數(shù)的社區(qū)發(fā)現(xiàn)算法，其主要思想是:第一，基于鄰域信息的模糊中心度來組織網(wǎng)絡(luò)中節(jié)點(diǎn)的處理順序;第二，在一個(gè)社區(qū)中擁有最大的模糊中心度的節(jié)點(diǎn)被認(rèn)為是這個(gè)社區(qū)的中心，社區(qū)從

5、這個(gè)節(jié)點(diǎn)開始向外擴(kuò)展;第三，在社區(qū)擴(kuò)展的過程中，模糊隸屬度被用來決定是否繼續(xù)擴(kuò)展當(dāng)前社區(qū)。對比了FCFM和經(jīng)典的社區(qū)發(fā)現(xiàn)算法在真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果驗(yàn)證了FCFM算法的有效性。
　　(3)提出了基于模糊關(guān)系的社區(qū)發(fā)現(xiàn)算法CDFR。首先，提出NGC(NearestGreaterCentrality)節(jié)點(diǎn)的概念。然后，引入了基于鄰域信息的模糊關(guān)系的概念，并且給出了計(jì)算每個(gè)節(jié)點(diǎn)到其NGC節(jié)點(diǎn)的模糊關(guān)系的方法。這種模糊關(guān)系