一種混合屬性數(shù)據(jù)的聚類算法

張艷麗，鄭 誠

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039）

一種混合屬性數(shù)據(jù)的聚類算法

張艷麗，鄭 誠

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039）

提出一種基于屬性分解的隨機(jī)分組的改進(jìn)方法，以提高聚類算法的穩(wěn)定性和適用性。實(shí)驗(yàn)仿真結(jié)果表明，改進(jìn)算法具有很好的穩(wěn)定性和應(yīng)用性。

聚類；混合數(shù)據(jù)；分類屬性

所謂聚類，就是將物理或抽象對(duì)象的集合構(gòu)成為由類似的對(duì)象組成多個(gè)類或簇的過程。由聚類所生成的簇是一組數(shù)據(jù)對(duì)象的集合，同一簇中的數(shù)據(jù)對(duì)象盡可能相似，不同簇中的數(shù)據(jù)對(duì)象盡可能相異[1]。聚類算法在許多領(lǐng)域獲得了廣泛應(yīng)用[2]，但是，由于在實(shí)際應(yīng)用中，許多數(shù)據(jù)集不僅包含數(shù)值屬性的數(shù)據(jù)，同時(shí)也包含如地圖顏色、幾何紋理等分類屬性的數(shù)據(jù)。因此使得基于傳統(tǒng)的歐式距離劃分的聚類算法難以適用于混合屬性數(shù)據(jù)集的要求。為此各研究學(xué)者就此問題進(jìn)行了深入地研究和探討。

MacQueen所提出的 k-means方法[3]是最早、也是最簡單的聚類方法，但是該方法只能對(duì)數(shù)值屬性的對(duì)象集進(jìn)行聚類，無法對(duì)分類屬性和混合型屬性的對(duì)象集進(jìn)行聚類。Huang提出的k-modes算法和k-prototypes算法[4]推廣了k-means方法，使之可以對(duì)分類屬性和混合型屬性的數(shù)據(jù)集進(jìn)行聚類。同時(shí)陳寧、陳安、周龍?bào)J進(jìn)一步提出了模糊k-prototypes算法，并利用引進(jìn)模糊聚類算法來提高聚類結(jié)果的準(zhǔn)確性[5]。

上述方法在聚類過程中，均利用分類型屬性簡單匹配相異度，將分類型屬性的數(shù)據(jù)轉(zhuǎn)化為數(shù)值型屬性數(shù)據(jù)間的基于距離的計(jì)算問題，從而解決了對(duì)混合屬性數(shù)據(jù)集的聚類問題。但是上述方法在對(duì)分類屬性數(shù)據(jù)和混合型屬性數(shù)據(jù)進(jìn)行聚類時(shí)，總會(huì)存在一些如聚類結(jié)果的隨機(jī)性和不穩(wěn)定性等缺點(diǎn)，甚至有時(shí)會(huì)出現(xiàn)空聚類[6-7]現(xiàn)象。

為此，本文在k-prototypes算法的基礎(chǔ)上進(jìn)行改進(jìn)，利用隨機(jī)分組的思想動(dòng)態(tài)地選取初始原型點(diǎn)，同時(shí)對(duì)分類屬性數(shù)據(jù)采取屬性分解的方法進(jìn)行處理，從而提高算法的穩(wěn)定性和適用性，使聚類結(jié)果更加理想化。

1 相關(guān)觀念

聚類是將數(shù)據(jù)對(duì)象分成類或簇的過程，使同一個(gè)簇中的對(duì)象之間具有很高的相似度，而不同簇中的對(duì)象高度相異[2]。其中對(duì)象間的相異度度量用來表示對(duì)象間的相異程度，代價(jià)函數(shù)用來表示對(duì)象間的相似程度。

1.1 相異度度量

對(duì)象X、Y的相異度定義為對(duì)象中不相等的分類屬性值的數(shù)目。設(shè)X、Y是數(shù)據(jù)集中兩個(gè)包含m種分類屬性的數(shù)據(jù)對(duì)象，也可以說X、Y是數(shù)據(jù)集中任意兩個(gè)具有 m（x1，x2，x3，…，xm）維分類屬性值的數(shù)據(jù)對(duì)象，對(duì)象間的相異度 d（i，j）定義為：

如果xif或者 xjf缺失（即對(duì)象 i或?qū)ο?j沒有變量 f的度量值），或者 xif=xjf=0，且變量 f是非對(duì)稱的二元變量，則指示項(xiàng)=0；否則，指示項(xiàng)=1。為了方便計(jì)算，假定每一個(gè)屬性中的全部屬性值以同等概率出現(xiàn)，即式（1）中的指示項(xiàng)=1。由此得到簡化的相異度公式為：

其中，當(dāng)xj=yj時(shí)，δ（x，yj）=0；當(dāng) xj≠yj時(shí) ，δ（xj，yj）=1。 nxj，nyj是數(shù)據(jù)集中屬性j所包含屬性值xj，yj的個(gè)數(shù)，舉例如表1所示。

表1 舉例所用數(shù)據(jù)

根據(jù)公式計(jì)算：d（1，2）=2+2=4；d（1，4）=0；d（1，3）=2+2=4；d（1，5）=2+2=4。

該公式說明兩個(gè)對(duì)象不相等的分類屬性值的數(shù)目越大，則兩個(gè)對(duì)象越不相似。

由此可以得出，計(jì)算數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)的混合數(shù)據(jù)的相異度度量的距離為：

1.2 代價(jià)函數(shù)的計(jì)算

代價(jià)函數(shù)用來表示對(duì)象間的相似程度，擴(kuò)展kmeans算法代價(jià)函數(shù)的計(jì)算方法，使其可以計(jì)算數(shù)值型數(shù)據(jù)和分類型混合屬性數(shù)據(jù)對(duì)象的代價(jià)函數(shù)。定義X是具有m種屬性值總數(shù)為n的對(duì)象的數(shù)據(jù)集，即X={X1，X2， … ，Xn}，Xi=（x1，x2， … ，xm）， 其 中 包 含 m1個(gè) 數(shù) 值型的數(shù)據(jù)，m2個(gè)分類型的數(shù)據(jù)，m=m1+m2，k是正整數(shù)，表示聚類的個(gè)數(shù)。則代價(jià)函數(shù)的計(jì)算總公式為：

其中，Ql=[ql1，ql2，…，qlm]是聚類 I的模式或者原型，yil是劃分矩陣Yn×l中的任意一個(gè)元素，d表示相似度量值。在該公式中，Y有以下兩個(gè)特性：

在式（4）中，針對(duì)于混合屬性的數(shù)據(jù)，引用了混合屬性數(shù)據(jù)中的數(shù)值屬性數(shù)據(jù)和分類屬性數(shù)據(jù)的計(jì)算相異度的式（3），得到總的代價(jià)函數(shù)公式為：

2 算法的改進(jìn)

k-modes算法和k-prototypes算法在聚類混合屬性數(shù)據(jù)時(shí)，對(duì)初值有明顯的依賴，導(dǎo)致聚類結(jié)果不理想，甚至出現(xiàn)聚類空集的現(xiàn)象。因此本文在原有算法的基礎(chǔ)上進(jìn)一步改進(jìn)，利用隨機(jī)分組確定初始原型的方法，然后對(duì)隨機(jī)分組得到的初始原型進(jìn)一步加工處理，使得聚類結(jié)果對(duì)初值的依賴性有所降低，從而使聚類結(jié)果更合理、穩(wěn)定，達(dá)到改進(jìn)算法的目的。

2.1 分類屬性處理算法

假定數(shù)據(jù)對(duì)象x是具有m維屬性的數(shù)據(jù)對(duì)象，其中含有m1個(gè)數(shù)值型數(shù)據(jù)和m2個(gè)分類型屬性。那么，可以直觀地將數(shù)據(jù)對(duì)象x看成分別有m1維數(shù)值屬性和m2維分類屬性組成，其中m2維分類屬性又可以分別看成由多維數(shù)據(jù)值組成。例如：表2中的分類型屬性“渠道”可以看成是由 “直接”、“間接”2維分類數(shù)據(jù)值組成的；分類型屬性“語義范疇”可以看成是由“植物”、“語言”2維分類數(shù)據(jù)組成的。在計(jì)算中，分別將分類型屬性看成是由多維的分類屬性數(shù)據(jù)值組成的。

表2 屬性分解原型舉例

對(duì)象1的分解原型表示為：

1={2，{0（直接），1（間接）}，{1（植物），0（語言）}}；

對(duì)象2的分解原型表示為：

2={2，{1（直接），0（間接）}，{0（植物），1（語言）}}；

對(duì)象3的分解原型表示為：

3={3，{1（直接），0（間接）}，{1（植物），0（語言）}}；

對(duì)象4的分解原型表示為：

4={3，{0（直接），1（間接）}，{1（植物），0（語言）}}；

對(duì)象5的原型表示為：

5={2，{1（直接），0（間接）}，{0（植物），1（語言）}}；

則對(duì)象1，2，5組成的聚類Q1的分解原型可以表示為：

Q1={2，{2/3（直 接 ），1/3（間 接 ）}，{0（植 物 ），3/3（語言）}}；

則對(duì)象3，4組成的聚類Q2的分解原型可以表示為：

Q2={2，{1/2（直 接 ），1/2（間 接 ）}，{2/2（植 物 ），0（語言）}}；

然后利用式（2）計(jì)算對(duì)象與聚類之間的距離，得到其中的最小距離。通過這種方式，可以有效地避免在分類屬性中出現(xiàn)頻率少的屬性值丟失的現(xiàn)象，從而得到更合理的聚類的結(jié)果。

2.2 隨機(jī)分組算法

隨機(jī)分組算法的基本原理是依據(jù)需要聚類的個(gè)數(shù)k和數(shù)據(jù)集中所包含數(shù)據(jù)的個(gè)數(shù)n。將總數(shù)為n的數(shù)據(jù)集劃分為count=n/k組，然后從count組中分別選擇數(shù)據(jù)對(duì)象k次，構(gòu)成k個(gè)聚類的初始原型值。

算法流程：

（1）分組數(shù)據(jù)集。已知數(shù)據(jù)集 X={x1，x2，…，xn}是包含n個(gè)數(shù)據(jù)對(duì)象的集合。依據(jù)數(shù)據(jù)集中數(shù)據(jù)個(gè)數(shù)n和需要聚類的個(gè)數(shù)k，將整個(gè)數(shù)據(jù)集分組成為count=n/k組，即數(shù)據(jù)集 X={[x1，x2，…，xk]，[xk+1，…，x2k]，…}。 如果分組后數(shù)據(jù)集中還有剩余的對(duì)象未分配，則將剩余的對(duì)象分配到任意組中，本文選擇將其分配到第一個(gè)分組中。

（2）隨機(jī)獲得一個(gè)初始點(diǎn)。將數(shù)據(jù)集分組成為子數(shù)據(jù)集后，依次從count個(gè)子數(shù)據(jù)集中隨機(jī)選擇一個(gè)數(shù)據(jù)對(duì)象，形成由count個(gè)數(shù)據(jù)對(duì)象組成的新的子數(shù)據(jù)集。將這個(gè)新的子數(shù)據(jù)集中的所有m1個(gè)數(shù)值型屬性中的值利用式（5）計(jì)算平均值作為初始點(diǎn)的對(duì)應(yīng)的數(shù)值型屬性的值，對(duì)于分類型屬性的值，則利用2.1節(jié)的分類屬性數(shù)據(jù)處理方法進(jìn)行處理后作為初始值的對(duì)應(yīng)分類型屬性的值。

（3）重復(fù)步驟（2）k次，得到k個(gè)初始點(diǎn)，作為聚類分析的k個(gè)原型點(diǎn)。

2.3 聚類算法描述

改進(jìn)算法的流程和k-prototypes算法的流程基本相同。具體算法描述如下：

（1）將數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)對(duì)象按照2.1節(jié)中的分類屬性數(shù)據(jù)值的處理方法進(jìn)行處理。

（2）利用隨機(jī)分組算法獲得k個(gè)初始原型點(diǎn)，每一個(gè)初始原型點(diǎn)對(duì)應(yīng)一個(gè)聚類原型初值。

（3）將數(shù)據(jù)集中剩下的任一個(gè)對(duì)象分配給一個(gè)聚類，根據(jù)相異度度量的距離公式計(jì)算的結(jié)果確定一個(gè)聚類的原型與它最近，分配給該聚類后，將聚類的原型更新。

（4）在所有的數(shù)據(jù)對(duì)象全部分配給聚類之后，重新計(jì)算該數(shù)據(jù)對(duì)象與當(dāng)前每一個(gè)聚類之間的距離。如果發(fā)現(xiàn)一個(gè)數(shù)據(jù)對(duì)象它的最近原型屬于另一個(gè)聚類而不是當(dāng)前的聚類，將該數(shù)據(jù)對(duì)象重新分配給另一個(gè)聚類并更新兩個(gè)聚類的原型。

（5）重復(fù)算法（4），直到數(shù)據(jù)集中的所有數(shù)據(jù)對(duì)象再?zèng)]有對(duì)象變更聚類為止。

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

一般評(píng)價(jià)聚類結(jié)果均是采用“誤分率”等統(tǒng)計(jì)方法。在本文的仿真實(shí)驗(yàn)中，通過將本文的改進(jìn)算法和kprototypes算法進(jìn)行比較，采用錯(cuò)誤的分類數(shù)目來評(píng)價(jià)聚類算法性能。錯(cuò)誤的分類數(shù)目，即對(duì)算法的聚類結(jié)果和數(shù)據(jù)集本身進(jìn)行比較，聚類結(jié)果中沒有被正確分配到相應(yīng)聚類的數(shù)據(jù)對(duì)象的數(shù)目。本文通過兩個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

（1）采用UCI數(shù)據(jù)集中的abalone數(shù)據(jù)集進(jìn)行測試。該數(shù)據(jù)集包括涉及生活領(lǐng)域的8個(gè)類別的4 177個(gè)數(shù)據(jù)對(duì)象，其中含有1個(gè)分類型屬性，1個(gè)整數(shù)型屬性和6個(gè)實(shí)數(shù)型屬性。分類屬性數(shù)據(jù)對(duì)象中含有1 528個(gè)記錄為F（父）值，1 307個(gè)記錄為M（母）值，還有1 342個(gè)記錄為I（未成年人）值。

如圖1所示，在改變聚類個(gè)數(shù)的情況下，通過比較兩種算法的聚類結(jié)果的錯(cuò)誤分類數(shù)目可知，改進(jìn)算法在一定程度上比原有算法的穩(wěn)定性更高。

（2）采用UCI數(shù)據(jù)集中的post-operative patient數(shù)據(jù)集。該數(shù)據(jù)集中還有涉及生活領(lǐng)域的9個(gè)類別的90個(gè)數(shù)據(jù)對(duì)象，其中還有8個(gè)分類屬性和1個(gè)整數(shù)型屬性，包含有2個(gè)記錄為I（病人送加護(hù)病房），24個(gè)對(duì)象為S（病人準(zhǔn)備回家），64個(gè)對(duì)象為A（病人送去普通病房）。

由圖2可知，在分類屬性較多的混合屬性數(shù)據(jù)集中，改進(jìn)算法的穩(wěn)定性仍在一定程度上優(yōu)于原型算法，保證了改進(jìn)算法對(duì)于混合屬性數(shù)據(jù)聚類結(jié)果的穩(wěn)定性和有效性。

對(duì)于數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)的混合數(shù)值的聚類，目前雖然有一些算法，如k-modes算法和k-prototypes算法。但是這些算法在選擇聚類初始點(diǎn)時(shí)過于隨機(jī)，導(dǎo)致聚類結(jié)果不理想。因此本文提出了一種基于分類屬性數(shù)據(jù)分解的隨機(jī)分組選擇初始原型的改進(jìn)算法。但是在本文的改進(jìn)算法中，仍然存在一些缺點(diǎn)，例如，聚類個(gè)數(shù)仍是人為確定，不能動(dòng)態(tài)確定適合數(shù)據(jù)集合理的聚類的個(gè)數(shù)。因此，為了使改進(jìn)算法的適應(yīng)性和穩(wěn)定性更好，同時(shí)使數(shù)據(jù)集的聚類結(jié)果與輸入數(shù)據(jù)對(duì)象的順序無關(guān)，動(dòng)態(tài)確定聚類合理的聚類個(gè)數(shù)是今后的研究重點(diǎn)。

[1]王欣，徐騰飛，唐連章，等.SQL Server2005數(shù)據(jù)挖掘?qū)嵗治鯷M].北京，中國水利水電出版社，2008.

[2]Han Jiawei，KAMBER M.Dataminingconceptsand techniques[M].北京：機(jī)械工業(yè)出版社，2001.

[3]CHRISTOPHER J，BURGESC.A tutorialonsupport vector machines for pattern recognition[J].Data Mining and knowledge Discovery，1998：2（2）：121-167.

[4]VAPNIK V N.An overview of statistical learning theory[J].IEEE Trans on NeuralNetwork， 1999； 10（5）：988-999.

[5]張文生，王玨.利用支持向量機(jī)構(gòu)造函數(shù)型連接網(wǎng)絡(luò)的研究[J].計(jì)算機(jī)科學(xué)，2001，28（5）：172-177.

[6]趙立江，黃永青.混合屬性數(shù)據(jù)聚類初始點(diǎn)選擇的改進(jìn)[J].廣西師范大學(xué)學(xué)報(bào)：自然科學(xué) 報(bào)，2007，25（4）：102-105.

[7]林培俊，王宇.對(duì)類屬性和混合屬性數(shù)據(jù)聚類的一種有效地算法[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（1）：190-191.

A cluster algorithm of categorical attribute data

Zhang Yanli，Zheng Cheng

（Computer Science and Technical Institute，Anhui University，Hefei 230039，China）

This article proposed a kind of the stochastic grouping improvement method which decomposes based on the attribute，enhances the cluster algorithm the stability and the service ability.The experimental simulation result indicated that，the improvement algorithm has the very good stability and the utility.

clustering；mixed data；categorical attribute

TP301

A

1674-7720（2011）03-0064-03

2010-07-12）

張艷麗，女，1982年生，在讀碩士，主要研究方向：數(shù)據(jù)挖掘，聚類。

鄭誠，男，1964年生，副教授，碩士生導(dǎo)師，主要研究方向：數(shù)據(jù)挖掘，語義 WEB。