[發明專利]基于增量成員選擇和改進共協矩陣的聚類融合方法

在審

• 申請號: 201610877582.0
• 申請日: 2016-10-08
• 公開（公告）號: CN106650772A
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 馬廷淮;吳秀格;薛羽;曹杰
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 江蘇愛信律師事務所32241
• 代理人: 唐小紅

1.基于增量成員選擇和改進共協矩陣的聚類融合方法，其特征在于，包括以下步驟：

步驟1)，用K-means算法對數據集X進行M次有差異的聚類，最終得到M個有差異的劃分P₁,P₂,…P_M，組成聚類融合成員集合Old＝{P₁,P₂,…P_M}；

步驟2)，根據誤差平方和SSE，升序排列步驟1)得到的聚類融合成員集合Old＝{P₁,P₂,…P_M}，選擇SSE最小的聚類融合成員加入新的聚類融合成員集合New；根據局部成本函數升序排列聚類融合成員集合Old＝{P₁,P₂,…P_M}中剩余的M-1個聚類融合成員，判斷若聚類融合成員P_m加入New后，分別計算用New和New'＝New+P_m得到的最終聚類結果的誤差平方和SSE(New)和SSE(New')，若SSE(New)＞SSE(New')，則New＝New'，Old＝Old-P_m，否則New和Old不變，繼續判斷下一個聚類融合成員P_m+1，如此迭代的增量選擇直至New中有W個聚類融合成員；

步驟3)，考慮步驟2)得到的W個聚類融合成員之間的關系，考慮數據點x_i和x_j同時落在簇C_wh，聚類融合成員P_w的第h個簇的概率P(x_i,x_j|C_wh)和簇C_wh的穩定性S'(C_wh)，根據公式構造共協矩陣CM；

步驟4)，根據步驟3)得到的共協矩陣CM建立加權圖G＝(V,E)和對角矩陣D，求出特征系統(D-CM)y＝λDy的特征值和與其相對應的特征向量，使用具有第二個最小特征值的特征向量將加權圖G劃分為兩部分，根據Ncut值是否穩定判斷是否需要繼續分割，若是，遞歸此步驟分割上一次分割好的圖。

2.如權利要求1所述的方法，其特征在于，步驟1)用K-means算法對數據集X進行M次有差異的聚類，即K-means算法每次選取不同的初始聚類中心，最終得到M個有差異的劃分P₁,P₂,…P_M，組成聚類融合成員集合Old＝{P₁,P₂,…P_M}。