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

在審

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

技術領域

本發明屬于計算；推算；計數的技術領域，特別涉及一種基于小子集分組的聚類方法。

背景技術

在很多領域的數據處理和分析問題中，需要用聚類算法把一個數據集中的樣本進行分組，從而基于分組結果對整個數據集的內部結構進行快速瀏覽、分析和處理。

現有的聚類方法絕大多數是基于數據集中對象之間某些特征的相似度來對其進行分組，使得在同一個組內的對象之間比屬于不同組的對象之間的相似度更高。這種完全基于數據的、或是借用少部分監督信息，如兩兩之間約束的聚類依賴于有效的特征表示以及有效的相似度衡量。在現實應用中，通常需要具有一定專業知識和經驗的專家來定義和選取特征及相似度度量來保證達到比較理想的聚類效果。

近幾年，眾包技術被提出并在機器學習領域得到成功應用。眾包聚類的思想是借助眾包平臺發布一系列子數據集的分組任務，然后從收集到的子集分組進行整合得到對整個數據集的聚類。顯然，在上述眾包聚類中，如何從很多個子集分組結果得到對整個數據集的全局聚類是一個關鍵問題。

發明內容

本發明解決的技術問題是，現有技術中，眾包技術被提出并在機器學習領域得到成功應用，眾包聚類中得到很多個子數據集的分組，但這些子數據集包含的樣本數目很小，導致子集之間的重疊度很小，因此產生從子集分組得到對整個數據集的全局聚類的問題，本發明提供了一種優化的基于小子集分組的聚類方法。

本發明所采用的技術方案是，一種基于小子集分組的聚類方法，所述方法包括以下步驟：

步驟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：輸出聚類結果。

優選地，所述步驟1中，s_i≤10。

優選地，所述步驟1中，h≥0.3N。

優選地，所述步驟2包括以下步驟：

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

步驟2.2：當則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。

優選地，所述步驟2.3中，把樣本關系矩陣W中的所有數據減去當前樣本關系矩陣W中的最小元素值，得到最終的樣本關系矩陣W。

優選地，所述步驟3包括以下步驟：

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

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

優選地，所述步驟6包括以下步驟：

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

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

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

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

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

優選地，所述步驟6.2中，每個對象到中心點的距離以歐氏距離計算得到。

優選地，所述步驟6.5中，所有k個中心點的變化量采用當前中心點在更新前后的歐氏距離計算。