[發(fā)明專利]一種基于圖學習的快速譜嵌入聚類方法

在審

• 申請?zhí)枺?/td>: 202011041375.4
• 申請日: 2020-09-28
• 公開（公告）號: CN112132224A
• 公開（公告）日: 2020-12-25
• 發(fā)明（設計）人: 林郭權;楊曉君;郭春炳;陽琴;蔡湧達;許裕雄
• 申請（專利權）人: 廣東工業(yè)大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 尹君君

1.一種基于圖學習的快速譜嵌入聚類方法，其特征在于，所述方法包括如下步驟：

S10、輸入數據：

輸入待聚類的數據集X＝[x₁,…,x_n]^T∈R^n×d、設定類簇數c；利用K-means方法選取m個錨點U＝[u₁,…,u_m]^T∈R^m×d；

S20、構建組合二部圖矩陣，通過組合二部圖得到數據點的低維表示F和G：

計算數據點X和錨點U之間的二部圖矩陣：Z₁∈R^n×m；

計算數據點X和錨點U之間的分配矩陣：Z₂∈R^m×m；

得到組合的二部圖矩陣：

求出矩陣Z的相似矩陣A，對相似矩陣A進行譜分析，其目標函數為：

其中，Λ∈R^m×m為對角矩陣；其中，

F∈R^n×c和G∈R^m×c分別對應于數據點和錨點的低維表示；

此處對進行奇異值分解，得到H的松弛連續(xù)解，從而得到低維的譜嵌入數據；

S30、構建數據點和錨點的低維表示的目標函數：

其中，P為數據點和錨點的相似度矩陣，Q為最大的c個奇異值對應的左右奇異向量的相似度矩陣，f_i為對應F∈R^n×c的向量表示形式，g_j為對應G∈R^m×c的向量表示形式；λ為約束系數；

S40、判定步驟S30中目標函數是否收斂；若目標函數收斂，則轉至步驟S60；若目標函數不收斂，則轉至步驟S50；

S50、通過交替迭代優(yōu)化方式更新目標函數，并返回步驟S20；

S60、輸出圖結構信息完整的相似度矩陣P，結束。

2.根據權利要求1所述的基于圖學習的快速譜嵌入聚類方法，其特征在于，所述步驟S50中：通過交替迭代優(yōu)化方式更新目標函數，包含步驟如下：

S501、固定Q，求解相似度矩陣P得到：

令l_i∈R^m×1，則轉化為：

通過KKT條件，此時將γ代入公式得求得相似度矩陣P；

S502、根據步驟S401所求相似度矩陣P值求解Q，可使目標公式可以改寫為：

令則目標公式進一步優(yōu)化為：此時可通過求的奇異值和奇異向量獲得；U、V分別為矩陣的最大的c個奇異值對應的左右奇異向量；

S403、令Z₁＝Z₁+βP，其中β為設定的更新系數。

3.根據權利要求1所述的基于圖學習的快速譜嵌入聚類方法，其特征在于，所述步驟S20中，在構建組合二部圖矩陣前，需計算數據點和錨點之間的分配矩陣：

令d_i∈R^m×1是第j個元素為d_ij的向量，求得：

其中，k為近鄰點的個數，z_1ij為第i個數據點與第j個錨點之間的相似度的權重，參數γ被設置為

4.根據權利要求1所述的基于圖學習的快速譜嵌入聚類方法，其特征在于，所述步驟S30中的：構建原始數據點和錨點的目標函數，其具體構建步驟如下：

S301、為從數據點和錨點中得到相似度矩陣，有以下方程：

S302、對步驟301中的目標公式加上秩約束，并通過特征分解逼近得到：

此時，令和得到目標函數。

5.根據權利要求1-4任一項所述的基于圖學習的快速譜嵌入聚類方法，其特征在于，所述所述m、所述n、所述i、所述j、所述k的取值范圍均為正整數。