K-means中心思想:事先確定常數K,常數K意味著最終的聚類類別數,首先隨機選定初始點為質心,並通過計算每一個樣本與質心之間的相似度(這裡為歐式距離),將樣本點歸到最相似的類中,接著,重新計算每個類的質心(即為類中心),重複這樣的過程,直到質心不再改變,最終就確定了每個樣本所屬的類別以及每個類的質心。由於每次都要計算所有的樣本與每一個質心之間的相似度,故在大規模的數據集上,K-Means算法的收斂速度比較慢。
聚類算法:是一種典型的無監督學習算法,主要用於將相似的樣本自動歸到一個類別中。
聚類算法與分類算法最大的區別是:聚類算法是無監督的學習算法,而分類算法屬於監督的學習算法,分類是知道結果的。
在聚類算法中根據樣本之間的相似性,將樣本劃分到不同的類別中,對於不同的相似度計算方法,會得到不同的聚類結果,常用的相似度計算方法有歐式距離法。
k-means算法流程1.選擇聚類的個數k(kmeans算法傳遞超參數的時候,只需設置最大的K值)
2.任意產生k個聚類,然後確定聚類中心,或者直接生成k個中心。
3.對每個點確定其聚類中心點。
4.再計算其聚類新中心。
5.重複以上步驟直到滿足收斂要求。(通常就是確定的中心點不再改變。)
k-means優點與缺點優點:
1、原理簡單(靠近中心點) ,實現容易
2、聚類效果中上(依賴K的選擇)
3、空間複雜度o(N)時間複雜度o(IKN,N為樣本點個數,K為中心點個數,I為迭代次數)
缺點:
1、對離群點, 噪聲敏感 (中心點易偏移)
2、很難發現大小差別很大的簇及進行增量計算
3、結果不一定是全局最優,只能保證局部最優(與K的個數及初值選取有關)
k-means的經典案例與適用範圍1.文檔分類器:根據標籤、主題和文檔內容將文檔分為多個不同的類別。這是一個非常標準且經典的K-means算法分類問題。
2.物品傳輸優化:使用K-means算法的組合找到無人機最佳發射位置和遺傳算法來解決旅行商的行車路線問題,優化無人機物品傳輸過程。
3.識別犯罪地點:使用城市中特定地區的相關犯罪數據,分析犯罪類別、犯罪地點以及兩者之間的關聯,可以對城市或區域中容易犯罪的地區做高質量的勘察。
4.客戶分類聚類能過幫助營銷人員改善他們的客戶群(在其目標區域內工作),並根據客戶的購買歷史、興趣或活動監控來對客戶類別做進一步細分。
5.球隊狀態分析:分析球員的狀態一直都是體育界的一個關鍵要素。隨著競爭越來愈激烈,機器學習在這個領域也扮演著至關重要的角色。如果你想創建一個優秀的隊伍並且喜歡根據球員狀態來識別類似的球員,那麼K-means算法是一個很好的選擇。
6.保險欺詐檢測:利用以往欺詐性索賠的歷史數據,根據它和欺詐性模式聚類的相似性來識別新的索賠。由於保險欺詐可能會對公司造成數百萬美元的損失,因此欺詐檢測對公司來說至關重要。
7.乘車數據分析:面向大眾公開的Uber乘車信息的數據集,為我們提供了大量關於交通、運輸時間、高峰乘車地點等有價值的數據集。分析這些數據不僅對Uber大有好處,而且有助於我們對城市的交通模式進行深入的了解,來幫助我們做城市未來規劃。
8.網絡分析犯罪分子:網絡分析是從個人和團體中收集數據來識別二者之間的重要關係的過程。網絡分析源自於犯罪檔案,該檔案提供了調查部門的信息,以對犯罪現場的罪犯進行分類。
9.呼叫記錄詳細分析:通話詳細記錄(CDR)是電信公司在對用戶的通話、簡訊和網絡活動信息的收集。將通話詳細記錄與客戶個人資料結合在一起,這能夠幫助電信公司對客戶需求做更多的預測。
10.IT警報的自動化聚類:大型企業IT基礎架構技術組件(如網絡,存儲或資料庫)會生成大量的警報消息。由於警報消息可以指向具體的操作,因此必須對警報信息進行手動篩選,確保後續過程的優先級。對數據進行聚類可以對警報類別和平均修復時間做深入了解,有助於對未來故障進行預測。
sk-learns的參數詳解與調優流程不像監督學習的分類問題和回歸問題,無監督聚類沒有樣本輸出,也就沒有比較直接的聚類評估方法。目前來講有兩種方法能夠比較好的確定k的取值:
(1)慣性確定法,慣性只樣本到其最近聚類中心的平方距離之和。基於歐幾裡得距離,K-Means算法需要優化的問題就是,使得簇內誤差平方和(within-cluster sum of squared errors,SSE)最小,也叫簇慣性(cluster intertia)。隨著分類數量的增多,SE的數值也會變得越來越小,但並不是分類數量越多越好,在選擇時就需要選擇『拐點處的k值』後邊有詳細介紹。
SSE
(2)另一種方法是從簇內的稠密程度和簇間的離散程度來評估聚類的效果。常見的方法有輪廓係數Silhouette Coefficient和Calinski-Harabasz Index。個人比較喜歡Calinski-Harabasz Index,這個計算簡單直接,得到的Calinski-Harabasz分數值s越大則聚類效果越好。Calinski-Harabasz分數值s的數學計算公式是:
Calinski-Harabasz
其中m為訓練集樣本數,k為類別數。Bk為類別之間的協方差矩陣,Wk為類別內部數據的協方差矩陣。tr為矩陣的跡。也就是說,類別內部數據的協方差越小越好,類別之間的協方差越大越好,這樣的Calinski-Harabasz分數會高。在scikit-learn中, Calinski-Harabasz Index對應的方法是metrics.calinski_harabsaz_score.
實戰案例-使用sk_learn裡的KMeans模塊進行演示:import numpy as npimport matplotlib.pyplot as pltfrom sklearn.cluster import KMeansfrom sklearn.datasets import make_blobs from sklearn import metricsn_samples=5000 random_state=10 centers=5 x, y = make_blobs(centers=centers,n_samples=n_samples, random_state=random_state) plt.figure(figsize=(25, 25))plt.subplot(4,3,1)plt.scatter(x[:,0],x[:,1],c=y)plt.title('initial data')生成的測試數據如下:
原始數據
對數據進行計算,n_clusters的取值範圍在2~9,並記錄每一個n_clustrs取值時的SSE與calinski_harabaz_score取值:
inertia=[]calinski_harabaz_score=[]a=2for i in range(2,10): km = KMeans(n_clusters=i,n_init=10,init='k-means++').fit(x) y_pred=km.predict(x) center_=km.cluster_centers_ inertia.append([i,km.inertia_]) z=metrics.calinski_harabaz_score(x, y_pred) calinski_harabaz_score.append([i,z]) plt.subplot(4,3,a) a=a+1 plt.scatter(x[:,0],x[:,1],c=y_pred) plt.scatter(center_[:,0],center_[:,1],color='red') plt.title('n_clusters=%s'%i)inertia=np.array(inertia)plt.subplot(4,3,10)plt.plot(inertia[:, 0], inertia[:, 1])plt.title('SSE - n_clusters')plt.subplot(4,3,11)calinski_harabaz_score=np.array(calinski_harabaz_score)plt.plot(calinski_harabaz_score[:, 0], calinski_harabaz_score[:, 1])plt.title('calinski_harabaz_score - n_clusters')plt.show()最終結果如下:n_clusters=2
n_clusters=2
n_clusters=5
n_clusters=5
n_clusters=9
n_clusters=9
在不同的n_clusters取值情況下,SSE與calinski_harabaz_score的取值情況:
SSE隨n_clusters變化
metrics.calinski_harabsaz_score隨n_clusters的變化
通過SSE的定義可知,SSE隨著n_clusters的增大是會變小的,一般會在SSE出現拐點的地方取值,同時還需要參考calinski_harabaz_score的取值。在此案例中能夠看出,SSE在n_clusters=5的時候出現較大的拐點,calinski_harabaz_score在n_clusters=5的時候取得最大值。