一種基于屬性值權(quán)重的k-modes 聚類分析算法*

郝榮麗 胡立華

（太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 太原 030024）

1 引言

聚類分析是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域中的主要研究內(nèi)容之一，它是將物理或抽象的數(shù)據(jù)對(duì)象根據(jù)某種相似準(zhǔn)則劃分成多個(gè)對(duì)象類的過程，使得同一個(gè)類中的對(duì)象之間具有較高的相似性，而不同簇中的對(duì)象具有較高的相異性［1］，并已經(jīng)廣泛地應(yīng)用在基因分類［2］、股市波動(dòng)的特征分析［3］、天光光譜特征分析［4］、文檔的分類［5］、圖像處理［6］等許多領(lǐng)域。聚類分析主要分為劃分聚類［7］、層次聚類［8］、密度聚類［9］和網(wǎng)格聚類［10］。k-means算法［11］是一種經(jīng)典、常用的劃分聚類算法，具有簡單高效，易于理解和實(shí)現(xiàn)等優(yōu)點(diǎn)，但在實(shí)際應(yīng)用中，由于存在大量的分類型數(shù)據(jù)，k-means 方法不能處理包含分類屬性的數(shù)據(jù)集，限制了其實(shí)際應(yīng)用領(lǐng)域。

k-modes［12］作為k-means 聚類分析算法的一種擴(kuò)展，可適用于含有分類屬性的數(shù)據(jù)集，具有計(jì)算簡單、復(fù)雜度低等優(yōu)點(diǎn)，但該聚類算法采用簡單匹配差異法，未能充分體現(xiàn)數(shù)據(jù)集的分布特征，將所有屬性視為同等地位，忽略了屬性之間的重要性差異，若頻率最高的屬性值有多個(gè)，傳統(tǒng)k-modes 算法無法選出最恰當(dāng)?shù)膶傩灾底鳛樵摯啬Ｊ健１疚睦么植诩械牡葍r(jià)類計(jì)算屬性值權(quán)重的思想，提出了一種k-modes 聚類分析算法。由于該算法充分利用了屬性值在數(shù)據(jù)集中的分布特征與屬性值自身的差異，有效地解決了屬性值之間的差異性度量，并利用屬性值頻率和各屬性值的權(quán)重，給出一種聚類中心更新途徑，從而有效地提高了聚類分析的效果。本文主要貢獻(xiàn)為

1）利用屬性值之間的差異和屬性值的權(quán)重，重新定義了相異度度量公式；

2）采用屬性值頻率和各屬性值的權(quán)重，給出了一種聚類中心更新迭代公式；

3）提出了一種基于屬性值權(quán)重的k-modes 聚類算法。

2 相關(guān)工作

k-modes 作為k-means 算法的一種擴(kuò)展，根據(jù)分類數(shù)據(jù)的特點(diǎn)，采用簡單的0-1 匹配法來度量分類數(shù)據(jù)間的距離，用模式代替均值，但是這種采用簡單匹配差異法忽略了屬性之間的差異性，導(dǎo)致差異性度量不準(zhǔn)確。對(duì)k-modes 改進(jìn)的典型成果為：He［13］等使用屬性值在類內(nèi)出現(xiàn)的頻率提出新的類內(nèi)屬性距離計(jì)算公式；Hsu［14］等提出一種基于概念層次的方法來計(jì)算屬性值之間的距離，但該方法需要專家經(jīng)驗(yàn)；賈彬［15］等使用信息熵為屬性加權(quán)來解決屬性之間的差異問題，但是該方法在確定屬性權(quán)重時(shí)只考慮了某一屬性的分布，沒有考慮相關(guān)屬性對(duì)其的影響；白亮［16］等利用粗糙集中的上、下近似提出了一種新的相似性度量，改善了聚類效果，卻提高了計(jì)算的復(fù)雜度；趙亮［17］等基于樸素貝葉斯分類器中間運(yùn)算結(jié)果計(jì)算屬性值之間的距離；黃苑華［18］等基于相互依存的冗余理論提出一種新的距離公式，采用內(nèi)部距離和外部距離共同衡量兩個(gè)對(duì)象屬性值之間的距離，在進(jìn)行外部距離計(jì)算時(shí)，僅從相關(guān)屬性的角度對(duì)屬性值在整個(gè)數(shù)據(jù)集上的分布情況進(jìn)行描述，導(dǎo)致差異性度量不準(zhǔn)確，這些算法不能夠準(zhǔn)確應(yīng)用屬性空間中數(shù)據(jù)間的關(guān)系，因而會(huì)丟失數(shù)據(jù)間的相似關(guān)系。針對(duì)傳統(tǒng)k-modes 算法中的模式問題，賈彬［15］提出了多屬性值modes 的相異度度量方法，每個(gè)屬性都保留全部屬性值和其出現(xiàn)頻率，但這樣也使得數(shù)據(jù)對(duì)象與modes 之間的距離計(jì)算變得復(fù)雜化。

綜上所述，k-modes 雖然將k-means 聚類分析算法應(yīng)用范圍擴(kuò)展到了分類數(shù)據(jù)集，但其多種距離度量都無法有效地度量分類數(shù)據(jù)之間的距離，未能充分體現(xiàn)分類變量間的差異，以及在整個(gè)數(shù)據(jù)集中的分布特征。

3 聚類目標(biāo)函數(shù)與多屬性權(quán)重

為適用于分類數(shù)據(jù)的聚類分析，Huang 等于1998年提出了k-modes聚類算法，給定一組分類數(shù)據(jù)對(duì)象X={x1，x2，…，xn}和整數(shù)k（k≤n），數(shù)據(jù)集隨機(jī)初始劃分成k個(gè)互斥的簇，對(duì)數(shù)據(jù)對(duì)象迭代重定位簇，最終搜索得到使簇內(nèi)平方誤差和，即目標(biāo)函數(shù)F最小化的k個(gè)互斥的簇，參照文獻(xiàn)［12］，其目標(biāo)函數(shù)定義如下：

聚類目標(biāo)函數(shù)為

在式（1）中，W是一個(gè)n×k的{0 ，1} 矩陣，n表示數(shù)據(jù)集U中數(shù)據(jù)點(diǎn)的個(gè)數(shù)，k表示聚類的個(gè)數(shù)，Z={z1，z2，…，zk}，zl為第l 個(gè)類的中心點(diǎn)，zl={zl1，zl2，…，zlm} ，zlm是第l個(gè)類的第m個(gè)屬性上出現(xiàn)頻率最高的屬性值，d(xi，zl)為簡單的0-1匹配計(jì)算得出的分類變量間的距離。

多屬性值權(quán)重是屬性值在屬性空間中分布特征的體現(xiàn)，可從本地屬性和相關(guān)屬性兩個(gè)角度，來有效地刻畫屬性值在屬性空間上的分布特征。則參照文獻(xiàn)［19］，相關(guān)概念如下：

對(duì)于任意ai∈A，設(shè)xki∈Vai，從本地屬性ai的角度度量xki的單屬性權(quán)重為

從相關(guān)屬性aj的角度度量xki的多屬性權(quán)重為

結(jié)合本地屬性和相關(guān)屬性定義屬性值的權(quán)重為

其中：[xk]ai表示數(shù)據(jù)對(duì)象xk在屬性ai的等價(jià)類，表示屬性值xki和xkj的共現(xiàn)次數(shù)。屬性值權(quán)重W(xki)體現(xiàn)了屬性值在整個(gè)屬性空間中的分布特征。

4 基于屬性值權(quán)重的k-mode 聚類分析

兩個(gè)數(shù)據(jù)對(duì)象同一屬性下兩個(gè)值之間是否相似既取決于屬性值本身，又取決于其所處的環(huán)境，即屬性值所處的屬性空間［16］?？衫脤傩灾档臋?quán)重來表示屬性空間的分布特征對(duì)屬性值相異度的影響，即外部相異度；同時(shí)，也需考慮屬性值本身之間的差異性，即內(nèi)部相異度。因此，數(shù)據(jù)對(duì)象屬性值之間的相異度是由外部相異度和內(nèi)部相異度共同決定，其相異度越大，距離也越大。

設(shè)xi和xj為數(shù)據(jù)集中的任意兩個(gè)數(shù)據(jù)對(duì)象，at為任一屬性，則參照文獻(xiàn)［18］，數(shù)據(jù)對(duì)象xi和數(shù)據(jù)對(duì)象xj在屬性at上的相異度度量公式重新定義如下：

在式（5）中，d1(xit，xjt)表示兩個(gè)數(shù)據(jù)對(duì)象屬性值本身的差異度，即內(nèi)部相異度；d2(xit，xjt)表示兩個(gè)數(shù)據(jù)對(duì)象在整個(gè)屬性空間中分布的差異度，即外部相異度；1 2 表示兩種差異度的重要性相當(dāng)，共同決定了屬性值之間的距離，差異度越高，距離越遠(yuǎn)。

參照文獻(xiàn)［18］，數(shù)據(jù)對(duì)象xi和數(shù)據(jù)對(duì)象xj在屬性at上的內(nèi)部相異度的度量公式如下：

在式（6）中，使用簡單0-1 匹配來計(jì)算兩個(gè)屬性值間的內(nèi)部相異度。

由式（4）引入的屬性值權(quán)重，可得出第i個(gè)數(shù)據(jù)對(duì)象和第j個(gè)數(shù)據(jù)對(duì)象在屬性at上的外部相異度的度量公式如下：

式中W(xit)，W(xjt)分別代表屬性值xit和xjt對(duì)應(yīng)的權(quán)重，用權(quán)重的差值來表示他們之間的外部相異度。

傳統(tǒng)的k-modes 算法在每個(gè)簇的每個(gè)屬性上選擇出現(xiàn)次數(shù)最多的屬性值作為該簇中心點(diǎn)在該屬性上的值，但是屬性上出現(xiàn)頻率高的屬性值有多個(gè)的話難以獲得最合適的中心點(diǎn)，因此，利用屬性取值的頻率以及屬性值的權(quán)重，重新描述類中心，并找出類中心對(duì)應(yīng)的平均權(quán)重，從而可有效提高聚類精度。聚類族中心和對(duì)應(yīng)的平均權(quán)重定義如下：

定義1 類l中某屬性at上某一屬性值的平均權(quán)重為該類中屬性at對(duì)應(yīng)的該屬性值的所有權(quán)重之和的平均值。

定義2 類l的中心為zl={zl1，zl2，…，zlm} ，其中zlm為類l中數(shù)據(jù)對(duì)象在屬性am上出現(xiàn)頻率最高的，且具有最高平均權(quán)重的屬性值。每一個(gè)中心點(diǎn)對(duì)應(yīng)一個(gè)平均權(quán)重集平均權(quán)重集代表模式中每個(gè)屬性值在屬性空間中的分布情況。

5 基于屬性值權(quán)重的k-mode 聚類算法

根據(jù)第3 節(jié)和第4 節(jié)的描述，在分類型數(shù)據(jù)集中，采用重新定義的相異度度量方式以及聚類簇中心選擇的聚類分析基本步驟為利用粗糙集中的等價(jià)類，計(jì)算數(shù)據(jù)集中所有數(shù)據(jù)對(duì)象的屬性值的屬性權(quán)重；隨機(jī)選擇數(shù)據(jù)集U中k個(gè)數(shù)據(jù)點(diǎn)作為初始的聚類中心；計(jì)算數(shù)據(jù)集中所有數(shù)據(jù)對(duì)象與k個(gè)聚類中心之間的相異度，然后將每個(gè)對(duì)象分配到與其相異度最小的聚類中心所在的簇中；在得到的k個(gè)簇中，更新簇的中心點(diǎn)及其對(duì)應(yīng)的權(quán)重；重復(fù)上述兩個(gè)步驟，直到目標(biāo)函數(shù)達(dá)到最小值，k個(gè)簇的類中心不再發(fā)生變化為止。算法偽代碼描述如下：

算法：MCAMAW（K-modes clustering algorithm based on multiple attribute weights）

輸入：分類數(shù)據(jù)集，簇的個(gè)數(shù)k

輸出：聚類簇

1）for（int i=0；i＜n；i++）｛

2）for（int j=0；j＜m；j++）｛

3） 利用xit在屬性at上的等價(jià)類，根據(jù)式（2）～（4）計(jì)算出屬性值xit的屬性權(quán)重W( )xit。

4）｝

5）｝

6）隨機(jī)初始找出k個(gè)簇中心，平均權(quán)重集為其對(duì)應(yīng)的屬性值的權(quán)重

7）for（int i=0；i＜n；i++）｛

8） for（int cu=0；cu＜k；cu++）｛

9） for（int j=0；j＜m；j++）｛

10） 根據(jù)式（5）～（7）計(jì)算出所有數(shù)據(jù)對(duì)象與簇中心之間的距離，然后將各個(gè)數(shù)據(jù)對(duì)象

11） 分配到離其最近的簇中。

12）｝｝｝

13）for（int cu=0；cu＜k；cu++）｛

14） 根據(jù)定義1 和定義2 更新各個(gè)簇的中心及其平均權(quán)重集

15）｝

16）重復(fù)第7）步到第17）步，直至式（3）達(dá)到最小值，k個(gè)簇的類中心不再發(fā)生變化為止

17）返回聚類簇

6 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證所提MCAMAW 算法的有效性，從UCI數(shù)據(jù)集中選取Mushroom、Vote、Breast-cancer三個(gè)數(shù)據(jù)集，詳見表1 所示。采用python 語言實(shí)現(xiàn)了MCAMAW 算法、傳統(tǒng)k-modes 算法［12］和基于相互依存冗余度量k-modes 算法［18］，并分別從分類正確率、分類精度和召回率三個(gè)指標(biāo)進(jìn)行評(píng)價(jià)。

表1 UCI數(shù)據(jù)集

表2～4 給出了MCAMAW 算法與傳統(tǒng)k-modes算法［12］和基于相互依存冗余度量k-modes 算法［18］的實(shí)驗(yàn)比較結(jié)果。可以看出在Mushroom、Vote、Breast-cancer數(shù)據(jù)集上MCAMAW 算法的三個(gè)指標(biāo)均有所提高，聚類效果也優(yōu)于其他兩個(gè)算法。其主要原因是MCAMAW 算法充分利用數(shù)據(jù)對(duì)象在數(shù)據(jù)集中的空間特征，準(zhǔn)確地描述了數(shù)據(jù)對(duì)象之間的關(guān)系，有效地避免了其他兩個(gè)對(duì)比算法中分類數(shù)據(jù)對(duì)象之間距離度量不準(zhǔn)確的問題。

表2 Mushroom數(shù)據(jù)集

表3 Vote數(shù)據(jù)集

表4 Breast-cancer數(shù)據(jù)集

7 結(jié)語

本文采用多屬性權(quán)重，提出了一種k-modes 聚類算法。該算法從本地屬性和相關(guān)屬性兩個(gè)角度，描述了數(shù)據(jù)對(duì)象的屬性空間分布特征。在度量數(shù)據(jù)對(duì)象間的距離時(shí)，不僅考慮了數(shù)據(jù)對(duì)象本身的差異性，而且考慮了數(shù)據(jù)對(duì)象在整個(gè)屬性空間結(jié)構(gòu)中的差異性。此外，在屬性值分布過于分散或相對(duì)均等時(shí)，可以根據(jù)屬性值的平均權(quán)重進(jìn)一步確定模式中的屬性值，以便能夠找到更恰當(dāng)?shù)膶傩灾底鳛樵擃惖哪Ｊ剑瑥亩行У靥岣呔垲愋Ч?/p>