郭小康

（西安建筑科技大學管理學院，陜西 西安 710050）

0 引言

研究者們已經(jīng)提出了許多優(yōu)秀的聚類算法，并在實際中得到了很好的應(yīng)用。然而，現(xiàn)有的聚類算法大多是針對低維數(shù)據(jù)設(shè)計的，而且，這些算法都是針對不同的特殊數(shù)據(jù)類型設(shè)計的，很難找到一種通用的算法應(yīng)用于各種數(shù)據(jù)類型的聚類分析中，尤其是對高維數(shù)據(jù)，由于其數(shù)據(jù)分布的特殊性，使得現(xiàn)有的聚類算法無法滿足處理高維數(shù)據(jù)的需求。為了對高維數(shù)據(jù)進行聚類，提出了一種新的高維數(shù)據(jù)聚類算法（AWSCH：an weighted subspace algorithm for the clustering of high-dimensional dataset）[1-2]，算法采用基于變異信息熵和方差的概念對高維數(shù)據(jù)進行類的特征子空間的搜索，在盡可能保留數(shù)據(jù)有效信息的情況下有效地降低了數(shù)據(jù)的維度，從而顯著地提高了聚類效率，同時，由于采用了新的相似度度量方式，從而在混合型數(shù)據(jù)空間上也可以進行特征子空間的搜索，算法的通用性也得到了提高。

1 數(shù)據(jù)聚類

數(shù)據(jù)在預(yù)處理之后，留下的數(shù)據(jù)相對來說都是特征較為明顯的數(shù)據(jù)，在此基礎(chǔ)之上，我們采用凝聚算法的思想進行初始數(shù)據(jù)簇的合并操作，直到簇的個數(shù)等于原始數(shù)據(jù)種類的個數(shù)。在聚類的過程中，采用子空間聚類的方式進行，而子空間的搜索使用維純度的方差進行。

1.1 子空間的尋找

在子空間聚類思想里，子空間維度能較好地體現(xiàn)數(shù)據(jù)類的特征，它們的特征通常比較明顯，而非特征子空間的維度特征相對來說就沒有那么明顯。在子空間的搜索過程中，子空間的凝聚度越大越好，而噪聲空間凝聚度越小越好，怎樣在兩者之間找到一個平衡點成為子空間搜索的關(guān)鍵。

通常特征子空間搜索時大多是采用一個閾值，進而在數(shù)據(jù)空間每個維度上得出一個標準，比如信息熵，當熵值小于閾值時，就把該維放進特征子空間，否則相反。但是閾值的選取受人為因素影響較大，尤其是針對不同的數(shù)據(jù)集，所采用的閾值大多不一樣，所以找到一個自適應(yīng)的方式進行特征子空間的搜索顯得十分必要。

為解決這個問題，我們利用維純度的方差進行特征子空間的搜索，在經(jīng)過數(shù)據(jù)的預(yù)處理之后，數(shù)據(jù)已經(jīng)變成一個個的數(shù)據(jù)簇，對于每一個簇的每一個維度可以進行維純度的計算，維純度就代表了該維度上的凝聚程度。在進行特征子空間的搜索時，把噪聲子空間維純度的方差定義為Variance(S)，特征子空間的維方差定義為Variance(F)，這樣就可以按自適應(yīng)函數(shù)f(e)計算出該簇的特征子空間[3]。

其中，對于子空間M來說：

其中|M|為子空間M的維數(shù)，avgM為子空間 M 上維純度的平均值，Sl(i)為子空間 M中第 i維上的維純度。

所求出的子空間應(yīng)使f(e)取得最小值。該函數(shù)既考慮了子空間的數(shù)據(jù)的緊湊度，又考慮了噪聲空間的凌亂程度，在特征子空間和噪聲子空間之間找到了一個平衡點，使得特征子空間的搜索更加合理化。

方差是度量數(shù)據(jù)離散程度的最重要、最常用的指標之一，它是測算數(shù)值型數(shù)據(jù)離散程度的最重要的方法之一，把它用于簇的特征子空間的搜索顯得很自然。由函數(shù)f(e)求出的特征子空間能代表該簇的屬性特征[4]。

1.2 類的prototype提取

類 prototype的提取其實就是類的特征的提取，對于一個數(shù)據(jù)集來說，它所包含的k個類就具有k個prototype，如果能把原始數(shù)據(jù)分成到k個凝聚度較好的簇，則這k個簇就可以被看作是該數(shù)據(jù)集k的具體的類，類的特征就是該數(shù)據(jù)集的k個prototype。

在類prototype提取的過程中，兩個簇的相似度是在兩個簇的特征子空間的并集上進行的，這樣能充分的考慮到兩個簇的特征信息以及合并之后數(shù)據(jù)緊湊度。在得到兩個簇的特征子空間的基礎(chǔ)上，通過公式即可得到兩個簇的相似度[5]。

這樣，通過計算所有簇對之間的相似度就能得到由簇對的相似度組成的相似度矩陣，在每次進行簇的合并時，從相似度矩陣中找到具有最大相似度的兩個簇進行合并，直到簇的個數(shù)等于原始數(shù)據(jù)集中類的個數(shù)，至此，非噪聲據(jù)的聚類工作結(jié)束。

每個簇的特征子空間所包含的簇通常情況下是不同的。在子空間并集上進行相似度的計算，既能保留每一個簇的特征子空間信息，又能同時滿足保留兩個簇的相關(guān)特征信息的基本要求，同時又去掉了共同的噪聲空間維度的干擾，能較好地體現(xiàn)子空間聚類的思想[6]。

2 算法描述

算法由三部分組成，第一部分是數(shù)據(jù)的預(yù)處理，這里利用了一種新的相似度的度量方式進行數(shù)據(jù)之間的相似度的計算，把原始數(shù)據(jù)集初始化成一個個小的數(shù)據(jù)簇，然后進行異常數(shù)據(jù)的隔離，經(jīng)過隔離之后留下來的簇第二部分輸入；第二部分是數(shù)據(jù)集類的 prototype 的提取，在此過程中采用子空間的方式進行簇之間的相似度的計算，直到剩下的簇的個數(shù)等于數(shù)據(jù)集中類的個數(shù)；第三部分是被隔離的異常數(shù)據(jù)的回歸，也就是把第一步隔離出來的異常數(shù)據(jù)回歸到第二部分形成的初始類中[7-8]。

算法的輸入有數(shù)據(jù)D，數(shù)據(jù)初始化閾值init_rate，異常數(shù)據(jù)隔離閾值min_size，輸出是聚類結(jié)果Result，AWSCH算法具體表述如下[9-10]：

Step0: 初始化閾值和類的個數(shù)k；

Step1: 對數(shù)據(jù)集D進行預(yù)處理；

Step2: 依據(jù)min_size隔離異常數(shù)據(jù)；

Step3: 按公式（1）提取子空間，計算相似度，進行初始簇的合并，提取類prototype提??；

Step4: 按公式（1）提取子空間，計算相似度，對被隔離的異常數(shù)據(jù)進行回歸分類處理；

Step5：輸出聚類結(jié)果Result。

3 實驗對比

3.1 混合型數(shù)據(jù)

在實驗過程中，選取 UCI機器學習網(wǎng)站上Heart Disease(Heart)、 Acute Inflammations(Acute)、Credit Approval(Credit)和 Zoo四個典型的混合型數(shù)據(jù)集進行實驗驗證，并對聚類結(jié)果進行分析。

3.2 數(shù)據(jù)描述

Zoo含有 101個數(shù)據(jù)，總維數(shù)為17。數(shù)據(jù)集包含數(shù)值型維數(shù) 2維，分類型15維。其中，第一維為類標識。數(shù)據(jù)集共分為7類，各個類包含的數(shù)據(jù)個數(shù)分別為 41、20、5、13、4、8、10（表1）。

表1 數(shù)據(jù)集基本信息

Credit含有 690個數(shù)據(jù)，總維數(shù)為15。數(shù)據(jù)集包含數(shù)值型維數(shù)7維，分類型數(shù)據(jù)維數(shù)8維。其中，最后一維為類標識，取值只有兩個。數(shù)據(jù)集共分為2類，各個類包含的數(shù)據(jù)個數(shù)分別為303、383。表2給出了各算法在Credit數(shù)據(jù)集上的正確率。

表2 各算法在數(shù)據(jù)集上的正確率

Heart含有303個的數(shù)據(jù)，總維數(shù)為14。數(shù)值型維數(shù)為6，分類型維數(shù)為8。其中，最后一維為類標識，數(shù)據(jù)集共分為5類，各個類包含的數(shù)據(jù)個數(shù)分別為164、55、36、35、13。

Acute含有120個數(shù)據(jù)，總維數(shù)為8。數(shù)值型維數(shù)為3，分類型數(shù)據(jù)維數(shù)為5。數(shù)據(jù)集可以在最后兩維針對不同的情況進行不同的類標識。以最后一維為依據(jù)時，類的大小分別為50、70；以另一維為依據(jù)時，類的大小分別為59、61。

四個數(shù)據(jù)集的詳細信息如下：

在對混合型數(shù)據(jù)進行聚類時，可以進行相似度的計算，采用公式（1）進行特征子空間的搜索，在聚類過程中的p和q的取值依據(jù)數(shù)據(jù)集的不同情況進行設(shè)定[11]。

3.3 實驗結(jié)果對比

從表2中可以看出，本文算法能取得表中結(jié)果的參數(shù)并不是唯一的，在許多其他參數(shù)下也能得到相同或接近的結(jié)果，圖1即為 init_rate 取不同值時，AWSCH 算法在數(shù)據(jù)集 Credit上的聚類準確率。

圖1 init_rate 取不同值時在Credit 上的正確率

由圖1可以看出，當 init_rate大于0.8 時，AWSCH在Credit上的正確率都是一樣的，也就是說AWSCH算法在其他參數(shù)下同樣具有較好的聚類準確率， 顯示了AWSCH算法的有效性。AWSCH在其他參數(shù)不同取值及其他數(shù)據(jù)集上也有類似的效果，不再逐一列舉。

為了更直觀地顯示各個算法的聚類結(jié)果，特對各算法的聚類結(jié)果用直方圖顯示，如圖2所示。

圖2 各算法在數(shù)據(jù)集上的正確率

從圖2可以直觀地看出，AWSCH算法的聚類明顯優(yōu)于其他算法，體現(xiàn)了算法的有效性。算法的性能來源于它prototype提取的合理性、相似度度量的適宜性以及隔離數(shù)據(jù)到prototype分配的創(chuàng)新性。

4 結(jié)論

本文提出了一種子空間聚類算法AWSCH。利用維純度去度量每一維數(shù)據(jù)的有序程度，避免了混合型數(shù)據(jù)聚類中標準不統(tǒng)一的問題；利用維純度的方差去搜索子空間，找到了一個自適應(yīng)的約束方程，充分地考慮了特征子空間和噪聲空間的影響，使子空間的搜索更加合理；在子空間權(quán)重分配時，沒有明顯的去分配每一維的權(quán)重，而采用維純度無形當中就給子空間中每一個維度賦予適當?shù)臋?quán)值；提出了一種能應(yīng)用于混合型數(shù)據(jù)相似度的計算方法，從而提出一種類prototype的提取方法，用于高維數(shù)據(jù)聚類。在相似度計算方面，首先搜索能較好地代表數(shù)據(jù)特征的子空間，然后在子空間上進行相似度的計算，從而提高聚類的精確度。在數(shù)據(jù)集類prototype的提取方面，先把較為相似的數(shù)據(jù)聚在一塊，在對噪聲數(shù)據(jù)隔離之后再進行prototype的提取，這樣就能避免噪聲數(shù)據(jù)對prototype的影響， 而且能避免把較為相似的數(shù)據(jù)聚到不同的類中，從而提高聚類精度。prototype 提取結(jié)束之后，在被隔離數(shù)據(jù)分配到類prototype過程中，并不是把數(shù)據(jù)直接分配到相關(guān)prototype所在的類，而是在所有數(shù)據(jù)prototype匹配結(jié)束之后，統(tǒng)一進行數(shù)據(jù)的分配，這樣減少了噪聲數(shù)據(jù)對類prototype的影響，避免了噪聲數(shù)據(jù)對類的真實prototype的影響，并且降低了prototype更新所帶來的計算復(fù)雜度。