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

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

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

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

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