[發明專利]一種基于譜聚類算法的選擇性聚類集成方法

有效

• 申請號: 201410096258.6
• 申請日: 2014-03-14
• 公開（公告）號: CN103995821B
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 徐森;李先鋒;曹瑞;花小朋;徐靜;陳榮
• 申請（專利權）人: 鹽城工學院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京蘇高專利商標事務所(普通合伙)32204
• 代理人: 李玉平

技術領域

本發明涉及一種基于譜聚類算法的選擇性聚類集成方法，屬于數據挖掘技術領域。

背景技術

聚類分析已有四十多年的研究歷史，它在機器學習、數據挖掘、信息檢索、模式識別、生物信息學等領域發揮了極其重要的作用。傳統的聚類算法層出不窮，然而沒有一種算法能夠有效識別出具有不同大小、不同形狀、不同密度甚至可能包含噪聲的簇。與傳統的聚類算法相比，聚類集成技術具備魯棒性、新穎性、穩定性等優點，目前已成為機器學習的研究熱點之一。現有的聚類集成方法都存在很多問題與不足，如對簇的形狀強加了某種結構、對簇的大小有很強的約束、計算復雜度高、得到局部最優解等。

發明內容

發明目的：針對現有技術中存在的問題與不足，本發明提供一種可以有效提升聚類集成效果的基于譜聚類算法的選擇性聚類集成方法。

技術方案：一種基于譜聚類算法的選擇性聚類集成方法，包括如下步驟：

1、聚類成員生成；2、基于譜聚類算法選擇代表成員；3、對代表成員進行集成；4、結束。

有益效果：與現有技術相比，本發明提供的基于譜聚類算法的選擇性聚類集成方法實現簡單且可以有效提升聚類集成的效果。

附圖說明

圖1是本發明方法的流程圖；

圖2是聚類成員生成的流程圖；

圖3是基于譜聚類算法選擇代表成員的流程圖；

圖4是對代表成員進行集成的流程圖；

圖5是使用譜聚類算法對聚類成員聚類的流程圖；

圖6是使用譜聚類算法對數據集聚類的流程圖。

具體實施方式

下面結合具體實施例，進一步闡明本發明，應理解這些實施例僅用于說明本發明而不用于限制本發明的范圍，在閱讀了本發明之后，本領域技術人員對本發明的各種等價形式的修改均落于本申請所附權利要求所限定的范圍。

本發明的方法如圖1所示。步驟0是初始動作。步驟1為聚類成員生成，該步驟將在后面的部分結合圖2進行具體介紹。步驟2基于譜聚類算法選擇代表成員，該步驟將在后面的部分結合圖3進行具體介紹。步驟3對代表成員進行集成，該步驟將在后面的部分結合圖4進行具體介紹。步驟4是圖1的結束狀態。

圖2詳細說明了圖1中的步驟1，其作用是生成多個聚類成員。步驟10是起始動作。步驟11獲取聚類成員個數r(r是一個大于1的整數)和聚類個數k(一般將聚類個數k設置為數據集包含的真實類別數)。步驟12將控制參數i置初值1。步驟13判斷控制參數i是否小于或等于r，是則轉到步驟14，否則轉到步驟17。步驟14隨機生成k個均值向量，作為K均值算法的初始質心，使用K均值算法對數據集進行劃分。步驟15得到聚類結果P⁽ⁱ⁾＝{C₁⁽ⁱ⁾，…，C_k⁽ⁱ⁾}。步驟16將控制變量i加1，然后轉到步驟13。步驟17構建聚類成員集合P’＝{P⁽¹⁾,…,P^(r)}。步驟18是圖2的結束狀態。

圖3詳細說明了圖1中的步驟2，其作用是基于譜聚類算法選擇代表成員，用于后續集成。步驟20是起始動作。步驟21計算聚類成員之間的相似度，即聚類成員之間的NMI值(Normalized Mutual Information，規范化互信息)。NMI值越大，兩個聚類結果的匹配程度越高，聚類成員之間的相似度越大，其求解方法如下。設X和Y分別為聚類成員P^(a)和P^(b)表示的隨機變量，其中P^(a)和P^(b)分別有k^a和k^b個簇。設為P^(a)中的簇C_h包含的對象個數，為P^(b)中的簇C_l包含的對象個數，n_h,l表示C_h和C_l共有的對象個數，則P^(a)和P^(b)之間的NMI值為：