[發明專利]一種基于蝴碟模型的主題-文檔二分圖網絡聚類切割方法

在審

• 申請號: 202010436501.X
• 申請日: 2020-05-21
• 公開（公告）號: CN111611381A
• 公開（公告）日: 2020-09-01
• 發明（設計）人: 鄭軍;鄭藝;吳可心
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F16/35
• 分類號: G06F16/35;G06F16/31;G06F16/953
• 代理公司: 北京正陽理工知識產權代理事務所(普通合伙) 11639
• 代理人: 王民盛

1.一種基于蝴碟模型的主題-文檔二分圖網絡聚類切割方法，其特征在于：包括以下步驟：

步驟1：計算出圖G的主題鄰接矩陣W_M、主題度矩陣D_M和主題拉普拉斯矩陣L_M；

步驟1.1：計算出圖G的主題鄰接矩陣W_M；

其中，主題鄰接矩陣W_M為n行n列的方陣，且W_M中第i行第j列元素，記為(W_M)_ij，該元素(W_M)_ij等于節點i和節點j同時參與的主題實例數，i和j的取值范圍均為1到n；

步驟1.2：計算出圖G的主題度矩陣D_M；

其中，主題度矩陣D_M為對角線矩陣，且D_M對角線上的元素(D_M)_ii通過計算，對角線外的其余元素皆為0；

步驟1.3：計算出圖G的主題拉普拉斯矩陣L_M；

其中，主題拉普拉斯矩陣L_M通過L_M＝D_M-W_M計算；

步驟2：根據主題鄰接矩陣W_M構造出無向加權圖G_M；

步驟3：計算主題拉普拉斯矩陣L_M第二小特征值對應的特征向量及該特征向量的索引值，具體為：

步驟3.1：計算主題拉普拉斯矩陣L_M第二小特征值對應的特征向量z；

步驟3.2：輸出的特征向量z中n個值從大到小排序對應的索引值；

其中，索引值σ_k代表z的第i個最大值的索引，即特征向量z中數值從大到小排序中的第k個值對應的位置；

其中，k取值范圍為1到r；

步驟3.3：建立r個索引值集合S₁到S_r；

其中，S₁＝{σ₁}，S₂＝{σ₁,σ₂}，…S_k＝{σ₁,σ₂,...,σ_k}，…，S_r＝{σ₁,...,σ_r}；

S_k＝{σ₁,σ₂,...,σ_k}，代表包含σ₁、σ₂,...,σ_k元素的集合；

步驟4：分別計算S_r＝{σ₁,...,σ_r}的電導率，電導率中的最小值所對應的類即為所求的目標聚類，具體包括如下子步驟：

步驟4.1通過公式(1)計算S_k的電導率：

其中，k的取值范圍為1到r；φ^(G)(S_k)代表S_k的電導率，且S_k＝{σ₁,σ₂,...,σ_k}；表示S_k補集，表示被切割的邊的權重和，vol^(G)(S_k)表示S_k中點的邊權重和，表示中點的邊權重和；

步驟4.2求步驟4.1計算的r個電導率中的最小值；

其中，r個電導率中的最小值，記為

步驟4.3找出步驟4.2計算電導率最小值對應的類，即為所求目標聚類。

2.根據權利要求1所述的一種基于蝴碟模型的主題-文檔二分圖網絡聚類切割方法，其特征在于：步驟1中圖G為主題-文檔二分圖。

3.根據權利要求1所述的一種基于蝴碟模型的主題-文檔二分圖網絡聚類切割方法，其特征在于：步驟2中，無向加權圖G_M為n個節點及節點間基于權重的邊連接關系。