拓展差異度的高維數(shù)據(jù)聚類算法

武 森，何慧霞，范巖巖

北京科技大學(xué) 經(jīng)濟管理學(xué)院，北京 100083

1 引言

高維數(shù)據(jù)聚類是文本挖掘、客戶管理以及圖文聲像等應(yīng)用領(lǐng)域的常見研究課題[1-3]。大部分傳統(tǒng)聚類算法為低維數(shù)據(jù)而設(shè)計，但是當(dāng)數(shù)據(jù)量和數(shù)據(jù)維數(shù)呈指數(shù)增長時，傳統(tǒng)算法的局限就日益顯現(xiàn)[4]。高維數(shù)據(jù)具有稀疏性、維度災(zāi)難等特性，并且噪聲變量降低了在所有維中識別類的可能性[5]。如何在高維數(shù)據(jù)下進行有效的聚類，成為一項有意義且具有挑戰(zhàn)性的課題。

CABOSFV[6]是一種針對高維數(shù)據(jù)的稀疏特征進行聚類的算法，只需對數(shù)據(jù)進行一次掃描就能生成最終聚類結(jié)果，計算效率大幅提升。CABOSFV算法因其高效性幫助解決了一系列高維數(shù)據(jù)聚類問題，黃月等[7]采用CABOSFV 的思想構(gòu)建了基于“文獻-關(guān)鍵詞”矩陣的知識結(jié)構(gòu)識別方法；Wang 等[8]基于CABOSFV 對肺癌患者的癥候進行聚類，歸納出肺癌的三種中醫(yī)證候分類；劉希宋等[9]將CABOSFV用于客戶知識管理的應(yīng)用場景中，驗證了CABOSFV 相對于傳統(tǒng)聚類算法的優(yōu)越性。然而CABOSFV 由于參數(shù)指定復(fù)雜性和順序敏感性造成了聚類結(jié)果不穩(wěn)定。文獻[10]采用層次聚類的思想，繞過了參數(shù)指定的要求并避免了數(shù)據(jù)對象的輸入順序?qū)垲惤Y(jié)果的影響，但其改變了CABOSFV 的效率優(yōu)勢，增加了算法的計算復(fù)雜度，隨著數(shù)據(jù)數(shù)量和維數(shù)的增加，算法的時間效率明顯降低。

如何在保證并進一步提高算法效率的同時獲得更高的聚類質(zhì)量成為本文研究的出發(fā)點?；诖?，針對CABOSFV算法數(shù)據(jù)對象分配受類大小影響這一問題，提出拓展差異度的CABOSFV_D 聚類算法。引入調(diào)整指數(shù)p，拓展稀疏差異度度量方式，降低類中對象個數(shù)對對象分配的影響，使聚類過程更加準(zhǔn)確合理。在此基礎(chǔ)上結(jié)合位集（BitSet）運算速度快的優(yōu)點，提出用位集的方式實現(xiàn)CABOSFV_D 算法，提高算法的運行效率?；诹鶄€UCI標(biāo)準(zhǔn)數(shù)據(jù)集進行聚類實驗，分析討論調(diào)整指數(shù)的分布范圍，并給出確定差異度上限的方法。

2 相關(guān)工作

2.1 高維數(shù)據(jù)聚類

目前對高維數(shù)據(jù)的聚類主要包括：基于降維的聚類[11-12]、子空間聚類[13-14]、基于超圖的聚類[15]以及基于稀疏特征聚類[16]。基于降維的聚類，通過特征選擇[17-18]或特征變換[19]對高維數(shù)據(jù)進行降維處理再完成聚類。這類算法應(yīng)用廣泛，但其不足在于：降維后數(shù)據(jù)空間改變，可能損失部分重要聚類信息。由于高維數(shù)據(jù)在全維空間進行聚類比較困難，一些學(xué)者利用子空間思想在相同數(shù)據(jù)集的不同子空間中發(fā)現(xiàn)類。子空間聚類可以從多角度、多屬性綜合考慮來進行聚類，但其缺陷是子空間的劃分和選取標(biāo)準(zhǔn)難以界定?；诔瑘D聚類算法的主要思想是把高維數(shù)據(jù)處理問題轉(zhuǎn)換為圖劃分問題，可以根據(jù)用戶需要靈活調(diào)整聚類效果和質(zhì)量，但相關(guān)參數(shù)的選取將直接影響著聚類質(zhì)量的好壞。還有一類針對高維數(shù)據(jù)的稀疏特征進行聚類的算法，代表算法是CABOSFV算法[6]，將在下一部分進行介紹。

2.2 CABOSFV算法

CABOSFV算法是針對二態(tài)變量高維稀疏數(shù)據(jù)的高效聚類算法。該算法定義了集合的稀疏差異度（SFD），反映二態(tài)變量高維稀疏數(shù)據(jù)集合中對象的相似性。CABOSFV算法還定義了稀疏特征向量（SFV）及其可加性定理，能夠?qū)崿F(xiàn)只對數(shù)據(jù)進行一次掃描就完成聚類。因此，CABOSFV算法可以節(jié)省大量數(shù)據(jù)掃描和比較的時間，計算效率得到很大的提高[20]。CABOSFV 算法具有高效性，但受參數(shù)指定和輸入順序的影響造成聚類質(zhì)量不穩(wěn)定。現(xiàn)有的相關(guān)改進算法[10]對聚類過程進行調(diào)整和優(yōu)化，以避免上述缺陷，但是增加了算法的復(fù)雜性，聚類效率受到較大影響。如何在保證算法效率的同時提高聚類質(zhì)量是本文要解決的一個問題。

稀疏差異度是CABOSFV的一個核心概念，其計算公式為SFD(X)=e/(|X| ×a)，其中 |X|指集合X中的對象個數(shù)，e為該子集中所有對象取值不全相同的屬性個數(shù)，a為取值全為1的屬性個數(shù)。閾值b是算法的一個參數(shù)，代表一個類內(nèi)對象的差異度上限。稀疏差異度SFD 和閾值b共同決定當(dāng)前對象是否被分配到集合X中。根據(jù)CABOSFV算法步驟，當(dāng)前對象需要從已存在的k個類中尋找與其合并后稀疏差異度最小的類，然后根據(jù)差異度上限b判斷是否加入該類。然而隨著現(xiàn)存集合中的數(shù)據(jù)對象逐漸變多，即 |X|變大，|X|這一項對SFD的影響起到主導(dǎo)作用，使得即使不是十分相似的對象構(gòu)成集合的SFD 也很小，小于等于提前指定好的b，從而把本不太相似的對象分到同一類。即CABOSFV算法更傾向于將對象分配到數(shù)據(jù)對象較多的類中。針對上述問題，提出一種拓展差異度的CABOSFV_D聚類算法。

3 CABOSFV_D聚類算法

針對CABOSFV算法稀疏差異度的不足，本文提出拓展的差異度度量方式，同時用位集實現(xiàn)算法，使聚類效果和計算效率都得到提升。

3.1 拓展的差異度度量方式

在CABOSFV算法中，集合的稀疏差異度SFD是計算相似度的基礎(chǔ)，由于集合內(nèi)的差異度決定了是否將當(dāng)前對象加入到某一集合（類），因此其在算法流程中起到至關(guān)重要的作用。通過分析傳統(tǒng)CABOSFV 中稀疏差異度計算公式的局限性，發(fā)現(xiàn)問題主要在于算法的執(zhí)行過程中稀疏差異度公式中數(shù)據(jù)對象 |X|變化幅度過大，調(diào)節(jié)趨勢過度，而e a這一項的變化趨勢緩慢。因此，提出一種拓展的集合稀疏差異度定義方式。

定義1（拓展集合差異度）設(shè)具有n個對象的二態(tài)數(shù)據(jù)集合{x1,x2,…,xn} ，X為其中的一個對象子集，其中的對象個數(shù)記為 |X|，在該子集中所有對象稀疏特征取值皆為1的屬性個數(shù)為a，稀疏特征取值不全相同的屬性個數(shù)為e，p為大于等于1 的常整數(shù)，則集合X的拓展差異度表示為：

拓展的稀疏差異度通過給定指數(shù)p，調(diào)整稀疏差異度公式中分母的變化幅度，使不相似的對象不會誤分到同一類，增強算法的合理性。傳統(tǒng)CABOSFV的稀疏差異度是該拓展定義p=1 時的一種特殊情況。

假設(shè){x1,x2,…,x10} 是由屬性{a1,a2,…,a5} 描述的數(shù)據(jù)對象，每個數(shù)據(jù)對象的各屬性取值以及外部類標(biāo)簽如表1 所示。給定差異度上限b=0.5，分別使用原始差異度計算公式(p=1) 和拓展的差異度計算公式(p≥1)進行聚類。使用原稀疏差異度聚類的對象分配過程為：（1）將每個數(shù)據(jù)對象視作一個集合；（2）計算，將集合和合并到一個新類中，即={x1,x2}；（3）計算SFD(?)=5/(3×0)=∞＞b，將視作一個新的類，即；（4）計 算，且，因此將集合（5）對于集合，進行類似于（4）的操作，可得{x1,x2,x4,x5,x6} ；（6）對于集合，計算SFD(?)=b，因此將加入類中，={x1,x2,x4,x5,x6,x7,}。此時發(fā)現(xiàn)使用原始差異度聚類，前六個對象分配結(jié)果和實際情況相符，然而隨著類內(nèi)對象個數(shù)的增加，對象x7被誤分到了標(biāo)簽為1的類中，實際上x7和標(biāo)簽為1 的對象（如x6）并不相似。與原差異度公式中p僅能取1 不同，使用拓展的差異度度量方式進行聚類時，指數(shù)p可取大于等于1 的常整數(shù)，此處以p=2 為例，前6個數(shù)據(jù)對象的分配結(jié)果和使用原始差異度聚類的結(jié)果是一致的。對于對象x7，計算SFD(X7(0)?X1(1))=，因此將視作一個新的類，即={x7} ，和實際情況相符。通過進一步分析發(fā)現(xiàn)p取3、4等值時也能得到正確的聚類結(jié)果。因此說明和原差異度p僅能取1的計算方式相比，拓展的集合差異度具有調(diào)整分母的變化幅度的能力，從而能夠更加準(zhǔn)確地進行對象的分配。

表1 十個數(shù)據(jù)對象取值描述

3.2 位集及位集差異度

位集是一種特殊的數(shù)據(jù)結(jié)構(gòu)[21]，由二進制位構(gòu)成，保存l、0信息。CABOSFV_D算法適用于二態(tài)變量高維稀疏數(shù)據(jù)，結(jié)合二態(tài)變量僅有1和0兩種取值的特殊性，以及位集保存l和0信息這種特殊的數(shù)據(jù)結(jié)構(gòu)。本文提出用位集的方式實現(xiàn)CABOSFV_D聚類算法，把對象用位集表示，繼而所有的稀疏差異度的計算也通過位集運算完成，從而保證整個算法用位集實現(xiàn)。另外，由于位集的大小按需增長，數(shù)據(jù)維度的增加對位集的構(gòu)建與運算沒有影響，分類屬性采用獨熱編碼[22]的方式轉(zhuǎn)化為二態(tài)屬性沒有信息的損失，因此基于拓展差異度的CABOSFV_D算法同樣適用于分類屬性聚類問題。

3.2.1 二態(tài)數(shù)據(jù)對象的位集表示

為了有效地運用位集運算進行二態(tài)數(shù)據(jù)對象聚類，需要將描述每個對象的所有二態(tài)數(shù)據(jù)全部存入位集中。假設(shè)具有n個對象的二態(tài)數(shù)據(jù)對象集合X={x1,x2,…,xn}，描述對象的m個屬性集合為A={a1,a2,…,am} ，屬性aq(q∈{1,2,…,m} )均有兩種取值，即1 或0。對于每一個對象xi,i∈{1,2,…,n} ，將其所有屬性值按位存儲到位集中，記為B(xi)，稱為對象xi的位集表示。其中，第1 位存儲屬性a1取值的信息；第2 位存儲屬性a2取值的信息，以此類推。存儲一個對象的位集所需的位數(shù)為m。按照這種方式將描述每個對象的所有二態(tài)屬性數(shù)據(jù)以二進制形式全部存儲到位集中，不同的對象對應(yīng)不同的位集，且不損失任何屬性信息，繼而可以有效地運用位集運算進行二態(tài)變量高維稀疏聚類。

3.2.2 位集差異度及性質(zhì)

為將拓展的稀疏差異度計算公式SFD(X)=e/用位集的方式表示，先給出位集差異度的定義。

定義2（位集差異度）設(shè)二態(tài)數(shù)據(jù)集合表示X={x1,x2,…,xn} ，B(xi)和B(xj)分別為對象xi和xj的位集表示，則這兩個對象之間的位集差異度d(xi,xj)定義為：

其中，B(xi)ORB(xj)和B(xi)AND(xj)分別表示對應(yīng)的位進行邏輯或（OR）和邏輯與（AND）運算，結(jié)果仍然是位集；| |表示取值為1的位數(shù)。根據(jù)該位集差異度定義，兩對象間取值不同的位數(shù)越多，且取值皆為1 的位數(shù)越少，則兩個對象越具有較大的差異性。根據(jù)邏輯與（AND）和邏輯或（OR）運算滿足冪等率和交換率，位集差異度滿足性質(zhì)：（1）d(xi,xi)=0 ；（2）d(xi,xj)=d(xj,xi)。

定義3（位集差異度推廣）X={x1,x2,…,xn} 為二態(tài)數(shù)據(jù)集合，設(shè)B(xi)為對象xi,i∈{1,2,…,n} 的位集表示，且記BOR(x1,x2,…,xn)和BAND(x1,x2,…,xn)分別為：

其中BOR(x1,x2,…,xn)和BAND(x1,x2,…,xn)仍然是位集，將兩個對象之間的位集差異度定義推廣到集合X={x1,x2,…,xn} 內(nèi)各對象之間位集差異度的定義為：

根據(jù)位集差異度推廣的定義，n個對象取值不同的位數(shù)越多，及取值皆為1 的位數(shù)越少，代表這n個對象間的差異越大。其中兩個對象之間的位集差異度是位集差異度推廣的定義在集合中只包含兩個對象時的一種特殊情況。下面給出計算任意兩個非空子集合并后的差異度公式。

設(shè)二態(tài)數(shù)據(jù)集合表示X={x1,x2,…,xn} ，Y和Z為X的任意兩個非空子集，則Y和Z合并后的差異度表示為：

式（6）表明，當(dāng)X的任意兩個非空子集Y和Z合并時，可以根據(jù)關(guān)于Y的位集BOR(Y)和BAND(Y)及關(guān)于Z的位集BOR(Z)和BAND(Z)直接計算得到關(guān)于合并后集合的位集BOR(Y?Z)和BAND(Y?Z)及位集差異度d(Y?Z)。特別地，當(dāng)Y=Z時，d(Y?Z)=d(Y)=d(Z)。

3.3 CABOSFV_D算法步驟

基于拓展差異度的CABOSFV_D算法步驟如下：

輸入：對象xi的位集表示B(xi),i=1,2,…,n；閾值b；指數(shù)p。

輸出：類X1,X2,…,Xc。

步驟1計算BOR(x1,x2)和BAND(x1,x2)，根據(jù)定義2中的公式（2）得到x1和x2的位集差異度，若合并后的位集差異度不大于閾值b，則類為X1={x1,x2} ，類的個數(shù)c=1；否則，將兩個對象分別作為一個初始類，即X1={x1} ，X2={x2} ，類的個數(shù)c=2。

步驟2對于B(x3)，分別計算BOR(Xk?{x3} )和BAND(Xk?{x3} )，k∈{1,2,…,c} ，根據(jù)公式（6）得到集合Xk?{x3} 內(nèi)各對象間的位集差異度d(Xk?{x3} )，尋找使得該位集差異度最小的k0，對應(yīng)的類為Xk0。若求得的最小的位集差異度不大于閾值b，則類Xk0=Xk0?{x3} ，此時類的個數(shù)c不變；否則，新建一個類Xc+1={x3} ，類的個數(shù)更新為c=c+1。

步驟3對于B(xi),i∈{4,5,…,n} ，重復(fù)進行類似于步驟2的操作。

步驟4輸出類X1,X2,…,Xc。

從上述算法步驟可知，CABOSFV_D的算法流程和原CABOSFV 是一致的，因此時間復(fù)雜度沒有變化，兩者的區(qū)別在于CABOSFV 算法在執(zhí)行過程中計算差異度時需要對數(shù)據(jù)對象的所有屬性維分別進行計算，而CABOSFV_D使用位集只需進行一次運算，數(shù)據(jù)維度對位集的構(gòu)建并沒有影響，因此CABOSFV_D能夠提升算法的運算效率。

CABOSFV_D 聚類算法綜合考慮了算法的聚類準(zhǔn)確性和時間性能，一方面對稀疏差異度計算公式進行拓展，調(diào)整公式中分母的變化幅度，能夠提高聚類過程對象分配的準(zhǔn)確性，另一方面利用位集定義集合差異度并快速實現(xiàn)算法，進一步提高了算法的時間效率。綜合CABOSFV_D的聚類效果和運算效率，其更能有效地解決大規(guī)模高維數(shù)據(jù)聚類問題。

4 實驗結(jié)果

4.1 數(shù)據(jù)集選取與處理

實驗中選取了UCI 機器學(xué)習(xí)庫中的六個真實數(shù)據(jù)集Zoo（ZO）、Soybean-smal（lSS）、Congressional Voting Records（VO）、Lymphography（LYM）、Audiology_Standardized（AS）和Dermatology（DER）進行算法驗證。其中VO數(shù)據(jù)集部分缺失，去除有缺失屬性的對象，最終用于實驗的VO數(shù)據(jù)集的對象個數(shù)是232個。此外CABOSFV_D算法是針對二態(tài)變量高維稀疏數(shù)據(jù)提出的，因此對于非二值的分類屬性，采用獨熱編碼[22]的方式處理成二態(tài)數(shù)據(jù)。實驗數(shù)據(jù)描述如表2所示。

表2 數(shù)據(jù)集描述

4.2 評價指標(biāo)

由于在實驗中使用的數(shù)據(jù)集已經(jīng)有了類別標(biāo)簽，因此選擇外部質(zhì)量評價準(zhǔn)則進行評價，直接將聚類標(biāo)簽與實際標(biāo)簽進行比較。本實驗選擇標(biāo)準(zhǔn)互信息（Normalized Mutual information，NMI）和蘭德指數(shù)（Rand Index，RI）兩個常用聚類評價指標(biāo)對聚類結(jié)果進行評價。

（1）標(biāo)準(zhǔn)互信息

其中，X為實際類別信息，Y為聚類結(jié)果信息，MI是互信息，H是信息熵，NMI越大，表明聚類效果與真實情況越吻合。

（2）蘭德指數(shù)

其中，X和Y分別是實際類別信息和聚類結(jié)果信息，n1表示在X與Y中均屬于同一類的數(shù)據(jù)對個數(shù)，n2表示在X與Y中均不屬于同一類的數(shù)據(jù)對個數(shù)。n為數(shù)據(jù)集中對象個數(shù)，表示集合中能夠形成的數(shù)據(jù)對的總個數(shù)。蘭德指數(shù)越大，聚類效果越接近真實結(jié)果。

4.3 實驗及結(jié)果分析

4.3.1 實驗設(shè)計

實驗環(huán)境為Windows 10 操作系統(tǒng)，CPU處理器為Intel Core i5 8250U，內(nèi)存8 GB，編程工具為Matlab R2015a。

為檢驗CABOSFV_D 算法的聚類性能，選取傳統(tǒng)CABOSFV 算法進行對比實驗。實驗中CABOSFV_D和CABOSFV需要預(yù)先設(shè)置差異度閾值，給定閾值范圍b={0.125,0.25,0.375,…,2.875,3} ；CABOSFV_D 需要預(yù)先設(shè)置差異度調(diào)整指數(shù)p，給定范圍p={1,2,…,10} 。對數(shù)據(jù)進行隨機排序，分別使用傳統(tǒng)CABOSFV 算法和CABOSFV_D 算法對數(shù)據(jù)聚類，記為一組實驗。分別在六個數(shù)據(jù)集上進行100 組重復(fù)實驗以消除算法隨機性，每組實驗取參數(shù)b和p最佳情況下的聚類結(jié)果，然后將這100 組最優(yōu)聚類結(jié)果的平均值作為最終聚類結(jié)果。

4.3.2 結(jié)果分析

利用Matlab 實現(xiàn)兩種算法在UCI 數(shù)據(jù)集上的聚類實驗，獲得了算法在六個數(shù)據(jù)集上聚類結(jié)果的RI 和NMI評價指標(biāo)，如表3和表4所示。圖1和圖2是聚類結(jié)果的評價指標(biāo)對比圖，從中可以看出，當(dāng)算法以拓展的稀疏差異度公式進行聚類時，六個數(shù)據(jù)集的聚類結(jié)果的NMI和RI指標(biāo)值都得到了提高，其中AS數(shù)據(jù)集上聚類評價指標(biāo)值的提升最為明顯。外部評價指標(biāo)NMI和RI代表著聚類結(jié)果和真實結(jié)果的吻合程度，NMI和RI的值越大說明聚類越準(zhǔn)確，因此可以證明CABOSFV_D算法的聚類準(zhǔn)確性要高于CABOSFV算法。鑒于CABOSFV_D的位集實現(xiàn)方式只對算法的運算效率產(chǎn)生影響，因此聚類準(zhǔn)確性的提高主要是由于拓展的稀疏差異度調(diào)整了公式中分母的變化幅度。

表3 兩種算法聚類結(jié)果的NMI指標(biāo)

表4 兩種算法聚類結(jié)果的RI指標(biāo)

圖1 聚類結(jié)果的NMI指標(biāo)對比圖

圖2 聚類結(jié)果的RI指標(biāo)對比圖

在實驗中還記錄了各個算法運行所需時間，采用平均運行時間（Average Time，AT）來衡量算法的時間效率。平均運行時間計算方式如公式（9）所示：

其中，ti表示算法第i次運行所需時間，n表示算法運行的次數(shù)。

表5顯示了原始CABOSFV算法和CABOSFV_D算法在六個數(shù)據(jù)集上的平均運行時間。其中CABOSFV_D算法使用位集的實現(xiàn)方法進行聚類，在六個數(shù)據(jù)集上的平均運行時間相比原始算法分別減少了80.06%、87.89%、70.02%、90.08%、87.85%、93.70%。

表5 兩種算法運行時間比較

綜合以上實驗結(jié)果，CABOSFV_D算法的聚類結(jié)果要優(yōu)于傳統(tǒng)CABOSFV算法，且時間成本遠(yuǎn)遠(yuǎn)低于原始的聚類實現(xiàn)方式。因此可以證明CABOSFV_D 和傳統(tǒng)CABOSFV相比具有更好的聚類性能，在保證且進一步提高算法效率的同時獲得了更高的聚類質(zhì)量。

4.3.3 差異度調(diào)整指數(shù) p 分析

CABOSFV_D 算法引入指數(shù)p拓展了集合的稀疏差異度，指數(shù)p影響著稀疏差異度分母的調(diào)整幅度，進而影響算法聚類質(zhì)量，因此選取合適的p對算法至關(guān)重要。不同數(shù)據(jù)集100 組隨機實驗的最優(yōu)指數(shù)p的分布呈現(xiàn)出了不同的規(guī)律。圖3 顯示了在六個數(shù)據(jù)集上最優(yōu)指數(shù)p的分布，其中ZO、SS、LYM、DER 四個數(shù)據(jù)集的分布較為類似，它們的最優(yōu)p值為2的次數(shù)在總實驗次數(shù)中占比最高。LYM 的最優(yōu)p值集中分布在[1，4]，在100 次實驗中占比100%。DER 的最優(yōu)p值集中分布在[2，3]，在總實驗次數(shù)中占比99%。ZO最優(yōu)p值集中分布在[1，4]，在100次實驗中占比97%。SS數(shù)據(jù)集上最優(yōu)p值的分布相對分散，主要集中在[1，4]，在實驗中占比74%。AS 數(shù)據(jù)集在p=4 時取得最優(yōu)值的次數(shù)最多，其最優(yōu)p值分布也相對分散，主要集中于[2，4]，在實驗中占比57%。對于VO數(shù)據(jù)集，p=1時取得最佳結(jié)果的次數(shù)最多，最優(yōu)p值集中在[1，2]，在總實驗次數(shù)中占比97%。

圖3 六個數(shù)據(jù)集上的最優(yōu)p 值分布

由上述分析可知，同一數(shù)據(jù)集的最優(yōu)p值分布相對集中，對于不同數(shù)據(jù)集，最優(yōu)p值的分布略有差異，但多集中于[1，4]的范圍內(nèi)，在實際應(yīng)用中可在此范圍中選擇合適的p值。

4.3.4 閾值b 確定方法

閾值b是集合差異度上限，在本實驗中為了檢驗所提算法的性能采用帶有外部類標(biāo)簽信息的標(biāo)準(zhǔn)數(shù)據(jù)集，通過比較不同參數(shù)下聚類結(jié)果的外部評價指標(biāo)選取合適的b值。然而實際聚類應(yīng)用中的數(shù)據(jù)通常沒有類標(biāo)簽，此時可利用內(nèi)部評價指標(biāo)來確定b。CVTAB[23]是一種二值數(shù)據(jù)內(nèi)部評價指標(biāo)，CVTAB取值越大，表明類間差異度越大，聚類效果越好。利用CVTAB 確定閾值b的具體步驟如下：

輸入：數(shù)據(jù)集data,b可選取值{b1,b2,…,bz} ，其中bi∈[0.125,3],i∈{1,2,…,z}，調(diào)整指數(shù)p。

輸出：最佳b值。

（1）將 (b1,p,data)輸入CABOSFV_D 中，得到數(shù)據(jù)集data的一個劃分π1。

（2）計算劃分π1的內(nèi)部有效性評價指標(biāo)CVTAB1。

（3）對于bi,i∈{2,3,…,z} ，重復(fù)步驟（1）、（2）的操作，得到對應(yīng)的CVTABi。

（4）尋 找z0使 得CVTABz0=max(CVTABi), i∈{1,2,…,z}。

（5）輸出最佳b值：bz0。

5 結(jié)束語

針對CABOSFV 算法在聚類過程中數(shù)據(jù)對象更易被分配到較大的類中這一問題提出CABOSFV_D 算法。該算法對稀疏差異度度量方式進行了拓展，引入差異度調(diào)整指數(shù)p，從而緩和稀疏差異度公式中對象個數(shù)的影響，使對象分配更加準(zhǔn)確合理。在此基礎(chǔ)上，結(jié)合位集具有運算速度快這一優(yōu)勢，將二態(tài)數(shù)據(jù)對象和稀疏差異度都用位集存儲和表示，提高算法處理大規(guī)模數(shù)據(jù)時的運算效率。在六個UCI 標(biāo)準(zhǔn)數(shù)據(jù)集上進行實驗，結(jié)果表明CABOSFV_D獲得了比CABOSFV更好的聚類結(jié)果，且時間效率明顯提高，更能適用于數(shù)據(jù)規(guī)模較大的實際應(yīng)用場景。最后基于實驗結(jié)果討論了選取調(diào)整指數(shù)p的參考范圍，并給出了確定差異度上限b的方法。