一種改進(jìn)的k-modes聚類算法

施振佺 陳世平

(1.上海理工大學(xué) 管理學(xué)院,上海 200093； 2.南通大學(xué),江蘇 南通 226019)

0 引言

聚類是將相似度較高的數(shù)據(jù)對象分成相同類的過程。它通常是通過計算不同數(shù)據(jù)對象之間的相似度來判斷他們屬于哪個類，將相似度較高的分在同一個類，從而進(jìn)行分類的過程。聚類是數(shù)據(jù)挖掘的一個重要研究方向。現(xiàn)實中聚類分析的數(shù)據(jù)對象有不同的類型，可以分為數(shù)值型、分類型、數(shù)值和分類混合型。針對三種處理數(shù)據(jù)對象的類型分別有三種代表性的聚類方法，是K-means算法[1]、K-modes算法[2]和K-Prototype算法[3]。HUANG ZX[2]在K-means算法基礎(chǔ)上提出了K-modes算法，該算法改進(jìn)了k-means算法中采用距離作為度量的問題，而采用了相異度來度量。算法通過計算樣本和聚類中心的相異度來進(jìn)行聚類，相異度越小，則表示屬于這個類的可能性越大。

K-modes算法給分類型對象帶來了一種新的解決無法像數(shù)值型對象那樣計算距離的新方向，但考慮到HUANG ZX來計算分類對象屬性值間距離時僅采用了簡單的“0-1”匹配方法，雖然這種方法計算簡便也能很容易被應(yīng)用在各種領(lǐng)域，但這種算法談話了對象類屬性內(nèi)部的相似性問題，因此He[4]、San[5]、Ng[6]等人提出了屬性值在類內(nèi)出現(xiàn)的頻率來計算兩個屬性值之間的距離。Hsu等人[7,8]通過計算對象層次的距離提出了一種新方法，但主要依靠專家的經(jīng)驗和專業(yè)技術(shù)知識。Ganti等人[9]和Ahmad等人[10,11]用同一屬性下不同對象值之間的貢獻(xiàn)程度來計算他們之間的距離，但該方法沒有考慮屬性自身的差異。這些研究都在K-modes 算法改進(jìn)了對同一屬性下不同對象的聚類能力，但忽略了對象的不同屬性間的差異。……