摘 要：傳統(tǒng)的K-modes聚類算法在計(jì)算兩個(gè)對象之間的距離時(shí)，并沒有考慮不同屬性之間的差異性。針對這一問題，本文基于粗糙集理論引入一種新的距離度量標(biāo)準(zhǔn)——加權(quán)重疊距離，并提出一種基于加權(quán)重疊距離的K-modes聚類算法WODKM。

關(guān)鍵詞：聚類分析；粗糙集理論；加權(quán)重疊距離；屬性重要性

中圖分類號：TP391.41

近年來，針對類別型數(shù)據(jù)（categorical data）的聚類問題引起了廣泛關(guān)注，其中K-modes聚類算法在各個(gè)領(lǐng)域中被廣泛使用[1]。

現(xiàn)有的K-modes聚類方法在計(jì)算對象之間的距離時(shí)，假設(shè)所有屬性的作用都是相同的，并沒有考慮不同屬性之間的差異性[1]。在一個(gè)給定的信息表中，不同的屬性對于距離運(yùn)算結(jié)果的影響在很多時(shí)候是不同的。因此，有必要將不同的屬性嚴(yán)格區(qū)分開來。

針對現(xiàn)有方法所存在的問題，本文提出一種新的針對類別型數(shù)據(jù)的距離度量標(biāo)準(zhǔn)——加權(quán)重疊距離。在計(jì)算對象之間的加權(quán)重疊距離時(shí)，我們利用粗糙集理論中的信息熵、屬性重要性等概念來為每個(gè)屬性賦予一個(gè)權(quán)值[2-3]。通過使用加權(quán)重疊距離，我們在現(xiàn)有的K-modes聚類算法基礎(chǔ)上，進(jìn)一步提出了一種基于加權(quán)重疊距離的K-modes聚類算法WODKM。

1 相關(guān)概念

作為一種不確定性的有效度量機(jī)制，香農(nóng)所提出的信息熵已被廣泛應(yīng)用于很多不同的領(lǐng)域中[3]。為了度量粗糙集中的不確定性，不少學(xué)者把信息熵引入到粗糙集中，并由此提出了不同的信息熵模型，其中Düntsch等所提出的信息熵模型被廣泛使用[4]，具體定義如下：

定義1.給定信息表IS=（U，A，V，f），對任意B?A，令U/IND（B）={B1，…，Bp}表示不可區(qū)分關(guān)系IND（B）對U的劃分的。我們將關(guān)系IND（B）的信息熵E（B）定義為：

，

其中，∣Bi∣/∣U∣表示任何元素x∈U在等價(jià)類Bi中出現(xiàn)的概率，1≤i≤p。

定義2.[基于信息熵的屬性重要性]給定信息表IS=（U，A，V，f），對任意a∈A，屬性a。在IS中的重要性被定義為[5]：

。

2 加權(quán)重疊距離

在Huang等所提出的K-modes聚類算法中，簡單重疊距離被用來度量任意兩個(gè)對象x與y之間的不相似性，具體定義如下[1]：

定義3.[簡單重疊距離] 給定一個(gè)信息表IS=（U，A，V，f），對于任意兩個(gè)對象x，y∈U，x與y之間的簡單重疊距離定義如下：

，

其中，δa（x，y）表示x和y在屬性a上的簡單匹配距離，定義如下：

很明顯，在上述定義中，每個(gè)屬性對于兩個(gè)對象之間距離的影響是一樣的，即各個(gè)屬性的權(quán)重都等于1。然而，在很多情況下，每個(gè)屬性的影響很有可能是不同的。接下來，我們將在簡單重疊距離的基礎(chǔ)上，提出一種加權(quán)重疊距離，其中每個(gè)屬性的權(quán)值都是通過計(jì)算該屬性的重要性而得到的（注：我們基于信息熵來計(jì)算每個(gè)屬性的重要性，見定義2）。

定義4.[加權(quán)重疊距離]給定一個(gè)信息表（U，A，V，f），對于任意屬性a∈A，用Sig（a）表示a的重要性，對任意兩個(gè)對象x，y∈U，x和y之間的加權(quán)匹配距離定義如下：

，

其中，δa（x，y）見定義3，weight（a）表示屬性a的權(quán)重，定義如下：

3 WODKM算法

下面，我們給出基于加權(quán)重疊距離的K-modes聚類算法WODKM：

算法1 WODKM

輸入：信息表IS=（U，A，V，f），參數(shù)K。

輸出：U中每個(gè)對象所在的簇（聚類結(jié)果）

（1）根據(jù)基數(shù)排序，計(jì)算不分明關(guān)系IND（A） 對論域U的劃分U/IND（A）。

（2）計(jì)算關(guān)系IND（A）的信息熵E（A）。

（3）對于每個(gè)屬性a∈A：①根據(jù)基數(shù)排序，計(jì)算不分明關(guān)系IND（A-{a}）對U的劃分U/IND（A-{a}）；②計(jì)算IND（A-{a}）的信息熵E（A-{a}）；③計(jì)算屬性a的重要性Sig（a）；④計(jì)算屬性a的權(quán)值weight（a）。

（4）從論域U中隨機(jī)選擇K個(gè)對象作為初始中心點(diǎn)：z1，...，zK，令t=1。

（5）根據(jù)每個(gè)屬性的權(quán)值，計(jì)算U中每個(gè)對象與每個(gè)中心點(diǎn)zi的加權(quán)重疊距離，1≤i≤K，并把每個(gè)對象劃分到距離它最近的中心點(diǎn)所代表的簇中。

（6）根據(jù)屬性值的取值頻率，重新計(jì)算每個(gè)簇的中心點(diǎn)。

（7）重復(fù)步驟5和6，直到目標(biāo)函數(shù)的值不變（或者變化小于給定的閾值）。

在算法1中，我們采用了一種預(yù)先對U中對象進(jìn)行基數(shù)排序，然后再求劃分U/IND（B）的方法[6]，從而使得計(jì)算U/IND（B）的時(shí)間復(fù)雜度降低為O（|B|×|U|）。在最壞的情況下，算法1的時(shí)間復(fù)雜度為O（|A|2×|U|+t×K×|U|×|A|），空間復(fù)雜度為O（|A|+|U|+K），其中t和K分別為算法的迭代次數(shù)和簇的個(gè)數(shù)。

4 結(jié)束語

本文基于粗糙集理論中的屬性重要性和信息熵等概念，提出了一種新的距離度量標(biāo)準(zhǔn)，并將此距離度量標(biāo)準(zhǔn)應(yīng)用于傳統(tǒng)的K-modes聚類算法中。通過充分考慮不同屬性之間的差異性，我們所提出的K-modes聚類算法更加符合客觀實(shí)際。

參考文獻(xiàn)：

[1]Z.Huang.Extensions to the k-means algorithm for clustering large data sets with categorical values.Data Mining and Knowledge Discovery，1998，2（03）：283-304.

[2]Pawlak Z.Rough Sets-Theoretical Aspects of Reasoning About Data.London：Kluwer Academic Publishers，1991.

[3]Shannon，C.E.，1948.The mathematical theory of communication.Bell System Technical Journal，27（3-4）pp：373-423.

[4]Düntsch，I.，Gediga，G.，1998.Uncertainty measures of rough set prediction，Artificial Intelligence，106，pp：109-137.

[5]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學(xué)出版社，2001.

[6]徐章艷，劉作鵬，楊炳儒.一個(gè)復(fù)雜度為max（O（|C||U|），O（|C|2|U/C|））的快速屬性約簡算法[J].計(jì)算機(jī)學(xué)報(bào)，2006（03）：391-399.

作者簡介：儲璐璐（1991-），女，碩士研究生，研究方向：數(shù)據(jù)挖掘、粗糙集理論等；江峰（1978-），男，副教授，研究方向：人工智能、粗糙集理論等。

作者單位：青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院，山東青島 266061

基金項(xiàng)目：本文受國家自然科學(xué)基金項(xiàng)目（60802042，61273180）、山東省自然科學(xué)基金項(xiàng)目（ZR2011FQ005，ZR2011FQ026）資助。