1 kmeans算法概述

往往在實際數(shù)據(jù)分析中，我們需要發(fā)現(xiàn)數(shù)據(jù)的一些內(nèi)在規(guī)律，但是數(shù)據(jù)一般都是未標(biāo)注，因此希望通過某個算法來揭示數(shù)據(jù)的內(nèi)在性質(zhì)和規(guī)律，其中最常用的算法就是聚類。

kmeans就是聚類算法中最常用的一種，是無監(jiān)督的算法，目標(biāo)是通過數(shù)據(jù)分布來發(fā)現(xiàn)其中存在的類簇。
如下圖，我們可以直觀的看出數(shù)據(jù)可能存在兩個類簇，但是如何通過算法來發(fā)現(xiàn)？

kmeans1

2 kmeans算法流程

我們的目標(biāo)就是希望找到類別的中心使得類內(nèi)點到中心的距離盡可能近，這個距離可以表示如下：

目標(biāo)就是最小化E，但是這是個NP問題，kmeans采用貪心算法來迭代找到最優(yōu)。

kmeans的大致算法思想如下

1. 先假設(shè)數(shù)據(jù)可以分為k類
2. 隨機(jī)從數(shù)據(jù)集中選擇k個點作為中心點
3. 分別計算所有點與這k個中心點的距離，選擇最近的中心點所在的類別作為類別標(biāo)簽，這樣就把所有點都分配了類標(biāo)
4. 然后根據(jù)k個類別的樣本重新計算各個類別的中心點，得到新的k個類中心點。
5. 重復(fù)步驟3、步驟4，直至中心點不再發(fā)生改變，結(jié)束。

這是一個循環(huán)迭代的過程，通過反復(fù)迭代直至找到中心點?？雌饋肀容^簡單，但其實背后有很多需要注意的地方。

2.1 k值選擇

公式(1)很直觀，只要能夠最小化E即可，但是k是一個超參數(shù)（不是通過數(shù)據(jù)迭代得來，是我們初始化指定），我們發(fā)現(xiàn)，

1. 如果k選擇越大，那么這個E可以最小化到0，即如果類別十分細(xì)，細(xì)到每個樣本作為一個單獨的類，那么E=0，但這不是我們希望看到的。
2. 如果k選擇較小，那么類別較粗，可能類內(nèi)的距離就比較大。

因此如何選擇k將直接影響聚類的結(jié)果。
我們做個直觀的圖，還是最開始的數(shù)據(jù)圖，我們可以發(fā)現(xiàn)E和k的關(guān)系如下:

k_E_relation

• 基于曲率判斷
  有種確定k的方法，即看上圖中曲率變化最大的點，我們可以看到k=2的時候曲率變化最大，那么最優(yōu)的k應(yīng)該就選2。

2.2 初始中心點選擇

初始中心點的選擇如果不當(dāng)，可能會陷入局部最優(yōu)的。
下面列種改進(jìn)方法
kmeans++

1. 初始化中心點集合:C = {}
2. 從輸入的數(shù)據(jù)點集合中隨機(jī)選擇一個點c_k作為中心點，加入到中心點集合C= C +c_k
3. 數(shù)據(jù)集中每個點x計算與中心點集合中最近的中心點的距離d(x)
4. 在d(x)中選擇距離較大的點作為新的中心點，加入到中心點集合
5. 重復(fù)步驟2、步驟3、步驟4，直至找到k個中心點，然后再采用kmeans算法來進(jìn)行聚類。

另一種確定中心點的方法就是通過層次聚類或者Canopy方法先得到k個類別，把他們的中心點作為初始化中心點。

2.3 距離度量

既然涉及到空間距離，自然離不開距離度量函數(shù)的定義，這點往往容易被忽視，我們在實際實踐中，默認(rèn)采用都是歐式距離來表示，但是這個距離合理性的前提是我們的特征向量表征一定也是符合歐式空間特征才行，否則出來的結(jié)果會較差。

距離定義首先需要滿足一些基本性質(zhì)：

非負(fù)性: d(x, y)>=0
同一性：d(x, y)=0 當(dāng)且僅當(dāng)x=y
對稱性：x(x, y)=d(y, x)
直遞性（三角不等式）：d(x, y)<=d(x,z) + d(z, y)

• 閔可夫斯基距離
  我們常用的就是閔可夫斯基距離
  
  
  

當(dāng)p=1，表示曼哈頓距離
當(dāng)p=2，表示歐式距離

但是，在實踐中，我們的特征向量未必都是連續(xù)性變量，上述距離度量函數(shù)使用與連續(xù)變量空間，對于離散變量，一般采用其他的方法來衡量距離，例如VDM。
另外我們常用的距離衡量還有余弦距離等，這里推薦一個python庫，支持較多的距離衡量

Biopython為k-means聚類提供了各種距離函數(shù)，包括余弦距離、皮爾遜相似度量、歐式距離等。

3 kmeans算法不足

• kmeans算法由于距離度量采用的是點-點的距離，對于球狀的空間分布是可以正確聚類的，但是非球狀的則無法正確聚類，解決方案一般是通過特征變換來達(dá)到高維空間或者另一個特征空間的可分（可聚類）

  
  
  ball_cluster

• 如果特征空間高維，數(shù)據(jù)量較大，kmeans運算速度較慢

4 二分k-means算法

層次聚類算法是從底向上，逐步聚類，而二分kmeans算法則是從頂向下，逐步分裂，最終得到我們要的k個類。
算法描述如下

1. 先將整個樣本集合作為一個簇，該簇中心點即等于所有向量平均，計算此時的SSE（公式1）
2. 對每個類簇都進(jìn)行二分類（采用kmeans算法），然后計算拆分后的總的SSE，選擇變化最大的那個分類簇進(jìn)行二分裂
3. 重復(fù)上述步驟，直至類別數(shù)等于k，結(jié)束。

這個分類算法有點類似決策樹的分裂思想，在決策樹分裂的過程中，我們希望的是找到熵減少（熵增益）最大的特征分裂點，而這里是找到SSE減少最大的類別。分類算法和聚類算法目標(biāo)都是希望能夠找到讓類內(nèi)樣本越純的方法。后續(xù)我們講到?jīng)Q策樹的時候會再闡開這塊內(nèi)容。