高維混合型數據聚類算法研究

郭小康

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

0 引言

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

1 數據聚類

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

1.1 子空間的尋找

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

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

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

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

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

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

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

1.2 類的prototype提取

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

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

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

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

2 算法描述

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

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

Step0: 初始化閾值和類的個數k；

Step1: 對數據集D進行預處理；

Step2: 依據min_size隔離異常數據；

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

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

Step5：輸出聚類結果Result。

3 實驗對比

3.1 混合型數據

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

3.2 數據描述

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

表1 數據集基本信息

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

表2 各算法在數據集上的正確率

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

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

四個數據集的詳細信息如下：

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

3.3 實驗結果對比

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

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

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

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

圖2 各算法在數據集上的正確率

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

4 結論

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