針對高維數據的動態網格子空間聚類算法HDGCLUS

劉晨赫，劉小晴，劉 青，蘇 蕉，楊 楠，肖 林

(中國人民大學 信息學院計算機系，北京 100872)

1 引 言

聚類分析是一種重要的無監督學習方法，信息時代大量涌現的基因表達數據、圖像、文本數據等都具有很高的維度，為了解決高維數據聚類難題，產生了子空間聚類算法，它是一種在局部子空間而非全維度空間上進行搜索和識別數據中稠密簇的聚類方法.

CLIQUE[1]是較早嘗試在子空間中搜索稠密簇的算法，由IBM Almaden研究中心數據挖掘課題組提出和實現.CLIQUE綜合了傳統聚類算法中基于網格的聚類和基于密度的聚類的特點，從單一維度開始自底向上地搜索存在于子空間中的稠密簇.此后國內外提出了大量子空間聚類算法，以期提高這種聚類方法的質量和效率，德國慕尼黑大學HANS-PETER KRIEGEL教授對高維數據聚類算法做了詳細的綜述[2].依據不同的搜索策略，可以將子空間聚類分為自底向上和自頂向下的兩大類.著名的CLIQUE算法和ENCLUS[3]、MAFIA[4]、GPUMAFIA[5]、并行框架[6]以及SUBCLU[7]等都是自底向上的子空間聚類算法.自頂向下的子空間聚類算法有PROCLUS[8]、ORCLUS[9]、FINDIT[10]、δ-Clusters[11]以及COSA[12]等.

隨著硬件平臺的提升，近年來通過并行處理[5,6]和云計算[17,18]來提高子空間聚類的計算效率.由于子空間聚類方法在聚類的同時對數據進行降維和特征提取，有文獻結合機器學習領域的研究熱點如深度網絡、圖模型等來獲得低維的數據表示[13-15]，也取得較好效果.

CLIQUE算法雖然存在較多缺點，比如較高的時間復雜度、敏感的參數設置，以及采用固定網格劃分、MDL剪枝等技術，容易破壞稠密區域的邊緣或者丟失一些有用信息等，但也具有模型簡明易擴展、能對任意形狀的數據聚類、對數據輸入順序不敏感、聚類結果易于解釋以及對硬件配置和平臺要求不高的優點，尤其在生物信息學中對疾病聚類的同時發現致病原因的應用效果明顯.本文基于CLIQUE算法提出了改進的HDGCLUS(High-Dimensional Genomic data subspace CLUStering) 子空間聚類算法.新算法采用基于稀疏區域的動態網格劃分技術，實現了網格的動態劃分和稠密區域的動態合并，并加入了邊界調整技術，減少了初始候選稠密單元個數，避免了人工輸入網格參數和邊界數據信息的丟失，提高了聚類質量和算法效率.同時新算法采用靜態剪枝和信息增量動態剪枝相結合的技術，進一步降低了算法復雜度，優化了算法性能.

2 HDGCLUS算法

2.1 CLIQUE算法基本概念與符號

假設輸入為n維數據矩陣S，矩陣的行表示樣本，列表示屬性，那么S=A1*A2*A3…*An.其中A1、A2等代表相應屬性維度.S的行表示為V={V1，V2，V3，…，Vm}，其中每個樣本Vi={Vi1，Vi2，…，Vin}，即Vi的第j個分量Vij∈Aj.

定義1. 子空間

對于一個 n維的數據集合，其在任意K個維度上組成的空間，被稱為 K維子空間.

定義2. 網格參數 ξ

CLIQUE有兩個輸入參數：網格參數 ξ和密度參數τ.算法初始時基于網格參數將數據集S的每一個維度都分割成均勻的 ξ個區間，每個區間描述為一個類似于 Ui=[li，hi) 的前閉后開網格.

數據集中的一個樣本點集 V={V1，V2，…，Vk}當且僅當對于每一個 Ui都有li≤ Vi< hi成立時，才稱其在單元 U={U1，U2，…，Uk}中.

定義3. 密度參數 τ

CLIQUE算法根據密度參數來判定單元格是否為稠密單元格.數據單元 U是稠密的，當且僅當selectivity(U)>τ，其中 selectivity(U) 稱為單元格 U的選擇率，定義為：

selectivity(U)=單元格中樣本數/數據集總樣本數

定義4. 單元格連通

兩個K維空間中的單元格u1，u2稱為連通的，僅當這兩個單元格有一個公共的面，或者這兩個單元格u1，u2都跟另外一個單元格u3連通.

定義5. 公共面

定義6. 區域

區域是指由單元格組成、具有規則形狀的，并且每一條邊都與坐標軸平行的一個類矩形，可以用區間的交的形式表示.

稱R是最大區域，當且僅當 R∩C=R，即沒有一個R的超集R’也包含于C，其中C是區域 R包含的一個聚類.

CLIQUE是自底向上的子空間聚類算法，算法步驟如下[1]：

第1步. 根據網格參數ξ的值將原數據的每一維度劃分成相等的區間；

第2步. 初始K=1；

第3步. 掃描數據集，找出K維子空間中落在每個候選單元格的數據點數，根據密度閾值τ找出K維子空間中的所有稠密單元；

第4步. MDL修剪；

第5步. 由K維子空間中的稠密單元集，生成K+1維子空間中的侯選稠密單元集，若K+1維子空間中的侯選稠密單元集不為空，跳轉第3步；

第6步. 隨機選取一稠密單元格，用深度優先策略找出K維空間中的簇；

第7步. 用貪心算法求出覆蓋每個簇的最大區域；

第8步. 根據最大區域計算出每個聚類的最小覆蓋描述，并以析取范式的形式輸出結果；

2.2 HDGCLUS的動態網格劃分

由以上對CLIQUE算法的描述和實驗可知，該算法對輸入的網格參數 ξ和密度參數τ敏感，采用固定等長的網格劃分，不僅容易破壞稠密區域的邊緣，降低最終聚類結果的準確性，而且由于增加了網格參數，人為增加了聚類結果的不準確性.在HDGCLUS算法中，實現了網格的動態劃分和稠密區域合并，并加入了邊界調整技術，降低了算法初始候選稠密單元個數，避免了人工輸入網格參數和邊界數據信息的丟失，提高了聚類質量和算法效率.

2.2.1 確定網格劃分數目

當高維數據維度無限大時，其在低維空間的投影以概率1逼近正態分布[16].

因此，為了更好地反映高維數據在低維投影的分布情況，根據信息理論，將高維數據在每一維上的投影按數據的統計特征劃分為多個網格區間，N=min{(1+log2S)d，k}其中，N為每一維上網格劃分的個數，S為樣本數，d為子空間維度數目(一維空間d值為1)，k為全局空間維度數目即屬性個數.

通過將每一維度劃分為N個不同的網格，更真實的反映了高維數據在低維的分布情況，同時也避免了網格參數的敏感性對聚類結果的影響.

2.2.2 密度閾值參數設定

2.2.3 單一維度簇識別

CLIQUE根據用戶輸入的密度閾值進行稠密網格的識別，同時刪除稀疏網格.這樣可能破壞稠密區域的邊界，導致稠密區域邊界上的點無法有效識別.聚類可被看作稠密區域的集合，而稠密區域又是由稀疏區域分隔開的，因此本文將聚類重新定義為由稀疏區域分隔開的稠密區域.關聯規則指出，K維上稠密區域，在任一K-1維上的投影亦是稠密的.反過來說，任一K-1維上的稀疏區域，在K維上也是稀疏的.那么單一維度上的稀疏區域，也即是高維空間中的稀疏區域在一維空間上的投影，因此一維空間上的稀疏區域構成了類的邊界，本算法也將立足于此進行稠密區域的劃分.

依據聚類為稀疏區域分隔開的稠密區域這一思想，按照平均誤差最小的原則，本文將每一維度上簇的分界定義為與稠密區域相鄰的稀疏區域的中間值.這樣調整了稠密區域的邊界，避免了稠密區域邊界上的點信息的丟失.

圖1 單一維度簇識別樣例圖Fig.1 Clusters in single dimension

圖1的平行坐標系展示了具有3個屬性的64個樣本.第一步的網格劃分，將64個樣本點劃分為7個網格，在V1維度上，可以看到[0，10)，[10，20)，[30，40) 為稠密單元格，其余為稀疏單元格.傳統的稠密單元識別算法，將會丟失[20，22)之間的數據點，造成聚類信息的不完整.

本算法通過相鄰稠密單元格的合并，以及在稀疏區域中點的劃分，可以有效的識別單一維度上的簇.具體各維度上的簇的表示如下：

V1：[0，25)，[25，45)

V2：[0，25)，[25，45)

V3：不存在密集區域

HDGCLUS算法中單一維簇識別步驟如下：

1)依次輸入每一維度，并進行排序；

2)統計每一維度的最大值max和最小值min；

3)將每一維度[min，max]區間，劃分為(1+log2S) 個前閉后開的網格區間；

4) 根據密度閾值τ確定稠密單元格，并將相鄰稠密單元格合并；

5) 按照稠密區域相鄰的稀疏區域的中間值為簇邊界進行網格劃分.

2.3 識別子空間

HDGCLUS識別子空間的過程分為靜態剪枝和信息增量動態剪枝兩部分，目的在于提高計算效率.

2.3.1 靜態剪枝

靜態剪枝是指在前面單一維度簇識別過程中，對每一維度進行檢測，將滿足以下兩種情況中任意一種的維度刪除：

a.該維度上不存在任何稠密區域；

b.該維度上只有唯一的一個稠密區域；

情況a表明高維空間在這個維度上的投影是分散的或者是均勻的，那么該維度對最終類的發現沒有任何貢獻，因此將其刪除.

情況b顯示高維空間上的類在此維度上的投影只有一個稠密區域，即任何類在該維度上的投影都在同一個區域，那么這個維度對識別高維空間上的類也沒有任何貢獻的，因此將其刪除.

2.3.2 信息增量動態剪枝

在子空間自底向上迭代搜索的過程中，我們對每一個發現的子空間進行判斷，同時定義了一個興趣度增量參數，如果該子空間的興趣度增益大于給定的興趣度增量參數，則該子空間不再增長.這樣動態的剪枝策略，不僅有效地避免了子空間盲目地增長，降低了算法復雜度，同時也有助于生成無冗余的聚類描述.

1)熵值

根據信息熵的概念，在子空間聚類過程中，存在簇的子空間往往比不存在簇的子空間擁有更小的熵值.

設X為一個離散隨機變量，其概率分布為：

則隨機變量X的信息熵定義為：

(1)

本文信息熵的對數的底數取值為2，信息熵的單位為比特(bit).

2)互信息

互信息(Mutual Information)在信息論中是衡量兩個事件集合之間相關性大小的度量，設事件X和Y，則Y對X的互信息量定義為X的后驗概率與先驗概率比值的對數，即：

(2)

根據熵的連鎖規則可知I(X，Y)=I(Y，X)，

即有，

I(X，Y) =H(X)-H(X|Y)=H(Y)-H(Y|X)

=H(X)+H(Y)-H(X，Y)

其中H(X，Y)是事件X和Y的聯合熵(Joint Entropy)，定義為：

H(X，Y)=-∑p(x，y)·log2p(x，y)

(3)

3) 子空間信息增量

單一維度兩兩之間的相關性可以用信息熵中的互信息I(X，Y)來衡量，同理多個維度之間的相關性我們也用熵來衡量，并將其定義為興趣度In(X)(1維子空間的興趣度為0)[3]：

(4)

其中：

H({X1，X2，…，Xn})
=-∑x1…∑xnp(x1，…，xn)log2p(x1，…，xn)

(5)

x1，x2，…， xn是 X1，X2，…，Xn的特定值，相應的 p(x1，x2，…，xn) 為 X1，X2，…，Xn這些變量同時出現的概率.在全維空間中，假設存在維度A和維度B，兩維之間數據分布相似，那么這兩個維度之間具有較強的相關性.A和B共同形成的子空間AB已經能很好的表述A和B形成的類，為了得到最小無冗余的子空間，AB子空間無需繼續增長.更一般化的來說，在算法自底向上的搜索過程中，對于任一候選的k維子空間Sk，如果In(Sk)的值大于給定的閾值ε，則該子空間不再增長.

為了更直觀的衡量維度之間相關性的增長，本文定義一個新的函數，興趣度增量In_gain.子空間 {X1，X2，…，Xn}的興趣度增量定義為：

In_gain({X1，X2，…，Xn})=

In({X1，X2，…，Xn})-max{In({X1，X2，…，Xn}-{Xi})}

(6)

興趣度增量是子空間增加一個維度的最小興趣度增量，1維子空間的興趣度增量為0.在算法自底向上的搜索過程中，對于任一候選的k維子空間Sk，如果In_gain(Sk)的值大于給定的閾值ε′，則該子空間不再增長.

2.4 識別聚類

識別聚類的過程是根據稠密單元格的集合Dk(集合中單元格全部都在同一個k維空間S中)，得出集合Dk的一個劃分{Dk1，Dk2，…，Dkq}，滿足處于Dki中所有稠密單元格都是相鄰的，并且處在不同的Di、Dj中的單元格是不相鄰的.

2.5 生成聚類描述

根據2.4產生集合Dk的每一個劃分{Dk1，Dk2，…，Dkq}，找到聚類的最大覆蓋，通過最大覆蓋生成最小描述，并以析取范式的形式表示出來.

2.6 HDGCLUS算法性能分析

與CLIQUE算法相比，HDGCLUS算法同樣采用自底向上的搜索過程，但動態網格劃分以及靜態剪枝和信息增量動態剪枝相結合的剪枝方法大大減少了稠密網格數目以及子空間迭代搜索次數，降低了算法時間復雜度.假定S為樣本數，D為數據集維數，K為子空間大小，HDGCLUS算法整體的時間復雜度為O(S*logS *K)，同時算法在子空間搜索過程中需要存儲每一個稠密區域信息，空間復雜度為O(D*logS).

3 實 驗

本文實驗均在Windows7操作系統，英特爾酷睿i3 CPU，4GB內存硬件平臺上進行，軟件開發實現語言為JAVA，數據處理平臺為MATLAB R2012a.

3.1 實驗數據集

為了檢測HDGCLUS算法在不同高維數據集上的良好伸縮性，實驗選取了4組真實數據集：高維度的SoyBean[19]，較高維度的Leukemia[20]、DLBCL[21]以及超高維Breast Cancer[22]，數據集具體信息如表1所示.

表1 實驗數據集Table 1 4 Datasets

3.2 評價指標

由于子空間聚類是在局部樣本集以及局部空間中搜索可能存在的聚類，因此部分樣本和維度可能并不在聚類結果中，為了更為客觀的展示HDGCLUS算法與其他算法的性能，本文選取信息檢索中的準確率(Precision)和F1值(F-Measure)兩者作為評價指標.

在信息檢索結果評價中，準確率和召回率(Recall)是兩個基本指標，準確率定義為返回結果中相關文檔所占的比例，召回率描述了返回的相關文檔占所有相關文檔的比例.在聚類結果評價中，準確率可以很好地衡量參與聚類的樣本集中正確聚類的樣本比例.

本文采用F1值作為衡量聚類結果的另一評價指標.F1值融合了準確率P值和召回率R值，定義為P值和R值的調和平均值：

(7)

由于聚類結果中存在多個簇，因此本文定義整個聚類的P值為所有簇的P值的平均值，同理F1值也為所有簇的F1值的平均值.假設k為聚類結果中簇的個數，則聚類的P值和F1值定義如下：

(8)

(9)

針對基因表達數據，我們還進行了NCBI生物驗證，其生物學意義十分顯著，此處限于篇幅不作介紹.

3.3 實驗結果

表2 聚類結果Table 2 Clustering results

3.4 同類算法對比實驗

本文將HDGCLUS與應用廣泛的聚類算法K-Means、CLIQUE、SUBCLU、以及PROCLUS進行對比實驗，進一步驗證了HDGCLUS算法在聚類結果準確性以及算法時間復雜度上的優越性.考慮到傳統算法如K-means對處理超高維數據能力太弱，在此僅展示Soybean數據集結果.5種聚類算法的參數設置見表3，聚類結果的P值和F1值如表4所示.

表3 5種聚類算法的參數設置Table 3 Parameter setting of five algorithms

表4 各算法在SoyBean數據集上的運行評價值Table 4 Evaluation values of clustering on Soybean data

各算法對數據集SoyBean聚類的運行時間如圖2所示.

圖2 Soybean數據集上各算法運行時間Fig.2 Running time of five algorithms on Soybean data

4 結束語

本文設計實現了針對超高維數據的子空間聚類算法HDGCLUS，分析并實驗驗證了HDGCLUS在處理超高維數據時的優良性能.通過研究分析可知HDGCLUS依然存在不足，我們將在以下方面做進一步的探索：

1)子空間聚類算法對數據類別分布敏感，因此在今后的工作中需要進一步優化算法，解決新算法在類別樣本數分布不均勻的數據集上聚類效果不理想的問題.

2)進一步降低算法的參數敏感度，可在下一步工作中實現自適應選擇的興趣度增益閾值參數ε.