一種新的類別型數據聚類算法

賴芨宇，陳克明

(1.福建農林大學 交通與土木工程學院，福州 350002；2.東華大學 管理學院，上海 200051)

一種新的類別型數據聚類算法

賴芨宇1，陳克明2

(1.福建農林大學 交通與土木工程學院，福州 350002；2.東華大學 管理學院，上海 200051)

文章基于類別數據集合引入質量和特征向量的概念；確定了計算類別型數據的相似度；給出聚類結果清晰度及其變化率的定義；提出一種對質量和特征向量有效聚類類別型數據的算法。

類別型數據；聚類；質量；特征向量；清晰度

0 引言

數據挖掘中聚類算法的應用很廣泛。在商務上，聚類能幫助市場分析人員從客戶基本庫中發現不同的客戶群，并且用不同的購買模式來刻畫不同的消費群體的特征。在生物學上，聚類能用于幫助推導植物和動物的種類、基因和蛋白質的分類，獲得對種群中固定結構的認識。聚類在地球觀測數據中相似地區的確定，根據房屋的類型、價值和位置對一個城市中房屋的分類發揮作用。聚類也能用來對web上的文檔進行分類，以發現有用的信息。聚類分析能作為一種獨立的工具來獲得數據分布的情況，觀察每個簇的特點，并對某些特定的節點進一步分析。此外，聚類還可以作為其他方法的預處理步驟。聚類的目標是使同一類對象的相似度盡可能地?。徊煌悓ο笾g的相似度盡可能地大。目前聚類的方法有很多種。與數值型數據相比，類別型數據的聚類研究成果相對較少，其有效性也值得進一步探討。

對于類別型數據，本文提出一種基于質量和特征向量的聚類算法。首先，初始集合被劃分為含有相同數據對象的初始類，后續工作基于這些初始類展開。其次，借助于萬有引力定律的理念，將質量和特征向量概念引入到這些類中，使用層次聚類算法對其聚類，并采用清晰度概念確定合理聚類個數，最后實驗數據驗證算法的有效性。

1 特征向量和距離

本文提出質量和特征向量概念，進一步地定義了類別型數據之間距離。

1.1 特征向量

假設D={X1， X2， …， Xn}是含有n個類別型數據，帶有p個屬性(A1，A2，…，Ap)的集合。這里,Ai是第i個屬性的取值集合{ai1，ai2，…，aiqi}，其中，i=1,2,…,p。

設該集合沒有任何的先驗信息，且各個屬性的權重都是一樣的，每個屬性取值之間是均等的。類別型數據的屬性取值表示如下：

（責任編輯/易永生）

進一步地，構造一個q維向量，q=q1+q2+…+qp，如下：N=(n11，n12，…，n1q1，n21，n22，…，n2q2，…，np1，np2，…，npqp)這里，nimi是集合D中屬性aimi出現的次數之和，其中i=1,2,...,p;m=1,2,...,qi。

分割集合D為M個初始的非空集合(D1，D2，…，DM)，稱為單元。每個單元含有的元素的取值是相同的，單元Dk含有nk個元素(k =1，2，…，M )，且n1+n2+…+nM=n。這里單元可以看作集合D的初始聚類結果，下面的聚類分析就是從這些單元開始的。

假設單元 Dk中元素取值為a1k1，a2k2，…，apkp，這里kl∈{1 ，2,...,ql},l=1，2,...,p。這樣可以構造對應予單元Dk的一個向量，表示如下：

1.2 類別型數據之間的距離

利用單元的特征向量和質量的定義，以萬有引力法則，定義兩個單元之間的距離為：

同樣地，兩個子類間的距離定義為：

為了避免“黑洞現象”（如果一個子類的質量與其他子類的質量相差較大時，那么在隨后的聚類過程中，質量較小的類會被質量較大的類一個一個地吞噬掉，以上類似于宇宙中的“黑洞現象”），引入參數和到距離公式中。這兩個參數主要用來降低質量對單元或子類間距離的影響，數值實驗表明這兩個參數的引入是非常有效的。

2 確定聚類個數

一般地，聚類個數越多，類內元素越相似，聚類結果越清楚。因此，本文提出一個計算聚類清晰度的算法。清晰度是衡量特定聚類的整體特征的量。如果把原始集合看作一個聚類結果，則其清晰度最低；如果把每個元素看作一個子類，則清晰度最高。

定義聚類結果(C1J,C2J,…,CJJ)(1≤J≤M))的清晰度計算如下：

再采用凝聚式的層次聚類算法，聚類個數單調地由M變為1時，那么聚類結果的清晰度就單調地由1變為0。

比較Cla(3)和Cla(4)：

圖1 Cla(4)到Cla(3)的清晰度

聚類清晰度(Cla(J))顯示了當數據集合被劃分為J個子類時聚類結果的整體特征。隨著聚類個數的增加，清晰度也在增加。為了得到合理的子類個數，可以計算聚類結果清晰度的變化率，定義如下：

數列Δ2，Δ3，…，ΔM-1出現最小值時，相鄰聚類個數的聚類結果的清晰度變化相對最小。根據清晰度變化率的定義，如果Δi(2≤i≤M-1)是最小值，那么數字i就是合理的聚類個數。在實踐中，數列的第一個極小值所對應的聚類個數通常確定為合理聚類個數。

3 實驗

本文選取三個數據集合進行驗證。它們分別是投票數據集合、乳癌數據集合和動物園數據集合，均來自于機器學習資料庫。

3.1 投票數據集合

投票數據集合是美國國會的一次投票數據，包含435個樣本，每個樣本有16個屬性，且每個屬性取值集合均為{Y,N,U}。投票數據集合分為兩組，一組是民主黨議員，另一組是共和黨議員，詳細內容請見http://www.sgi.com/ tech/mlc/db/vote.all。

根據特征向量的定義，該集合的單元或子類的特征向量是48（16*3）維的。利用1.2節對類別型數據之間距離定義，本文采用凝聚式層次聚類算法得到一組數列，如表1所示。

表1 投票數列集合的數列變化率

由于Δ7是數列(Δ3,Δ4,…,Δ8)的極小值（實際上，Δ7也是第一個局部極小值），那么合理的聚類個數定為7。

當聚類個數為7時，獲得聚類結果如表2所示。

表2 投票數據集合的聚類結果

表2是投票數據集合的聚類結果。聚類結果由2個非常大的子類和5個很小的子類組成。5個很小的子類僅包含8個數據元素，它們依次是68,168,253;30;154;257,262; 289。在聚類過程中，本文把435個數據對象按照原始順序標記為0～434。也就是說，68號元素也就是原始數據集合的第69個元素。分析表明這8個元素與其他元素相差很大。也就是說，這8個元素可以看作該集合的離群點元素。

在cluster-1中有205個數據元素，其中158個是共和黨人，47個是民主黨人。cluster-1的部分元素屬于共和黨人，也就是說，77.1%(158/205)的元素被正確地聚類到共和黨一組中。

在cluster-2中有222個數據元素，其中215個是民主黨人，僅有7個是共和黨人。也就是說，高達96.8%(215/ 222)的元素被正確地聚類到民主黨一組中。

3.2 乳癌數據集合

乳癌數據集合取自http://archive.ics.uci.edu/ml/machine-learning-databases/breast-cancer-wisconsin/，共包含699個樣本。樣本數據含有9個屬性，每個屬性的取值集合均是{1,2,…,10}。每個樣本要么是屬于良性組，要么是屬于惡性組。另外，由于這699個元素中有16個元素含有缺失值，因此本實驗的數據對象是不包含缺失值的685個元素。

類似地，可以得到該集合不同聚類結果清晰度變化率的數列Δ3,Δ4,…,Δ11，見表3所示。

表3 乳癌數據集合聚類結果

由于Δ10是數列(Δ3,Δ4,…,Δ11)的極小值（實際上，Δ10也是第一個局部極小值），那么合理的聚類個數定為10。當聚類個數為10時，獲得聚類結果如表4所示。

聚類結果由2個非常大的子類和8個很小的子類組成。8個很小的子類僅包含13個數據元素，它們依次是4,339,491;66,386;96;139;270;287;335,681,610;620。

表4 聚類個數為10的乳癌數據集合聚類結果

同樣地，以上兩個較大的子類（cluster-1、cluster-2）對應良性組和惡性組，其準確率各自高達98.37%和91.25%。

3.3 動物園數據集合

動物園數據集合數據來源http://archive.ics.uci.edu/ml/ machine-learning-databases/zoo/，包含101種動物樣本，每個樣本有18個屬性，屬性1是動物名字，屬性18是動物的分類編號（1,2,…,7）。屬性14是腿的數目，取值集合為{0, 2,4,5,6,8}，本文也是把它視為類別型屬性。其余屬性是布爾取值集合{0,1}。

對于該數據集合本文獲得如下數列(Δ3,Δ4,…,Δ9)，見表5所示。

表5 動物園數據集合的數列

Δ7是上面數列的極小值，并且是第一個局部極小值。當聚類個數為7時，獲得聚類結果見表6所示。

表6 聚類個數為7動物園數值集合聚類

類似于表2和表4，以上的聚類結果也是不錯。例如，cluster-1中的38個數據對象，有37個屬于class-1，僅有1個屬于class-3。也就是，聚類結果的子類cluster-1中絕大部分元素正確地聚類到class-1中。特別地，聚類結果的子類cluster-3中的20個元素恰好與class-2完全一致。因此，該集合的聚類正確率也是相當高。

4 結論

類別型數據的聚類分析是數據挖掘中一項有意義的工作?；谫|量和特征向量的聚類算法是對類別型數據集合聚類分析的一個新的研究方向。本文通過對3個類別型數據集合進行實驗，驗證本文的算法是有效的。

含有權重的特征向量構造是下一步的工作，對類別型數據間距離公式中參數修正、結合實際問題的合理選擇聚類個數，以及聚類算法的有效性評價問題也是值得研究的問題。

[1]Han J,Kamber M.Data Mining:Concepts and Techniques,(2nd Edi?tion)[J].Elsevier Inc.2006.

[2]Xu R,Wunsch D I,Survey of Clustering Algorithms[J].IEEE Transac?tions on Neural Networks,2005,16(3).

[3]Yang M,Chiang Y,Chen C,et al.A Fuzzy K-partitions Model for Cat?egorical Data and Its Comparison to the GoM Model[J].Fuzzy Sets and Systems,2008,(159).

[4]Kim D,Lee K H,Lee D.Fuzzy Clustering of Categorical Data Using Fuzzy Centroids[J].Pattern Recognition Letters,2004,(25).

[5]Parmar D,Wu T,Blackhurst J.An Algorithm for Clustering Categori?cal Data Using Rough Set Theory[J].Data&Knowledge Engineering, 2007,(63).

[6]Chen D,Cui D,Wang C,et al.A Rough Set-based Hierarchical Clus?tering Algorithm for Categorical Data[J].International Journal of Infor?mation Technology,2006,12(3).

[7]Li T,Ma S,Ogihara M.Entropy-based Criterion in Categorical Clus?tering[M].Canada:Proceedings of the 21stInternational Conference on Machine Learning Banff,2004.

[8]Boutsinas B,Papastergiou T.On Clustering Tree Structured Data With Categorical Nature[J].Pattern Recognition,2008,(41).

[9]Ahmad A,Dey L.A Method to Compute Distance Between Two Cate?gorical Values of Same Attribute in Unsupervised Learning for Cate?gorical Data Set[J].Pattern Recognition Letters,2007,(28).

[10]Le S Q,Ho T B.An Association-based Dissimilarity Measure for Categorical Data[J].Pattern Recognition Letters,2005,(26).

[11]Pakhira M K,Bandyopadhyay S,Maulik U.Validity Index for Crisp and Fuzzy Clusters[J].Pattern Recognition,2004,(37).

[12]Chen K,Liu L.“Best K”:Critical Clustering Structures in Categori?cal Datasets[J].Knowledge and Information Systems,2009,(20).

（責任編輯/浩 天）

C931

A

1002-6487（2016）23-0069-04

國家社會科學基金資助項目(13GBL150);上海市自然科學基金資助項目(15ZR1401600)；福建省軟科學項目（2014R0055）

賴芨宇（1962—），男，福建福州人，博士，教授，研究方向：數據挖掘、項目管理。

陳克明（1979—），男，江西新余人，博士研究生，副教授，研究方向：云計算、知識管理。