[發明專利]一種基于小子集分組的聚類方法

在審

• 申請號: 201611133746.5
• 申請日: 2016-12-10
• 公開（公告）號: CN106778858A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 梅建萍
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 杭州賽科專利代理事務所(普通合伙)33230
• 代理人: 郭薇

1.一種基于小子集分組的聚類方法，其特征在于：所述方法包括以下步驟：

步驟1：從包含N個樣本的數據集中隨機抽樣，產生樣本容量為s_i的h個子集C_i；將每個子集C_i分為k_i個組，即其中，1≤k_i≤s_i；

步驟2：逐個考慮每個子集C_i的分組結果，累計得到所有樣本兩兩關系矩陣W；

步驟3：計算樣本關系矩陣W的規范化拉普拉斯矩陣L；

步驟4：對L進行特征分解，得到k個對應最小特征值的特征向量組成的矩陣V＝[v₁,v₂...v_k]，其中，v_c對應第c小的特征值的特征向量，c＝1,2...k，1<k<N；

步驟5：歸一化V中的橫向量，使得V中的橫向量中各個元素之和為1，其中，v_pf為V中第p行第f列的元素，為橫向量歸一化后對應位置元素的值；

步驟6：基于構成用k-means得到所有對象聚類；

步驟7：輸出聚類結果。

2.根據權利要求1所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟1中，s_i≤10。

3.根據權利要求1所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟1中，h≥0.3N。

4.根據權利要求1所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟2包括以下步驟：

步驟2.1：取子集C_i中的任意兩個樣本x_p、x_q；

步驟2.2：當x_p,則W_p,q＝W_p,q+1；當且f≠g，則W_p,q＝W_p,q-1；

步驟2.3：對i＝1,2...h，重復步驟2.1和步驟2.2，得到所有樣本的兩兩關系矩陣W。

5.根據權利要求4所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟2.3中，把樣本關系矩陣W中的所有數據減去當前樣本關系矩陣W中的最小元素值，得到最終的樣本關系矩陣W。

6.根據權利要求1所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟3包括以下步驟：

步驟3.1：計算W每行之和，得到對角矩陣D，D中每個對角元素

步驟3.2：計算規范化的拉普拉斯矩陣

7.根據權利要求1所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟6包括以下步驟：

步驟6.1：以V的每一行為一個對象的特征表示，隨機初始化k個中心點；

步驟6.2：計算每個對象到中心點的距離；

步驟6.3：將每個對象分到距離最近的中心點所在的類；

步驟6.4：更新k個中心點，每個中心點為所對應類中的對象均值；

步驟6.5：重復步驟6.2，并計算所有k個中心點的變化量，當k個中心點的最大變化量小于ε時，對象聚類穩定，繼續下一步驟。

8.根據權利要求7所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟6.2中，每個對象到中心點的距離以歐氏距離計算得到。

9.根據權利要求7所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟6.5中，所有k個中心點的變化量采用當前中心點在更新前后的歐氏距離計算。

10.根據權利要求7所述的一種基于小子集分組的聚類方法，其特征在于：所述步驟6.5中，10^-5≤ε≤10^-3。