石鴻雁， 徐明明

(沈陽工業(yè)大學(xué) 理學(xué)院， 沈陽 110870)

聚類是將物理或者抽象的對象集合分成若干個類，使得同一個類中的對象具有較高相似度，不同類中的對象具有較低相似度[1]，聚類分析技術(shù)在圖像處理、模式識別、生物學(xué)等諸多領(lǐng)域有著廣泛的應(yīng)用[2-4].在實際生活中的各個方面比如醫(yī)療衛(wèi)生教育、社交網(wǎng)站、商場和購物網(wǎng)站等領(lǐng)域每時每刻都會產(chǎn)生大量的數(shù)據(jù)，這些數(shù)據(jù)大多是由連續(xù)的數(shù)值屬性和代表類別的分類屬性所構(gòu)成的混合屬性數(shù)據(jù)，所以混合屬性數(shù)據(jù)聚類算法的研究成為聚類分析領(lǐng)域的一個熱點問題.目前，許多學(xué)者對混合屬性數(shù)據(jù)聚類進行研究，并提出了一些相關(guān)算法.Huang結(jié)合k-means和k-modes算法的思想提出了k-prototypes算法[5]，該算法實現(xiàn)簡單，易操作，能夠有效聚類混合數(shù)據(jù)，但其對初始聚類中心和聚類數(shù)目過于依賴，使得聚類結(jié)果容易陷入局部最優(yōu)，并且在計算分類屬性之間的相異度時，簡單采用數(shù)值0和1不能客觀地體現(xiàn)數(shù)據(jù)對象與類之間的相異度，從而導(dǎo)致聚類結(jié)果不理想.針對k-prototypes算法存在的問題，歐陽浩等提出了基于信息熵的粗糙k-prototypes聚類算法[6]，利用信息熵的概念，為每個數(shù)據(jù)對象的分類屬性賦予權(quán)重，并且引入粗糙集的理論來計算各數(shù)據(jù)對象與粗糙中心之間的差異度，提高了聚類結(jié)果的準(zhǔn)確率.Chatzis提出了一種新的FCM算法[7]，對Gath-Geva算法進行了擴展，該算法假設(shè)簇中的數(shù)據(jù)對象符合高斯分布，主要對高斯多項分布數(shù)據(jù)進行聚類.Zheng等利用進化算法(EA)具有全局搜索能力的特點，將其引入到k-prototypes算法中，提出EKP算法[8]，算法中令k-prototypes算法作為局部搜索策略，并在EA框架的控制下運行.錢潮愷等[9]針對k-prototypes算法分辨率低，聚類結(jié)果的隨機性較大等問題，提出基于維度頻率相異度的方法來計算分類屬性，并且對預(yù)聚類產(chǎn)生的子簇構(gòu)造連通圖，分析其之間的連通關(guān)系，用強連通融合方法進行聚類.陳晉音等提出了基于混合屬性距離度量公式的密度聚類算法[10]，將數(shù)據(jù)對象分為分類占優(yōu)、數(shù)值占優(yōu)和均衡型，對于不同情況的特征，分別選擇不同的距離度量方式，通過預(yù)先設(shè)定的參數(shù)尋找數(shù)據(jù)密度最大的區(qū)域，選定核心點，再根據(jù)核心點將密度相連的數(shù)據(jù)對象劃分為一類，最后得到聚類結(jié)果.

上述處理混合屬性數(shù)據(jù)的算法雖然在不同程度上提高了聚類效果，但大都采取了隨機選擇初始聚類中心的方式，給算法的執(zhí)行效率帶來了很大的不確定性[11].為了解決這個問題，已有學(xué)者提出一些改進算法，文獻[12]在考慮數(shù)據(jù)對象在類歸屬上不確定的同時，利用均值和分布質(zhì)心表示類中心；文獻[13]提出了基于密度聚類中心自動確定的聚類算法.實際上，聚類中心點的分布比較疏散，不會局限在一個小的范圍區(qū)域內(nèi).本文利用平均差異度方法選取初始聚類中心點，并用這些點進行聚類，可以得到較好的效果.為進一步提高算法質(zhì)量，利用信息熵確定數(shù)值屬性權(quán)重，并對分類屬性度量公式進行改進，給出了一種混合屬性數(shù)據(jù)度量公式.

1 k-prototypes聚類算法

設(shè)k∈N+，k-prototypes算法聚類是將數(shù)據(jù)集劃分成k個不同的類，使得目標(biāo)函數(shù)值最小，即

(1)

式中：vl為類cl的聚類中心，cl為聚類集；μil為數(shù)據(jù)對象xi對類cl的隸屬度，0≤μil≤1；d(xi，vl)為混合屬性數(shù)據(jù)度量公式，即

(2)

1) 在數(shù)據(jù)集中任選k個初始聚類中心點；

2) 根據(jù)式(2)計算對象與初始聚類中心的距離，按照最小距離原則分到離其最近的中心所在的類中；

3) 更新聚類中心，對數(shù)值屬性數(shù)據(jù)求平均值，對分類屬性數(shù)據(jù)求屬性中出現(xiàn)次數(shù)最多的值；

4) 重復(fù)步驟2)和3)，直到目標(biāo)函數(shù)F不再發(fā)生變化為止.

2 改進k-prototypes聚類算法

k-prototypes算法雖實現(xiàn)了混合屬性數(shù)據(jù)的有效聚類，但在聚類過程中仍存在一些問題，隨機選取初始聚類中心導(dǎo)致聚類結(jié)果具有不確定性和隨機性.采用式(2)計算數(shù)據(jù)對象間的相似度，忽略了數(shù)值屬性數(shù)據(jù)對聚類結(jié)果的影響.同時分類屬性采用簡單匹配度量計算數(shù)據(jù)與類中心的相似度有兩個缺點：1)不能準(zhǔn)確地描述數(shù)據(jù)對象與類中心對應(yīng)的簇中其他數(shù)據(jù)的相似度，數(shù)據(jù)對象是否被劃分到一個簇中，不僅依賴于與聚類中心的相似度，還依賴于與類內(nèi)已有對象的總體相似度；2)當(dāng)數(shù)據(jù)對象與多個聚類中心的相似度相同時，算法往往會隨機將此數(shù)據(jù)加入到一個聚類集中，從而不能準(zhǔn)確地劃分到相似性更大的聚類集中.

2.1 改進的混合屬性數(shù)據(jù)度量公式

針對k-prototypes算法存在的問題，利用信息熵Ej的概念對數(shù)值屬性進行加權(quán)，并對分類屬性度量公式進行改進，給出混合屬性數(shù)據(jù)度量公式.

(3)

定義1數(shù)值屬性度量采用加權(quán)曼哈頓距離公式，數(shù)據(jù)對象xi與xj之間的度量計算定義為

(4)

定義2設(shè)cl表示聚類過程中的一個類，則分類屬性度量公式定義為

(5)

(6)

將定義3應(yīng)用到k-prototypes算法的目標(biāo)函數(shù)中，即

(7)

2.2 初始聚類中心選取

為了克服隨機選擇初始聚類中心導(dǎo)致聚類結(jié)果不穩(wěn)定的問題，借鑒文獻[15]中選擇初始聚類中心點的思想，并且利用平均差異度選取初始聚類中心.基于的原則是：初始聚類中心應(yīng)具有較大的平均差異度，且聚類中心之間的差異度要大于總體平均差異度.

平均差異度的計算依賴于數(shù)據(jù)對象兩兩之間的距離d(xi，xj)，本文采用混合屬性數(shù)據(jù)距離代替原方法中的歐式距離，其中數(shù)值部分為由定義1給出的數(shù)值屬性度量公式，分類屬性部分采用簡單匹配度量，從而擴展了原方法只能處理數(shù)值屬性數(shù)據(jù)的限制，使其能夠更好地解決混合屬性數(shù)據(jù)聚類問題.

2.3 算法描述

綜上得到基于平均差異度的改進k-prototypes聚類算法的步驟如下：

1) 給定聚類個數(shù)k，計算每個數(shù)據(jù)對象的平均差異度和總體平均差異度，將平均差異度進行排序，并把平均差異度最大的數(shù)據(jù)對象作為第1個初始聚類中心v1，同時將該數(shù)據(jù)從數(shù)據(jù)集中刪除；

2) 尋找其余數(shù)據(jù)對象中平均差異度最大的數(shù)據(jù)，計算其與已有聚類中心的距離；

3) 若計算其與已有聚類中心的距離均不小于總體平均差異度，則可作為聚類中心，否則，返回步驟2)，重復(fù)步驟2)和3)，直到初始聚類中心的個數(shù)達到k，并輸出初始聚類中心；

4) 根據(jù)定義3計算數(shù)據(jù)對象到各聚類集的距離，按照就近原則將數(shù)據(jù)分配到離其最近的聚類集中；

5) 更新每個類的中心，對數(shù)值屬性數(shù)據(jù)計算平均值，對分類屬性數(shù)據(jù)取屬性中出現(xiàn)概率最大的值；

6) 重復(fù)步驟4)和5)，直到各個聚類中心穩(wěn)定，目標(biāo)函數(shù)值不再發(fā)生變化，結(jié)束.

3 仿真試驗與結(jié)果分析

3.1 試驗環(huán)境

本文仿真試驗采用Matlab R2012a開發(fā)環(huán)境，Intel(R) Core(TM) i3-4005U CPU 1.70 GHz，4 GB內(nèi)存，在Windows7操作系統(tǒng)上運行.試驗數(shù)據(jù)采用UCI機器學(xué)習(xí)數(shù)據(jù)庫中的4個真實數(shù)據(jù)集，數(shù)據(jù)集描述如表1所示.

表1 試驗數(shù)據(jù)集描述Tab.1 Description of experiment data sets

以上4個數(shù)據(jù)集包括3種數(shù)據(jù)類型，其中Iris為數(shù)值型數(shù)據(jù)，Soybean為分類型數(shù)據(jù)，Credit和Heart為混合型數(shù)據(jù).

3.2 試驗結(jié)果

為了驗證本文算法的有效性和可行性，分別用k-prototypes算法、EKP算法、KL-FCM-GM算法、文獻[12]算法、文獻[13]算法和本文算法對上述數(shù)據(jù)進行聚類分析，試驗結(jié)果如圖1所示.

圖1 各種算法的聚類準(zhǔn)確率Fig.1 Clustering accuracy of various algorithms

從圖1可以看出，本文算法在處理Soybean數(shù)據(jù)集、Credit數(shù)據(jù)集和Heart數(shù)據(jù)集時，聚類準(zhǔn)確率都高于其他算法，只有在處理Iris數(shù)據(jù)時，低于文獻[13]算法，但優(yōu)于其他算法.這說明本文算法在處理混合型數(shù)據(jù)和分類型數(shù)據(jù)時有效性更高，而處理數(shù)值型數(shù)據(jù)有待提高.

為了進一步驗證本文算法的聚類質(zhì)量，比較本文算法與k-prototypes算法的聚類精度，利用Credit數(shù)據(jù)集的聚類結(jié)果，根據(jù)數(shù)據(jù)集依次迭代不同次數(shù)所對應(yīng)的目標(biāo)函數(shù)值，生成的對比結(jié)果如圖2所示.

圖2 迭代次數(shù)與目標(biāo)函數(shù)曲線Fig.2 Curves of iteration number and objective function

從圖2可以看出，目標(biāo)函數(shù)值均隨著迭代次數(shù)的增高而降低，但是在相同條件下，本文算法的目標(biāo)函數(shù)值比k-prototypes算法低，說明本文算法的聚類精度比k-prototypes算法高.

3.3 算法復(fù)雜度分析

本文算法主要由初始聚類中心的選取和聚類迭代兩部分構(gòu)成，其中選取初始聚類中心要計算數(shù)據(jù)對象之間的距離和尋找聚類中心，該過程的計算代價分別為O(n2)和O(kn)，確定聚類中心后，算法需要進行迭代劃分，其計算代價為O(tkn)，因此，總的時間復(fù)雜度變?yōu)镺(n2+kn+tkn)，其中，t為迭代次數(shù)，k?n.本文算法和其他算法的時間復(fù)雜度比較如表2所示.

表2 算法的時間復(fù)雜度統(tǒng)計Tab.2 Statistics results of time complexity for various algorithms

從表2中分析可以得出，本文算法的時間復(fù)雜度比k-prototypes、EKP、KL-FCM-GM及文獻[12]要高，主要消耗在選取初始聚類中心的環(huán)節(jié)上，但是確定了較優(yōu)的聚類中心點之后，會減少迭代次數(shù)，并得到較滿意的聚類結(jié)果，從而在一定程度上可以彌補時間復(fù)雜度較高的不足.

4 結(jié) 論

本文提出的基于平均差異度的改進k-prototypes聚類算法，是在傳統(tǒng)k-prototypes聚類算法基礎(chǔ)上進行的擴展.通過利用平均差異度確定初始聚類中心，考慮了數(shù)據(jù)的空間分布信息，使得聚類中心更符合實際情況，避免了對初始中心選擇所帶來的不確定性.改進的分類屬性數(shù)據(jù)度量公式，不僅考慮了數(shù)據(jù)對象與類中心的距離，還有效利用了數(shù)據(jù)與類中已有對象之間的總體相異性，使得在迭代過程中，對聚類集中已有對象的信息進行了統(tǒng)計參考，從而獲得更好的聚類結(jié)果.但該算法中聚類數(shù)目的選擇會影響聚類結(jié)果，因此，下一步將研究聚類數(shù)目的確定方法，尋找能夠自動選取合理聚類數(shù)目的方法.