[發(fā)明專利]一種主動(dòng)地糾錯(cuò)式半監(jiān)督聚類社區(qū)發(fā)現(xiàn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810447419.X
• 申請(qǐng)日: 2018-05-11
• 公開(kāi)（公告）號(hào): CN110490755A
• 公開(kāi)（公告）日: 2019-11-22
• 發(fā)明（設(shè)計(jì)）人: 張賢坤;劉淵博;張高禎
• 申請(qǐng)（專利權(quán)）人: 天津科技大學(xué)
• 主分類號(hào): G06Q50/00
• 分類號(hào): G06Q50/00;G06K9/62
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明涉及一種主動(dòng)地糾錯(cuò)式半監(jiān)督聚類社區(qū)發(fā)現(xiàn)方法，其主要技術(shù)特點(diǎn)是：按照初始聚類中心選取原則選取K個(gè)節(jié)點(diǎn)作為初始聚類中心；按照距離公式對(duì)剩余的每個(gè)節(jié)點(diǎn)測(cè)量其到每個(gè)聚類中心的距離，并把它歸到最近中心的一類，并更新聚類中心；根據(jù)上一步中的歸類結(jié)果，找出當(dāng)前劃分結(jié)果中每個(gè)社區(qū)的中心節(jié)點(diǎn)和邊界節(jié)點(diǎn)，根據(jù)真實(shí)標(biāo)簽和三個(gè)主動(dòng)地糾錯(cuò)式規(guī)則修改網(wǎng)絡(luò)結(jié)構(gòu)，得到新的鄰接矩陣后更新聚類中心；用更新后的鄰接矩陣重新計(jì)算各個(gè)節(jié)點(diǎn)到聚類中心的距離，并把它歸到最近的聚類中心那一類，再次按照公式更新聚類中心。若迭代次數(shù)t＝＝maxIter或直至節(jié)點(diǎn)的歸類不再變化，算法結(jié)束。本發(fā)明設(shè)計(jì)合理，通過(guò)在聚類的過(guò)程中加入部分先驗(yàn)信息，根據(jù)已知信息保留正確的劃分，糾正錯(cuò)誤的劃分來(lái)改變網(wǎng)絡(luò)的連接關(guān)系，使網(wǎng)絡(luò)具有更明顯的塊結(jié)構(gòu)，提高社區(qū)劃分的準(zhǔn)確度，可廣泛用于社區(qū)發(fā)現(xiàn)、社交網(wǎng)絡(luò)等領(lǐng)域。

技術(shù)領(lǐng)域

本發(fā)明涉及智能信息處理，復(fù)雜網(wǎng)絡(luò)研究及社區(qū)發(fā)現(xiàn)的內(nèi)容。

背景技術(shù)

社區(qū)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)的主要特性之一，是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的研究重點(diǎn)。同一個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)之間聯(lián)系較為密切，而社區(qū)之間的節(jié)點(diǎn)聯(lián)系則較為松散。復(fù)雜網(wǎng)絡(luò)內(nèi)部連接緊密的節(jié)點(diǎn)組成的集合稱為社區(qū)。經(jīng)典的無(wú)監(jiān)督聚類算法快速、簡(jiǎn)單而且適合挖掘大規(guī)模數(shù)據(jù)集。可以直接對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)，但是這些無(wú)監(jiān)督算法存在著共同的缺陷，例如k-means每次隨機(jī)的尋找聚類中心，導(dǎo)致聚類結(jié)果不夠穩(wěn)定；部分社區(qū)的結(jié)構(gòu)性較弱容易造成錯(cuò)誤劃分。

無(wú)監(jiān)督聚類分析廣泛運(yùn)用于市場(chǎng)細(xì)分、集群計(jì)算、天體數(shù)據(jù)分析等領(lǐng)域。在數(shù)據(jù)挖掘中，無(wú)監(jiān)督學(xué)習(xí)也稱為聚類分析，復(fù)雜網(wǎng)絡(luò)聚類本質(zhì)上是圖的劃分問(wèn)題，因此采用傳統(tǒng)的聚類算法對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類，已經(jīng)普遍應(yīng)用于發(fā)現(xiàn)社區(qū)，例如，K-means、K-mediods、譜聚類和圖聚類等。

現(xiàn)有的大部分半監(jiān)督算法都是使用成對(duì)約束作為辨別信息，而且已經(jīng)取得了顯著的效果，例如，Liu等利用標(biāo)簽傳播方法，將已標(biāo)注的節(jié)點(diǎn)類標(biāo)號(hào)向周圍鄰居進(jìn)行傳播。Silva等人基于模塊度最大化的準(zhǔn)則將半監(jiān)督方法融入社區(qū)發(fā)現(xiàn)中。相比于節(jié)點(diǎn)的類標(biāo)號(hào)，數(shù)據(jù)的成對(duì)約束信息相對(duì)更容易獲得。Zhang等直接將節(jié)點(diǎn)的成對(duì)約束加到待分解的鄰接矩陣上。Yang等人利用半監(jiān)督的潛在空間圖正則化方法建立了一個(gè)統(tǒng)一的社區(qū)檢測(cè)框架。這些方法用隨機(jī)的方式將已知的先驗(yàn)信息加入網(wǎng)絡(luò)節(jié)點(diǎn)中，通常這種先驗(yàn)信息的加入方式對(duì)提高聚類準(zhǔn)確率并不明顯，需要較大比例的標(biāo)簽信息才能有效地提高聚類效果。在實(shí)際應(yīng)用中，人工標(biāo)注先驗(yàn)信息代價(jià)昂貴，因此，在聚類過(guò)程中，主動(dòng)標(biāo)記先驗(yàn)信息的方法被提出，能夠自適應(yīng)的選擇網(wǎng)絡(luò)中信息量比較大的節(jié)點(diǎn)或者節(jié)點(diǎn)對(duì)進(jìn)行標(biāo)注，從而能夠利用少量的先驗(yàn)信息，提高聚類的效果。

綜上所述，現(xiàn)有的半監(jiān)督聚類方法雖然簡(jiǎn)單快速，但是劃分結(jié)果不穩(wěn)定，隨機(jī)性較強(qiáng)且需要大量的監(jiān)督信息，在穩(wěn)定度和劃分精度上都存在很大的提升空間。

發(fā)明內(nèi)容

本發(fā)明的目的在于通過(guò)提供一種分步計(jì)算的主動(dòng)地糾錯(cuò)式半監(jiān)督聚類方法，在聚類的過(guò)程中加入部分先驗(yàn)信息，根據(jù)先驗(yàn)信息保留正確的劃分，糾正錯(cuò)誤的劃分來(lái)改變網(wǎng)絡(luò)的連接關(guān)系，使網(wǎng)絡(luò)具有更明顯的塊結(jié)構(gòu)，提高社區(qū)劃分的準(zhǔn)確度。

為實(shí)現(xiàn)上述目的本發(fā)明的技術(shù)方案是：主動(dòng)地糾錯(cuò)式半監(jiān)督聚類社區(qū)發(fā)現(xiàn)方法，包括以下步驟：

步驟A：按照初始聚類中心選取原則選取K個(gè)節(jié)點(diǎn)作為初始聚類中心{c_j}，j＝1，2，...，k；

步驟B：按照距離公式(1)對(duì)剩余的每個(gè)節(jié)點(diǎn)測(cè)量其到每個(gè)聚類中心的距離，并把它歸到最近中心的一類，并且按照公式(2)更新聚類中心；

步驟C：根據(jù)上一步中的歸類結(jié)果，找出當(dāng)前劃分結(jié)果中每個(gè)社區(qū)的中心節(jié)點(diǎn){V_hub}和邊界節(jié)點(diǎn){V_mar}，根據(jù)真實(shí)標(biāo)簽和下文中的三個(gè)主動(dòng)地糾錯(cuò)式規(guī)則修改網(wǎng)絡(luò)結(jié)構(gòu)，得到新的鄰接矩陣后更新聚類中心；