武 森，何慧霞，范巖巖

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

1 引言

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

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

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

2 相關(guān)工作

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

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

2.2 CABOSFV算法

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

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

3 CABOSFV_D聚類(lèi)算法

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

3.1 拓展的差異度度量方式

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

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

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

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

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

3.2 位集及位集差異度

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

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

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

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

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

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

其中，B(xi)ORB(xj)和B(xi)AND(xj)分別表示對(duì)應(yīng)的位進(jìn)行邏輯或（OR）和邏輯與（AND）運(yùn)算，結(jié)果仍然是位集；| |表示取值為1的位數(shù)。根據(jù)該位集差異度定義，兩對(duì)象間取值不同的位數(shù)越多，且取值皆為1 的位數(shù)越少，則兩個(gè)對(duì)象越具有較大的差異性。根據(jù)邏輯與（AND）和邏輯或（OR）運(yùn)算滿足冪等率和交換率，位集差異度滿足性質(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)為對(duì)象xi,i∈{1,2,…,n} 的位集表示，且記BOR(x1,x2,…,xn)和BAND(x1,x2,…,xn)分別為：

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

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

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

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

3.3 CABOSFV_D算法步驟

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

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

輸出：類(lèi)X1,X2,…,Xc。

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

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

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

步驟4輸出類(lèi)X1,X2,…,Xc。

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

4.2 評(píng)價(jià)指標(biāo)

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

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

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

（2）蘭德指數(shù)

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

4.3 實(shí)驗(yàn)及結(jié)果分析

4.3.1 實(shí)驗(yàn)設(shè)計(jì)

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

為檢驗(yàn)CABOSFV_D 算法的聚類(lèi)性能，選取傳統(tǒng)CABOSFV 算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)中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} 。對(duì)數(shù)據(jù)進(jìn)行隨機(jī)排序，分別使用傳統(tǒng)CABOSFV 算法和CABOSFV_D 算法對(duì)數(shù)據(jù)聚類(lèi)，記為一組實(shí)驗(yàn)。分別在六個(gè)數(shù)據(jù)集上進(jìn)行100 組重復(fù)實(shí)驗(yàn)以消除算法隨機(jī)性，每組實(shí)驗(yàn)取參數(shù)b和p最佳情況下的聚類(lèi)結(jié)果，然后將這100 組最優(yōu)聚類(lèi)結(jié)果的平均值作為最終聚類(lèi)結(jié)果。

4.3.2 結(jié)果分析

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

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

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

圖1 聚類(lèi)結(jié)果的NMI指標(biāo)對(duì)比圖

圖2 聚類(lèi)結(jié)果的RI指標(biāo)對(duì)比圖

在實(shí)驗(yàn)中還記錄了各個(gè)算法運(yùn)行所需時(shí)間，采用平均運(yùn)行時(shí)間（Average Time，AT）來(lái)衡量算法的時(shí)間效率。平均運(yùn)行時(shí)間計(jì)算方式如公式（9）所示：

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

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

表5 兩種算法運(yùn)行時(shí)間比較

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

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

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

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

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

4.3.4 閾值b 確定方法

閾值b是集合差異度上限，在本實(shí)驗(yàn)中為了檢驗(yàn)所提算法的性能采用帶有外部類(lèi)標(biāo)簽信息的標(biāo)準(zhǔn)數(shù)據(jù)集，通過(guò)比較不同參數(shù)下聚類(lèi)結(jié)果的外部評(píng)價(jià)指標(biāo)選取合適的b值。然而實(shí)際聚類(lèi)應(yīng)用中的數(shù)據(jù)通常沒(méi)有類(lèi)標(biāo)簽，此時(shí)可利用內(nèi)部評(píng)價(jià)指標(biāo)來(lái)確定b。CVTAB[23]是一種二值數(shù)據(jù)內(nèi)部評(píng)價(jià)指標(biāo)，CVTAB取值越大，表明類(lèi)間差異度越大，聚類(lèi)效果越好。利用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的一個(gè)劃分π1。

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

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

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

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

5 結(jié)束語(yǔ)

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