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

在審

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

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

S10、輸入數(shù)據(jù)：

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

S20、構(gòu)建組合二部圖矩陣，通過組合二部圖得到數(shù)據(jù)點的低維表示F和G：

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

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

得到組合的二部圖矩陣：

求出矩陣Z的相似矩陣A，對相似矩陣A進行譜分析，其目標(biāo)函數(shù)為：

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

F∈R^n×c和G∈R^m×c分別對應(yīng)于數(shù)據(jù)點和錨點的低維表示；

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

S30、構(gòu)建數(shù)據(jù)點和錨點的低維表示的目標(biāo)函數(shù)：

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

S40、判定步驟S30中目標(biāo)函數(shù)是否收斂；若目標(biāo)函數(shù)收斂，則轉(zhuǎn)至步驟S60；若目標(biāo)函數(shù)不收斂，則轉(zhuǎn)至步驟S50；

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

S60、輸出圖結(jié)構(gòu)信息完整的相似度矩陣P，結(jié)束。

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

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

令l_i∈R^m×1，則轉(zhuǎn)化為：

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

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

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

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

3.根據(jù)權(quán)利要求1所述的基于圖學(xué)習(xí)的快速譜嵌入聚類方法，其特征在于，所述步驟S20中，在構(gòu)建組合二部圖矩陣前，需計算數(shù)據(jù)點和錨點之間的分配矩陣：

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

其中，k為近鄰點的個數(shù)，z_1ij為第i個數(shù)據(jù)點與第j個錨點之間的相似度的權(quán)重，參數(shù)γ被設(shè)置為

4.根據(jù)權(quán)利要求1所述的基于圖學(xué)習(xí)的快速譜嵌入聚類方法，其特征在于，所述步驟S30中的：構(gòu)建原始數(shù)據(jù)點和錨點的目標(biāo)函數(shù)，其具體構(gòu)建步驟如下：

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

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

此時，令和得到目標(biāo)函數(shù)。

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