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

在審

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

1.一種基于屬性融合的圖聚類方法，其特征在于，包括以下步驟：

(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)、定義三個不同層次：屬性層，結構層和底層網絡；

定義屬性層G_a(l)，G_a(l)＝(V_a(l),E_a(l),W_a(l))，l＝1,2,…,m和結構層G_b，G_b＝(V_b,E_b,W_b)；其中，V_a(l)表示屬性圖中存在屬性a(l)的節點集合，E_a(l)表示兩個節點之間因共同的屬性a(l)而存在的邊的集合，W_a(l)是屬性a(l)之間的相似性權重值；V_b是屬性圖中節點集合，E_b是連接節點之間存在關系邊的集合，W_b是節點之間存在原有結構關系的邊的權重值；底層網絡G_u＝(V_u,E_u,W_u)，其中E_u是屬性圖中所有節點的集合，E_u是屬性圖中邊的集合，W_u是由多層屬性融合以后的節點之間邊的權重值；

(3)、根據多層屬性融合規則規則，將屬性層和結構層加權融合到底層網絡G_u中；

(3.1)、若頂點集合V中，任意兩個節點之間只存在屬性關系，則將頂點集合V中所有節點的不同屬性層權重系數設置為α_a(1),α_a(2),…,α_a(m)，再將各個屬性層經過加權后合并到底層網絡中，合并后的底層網絡中權重值W_u修改為：

W_u＝α_a(1)W_a(1)+α_a(2)W_a(2)+…+α_a(m)W_a(m)；

(3.2)、若頂點集合V中，任意兩個節點之間只存在結構層，即兩個節點之間只具有原有的拓撲結構關系，則對兩個節點之間的結構關系經過加權后合并到底層網絡中，合并后的底層網絡中兩個節點之間的權重W_u值修改為：

W_u＝β_bW_b

其中，β為結構層的權重系數；

(3.3)、判斷節點集合V中任意兩個節點是否同時存在于屬性層和結構層，如果兩個節點之間既存在屬性層又存在結構層，則將結構層和屬性層一起合并到底層網絡中，合并后的底層網絡中兩個節點之間的權重W_u值修改為：

Wu=Σl=1mαa(l)Wa(l)+βbWb;]]>

(4)、構建底層網絡的相似度矩陣；

(4.1)、計算底層網絡中任意兩節點之間的余弦相似度；

設任意兩節點為X,Y，利用兩節點的屬性特征計算這兩節點之間的余弦相似度為：

cos(X,Y)=X′Y[(X′X)(Y′Y)]1/2]]>

其中，X′、Y′分別表示X、Y的一階導數；

(4.2)、根據底層網絡中任意兩節點之間的余弦相似度構建相似度矩陣；

(5)、利用AP算法對相似度矩陣進行聚類操作，得到k個簇為C₁,C₂,…,C_k；

(6)通過節點投票機制來自適應更新屬性層權重系數

(6.1)、對k個簇進行節點投票；

在每個簇內，判斷簇內節點與聚類中心之間是否存在共同的屬性a(l)，如果存在共同屬性，則記該屬性對節點的投票為1，反之，則為0，用公式表示為：

votel(Cj‾,vi‾)=1a(l)∈vi‾∩Cj‾0a(l)∉vi‾∩Cj‾]]>

其中，為聚類后的第個簇，表示第個簇中第個節點；

(6.2)、定義為第t次迭代后的屬性a(l)權重系數，則屬性a(l)的t+1次權重系數更新為：

αa(l)t+1=12(αa(l)t+Δαa(l)t)]]>

其中，表示第t次迭代中屬性a(l)的增值；

Δαa(l)t=Σj‾=1kΣvi‾∈Cj‾votel(vi‾)(Cj‾,vi‾)Σl=1mΣj‾=1kΣvi‾∈Cj‾votel(Cj‾,vi‾)]]>

(7)、待屬性a(l)的t+1次權重系數更新后，返回步驟(3.1)，重新更新屬性層的權重系數，再利用AP算法進行聚類操作，直到達到預設的迭代次數或α_a(l)保持不變時，迭代停止。

2.根據權利要求1所述的基于屬性融合的圖聚類方法，其特征在于，所述的余弦相似度cos(X,Y)是一個介于[0,1]之間的數，最大的相似度為1，最大的相異度為0。