今天是機器學習專題的第13篇文章，我們來看下Kmeans算法的優化。
在上一篇文章當中我們一起學習了Kmeans這個聚類算法，在算法的最後我們提出了一個問題：Kmeans算法雖然效果不錯，但是每一次迭代都需要遍歷全量的數據，一旦數據量過大，由於計算複雜度過大迭代的次數過多，會導致收斂速度非常慢。
想想看，如果我們是在面試當中遇到的這個問題，我們事先並不知道正解，我們應該怎麼回答呢？
還是老套路，我們在回答問題之前，先來分析問題。問題是收斂速度慢，計算複雜度高。計算複雜度高的原因我們也知道了，一個是因為樣本過大，另一個是因為迭代次數過多。所以顯然，我們想要改進這個問題，應該從這兩點入手。
這兩點是問題的關鍵點，針對這兩點我們其實可以想出很多種優化和改進的方法。也就是說這是一個開放性問題，相比標準答案，推導和思考問題的思路更加重要。相反，如果我們抓不住關鍵點，那麼回答也會跑偏，這就是為什麼我在面試的時候，有些候選人會回答使用分佈式系統或者是增加資源加速計算，或者是換一種其他的算法的原因。
也就是說分析問題和解決問題的思路過程，比解決方法本身更加重要。
下面，我們就上面提到的兩個關鍵點各介紹一個優化方法。
mini batch
mini batch的思想非常樸素，既然全體樣本當中數據量太大，會使得我們迭代的時間過長，那麼我們縮小數據規模行不行？
那怎麼減小規模呢，很簡單，我們隨機從整體當中做一個抽樣，選取出一小部分數據來代替整體。這樣我們人為地縮小樣本的規模，不就可以提升迭代的速度了？
通過抽樣我們的確可以提升迭代的效率，但是這樣能保證正確性嗎？
這個問題很好回答，我們只需要簡單做個實驗就可以證明。
我們利用上週開發的並沒有經過任何優化的代碼，並且將生成的樣本的數量增加到五萬，從下面的這張圖我們可以看出，樸素的Kmeans足足用了37.2秒才完成了計算。我們得到的聚類結果如下：
接著我們通過numpy下的random.choice，從中隨機選擇1000條樣本，我們對比一下前後的耗時和結果。
我們再來看下兩次聚類的中心，從圖片上來看兩者誤差極小，我們打印出座標來觀察，誤差在0.05以內，可以說是非常接近了。
雖然mini batch的原理說穿了一錢不值，但是它的的確確非常重要，不僅重要而且在機器學習領域廣為使用。在大數據的場景下，幾乎所有模型都需要做mini batch優化。
但是我們不禁有一個問題，這個方案全靠隨機，看起來非常不靠譜，會不會出現我們選出來的結果偏差特別大的情況，比如剛好都在一個簇當中？從理論上來看，這當然是可能的，所以為了謹慎起見，我們可以重複多次採樣，再對計算到的類簇座標計算均值，直到簇中心趨於穩定為止。或者可以人工設置迭代次數，直到滿足迭代次數要求時停止。
Kmeans ++
如果說mini batch是一種通用的方法，並且看起來有些兒戲的話，那麼下面要介紹的方法則要硬核許多。這個方法直接在Kmeans算法本身上做優化因此被稱為Kmeans++。
前文當中我們已經說過了，想要優化Kmeans算法的效率問題，大概有兩個入手點。一個是樣本數量太大，另一個是迭代次數過多。剛才我們介紹的mini batch針對的是樣本數量過多的情況，Kmeans++的方法則是針對迭代次數。我們通過某種方法
降低收斂需要的迭代次數，從而達到快速收斂的目的。這個思路很明確，但是操作卻不簡單，迭代次數和收斂效果是相關的。也就是說在達到收斂之前，迭代次數是不能減少的，否則就會導致不收斂。而且聚類問題和分類問題不同，我們在分類問題當中有一個明確的損失函數用來優化。在我們使用梯度下降法的時候，還可以將梯度前的學習率設置得稍稍大一些，從而加快收斂的速度。但是聚類問題不同，尤其是Kmeans算法，我們的依次迭代，座標變換的值是通過求平均座標也就是質心的座標得到的。除非我們修改迭代的邏輯，否則沒辦法加快迭代。
我們從算法運作的思路出發的確會得到這個結論，這個結論也是沒問題的，但是有問題的是收斂的速度除了取決於每次迭代的變化率之外，還有另外一個重要的指標。就是迭代起始的位置。
也就是說我們是從怎樣的情況開始收斂的，顯然如果我們的初始狀態離最終的收斂狀態越近，那麼收斂需要的迭代次數就越少，所以我們這個優化算法的目標就是想辦法找到一個足夠接近收斂結果的起始狀態。這個思路應該也不難想通，但是這當中藏著一個巨大的疑問，我們在訓練的時候並不知道收斂的狀態是什麼，又怎麼能判斷起始狀態距離收斂結果的遠近呢？
顯然直接走是走不通的，我們需要迂迴一下。
我們來分析一下，其實可以得到很多結論。首先，如果我們隨機選擇K個樣本點作為起始的簇中心效果比隨機K個座標點更好。原因也很簡單，因為我們隨機座標對應的是在最大和最小值框成的矩形面積當中選擇K個點，而我們從樣本當中選K個點的範圍則要小得多。我們可以單純從面積的佔比就可以看得出來。由於樣本具有聚集性，我們在樣本當中選擇起始狀態，選到接近類簇的可能性要比隨機選大得多。
但是還有一個小問題，比如說在上面的例子當中類簇是3，我們隨機選擇3個樣本作為起始狀態。但是問題來了，如果我們剛好選的3個點在一個類簇當中怎麼辦，那樣到收斂狀態不也需要很久嗎？
這個問題的確是存在的，我們要避免選到同一個簇中點的情況。但是由於我們並不知道樣本的分佈情況，怎麼來判斷呢？
這個時候需要用到聚類的另一個性質，我們再來觀察一下上面的圖：
我們可以發現，簇是有向心性的。也就是說在同一個簇附近的點都會被納入這個簇的範圍內，反過來說就是兩個離得遠的點屬於不同簇的可能性比離得近的大。
Kmeans++的思路正是基於上面的這兩點，我們將目前已經想到的洞見整理一下，就可以得到算法原理了。
算法原理
首先，其實的簇中心是我們通過在樣本當中隨機得到的。不過我們並不是一次性隨機K個，而是隻隨機1個。
接著，我們要從生下的n-1個點當中再隨機出一個點來做下一個簇中心。但是我們的隨機不是盲目的，我們希望設計一個機制，使得距離所有簇中心越遠的點被選中的概率越大，離得越近被隨機到的概率越小 。
我們重複上述的過程，直到一共選出了K個簇中心為止。
輪盤法
我們來看一下如何根據權重來確定概率，實現這點的算法有很多，其中比較簡單的是輪盤法。這個算法應該源於賭博或者是抽獎，原理也非常相似。
我們或多或少都玩過超市或者是其他場景下的轉盤抽獎，在抽獎當中有一個指針一直保持不動。我們轉動轉盤，當轉盤停下的時候，指針所指向的位置就是抽獎的結果。
我們都知道命中結果的概率和輪盤上對應的面積有關，面積越大抽中的概率也就越大，否則抽中的概率越小。
我們用公式表示一下，對於每一個點被選中的概率是：
其中 f(xi) 是每個點到所有類簇的最短距離，P(xi) 表示點 xi 被選中作為類簇中心的概率。
輪盤法其實就是一個模擬轉盤抽獎的過程，只不過我們用數組模擬了轉盤。我們把轉盤的扇形拉平，拉成條狀，原來的每個扇形就對應了一個區間。扇形的面積就對應了區間的長度，顯然長度越長，抽中的概率越大。然後我們來進行抽獎，我們用區間的長度總和乘上一個0-1區間內的數。
我們找到這個結果落在的區間，就是這次輪盤抽中的結果。這樣我們就實現了控制隨機每個結果的概率。
在上面這張圖當中，我們隨機出來的值是0.68，然後我們每一次減去區間長度，最後落到的區間，就是我們隨機得到的結果。
總結
明白了輪盤算法之後，整個Kmeans++的思路已經是一覽無餘了。也就是說我們把抽取類簇中心類比成了輪盤抽獎，我們利用輪盤抽取K個樣本來作為初始的類簇中心。從而儘可能地減少迭代次數，逼近最終的結果。
那麼，這樣的方法究竟有沒有效果呢？
同樣，我們通過實驗來證明，首先我們來寫出代碼。我們需要一個輔助函數用來計算某個樣本和已經選好的簇中心之間的最小距離，我們要用這個距離來做輪盤算法。
這個函數很簡單，只是計算距離，取最小值而已：
接著就是用輪盤法選出K箇中心，首先我們先隨機選一個，然後再根據距離這個中心的舉例用輪盤法選下一個，依次類推，直到選滿K箇中心為止。
最後，我們把圖畫出來看下效果：
上圖當中白色的點表示最後收斂的位置，紅色的X表示我們用Kmeans++計算得到的起始位置，可以發現距離最終的結果已經非常接近了。顯然，我們只需要很少幾次迭代就可以達到收斂狀態。
當然Kmeans++本身也具有隨機性，並不一定每一次隨機得到的起始點都能有這麼好的效果，但是通過策略，我們可以保證即使出現最壞的情況也不會太壞。
在實際的場景當中，如果我們真的需要對大規模的數據應用Kmeans算法，我們往往會將多種優化策略結合在一起用，並且多次計算取平均，從而保證在比較短的時間內得到一個足夠好的結果。這也是機器學習領域很多算法優化的精髓，即不再追求最優解，而只要一個足夠好的解。很多時候，在結果上一點小小的退讓，可以將算法效率提升很多。
今天關於Kmeans的優化內容就到這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
