什麼是K-Means？
維基百科，自由的百科全書中提到
K-平均算法（英文：k-means clustering）源於信號處理中的一種向量量化方法，現在則更多地作為一種聚類分析方法流行於數據挖掘領域。k-平均聚類的目的是：把n個點（可以是樣本的一次觀察或一個實例）劃分到k個聚類中，使得每個點都屬於離他最近的均值（此即聚類中心）對應的聚類，以之作為聚類的標準。這個問題將歸結為一個把數據空間劃分為Voronoi cells的問題。
這個問題在計算上是NP困難的，不過存在高效的啟發式算法。一般情況下，都使用效率比較高的啟發式算法，它們能夠快速收斂於一個局部最優解。這些算法通常類似於通過迭代優化方法處理高斯混合分布的最大期望算法（EM算法）。而且，它們都使用聚類中心來為數據建模；然而k-平均聚類傾向於在可比較的空間範圍內尋找聚類，期望-最大化技術卻允許聚類有不同的形狀。
簡單理解為：聚類是一個將數據集中在某些方面相似的數據成員進行分類組織的過程，聚類就是一種發現這種內在結構的技術，聚類技術經常被稱為無監督學習。k均值聚類是最著名的劃分聚類算法，由於簡潔和效率使得他成為所有聚類算法中最廣泛使用的。給定一個數據點集合和需要的聚類數目k，k由用戶指定，k均值算法根據某個距離函數反覆把數據分入k個聚類中
K-Means做法與生活例子
做法
隨機選取K各中心點，生成對應的k個簇遍歷所有的數據點，依據「距離」將每一個數據點劃分到最近的中心點所在的簇計算每個簇所有的數據點的平均值，並作為該簇新的中心。重複2-3步，直到這k個簇的中心點不再變化，或者達到我們規定的迭代次數生活中的例子
文檔分類器根據標籤、主題和文檔內容將文檔分為多個不同的類別。這是一個非常標準且經典的K-means算法分類問題。首先，需要對文檔進行初始化處理，將每個文檔都用矢量來表示，並使用術語頻率來識別常用術語進行文檔分類，這一步很有必要。然後對文檔向量進行聚類，識別文檔組中的相似性。這裡是用於文檔分類的K-means算法實現案例。物品傳輸優化使用K-means算法的組合找到無人機最佳發射位置和遺傳算法來解決旅行商的行車路線問題，優化無人機物品傳輸過程。識別犯罪地點使用城市中特定地區的相關犯罪數據，分析犯罪類別、犯罪地點以及兩者之間的關聯，可以對城市或區域中容易犯罪的地區做高質量的勘察。乘車數據分析面向大眾公開的乘車信息的數據集，為我們提供了大量關於交通、運輸時間、高峰乘車地點等有價值的數據集。分析這些數據不僅對大有好處，而且有助於我們對城市的交通模式進行深入的了解，來幫助我們做城市未來規劃網絡分析犯罪分子網絡分析是從個人和團體中收集數據來識別二者之間的重要關係的過程。網絡分析源自於犯罪檔案，該檔案提供了調查部門的信息，以對犯罪現場的罪犯進行分類。保險欺詐檢測機器學習在欺詐檢測中也扮演著一個至關重要的角色，在汽車、醫療保險和保險欺詐檢測領域中廣泛應用。利用以往欺詐性索賠的歷史數據，根據它和欺詐性模式聚類的相似性來識別新的索賠。由於保險欺詐可能會對公司造成數百萬美元的損失，因此欺詐檢測對公司來說至關重要。客戶分類聚類能過幫助營銷人員改善他們的客戶群（在其目標區域內工作），並根據客戶的購買歷史、興趣或活動監控來對客戶類別做進一步細分。這是關於電信運營商如何將預付費客戶分為充值模式、發送簡訊和瀏覽網站幾個類別的白皮書。對客戶進行分類有助於公司針對特定客戶群制定特定的廣告。球隊狀態分析分析球員的狀態一直都是體育界的一個關鍵要素。隨著競爭越來愈激烈，機器學習在這個領域也扮演著至關重要的角色。如果你想創建一個優秀的隊伍並且喜歡根據球員狀態來識別類似的球員，那麼K-means算法是一個很好的選擇。K-Means數學算法
已知觀測集{x1,x2,…,xn}，其中每個觀測都是一個d-維實向量，K-Means要把這n個觀測劃分到k個集合中(k≤n),使得組內平方和最小。換句話說，它的目標是找到使得下式滿足的聚類Ci其中：x是Ci中的樣本點， mi是Ci的質心（Ci中所有樣本的均值）,SSE(誤差平方和)是所有樣本的聚類誤差，代表了聚類效果的好壞
怎樣讓SSE最小呢？——求導！
K-Means代碼實現
1. 引入依賴
1import numpy as np2import matplotlib.pyplot as plt34# 從sklearn中直接生成聚類數據5from sklearn.datasets.samples_generator import make_blobsmake_blobs方法常被用來生成聚類算法的測試數據，直觀地說，make_blobs會根據用戶指定的特徵數量、中心點數量、範圍等來生成幾類數據，這些數據可用於測試聚類算法的效果。下面會介紹參數詳情。
Sklearn提供的常用數據集
自帶的小數據集（packageddataset）：sklearn.datasets.load_
還有可在線下載的數據集；計算機生成的數據集；svmlight/libsvm格式的數據集；data.org在線下載獲取的數據集。 這裡不在一一羅列。列舉的目的是讓你知道有這個東西
2. 數據加載
1x, y = make_blobs( n_samples=200, centers=6, random_state=1234, cluster_std=0.6 )23plt.figure(figsize=(6,6))4plt.scatter(x[:,0], x[:,1], c=y)5plt.show()6x,ymake_blobs參數解釋
返回值類型
效果圖
3. 算法實現
1# 引入scipy中的距離函數，默認歐式距離 2from scipy.spatial.distance import cdist 3 4classK_Means(object): 5# 初始化，參數 n_clusters（K）、迭代次數max_iter、初始質心 centroids 6def__init__(self, n_clusters=6, max_iter=300, centroids=[]): 7self.n_clusters = n_clusters 8self.max_iter = max_iter 9self.centroids = np.array( centroids, dtype=np.float )1011# 訓練模型方法，k-means聚類過程，傳入原始數據12deffit(self, data):13# 假如沒有指定初始質心，就隨機選取data中的點作為初始質心14if( self.centroids.shape == (0,) ):15# 從data中隨機生成0到data行數的6個整數，作為索引值16self.centroids = data[ np.random.randint( 0, data.shape[0], self.n_clusters ) ,: ]1718# 開始迭代19for i in range(self.max_iter):20# 1. 計算距離矩陣，得到的是一個100*6的矩陣21 distances = cdist(data, self.centroids)2223# 2. 對距離按有近到遠排序，選取最近的質心點的類別，作為當前點的分類24 c_ind = np.argmin( distances, axis=1 )2526# 3. 對每一類數據進行均值計算，更新質心點坐標27for i in range(self.n_clusters):28# 排除掉沒有出現在c_ind裡的類別29if i inc_ind:30# 選出所有類別是i的點，取data裡面坐標的均值，更新第i個質心31self.centroids[i] = np.mean( data[c_ind==i], axis=0 )3233# 實現預測方法34defpredict(self, samples):35# 跟上面一樣，先計算距離矩陣，然後選取距離最近的那個質心的類別36 distances = cdist(samples, self.centroids)37 c_ind = np.argmin( distances, axis=1 )3839return c_ind4041dist = np.array([[121,221,32,43],42 [121,1,12,23],43 [65,21,2,43],44 [1,221,32,43],45 [21,11,22,3],])46c_ind = np.argmin( dist, axis=1 )47x_new=x[0:5]48np.mean(x_new[c_ind==2], axis=0)一些方法解釋
numpy.argmin(a, axis)表示最小值在數組中所在的位置若添加答axis這個參數求在回行或者列方向上的最小值索答引axis=0 表示列方向上的最小值索引，axis=1表示行方向的最小值索引numpy.mean(a, axis, dtype, out，keepdims)求取均值,經常操作的參數為axis，以m * n矩陣舉例：axis 不設置值，對 m*n 個數求均值，返回一個實數axis = 0：壓縮行，對各列求均值，返回 1* n 矩陣axis =1 ：壓縮列，對各行求均值，返回 m *1 矩陣4. 測試
1# 定義一個繪製子圖函數 2def plotKMeans(x, y, centroids, subplot, title): 3 # 分配子圖，121表示1行2列的子圖中的第一個 4 plt.subplot(subplot) 5 plt.scatter(x[:,0], x[:,1], c='r') 6 # 畫出質心點 7 plt.scatter(centroids[:,0], centroids[:,1], c=np.array(range(6)), s=100) 8 plt.title(title) 910kmeans = K_Means(max_iter=300, centroids=np.array([[2,1],[2,2],[2,3],[2,4],[2,5],[2,6]]))111213plt.figure(figsize=(16, 6))14plotKMeans( x, y, kmeans.centroids, 121, 'Initial State' )1516# 開始聚類17kmeans.fit(x)1819plotKMeans( x, y, kmeans.centroids, 122, 'Final State' )2021# 預測新數據點的類別22x_new = np.array([[0,0],[-3,7]])23y_pred = kmeans.predict(x_new)2425print(kmeans.centroids)26print(y_pred)2728plt.scatter(x_new[:,0], x_new[:,1], s=100, c='black')效果圖
附加：用肘部法則來確定最佳的K值
當Kmeans聚類的K沒有指定時，可以通過肘部法來估計聚類數量K_means參數的最優解是以成本函數最小化為目標每個類的畸變程度等於該類重心與其內部成員位置距離的平方和
參數解釋
代碼
1import numpy as np 2from sklearn.cluster import KMeans 3from scipy.spatial.distance import cdist 4import matplotlib.pyplot as plt 5cluster1 = np.random.uniform(0.5, 1.5, (2, 10)) 6cluster2 = np.random.uniform(3.5, 4.5, (2, 10)) 7X = np.hstack((cluster1, cluster2)).T 8K = range(1, 10) 9meandistortions = []10for k in K:11 kmeans = KMeans(n_clusters=k)12 kmeans.fit(X)13 meandistortions.append(sum(np.min(cdist(X,kmeans.cluster_centers_, 'euclidean'), axis=1)) / X.shape[0])14print(meandistortions)15plt.plot(K, meandistortions, 'bx-')16plt.xlabel('k')17# plt.ylabel('平均畸變程度',fontproperties=font)18plt.ylabel('Ave Distor')19# plt.title('用肘部法則來確定最佳的K值',fontproperties=font);20plt.title('Elbow method value K');21plt.show()一些方法解釋
效果圖
從圖中可以看出圖片像一隻手肘，肘處的K即為最佳K值：K=2
至此，K-Means算法介紹完了
機器學習未完待續 ……歡迎關注