本文關(guān)鍵詞：基于鄰域信息的聚類和社區(qū)發(fā)現(xiàn)算法研究

  更多相關(guān)文章： 聚類 社區(qū)發(fā)現(xiàn) 鄰域信息 模糊關(guān)系

【摘要】：隨著數(shù)據(jù)挖掘技術(shù)在各行各業(yè)的廣泛應(yīng)用,人們對(duì)這一領(lǐng)域的相關(guān)技術(shù)越來越關(guān)注。數(shù)據(jù)聚類和社區(qū)發(fā)現(xiàn)是數(shù)據(jù)挖掘領(lǐng)域中十分重要的兩個(gè)課題,它們之間也有一些共性。聚類是指將數(shù)據(jù)對(duì)象分為若干個(gè)簇,使得簇內(nèi)的對(duì)象關(guān)系緊密,而簇之間的對(duì)象關(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)算法的研究工作。本文針對(duì)已有的經(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)提出了基于鄰域交集和密度差異的聚類算法NIDD。在分析聚類算法FDP的過程中,發(fā)現(xiàn)它在某些數(shù)據(jù)集上的效果并不理想。針對(duì)FDP的一些不足,提出了聚類算法NIDD。該算法的思想是:第一,在簇的擴(kuò)展過程中會(huì)選擇一個(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)的密度變化相對(duì)較大,那么該待擴(kuò)展點(diǎn)被歸為當(dāng)前簇,但是該數(shù)據(jù)點(diǎn)不可以繼續(xù)擴(kuò)展。第二,如果參考點(diǎn)和待擴(kuò)展點(diǎn)之間的k最近鄰交集率很小,說明它們之間的公共鄰居占據(jù)的比例很小,此時(shí)不管它們密度是否相似,它們會(huì)被劃分在不同的簇中。實(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ū)從這個(gè)節(jié)點(diǎn)開始向外擴(kuò)展;第三,在社區(qū)擴(kuò)展的過程中,模糊隸屬度被用來決定是否繼續(xù)擴(kuò)展當(dāng)前社區(qū)。對(duì)比了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(Nearest Greater Centrality)節(jié)點(diǎn)的概念。然后,引入了基于鄰域信息的模糊關(guān)系的概念,并且給出了計(jì)算每個(gè)節(jié)點(diǎn)到其NGC節(jié)點(diǎn)的模糊關(guān)系的方法。這種模糊關(guān)系可以看做是節(jié)點(diǎn)對(duì)其NGC節(jié)點(diǎn)的依賴程度。依賴程度越小說明該節(jié)點(diǎn)的自治性越大,換句話說,該節(jié)點(diǎn)成為社區(qū)中心節(jié)點(diǎn)的可能性越大。最后,每個(gè)節(jié)點(diǎn)屬于哪個(gè)社區(qū)取決于其NGC節(jié)點(diǎn)以及它們之間的模糊關(guān)系。實(shí)驗(yàn)結(jié)果表明,CDFR算法對(duì)于非重疊社區(qū)檢測(cè)是有效的。本文工作不僅在聚類方法研究方面具有參考價(jià)值,而且對(duì)于社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)研究也具有參考價(jià)值。
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.13

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前2條

1 WANG Shuliang;WANG Dakui;LI Caoyuan;LI Yan;DING Gangyi;;Clustering by Fast Search and Find of Density Peaks with Data Field[J];Chinese Journal of Electronics;2016年03期

2 武志昊;林友芳;Steve Gregory;萬懷宇School of Computer and Information Technology,Beijing Jiaotong University;田盛豐;;Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J];Journal of Computer Science & Technology;2012年03期

，

本文編號(hào)：1275911