一種基於譜聚類算法的選擇性聚類集成方法
2023-08-02 03:05:16 1
一種基於譜聚類算法的選擇性聚類集成方法
【專利摘要】本發明公開了一種基於譜聚類算法的選擇性聚類集成方法，包括以下步驟：聚類成員生成；基於譜聚類算法選擇代表成員；對代表成員進行集成；結束。本發明的顯著優點是：實現簡單且可以有效提升聚類集成的效果。
【專利說明】一種基於譜聚類算法的選擇性聚類集成方法
【技術領域】
[0001]本發明涉及一種基於譜聚類算法的選擇性聚類集成方法，屬於數據挖掘【技術領域】。
【背景技術】
[0002]聚類分析已有四十多年的研究歷史，它在機器學習、數據挖掘、信息檢索、模式識另O、生物信息學等領域發揮了極其重要的作用。傳統的聚類算法層出不窮，然而沒有一種算法能夠有效識別出具有不同大小、不同形狀、不同密度甚至可能包含噪聲的簇。與傳統的聚類算法相比，聚類集成技術具備魯棒性、新穎性、穩定性等優點，目前已成為機器學習的研究熱點之一。現有的聚類集成方法都存在很多問題與不足，如對簇的形狀強加了某種結構、對簇的大小有很強的約束、計算複雜度高、得到局部最優解等。
【發明內容】
[0003]發明目的:針對現有技術中存在的問題與不足，本發明提供一種可以有效提升聚類集成效果的基於譜聚類算法的選擇性聚類集成方法。
[0004]技術方案:一種基於譜聚類算法的選擇性聚類集成方法，包括如下步驟:
[0005]1、聚類成員生成；2、基於譜聚類算法選擇代表成員；3、對代表成員進行集成；4、結束。
[0006]有益效果:與現有技術相比，本發明提供的基於譜聚類算法的選擇性聚類集成方法實現簡單且可以有效提升聚類集成的效果。
【專利附圖】
【附圖說明】
[0007]圖1是本發明方法的流程圖；
[0008]圖2是聚類成員生成的流程圖；
[0009]圖3是基於譜聚類算法選擇代表成員的流程圖；
[0010]圖4是對代表成員進行集成的流程圖；
[0011]圖5是使用譜聚類算法對聚類成員聚類的流程圖；
[0012]圖6是使用譜聚類算法對數據集聚類的流程圖。
【具體實施方式】
[0013]下面結合具體實施例，進一步闡明本發明，應理解這些實施例僅用於說明本發明而不用於限制本發明的範圍，在閱讀了本發明之後，本領域技術人員對本發明的各種等價形式的修改均落於本申請所附權利要求所限定的範圍。
[0014]本發明的方法如圖1所示。步驟O是初始動作。步驟I為聚類成員生成，該步驟將在後面的部分結合圖2進行具體介紹。步驟2基於譜聚類算法選擇代表成員，該步驟將在後面的部分結合圖3進行具體介紹。步驟3對代表成員進行集成，該步驟將在後面的部分結合圖4進行具體介紹。步驟4是圖1的結束狀態。
[0015]圖2詳細說明了圖1中的步驟1，其作用是生成多個聚類成員。步驟10是起始動作。步驟11獲取聚類成員個數I (I是一個大於I的整數)和聚類個數k (一般將聚類個數k設置為數據集包含的真實類別數)。步驟12將控制參數i置初值I。步驟13判斷控制參數i是否小於或等於1，是則轉到步驟14，否則轉到步驟17。步驟14隨機生成k個均值向量，作為K均值算法的初始質心，使用K均值算法對數據集進行劃分。步驟15得到聚類結果？「) = ^,)，…，Ck(i)}。步驟16將控制變量i加I，然後轉到步驟13。步驟17構建聚類成員集合P={P(1)，…，Ρα)}。步驟18是圖2的結束狀態。
[0016]圖3詳細說明了圖1中的步驟2，其作用是基於譜聚類算法選擇代表成員，用於後續集成。步驟20是起始動作。步驟21計算聚類成員之間的相似度，即聚類成員之間的NMI值(Normalized Mutual Information,規範化互信息)。NMI值越大,兩個聚類結果的匹配程度越高，聚類成員之間的相似度越大，其求解方法如下。設X和Y分別為聚類成SP(a)和P(b)表示的隨機變量，其中Ρω和P(b)分別有1^和0個簇。設<SP(a)中的簇Ch包含的對象個
數，？if為P(b)中的簇C1包含的對象個數^^表示Ch和C1共有的對象個數，則P(a)和P(b)之間的匪I值為:
【權利要求】
1.一種基於譜聚類算法的選擇性聚類集成方法，其特徵在於，包括以下步驟: (1)聚類成員生成； (2)基於譜聚類算法選擇代表成員； (3)對代表成員進行集成； (4)結束。
2.根據權利要求1所述的基於譜聚 類算法的選擇性聚類集成方法，其特徵在於，所述聚類成員生成的步驟是: (1)步驟11獲取聚類成員個數I和聚類個數k，其中I是一個大於I的整數，將聚類個數k設置為數據集包含的真實類別數； (2)步驟12將控制參數i置初值I; (3)步驟13判斷控制參數i是否小於或等於聚類成員個數I，是則執行步驟14，否則轉到步驟17 ； (4)步驟14隨機生成k個均值向量，作為K均值算法的初始質心，使用K均值算法對數據集進行劃分； (5)步驟15得到聚類結果Ρω= {Αω，-,Ck(i)}； (6)步驟16將控制參數i加I，然後轉到步驟13； (7)步驟17構建聚類成員集合P={Ρω，…，Ρ(1)}； (8)結束。
3.根據權利要求1所述的基於譜聚類算法的選擇性聚類集成方法，其特徵在於，所述基於譜聚類算法選擇代表成員的步驟是: (1)步驟21計算聚類成員之間的相似度； (2)步驟22根據步驟2計算出的相似度，使用譜聚類算法對聚類成員聚類； (3)步驟23根據步驟22獲得的聚類結果，從每個聚類成員集合中各選出一個與該簇中所有其他成員之間的NMI值之和最大的聚類成員作為代表成員； (4)結束。
4.根據權利要求1所述的基於譜聚類算法的選擇性聚類集成方法，其特徵在於所述對代表成員進行集成的步驟是: (1)步驟31計算數據點之間的相似度,數據點(Ii和dj的相似度計算如下=Sij=Cli與dj屬於同一個簇的次數/r ; (2)步驟32使用譜聚類算法對數據集聚類； (3)結束。
5.根據權利要求3所述的基於譜聚類算法的選擇性聚類集成方法，其特徵在於基於譜聚類算法選擇代表成員中，所述使用譜聚類算法對聚類成員聚類的步驟是: (1)步驟221獲取要選出的代表成員個數&； (2)步驟222構建圖上的隨機遊走對應的轉移概率矩陣P1，具體求解方法如下:P1= (D1) I1，其中S1是聚類成員之間的相似度矩陣，其元素值在權利要求書3中的步驟21求得，D1是對角度矩陣，對角元素#(「);(3)步驟223求解P1的特徵值X1≥…≥λi，若存在某個序i，使得入1嚴格大於λ?+1，則令r=i ;否則令r=rQ ； (4)步驟224將P1的前r個最大特徵值對應的特徵向量按列排放，構建矩陣1=[ιν..ur]； (5)步驟225使用K均值算法將Ur的行聚為r個聚類成員集合G1，…，Gr； (4)結束。
6.根據權利要求4所述的基於譜聚類算法的選擇性聚類集成方法，其特徵在於對代表成員進行集成，所述使用譜聚類算法對數據集聚類的步驟是: (I)步驟321構建圖上的隨機遊走對應的轉移概率矩陣P，具體求解方法如下=P=D4S,其中S是數據點之間的相似度矩陣，其元素值由步驟31求得，D是對角度矩陣，對角元素o(i,i) = j)； (2 )步驟3 2 2求解P的前k個最大特徵值對應的特徵向量並按列排放，構建矩陣Vk= [V1 …vk]; (3)步驟323使用K均值算法將Vk的行聚為k個簇D1,-,Dk； (4)結束。
【文檔編號】G06F17/30GK103995821SQ201410096258
【公開日】2014年8月20日 申請日期:2014年3月14日 優先權日:2014年3月14日
【發明者】徐森, 李先鋒, 曹瑞, 花小朋, 徐靜, 陳榮 申請人:鹽城工學院