k-means算法原理以及數(shù)學知識

摘要

在大數(shù)據(jù)算法中，聚類算法一般都是作為其他算法分析的基礎，對數(shù)據(jù)進行聚類可以從整體上分析數(shù)據(jù)的一些特性。聚類有很多的算法，k-means是最簡單最實用的一種算法。在這里對k-means算法的原理以及其背后的數(shù)學推導做一

些詳細的介紹，并討論在實際應用中要避免的一些坑。

算法

k-means算法很簡單，但是當我們正真把這個算法用在生產(chǎn)中時還是存在很多的細節(jié)需要考慮的，這些細節(jié)將要在后面進行討論。首先給出k-means算法的步驟：

1、給出k個初始聚類中心

2、repeat：

      把每一個數(shù)據(jù)對象重新分配到k個聚類中心處，形成k個簇

      重新計算每一個簇的聚類中心

3、until  聚類中心不在發(fā)生變化

k和初始聚類中心的選擇的討論

1、k的選擇

當我們拿到一批數(shù)據(jù)時，大多數(shù)情況下我們是不知道簇的個數(shù)的。

a、在一些情況下，我們通過對業(yè)務了解的加深，是可以找到數(shù)據(jù)的簇的，比如我們手里有一批用戶購買商品的記錄數(shù)據(jù)，已經(jīng)統(tǒng)計出用戶工作日和周末購買物品的數(shù)量，在二維做坐標中分別為：工作日購買的物品數(shù)和周末購買的物品數(shù)，從這我們可以發(fā)現(xiàn)，我們?nèi)藶橐呀?jīng)把數(shù)據(jù)分為三個簇：周末購買、工作日購買和周末和工作日都購買的人數(shù)

b、當我們真的確定不了數(shù)據(jù)的簇時，我們可以通過相關(guān)的算法來大概確定數(shù)據(jù)的簇。對k進行多次取值，通過一個目標函數(shù)f進行度量，選取使這個f值最小的k作為聚類中心（目標函數(shù)f后面會講到),進行多次選擇k值時，時間和空間復雜度都會增加。還一種策略是通過一個算法canopy算法初始選取出聚類的個數(shù)k和初始的聚中心作為k-means算法的輸入，而canopy算法不需要輸入k和初始聚類中心，它可以作為k-means算法預處理算法用來選取k-means算法。所需要的k值和聚類中心

2、聚類中心的選擇

選取初始聚類中心是最讓人頭疼的一件事，如果選擇的不好就容易找到局部最優(yōu)聚類中心而不是全局最優(yōu)的聚類中心。

a、知道了k后，再選取初始的聚類中心。一種策略是進行多次隨機的選擇k個點作為初始聚類中心，比較目標函數(shù)f，選取目標函數(shù)f最小的最為初始的聚類中心，這種隨機選擇有很多的不足：1、無形中就增加了時間開銷和空間開銷  2、找到的聚類中心可能是局部最優(yōu)的而不是全局最優(yōu)的，因為當隨機選擇的兩個聚類中心位于一個簇中，無論怎么重新計算聚類中心，得到的結(jié)果都不是全局最優(yōu)的，分類的結(jié)果也不是我們想要的。雖然這種策略有很多的不足，不代表我們不可以使用，在實際應用中我們還是可以選擇這中策略進行生產(chǎn)的。

b、當知道了k后，還有一種選取聚類中心的策略:首先我們把數(shù)據(jù)分為兩個部分：聚類中心集合和原始數(shù)據(jù)集合，首先我們從原始數(shù)據(jù)集合中隨機的選擇一個數(shù)據(jù)最為初始聚類中心的一個簇中心放入聚類中心集合中，然后我們再從原始數(shù)據(jù)集中選擇一個聚類聚類中心集合中所有的記錄都最遠的一個點作為下一個初始的聚類中心。這種選擇在實際應用中證明了也是比較好的一種策略，得到的效果要比a策略得到的好一些，但是這種策略要受到離群點的擾動比較的大，同時選擇初始聚類中心的計算量也是非常大的，空間消耗也非常的大。

c、當k不知道的情況下，最常用的一種策略就是使用canopy算法來尋找k和聚類中心。

k-means最近鄰的度量

在k-means算法中，我們需要把數(shù)據(jù)集分到距離聚類中心最近的那個簇中，這樣就需要最近鄰的度量策略。我們需要用什么來衡量最近，怎么衡量？k-means算法需要計算距離，計算距離就需要數(shù)值，因此k-means算法也是對數(shù)值型數(shù)據(jù)比較實用。k-means算法中最常用的度量公式：在歐式空間中采用的是歐式距離，在處理文檔中采用的是余弦相似度函數(shù)，有時候也采用曼哈頓距離作為度量，不同的情況實用的度量公式是不一樣的。

歐式距離

余弦相似度計算公式

向量表示法

曼哈頓距離:

k-means算法背后的數(shù)據(jù)知識(k-means算法好壞的評價標準)

k-means算法要解決的問題是我們把數(shù)據(jù)給分成不同的簇，那我們要達到的目標是什么呢？是使得同一個簇的差異很小，不同簇之間的數(shù)據(jù)差異最大化，這是文字描述的，不能用來標準化研究或者數(shù)學推導，我們想要剛才的一句話用一個數(shù)據(jù)公式或者數(shù)學模型來進行衡量，建立怎么樣的數(shù)學公式才能用來衡量上面的描述？一般情況下采用的是誤差平方和作為衡量的目標函數(shù)SSE，上面提到的目標函數(shù)f就是SSE也是誤差平方和。先上公式:

元素解釋:C表示的聚類中心的值，x是屬于這個簇的數(shù)據(jù)點，d為歐式距離

為了實現(xiàn)同一個簇的差異很小，不同簇之間的元素數(shù)據(jù)差異最大化(我們默認的數(shù)據(jù)都是在歐式空間中，數(shù)據(jù)的差異采用的是歐式距離來進行衡量)。為了實現(xiàn)這個目標，實際上是使誤差平方和SSE最小，在了k-means算法中，有兩個地方降低了SSE數(shù)值：把數(shù)據(jù)點分到距離中心點最近的簇中，這樣計算出來的SSE將減少、重新計算聚類中心點，又進一步的降低了SSE，但是這樣的優(yōu)化策略只是為了找到局部最優(yōu)解，如果想要找到全局最優(yōu)解需要找到合理的初始聚類中心。

還有一個問題需要我們來討論，我們?yōu)槭裁催x取簇集合的平均值作為聚類中心呢，因為這樣才能是SSE達到最小，在數(shù)學中求一個函數(shù)的最小值，怎么辦？是不是求導，我們發(fā)現(xiàn)SSE是一個二元函數(shù)，那就求偏導吧，如下推導。

從上面的推導，可以看出我們?yōu)槭裁催x擇均值作為聚類中心，當聚類中心為簇中的均值時，才能是SSE最小，在接下來會對sparkMLlib中對于k-means的算法進行詳細的介紹，再補吧