◆郭 靖

（中國人民公安大學(xué)信息工程與網(wǎng)絡(luò)安全學(xué)院 北京 100038）

對K-means聚類算法歐氏距離加權(quán)系數(shù)的研究

◆郭 靖

（中國人民公安大學(xué)信息工程與網(wǎng)絡(luò)安全學(xué)院 北京 100038）

K-means聚類算法廣泛應(yīng)用于模式識別、圖像處理和數(shù)據(jù)挖掘等領(lǐng)域中，有著簡潔高效等優(yōu)點(diǎn)。然而，傳統(tǒng)的K-means聚類算法在以歐氏距離為度量函數(shù)時(shí)簡單地把數(shù)據(jù)的各個(gè)屬性平等對待，忽略了不同屬性的重要性不同。本文結(jié)合統(tǒng)計(jì)學(xué)中描述數(shù)據(jù)離散程度的四種指標(biāo)提出四種計(jì)算加權(quán)系數(shù)的方法，并通過實(shí)驗(yàn)比較這四種加權(quán)系數(shù)對聚類結(jié)果準(zhǔn)確度的影響，以此來說明對歐氏距離加權(quán)的必要性和計(jì)算加權(quán)系數(shù)的簡單可行的方法。

K-means聚類算法；歐氏距離；加權(quán)系數(shù)

0 引言

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

大量的相關(guān)研究表明：對K-means聚類算法中的歐氏距離引入加權(quán)系數(shù)可以提高聚類準(zhǔn)確度。已知的加權(quán)方法包括：基于密度加權(quán)[2]，特征權(quán)值學(xué)習(xí)[3]，自適應(yīng)加權(quán)[4]等。在2002年，F(xiàn)abrizio[5]對已有加權(quán)系數(shù)的計(jì)算方法作了總結(jié)，分析了包括Document frequency，Information gain，Mutual information，Chi-square等多種加權(quán)系數(shù)計(jì)算方法的特性及適用領(lǐng)域。相關(guān)理論分析和實(shí)驗(yàn)結(jié)果指出每種計(jì)算方法在運(yùn)算速度和聚類結(jié)果的精度等方面各有優(yōu)劣。

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

1 相關(guān)工作

1.1 K-means聚類算法

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

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

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

輸出：聚類結(jié)果。

①從數(shù)據(jù)集U中隨機(jī)選取k個(gè)數(shù)據(jù)對象，作為初始聚類的中心點(diǎn)。

②按歐氏距離公式（1）計(jì)算其余各數(shù)據(jù)對象到聚類中心的距離，然后將各個(gè)數(shù)據(jù)對象劃分到離它們最近的那個(gè)中心點(diǎn)所屬類中。

③重新計(jì)算各個(gè)類的中心。

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

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

1.2 加權(quán)系數(shù)

在統(tǒng)計(jì)學(xué)中，描述數(shù)據(jù)離散程度常用的指標(biāo)有：標(biāo)準(zhǔn)差（Standard Deviation），方差（variance），變異系數(shù)（Coefficient of Variation）?？紤]到平均絕對偏差（Mean Absolute Difference）也能從某種程度上反應(yīng)數(shù)據(jù)的波動情況，因此，本文通過這四個(gè)指標(biāo)來確定加權(quán)系數(shù)。

定義數(shù)據(jù)集中每維屬性的加權(quán)系數(shù)分別為1w，2w，...，cw（c為數(shù)據(jù)維度）。

標(biāo)準(zhǔn)差（standard deviation）就是方差的平方根：一組數(shù)據(jù)中的每一個(gè)數(shù)與這組數(shù)據(jù)的平均數(shù)的差的平方的和再除以數(shù)據(jù)的個(gè)數(shù)，取平方根即是。則加權(quán)系數(shù)為：

方差（variance）是各個(gè)數(shù)據(jù)與平均數(shù)之差的平方的和的平均數(shù)。則加權(quán)系數(shù)為：

變異系數(shù)（Coefficient of Variation）是標(biāo)準(zhǔn)差與其平均數(shù)的比，當(dāng)需要比較兩組數(shù)據(jù)離散程度大小的時(shí)候，如果兩組數(shù)據(jù)的測量尺度相差太大，或者數(shù)據(jù)量綱的不同，直接使用標(biāo)準(zhǔn)差來進(jìn)行比較不合適，此時(shí)就應(yīng)當(dāng)消除測量尺度和量綱的影響，而變異系數(shù)可以做到這一點(diǎn)。則加權(quán)系數(shù)為：

平均絕對偏差（Mean Absolute Difference）是所有單個(gè)數(shù)據(jù)與算術(shù)平均值的偏差的絕對值的平均。則加權(quán)系數(shù)為：

1.3 改進(jìn)的K-means聚類算法

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

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

輸出：聚類結(jié)果。

①計(jì)算數(shù)據(jù)集U中各維屬性的權(quán)重系數(shù)jw。

②從數(shù)據(jù)集U中隨機(jī)選取k個(gè)數(shù)據(jù)對象，作為初始聚類的中心點(diǎn)。

③按加權(quán)歐氏距離公式（6）計(jì)算其余各數(shù)據(jù)對象到聚類中心的距離，然后將各個(gè)數(shù)據(jù)對象劃分到離它們最近的那個(gè)中心點(diǎn)所屬類中。

④重新計(jì)算各個(gè)類的中心。

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

加權(quán)歐氏距離，定義如下：

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

圖1 聚類算法的流程圖

2 實(shí)驗(yàn)及比較分析

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

由于算法的初始中心點(diǎn)是隨機(jī)選取，因此聚類結(jié)果不穩(wěn)定。通過多次實(shí)驗(yàn)得到不同權(quán)重系數(shù)下最優(yōu)的聚類結(jié)果。

表1 iris數(shù)據(jù)集聚類結(jié)果比較

注：表1和表2中的MAD、STD、VAR和CV分別代表平均絕對偏差、標(biāo)準(zhǔn)差、方差和變異系數(shù)。

從表1中可以看出四種加權(quán)算法的正確率都比傳統(tǒng)算法的高，而且以變異系數(shù)為加權(quán)系數(shù)使算法達(dá)到最高準(zhǔn)確率。從表2中可以看到雖然以平均絕對偏差和方差為加權(quán)系數(shù)時(shí)準(zhǔn)確率略有降低，但以標(biāo)準(zhǔn)差和變異系數(shù)為加權(quán)系數(shù)時(shí)準(zhǔn)確率仍比傳統(tǒng)算法高。

3 結(jié)束語

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

[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]鄭超，苗奪謙，王睿智．基于密度加權(quán)的粗糙K-均值聚類改進(jìn)算法[J]．計(jì)算機(jī)科學(xué)，2009．

[3]王熙照，王亞東，湛燕，等．學(xué)習(xí)特征權(quán)值對K—均值聚類算法的優(yōu)化[J]．計(jì)算機(jī)研究與發(fā)展，2003．

[4]陳森平，陳啟買．基于熵的K均值算法的改進(jìn)[J]．廣東技術(shù)師范學(xué)院學(xué)報(bào)，2008．

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

[6]馮榮耀，上官廷華，柳宏川．一種基于均方差屬性加權(quán)的K-means算法[J]．信息技術(shù)，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．