對K-means聚類算法歐氏距離加權系數的研究

◆郭 靖

（中國人民公安大學信息工程與網絡安全學院 北京 100038）

對K-means聚類算法歐氏距離加權系數的研究

◆郭 靖

（中國人民公安大學信息工程與網絡安全學院 北京 100038）

K-means聚類算法廣泛應用于模式識別、圖像處理和數據挖掘等領域中，有著簡潔高效等優點。然而，傳統的K-means聚類算法在以歐氏距離為度量函數時簡單地把數據的各個屬性平等對待，忽略了不同屬性的重要性不同。本文結合統計學中描述數據離散程度的四種指標提出四種計算加權系數的方法，并通過實驗比較這四種加權系數對聚類結果準確度的影響，以此來說明對歐氏距離加權的必要性和計算加權系數的簡單可行的方法。

K-means聚類算法；歐氏距離；加權系數

0 引言

K-means聚類算法[1]是最著名的劃分聚類算法之一，簡潔、高效以及適應性強等優點使得它成為所有聚類算法中最廣泛使用的。它的中心思想是：在數據集中隨機選擇K個對象作為初始聚類中心并代表K個類別；然后將其余的數據點依據它們到各初始聚類中心的歐氏距離劃分到與其距離最近的類別中，以形成初始分類；最后對初始分類進行多次迭代修正，直到分類比較合理為止。傳統的K-means算法認為數據的各個屬性對聚類結果的貢獻相同，沒有考慮不同屬性對聚類結果可能造成的不同影響，進而可能使聚類結果無法準確地反映數據類別的真實情況。

大量的相關研究表明：對K-means聚類算法中的歐氏距離引入加權系數可以提高聚類準確度。已知的加權方法包括：基于密度加權[2]，特征權值學習[3]，自適應加權[4]等。在2002年，Fabrizio[5]對已有加權系數的計算方法作了總結，分析了包括Document frequency，Information gain，Mutual information，Chi-square等多種加權系數計算方法的特性及適用領域。相關理論分析和實驗結果指出每種計算方法在運算速度和聚類結果的精度等方面各有優劣。

本文從要聚類分析的數據本身入手，以數據各個特征的離散程度來確定加權系數的大小。對于任意兩個屬性特征c1、c2，如果c1樣本的離散程度比c2的大，則可以認為c1屬性在聚類中應占有更重要的地位。通過對c1屬性賦予較大權值來調整特征空間，可以更準確反映類內相似度并得到更佳的聚類結果[6]。這種方法不需要分析人員額外輸入其他的參數，保證了聚類結果的客觀性，減少了工作難度，簡單快捷，易于實現。

1 相關工作

1.1 K-means聚類算法

K-means聚類算法的主要思想是：首先，在需要分類的數據中隨機尋找K個數據作為初始聚類中心；然后，計算其他數據距離這K個聚類中心的歐式距離，將數據歸入與其歐式距離最近的那一類別，再對這K個聚類中的數據分別計算算術平均值，作為各個聚類的新的聚類中心；最后，重復以上步驟，直到完成想要的迭代次數或者新的聚類中心與上一次的聚類中心相同時結束算法。

K-means聚類算法步驟可以簡單地描述如下：

輸入：數據集U，假設包含n個數據對象，每個數據對象包含c維屬性，要劃分的類別的數目是k。

輸出：聚類結果。

①從數據集U中隨機選取k個數據對象，作為初始聚類的中心點。

②按歐氏距離公式（1）計算其余各數據對象到聚類中心的距離，然后將各個數據對象劃分到離它們最近的那個中心點所屬類中。

③重新計算各個類的中心。

④比較與上次聚類的劃分是否有變化，如果沒變化，則聚類過程結束，輸出聚類結果；否則，返回步驟②繼續迭代，直到聚類劃分不再改變。

K-means聚類算法最常用的計算兩個數據對象間的距離度量為歐氏距離，定義如下：

1.2 加權系數

在統計學中，描述數據離散程度常用的指標有：標準差（Standard Deviation），方差（variance），變異系數（Coefficient of Variation）。考慮到平均絕對偏差（Mean Absolute Difference）也能從某種程度上反應數據的波動情況，因此，本文通過這四個指標來確定加權系數。

定義數據集中每維屬性的加權系數分別為1w，2w，...，cw（c為數據維度）。

標準差（standard deviation）就是方差的平方根：一組數據中的每一個數與這組數據的平均數的差的平方的和再除以數據的個數，取平方根即是。則加權系數為：

方差（variance）是各個數據與平均數之差的平方的和的平均數。則加權系數為：

變異系數（Coefficient of Variation）是標準差與其平均數的比，當需要比較兩組數據離散程度大小的時候，如果兩組數據的測量尺度相差太大，或者數據量綱的不同，直接使用標準差來進行比較不合適，此時就應當消除測量尺度和量綱的影響，而變異系數可以做到這一點。則加權系數為：

平均絕對偏差（Mean Absolute Difference）是所有單個數據與算術平均值的偏差的絕對值的平均。則加權系數為：

1.3 改進的K-means聚類算法

改進的K-means聚類算法步驟可以簡單地描述如下：

輸入：數據集U，假設包含n個數據對象，每個數據對象包含c維屬性，要劃分的簇的數目是k。

輸出：聚類結果。

①計算數據集U中各維屬性的權重系數jw。

②從數據集U中隨機選取k個數據對象，作為初始聚類的中心點。

③按加權歐氏距離公式（6）計算其余各數據對象到聚類中心的距離，然后將各個數據對象劃分到離它們最近的那個中心點所屬類中。

④重新計算各個類的中心。

⑤比較與上次聚類的劃分是否有變化，如果沒變化，則聚類過程結束，輸出聚類結果；否則，返回步驟③繼續迭代，直到聚類劃分不再改變。

加權歐氏距離，定義如下：

由此，我們可以得出改進K-means聚類算法的流程圖如下所示：

圖1 聚類算法的流程圖

2 實驗及比較分析

實驗數據集采用來自UCI數據集[7]中常用的2個聚類分析數據集iris和seeds。Iris數據集一共有150個數據，這些數據分為3類，每類分別包含50個數據，其中每個數據有4維屬性。Seeds數據集一共有210個數據，這些數據分為3類，每類分別包含70個數據，其中每個數據有7維屬性。

由于算法的初始中心點是隨機選取，因此聚類結果不穩定。通過多次實驗得到不同權重系數下最優的聚類結果。

表1 iris數據集聚類結果比較

注：表1和表2中的MAD、STD、VAR和CV分別代表平均絕對偏差、標準差、方差和變異系數。

從表1中可以看出四種加權算法的正確率都比傳統算法的高，而且以變異系數為加權系數使算法達到最高準確率。從表2中可以看到雖然以平均絕對偏差和方差為加權系數時準確率略有降低，但以標準差和變異系數為加權系數時準確率仍比傳統算法高。

3 結束語

本文提出在K-means聚類算法中對歐氏距離進行加權的四種方法，并通過實驗比較了四種加權方法的效果。實驗結果表明在K-means聚類算法中對歐氏距離進行合理的加權可以提高聚類結果的準確率并且以變異系數為加權系數是一個簡單有效的方法。相比其它的加權系數計算方法而言，這四種方法只依賴于要分析的數據本身，而不需要用戶輸入多余的參數，降低了用戶的使用難度。

[1]Macqueen J．Some Methods for Classification and Analy sis of MultiVariate Observations[C]// Proc．of，Berkeley Sympo sium on Mathematical Statistics and Probability，1967．

[2]鄭超，苗奪謙，王睿智．基于密度加權的粗糙K-均值聚類改進算法[J]．計算機科學，2009．

[3]王熙照，王亞東，湛燕，等．學習特征權值對K—均值聚類算法的優化[J]．計算機研究與發展，2003．

[4]陳森平，陳啟買．基于熵的K均值算法的改進[J]．廣東技術師范學院學報，2008．

[5]Sebastiani F．Machine Learning in Automated Text Cat egorization：a Bibliography[J]．Acm Computing Surveys，2002．

[6]馮榮耀，上官廷華，柳宏川．一種基于均方差屬性加權的K-means算法[J]．信息技術，2010．

[7]Blake C L，Merz C J．UCI repository of machine lear ning databases[DB]．1998．http：//www．ics．uci．edu/mlearn /MLR epository．html．