1、種混合屬性數(shù)據(jù)的聚類算法摘 要：提出一種基于屬性分解的隨機分組的改進(jìn)方法，以提高聚類算法的穩(wěn)定性和適用 性。實驗仿真結(jié)果表明，改進(jìn)算法具有很好的穩(wěn)定性和應(yīng)用性。關(guān)鍵詞：聚類；混合數(shù)據(jù)；分類屬性所謂聚類，就是將物理或抽象對象的集合構(gòu)成為由類似的對象組成多個類或簇的過程。由 聚類所生成的簇是一組數(shù)據(jù)對象的集合，同一簇中的數(shù)據(jù)對象盡可能相似，不同簇中的數(shù)據(jù) 對象盡可能相異1。聚類算法在許多領(lǐng)域獲得了廣泛應(yīng)用2，但是，由于在實際應(yīng)用中， 許多數(shù)據(jù)集不僅包含數(shù)值屬性的數(shù)據(jù)，同時也包含如地圖顏色、幾何紋理等分類屬性的數(shù)據(jù)。 因此使得基于傳統(tǒng)的歐式距離劃分的聚類算法難以適用于混合屬性數(shù)據(jù)集的要求。為此各研

2、究學(xué)者就此問題進(jìn)行了深入地研究和探討。MacQueen所提出的k-means方法3是最早、也是最簡單的聚類方法，但是該方法只能 對數(shù)值屬性的對象集進(jìn)行聚類，無法對分類屬性和混合型屬性的對象集進(jìn)行聚類。Huang 提出的k-modes算法和k-prototypes算法4推廣了 k-means方法，使之可以對分類屬性和 混合型屬性的數(shù)據(jù)集進(jìn)行聚類。同時陳寧、陳安、周龍驤進(jìn)一步提出了模糊k-prototypes 算法，并利用引進(jìn)模糊聚類算法來提高聚類結(jié)果的準(zhǔn)確性5。上述方法在聚類過程中，均利用分類型屬性簡單匹配相異度，將分類型屬性的數(shù)據(jù)轉(zhuǎn)化為 數(shù)值型屬性數(shù)據(jù)間的基于距離的計算問題，從而解決了對混合屬

3、性數(shù)據(jù)集的聚類問題。但是 上述方法在對分類屬性數(shù)據(jù)和混合型屬性數(shù)據(jù)進(jìn)行聚類時，總會存在一些如聚類結(jié)果的隨機 性和不穩(wěn)定性等缺點，甚至有時會出現(xiàn)空聚類6-7 現(xiàn)象。為此，本文在k-prototypes算法的基礎(chǔ)上進(jìn)行改進(jìn)，利用隨機分組的思想動態(tài)地選取初 始原型點，同時對分類屬性數(shù)據(jù)采取屬性分解的方法進(jìn)行處理，從而提高算法的穩(wěn)定性和適 用性，使聚類結(jié)果更加理想化。1相關(guān)觀念聚類是將數(shù)據(jù)對象分成類或簇的過程，使同一個簇中的對象之間具有很高的相似度，而不 同簇中的對象高度相異2。其中對象間的相異度度量用來表示對象間的相異程度，代價函 數(shù)用來表示對象間的相似程度。1J相異度度量對象的相異度定義為對象中不

4、相等的分類屬性值的數(shù)目。設(shè)X是數(shù)據(jù)集中兩個包含E種分類底性的數(shù)據(jù)對象.也可以說U是數(shù)據(jù)集中任意兩個具有.壇)維分類屬性值的數(shù)據(jù)對象.對象間的相異度邱定義為：日打)二 (I)富的A如果巧或者械缺失(即對象，或?qū)ο?沒有變量/的度 量值)，或者=0.且變雖/是非對稱的二元變量，則 指示項8?=0 ；否則.指示項為了方便計算，假定 每一個屬性中的全部屬性值以同等概率出現(xiàn).即式(1)中的指示項由此得到簡化的相異度公式為：d(X,y)Z 園坦&(和力)(2)其中，當(dāng)?shù)?方時3(* ,力)=0 ；當(dāng)Xj供*時，3(初:)= I O 町,flyj 是數(shù)據(jù)集中屬性/所包含屬性值 5 的個數(shù)，舉例如表 1所示。

5、表1舉例所用數(shù)據(jù)對象時間渠道范疇1間接植物宜接語言33宜接語言43間接植物5r直接語言根據(jù)公式計算:d(l,2)=2+2=4；d(l ,4)=0；d(l,3)= 2 + 2=4 ；/(!,5)=2 + 2=4o該公式說明兩個對象不相等的分類屬性值的數(shù)目 越大，則兩個對象越不相似。由此可以得出，計算數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)的混 合數(shù)據(jù)的相異度度量的距離為：d(x，X)= ；】(*廠力)2+2二.0(號,方)1.2代價函數(shù)的計算代價函數(shù)用來表示對象間的相似程度，擴展k- means算法代價函數(shù)的計算方法，使其可以計算數(shù)值型 數(shù)據(jù)和分類型混合屬性數(shù)據(jù)對象的代價函數(shù)。定義X 是具有m種屬性值總數(shù)為的對象

6、的數(shù)據(jù)集，即乂 = XM,，XJ,Xi=(%5,土),其中包含皿個數(shù)值 型的數(shù)據(jù).皿個分類型的數(shù)據(jù),m=ml + m2.A-是正整數(shù)， 表示聚類的個數(shù)。則代價函數(shù)的計算總公式為：E=L ：Qd(Xj,QJ(4)其中，0戶伽.如，q異是聚類【的模式或者原型，是 劃分矩陣Kx中的任意一個元素，/表示相似度雖值。 在該公式中，丫有以下兩個特性：0矽聲1：5=1，本文中取 ye(O.I)在式(4)中，針對于混合屬性的數(shù)據(jù).引用了混合屬 性數(shù)據(jù)中的數(shù)值屬性數(shù)據(jù)和分類屬性數(shù)據(jù)的計算相異 度的式(3),得到總的代價函數(shù)公式為：2算法的改進(jìn)k-modes算法和k-prototypes算法在聚類混合屬性數(shù)據(jù)時，

7、對初值有明顯的依賴，導(dǎo)致 聚類結(jié)果不理想，甚至出現(xiàn)聚類空集的現(xiàn)象。因此本文在原有算法的基礎(chǔ)上進(jìn)一步改進(jìn)，利 用隨機分組確定初始原型的方法，然后對隨機分組得到的初始原型進(jìn)一步加工處理，使得聚 類結(jié)果對初值的依賴性有所降低，從而使聚類結(jié)果更合理、穩(wěn)定，達(dá)到改進(jìn)算法的目的。 2.1分類屬性處理算法假定數(shù)據(jù)對象x是具有m維屬性的數(shù)據(jù)對象，其中含有ml個數(shù)值型數(shù)據(jù)和m2個分類 型屬性。那么，可以直觀地將數(shù)據(jù)對象x看成分別有ml維數(shù)值屬性和m2維分類屬性組成， 其中m2維分類屬性又可以分別看成由多維數(shù)據(jù)值組成。例如：表2中的分類型屬性渠道 可以看成是由直接”、間接”2維分類數(shù)據(jù)值組成的;分類型屬性語義范疇

8、可以看成是由植 物、語言2維分類數(shù)據(jù)組成的。在計算中，分別將分類型屬性看成是由多維的分類屬性數(shù) 據(jù)值組成的。對象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（語言）；貝0對象1，2, 5組成的聚類Q1的分解原型可以表示為：Q1=2，2/3（直接），1/3（間接）

9、，0（植物），3/3（語言）；則對象3, 4組成的聚類Q2的分解原型可以表示為：Q2=2，1/2（直接），1/2（間接），2/2（植物），0（語言）；然后利用式（2）計算對象與聚類之間的距離，得到其中的最小距離。通過這種方式，可以 有效地避免在分類屬性中出現(xiàn)頻率少的屬性值丟失的現(xiàn)象，從而得到更合理的聚類的結(jié)果。 2.2隨機分組算法隨機分組算法的基本原理是依據(jù)需要聚類的個數(shù)k和數(shù)據(jù)集中所包含數(shù)據(jù)的個數(shù)n。將總 數(shù)為n的數(shù)據(jù)集劃分為count=n/k組，然后從count組中分別選擇數(shù)據(jù)對象k次，構(gòu)成k 個聚類的初始原型值。算法流程：（1）分組數(shù)據(jù)集。已知數(shù)據(jù)集X=x1，x2，xn是包含n個數(shù)據(jù)對象

10、的集合。依據(jù)數(shù)據(jù) 集中數(shù)據(jù)個數(shù)n和需要聚類的個數(shù)k，將整個數(shù)據(jù)集分組成為count=n/k組，即數(shù)據(jù)集 X=x1，x2，xk，xk+1，x2k，。如果分組后數(shù)據(jù)集中還有剩余的對象未分 配，則將剩余的對象分配到任意組中，本文選擇將其分配到第一個分組中。（2）隨機獲得一個初始點。將數(shù)據(jù)集分組成為子數(shù)據(jù)集后，依次從count個子數(shù)據(jù)集中隨 機選擇一個數(shù)據(jù)對象，形成由count個數(shù)據(jù)對象組成的新的子數(shù)據(jù)集。將這個新的子數(shù)據(jù)集 中的所有m1個數(shù)值型屬性中的值利用式（5）計算平均值作為初始點的對應(yīng)的數(shù)值型屬性的 值，對于分類型屬性的值，則利用2.1節(jié)的分類屬性數(shù)據(jù)處理方法進(jìn)行處理后作為初始值的 對應(yīng)分類型

11、屬性的值。3)重復(fù)步驟(2)k次，得到k個初始點，作為聚類分析的k個原型點。2.3聚類算法描述改進(jìn)算法的流程和k-prototypes算法的流程基本相同。具體算法描述如下：將數(shù)據(jù)集中的每一個數(shù)據(jù)對象按照2.1節(jié)中的分類屬性數(shù)據(jù)值的處理方法進(jìn)行處理。利用隨機分組算法獲得k個初始原型點，每一個初始原型點對應(yīng)一個聚類原型初值。將數(shù)據(jù)集中剩下的任一個對象分配給一個聚類，根據(jù)相異度度量的距離公式計算的結(jié) 果確定一個聚類的原型與它最近，分配給該聚類后，將聚類的原型更新。4)在所有的數(shù)據(jù)對象全部分配給聚類之后，重新計算該數(shù)據(jù)對象與當(dāng)前每一個聚類之間的 距離。如果發(fā)現(xiàn)一個數(shù)據(jù)對象它的最近原型屬于另一個聚類而不

12、是當(dāng)前的聚類，將該數(shù)據(jù)對 象重新分配給另一個聚類并更新兩個聚類的原型。重復(fù)算法(4)，直到數(shù)據(jù)集中的所有數(shù)據(jù)對象再沒有對象變更聚類為止。3實驗分析一般評價聚類結(jié)果均是采用誤分率等統(tǒng)計方法。在本文的仿真實驗中，通過將本文的改 進(jìn)算法和k-prototypes算法進(jìn)行比較，采用錯誤的分類數(shù)目來評價聚類算法性能。錯誤的 分類數(shù)目，即對算法的聚類結(jié)果和數(shù)據(jù)集本身進(jìn)行比較，聚類結(jié)果中沒有被正確分配到相應(yīng) 聚類的數(shù)據(jù)對象的數(shù)目。本文通過兩個數(shù)據(jù)集進(jìn)行實驗。(1)采用UCI數(shù)據(jù)集中的abalone數(shù)據(jù)集進(jìn)行測試。該數(shù)據(jù)集包括涉及生活領(lǐng)域的8個類 別的4 177個數(shù)據(jù)對象，其中含有1個分類型屬性，1個整數(shù)型屬

13、性和6個實數(shù)型屬性。分 類屬性數(shù)據(jù)對象中含有1 528個記錄為F(父)值，1 307個記錄為M(母)值，還有1 342個 記錄為【(未成年人)值。如圖1所示，在改變聚類個數(shù)的情況下，通過比較兩種算法的聚類結(jié)果的錯誤分類數(shù)目可知， 改進(jìn)算法在一定程度上比原有算法的穩(wěn)定性更高。數(shù)據(jù)器炒商改避算法u k.-pm tot ypw 算袱數(shù)據(jù)器炒商改避算法u k.-pm tot ypw 算袱hz彰將企爪茹(2)米用UCI數(shù)據(jù)集中的post-operative patient數(shù)據(jù)集。該數(shù)據(jù)集中還有涉及生活領(lǐng)域的 9個類別的90個數(shù)據(jù)對象，其中還有8個分類屬性和1個整數(shù)型屬性，包含有2個記錄為 1(病人送加護(hù)

14、病房)，24個對象為S(病人準(zhǔn)備回家)，64個對象為A(病人送去普通病房)。由圖2可知，在分類屬性較多的混合屬性數(shù)據(jù)集中，改進(jìn)算法的穩(wěn)定性仍在一定程度上優(yōu) 于原型算法，保證了改進(jìn)算法對于混合屬性數(shù)據(jù)聚類結(jié)果的穩(wěn)定性和有效性。對于數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)的混合數(shù)值的聚類，目前雖然有一些算法，如k-modes算 法和k-prototypes算法。但是這些算法在選擇聚類初始點時過于隨機，導(dǎo)致聚類結(jié)果不理 想。因此本文提出了一種基于分類屬性數(shù)據(jù)分解的隨機分組選擇初始原型的改進(jìn)算法。但是 在本文的改進(jìn)算法中，仍然存在一些缺點，例如，聚類個數(shù)仍是人為確定，不能動態(tài)確定適 合數(shù)據(jù)集合理的聚類的個數(shù)。因此，為了

15、使改進(jìn)算法的適應(yīng)性和穩(wěn)定性更好，同時使數(shù)據(jù)集 的聚類結(jié)果與輸入數(shù)據(jù)對象的順序無關(guān)，動態(tài)確定聚類合理的聚類個數(shù)是今后的研究重點。參考文獻(xiàn)王欣，徐騰飛，唐連章，等.SQL Server2005數(shù)據(jù)挖掘?qū)嵗治鯩.北京，中國水利水 電出版社，2008.Han Jiawei， KAMBER M. Data mining concepts and techniquesM.北京：機械工業(yè) 出版社，2001.CHRISTOPHER J，BURGES C. A tutorial on support vector machines for pattern recognitionJ. Data Mining and knowledge Discovery， 1998： 2(2): 121-167.VAPNIK V N. An overview of statistical learn