在數據分析中，我們常常想將看上去相似或者行為形似的數據聚合在一起。例如，對一個營銷組織來說，將不同客戶根據他們的特點進行分組，從而有針對性地定制營銷活動，這很重要。又比如，對學校老師來說，將學生分組同樣能夠有所側重的進行教育活動。分類與聚類是數據挖掘領域兩大基礎方法，分類被用于監督學習中而聚類算法屬于無監督的。聚類算法主要是將相似的數據聚合在一起形成不同的組別，但是組與組之間相差很大。
在本次分享中，我將給大家介紹一種無監督算法K-means算法，為什么介紹這種算法呢？因為這種算法概念簡單，實現容易，而且好用！

K-means算法是一種無監督學習算法，可以被應用到無標簽的數據中。這個算法的目的就是要找到數據的分組，分組的數目由K指定。這個算法基于提供的特征，迭代地將數據分配個K個組別的其中一個。數據是基于數據相似性被聚類的。K-means聚類算法的結果就是：

K個聚類中心，可以用來標注新的數據

數據標簽，每個數據都被分配給一個簇

基本K-means算法的相似性度量是基于距離計算的，最典型的就是歐幾里得距離。歐幾里得距離計算給定兩點之間的距離，公式如下：

disted(xi,xj)=||xi?xj||2=∑u=1n|xiu?xju|2????????????√

K-means算法的流程很簡單，具體如下：

首先，隨機確定k個初始點作為質心。

然后將數據集中的每個點分配到一個簇中，具體來講，為每個點找距其最近的質心，并將其分配給該質心所對應的簇。

將每個簇的質心更新為該簇所有點的平均值

如果質心不再變化或者說變化很小，退出循環，否則返回到第二步

K-means的偽代碼如下：

因為在前面一次博文分享中，有講到K-means算法的實際應用場景，大家可以直接調轉到那里去： 基于改進的K-means算法在共享交通行業客戶細分中的應用那篇博文使用的K-means算法是sklearn中的K-means++算法。

K-means算法在實際使用中存在一些不足。在實際使用中，我們發現K-means對初始點的選取很敏感，這種敏感就會導致K-means算法很可能收斂到局部最優。于是有人提出了兩種方法，一種是K-means++，一種是二分K-means算法來盡量使K-means達到全局最優。

k-means++算法選擇初始聚類中心的基本原則是：初始的聚類中心之間的相互距離要盡可能的遠。它選擇初始聚類中心的步驟是：

（1）從輸入的數據點集合中隨機選擇一個點作為第一個聚類中心；
（2）對于數據集中的每一個點x，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(x)，并根據以下概率選擇新的聚類中心。
（3）重復過程（2）直到找到k個聚類中心。

二分K-means使用一種度量聚類效果的指標是SSE(Sum of Squared Error，誤差平方和)。SSE越小表示數據點越接近它們的質心，聚類效果也是最好。二分K-means算法的工作流程是：

（1）首先將所有點作為一個簇，然后將簇一分為二

（2）之后選擇其中一個簇繼續進行劃分，選擇哪一個簇進行劃分取決于對其劃分是否可以最大程度地降低SSE的值

（3）上述基于SSE的劃分過程不斷重復，直到得到用戶指定的簇數目為止。

這個k值選擇的問題，講真目前還真沒有什么太好的方法解決，一般都是實際業務場景，靠工程經驗去判定k的取值。

上面K-means的實現我們是基于歐幾里得距離的，但是實際業務場景中有很多的距離計算方式，有個叫”distance metric learning”的實現方法可以用來做這件事情。本博文就不做介紹了。