基于半監(jiān)督的GN聚類算法研究.pdf

1、隨著“互聯(lián)網(wǎng)+”時(shí)代的到來(lái)，網(wǎng)絡(luò)中的數(shù)據(jù)呈爆炸性增長(zhǎng)，導(dǎo)致處理、分析網(wǎng)絡(luò)中的數(shù)據(jù)成為一個(gè)棘手的問(wèn)題。將網(wǎng)絡(luò)中的數(shù)據(jù)按照某種屬性快速劃分成若干社區(qū)是處理、分析數(shù)據(jù)一種有效快速的方式，該方式即社區(qū)發(fā)現(xiàn)方法?，F(xiàn)有的社區(qū)發(fā)現(xiàn)方法存在需要事先指定社區(qū)的數(shù)目、事先確定劃分后每個(gè)社區(qū)大小或者其他關(guān)于社區(qū)范圍的信息以及預(yù)先指定評(píng)價(jià)指標(biāo)等缺陷，同時(shí)大多數(shù)社區(qū)發(fā)現(xiàn)算法屬于無(wú)監(jiān)督范疇，不能有效利用已知的先驗(yàn)知識(shí)。經(jīng)典的GN(Givern-Newman)算法是

2、一種基于啟發(fā)式的分裂層次聚類算法，準(zhǔn)確性高，適用于中小型網(wǎng)絡(luò)。但GN算法不能利用已知的先驗(yàn)知識(shí)，且時(shí)間復(fù)雜度相對(duì)較高。本文針對(duì)以上問(wèn)題對(duì)GN算法進(jìn)行改進(jìn)，主要?jiǎng)?chuàng)新點(diǎn)有:
　　(1)基于半監(jiān)督的GN算法
　　為解決經(jīng)典GN算法無(wú)法利用已知的先驗(yàn)信息學(xué)習(xí)的問(wèn)題，采用基于約束的半監(jiān)督提出了基于半監(jiān)督的GN算法，記為S-GN(Givern-Newman based on semi-supervised)。S-GN算法采用基于約束的半

3、監(jiān)督學(xué)習(xí)方法，對(duì)已知的Must-link約束、Cannot-link約束信息進(jìn)行學(xué)習(xí)，將學(xué)習(xí)到的知識(shí)通過(guò)基于距離的度量方法進(jìn)行驗(yàn)證，從而提高先驗(yàn)信息的數(shù)量和質(zhì)量。將已知的約束對(duì)和學(xué)習(xí)到的約束對(duì)融入網(wǎng)絡(luò)，從網(wǎng)絡(luò)中剔除Cannot-link約束信息。再通過(guò)迭代計(jì)算剩余邊的邊介值(betweenness)并刪去邊介值最大(full-betweenness)的邊，至劃分成最佳社區(qū)狀態(tài)。在人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中對(duì)S-GN算法分析，S-GN算法的時(shí)間

4、復(fù)雜度有待改善，但在準(zhǔn)確性和運(yùn)行效率方面均有所提升。
　　(2)基于相似度的半監(jiān)督GN算法
　　為解決S-GN算法時(shí)間復(fù)雜度高的問(wèn)題，提出了基于相似度的半監(jiān)督GN算法，記為S-SGN(Givern-Newman based on similarity and semi-supervised)。S-SGN算法利用已知的和學(xué)習(xí)到的先驗(yàn)信息中節(jié)點(diǎn)對(duì)的關(guān)系，根據(jù)不同的相似度構(gòu)造方法修改網(wǎng)絡(luò)初始矩陣中對(duì)應(yīng)的值。通過(guò)迭代計(jì)算節(jié)點(diǎn)相似度值