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

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

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

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

1 概述

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

2 聚類算法介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在采用標(biāo)準(zhǔn)的余弦距離度量公式得到向量之間的距離后，為使同一簇中數(shù)據(jù)點(diǎn)間的距離更小，不同簇中數(shù)據(jù)點(diǎn)間的距離更大，當(dāng)距離D取值為0～0.5時(shí)，通過對(duì)距離平方減小同一簇中數(shù)據(jù)點(diǎn)之間的距離，當(dāng)距離D取值大于0.5時(shí)，通過對(duì)距離開平方增大不同簇?cái)?shù)據(jù)點(diǎn)之間的距離。采用改進(jìn)的余弦距離度量公式后，可使得簇內(nèi)數(shù)據(jù)點(diǎn)間距離減小，簇間數(shù)據(jù)點(diǎn)間距離增加，從而達(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.