本篇大綱：
1、背景知識：一些常見的距離度量/相似度計算方式
2、聚類算法之Kmeans
3、kmeans優缺點及其改進
4、kmeans的簡單代碼實現
上上期回顧
1、我們先做了基本鋪墊，對於最值求解問題進行三種類別劃分，包括無約束問題，等式約束問題和不等式約束問題，並簡單闡述對應的求解方式。
2、我們從感知器出發，簡單闡述其二分類原理，從而明白SVM是從何算法改進而來。
3、我們從svm的兩個核心目標出發，推出其目標函數和約束條件，根據函數距離和幾何距離相等的約束來簡化計算過程，從而得到精簡版的目標函數和約束條件。通過對約束條件的變形，我們基本轉成不等式約束的基本形式，從而進行KKT條件的轉換，通過導數求解，我們解出w的值以及另一個等式約束條件，進一步的，我們通過smo求解方式對函數進行進一步求解，得到最終的w和b的值，也就獲得了函數超平面的方程。通過對函數超平面方程進行符號化的封裝，從而達到通過給定空間樣本坐標，得到目標分類結果的效果。
4、我們淺嘗輒止地談了一下解決低維空間數據映射到高維空間高計算量問題的核函數，以及用於增強超平面泛化能力的軟間隔，並簡單分析了一下鬆弛因子和懲罰係數的關係。
5、我們言簡意賅地提了一下SVM的特點及其應用場景，並給出了svm在sklearn中相關的算法及參數的說明。
沒事嘮兩句
在傳統機器學習領域裡，主要涉及的任務有回歸、分類、聚類、推薦等。
回歸由於其精確度問題，並沒有被廣泛大量地商業化應用，多是用於一些分析工作，或是作為一個簡單的參考數據以及輔助數據而存在。
分類是一大主流方向，也是商業化覆蓋最大的一個方向，包括後面深度學習領域的一些主攻方向，個人理解也是在分類基礎上做了進一步其它工作。
聚類多用於前期數據分析的輔助，零散錯亂的數據，無論是對於標註還是對於分析，相比整齊規劃的數據而言，其時間開銷和精度提升的代價多是會相對大一些，而整齊有致的數據，則多會讓工作變得更加條理高效一些。
推薦算法領域頗廣，常見的如電商平臺的物品推薦，音樂視頻的興趣推薦，閱讀平臺的興趣文章推薦等等，是另一個商業化覆蓋較大的方向領域。但是就目前市場來看，推薦算法的整體效果還未完全成熟，雖百家齊放，但效果上仍參差不齊。
背景知識
啥是聚類：
簡單來說，就是物以類聚，人以群分。
換一句話說，就是將相似的歸為一類，不相似的則不為一類。
那麼問題就來了，什麼才是相似，相似的度量方式是什麼？
難道標籤一致還不能作為相似的標準嗎？還需要其他的方式來進一步度量是否相似嗎？
首先，標籤是結果，是參考答案。所以自然可以理解為標籤一致的即屬於相似的一類，標籤不一致的則不屬於相似的一類。
但是並不是所有數據上來就有答案的，或者並不是所有數據都是帶標籤的。
那麼聚類問題實際上就是屬於無監督(無標籤)學習，自然需要其它的方式來進行判斷是否相似。
一般來說，我們會以距離或者相似度來作為相似的度量方式。
常見的距離度量方式
先給出米可夫斯基距離：
那麼，當p等於1時，也就是曼哈頓距離：
當p等於2時，則是歐幾裡得距離，也就是歐氏距離：
當p等於無窮時，則是切比雪夫距離：
在這裡，我們最常見的是曼哈頓距離和歐式距離。
曼哈頓距離最初是源於曼哈頓城市的計程車距離計算，對於我們來說，這個背景可有可無，就不展開講了。或許，我們更應該關心的是，什麼時候用曼哈頓距離，什麼時候用歐式距離，以及使用兩者對應的優缺點是什麼？
對於這個問題，實際上，我們可以參考L1正則和L2正則的優缺點，因為L1正則實際上就是使用的曼哈頓距離公式，而L2正則實際上就是使用的歐式距離公式，具體優缺點，我們可以回顧這裡：回歸算法之線性回歸（二）
常見的相似度計算方式
傑卡德係數：
傑卡德係數多用於文本相似的計算，比如A文本共100個詞，B文本也是100個詞，兩個文本交集為50個詞，兩個文本併集為150個詞，那麼兩者對應的傑卡德係數即可三分之一，兩者的距離則為三分之二，距離越大，自然也就越不相似。但從其計算方式上我們可以大概知道，傑卡德係數用於文本分類，其粒度較粗，更多是從詞的組成上來判斷是否相似的，而不會去考慮語義。
餘弦相似度：
從數學的角度來講，向量是空間中帶有方向的線段，而餘弦的求解過程也可以理解為一個向量在另一個向量方向上的投影，故而當兩個向量的方向一致時，其餘弦值則會為1。如果運用到文本相似度計算上，比如我們使用文章各詞語的詞頻所構成的向量，作為該文章的向量化表示，那麼計算兩個向量的餘弦值，就可以作為兩文章的相似程度判斷，這裡我們使用餘弦相似度來作為相似度判斷標準，更多的，是考慮文章的描述方向，對於其文章的長度，我們考慮則會相對少一些。
實際應用中，對於數據而言，如果會有一些預處理操作，那麼就會使得後面更加高效快捷。對於求餘弦相似度而言，我們可能會先對數據進行歸一化操作，所謂歸一化，也就是讓向量的模長變為1，因為是同時對所有數據進行相同操作，故而對於結果而言，該變化不會產生多少影響，另外，歸一化操作同標準化、區間放縮法一樣，都具備去量綱的效果，故而多數情況下，我們在求餘弦相似度之前，會加上一步歸一化操作，從而簡化餘弦相似度的計算。
皮爾遜係數：
相關係數的取值是從-1到1，當相關係數的值小於0時，則代表X和Y之間負相關，當相關係數的值大於0時，則代表X和Y之間正相關，一般而言，當相關係數的絕對值大於0.8時，我們認為是極相關，當然，也可以個人要求更嚴格一些，比如認為大於0.85我們才去認為極相關，也是無可厚非的。特殊的，通過公式我們可以看出，當X=Y時，分子等於分母（因為DX=E(X^2)-(EX)^2)，此時相關係數為1，也就是兩者完全相同，也就是完全可以被彼此代替。
那麼皮爾遜係數和餘弦相似度兩者之間又有什麼聯繫呢？有什麼講究什麼時候選擇哪種方式呢？
先看看餘弦相似度和皮爾遜係數的另一種表達方式：
所以，實際上，皮爾遜係數是去中心化的餘弦相似度。
那什麼場景下會更適合皮爾遜係數呢，舉個例子，比如說有用戶甲，對電影A、電影B、電影C都有一個自己的打分，用戶乙，同樣對電影A、電影B、電影C有一個自己的打分，現在要看用戶對各個電影的評價是否是相似的，直白的，我們可以通過對分數的對比來獲得結果，但是因為不同用戶都有自己的評價標準，A用戶比較嚴格，認為是好的，也就給打7分，而B用戶則比較感性化，認為是好的，則打9分。故而這裡我們需要做一個去用戶標準化操作，故而選擇使用皮爾遜相關係數會比較合適。
再舉個例子，比如我們有若干特徵變量，我們想要判斷一下不同特徵變量之間是否具有相關性較強的特徵變量，這個時候，因為不同的特徵變量都有自己的一個隱藏標準，在各自的標準下，其數值自然也就不同，故而此時，我們要想判斷變量之間是否相關，則需要做一個變量的去中心化操作，從而消去特徵變量自身的隱藏標準，也就更加準確。
互信息：
互信息的相關介紹以及其對應的應用場景，有興趣的可以再去看看決策樹這篇內容，這裡就不再贅述。
那麼到這裡，我們對於一些基本的相似讀計算方式也就算有個大概的了解了。
聚類算法之Kmeans
聚類算法其實有很多，包括層次聚類，密度聚類，譜聚類等等。
但是為何這篇只提Kmeans，是因為Kmeans是算法理解簡單，而又使用最多，並且從原理上來說，其它的聚類算法只是其算法或求解思路有些差別，但是其核心思路還是一致，具體做的事也是有著同一個目標，故而這篇我們重點詳細單獨闡述Kmeans算法。對於其它聚類算法，如果必要，我們在下一篇再進行展開。
基本上來說，聚類算法的核心都是先獲得簇心，然後根據簇心劃分簇，再按照一定的標準或方法更新簇心，根據更新後的簇心重新劃分簇，不斷迭代至滿足一定條件。當然，這只是大部分情況下，也並不是絕對的，比如密度聚類，則並不是按上述流程走的，這個我們後面再敘。
所以，大部分情況下，不同的聚類算法，其主要的差別有這麼幾點：第一，其簇心選擇方式可能不同。第二，根據簇心劃分簇的方式可能不一樣。第三，其更新簇心的方式可能不同。
Kmeans算法，也叫k均值算法，顧名思義，其核心思想也就是根據均值來更新簇心。
其具體算法流程如下：
1、隨機初始化k個簇心
2、對於每個樣本，根據其到各簇心的距離(這裡用歐式距離)，將其標註為距離最近的簇心類別。
3、更新每個簇的簇心，計算方式即求均值。
4、重複上述2、3兩個步驟，直到能達到某個終止條件。
一般終止條件有：
1、迭代次數：即自己設定一定的迭代次數。
2、最小平方誤差MSE：即上輪簇心和當前計算均值所得結果的mse
3、簇中心的變化率：即更新一輪，簇心發生變化的總比例值。
或許有人會問，是否可以對這個算法進行改進，比如單純地換一種距離度量方式，如使用曼哈頓距離，或者單純地換一種簇心計算方法，如使用中位數等。
然而，這裡歐氏距離計算方式和求均值更新簇心實際上是綁定的，嚴格來說，正是由於歐氏距離求解方式的確定，進而導致了更新簇心時是求均值的方式。
可以這麼理解
假定我們記k個簇心分別為a1，a2，。。。ak，每個簇的樣本數量為N1，N2，。。。Nk。
我們使用平方誤差(歐氏距離)作為目標函數，即
那麼要想獲得最優解，，也就是目標函數要儘可能小，也就是，求偏導，讓其等0。這裡的求偏導是對第j個簇心aj求的偏導。故而：
故而我們也就明白了，這裡的簇心更新的方式，實際上是由距離度量方式所決定的。
kmeans優缺點及其改進
整體上看，Kmeans算法原理簡單，操作可行性高。
但不可避免的，kmeans算法有以下一些缺點:
1、簇心初值敏感，不同的初值其劃分的結果可能不一樣
舉例來說：假定我們的數據是人為的創造上下左右四個圓，然後分別在四個圓裡隨意畫上若干個點。那麼理論上我們知道，我們期望是能分出上下左右四個簇。
實際上，如果我們初始化四個簇心，而這四個簇心恰好分別處於四個圓裡，那麼根據kmeans的處理流程，我們大概率能夠獲得我們期望的四個簇，即分別屬於上下左右四個圓裡(這裡的圓只是我們自己的輔助說法，並非在數據中真實存在，數據均為空間中點的坐標)。
如果我們初始化的四個簇心，有兩個或兩個以上簇心，是在同一個圓裡，那麼，根據kmeans的流程，最後的結果，很可能是和我們的預期完全不一致。也就是我們說的初值敏感。
2、異常點存在會導致偏差嚴重
舉例來說：為簡化運算，我們以一維數據為例，假定我們某個簇共有五個點，這五個點對應的值分別為2,4,6,8,100。不論該簇的初始簇心是幾，這輪更新簇心時，根據kmeans算法，我們求平均，則是120/5=24。看起來這個數似乎並不合理，有點員工和老闆的平均薪資來計算整體平均收入的代入感。。。這也就是我們說的異常點的存在，會導致偏差叫嚴重。
3、更新簇心求均值，迭代效率慢
回到kmeans算法流程上，我們每次更新簇心，是計算本簇中所有樣本點的均值來作為新的簇心，這也就意味著，對於本簇中的所有非簇心樣本，簇心都要與其進行一次距離計算，這還只是一輪，要知道，我們的數據量往往並不是幾十幾百或者幾千。。。這個計算代價，就顯得非常龐大了。
相應的，對於這些缺點，也就有了相應的改進措施。
一、對於簇心初值敏感問題
1、二分kmeans算法：其核心在於二分法。
具體流程：先以所有樣本為一個簇，然後進行kmeans劃分，將一個簇一分為二劃分為兩個簇。然後，再選擇一個簇進行kmeans算法劃分，再次將該簇一分為二，劃分為兩個簇。循環以上操作，直至達到終止條件(這裡終止條件可以是簇的數量或者是迭代次數)。
而這裡最重要的選簇依據一般有兩種：一種是簇中樣本數最多的。另一種即對所有簇進行SSE(即簇中所有非簇心點到簇心點的距離平方和相加所得)計算，選擇SSE最大的簇進行劃分。
2、k-means++算法：其核心也是簇心數目從小到大不斷累加上去。
具體流程：先從所有數據集中隨機選取一個節點作為第一個簇心，然後計算其他所有點到該簇心的距離(當有多個簇心時，則為計算所有點到所有簇心的距離和)，根據距離，按照概率選出下一個簇心，這裡的概率和距離成正比，即距離越大，概率越大。比如a、b、c三點距離簇心距離和分別為3、2、1，則選擇a點的概率為3/(3+2+1)=1/2。重複迭代至找到k個簇心。多補充一句，sklearn中kmeans的簇心初始化方法，一般也默認選擇k-means++。當然，這個是可選可配的。
由於k-means++計算的是所有的樣本點到簇心的距離和，其計算量龐大，故而又有了kmeansII算法。
其具體流程為：先從所有數據集中任選一個節點作為第一個簇心，然後重複logn次，每次隨機選擇k個樣本點，計算k個節點到它的距離(當有多個簇心時，則為計算所有點到所有簇心的距離和),根據距離按概率選出下一個簇心，依然是距離越大，概率越大。重複迭代至找到k個簇心。
那麼以上三種算法都是對於kmeans算法初值敏感問題的改進，進一步說，主要解決的是kmeans初始化k個簇心的問題。而對於kmeans其它的步驟，並不會產生影響，依然還是按原有流程繼續往下走。
二、對於異常點導致偏差大的問題
這裡主要是使用的k中值法來解決，也就是說，不再使用均值法來更新簇心，而均值法是由歐式距離最小化得來的。故而k中值法即並非用歐氏距離來度量樣本之間的距離，k中值用的是曼哈頓距離，相應的，其簇心更新為中位數更新，也就是選取所有樣本的中位數點對應的樣本作為新一輪的簇心。這裡的推導和歐氏距離推均值一個思路，有興趣的可以自己推一推。
三、對於更新簇心求均值，計算慢的問題
這裡則主要使用miniBatch Kmeans算法來解決，其具體思路為：將所有數據集看成一個籃子，先從籃子裡抽取部分數據集，然後根據kmeans算法構建出k個簇心的模型，然後再從籃子中繼續抽取部分數據，繼續添加到現有模型中，分配給距離最近的簇心點，再更新簇心，然後繼續從籃子中取數據，添加至模型，迭代至簇心穩定或達到一定迭代次數。
整體而言，miniBatch kmeans是kmeans的一種簡易版本，計算量少，迭代快，效果上也只是略差於kmeans。但其整體速度相比而言，是毋庸置疑的，當然，這裡的前提是數據量比較大的情況下。
那麼到這裡，kmeans算法的缺點以及其相應的改進算法也就基本明確了。
場景分析
首先，開頭我們便提到，kmeans算法由於其原理簡單，應用廣泛，故而先提。實際上，它確實是屬於用得相對最多的一個。
雖然對於不同的數據類型而言，不同的聚類算法其聚類效果不一樣，比如環形，月牙形等，kmeans的效果並不是很理想，但是現實業務中，大多數情況下，我們要進行聚類的數據多屬於服從高斯分布的數據，而對於這類分布的數據而言，使用kmeans算法還是使用其他的聚類算法，如譜聚類，層次聚類等等，效果上並沒有太大差別，加上kmeans在聚類算法中往往先入為主，也只是輔助作用，效果也不差，故而一般情況下而言，還是會優先考慮選擇使用kmeans算法。
當然，特殊場景，還是需要特殊考慮，尤其是在需要嚴格要求精度的情況下。
kmeans算法的代碼實現
以下是個人實現的kmeans代碼，可簡單參考一下。
從兩圖中可以看出，左邊是原始給定數據樣本點，右邊是聚好類別後的四個簇，整體上看，效果還可以。
排版不佳，還請見諒。
快樂需要傳遞，知識需要分享。
如果感覺還不錯，請幫忙分享推廣。
更多文章請關注