聚類集成算法中度量方法

展金梅 陳君濤

（1.瓊臺(tái)師范學(xué)院 海南省?？谑?571127）

（2.海南經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 海南省海口市 571127）

現(xiàn)代信息技術(shù)快速發(fā)展的新形勢背景環(huán)境下，如何在復(fù)雜多變的數(shù)據(jù)中搜索具有有價(jià)值意義的信息，成為了研究學(xué)者們較為關(guān)切的研究內(nèi)容。聚類集成算法能夠適用于不同的行業(yè)，幫助客戶細(xì)分應(yīng)用場景，不僅彌補(bǔ)了傳統(tǒng)客戶細(xì)分技術(shù)的不足，還更科學(xué)合理的劃分客戶。聚類集成算法可以將多個(gè)聚類成員以科學(xué)合理的方式進(jìn)行劃分，確保了結(jié)果的穩(wěn)定性和準(zhǔn)確率。

1 聚類集成的概況

1.1 聚類定義及方法

聚類是在不知道分類的情況下，將數(shù)據(jù)模式、特征向量，與其他數(shù)據(jù)樣本，根據(jù)某種相似性度量標(biāo)準(zhǔn)分成不同的分組，確保同一組中的成員相似，實(shí)現(xiàn)不同組成員的差異性最大化。聚類的目標(biāo)就是從無類標(biāo)簽數(shù)據(jù)組合的群集中找尋內(nèi)在結(jié)構(gòu)。通常一個(gè)好的聚類算法可以產(chǎn)生高質(zhì)量的聚類，其中聚類內(nèi)部的相似度最大，而聚類間的相似度則最低。

從統(tǒng)計(jì)學(xué)分析，聚類運(yùn)用數(shù)據(jù)建模的方法，使數(shù)據(jù)變得更簡單。

當(dāng)前越來越多的聚類方法被開發(fā)和利用，我們從不同角度對(duì)各種分類系統(tǒng)進(jìn)行定義。例如，從不同的假設(shè)方法、不同數(shù)據(jù)類型的算法等角度。關(guān)于聚類方法我們主要分為五個(gè)方法：

（1）基于分區(qū)的聚類方法。遵循優(yōu)化一個(gè)目標(biāo)劃分的準(zhǔn)則，將D分成K個(gè)分區(qū)，其中K-均值聚類是最特殊的分區(qū)劃分方法；

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

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

（4）基于網(wǎng)格的聚類方法，是指在多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)下，將D量化成若干個(gè)有限的單元格，構(gòu)建成一個(gè)網(wǎng)格結(jié)構(gòu)，其中最典型的基于網(wǎng)格的聚類方法是STING。

（5）基于模型的聚類方法，這種方法假設(shè)用一個(gè)數(shù)字模型表示D的特性，實(shí)現(xiàn)聚類優(yōu)化數(shù)據(jù)與基本模型之間的契合度，高斯混合模型聚類（GMM）是模型聚類方法的典型代表[1]。

1.2 聚類集成定義

聚類集成最早在2002年提出，通過運(yùn)行基聚類算法劃分?jǐn)?shù)據(jù)集，而后經(jīng)過組合方法對(duì)數(shù)據(jù)進(jìn)行劃分。聚類集成是運(yùn)用若干個(gè)基聚類結(jié)果，以探索出一個(gè)新型數(shù)據(jù)劃分模式來共享信息。其算術(shù)描述如下：

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

相比單個(gè)的聚類算法，聚類集成的優(yōu)勢主要表現(xiàn)為四個(gè)方面：

（1）穩(wěn)健性，可以針對(duì)不同的領(lǐng)域和不同的數(shù)據(jù)集，相比性能來說聚類集成更具有優(yōu)勢。

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

（3）與單個(gè)聚類算法相比，聚類集成算法融合不同算法在處理噪聲、孤立點(diǎn)及樣本差異時(shí)，更具穩(wěn)定性和可信估計(jì)，可以通過集成的分布情況評(píng)估聚類的不確定性。

（4）聚類集成算法通過將多個(gè)數(shù)據(jù)子集并行聚類，而獲得組合結(jié)果，將不同數(shù)據(jù)源的數(shù)據(jù)融合在一起，具有并行性和規(guī)模性的優(yōu)勢。

此外，聚類集成算法還可以保護(hù)隱私，對(duì)單個(gè)構(gòu)造器達(dá)到知識(shí)重用的效果[2]。

1.3 聚類集成算法的構(gòu)成

聚類集成算法主要包括三部分，分別是基聚類器的生成、共識(shí)函數(shù)、聚類結(jié)果的質(zhì)量評(píng)估構(gòu)成。

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

（2）共識(shí)函數(shù)的應(yīng)用，當(dāng)基聚類器獲得以后就可以應(yīng)用各種共識(shí)函數(shù)，對(duì)基聚類器的結(jié)果重新整合，進(jìn)而獲得最終的聚類結(jié)果。關(guān)于共識(shí)函數(shù)一般分為成對(duì)相似性、基于圖、基于特征及投票等共識(shí)函數(shù)種類。

（3）聚類集成結(jié)果質(zhì)量的評(píng)估，可以使用不同類型的有效性測量表對(duì)結(jié)果質(zhì)量進(jìn)行評(píng)估，一般按照內(nèi)部評(píng)估指標(biāo)和外部評(píng)估指標(biāo)兩個(gè)指標(biāo)對(duì)結(jié)果進(jìn)行評(píng)估。其中內(nèi)部評(píng)估指標(biāo)包括：Compactness，Davies-Bouldin與Dunn，外部評(píng)估指標(biāo)包括RI，AR、標(biāo)準(zhǔn)化交互信息（NMI）。

2 聚類集成的分類

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

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

基于相似的聚類集成算法是將基聚類學(xué)習(xí)器組織成一個(gè)共識(shí)相似矩陣Mmxm，在并在這個(gè)基礎(chǔ)上生成最終的聚類集成結(jié)果?；谙嗨贫染垲惣伤惴ㄓ址譃镃risp聚類集成算法和軟聚類集成算法，不過這一類算法的效率是其最大的缺點(diǎn)。因此，它只用于處理中小型規(guī)模的問題，一旦遇到大規(guī)模數(shù)據(jù)處理就存在一定的難度[3]。

2.2 基于圖的聚類集成算法

基于圖的聚類集成算法，這一算法是通過構(gòu)圖整合基聚類器所傳遞的聚類信息，然后通過執(zhí)行圖的圖劃分，鑒定集成聚類?；趫D的聚類集成算法對(duì)生成聚類集成算法的圖劃分過于依賴，劃分聚類由于是圖劃分過程中的副產(chǎn)品，由此極容易影響聚類集成的結(jié)果。當(dāng)內(nèi)在數(shù)據(jù)聚類高度不平衡的情況下，那么最終聚類集成算法將會(huì)變得不適用。

2.3 基于重新標(biāo)記的聚類集成算法

通過對(duì)齊或者重新標(biāo)記所有基聚類器的聚類標(biāo)簽，表現(xiàn)整個(gè)基聚類器中相似性的聚類，根據(jù)對(duì)齊標(biāo)簽推導(dǎo)出最后的聚類集成算法。這一方法最大的缺點(diǎn)是當(dāng)基聚類器之間沒有合理的對(duì)應(yīng)時(shí)，就不能夠很好的工作[4]。

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

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

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

基于連接的聚類集成算法的提出，是為了提高標(biāo)準(zhǔn)相似方法的性能，基于鏈接的相似性測量準(zhǔn)則，完善數(shù)據(jù)點(diǎn)之間的相似性值?；谶B接的聚類集成算法使用K-mean算法生成同構(gòu)的基聚類器，并將各個(gè)聚類中心隨機(jī)進(jìn)行初始化[5]。

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

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

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

一般相似系數(shù)與距離相反，相似系數(shù)越大，那么對(duì)象間的相似性也就越大。一般在傳統(tǒng)的聚類分析中，將對(duì)象中每個(gè)屬性在聚類過程中的貢獻(xiàn)當(dāng)作是相同的。

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

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

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

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

4.1 聚類集體差異性與聚類集成準(zhǔn)確度之間的關(guān)系

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

在計(jì)算聚類集體差異性度量值之所以運(yùn)用CSPA算法，那是因?yàn)樵谝酝木垲惣蓪?duì)比實(shí)驗(yàn)研究中，這一算法有著較為穩(wěn)定性的性能，且準(zhǔn)確度比較高的優(yōu)勢。

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

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

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

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

5 結(jié)論

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