k-means算法

2021-02-08 交通運輸規劃與管理專業
k-means算法原理

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的時候取得最大值。

相關焦點

  • 機器學習算法之K-means算法
    K-means舉例shi'li1 K-means算法簡介k-means算法是一種聚類算法,所謂聚類,即根據相似性原則2 K-means算法原理k-means算法中的k代表類簇個數,means代表類簇內數據對象的均值(這種均值是一種對類簇中心的描述),因此,k-means算法又稱為k-均值算法。
  • 基本的k-means算法流程
    打開APP 基本的k-means算法流程 李倩 發表於 2018-07-24 17:44:21 1、引言 k-means
  • k-means聚類算法原理總結
    目錄1. k-means聚類算法原理2. k-means聚類算法步驟3. k-means++聚類優化算法4.小批量處理的k-means聚類算法5. k值的選取6. k-means聚類算法不適用的幾個場景7. k-means與knn區別8. 小結聚類算法性能度量的文章提到若簇類相似度好簇間的相似度差,則聚類算法的性能較好。我們基於此定義k-means聚類算法的目標函數: 其中
  • 詳解 kmeans 聚類算法
    也是聚類算法中最簡單的一種了,但是裡面包含的思想卻是不一般。。下圖展示了對n個樣本點進行K-means聚類的效果,這裡k取2。     K-means面對的第一個問題是如何保證收斂,前面的算法中強調結束條件就是收斂,可以證明的是K-means完全可以保證收斂性。
  • k-means聚類算法從入門到精通
    目錄1. k-means聚類算法原理2. k-means聚類算法步驟3. k-means++聚類優化算法4.小批量處理的k-means聚類算法5. k值的選取6. k-means聚類算法不適用的幾個場景7. k-means與knn區別8. 小結聚類算法性能度量的文章提到若簇類相似度好簇間的相似度差,則聚類算法的性能較好。我們基於此定義k-means聚類算法的目標函數: 其中
  • K-Means聚類算法
    ,與之前提到的樸素貝葉斯等算法不同,它屬於無監督學習。簡單來說,之前的算法中我們是利用特徵 x 和類別 y 來進行訓練、分類的,而無監督學習是指不需要我們提供具體的類別 y ,而讓數據自己聚在一起,形成 k 個簇,以實現分類的目的。具體方法是通過對給定的樣本進行劃分,分為 k 個簇,使得簇內的點儘量緊密的連在一起,而簇間的距離儘量大,評判的標準就是通過歐氏距離。
  • K-Means聚類算法詳解
    random 的方式則是完全隨機的方式,一般推薦採用優化過的 k-means++ 方式;algorithm:k-means 的實現算法,有「auto」 「full」「elkan」三種。一般來說建議直接用默認的"auto"。簡單說下這三個取值的區別,如果你選擇"full"採用的是傳統的 K-Means 算法,「auto」會根據數據的特點自動選擇是選擇「full」還是「elkan」。
  • 聚類算法之Kmeans
    Kmeans算法,也叫k均值算法,顧名思義,其核心思想也就是根據均值來更新簇心。其具體算法流程如下:1、隨機初始化k個簇心2、對於每個樣本,根據其到各簇心的距離(這裡用歐式距離),將其標註為距離最近的簇心類別。
  • 聚類算法入門:k-means
    比如垃圾分類就是分類算法,你知道豬能吃的是溼垃圾,不能吃的是幹垃圾……;打掃房間時你把雜物都分分類,這是聚類,你事先不知道每個類別的標準。二、劃分聚類方法: K-means:對於給定的樣本集,按照樣本之間的距離(也就是相似程度)大小,將樣本集劃分為K個簇(即類別)。
  • kmeans優化算法:二分Kmeans聚類算法
    算法的理解Bi這裡是的意思就是Binary,二進位的意思,所以有時候叫這個算法為二進Kmeans算法。為什麼我們需要用BiKmeans呢,就是為了解決初始化k個隨機的質心點時其中一個或者多個點由於位置太極端而導致迭代的過程中消失的問題。
  • K-means 聚類算法及其代碼實現
    K-means聚類算法的思想,同時給出在matlab環境中實現K-means算法的代碼。代碼使用向量化(vectorization1)來計算,可能不是很直觀但是效率比使用循環算法高。K-means算法本節首先直觀敘述要解決的問題,然後給出所要求解的數學模型,最後從EM2 算法的角度分析K-means算法的特點。
  • 使用K-means 算法進行客戶分類
    ,xn),其中每一個觀測值都是d維實數向量,K均值聚類旨在將n個觀測值劃分為k(k≤n)個集合S={S1,S2,...,Sk}以最小化聚類內的平方和,其中µi是Si中的點的平均值。保證K-Means算法收斂到局部最優。
  • 機器學習十大經典算法之K-Means聚類算法
    K-Means聚類算法簡介K-Means是發現給定數據集的 K 個簇的聚類算法, 之所以稱之為 K-均值是因為它可以發現 K 個不同的簇, 且每個簇的中心採用簇中所含值的均值計算而成。簇個數 K 是用戶指定的, 每一個簇通過其質心(centroid), 即簇中所有點的中心來描述。聚類與分類算法的最大區別在於, 分類的目標類別已知, 而聚類的目標類別是未知的。
  • 算法雜貨鋪——k均值聚類(K-means)
    本文首先介紹聚類的基礎——距離與相異度,然後介紹一種常見的聚類算法 ——k均值和k中心點聚類,最後會舉一個實例:應用聚類方法試圖解決一個在體育界大家頗具爭議的問題——中國男足近幾年在亞洲到底處於幾流水平。4.2、相異度計算      在正式討論聚類前,我們要先弄清楚一個問題:如何定量計算兩個可比較元素間的相異度。
  • 數據挖掘十大算法 ——The k-means algorithm(二)
    、EM、PageRank、AdaBoost、kNN、Naive Bayes 和 CART。不僅它與處理混合正態分布的最大期望算法很相似,因為他們都試圖找到數據中自然聚類的中心。它假設對象屬性來自於空間向量,並且目標是使各個群組內部的均 方誤差總和最小。  假設有k個群組Si, i=1,2,...,k。μi是群組Si內所有元素xj的重心,或叫中心點。
  • python之kmeans數據聚類算法
    一 Kmeans原理kmeans是屬於無監督學習的數據聚類算法,根據點與點之間的距離推測每個點屬於哪個中心,常用計算距離的方式有:餘弦距離、歐式距離、曼哈頓距離等,本文以歐式距離為例。圖3kmeans實現邏輯:需要輸入待聚類的數據和欲聚類簇數k1.隨機生成k個初始點作為質心
  • 機器學習之SKlearn(scikit-learn)的K-means聚類算法
    Sklearn聚類算法對比Sklearn聚類算法官方列舉了不同的算法,大家可以根據自己的數據特徵,以及需要解決的問題,選擇不同的算法,本期我們首先簡單了解一下K-means算法Sklearn聚類算法的K-means
  • python機器學習之k-means聚類算法(1)
    k-means算法是一種無監督的機器學習算法,雖然是機器學習,但它簡單易於實現。本篇採用python語言,自主編程實現k-menas算法,當然python用專門的庫函數來實現該算法,但本次主要使用該算法闡述編程思想,所以不採用內置函數。採用自主編寫的程序的方式。
  • 深入淺出K-Means算法
    在數據挖掘中,K-Means算法是一種cluster analysis的算法,其主要是來計算數據聚集的算法,主要通過不斷地取離種子點最近均值的算法。問題K-Means算法主要解決的問題如下圖所示。我們可以看到,在圖的左邊有一些點,我們用肉眼可以看出來有四個點群,但是我們怎麼通過電腦程式找出這幾個點群來呢?
  • 機器學習之分類算法K-Means介紹與代碼分析(篇四)
    維基百科,自由的百科全書中提到K-平均算法(英文:k-means clustering)源於信號處理中的一種向量量化方法,現在則更多地作為一種聚類分析方法流行於數據挖掘領域。一般情況下,都使用效率比較高的啟發式算法,它們能夠快速收斂於一個局部最優解。這些算法通常類似於通過迭代優化方法處理高斯混合分布的最大期望算法(EM算法)。而且,它們都使用聚類中心來為數據建模;然而k-平均聚類傾向於在可比較的空間範圍內尋找聚類,期望-最大化技術卻允許聚類有不同的形狀。