機器學習-聚類（K-Means）

1. K-Means原理初探
2. 傳統K-Means算法流程

3. K-Means初始化優化K-Means++

   在上節我們提到，k個初始化的質心的位置選擇對最後的聚類結果和運作時間都有很大的影響，是以需要選擇合适的k個質心。如果僅僅是完全随機的選擇，有可能導緻算法收斂很慢。K-Means++算法就是對K-Means随機初始化質心的方法的優化。

   K-Means++的對于初始化質心的優化政策也很簡單，如下：

   　　　　a) 從輸入的資料點集合中随機選擇一個點作為第一個聚類中心 μ1 μ 1

   　　　　b) 對于資料集中的每一個點xixi，計算它與已選擇的聚類中心中最近聚類中心的距離

   D(x)=argmin∑i=0k=selected||xi−μr||22 D ( x ) = a r g m i n ∑ i = 0 k = s e l e c t e d | | x i − μ r | | 2 2

   　　　　

   　　　　c) 選擇一個新的資料點作為新的聚類中心，選擇的原則是：D(x)較大的點，被選取作為聚類中心的機率較大

   　　　　d) 重複b和c直到選擇出k個聚類質心

   　　　　e) 利用這k個質心來作為初始化質心去運作标準的K-Means算法

   　　　　(内涵：就是盡量選擇更分散的點來作為初始的聚類中心)

4. K-Means距離計算優化elkan K-Means

   在傳統的K-Means算法中，我們在每輪疊代時，要計算所有的樣本點到所有的質心的距離，這樣會比較的耗時。那麼，對于距離的計算有沒有能夠簡化的地方呢？elkan K-Means算法就是從這塊入手加以改進。它的目标是減少不必要的距離的計算。那麼哪些距離不需要計算呢？

   elkan K-Means利用了兩邊之和大于等于第三邊,以及兩邊之差小于第三邊的三角形性質，來減少距離的計算。

   第一種規律是對于一個樣本點 x x 和兩個質心μ1μ1, μ2 μ 2 。如果我們預先計算出了這兩個質心之間的距離 D(j1,j2) D ( j 1 , j 2 ) ，則如果計算發現 2D(x,j1)≤D(j1,j2) 2 D ( x , j 1 ) ≤ D ( j 1 , j 2 ) ,我們立即就可以知道 D(x,j1)≤D(x,j2) D ( x , j 1 ) ≤ D ( x , j 2 ) 。此時我們不需要再計算 D(x,j2) D ( x , j 2 ) ,也就是說省了一步距離計算。

   第二種規律是對于一個樣本點 x x 和兩個質心μ1μ1, μ2 μ 2 。我們可以得到

   D(x,j2)≥max{0,D(x,j1)−D(j1,j2)} D ( x , j 2 ) ≥ m a x { 0 , D ( x , j 1 ) − D ( j 1 , j 2 ) }

   這個從三角形的性質也很容易得到。

   利用上邊的兩個規律，elkan K-Means比起傳統的K-Means疊代速度有很大的提高。但是如果我們的樣本的特征是稀疏的，有缺失值的話，這個方法就不使用了，此時某些距離無法計算，則不能使用該算法。

5. 大樣本優化Mini Batch K-Means

   在統的K-Means算法中，要計算所有的樣本點到所有的質心的距離。如果樣本量非常大，比如達到10萬以上，特征有100以上，此時用傳統的K-Means算法非常的耗時，就算加上elkan K-Means優化也依舊。在大資料時代，這樣的場景越來越多。此時Mini Batch K-Means應運而生。

   顧名思義，Mini Batch，也就是用樣本集中的一部分的樣本來做傳統的K-Means，這樣可以避免樣本量太大時的計算難題，算法收斂速度大大加快。當然此時的代價就是我們的聚類的精确度也會有一些降低。一般來說這個降低的幅度在可以接受的範圍之内。

   在Mini Batch K-Means中，我們會選擇一個合适的批樣本大小batch size，我們僅僅用batch size個樣本來做K-Means聚類。那麼這batch size個樣本怎麼來的？一般是通過無放回的随機采樣得到的。

   為了增加算法的準确性，我們一般會多跑幾次Mini Batch K-Means算法，用得到不同的随機采樣集來得到聚類簇，選擇其中最優的聚類簇。

6. K-Means與KNN

   初學者很容易把K-Means和KNN搞混，兩者其實差别還是很大的。

   K-Means是無監督學習的聚類算法，沒有樣本輸出；而KNN是監督學習的分類算法，有對應的類别輸出。KNN基本不需要訓練，對測試集裡面的點，隻需要找到在訓練集中最近的k個點，用這最近的k個點的類别來決定測試點的類别。而K-Means則有明顯的訓練過程，找到k個類别的最佳質心，進而決定樣本的簇類别。

   當然，兩者也有一些相似點，兩個算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。

7. K-Means小結

   K-Means是個簡單實用的聚類算法，這裡對K-Means的優缺點做一個總結。

   　　　　K-Means的主要優點有：

   　　　　1）原理比較簡單，實作也是很容易，收斂速度快。

   　　　　2）聚類效果較優。

   　　　　3）算法的可解釋度比較強。

   　　　　4）主要需要調參的參數僅僅是簇數k。

   　　　　

   　　　　K-Means的主要缺點有：

   　　　　1）K值的選取不好把握

   　　　　2）對于不是凸的資料集比較難收斂

   　　　　3）如果各隐含類别的資料不平衡，比如各隐含類别的資料量嚴重失衡，或者各隐含類别的方差不同，則聚類效果不佳。

   　　　　4） 采用疊代方法，得到的結果隻是局部最優。

   　　　　5） 對噪音和異常點比較的敏感。