不同的K-means聚類算法比較研究

袁健斌 樊宇翊 伍興國

（1.東莞職業(yè)技術(shù)學(xué)院 廣東省東莞市 523808 2.懷化學(xué)院 湖南省懷化市 418000）

1 引言

聚類分析作為一種無監(jiān)督的機器算法，其中將大量的數(shù)據(jù)分類為在數(shù)據(jù)對象之間具有相似性的聚類，在探索性數(shù)據(jù)分析中是一種非常實用的工具，因此研究人員使用它作為分析大型數(shù)據(jù)的寶貴工具。聚類相當(dāng)于分組技術(shù)：其目的在于使得組與組之間有較大的差異，而每組內(nèi)部之中差異較小。目前已經(jīng)設(shè)計了不同技術(shù)的各種聚類算法，并將其成功應(yīng)用于各種數(shù)據(jù)挖掘問題。這些聚類算法會產(chǎn)生高效和高質(zhì)量的類簇，聚類結(jié)果主要取決這幾個因素；相似度、初始點和算法的不同選擇。

2 相似度的選擇

聚類分析的目的在于將相似的數(shù)據(jù)點盡可能地分為一個類，而將差異較大的點盡量分開，那么如何度量兩個數(shù)據(jù)點的相似度就顯得尤為重要。目前相似度的計算主要通過距離和相似系數(shù)來進(jìn)行，需要注意的是，根據(jù)距離來聚類一般是絕對聚類，而根據(jù)相似系數(shù)來聚類一般是相對聚類。如同分析客戶偏好一樣，如果根據(jù)偏好的大小來分析，一般按絕對值來聚類，可以采用距離的方式，而根據(jù)偏好的比例來分析，一般是按照相對值來分析，即采用相似系數(shù)來聚類。

2.1 基于距離的度量

一般地，計算兩點的距離是最為常見的相似度度量方法，通常假設(shè)數(shù)據(jù)空間上的點(a,b)之間的相似度為Sim(a,b)，如果數(shù)據(jù)點(a,b)的距離為(a,b)，則可以采用Sim(a,b)=1/(1+d(a,b))得到它們之間相似度，如果兩點距離d(a,b)=0，則兩點相似度Sim(a,b)=1。兩點距離d(a,b)的值較大，那么它們的相似度就小。常用的距離度量方式如下：

（1）歐氏距離：在數(shù)學(xué)上是通過計算多維空間上兩點的距離。如果兩個點的絕對值比較接近，那么兩點距離較短，兩個點的相似度就越高。

（2）其他距離：在數(shù)學(xué)上，除了歐氏距離外，還存在著其他的度量方式。如曼哈頓距離，其計算公式為：如果把歐氏距離看成是空間兩個點的直線距離，那么曼哈頓距離可以理解為空間兩個點的折線距離。另外還有切比雪夫距離，也稱為最大距離，其計算公式為：很明顯這些距離的度量更容易受到量綱的影響，因此在實際運用中并不多見。

2.2 基于相似系數(shù)的度量

我們之所以將基于相似系數(shù)的聚類稱為相對聚類，這是因為將某個樣本點各個維度的數(shù)據(jù)放大或者縮小m 倍，并不會改變他們之間的距離，即d(ma,b)=d(a,b)，這一等式在基于距離聚類時并不成立，因為距離聚類是依據(jù)樣本點的數(shù)據(jù)絕對大小進(jìn)行的。即使對樣本點的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化，也是依據(jù)某個維度進(jìn)行標(biāo)準(zhǔn)化，選擇的是某個維度上的均值和方差，在數(shù)據(jù)表上表現(xiàn)為縱向的處理。而基于相似系數(shù)的聚類是某個數(shù)據(jù)點在不同維度上進(jìn)行的，統(tǒng)計的是這個數(shù)據(jù)點的均值和方差（在不同維度上），在數(shù)據(jù)表上表現(xiàn)為橫向的處理，兩者存在本質(zhì)的區(qū)別。常見的基于相似系數(shù)的度量方式有：夾角余弦相似度和Pearson 相關(guān)系數(shù)。事實上，可以證明兩者是等價的。這種度量方式著重各個維度上相對值，而非絕對值，因此在分析用戶習(xí)慣、行為和偏好上非常有用。到底選擇哪種度量方式，要依據(jù)業(yè)務(wù)目標(biāo)來定，而不是玩一種數(shù)學(xué)游戲。

3 初始點的選擇

在K-means 聚類算法還需指定聚類數(shù)和初始點，初始點也稱為中心點或質(zhì)心（centroid）。傳統(tǒng)的K-means 算法假定質(zhì)心的初始數(shù)量是事先已知的，這種對簇數(shù)的依賴以及質(zhì)心的初始選擇會影響算法的性能和準(zhǔn)確性。如果初始點的選擇不恰當(dāng)，將會導(dǎo)致聚類的結(jié)果是局部最優(yōu)，而這樣的局部最優(yōu)解可能存在很多個。一般常用的確定初始中心點方法如下：

3.1 隨機選取

最簡單的方法是隨機選擇K 個點作為初始的類簇中心點，有時候可能選取的點較為接近，因此該方法在有些情況下的效果較差。聚類的結(jié)果與初始的類簇中心點有關(guān)，而初始點選擇具有隨機性，因此每次聚類的結(jié)果也初始中心點的不同而大相徑庭。

3.2 選擇遠(yuǎn)距離點

選取距離盡量遠(yuǎn)的K 個樣本點作為初始的類簇中心點：隨機選取第一個樣本c1作為第一個中心點，遍歷所有樣本選取離c1最遠(yuǎn)的樣本c2為第二個中心點，以此類推，選出K 個初始中心點，其中心思想為使得初始的聚類中心之間相互距離盡可能遠(yuǎn)。

3.3 預(yù)處理

先對數(shù)據(jù)用層次聚類算法或者Canopy 算法進(jìn)行聚類，得到K個簇之后，從K 個類簇別中分別隨機選取K 個點，該點可以是該類簇的中心點，或者是距類簇中心點（均值）最近的那個點，來作為K-means 的初始聚類中心點。

3.4 抽樣法

這種方法是對數(shù)據(jù)按照某種抽樣形式進(jìn)行，常見的有等距抽樣、分層抽樣等。如等距抽樣是指定將觀察值1、1 + K，1 + 2K，...分配給第一組，將觀察值2、2 + K，2 + 2K，...分配給第二組，依此類推來形成K 個分區(qū)或者群組。這K 個組的均值或中位數(shù)將用作初始的類簇中心點。也可以將數(shù)據(jù)劃分為K 個幾乎相等的分區(qū)。即將第一個到第N / K 個觀察值分配給第一組，將第二個N / K 觀察值分配給第二組，依此類推。這K 個組的均值或中位數(shù)將用作初始的類簇中心點。也可以提供了一個初始分組變量，按該變量劃分?jǐn)?shù)據(jù)集為K 個組，那么這K 個組的均值或中位數(shù)將用作初始類簇的中心點。

由于中心點用均值來代表，容易受到“噪聲”（奇異點、離群點）干擾，影響聚類的結(jié)果，因此提出了K-中心點聚類算法（K-mediods），它不是采用該類簇內(nèi)樣本的均值來計算，而是從聚類的樣本點中選取一個，使得在該類簇內(nèi)其余樣本點到這個樣本點距離之和最小，并將這個樣本點定義為類簇的中心點。這樣即使當(dāng)聚類的樣本點中有“噪聲”時，也不會受到噪聲異常維度的干擾，這樣所得質(zhì)點和實際質(zhì)點位置偏差不大，從而使類簇發(fā)生“畸變”的可能性不大。這種方法改善了 K-means 對“噪聲”的敏感，但是計算復(fù)雜度上升。

4 K-means聚類算法的思想

B.MacQueen 首先提出了K-means 聚類算法，作為一種經(jīng)典的聚類算法，目前已有許多應(yīng)用。K-means 算法的核心思想是將數(shù)據(jù)分為多個類，使得每個聚類中的數(shù)據(jù)與類簇中心之間的距離之和最小。K-means 算法是一種基于點的快速迭代聚類算法，最初將類簇中心放置在任意位置開始，然后在每一步迭代過程中，通過移動類簇中心以最大程度地減少聚類錯誤。該方法的主要缺點在于其對類簇中心初始位置的敏感性。因此，為了K-means 算法能夠獲得接近最佳的解決方案，可能需要運行多次，而每次運行的類簇中心的初始位置將有所不同。

在給定的觀測數(shù)據(jù)集(x1,x2,…,xn)，每一個觀測值是一個d 維的實數(shù)向量，K-Means 算法是將這些數(shù)據(jù)集劃分為指定的K 個集合{S1,S1,…,Sk}，這里的K＜n。極小化以下目標(biāo)函數(shù)：

這里的ci是集合Si的中心，一般定義為均值。它的具體算法如下：

（1）從n 個數(shù)據(jù)對象中選擇K 個對象作為初始類簇中心。

（2）根據(jù)每個類簇對象的中心，計算出每個對象與中心對象之間的距離，根據(jù)最小距離重新分類對象。

（3）重新計算每個類簇的中心點。

（4）計算目標(biāo)函數(shù)，如果滿足一定條件，則算法終止；

如果不滿足條件，則返回到步驟（2）。

由于K-Means 的吸引力在于其簡單性和局部最小收斂性，但它卻具有諸如以下的主要缺點：它在計算上的伸縮性比較差，這意味著它可能收斂較慢，并且在完成每次迭代所需的時間方面伸縮性很差，可能需要運行時間較長。

5 不同算法比較

隨著計算能力的增長，大型數(shù)據(jù)集的出現(xiàn)也隨之增長，K-means聚類在很多研究領(lǐng)域的分析和數(shù)據(jù)挖掘進(jìn)行數(shù)據(jù)探索非常有用。首先，其易實現(xiàn)、計算效率和低內(nèi)存消耗使K-means 聚類技術(shù)非常流行。與其他聚類技術(shù)相比，如連接模型，如層次聚類方法等，這類算法的優(yōu)點在于可以在數(shù)據(jù)中搜索未知數(shù)量的聚類，但由于是基于相異度矩陣（存儲n 個對象兩兩之間的近似性，表現(xiàn)形式是一個n*n 維的矩陣），計算成本非常高。當(dāng)然也還包括期望最大化算法和密度模型等分布模型等聚類算法。K-means 聚類的一個次要目標(biāo)是降低數(shù)據(jù)的復(fù)雜度。最后，K-means 聚類算法作為計算成本更高的算法（機器學(xué)習(xí)中的學(xué)習(xí)向量量化和混合高斯模型）的初始步驟，以數(shù)據(jù)的近似分類作為起點，并降低了數(shù)據(jù)集中存在的噪聲。

通常并不存在絕對的優(yōu)良聚類算法，這是因為聚類算法的性能依賴于數(shù)據(jù)集的特征（樣本容量和變量個數(shù)），因此很多學(xué)者建議在給定的數(shù)據(jù)集上嘗試不同的聚類算法，以便獲得更優(yōu)的聚類結(jié)果。K-means 聚類可以看作是將整個空間分割成子空間單元，因此類簇又定義為子空間。對于每兩個中心點，假設(shè)有一條線來連接它們。那么對這條連線的中點做垂線，這條垂線依賴于維度，它有可能是一條直線，或者是一個平面，也或者是一個超平面，把整個空間分為兩個獨立的子空間。因此，聚類的本質(zhì)是將整個空間劃分為K 個子空間，那么ci本質(zhì)上是所有子空間所包含元素的中心點。本節(jié)將簡要剖析三種不同的K-means 算法：Forgy / Lloyd 算法，MacQueen 算法和Hartigan&Wong 算法，來分析簡單但功能強大的K-means 聚類技術(shù)。

5.1 Forgy / Lloyd算法

Lloyd 算法(1957年)和Forgy 的算法(1965年)都是批量算法中心模型。這個中心是指一個類的幾何中心，一般認(rèn)為是一個類的平均值，這種批量算法是很適合于分析大型數(shù)據(jù)集。這是因為增量式的K-means 算法需要為每一個案例存儲子空間類別，當(dāng)一個案例被處理時，需要對這兩個子空間重新計算中心位置，這樣的計算在大型數(shù)據(jù)集上代價是比較昂貴。Lloyd算法與Forgy算法的區(qū)別在于：Lloyd 算法考慮的數(shù)據(jù)是離散的，而Forgy 算法考慮數(shù)據(jù)是連續(xù)的，除此以外，它們的程序完全相同。在所有算法中，這兩者是最簡單和最容易實現(xiàn)的。對于含有n 個案例集，聚類算法就是要找到K 個中心位置，使得下面的目標(biāo)函數(shù)達(dá)到極小值：

其中ρ(x)為概率密度函數(shù)，d 為距離函數(shù)。需要注意的是：如果概率密度函數(shù)ρ(x)是未知的，那么需要從數(shù)據(jù)中大致推斷出來。

Lloyd 算法的第一步是選擇和確認(rèn)K 個初始中心?？梢酝ㄟ^先驗經(jīng)驗知識來指定它們，也可以通過數(shù)據(jù)集的隨機選擇。一旦選擇了初始中心點，就會進(jìn)行以下兩步迭代：第一步，每個案例根據(jù)度量距離的遠(yuǎn)近將其分配到某一個子空間，所有分配到這個子空間的點都視作這個子空間的一部分。第二步是利用子空間內(nèi)部這些點上的數(shù)據(jù)來計算新的中心值以便更新中心位置。這兩步迭代是重復(fù)，在研究者決定的容忍度標(biāo)準(zhǔn)內(nèi)，中心點位置幾乎沒有變化，或直到?jīng)]有案例變化為止。Lloyd 算法偽代碼如下：

1-確定聚類的個數(shù)K

2-選擇和確定要使用的距離度量

3-選擇和確定初始中心點的方法

4-確定初始中心點

5-當(dāng)d(xij,ci)＞閾值時

a.對于所有的i 點

i.根據(jù)距離將第i 個點分配到最近的類別

b.重新計算中心值

5.2 MacQueen算法

MacQueen 算法（1967年）是一種迭代算法（增量）算法。與Forgy/Lloyd 算法的主要區(qū)別是：當(dāng)每個點改變子空間時，受影響的兩個子空間的中心點都會重新計算，并且完整循環(huán)一次后，需再次計算每個子空間的中心點。而在首次循環(huán)遍歷時，中心點是與Forgy/Lloyd 算法的初始化是相同的。當(dāng)依次遍歷每一個點時，如果它離它當(dāng)前所屬子空間的中心點是最近的，那么不做任何改變。如果它與另一個子空間的中心是最近的，那么它將會被重新分配到另一個子空間去，這時舊的和新的子空間都重新計算中心位置?？偟膩碚f，當(dāng)樣本進(jìn)行一次循環(huán)時，F(xiàn)orgy/Lloyd 算法的每一個子空間的中心位置是不變的，MacQueen 算法則不斷變化子空間的中心位置。而當(dāng)樣本遍歷結(jié)束后，兩個算法都需要重新再次計算每個子空間的中心位置。顯然，MacQueen 算法的效率要高Forgy/Lloyd 算法，因為它更新子空間中心點的頻率更高，而且通常還需要進(jìn)行一次完整的遍歷以便它是收斂的。MacQueen 算法偽代碼如下：

1-確定聚類的個數(shù)K

2-選擇和確定要使用的距離度量

3-選擇和確定初始中心點的方法

4-確定初始中心點

5-當(dāng)d(xij,ci)＞閾值時

a.對于

i.根據(jù)距離將第i 個點分配到最接近的群組，

ii.重新計算兩個受影響類的中心點

b.重新計算所有類的中心值

5.3 Hartigan&Wong算法

該算法劃分?jǐn)?shù)據(jù)空間是基于局部最優(yōu)的組內(nèi)誤差平方和(SSE)。對于某個數(shù)據(jù)點，即使它目前屬于最接近中心點的子空間，它仍然可能將一個數(shù)據(jù)點分配到另一個子空間去，因為這樣做可以使得各個類簇的總和達(dá)到最小化。該算法初始化為與Forgy/Lloyd 算法的方式相同，即將其分配到離它們最近中心點的子空間去，而中心點以該組數(shù)據(jù)點的平均值計算。該算法的迭代過程如下：如果中心點已經(jīng)在最后一步更新，對于子空間的每個數(shù)據(jù)點，計算當(dāng)前子空間的包含數(shù)據(jù)點的平方和（SSE1，假設(shè)子空間號i=1），再將這個數(shù)據(jù)點移到另外一個子空間去，計算這個子空間的包含這個數(shù)據(jù)點的平方和（SSE2，對所有i ≠1），如果某一個子空間的SSE2 小于等于當(dāng)前的類簇（SSE1），那么就將這個數(shù)據(jù)點分配到新的子空間去。其數(shù)學(xué)表達(dá)式如下：

循環(huán)往復(fù)，直到?jīng)]有數(shù)據(jù)點變換子空間為止。Hartigan 和Wong 算法偽代碼如下：

1-確定聚類的個數(shù)K

2-選擇和確定要使用的距離度量

3-選擇和確定初始中心點的方法

4-確定初始中心點

5-將案件分配到最近的中心點

6-計算子空間的中心點

7-對于第j ＜= nb 個子空間，如果中心點j 最后更新一次迭代

a.計算子空間的SSE1

b.對于這個子空間的每一個i 數(shù)據(jù)點

i.將這個數(shù)據(jù)點移到新的子空間t，計算這個子空間SSE2（t!=j）；

ii.如果SSE2＜ SSE1，則將改變這個數(shù)據(jù)點的子空間。否則保持不變。