K平均演算法

維基百科,自由的百科全書
前往: 導覽搜尋

聚類分析是數據挖掘及機器學習領域內的重點問題之一,在數據挖掘、模式識別、決策支持、機器學習及圖像分割等領域有廣泛的應用,是最重要的數據分析方法之一。聚類是在給定的數據集合中尋找同類的數據子集合,每一個子集合形成一個類簇,同類簇中的數據具有更大的相似性。聚類演算法大體上可分為基於劃分的方法、基於層次的方法、基於密度的方法、基於網格的方法以及基於模型的方法。

k-means algorithm演算法是一種得到最廣泛使用的基於劃分的聚類演算法,把n個對象分為k個簇,以使簇內具有較高的相似度。相似度的計算根據一個簇中對象的平均值來進行。它與處理混合常態分佈最大期望演算法很相似,因為他們都試圖找到數據中自然聚類的中心。

演算法首先隨機地選擇k個對象,每個對象初始地代表了一個簇的平均值或中心。對剩餘的每個對象根據其與各個簇中心的距離,將它賦給最近的簇,然後重新計算每個簇的平均值。這個過程不斷重複,直到準則函數收斂。

V = \sum_{i=1}^{k} \sum_{x_j \in S_i} (x_j - \mu_i)^2

它假設對象屬性來自於空間向量,並且目標是使各個群組內部的均方誤差總和最小。假設有k個群組Si, i=1,2,...,k。μi是群組Si內所有元素xj的重心,或叫中心點。

歷史[編輯]

術語「k-means」最早是由James MacQueen在1967年提出的,這一觀點可以追溯到1957年 Hugo Steinhaus所提出的想法。1957年,斯圖亞特·勞埃德最先提出這一標準演算法,當初是作為一門應用於脈碼調製的技術,直到1982年,這一演算法才在貝爾實驗室被正式提出。1965年, E.W.Forgy發表了一個本質上是相同的方法,1975年和1979年,Hartigan和Wong分別提出了一個更高效的版本。

演算法描述[編輯]

輸入:簇的數目k;包含n個對象的數據集D。

輸出:k個簇的集合。

方法:

  1. 從D中任意選擇k個對象作為初始簇中心;
  2. repeat;
  3. 根據簇中對象的均值,將每個對象指派到最相似的簇;
  4. 更新簇均值,即計算每個簇中對象的均值;
  5. 計算準則函數;
  6. until準則函數不再發生變化。

演算法的性能分析[編輯]

1)優點
(1)k-平均演算法是解決聚類問題的一種經典演算法,演算法簡單、快速。
(2)對處理大數據集,該演算法是相對可伸縮的和高效率的,因為它的複雜度大約是O(nkt),其中n是所有對象的數目,k是簇的數目,t是迭代的次數。通常k<<n。這個演算法經常以局部最優結束。
(3)演算法嘗試找出使平方誤差函數值最小的k個劃分。當簇是密集的、球狀或團狀的,而簇與簇之間區別明顯時,它的聚類效果很好。
2)缺點
(1)k-平均方法只有在簇的平均值被定義的情況下才能使用,不適用於某些應用,如涉及有分類屬性的數據不適用。
(2)要求使用者必須事先給出要生成的簇的數目k。
(3)對初值敏感,對於不同的初始值,可能會導致不同的聚類結果。
(4)不適合於發現非凸面形狀的簇,或者大小差別很大的簇。
(5)對於"噪聲"和孤立點數據敏感,少量的該類數據能夠對平均值產生極大影響。

演算法的改進[編輯]

針對演算法存在的問題,對K-means演算法提出一些改進:一是數據預處理,二是初始聚類中心選擇,三是迭代過程中聚類種子的選擇。

首先對樣本數據進行正規化處理,這樣就能防止某些大值屬性的數據左右樣本間的距離。給定一組含有n個數據的數據集,每個數據含有m個屬性,分別計算每一個屬性的均值、標準差對每條數據進行標準化。

其次,初始聚類中心的選擇對最後的聚類效果有很大的影響,原K-means演算法是隨機選取k個數據作為聚類中心,而聚類的結果要是同類間儘可能相似,不同類間儘可能相異,所以初始聚類中心的選取要儘可能做到這一點。採用基於距離和的孤立點定義來進行孤立點的預先篩選,並利用兩兩數據之間的最大距離在剩餘數據集合中尋找初始聚類中心。但對於實際數據,孤立點個數往往不可預知。在選擇初始聚類中心時,先將孤立點納入統計範圍,在樣本中計算對象兩兩之間的距離,選出距離最大的兩個點作為兩個不同類的聚類中心,接著從其餘的樣本對象中找出已經選出來的所有聚類中心的距離和最大的點為另一個聚類中心,直到選出k個聚類中心。這樣做就降低了樣本輸入順序對初始聚類中心選擇的影響。

聚類中心選好以後,就要進行不斷的迭代計算,在K-means演算法中,是將聚類均值點(類中所有數據的幾何中心點)作為新的聚類種子進行新一輪的聚類計算,在這種情況下,新的聚類種子可能偏離真正的數據密集區,從而導致偏差,特別是在有孤立點存在的情況下,有很大的局限性。在選擇初始中心點時,由於將孤立點計算在內,所以在迭代過程中要避免孤立點的影響。這裡根據聚類種子的計算時,採用簇中那些與第k-1輪聚類種子相似度較大的數據,計算他們的均值點作為第k輪聚類的種子,相當於將孤立點排除在外,孤立點不參與聚類中心的計算,這樣聚類中心就不會因為孤立點的原因而明顯偏離數據集中的地方。在計算聚類中心的時候,要運用一定的演算法將孤立點排除在計算均值點那些數據之外,這裡主要採用類中與聚類種子相似度大於某一閾值的數據組成每個類的一個子集,計算子集中的均值點作為下一輪聚類的聚類種子。為了能讓更多的數據參與到聚類中心的計算種去,閾值範圍要包含大多數的數據。在第k-1輪聚類獲得的類,計算該類中所有數據與該類聚類中心的平均距離S,選擇類中與聚類種子相似度大於2S的數據組成每個類的一個子集,以此子集的均值點作為第k輪聚類的聚類種子。在數據集中無論是否有明顯的孤立點存在,兩倍的平均距離都能包含大多數的數據。

對孤立點的改進—基於距離法[編輯]

經典k均值演算法中沒有考慮孤立點。所謂孤立點都是基於距離的, 是數據U集中到U中最近鄰居的距離最大的對象, 換言之, 數據集中與其最近鄰居的平均距離最大的對象。針對經典k均值演算法易受孤立點的影響這一問題, 基於距離法移除孤立點, 具體過程如下:

首先掃描一次數據集, 計算每一個數據對象與其臨近對象的距離, 累加求其距離和, 並計算出距離和均值。如果某個數據對象的距離和大於距離和均值, 則視該點為孤立點。把這個對象從數據集中移除到孤立點集合中, 重複直到所有孤立點都找到。最後得到新的數據集就是聚類的初始集合。

對隨機選取初始聚類中心的改進[編輯]

經典k均值演算法隨機選取k個點作為初始聚類中心進行操作。由於是隨機選取, 則變化較大, 初始點選取不同, 獲得聚類的結果也不同。並且聚類分析得到的聚類的準確率也不一樣。對k均值演算法的初始聚類中心選擇方法—隨機法進行改進, 其依據是聚類過程中相同聚類中的對象是相似的, 相異聚類中的對象是不相似的。因此提出了一種基於數據對象兩兩間的距離來動態尋找並確定初始聚類中心的思路, 具體過程如下:

首先整理移除孤立點後的數據集U,記錄數據個數y,令m=1。比較數據集中所有數據對象兩兩之間的距離。找出距離最近的2個數據對象形成集合Am;比較Am中每一個數據對象與數據對象集合U中每一個對象的距離,在U中找出與Am 中最近的數據對象,優先吸收到Am 中,直到Am 中的數據對象個數到達一定數值,然後令m=m+1。再從U中找到對象兩兩間距離最近的2個數據對象構成Am,重複上面的過程,直到形成k個對象集合。這些集合內部的數據是相似的,而集合間是相異的。 可以看出,這種聚類方法同時滿足以下2個條件:①每個組至少包含一個數據對象; ②每個數據對象必須屬於且僅屬於一個組。即數據對象Xi ∈Ai ,且U={{A1 ∪A2 ∪…∪Ak} ∪A0} ,且Ai ∩Aj =Φ。最後對k個對象集合分別進行算術平均,形成k個初始聚類中心。

參考資料[編輯]

  • J. B. MacQueen (1967): "Some Methods for classification and Analysis of Multivariate Observations", Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297
  • J. A. Hartigan (1975) "Clustering Algorithms". Wiley.
  • J. A. Hartigan and M. A. Wong (1979) "A K-Means Clustering Algorithm", Applied Statistics, Vol. 28, No. 1, p100-108.
  • D. ArthurS. Vassilvitskii (2006): "How Slow is the k-means Method?," Proceedings of the 2006 Symposium on Computational Geometry (SoCG).


外部連結[編輯]

參見[編輯]