[發(fā)明專利]一種基于博弈論的增量式異構(gòu)圖聚類方法

有效

• 申請?zhí)枺?/td>: 201810271526.1
• 申請日: 2018-03-29
• 公開（公告）號: CN108399268B
• 公開（公告）日: 2022-04-29
• 發(fā)明（設(shè)計）人: 高云君;陳璐;浦世亮;張遠亮
• 申請（專利權(quán)）人: 浙江大學(xué);杭州海康威視數(shù)字技術(shù)股份有限公司
• 主分類號: G06F16/35
• 分類號: G06F16/35
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 邱啟旺

本發(fā)明公開了一種基于博弈論的增量式異構(gòu)圖聚類方法。本發(fā)明利用Personalized Pagerank作為統(tǒng)一的距離度量方式；利用增量式計算提高Personalized Pagerank得分的計算效率；基于DBSCAN算法并且利用博弈論的方法對聚類結(jié)果進行調(diào)整；利用熵以及邊權(quán)重更新的方式來平衡結(jié)構(gòu)信息和屬性信息之間的重要性。本方法使用Personalized Pagerank來度量圖結(jié)構(gòu)中任意兩個結(jié)點之間的相似性，利用增量式計算方式計算結(jié)點之間的Personalized Pagerank得分；采用DBSCAN算法得到初步的聚類結(jié)果并根據(jù)博弈論來對聚類結(jié)果進行調(diào)整；根據(jù)聚類結(jié)果計算熵，更新不同類型的邊的權(quán)重。本發(fā)明同時考慮異構(gòu)圖結(jié)點的結(jié)構(gòu)相似性和屬性相似性，提高了Personalized Pagerank得分的計算效率并對聚類結(jié)果進行優(yōu)化，提出了一種效率高，聚類質(zhì)量好的異構(gòu)圖聚類方法。

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

本發(fā)明涉及異構(gòu)圖上的聚類技術(shù)，特別涉及一種基于博弈論的增量式異構(gòu)圖聚類方法。

背景技術(shù)

隨著社交媒體和移動互聯(lián)網(wǎng)的發(fā)展，現(xiàn)實生活中存在著大量的具有不同類型并且相互關(guān)聯(lián)的對象的集合，可以通過一個異構(gòu)圖模型來表示，例如DBLP和Flickr。通過對異構(gòu)圖中的對象結(jié)點進行聚類，可以將彼此相似并且聯(lián)系緊密的對象劃分到一起，可廣泛應(yīng)用于社區(qū)檢測和推薦系統(tǒng)等領(lǐng)域。異構(gòu)圖上的聚類算法一直以來都是數(shù)據(jù)庫、數(shù)據(jù)挖掘和機器學(xué)習(xí)領(lǐng)域的研究熱點。

目前主流的異構(gòu)圖聚類算法往往只考慮了異構(gòu)圖中的屬性特征或者結(jié)構(gòu)特征，因此丟失了大量的有用的信息；某些方法雖然同時考慮了異構(gòu)圖的屬性信息和結(jié)構(gòu)信息，但其方法需要進行大量的矩陣運算，并且計算過程需要將數(shù)據(jù)全部放在內(nèi)存中處理，因此存在巨大的時間開銷和存儲開銷，也制約了方法的擴展性。此外，傳統(tǒng)的聚類算法常存在對部分對象聚類效果欠佳的情況，有必要對聚類后的結(jié)果再進行優(yōu)化，以提高整體的聚類質(zhì)量。所以，設(shè)計一種高效，拓展性強，能同時考慮異構(gòu)圖結(jié)構(gòu)和屬性信息，并且能夠?qū)垲惤Y(jié)果進行更深層次優(yōu)化的異構(gòu)圖聚類算法為了學(xué)術(shù)界與工業(yè)界的迫切需求。

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

針對上述不足，本發(fā)明提供一種基于博弈論的增量式異構(gòu)圖聚類方法。該方法在構(gòu)建完DBLP的異構(gòu)圖模型后，采用Personalized Pagerank增量計算的方式計算任意兩個論文結(jié)點之間的Personalized Pagerank得分，基于傳統(tǒng)的DBSCAN算法進行聚類，并且利用博弈論方法對聚類結(jié)果進行調(diào)整，然后迭代進行邊權(quán)重更新直至收斂，完成聚類，得到所有的論文結(jié)點的聚類結(jié)果。

為了達到上述目的，本發(fā)明所采用技術(shù)方案如下：一種基于博弈論的增量式異構(gòu)圖聚類方法，該方法包括如下步驟：

步驟(1)：對DBLP數(shù)據(jù)集進行預(yù)處理，構(gòu)建異構(gòu)圖模型；

步驟(2)：對異構(gòu)圖模型中的每一個論文結(jié)點，基于Personalized Pagerank算法進行回退時，只處理主類結(jié)點，即論文結(jié)點，然后將所有結(jié)點的殘留值和儲存值保存在外存中，用于步驟(3)的更新使用；

步驟(3)：根據(jù)當(dāng)前邊的權(quán)重，對異構(gòu)圖模型中的每一個論文結(jié)點，重新計算轉(zhuǎn)移概率矩陣，讀取步驟(2)保存的殘留值和儲存值，對所有結(jié)點進行回退操作，計算出每個論文結(jié)點到圖結(jié)構(gòu)中其他論文結(jié)點的Personalized Pagerank得分；

步驟(4)：對任意兩個論文結(jié)點之間的兩個Personalized Pagerank得分，取兩者之間的較小值作為兩個結(jié)點的相似性度量；

步驟(5)：基于DBSCAN算法對所有論文結(jié)點進行聚類；

步驟(6)：基于博弈論對步驟(5)的聚類結(jié)果進行調(diào)整，得到新的聚類結(jié)果；

步驟(7)：基于步驟(6)獲得的新的聚類結(jié)果的信息熵對論文與其他屬性結(jié)點之間的邊權(quán)重進行更新，如果當(dāng)前邊權(quán)重和上一輪邊權(quán)重的均方誤差小于設(shè)定的誤差限，則得到最終聚類結(jié)果，否則返回步驟(3)重復(fù)迭代計算。