KMeans算法是最常用的聚類算法，主要思想是：在給定K值和K個初始類簇中心點的情況下，把每個點（亦即數據記錄）分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之后，根據一個類簇內的所有點重新計算該類簇的中心點（取平均值），然后再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。

　　KMeans算法本身思想比較簡單，但是合理的確定K值和K個初始類簇中心點對于聚類效果的好壞有很大的影響。

　　1. 確定K個初始類簇中心點

　　最簡單的確定初始類簇中心點的方法是隨機選擇K個點作為初始的類簇中心點，但是該方法在有些情況下的效果較差，如下（下圖中的數據是用五個二元正態高斯分布生成的，顏色代表聚類效果）：

　　《大數據》一書中提到K個初始類簇點的選取還有兩種方法：

　　1）選擇彼此距離盡可能遠的K個點

　　2）先對數據用層次聚類算法或者Canopy算法進行聚類，得到K個簇之后，從每個類簇中選擇一個點，該點可以是該類簇的中心點，或者是距離類簇中心點最近的那個點。

　　1） 選擇批次距離盡可能遠的K個點

　　首先隨機選擇一個點作為第一個初始類簇中心點，然后選擇距離該點最遠的那個點作為第二個初始類簇中心點，然后再選擇距離前兩個點的最近距離最大的點作為第三個初始類簇的中心點，以此類推，直至選出K個初始類簇中心點。

　　該方法經過我測試效果很好，用該方法確定初始類簇點之后運行KMeans得到的結果全部都能完美區分五個類簇：

　　2） 選用層次聚類或者Canopy算法進行初始聚類，然后利用這些類簇的中心點作為KMeans算法初始類簇中心點。

　　常用的層次聚類算法有BIRCH和ROCK，在此不作介紹，下面簡單介紹一下Canopy算法，主要摘自Mahout的Wiki：

　　首先定義兩個距離T1和T2，T1》T2.從初始的點的集合S中隨機移除一個點P，然后對于還在S中的每個點I，計算該點I與點P的距離，如果距離小于T1，則將點I加入到點P所代表的Canopy中，如果距離小于T2，則將點I從集合S中移除，并將點I加入到點P所代表的Canopy中。迭代完一次之后，重新從集合S中隨機選擇一個點作為新的點P，然后重復執行以上步驟。

　　Canopy算法執行完畢后會得到很多Canopy，可以認為每個Canopy都是一個Cluster，與KMeans等硬劃分算法不同，Canopy的聚類結果中每個點有可能屬于多個Canopy。我們可以選擇距離每個Canopy的中心點最近的那個數據點，或者直接選擇每個Canopy的中心點作為KMeans的初始K個類簇中心點。

　　K值的確定。

　　《大數據》中提到：給定一個合適的類簇指標，比如平均半徑或直徑，只要我們假設的類簇的數目等于或者高于真實的類簇的數目時，該指標上升會很緩慢，而一旦試圖得到少于真實數目的類簇時，該指標會急劇上升。

　　類簇的直徑是指類簇內任意兩點之間的最大距離。

　　類簇的半徑是指類簇內所有點到類簇中心距離的最大值。

　　廢話少說，上圖。下圖是當K的取值從2到9時，聚類效果和類簇指標的效果圖：

　　左圖是K取值從2到7時的聚類效果，右圖是K取值從2到9時的類簇指標的變化曲線，此處我選擇類簇指標是K個類簇的平均質心距離的加權平均值。從上圖中可以明顯看到，當K取值5時，類簇指標的下降趨勢最快，所以K的正確取值應該是5.為以下是具體數據：

　　《span style=“background-color： white;”》2 個聚類

　　所有類簇的半徑的加權平均值 8.51916676443

　　所有類簇的平均質心距離的加權平均值 4.82716260322

　　3 個聚類

　　所有類簇的半徑的加權平均值 7.58444829472

　　所有類簇的平均質心距離的加權平均值 3.37661824845

　　4 個聚類

　　所有類簇的半徑的加權平均值 5.65489660064

　　所有類簇的平均質心距離的加權平均值 2.22135360453

　　5 個聚類

　　所有類簇的半徑的加權平均值 3.67478798553

　　所有類簇的平均質心距離的加權平均值 1.25657641195

　　6 個聚類

　　所有類簇的半徑的加權平均值 3.44686996398

　　所有類簇的平均質心距離的加權平均值 1.20944264145

　　7 個聚類

　　所有類簇的半徑的加權平均值 3.3036641135

　　所有類簇的平均質心距離的加權平均值 1.16653919186

　　8 個聚類

　　所有類簇的半徑的加權平均值 3.30268530308

　　所有類簇的平均質心距離的加權平均值 1.11361639906

　　9 個聚類

　　所有類簇的半徑的加權平均值 3.17924400582

　　所有類簇的平均質心距離的加權平均值 1.07431888569《/span》

　　uk是第k 個類的重心位置。成本函數是各個類畸變程度（distortions）之和。每個類的畸變程度等于該類重心與其內部成員位置距離的平方和。若類內部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內部的成員彼此間越分散則類的畸變程度越大。求解成本函數最小化的參數就是一個重復配置每個類包含的觀測值，并不斷移動類重心的過程。

　　#-*- coding:utf-8 -*-

　　import numpy as np

　　import matplotlib.pyplot as plt

　　from sklearn.cluster import KMeans

　　from scipy.spatial.distance import cdist

　　import sys

　　reload（sys）

　　sys.setdefaultencoding（‘utf-8’）

　　x = np.array（［1， 2， 3， 1， 5， 6， 5， 5， 6， 7， 8， 9， 7， 9］）

　　y = np.array（［1， 3， 2， 2， 8， 6， 7， 6， 7， 1， 2， 1， 1， 3］）

　　data = np.array（list（zip（x， y）））

　　# 肘部法則 求解最佳分類數

　　# K-Means參數的最優解也是以成本函數最小化為目標

　　# 成本函數是各個類畸變程度（distortions）之和。每個類的畸變程度等于該類重心與其內部成員位置距離的平方和

　　‘’‘’‘aa=［］

　　K = range（1， 10）

　　for k in range（1，10）：

　　kmeans=KMeans（n_clusters=k）

　　kmeans.fit（data）

　　aa.append（sum（np.min（cdist（data， kmeans.cluster_centers_， ’euclidean‘），axis=1））/data.shape［0］）

　　plt.figure（）

　　plt.plot（np.array（K）， aa， ’bx-‘）

　　plt.show（）’‘’

　　#繪制散點圖及聚類結果中心點

　　plt.figure（）

　　plt.axis（［0， 10， 0， 10］）

　　plt.grid（True）

　　plt.plot（x，y，‘k.’）

　　kmeans=KMeans（n_clusters=3）

　　kmeans.fit（data）

　　plt.plot（kmeans.cluster_centers_［：，0］，kmeans.cluster_centers_［：，1］，‘r.’）

　　plt.show（）