針對(duì)高維數(shù)據(jù)的動(dòng)態(tài)網(wǎng)格子空間聚類算法HDGCLUS

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

(中國(guó)人民大學(xué) 信息學(xué)院計(jì)算機(jī)系，北京 100872)

1 引 言

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

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

隨著硬件平臺(tái)的提升，近年來通過并行處理[5,6]和云計(jì)算[17,18]來提高子空間聚類的計(jì)算效率.由于子空間聚類方法在聚類的同時(shí)對(duì)數(shù)據(jù)進(jìn)行降維和特征提取，有文獻(xiàn)結(jié)合機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)如深度網(wǎng)絡(luò)、圖模型等來獲得低維的數(shù)據(jù)表示[13-15]，也取得較好效果.

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

2 HDGCLUS算法

2.1 CLIQUE算法基本概念與符號(hào)

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

定義1. 子空間

對(duì)于一個(gè) n維的數(shù)據(jù)集合，其在任意K個(gè)維度上組成的空間，被稱為 K維子空間.

定義2. 網(wǎng)格參數(shù) ξ

CLIQUE有兩個(gè)輸入?yún)?shù)：網(wǎng)格參數(shù) ξ和密度參數(shù)τ.算法初始時(shí)基于網(wǎng)格參數(shù)將數(shù)據(jù)集S的每一個(gè)維度都分割成均勻的 ξ個(gè)區(qū)間，每個(gè)區(qū)間描述為一個(gè)類似于 Ui=[li，hi) 的前閉后開網(wǎng)格.

數(shù)據(jù)集中的一個(gè)樣本點(diǎn)集 V={V1，V2，…，Vk}當(dāng)且僅當(dāng)對(duì)于每一個(gè) Ui都有l(wèi)i≤ Vi< hi成立時(shí)，才稱其在單元 U={U1，U2，…，Uk}中.

定義3. 密度參數(shù) τ

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

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

定義4. 單元格連通

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

定義5. 公共面

定義6. 區(qū)域

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

稱R是最大區(qū)域，當(dāng)且僅當(dāng) R∩C=R，即沒有一個(gè)R的超集R’也包含于C，其中C是區(qū)域 R包含的一個(gè)聚類.

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

第1步. 根據(jù)網(wǎng)格參數(shù)ξ的值將原數(shù)據(jù)的每一維度劃分成相等的區(qū)間；

第2步. 初始K=1；

第3步. 掃描數(shù)據(jù)集，找出K維子空間中落在每個(gè)候選單元格的數(shù)據(jù)點(diǎn)數(shù)，根據(jù)密度閾值τ找出K維子空間中的所有稠密單元；

第4步. MDL修剪；

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

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

第7步. 用貪心算法求出覆蓋每個(gè)簇的最大區(qū)域；

第8步. 根據(jù)最大區(qū)域計(jì)算出每個(gè)聚類的最小覆蓋描述，并以析取范式的形式輸出結(jié)果；

2.2 HDGCLUS的動(dòng)態(tài)網(wǎng)格劃分

由以上對(duì)CLIQUE算法的描述和實(shí)驗(yàn)可知，該算法對(duì)輸入的網(wǎng)格參數(shù) ξ和密度參數(shù)τ敏感，采用固定等長(zhǎng)的網(wǎng)格劃分，不僅容易破壞稠密區(qū)域的邊緣，降低最終聚類結(jié)果的準(zhǔn)確性，而且由于增加了網(wǎng)格參數(shù)，人為增加了聚類結(jié)果的不準(zhǔn)確性.在HDGCLUS算法中，實(shí)現(xiàn)了網(wǎng)格的動(dòng)態(tài)劃分和稠密區(qū)域合并，并加入了邊界調(diào)整技術(shù)，降低了算法初始候選稠密單元個(gè)數(shù)，避免了人工輸入網(wǎng)格參數(shù)和邊界數(shù)據(jù)信息的丟失，提高了聚類質(zhì)量和算法效率.

2.2.1 確定網(wǎng)格劃分?jǐn)?shù)目

當(dāng)高維數(shù)據(jù)維度無限大時(shí)，其在低維空間的投影以概率1逼近正態(tài)分布[16].

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

通過將每一維度劃分為N個(gè)不同的網(wǎng)格，更真實(shí)的反映了高維數(shù)據(jù)在低維的分布情況，同時(shí)也避免了網(wǎng)格參數(shù)的敏感性對(duì)聚類結(jié)果的影響.

2.2.2 密度閾值參數(shù)設(shè)定

2.2.3 單一維度簇識(shí)別

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

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

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

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

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

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

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

V3：不存在密集區(qū)域

HDGCLUS算法中單一維簇識(shí)別步驟如下：

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

2)統(tǒng)計(jì)每一維度的最大值max和最小值min；

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

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

5) 按照稠密區(qū)域相鄰的稀疏區(qū)域的中間值為簇邊界進(jìn)行網(wǎng)格劃分.

2.3 識(shí)別子空間

HDGCLUS識(shí)別子空間的過程分為靜態(tài)剪枝和信息增量動(dòng)態(tài)剪枝兩部分，目的在于提高計(jì)算效率.

2.3.1 靜態(tài)剪枝

靜態(tài)剪枝是指在前面單一維度簇識(shí)別過程中，對(duì)每一維度進(jìn)行檢測(cè)，將滿足以下兩種情況中任意一種的維度刪除：

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

b.該維度上只有唯一的一個(gè)稠密區(qū)域；

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

情況b顯示高維空間上的類在此維度上的投影只有一個(gè)稠密區(qū)域，即任何類在該維度上的投影都在同一個(gè)區(qū)域，那么這個(gè)維度對(duì)識(shí)別高維空間上的類也沒有任何貢獻(xiàn)的，因此將其刪除.

2.3.2 信息增量動(dòng)態(tài)剪枝

在子空間自底向上迭代搜索的過程中，我們對(duì)每一個(gè)發(fā)現(xiàn)的子空間進(jìn)行判斷，同時(shí)定義了一個(gè)興趣度增量參數(shù)，如果該子空間的興趣度增益大于給定的興趣度增量參數(shù)，則該子空間不再增長(zhǎng).這樣動(dòng)態(tài)的剪枝策略，不僅有效地避免了子空間盲目地增長(zhǎng)，降低了算法復(fù)雜度，同時(shí)也有助于生成無冗余的聚類描述.

1)熵值

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

設(shè)X為一個(gè)離散隨機(jī)變量，其概率分布為：

則隨機(jī)變量X的信息熵定義為：

(1)

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

2)互信息

互信息(Mutual Information)在信息論中是衡量?jī)蓚€(gè)事件集合之間相關(guān)性大小的度量，設(shè)事件X和Y，則Y對(duì)X的互信息量定義為X的后驗(yàn)概率與先驗(yàn)概率比值的對(duì)數(shù)，即：

(2)

根據(jù)熵的連鎖規(guī)則可知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的聯(lián)合熵(Joint Entropy)，定義為：

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

(3)

3) 子空間信息增量

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

(4)

其中：

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

(5)

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

為了更直觀的衡量維度之間相關(guān)性的增長(zhǎng)，本文定義一個(gè)新的函數(shù)，興趣度增量In_gain.子空間 {X1，X2，…，Xn}的興趣度增量定義為：

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

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

(6)

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

2.4 識(shí)別聚類

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

2.5 生成聚類描述

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

2.6 HDGCLUS算法性能分析

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

3 實(shí) 驗(yàn)

本文實(shí)驗(yàn)均在Windows7操作系統(tǒng)，英特爾酷睿i3 CPU，4GB內(nèi)存硬件平臺(tái)上進(jìn)行，軟件開發(fā)實(shí)現(xiàn)語言為JAVA，數(shù)據(jù)處理平臺(tái)為MATLAB R2012a.

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 4 Datasets

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

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

在信息檢索結(jié)果評(píng)價(jià)中，準(zhǔn)確率和召回率(Recall)是兩個(gè)基本指標(biāo)，準(zhǔn)確率定義為返回結(jié)果中相關(guān)文檔所占的比例，召回率描述了返回的相關(guān)文檔占所有相關(guān)文檔的比例.在聚類結(jié)果評(píng)價(jià)中，準(zhǔn)確率可以很好地衡量參與聚類的樣本集中正確聚類的樣本比例.

本文采用F1值作為衡量聚類結(jié)果的另一評(píng)價(jià)指標(biāo).F1值融合了準(zhǔn)確率P值和召回率R值，定義為P值和R值的調(diào)和平均值：

(7)

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

(8)

(9)

針對(duì)基因表達(dá)數(shù)據(jù)，我們還進(jìn)行了NCBI生物驗(yàn)證，其生物學(xué)意義十分顯著，此處限于篇幅不作介紹.

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

表2 聚類結(jié)果Table 2 Clustering results

3.4 同類算法對(duì)比實(shí)驗(yàn)

本文將HDGCLUS與應(yīng)用廣泛的聚類算法K-Means、CLIQUE、SUBCLU、以及PROCLUS進(jìn)行對(duì)比實(shí)驗(yàn)，進(jìn)一步驗(yàn)證了HDGCLUS算法在聚類結(jié)果準(zhǔn)確性以及算法時(shí)間復(fù)雜度上的優(yōu)越性.考慮到傳統(tǒng)算法如K-means對(duì)處理超高維數(shù)據(jù)能力太弱，在此僅展示Soybean數(shù)據(jù)集結(jié)果.5種聚類算法的參數(shù)設(shè)置見表3，聚類結(jié)果的P值和F1值如表4所示.

表3 5種聚類算法的參數(shù)設(shè)置Table 3 Parameter setting of five algorithms

表4 各算法在SoyBean數(shù)據(jù)集上的運(yùn)行評(píng)價(jià)值Table 4 Evaluation values of clustering on Soybean data

各算法對(duì)數(shù)據(jù)集SoyBean聚類的運(yùn)行時(shí)間如圖2所示.

圖2 Soybean數(shù)據(jù)集上各算法運(yùn)行時(shí)間Fig.2 Running time of five algorithms on Soybean data

4 結(jié)束語

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

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

2)進(jìn)一步降低算法的參數(shù)敏感度，可在下一步工作中實(shí)現(xiàn)自適應(yīng)選擇的興趣度增益閾值參數(shù)ε.