聚類集成算法中度量方法

展金梅 陳君濤

（1.瓊臺師范學院 海南省海口市 571127）

（2.海南經貿職業技術學院 海南省海口市 571127）

現代信息技術快速發展的新形勢背景環境下，如何在復雜多變的數據中搜索具有有價值意義的信息，成為了研究學者們較為關切的研究內容。聚類集成算法能夠適用于不同的行業，幫助客戶細分應用場景，不僅彌補了傳統客戶細分技術的不足，還更科學合理的劃分客戶。聚類集成算法可以將多個聚類成員以科學合理的方式進行劃分，確保了結果的穩定性和準確率。

1 聚類集成的概況

1.1 聚類定義及方法

聚類是在不知道分類的情況下，將數據模式、特征向量，與其他數據樣本，根據某種相似性度量標準分成不同的分組，確保同一組中的成員相似，實現不同組成員的差異性最大化。聚類的目標就是從無類標簽數據組合的群集中找尋內在結構。通常一個好的聚類算法可以產生高質量的聚類，其中聚類內部的相似度最大，而聚類間的相似度則最低。

從統計學分析，聚類運用數據建模的方法，使數據變得更簡單。

當前越來越多的聚類方法被開發和利用，我們從不同角度對各種分類系統進行定義。例如，從不同的假設方法、不同數據類型的算法等角度。關于聚類方法我們主要分為五個方法：

（1）基于分區的聚類方法。遵循優化一個目標劃分的準則，將D分成K個分區，其中K-均值聚類是最特殊的分區劃分方法；

（2）基于分層的聚類方法，這種方法是在D的不同粒度級別上，通過建立一個層級聚類或者在指定粒度級別上設置層次閾值，從而獲得一個特定的聚類。

（3）基于密度的聚類方法。指的是在D上構建聚類采集密度的概念，低密度區域分割后的聚類就是高密度樣本區域，基于密度的聚類方法最具有代表性的就是DBSCAN。

（4）基于網格的聚類方法，是指在多分辨率的網格數據結構下，將D量化成若干個有限的單元格，構建成一個網格結構，其中最典型的基于網格的聚類方法是STING。

（5）基于模型的聚類方法，這種方法假設用一個數字模型表示D的特性，實現聚類優化數據與基本模型之間的契合度，高斯混合模型聚類（GMM）是模型聚類方法的典型代表[1]。

1.2 聚類集成定義

聚類集成最早在2002年提出，通過運行基聚類算法劃分數據集，而后經過組合方法對數據進行劃分。聚類集成是運用若干個基聚類結果，以探索出一個新型數據劃分模式來共享信息。其算術描述如下：

例如，假設給定N個數據模式的一個集合，O={O1,O2,O3,…ON}，聚類運行H次后獲得H個劃分結合，第h個劃分結果表示為其中πh(O1)的第h個劃分中，第i個模式的類標簽號。

相比單個的聚類算法，聚類集成的優勢主要表現為四個方面：

（1）穩健性，可以針對不同的領域和不同的數據集，相比性能來說聚類集成更具有優勢。

（2）聚類集成的新穎性，凡是單聚類算法無法得到的結果聚類集成算法都可以探索得到結果。

（3）與單個聚類算法相比，聚類集成算法融合不同算法在處理噪聲、孤立點及樣本差異時，更具穩定性和可信估計，可以通過集成的分布情況評估聚類的不確定性。

（4）聚類集成算法通過將多個數據子集并行聚類，而獲得組合結果，將不同數據源的數據融合在一起，具有并行性和規模性的優勢。

此外，聚類集成算法還可以保護隱私，對單個構造器達到知識重用的效果[2]。

1.3 聚類集成算法的構成

聚類集成算法主要包括三部分，分別是基聚類器的生成、共識函數、聚類結果的質量評估構成。

（1）基聚類器的生成，指的是通過實驗驗證，采用誤差不同的基聚類器構建的聚類集成算法最為有效，如果采用完全一致或者相似的基聚類器所得到的結果，將無法改善所構建的聚類集成算法的性能。關于基聚類器的生成方法主要包括同構集成方法、K均值聚類方法、數據子空間采樣方法和異構集成方法等。

（2）共識函數的應用，當基聚類器獲得以后就可以應用各種共識函數，對基聚類器的結果重新整合，進而獲得最終的聚類結果。關于共識函數一般分為成對相似性、基于圖、基于特征及投票等共識函數種類。

（3）聚類集成結果質量的評估，可以使用不同類型的有效性測量表對結果質量進行評估，一般按照內部評估指標和外部評估指標兩個指標對結果進行評估。其中內部評估指標包括：Compactness，Davies-Bouldin與Dunn，外部評估指標包括RI，AR、標準化交互信息（NMI）。

2 聚類集成的分類

聚類集成算法的分類主要分為五種，每種分類算法各有特點。

2.1 基于相似的聚類集成算法

基于相似的聚類集成算法是將基聚類學習器組織成一個共識相似矩陣Mmxm，在并在這個基礎上生成最終的聚類集成結果。基于相似度聚類集成算法又分為Crisp聚類集成算法和軟聚類集成算法，不過這一類算法的效率是其最大的缺點。因此，它只用于處理中小型規模的問題，一旦遇到大規模數據處理就存在一定的難度[3]。

2.2 基于圖的聚類集成算法

基于圖的聚類集成算法，這一算法是通過構圖整合基聚類器所傳遞的聚類信息，然后通過執行圖的圖劃分，鑒定集成聚類。基于圖的聚類集成算法對生成聚類集成算法的圖劃分過于依賴，劃分聚類由于是圖劃分過程中的副產品，由此極容易影響聚類集成的結果。當內在數據聚類高度不平衡的情況下，那么最終聚類集成算法將會變得不適用。

2.3 基于重新標記的聚類集成算法

通過對齊或者重新標記所有基聚類器的聚類標簽，表現整個基聚類器中相似性的聚類，根據對齊標簽推導出最后的聚類集成算法。這一方法最大的缺點是當基聚類器之間沒有合理的對應時，就不能夠很好的工作[4]。

2.4 基于變換的聚類集成算法

通過將各個實例表示成r元組，其中r是基聚類器的數量，第q個元素表明其聚類被分配給第q個聚類器，并在轉換以后的r元組上進行聚類分析。這一方法的缺點是，變換后的數據無法對原始數據中的信息進行完整的編碼，從而無法保證所得到的集成聚類結果與原始基聚類器上的結果具有相似性。

2.5 基于連接的聚類集成算法

基于連接的聚類集成算法的提出，是為了提高標準相似方法的性能，基于鏈接的相似性測量準則，完善數據點之間的相似性值。基于連接的聚類集成算法使用K-mean算法生成同構的基聚類器，并將各個聚類中心隨機進行初始化[5]。

3 聚類集成算法中度量方法

聚類集成算法中的相似性可以用數據之間的相似度或者相異度來描述。

3.1 聚類集成算法中的相似性度量方法

一般相似系數與距離相反，相似系數越大，那么對象間的相似性也就越大。一般在傳統的聚類分析中，將對象中每個屬性在聚類過程中的貢獻當作是相同的。

3.2 聚類集成算法中的差異性度量方法

假設每個對象有M個屬性，可以將一個對象視作M維空間的一個點，那么對兩個M維的數據對象Xi=(xi1，xi2，…，xim)和Xj=(xj1，xj2，…，xjm)，通常采用歐式距離公式是較為常用的差異性度量方法。

在聚類集成算法中歐式距離公式是較為常用的距離度量方法，而K-means則是一種簡單且較容易實現的聚類算法。

4 聚類集成算法中度量方法的分析研究

4.1 聚類集體差異性與聚類集成準確度之間的關系

為直觀的表現聚類集成差異性與聚類集成準確度之間存在的關系，主要通過模擬生成聚類集體的方法，生成一個30大小的一維矢量，來表現數據規模為30的真實聚類，以10個數據點為一簇。例如，采用10個1、10個2、10個3，將真實的聚類以[1，1，…，1，2，…，2，3，…，3…]來表示，并在此基礎上隨機改變30x（1-P)個點的簇標簽，以此模擬準確度的P聚類。如果將第一個點的簇標簽改為2，那么聚類生成為[2，1，…，1，2…，2，3，…，3]。只要采用這個方法，我們就能構成300個大小為3、平均準確度為0.6的聚類集體，聚類集體差異性度量值的計算通常使用CSPA算法。

在計算聚類集體差異性度量值之所以運用CSPA算法，那是因為在以往的聚類集成對比實驗研究中，這一算法有著較為穩定性的性能，且準確度比較高的優勢。

4.2 不同平均聚類成員準確度情況下，集體差異性度量與集成準確度之間的關系

我們通過運用試驗方法產生的平均成員準確度的方法，驗證集體差異性度量與集成性能之間的關系是否收到平均成員準確度的影響。例如，我們將每個準確度生成30個大小為3的集體，通過計算著30個集體產生的差異性，判斷與CSPA集成準確度之間的關系，并對此過程重復20次，從而得出相關系數的平均值。實驗最后得出的結論指出，隨著聚類成員平均準確度的不斷增加，集體差異性度量與集成性能之間系數的絕對值，也隨之不斷增加。一般各種差異性度量與集成性能之間的相關性在成員聚類準確度≤0.6時會很低。當平均成員的準確度>0.6時，差異性度量與集成性能之間的關系屬于正相關。

4.3 不同集體大小情況下，各種差異性度量與CSPA集成準確度的相關性研究

為探索和研究聚類集成大小是否影響到差異性度量與集成準確度之間的關系，我們通過實驗計算：在不同的聚類集體大小情況下，平均成員的準確度P=0.65的集體30個，在不同集體大小情況下，分析和計算集體的差異性與集成準確度的相關系數。實驗表示，差異性與集成準確度之間的關系確實受到集體大小的影響，在集體大小不斷增大的情況下，平均CSPA集成準確度雖然增加，但是差異性度量與集成性能之間的相關性卻不一定會增加。一般當集體大小在15-20時，差異性度量與集成性能之間呈現出最強的相關性[6]。

5 結論

綜上可見，運用聚類集成算法對在信息數據海量化背景下，提高了搜索信息的高效性和準確性。對此，本文分析聚類集成的概況，具體介紹聚類集成算法的分類，詳細分析和研究了聚類集成算法中的度量算法，以便充分利用聚類集成算法的優勢，洞察和分析數據的內在本質特點，為數據預處理和挖掘有價值的數據信息提供卓越、有效的探索工具。