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

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

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

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

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

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