一種新的類別型數(shù)據(jù)聚類算法

賴芨宇，陳克明

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

一種新的類別型數(shù)據(jù)聚類算法

賴芨宇1，陳克明2

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

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

類別型數(shù)據(jù)；聚類；質(zhì)量；特征向量；清晰度

0 引言

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

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

1 特征向量和距離

本文提出質(zhì)量和特征向量概念，進(jìn)一步地定義了類別型數(shù)據(jù)之間距離。

1.1 特征向量

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

設(shè)該集合沒有任何的先驗(yàn)信息，且各個(gè)屬性的權(quán)重都是一樣的，每個(gè)屬性取值之間是均等的。類別型數(shù)據(jù)的屬性取值表示如下：

（責(zé)任編輯/易永生）

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

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

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

1.2 類別型數(shù)據(jù)之間的距離

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

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

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

2 確定聚類個(gè)數(shù)

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

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

再采用凝聚式的層次聚類算法，聚類個(gè)數(shù)單調(diào)地由M變?yōu)?時(shí)，那么聚類結(jié)果的清晰度就單調(diào)地由1變?yōu)?。

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

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

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

數(shù)列Δ2，Δ3，…，ΔM-1出現(xiàn)最小值時(shí)，相鄰聚類個(gè)數(shù)的聚類結(jié)果的清晰度變化相對(duì)最小。根據(jù)清晰度變化率的定義，如果Δi(2≤i≤M-1)是最小值，那么數(shù)字i就是合理的聚類個(gè)數(shù)。在實(shí)踐中，數(shù)列的第一個(gè)極小值所對(duì)應(yīng)的聚類個(gè)數(shù)通常確定為合理聚類個(gè)數(shù)。

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

本文選取三個(gè)數(shù)據(jù)集合進(jìn)行驗(yàn)證。它們分別是投票數(shù)據(jù)集合、乳癌數(shù)據(jù)集合和動(dòng)物園數(shù)據(jù)集合，均來自于機(jī)器學(xué)習(xí)資料庫。

3.1 投票數(shù)據(jù)集合

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

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

表1 投票數(shù)列集合的數(shù)列變化率

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

當(dāng)聚類個(gè)數(shù)為7時(shí)，獲得聚類結(jié)果如表2所示。

表2 投票數(shù)據(jù)集合的聚類結(jié)果

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

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

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

3.2 乳癌數(shù)據(jù)集合

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

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

表3 乳癌數(shù)據(jù)集合聚類結(jié)果

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

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

表4 聚類個(gè)數(shù)為10的乳癌數(shù)據(jù)集合聚類結(jié)果

同樣地，以上兩個(gè)較大的子類（cluster-1、cluster-2）對(duì)應(yīng)良性組和惡性組，其準(zhǔn)確率各自高達(dá)98.37%和91.25%。

3.3 動(dòng)物園數(shù)據(jù)集合

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

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

表5 動(dòng)物園數(shù)據(jù)集合的數(shù)列

Δ7是上面數(shù)列的極小值，并且是第一個(gè)局部極小值。當(dāng)聚類個(gè)數(shù)為7時(shí)，獲得聚類結(jié)果見表6所示。

表6 聚類個(gè)數(shù)為7動(dòng)物園數(shù)值集合聚類

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

4 結(jié)論

類別型數(shù)據(jù)的聚類分析是數(shù)據(jù)挖掘中一項(xiàng)有意義的工作?；谫|(zhì)量和特征向量的聚類算法是對(duì)類別型數(shù)據(jù)集合聚類分析的一個(gè)新的研究方向。本文通過對(duì)3個(gè)類別型數(shù)據(jù)集合進(jìn)行實(shí)驗(yàn)，驗(yàn)證本文的算法是有效的。

含有權(quán)重的特征向量構(gòu)造是下一步的工作，對(duì)類別型數(shù)據(jù)間距離公式中參數(shù)修正、結(jié)合實(shí)際問題的合理選擇聚類個(gè)數(shù)，以及聚類算法的有效性評(píng)價(jià)問題也是值得研究的問題。

[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).

（責(zé)任編輯/浩 天）

C931

A

1002-6487（2016）23-0069-04

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

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

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