基于加權(quán)重疊距離的K—modes聚類算法

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

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

中圖分類號：TP391.41

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

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

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

1 相關(guān)概念

作為一種不確定性的有效度量機制，香農(nóng)所提出的信息熵已被廣泛應用于很多不同的領(lǐng)域中[3]。為了度量粗糙集中的不確定性，不少學者把信息熵引入到粗糙集中，并由此提出了不同的信息熵模型，其中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在等價類Bi中出現(xiàn)的概率，1≤i≤p。

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

。

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

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

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

，

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

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

定義4.[加權(quán)重疊距離]給定一個信息表（U，A，V，f），對于任意屬性a∈A，用Sig（a）表示a的重要性，對任意兩個對象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中每個對象所在的簇（聚類結(jié)果）

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

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

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

（4）從論域U中隨機選擇K個對象作為初始中心點：z1，...，zK，令t=1。

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

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

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

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

4 結(jié)束語

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

參考文獻：

[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].西安：西安交通大學出版社，2001.

[6]徐章艷，劉作鵬，楊炳儒.一個復雜度為max（O（|C||U|），O（|C|2|U/C|））的快速屬性約簡算法[J].計算機學報，2006（03）：391-399.

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

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

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