改進(jìn)K—Means算法的探討與分析

曹衛(wèi)華+喬平安

摘要：隨著人類社會的不斷進(jìn)步和發(fā)展，K-Means作為聚類中較常用的算法，得到廣泛的應(yīng)用。該文探討了K-Means和Canopy算法的執(zhí)行過程，針對K-Means及Canopy的優(yōu)缺點，提出了改進(jìn)的K-Means算法。算法中將Canopy作為K-Means的預(yù)處理，通過Canopy得到聚類中簇的個數(shù)、初始化的聚類中心，同時排除掉“噪聲”以及孤立點帶來的影響，將Canopy的結(jié)果用于K-Means，進(jìn)一步增強聚類性能，減少計算量。另外，針對K-Means中使用的距離度量公式，提出了改進(jìn)的余弦距離度量公式，使得簇內(nèi)數(shù)據(jù)點間的距離減小，簇間數(shù)據(jù)點間的距離增大，提高聚類質(zhì)量。

關(guān)鍵詞：聚類；K-Means；Canopy；余弦；距離度量公式；改進(jìn)

中圖分類號：TP319 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）06-0200-02

1 概述

聚類分析作為一項重要的人類社會活動，廣泛應(yīng)用于市場研究、模式識別、數(shù)據(jù)分析和圖像處理等諸多領(lǐng)域。在童年時期，我們通過不斷改進(jìn)潛意識聚類方案學(xué)習(xí)如何區(qū)分貓和狗，或動物和植物。通過自動化聚類，可以識別對象空間中的密集和稀疏區(qū)域，從而發(fā)現(xiàn)數(shù)據(jù)屬性中的總體分布模式和有趣的相關(guān)性。在商業(yè)活動中，聚類分析可以幫助營銷人員在其客戶群中發(fā)現(xiàn)不同的群體，并基于購買模式來表征客戶群。在生物學(xué)中，聚類分析可以將植物和動物區(qū)分開，將具有相似功能的基因進(jìn)行分類，并獲得對人群內(nèi)在結(jié)構(gòu)的了解。在未來的工作和生活中，聚類將繼續(xù)發(fā)揮越來越舉足輕重的作用，帶給我們前所未有的幫助。

2 聚類算法介紹

聚類技術(shù)中存在著許多算法，但是難以提供一種清晰的方法分類各種聚類算法，因為這些分類都可能重疊，使得一個聚類方法屬于許多類別中。然而，呈現(xiàn)不同聚類方法的相對分類組織卻是有用的。一般來說，主要的聚類方法可以分類為分區(qū)方法、分層方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法等，很多聚類算法的共同點是需要選擇度量距離的方法，可以根據(jù)向量空間和建模數(shù)據(jù)的性質(zhì)采用多種方法測量向量之間的距離。K-Means則是分區(qū)方法中較為常見的一種算法，其流程如圖1所示。

K-Means算法的主要不足體現(xiàn)在：

1）該算法必須事先確定簇的個數(shù)k，即要求用戶事先知道數(shù)據(jù)集中數(shù)據(jù)的一些特點。但很多時候用戶對數(shù)據(jù)集是不了解的，并不知道數(shù)據(jù)集應(yīng)該聚類成多少個簇才最合適。聚類結(jié)果對初始聚類個數(shù)比較敏感，對于不同的初始值，可能會導(dǎo)致不同的聚類結(jié)果。

2）該算法經(jīng)常以局部最優(yōu)結(jié)束，有時很難達(dá)到全局最優(yōu)。

3）該算法對初始化的聚類中心點較為敏感，對于不同的初始值，其聚類結(jié)果也可能有很大的差異?？赏ㄟ^多設(shè)置不同的初始值，對比最后的聚類結(jié)果，直到所有結(jié)果趨于穩(wěn)定來改進(jìn)這一不足，但該做法比較耗時，且浪費資源。

4）該算法只能發(fā)現(xiàn)球狀簇，其他形狀的簇較難發(fā)現(xiàn)。

5）該算法只有在簇的平均值被定義的情況下才能使用，這對于處理符號屬性的數(shù)據(jù)不適用。另外，“噪聲”和孤立點數(shù)據(jù)對聚類的結(jié)果影響也比較大，因為少量的該類數(shù)據(jù)可能對平均值產(chǎn)生極大的影響。

Canopy算法常作為K-Means算法的預(yù)處理，用于初始化聚類中心。Canopy聚類嘗試通過將聚類過程劃分為兩個子過程來加速維度較高、基數(shù)較大的數(shù)據(jù)集的聚類。首先，通過選擇一個簡單、快捷的距離度量公式和兩個閾值T1和T2，其中T1> T2，將數(shù)據(jù)集劃為多個子集成為“canopy”，各子集之間可能存在重疊部分。然后將所有數(shù)據(jù)點添加到一個list中，并隨機選擇list中的一個點。迭代計算list中剩余點與初始化點之間的距離。如果距離在T1內(nèi)，則該點將添加到該canopy。此外，如果距離在T2內(nèi)，則將該點從list中移除。該算法重復(fù)迭代，直到list為空[1]。其次，通過使用一個精準(zhǔn)、嚴(yán)密的距離計算方法來計算出現(xiàn)在第一步中同一個canopy的所有數(shù)據(jù)向量的距離。

Cnaopy聚類能幫助用戶在使用K-Means聚類時估計k值。對T1、T2給定一個合適的閾值，Canopy聚類將會找到合適數(shù)量的canopy。如上所述，在K-Means聚類中，這些可用作初始質(zhì)心。在Canopy聚類中，因為在第一步時將數(shù)據(jù)集簡單地分為多個canopy，從而使得canopy內(nèi)部的聚類速度明顯提高。Canopy算法的優(yōu)點主要體現(xiàn)在：

1）K-Means算法中孤立點和“噪聲”點對聚類結(jié)果有很大的影響。而在Canopy算法中，經(jīng)過第一步將所有的數(shù)據(jù)點劃分到一個或多個canopy中，可通過直接去掉數(shù)據(jù)點較少的canopy來排除孤立點或“噪聲”帶來的干擾。

2）Canopy算法通過第一步的粗糙距離計算方法把數(shù)據(jù)劃入不同的可重疊的子集中，接著只對同一個重疊子集中的樣本數(shù)據(jù)向量進(jìn)行計算，大大減少了需要計算距離的樣本數(shù)量，提高聚類效率。

3 改進(jìn)K-Means算法

綜上所述，可以將Canopy算法作為K-Means算法的預(yù)處理，通過Canopy算法的第一階段得到若干個canopy，將canopy的個數(shù)作為K-Means算法中初始化簇的個數(shù)，再將每個canopy的中心點作為K-Means算法的初始化聚類中心，并通過去掉含有極少數(shù)據(jù)點的canopy來排除可能存在的“噪聲”或孤立點。既可以保證算法的準(zhǔn)確性，又可以增加計算效率，減少計算時間。

在K-Means算法中主要通過距離度量公式計算簇的質(zhì)心與數(shù)據(jù)向量之間的距離將各個數(shù)據(jù)點劃分到距離最近的簇中，從而實現(xiàn)聚類。因此，距離度量公式的選擇在聚類中起著舉足輕重的作用，直接影響著聚類的質(zhì)量。在距離度量的各種公式中，歐式距離、平方歐式距離、余弦距離、曼哈頓距離以及Jaccard距離等較為常用。實驗證明在K-Means算法中采用Jaccard距離度量公式可取得較好的結(jié)果[2]，特別是針對高維數(shù)據(jù)集使用歐氏距離可使聚類的性能提高10～20倍[3]。相對于歐式距離，在K-Means中使用余弦計算公式可取得更好的效果[4]。在本文中提出另一種改進(jìn)的余弦距離計算公式，該公式可使得同一簇內(nèi)各個數(shù)據(jù)點之間的距離盡可能達(dá)到最小，不同簇內(nèi)各個數(shù)據(jù)點之間的距離達(dá)到最大，提高聚類的精確度。

余弦相似性是通過計算兩個向量之間夾角的余弦值來表示的。夾角為0°的余弦值為1，夾角為90°的余弦值為0，因此兩個向量之間相似度取值為-1～1。具有相同方向夾角為0°的兩個向量余弦相似度為1，夾角為90°的兩個向量之間的相似度為0，具有相反方向夾角為180°的兩個向量余弦相似度為-1。余弦值計算取決于向量之間的方向與向量之間夾角的大小無關(guān)[4]。余弦相似性計算經(jīng)常被用于真實的向量空間，它的取值范圍為[-1，1]。通過觀察兩個向量之間夾角的方向而不是夾角的大小來計算向量之間的余弦相似度，給定向量空間中的兩個向量，它們之間的余弦相似性表示如下：

根據(jù)上述公式，余弦相似性的取值范圍為[-1，1]。以同樣的方式，采用上述公式計算余弦相似性。在本文中向量之間的余弦值就是向量之間的距離測量標(biāo)準(zhǔn)，所以余弦值的范圍[-1，1]也是距離D的變化范圍。

在采用標(biāo)準(zhǔn)的余弦距離度量公式得到向量之間的距離后，為使同一簇中數(shù)據(jù)點間的距離更小，不同簇中數(shù)據(jù)點間的距離更大，當(dāng)距離D取值為0～0.5時，通過對距離平方減小同一簇中數(shù)據(jù)點之間的距離，當(dāng)距離D取值大于0.5時，通過對距離開平方增大不同簇數(shù)據(jù)點之間的距離。采用改進(jìn)的余弦距離度量公式后，可使得簇內(nèi)數(shù)據(jù)點間距離減小，簇間數(shù)據(jù)點間距離增加，從而達(dá)到改善簇的質(zhì)量，提高聚類準(zhǔn)確性的目的。

參考文獻(xiàn)：

[1] Mccallum A， Nigam K， Ungar L H. Efficient clustering of high-dimensional data sets with application to reference matching[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2000：169-178.

[2] Shameem M U S， Ferdous R. An efficient k-means algorithm integrated with Jaccard distance measure for document clustering[C]// Asian Himalayas International Conference on Internet， 2009. Ah-Ici. IEEE， 2009：1-6.

[3] Kanungo T， Mount D M， Netanyahu N S， et al. An efficient k-means clustering algorithm： analysis and implementation[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2002， 24（7）：881-892.

[4] Strehl E， Ghosh J， Mooney R. Impact of Similarity Measures on Web-page Clustering[C]// 2001：58-64.