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

　所謂聚類，就是將物理或抽象對象的集合構成為由類似的對象組成多個類或簇的過程。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，同一簇中的數(shù)據(jù)對象盡可能相似，不同簇中的數(shù)據(jù)對象盡可能相異[1]。聚類算法在許多領域獲得了廣泛應用[2]，但是，由于在實際應用中，許多數(shù)據(jù)集不僅包含數(shù)值屬性的數(shù)據(jù)，同時也包含如地圖顏色、幾何紋理等分類屬性的數(shù)據(jù)。因此使得基于傳統(tǒng)的歐式距離劃分的聚類算法難以適用于混合屬性數(shù)據(jù)集的要求。為此各研究學者就此問題進行了深入地研究和探討。
　MacQueen所提出的k-means方法[3]是最早、也是最簡單的聚類方法，但是該方法只能對數(shù)值屬性的對象集進行聚類，無法對分類屬性和混合型屬性的對象集進行聚類。Huang提出的k-modes算法和k-prototypes算法[4]推廣了k-means方法，使之可以對分類屬性和混合型屬性的數(shù)據(jù)集進行聚類。同時陳寧、陳安、周龍驤進一步提出了模糊k-prototypes算法，并利用引進模糊聚類算法來提高聚類結果的準確性[5]。
　上述方法在聚類過程中，均利用分類型屬性簡單匹配相異度，將分類型屬性的數(shù)據(jù)轉化為數(shù)值型屬性數(shù)據(jù)間的基于距離的計算問題，從而解決了對混合屬性數(shù)據(jù)集的聚類問題。但是上述方法在對分類屬性數(shù)據(jù)和混合型屬性數(shù)據(jù)進行聚類時，總會存在一些如聚類結果的隨機性和不穩(wěn)定性等缺點，甚至有時會出現(xiàn)空聚類[6-7]現(xiàn)象。
　為此，本文在k-prototypes算法的基礎上進行改進，利用隨機分組的思想動態(tài)地選取初始原型點，同時對分類屬性數(shù)據(jù)采取屬性分解的方法進行處理，從而提高算法的穩(wěn)定性和適用性，使聚類結果更加理想化。
1 相關觀念
　聚類是將數(shù)據(jù)對象分成類或簇的過程，使同一個簇中的對象之間具有很高的相似度，而不同簇中的對象高度相異[2]。其中對象間的相異度度量用來表示對象間的相異程度，代價函數(shù)用來表示對象間的相似程度。


2 算法的改進
　k-modes算法和k-prototypes算法在聚類混合屬性數(shù)據(jù)時，對初值有明顯的依賴，導致聚類結果不理想，甚至出現(xiàn)聚類空集的現(xiàn)象。因此本文在原有算法的基礎上進一步改進，利用隨機分組確定初始原型的方法，然后對隨機分組得到的初始原型進一步加工處理，使得聚類結果對初值的依賴性有所降低，從而使聚類結果更合理、穩(wěn)定，達到改進算法的目的。
2.1 分類屬性處理算法
　假定數(shù)據(jù)對象x是具有m維屬性的數(shù)據(jù)對象，其中含有m1個數(shù)值型數(shù)據(jù)和m2個分類型屬性。那么，可以直觀地將數(shù)據(jù)對象x看成分別有m1維數(shù)值屬性和m2維分類屬性組成，其中m2維分類屬性又可以分別看成由多維數(shù)據(jù)值組成。例如：表2中的分類型屬性“渠道”可以看成是由“直接”、“間接”2維分類數(shù)據(jù)值組成的；分類型屬性“語義范疇”可以看成是由“植物”、“語言”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(語言)}}；
　則對象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)計算對象與聚類之間的距離，得到其中的最小距離。通過這種方式，可以有效地避免在分類屬性中出現(xiàn)頻率少的屬性值丟失的現(xiàn)象，從而得到更合理的聚類的結果。
2.2 隨機分組算法
　隨機分組算法的基本原理是依據(jù)需要聚類的個數(shù)k和數(shù)據(jù)集中所包含數(shù)據(jù)的個數(shù)n。將總數(shù)為n的數(shù)據(jù)集劃分為count=n/k組，然后從count組中分別選擇數(shù)據(jù)對象k次，構成k個聚類的初始原型值。
算法流程：
　(1)分組數(shù)據(jù)集。已知數(shù)據(jù)集X={x1，x2，…，xn}是包含n個數(shù)據(jù)對象的集合。依據(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)計算平均值作為初始點的對應的數(shù)值型屬性的值，對于分類型屬性的值，則利用2.1節(jié)的分類屬性數(shù)據(jù)處理方法進行處理后作為初始值的對應分類型屬性的值。
　3)重復步驟(2)k次，得到k個初始點，作為聚類分析的k個原型點。
2.3 聚類算法描述
　改進算法的流程和k-prototypes算法的流程基本相同。具體算法描述如下：
　(1)將數(shù)據(jù)集中的每一個數(shù)據(jù)對象按照2.1節(jié)中的分類屬性數(shù)據(jù)值的處理方法進行處理。
　(2)利用隨機分組算法獲得k個初始原型點，每一個初始原型點對應一個聚類原型初值。
　(3)將數(shù)據(jù)集中剩下的任一個對象分配給一個聚類，根據(jù)相異度度量的距離公式計算的結果確定一個聚類的原型與它最近，分配給該聚類后，將聚類的原型更新。
　4)在所有的數(shù)據(jù)對象全部分配給聚類之后，重新計算該數(shù)據(jù)對象與當前每一個聚類之間的距離。如果發(fā)現(xiàn)一個數(shù)據(jù)對象它的最近原型屬于另一個聚類而不是當前的聚類，將該數(shù)據(jù)對象重新分配給另一個聚類并更新兩個聚類的原型。
　(5)重復算法(4)，直到數(shù)據(jù)集中的所有數(shù)據(jù)對象再沒有對象變更聚類為止。
3 實驗分析
　一般評價聚類結果均是采用“誤分率”等統(tǒng)計方法。在本文的仿真實驗中，通過將本文的改進算法和k-prototypes算法進行比較，采用錯誤的分類數(shù)目來評價聚類算法性能。錯誤的分類數(shù)目，即對算法的聚類結果和數(shù)據(jù)集本身進行比較，聚類結果中沒有被正確分配到相應聚類的數(shù)據(jù)對象的數(shù)目。本文通過兩個數(shù)據(jù)集進行實驗。
　(1)采用UCI數(shù)據(jù)集中的abalone數(shù)據(jù)集進行測試。該數(shù)據(jù)集包括涉及生活領域的8個類別的4 177個數(shù)據(jù)對象，其中含有1個分類型屬性，1個整數(shù)型屬性和6個實數(shù)型屬性。分類屬性數(shù)據(jù)對象中含有1 528個記錄為F(父)值，1 307個記錄為M(母)值，還有1 342個記錄為I(未成年人)值。
如圖1所示，在改變聚類個數(shù)的情況下，通過比較兩種算法的聚類結果的錯誤分類數(shù)目可知，改進算法在一定程度上比原有算法的穩(wěn)定性更高。

　(2)采用UCI數(shù)據(jù)集中的post-operative patient數(shù)據(jù)集。該數(shù)據(jù)集中還有涉及生活領域的9個類別的90個數(shù)據(jù)對象，其中還有8個分類屬性和1個整數(shù)型屬性，包含有2個記錄為I(病人送加護病房)，24個對象為S(病人準備回家)，64個對象為A(病人送去普通病房)。
　由圖2可知，在分類屬性較多的混合屬性數(shù)據(jù)集中，改進算法的穩(wěn)定性仍在一定程度上優(yōu)于原型算法，保證了改進算法對于混合屬性數(shù)據(jù)聚類結果的穩(wěn)定性和有效性。

　對于數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)的混合數(shù)值的聚類，目前雖然有一些算法，如k-modes算法和k-prototypes算法。但是這些算法在選擇聚類初始點時過于隨機，導致聚類結果不理想。因此本文提出了一種基于分類屬性數(shù)據(jù)分解的隨機分組選擇初始原型的改進算法。但是在本文的改進算法中，仍然存在一些缺點，例如，聚類個數(shù)仍是人為確定，不能動態(tài)確定適合數(shù)據(jù)集合理的聚類的個數(shù)。因此，為了使改進算法的適應性和穩(wěn)定性更好，同時使數(shù)據(jù)集的聚類結果與輸入數(shù)據(jù)對象的順序無關，動態(tài)確定聚類合理的聚類個數(shù)是今后的研究重點。
參考文獻
[1] 王欣，徐騰飛，唐連章，等.SQL Server2005數(shù)據(jù)挖掘實例分析[M].北京，中國水利水電出版社，2008.
[2] Han Jiawei， KAMBER M. Data mining concepts and techniques[M]. 北京：機械工業(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] 張文生，王玨.利用支持向量機構造函數(shù)型連接網(wǎng)絡的研究[J].計算機科學，2001，28(5)：172-177.
[6] 趙立江，黃永青.混合屬性數(shù)據(jù)聚類初始點選擇的改進[J].廣西師范大學學報：自然科學報，2007，25(4)：102-105.
[7] 林培俊，王宇.對類屬性和混合屬性數(shù)據(jù)聚類的一種有效地算法[J].計算機工程與應用，2004，40(1)：190-191.