[發明專利]一種基于屬性融合的圖聚類方法

在審

• 申請號: 201710507324.8
• 申請日: 2017-06-28
• 公開（公告）號: CN107273934A
• 公開（公告）日: 2017-10-20
• 發明（設計）人: 徐杰;陳文龍;盧思變;唐淳
• 申請（專利權）人: 電子科技大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F17/30
• 代理公司: 成都行之專利代理事務所(普通合伙)51220
• 代理人: 溫利平

技術領域

本發明屬于數據挖掘技術領域，更為具體地講，涉及一種基于屬性融合的圖聚類方法。

背景技術

隨著當前隨著互聯網的快速發展，相關領域產生了大量的復雜圖結構數據，如何充分利用這些數據，挖掘有用的知識和信息成為當前研究的熱點。圖聚類技術是挖掘圖結構數據的一種有效的方法，在生物領域，化學領域和社交網絡領域等有著重要的實際應用價值。

然而傳統的圖聚類技術如基于劃分的聚類方法，基于密度的聚類，基于層次的聚類，基于模型的聚類等往往只考慮圖的拓撲關系和節點屬性相似性，將圖劃分成結構緊密的子圖或者是節點相似度較高的子圖，對如何平衡節點屬性相似度和結構關系對聚類結果的影響考慮的較少。

例如，Yang Zhou等人提出的SA-Cluster算法及其擴展算法SA-Cluster-Opt和Inc-Cluster都是基于劃分的聚類算法。結合了數據對象的屬性相似性和結構相似性，采用基于距離的度量，在原始圖中增加屬性節點形成增廣圖，用基于隨機游走的距離度量屬性邊和結構邊之間的相似性。然后采用K-medoids算法，對增加屬性節點的增廣圖進行聚類。基于模型聚類的方法是通過設計一個融合圖結構和節點屬性特征的模型來尋找圖數據與給定模型之間的最佳擬合。Akoglu等人通過對節點屬性相似度和結構關系進行壓縮編碼，把圖聚類問題轉化為矩陣壓縮編碼問題，通過在聚類迭代過程中屬性和邊最大熵的節點進行劃分。Xu等人提出了基于貝葉斯概率模型的BAGC算法，將節點屬性特征和結構關系分別使其服從多項式分布和伯努利分布，最后將概率較大的節點劃分到相應的簇內。Jaewon等人提出了CESNA算法，將節點屬性特征和結構關系都設計成服從伯努利分布模型進行聚類。與BACG算法不同的是，CESNA算法的聚類結果簇之間有重疊的。此外，M.Ester提出的NetScan算法，NetScan算法將具有節點特征屬性的圖模型劃分不同屬性子圖。該算法需要預先指定聚類數目，但是在沒有先驗條件下指定的聚類數目與真實聚類結果可能會出現較大偏差，使得聚類效果較差。針對NetScan算法存在的問題，Moser等人提出了無需提前指定聚類數目的JointClust算法，雖然不需要指定聚類數目，但仍需初始化選擇聚類中心，使得聚類結果和初始類中心的選擇有著很大的關系。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于屬性圖融合的圖聚類方法，通過綜合考慮數據的結構關系和屬性特征來對數據進行聚類，挖掘數據中更多潛在的知識和信息。

為實現上述發明目的，本發明一種基于屬性融合的圖聚類方法，其特征在于，包括以下步驟：

(1)、利用將具有結構和屬性關系的數據構建一個屬性圖G＝(V,E,A,F)模型，其中，V表示屬性圖中頂點集合，V＝{v₁,v₂,…,v_n}；E表示屬性圖中邊的集合，E＝{(v_i,v_j)(v_i,v_j)∈E(G),1≤i,j≤n}，(v_i,v_j)表示由節點v_i,v_j構成的邊，n表示邊節點總數；A表示屬性集合，A＝{a₁,a₂,…,a_m}，a_m表示第m個屬性特征；F表示屬性圖中頂點所具有的屬性特征與其屬性值之間的映射關系，F＝{f_l|f_l:V→dom(a_l),1≤l≤m}；f_l表示屬性特征與其屬性值間的映射關系，dom(a_l)表示屬性a_l的屬性值；

(2)、定義屬性圖多層融合模型和融合規則；

(2.1)、定義三個不同層次：屬性層，結構層和底層網絡；