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

　所謂聚類，就是將物理或抽象對象的集合構(gòu)成為由類似的對象組成多個(gè)類或簇的過程。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，同一簇中的數(shù)據(jù)對象盡可能相似，不同簇中的數(shù)據(jù)對象盡可能相異[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]是最早、也是最簡單的聚類方法，但是該方法只能對數(shù)值屬性的對象集進(jìn)行聚類，無法對分類屬性和混合型屬性的對象集進(jìn)行聚類。Huang提出的k-modes算法和k-prototypes算法[4]推廣了k-means方法，使之可以對分類屬性和混合型屬性的數(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ì)算問題，從而解決了對混合屬性數(shù)據(jù)集的聚類問題。但是上述方法在對分類屬性數(shù)據(jù)和混合型屬性數(shù)據(jù)進(jìn)行聚類時(shí)，總會存在一些如聚類結(jié)果的隨機(jī)性和不穩(wěn)定性等缺點(diǎn)，甚至有時(shí)會出現(xiàn)空聚類[6-7]現(xiàn)象。
　為此，本文在k-prototypes算法的基礎(chǔ)上進(jìn)行改進(jìn)，利用隨機(jī)分組的思想動(dòng)態(tài)地選取初始原型點(diǎn)，同時(shí)對分類屬性數(shù)據(jù)采取屬性分解的方法進(jìn)行處理，從而提高算法的穩(wěn)定性和適用性，使聚類結(jié)果更加理想化。
1 相關(guān)觀念
　聚類是將數(shù)據(jù)對象分成類或簇的過程，使同一個(gè)簇中的對象之間具有很高的相似度，而不同簇中的對象高度相異[2]。其中對象間的相異度度量用來表示對象間的相異程度，代價(jià)函數(shù)用來表示對象間的相似程度。


2 算法的改進(jìn)
　k-modes算法和k-prototypes算法在聚類混合屬性數(shù)據(jù)時(shí)，對初值有明顯的依賴，導(dǎo)致聚類結(jié)果不理想，甚至出現(xiàn)聚類空集的現(xiàn)象。因此本文在原有算法的基礎(chǔ)上進(jìn)一步改進(jìn)，利用隨機(jī)分組確定初始原型的方法，然后對隨機(jī)分組得到的初始原型進(jìn)一步加工處理，使得聚類結(jié)果對初值的依賴性有所降低，從而使聚類結(jié)果更合理、穩(wěn)定，達(dá)到改進(jìn)算法的目的。
2.1 分類屬性處理算法
　假定數(shù)據(jù)對象x是具有m維屬性的數(shù)據(jù)對象，其中含有m1個(gè)數(shù)值型數(shù)據(jù)和m2個(gè)分類型屬性。那么，可以直觀地將數(shù)據(jù)對象x看成分別有m1維數(shù)值屬性和m2維分類屬性組成，其中m2維分類屬性又可以分別看成由多維數(shù)據(jù)值組成。例如：表2中的分類型屬性“渠道”可以看成是由“直接”、“間接”2維分類數(shù)據(jù)值組成的；分類型屬性“語義范疇”可以看成是由“植物”、“語言”2維分類數(shù)據(jù)組成的。在計(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(語言)}}；
　則對象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)計(jì)算對象與聚類之間的距離，得到其中的最小距離。通過這種方式，可以有效地避免在分類屬性中出現(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ù)對象k次，構(gòu)成k個(gè)聚類的初始原型值。
算法流程：
　(1)分組數(shù)據(jù)集。已知數(shù)據(jù)集X={x1，x2，…，xn}是包含n個(gè)數(shù)據(jù)對象的集合。依據(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ù)集中還有剩余的對象未分配，則將剩余的對象分配到任意組中，本文選擇將其分配到第一個(gè)分組中。
　(2)隨機(jī)獲得一個(gè)初始點(diǎn)。將數(shù)據(jù)集分組成為子數(shù)據(jù)集后，依次從count個(gè)子數(shù)據(jù)集中隨機(jī)選擇一個(gè)數(shù)據(jù)對象，形成由count個(gè)數(shù)據(jù)對象組成的新的子數(shù)據(jù)集。將這個(gè)新的子數(shù)據(jù)集中的所有m1個(gè)數(shù)值型屬性中的值利用式(5)計(jì)算平均值作為初始點(diǎn)的對應(yīng)的數(shù)值型屬性的值，對于分類型屬性的值，則利用2.1節(jié)的分類屬性數(shù)據(jù)處理方法進(jìn)行處理后作為初始值的對應(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ù)對象按照2.1節(jié)中的分類屬性數(shù)據(jù)值的處理方法進(jìn)行處理。
　(2)利用隨機(jī)分組算法獲得k個(gè)初始原型點(diǎn)，每一個(gè)初始原型點(diǎn)對應(yīng)一個(gè)聚類原型初值。
　(3)將數(shù)據(jù)集中剩下的任一個(gè)對象分配給一個(gè)聚類，根據(jù)相異度度量的距離公式計(jì)算的結(jié)果確定一個(gè)聚類的原型與它最近，分配給該聚類后，將聚類的原型更新。
　4)在所有的數(shù)據(jù)對象全部分配給聚類之后，重新計(jì)算該數(shù)據(jù)對象與當(dāng)前每一個(gè)聚類之間的距離。如果發(fā)現(xiàn)一個(gè)數(shù)據(jù)對象它的最近原型屬于另一個(gè)聚類而不是當(dāng)前的聚類，將該數(shù)據(jù)對象重新分配給另一個(gè)聚類并更新兩個(gè)聚類的原型。
　(5)重復(fù)算法(4)，直到數(shù)據(jù)集中的所有數(shù)據(jù)對象再沒有對象變更聚類為止。
3 實(shí)驗(yàn)分析
　一般評價(jià)聚類結(jié)果均是采用“誤分率”等統(tǒng)計(jì)方法。在本文的仿真實(shí)驗(yàn)中，通過將本文的改進(jìn)算法和k-prototypes算法進(jìn)行比較，采用錯(cuò)誤的分類數(shù)目來評價(jià)聚類算法性能。錯(cuò)誤的分類數(shù)目，即對算法的聚類結(jié)果和數(shù)據(jù)集本身進(jìn)行比較，聚類結(jié)果中沒有被正確分配到相應(yīng)聚類的數(shù)據(jù)對象的數(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ù)對象，其中含有1個(gè)分類型屬性，1個(gè)整數(shù)型屬性和6個(gè)實(shí)數(shù)型屬性。分類屬性數(shù)據(jù)對象中含有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ù)對象，其中還有8個(gè)分類屬性和1個(gè)整數(shù)型屬性，包含有2個(gè)記錄為I(病人送加護(hù)病房)，24個(gè)對象為S(病人準(zhǔn)備回家)，64個(gè)對象為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算法。但是這些算法在選擇聚類初始點(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ù)對象的順序無關(guān)，動(dòng)態(tài)確定聚類合理的聚類個(gè)數(shù)是今后的研究重點(diǎn)。
參考文獻(xiàn)
[1] 王欣，徐騰飛，唐連章，等.SQL Server2005數(shù)據(jù)挖掘?qū)嵗治鯷M].北京，中國水利水電出版社，2008.
[2] Han Jiawei， KAMBER M. Data mining concepts and techniques[M]. 北京：機(jī)械工業(yè)出版社，2001.
[3] CHRISTOPHER J， BURGES C. A tutorial on support 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 Neural Network， 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] 林培俊，王宇.對類屬性和混合屬性數(shù)據(jù)聚類的一種有效地算法[J].計(jì)算機(jī)工程與應(yīng)用，2004，40(1)：190-191.