基于平均差異度的改進(jìn)k-prototypes聚類算法*

石鴻雁， 徐明明

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

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

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

1 k-prototypes聚類算法

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

(1)

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

(2)

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

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

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

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

2 改進(jìn)k-prototypes聚類算法

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

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

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

(3)

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

(4)

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

(5)

(6)

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

(7)

2.2 初始聚類中心選取

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

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

2.3 算法描述

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

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

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

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

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

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

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

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

3.1 試驗(yàn)環(huán)境

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

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

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

3.2 試驗(yàn)結(jié)果

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

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

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

為了進(jìn)一步驗(yàn)證本文算法的聚類質(zhì)量，比較本文算法與k-prototypes算法的聚類精度，利用Credit數(shù)據(jù)集的聚類結(jié)果，根據(jù)數(shù)據(jù)集依次迭代不同次數(shù)所對(duì)應(yīng)的目標(biāo)函數(shù)值，生成的對(duì)比結(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)成，其中選取初始聚類中心要計(jì)算數(shù)據(jù)對(duì)象之間的距離和尋找聚類中心，該過程的計(jì)算代價(jià)分別為O(n2)和O(kn)，確定聚類中心后，算法需要進(jìn)行迭代劃分，其計(jì)算代價(jià)為O(tkn)，因此，總的時(shí)間復(fù)雜度變?yōu)镺(n2+kn+tkn)，其中，t為迭代次數(shù)，k?n.本文算法和其他算法的時(shí)間復(fù)雜度比較如表2所示.

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

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

4 結(jié) 論

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