一種混合屬性數據的聚類算法

張艷麗，鄭 誠

（安徽大學 計算機科學與技術學院，安徽 合肥 230039）

一種混合屬性數據的聚類算法

張艷麗，鄭 誠

（安徽大學 計算機科學與技術學院，安徽 合肥 230039）

提出一種基于屬性分解的隨機分組的改進方法，以提高聚類算法的穩定性和適用性。實驗仿真結果表明，改進算法具有很好的穩定性和應用性。

聚類；混合數據；分類屬性

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

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

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

為此，本文在k-prototypes算法的基礎上進行改進，利用隨機分組的思想動態地選取初始原型點，同時對分類屬性數據采取屬性分解的方法進行處理，從而提高算法的穩定性和適用性，使聚類結果更加理想化。

1 相關觀念

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

1.1 相異度度量

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

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

其中，當xj=yj時，δ（x，yj）=0；當 xj≠yj時 ，δ（xj，yj）=1。 nxj，nyj是數據集中屬性j所包含屬性值xj，yj的個數，舉例如表1所示。

表1 舉例所用數據

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

該公式說明兩個對象不相等的分類屬性值的數目越大，則兩個對象越不相似。

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

1.2 代價函數的計算

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

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

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

2 算法的改進

k-modes算法和k-prototypes算法在聚類混合屬性數據時，對初值有明顯的依賴，導致聚類結果不理想，甚至出現聚類空集的現象。因此本文在原有算法的基礎上進一步改進，利用隨機分組確定初始原型的方法，然后對隨機分組得到的初始原型進一步加工處理，使得聚類結果對初值的依賴性有所降低，從而使聚類結果更合理、穩定，達到改進算法的目的。

2.1 分類屬性處理算法

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

表2 屬性分解原型舉例

對象1的分解原型表示為：

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

對象2的分解原型表示為：

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

對象3的分解原型表示為：

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

對象4的分解原型表示為：

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

對象5的原型表示為：

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

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

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

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

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

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

2.2 隨機分組算法

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

算法流程：

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

（2）隨機獲得一個初始點。將數據集分組成為子數據集后，依次從count個子數據集中隨機選擇一個數據對象，形成由count個數據對象組成的新的子數據集。將這個新的子數據集中的所有m1個數值型屬性中的值利用式（5）計算平均值作為初始點的對應的數值型屬性的值，對于分類型屬性的值，則利用2.1節的分類屬性數據處理方法進行處理后作為初始值的對應分類型屬性的值。

（3）重復步驟（2）k次，得到k個初始點，作為聚類分析的k個原型點。

2.3 聚類算法描述

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

（1）將數據集中的每一個數據對象按照2.1節中的分類屬性數據值的處理方法進行處理。

（2）利用隨機分組算法獲得k個初始原型點，每一個初始原型點對應一個聚類原型初值。

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

（4）在所有的數據對象全部分配給聚類之后，重新計算該數據對象與當前每一個聚類之間的距離。如果發現一個數據對象它的最近原型屬于另一個聚類而不是當前的聚類，將該數據對象重新分配給另一個聚類并更新兩個聚類的原型。

（5）重復算法（4），直到數據集中的所有數據對象再沒有對象變更聚類為止。

3 實驗分析

一般評價聚類結果均是采用“誤分率”等統計方法。在本文的仿真實驗中，通過將本文的改進算法和kprototypes算法進行比較，采用錯誤的分類數目來評價聚類算法性能。錯誤的分類數目，即對算法的聚類結果和數據集本身進行比較，聚類結果中沒有被正確分配到相應聚類的數據對象的數目。本文通過兩個數據集進行實驗。

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

如圖1所示，在改變聚類個數的情況下，通過比較兩種算法的聚類結果的錯誤分類數目可知，改進算法在一定程度上比原有算法的穩定性更高。

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

由圖2可知，在分類屬性較多的混合屬性數據集中，改進算法的穩定性仍在一定程度上優于原型算法，保證了改進算法對于混合屬性數據聚類結果的穩定性和有效性。

對于數值型數據和分類型數據的混合數值的聚類，目前雖然有一些算法，如k-modes算法和k-prototypes算法。但是這些算法在選擇聚類初始點時過于隨機，導致聚類結果不理想。因此本文提出了一種基于分類屬性數據分解的隨機分組選擇初始原型的改進算法。但是在本文的改進算法中，仍然存在一些缺點，例如，聚類個數仍是人為確定，不能動態確定適合數據集合理的聚類的個數。因此，為了使改進算法的適應性和穩定性更好，同時使數據集的聚類結果與輸入數據對象的順序無關，動態確定聚類合理的聚類個數是今后的研究重點。

[1]王欣，徐騰飛，唐連章，等.SQL Server2005數據挖掘實例分析[M].北京，中國水利水電出版社，2008.

[2]Han Jiawei，KAMBER M.Dataminingconceptsand techniques[M].北京：機械工業出版社，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].計算機科學，2001，28（5）：172-177.

[6]趙立江，黃永青.混合屬性數據聚類初始點選擇的改進[J].廣西師范大學學報：自然科學 報，2007，25（4）：102-105.

[7]林培俊，王宇.對類屬性和混合屬性數據聚類的一種有效地算法[J].計算機工程與應用，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年生，在讀碩士，主要研究方向：數據挖掘，聚類。

鄭誠，男，1964年生，副教授，碩士生導師，主要研究方向：數據挖掘，語義 WEB。