一種支持權(quán)重的改進K-means聚類算法

方振東，汪峰坤

聚類是數(shù)據(jù)挖掘技術(shù)中重要的應用方法，它利用所定義的“距離”概念把數(shù)據(jù)集分成多個類或簇［1］，使得同一簇中的數(shù)據(jù)對象相似度較高，不同簇中的數(shù)據(jù)對象相似度較低。聚類算法一般分成四類，分別是層次聚類算法、劃分聚類算法、密度聚類算法以及其他聚類算法，其中K-means聚類算法［2］是一種提出較早、應用較廣泛的聚類算法，其他聚類算法都是基于K-means聚類算法進行改進的。K-means算法的優(yōu)點包括實現(xiàn)簡單、收斂速度快、能有效地處理大數(shù)據(jù)集等。經(jīng)典K-means算法的缺點有聚類結(jié)果容易只得到局部最優(yōu)解、孤立點對聚類結(jié)果影響較大、聚類結(jié)果受初始數(shù)據(jù)對象影響較大、只能對凸形數(shù)據(jù)進行聚類、算法要求提前給出類的個數(shù)及不支持權(quán)重等［1-3］。

已有研究人員針對K-means算法存在的缺陷提出了改進辦法。如：針對K值要提前給出的問題，劉曉悅等［4］提出了兩段法，先使用 Canopy算法處理數(shù)據(jù)集，計算出K值和初始的類中心位置，再進行K-means算法詳細聚類。鄭富蘭等［5］提出了每個聚類簇中由一個點作為簇代表，提高了聚類的效率。針對K-means算法無法對任意形狀的數(shù)據(jù)集有效聚類的問題，邢長征等［6］提出了以平均密度作為聚類中心的改進算法。公茂果等［7］提出了流形距離，使算法能適用于復雜分布的數(shù)據(jù)聚類問題。

在聚類的現(xiàn)實應用中，各維的重要性都不同。例如，在職工健康體檢的生化檢查包含的子項中，白蛋白/球蛋白、低密度脂蛋白（LDL）、空腹血糖（GLU）和高密度脂蛋白（HDL_C）等健康指標的重要性是有區(qū)別的。重要性一般由專家給出的權(quán)重表示，但在經(jīng)典的K-means算法中是不支持維的權(quán)重值的。

我們提出了支持權(quán)重的K-means改進算法并通過仿真實驗驗證所提出改進算法的有效性。

1 改進算法

1.1 算法的基本數(shù)據(jù)結(jié)構(gòu)

設(shè)待聚類的數(shù)據(jù)集D中數(shù)據(jù)對象個數(shù)為n，每一個數(shù)據(jù)對象都由M維數(shù)據(jù)組成，不同的數(shù)據(jù)具有不同的權(quán)重，數(shù)據(jù)對象的值記為V1，V2，…，Vn。 每維數(shù)據(jù)的權(quán)重為 R1，R2，…，Rn，給定聚類數(shù)為 K 個。

改進算法使用到的數(shù)據(jù)結(jié)構(gòu)如下：

權(quán)重Hash表R中每個鍵值對表示數(shù)據(jù)對象中的一個維，鍵取值為維（即屬性）名稱，值為相應屬性的權(quán)重。在支持權(quán)重的聚類應用中，數(shù)據(jù)對象維數(shù)一般不是很高，使用Hash表可以快速得到維相應的權(quán)重。

每一個數(shù)據(jù)對象都使用浮點類型數(shù)組表示，數(shù)組下標對應相應的維，數(shù)組值為數(shù)據(jù)對象相應維的值。

簇用自定義類表示，類中有數(shù)據(jù)對象列表和簇中心點坐標對象。數(shù)據(jù)對象列表中是該簇中所有的數(shù)據(jù)對象，中心點坐標對象表示該簇計算得到的中心點坐標。

1.2 算法流程及計算公式

算法流程如下：

1）隨機選擇K個數(shù)據(jù)對象作為初始簇的中心點。

2）循環(huán)遍歷其余數(shù)據(jù)對象，計算數(shù)據(jù)對象到K個簇中心點的距離。

3）將數(shù)據(jù)對象加入到距離最近的簇中。

4）重新計算加入新數(shù)據(jù)對象后簇的中心點坐標。

5）直到所有數(shù)據(jù)對象加入完成。

6）轉(zhuǎn)到2），直到未出現(xiàn)數(shù)據(jù)對象被重新分配到其他簇的情況。

K-means算法常用的計算簇內(nèi)距離公式是歐幾里德公式

其中 i=xi1，xi2，…，xiM和 j=xj1，xj2，…，xjM是兩個 M 維的數(shù)據(jù)對象。

經(jīng)典的K-means算法無法體現(xiàn)各維的重要性，而本算法對簇內(nèi)距離的計算公式進行了改進，使改進后的K-means算法支持權(quán)重。改進后的距離計算公式為

其中Rs表示第s維數(shù)據(jù)的權(quán)重，且Rs＞0。

改進后計算公式仍然滿足距離要求，即距離是非負的、數(shù)據(jù)對象與自身的距離為0、距離是對稱的、距離滿足三角不等式。

K-means算法針對簇中心點的計算方法常用的是均值法，即簇中任意維坐標中心點為改進后的計算公式為，Rs為相應維的權(quán)重。

對于在迭代過程中計算簇中心點，K-means使用的方法是遍歷簇中所有數(shù)據(jù)對象，通過公式進行計算，時間復雜度為O（n）。本算法改為直接利用上一次計算出的中心點，可將算法的時間復雜度減少為O（1）。具體思路是：設(shè)上一次計算某維中心點坐標為 x ’，簇中數(shù)據(jù)對象個數(shù)為m個，加入數(shù)據(jù)對象的相應維坐標為x，則加入數(shù)據(jù)對象后相應維坐標計算公式為x = ( x’× m + x ) /(k +1)。

綜上，相對于經(jīng)典的K-means算法，我們主要進行了兩方面的改進：1）修改了簇的中心點和簇內(nèi)距離的計算公式，使算法支持維權(quán)重；2）對迭代過程中的中心點計算公式進行了修改，使算法的時間復雜度降低。

2 改進算法實驗與分析

2.1 算法流程實驗

設(shè)某數(shù)據(jù)集中有8條數(shù)據(jù)，每條數(shù)據(jù)固定有3個屬性，這3個屬性的權(quán)重分別是8、4和1，聚類個數(shù)K取值為3。數(shù)據(jù)見表1。

表1 聚類數(shù)據(jù)示例

經(jīng)典的K-means算法不支持維的權(quán)重。在不考慮維權(quán)重的情況下，聚類過程如下：

1）為了簡單，我們按順序選擇初始簇。前（K-1）個簇中每個簇的元素個數(shù)為，其余元素放到第K個簇。簇 1數(shù)據(jù)對象為 {T1，T2}，中心點坐標為（5.5，4，2.5）；簇 2 數(shù)據(jù)對象為{T3，T4}，中心點坐標為（5.5，3，3.5）；則簇 3 數(shù)據(jù)對象為{T5，T6，T7，T8}，中心點坐標為（5.5，3，5.5）。

2）第一次迭代后，簇 1 數(shù)據(jù)對象為{T2，T3，T4}，中心點坐標為（7，4.3，2）；簇 2 數(shù)據(jù)對象為{T1}，中心點坐標為（1，1，1）；簇 3 數(shù)據(jù)對象為{T5，T6，T7，T8}，中心點坐標為（5.3，5，5.5）。

3）第二次迭代后，簇 1 數(shù)據(jù)對象為{T2，T3}，中心點坐標為（9.5，4.5，2.5）；簇 2 數(shù)據(jù)對象為{T1，T4}，中心點坐標為（1.5，2，5.1）；簇 3 數(shù)據(jù)對象為{T5，T6，T7，T8}，中心點坐標為（5.3，5.5，5.5）。

4）第三次迭代，無交換數(shù)據(jù)，結(jié)束。

本算法支持維的權(quán)重，聚類過程如下：

1）初始簇仍然使用順序選擇。簇1數(shù)據(jù)對象為{T1，T2}，中心點坐標（5.5，4.2，2.5）；簇 2 數(shù)據(jù)對象為{T3，T4}，中心點坐標為（5.5，3，3.5）；簇 3 數(shù)據(jù)對象為{T5，T6，T7，T8}，中心點坐標為（5，3.5，5.5）。

2）第一次迭代后，簇1數(shù)據(jù)對象為{T2}，中心點坐標為（10，7，4）；簇 2 數(shù)據(jù)對象為{T3，T7}，中心點坐標為（8，3，3.5）；簇 3 數(shù)據(jù)對象為{T1，T4，T5，T6，T8}，中心點坐標為（3.2，3，4.6）。

3）第二次迭代后，簇1數(shù)據(jù)對象為{T2}，中心點坐標為（10，7，4）；簇 2 數(shù)據(jù)對象為{T3，T5，T7}，中心點坐標為（7.3，3，3.5）；簇 3 數(shù)據(jù)對象為{T1，T4，T6，T8}，中心點坐標為（2.5，3，3.75）。

4）第三次迭代后，簇1數(shù)據(jù)對象為{T2}，中心點坐標（10，7，4）。 簇 2 數(shù)據(jù)對象為{T3，T5，T6，T7}，中心點坐標（6.75，3，3.5）；簇 3 數(shù)據(jù)對象為{T1，T4，T8}，中心點坐標為（1.6，3，2.6）。

5）第四次迭代，無交換數(shù)據(jù)，結(jié)束。

可以看出，引入權(quán)重后，簇類結(jié)果發(fā)生了變化，且權(quán)重越大的維在計算距離時產(chǎn)生的作用越大。

2.2 算法性能比較

測試數(shù)據(jù)選擇某醫(yī)院職工健康體檢中數(shù)據(jù)，共有10維，K=2，數(shù)據(jù)量從1萬條增加到20萬條。

由圖1中可見，當數(shù)據(jù)量較小時，兩種算法性能相近，但在數(shù)據(jù)量較大時，本文算法要略優(yōu)于K-means算法。

圖2是數(shù)據(jù)為10維，數(shù)據(jù)量為5萬條，在不同K值時算法性能的比較。由圖2可見，兩種算法運算時間與K值相關(guān)，隨著K值的變化運算時間發(fā)生變化。總體上，改進算法相對于K-means算法在運行時間上略有減少。

圖1 不同數(shù)據(jù)量時算法性能比較

圖2 不同K值時算法性能比較

3 結(jié)束語

我們根據(jù)實際聚類應用的需求，提出了支持不同維權(quán)重的改進的K-means算法，改進了簇中心點計算公式和簇內(nèi)距離計算公式，使公式支持維的權(quán)重。我們對在算法迭代過程中的中心點計算流程進行了優(yōu)化，使改進算法的性能有了一定的提高。

參考文獻：

［1］ JAIN A K,MURTY M N,FLYNN P J.Data clustering:a review［J］.ACMcomputing surveys,1999,31（3）:264-323.

［2］ HARTIGAN J A,WONG M A.A K-means clustering algorithm［J］.Applied statistics,1979,28（1）:100-108.

［3］ MAULIK U,BANDYOPADHYAY S.Genetic algorithmbased clustering technique［J］.Pattern recognition,2000,33（9）:1455-1465.

［4］ 劉曉悅，郭強.海量用電數(shù)據(jù)并行聚類分析［J］.遼寧工程技術(shù)大學學報（自然科學版），2016，35（1）：76-80.

［5］ 鄭富蘭，張艷芳，吳瑞.基于 leader的 K-means改進算法［J］.山西師范大學學報（自然科學版），2014，28（4）：26-29.

［6］ 邢長征，谷浩.基于平均密度優(yōu)化初始聚類中心的K-means算法［J］.計算機工程與應用，2014，50（20）：135-138.

［7］ 公茂果，王爽，馬萌，等.復雜分布數(shù)據(jù)的二階段聚類算法［J］.軟件學報，2011，22（11）：2760-2772.