拓展差異度的高維數據聚類算法

武 森，何慧霞，范巖巖

北京科技大學 經濟管理學院，北京 100083

1 引言

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

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

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

2 相關工作

2.1 高維數據聚類

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

2.2 CABOSFV算法

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

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

3 CABOSFV_D聚類算法

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

3.1 拓展的差異度度量方式

在CABOSFV算法中，集合的稀疏差異度SFD是計算相似度的基礎，由于集合內的差異度決定了是否將當前對象加入到某一集合（類），因此其在算法流程中起到至關重要的作用。通過分析傳統CABOSFV 中稀疏差異度計算公式的局限性，發現問題主要在于算法的執行過程中稀疏差異度公式中數據對象 |X|變化幅度過大，調節趨勢過度，而e a這一項的變化趨勢緩慢。因此，提出一種拓展的集合稀疏差異度定義方式。

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

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

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

表1 十個數據對象取值描述

3.2 位集及位集差異度

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

3.2.1 二態數據對象的位集表示

為了有效地運用位集運算進行二態數據對象聚類，需要將描述每個對象的所有二態數據全部存入位集中。假設具有n個對象的二態數據對象集合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取值的信息，以此類推。存儲一個對象的位集所需的位數為m。按照這種方式將描述每個對象的所有二態屬性數據以二進制形式全部存儲到位集中，不同的對象對應不同的位集，且不損失任何屬性信息，繼而可以有效地運用位集運算進行二態變量高維稀疏聚類。

3.2.2 位集差異度及性質

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

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

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

定義3（位集差異度推廣）X={x1,x2,…,xn} 為二態數據集合，設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個對象取值不同的位數越多，及取值皆為1 的位數越少，代表這n個對象間的差異越大。其中兩個對象之間的位集差異度是位集差異度推廣的定義在集合中只包含兩個對象時的一種特殊情況。下面給出計算任意兩個非空子集合并后的差異度公式。

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

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

3.3 CABOSFV_D算法步驟

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

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

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

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

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

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

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

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

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

4 實驗結果

4.1 數據集選取與處理

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

表2 數據集描述

4.2 評價指標

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

（1）標準互信息

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

（2）蘭德指數

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

4.3 實驗及結果分析

4.3.1 實驗設計

實驗環境為Windows 10 操作系統，CPU處理器為Intel Core i5 8250U，內存8 GB，編程工具為Matlab R2015a。

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

4.3.2 結果分析

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

表3 兩種算法聚類結果的NMI指標

表4 兩種算法聚類結果的RI指標

圖1 聚類結果的NMI指標對比圖

圖2 聚類結果的RI指標對比圖

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

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

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

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

綜合以上實驗結果，CABOSFV_D算法的聚類結果要優于傳統CABOSFV算法，且時間成本遠遠低于原始的聚類實現方式。因此可以證明CABOSFV_D 和傳統CABOSFV相比具有更好的聚類性能，在保證且進一步提高算法效率的同時獲得了更高的聚類質量。

4.3.3 差異度調整指數 p 分析

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

圖3 六個數據集上的最優p 值分布

由上述分析可知，同一數據集的最優p值分布相對集中，對于不同數據集，最優p值的分布略有差異，但多集中于[1，4]的范圍內，在實際應用中可在此范圍中選擇合適的p值。

4.3.4 閾值b 確定方法

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

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

輸出：最佳b值。

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

（2）計算劃分π1的內部有效性評價指標CVTAB1。

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

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

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

5 結束語

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