當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

4.K-MEANS聚类算法

發布時間：2024/9/27 编程问答 24 豆豆

生活随笔收集整理的這篇文章主要介紹了 4.K-MEANS聚类算法小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

4.K-MEANS聚類算法
4.1.概述
4.2.算法核心思想
4.3.K-Means原理初探
4.4.傳統K-Means算法流程
4.5.K-Means初始化優化K-Means++
4.7.大樣本優化Mini Batch K-Means
4.8.K-Means與KNN
4.9.KMEANS術語
4.10.KMEANS算法優缺點
4.11.K-Means算法API文檔簡介
4.12.K-MEANS算法樣例演示
4.13.KMeans算法的十大應用
4.13.1.文檔分類器
4.13.2.物品傳輸優化
4.13.3.識別犯罪地點
4.13.4.客戶分類
4.13.5.球隊狀態分析
4.13.6.保險欺詐檢測
4.13.7.乘車數據分析
4.13.8.網絡分析犯罪分子
4.13.9.呼叫記錄詳細分析
4.13.10.IT警報的自動化聚類
4.14.參考文章

4.K-MEANS聚類算法

K-Means算法是無監督的聚類算法，它實現起來比較簡單，聚類效果也不錯，因此應用很廣泛。K-Means算法有大量的變體，本文就從最傳統的K-Means算法講起，在其基礎上講述K-Means的優化變體方法。包括初始化優化K-Means++, 距離計算優化elkan K-Means算法和大數據情況下的優化Mini Batch K-Means算法。

4.1.概述

K-means聚類算法也稱k均值聚類算法，是集簡單和經典于一身的基于距離的聚類算法。它采用距離作為評價指標，即認為兩個對象的距離越近，其相似度就越大。該算法認為類簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標。

4.2.算法核心思想

K-means聚類算法是一種迭代求解的聚類分析算法，其步驟是隨機選取K個對象作為初始的聚類中心，然后計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。每分配一個樣本，聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是沒有（或最小數目）對象被重新分配給不同的聚類，沒有（或最小數目）聚類中心再發生變化，誤差平方和局部最小。

4.3.K-Means原理初探

L-Means算法的思想很簡單，對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為k個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大。

如果用數據表達式表示，假設簇劃分為k個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大。

如果我們想直接求上式的最小值并不容易，這是一個NP難的問題，因此只能采用啟發式的迭代方法。
K-Means采用的啟發方式很簡單，用下面的一組圖就可以形象的描述。

上圖a表達了初始的數據集，假設k=2。在圖b中，我們隨機選擇了兩個k類所對應的類別質心，即圖中的紅色質心和藍色質心，然后分別求樣本中所有點到這兩個質心的距離，并標記每個樣本的類別為和該樣本距離最小的質心的類別，如圖c所示，經過計算樣本和紅色質心和藍色質心的距離，我們得到了所有樣本點的第一輪迭代后的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心，如圖d所示，新的紅色質心和藍色質心的位置已經發生了變動。圖e和圖f重復了我們在圖c和圖d的過程，即將所有點的類別標記為距離最近的質心的類別并求新的質心。最終我們得到的兩個類別如圖f。

當然在實際的K-Means算法中，我們一般會多次運行圖c和圖d，才能達到最終的比較優的類別。

4.4.傳統K-Means算法流程

在上一節我們對K-Means的原理做了初步的探討，這里我們對K-Means的算法做一個總結。

首先我們看看K-Means算法的一些要點：
1）對于K-Means算法，首先要注意的是k值的選擇，一般來說，我們會根據對數據的先驗經驗選擇一個合適的k值，如果沒有什么先驗知識，則可以通過交叉驗證選擇一個合適的k值。
2）在確定了k的個數后，我們需要選擇k個初始化的質心，就像上圖b中的隨機質心。由于我們是啟發式方法，k個初始化的質心的位置選擇對最后的聚類結果和運行時間都有很大的影響，因此需要選擇合適的k個質心，最好這些質心不能太近。

好了，現在我們來總結下傳統的K-Means算法流程。

總結：
1、首先確定一個k值，即我們希望將數據集經過聚類得到k個集合。
2、從數據集中隨機選擇k個數據點作為質心。
3、對數據集中每一個點，計算其與每一個質心的距離（如歐式距離），離哪個質心近，就劃分到那個質心所屬的集合。
4、把所有數據歸好集合后，一共有k個集合。然后重新計算每個集合的質心。
5、如果新計算出來的質心和原來的質心之間的距離小于某一個設置的閾值（表示重新計算的質心的位置變化不大，趨于穩定，或者說收斂），我們可以認為聚類已經達到期望的結果，算法終止。
6、如果新質心和原質心距離變化很大，需要迭代3~5步驟。

4.5.K-Means初始化優化K-Means++

在上節我們提到，k個初始化的質心的位置選擇對最后的聚類結果和運行時間都有很大的影響，因此需要選擇合適的k個質心。如果僅僅是完全隨機的選擇，有可能導致算法收斂很慢。K-Means++算法就是對K-Means隨機初始化質心的方法的優化。

K-Means++對于初始化質心的優化策略也很簡單，如下：

4.7.大樣本優化Mini Batch K-Means

在傳統的K-Means算法中，要計算所有的樣本點到所有質心的距離。如果樣本量非常大，比如達到10萬以上，特有的100萬以上，此時用傳統的K-Means算法非常的耗時，就算加上elkan K-Means優化也依舊。在大數據時代，這樣的場景越來越多。此時Mini Batch K-Means應用而生。

顧名思義，Mini Batch，也就是用樣本集中的一部分的樣本來做傳統的K-Means，這樣可以避免樣本量太大時的計算難題，算法收斂速度大大加快。當然此時的代價就是我們的聚類的精確度也會有一些降低。一般來說這個降低的幅度在可以接受的范圍之內。

在Mini Batch K-Means中，我們會選擇一個合適的批樣本大小batch size，我們僅僅用batch size個樣本來做K-Means聚類。那么這batch size個樣本怎么來的？一般是通過無放回的隨機采樣得到的。

為了增加算法的準確性，我們一般會多跑幾次Mini K-Means算法，用得到不同的隨機采樣集來得到聚類簇，選擇其中最優的聚類簇。

4.8.K-Means與KNN

初學者很容易把K-Means和KNN搞混，兩者其實差別還是很大的。

K-Means是無監督學習的聚類算法，沒有樣本輸出；而KNN是監督學習的分類算法，有對應的類別輸出。KNN基本不需要訓練，對測試集里面的點，只需要找到在訓練集中最近的k個點，用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到k個類別的最佳質心，從而決定樣本的簇類別。

當然，兩者也有一些相似點，兩個算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。

4.9.KMEANS術語

簇：所有數據的點集合，簇中的對象是相似的。
質心：簇中所有點的中心（計算所有點的中心而來）

4.10.KMEANS算法優缺點

優點：
1、原理比較簡單，實現也是很容易，收斂速度快。
2、當結果簇是密集的，而簇與簇之間區別明顯時, 它的效果較好。
3、主要需要調參的參數僅僅是簇數k。
4、算法的可解釋度比較強。

缺點：
1、K值需要預先給定，很多情況下K值的估計是非常困難的。
2、K-Means算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同，對結果影響很大。
3、對噪音和異常點比較的敏感。用來檢測異常值。
4、采用迭代方法，可能只能得到局部的最優解，而無法得到全局的最優解。
5、對于不是凸的數據集比較難收斂。
6、如果各類隱含類別的數據不均衡，比如隱含類別的數據嚴重失衡，或者各隱含類別的方差不同，則聚類效果不佳。

4.11.K-Means算法API文檔簡介

sklearn.cluster.KMeans(n_clusters=8, *, init='k-means++', n_init=10,max_iter=300, tol=1e-4, precompute_distances='deprecated',verbose=0, random_state=None, copy_x=True,n_jobs='deprecated', algorithm='auto')

參數介紹：

n_clusters : int, default=8The number of clusters to form as well as the number ofcentroids to generate.init : {'k-means++', 'random', ndarray, callable}, default='k-means++'Method for initialization:'k-means++' : selects initial cluster centers for k-meanclustering in a smart way to speed up convergence. See sectionNotes in k_init for more details.'random': choose `n_clusters` observations (rows) at random from datafor the initial centroids.If an ndarray is passed, it should be of shape (n_clusters, n_features)and gives the initial centers.If a callable is passed, it should take arguments X, n_clusters and arandom state and return an initialization.n_init : int, default=10Number of time the k-means algorithm will be run with differentcentroid seeds. The final results will be the best output ofn_init consecutive runs in terms of inertia.max_iter : int, default=300Maximum number of iterations of the k-means algorithm for asingle run.tol : float, default=1e-4Relative tolerance with regards to Frobenius norm of the differencein the cluster centers of two consecutive iterations to declareconvergence.precompute_distances : {'auto', True, False}, default='auto'Precompute distances (faster but takes more memory).'auto' : do not precompute distances if n_samples * n_clusters > 12million. This corresponds to about 100MB overhead per job usingdouble precision.True : always precompute distances.False : never precompute distances... deprecated:: 0.23'precompute_distances' was deprecated in version 0.22 and will beremoved in 0.25. It has no effect.verbose : int, default=0Verbosity mode.random_state : int, RandomState instance, default=NoneDetermines random number generation for centroid initialization. Usean int to make the randomness deterministic.See :term:`Glossary <random_state>`.copy_x : bool, default=TrueWhen pre-computing distances it is more numerically accurate to centerthe data first. If copy_x is True (default), then the original data isnot modified. If False, the original data is modified, and put backbefore the function returns, but small numerical differences may beintroduced by subtracting and then adding the data mean. Note that ifthe original data is not C-contiguous, a copy will be made even ifcopy_x is False. If the original data is sparse, but not in CSR format,a copy will be made even if copy_x is False.n_jobs : int, default=NoneThe number of OpenMP threads to use for the computation. Parallelism issample-wise on the main cython loop which assigns each sample to itsclosest center.``None`` or ``-1`` means using all processors... deprecated:: 0.23``n_jobs`` was deprecated in version 0.23 and will be removed in0.25.algorithm : {"auto", "full", "elkan"}, default="auto"K-means algorithm to use. The classical EM-style algorithm is "full".The "elkan" variation is more efficient on data with well-definedclusters, by using the triangle inequality. However it's more memoryintensive due to the allocation of an extra array of shape(n_samples, n_clusters).For now "auto" (kept for backward compatibiliy) chooses "elkan" but itmight change in the future for a better heuristic... versionchanged:: 0.18Added Elkan algorithm

4.12.K-MEANS算法樣例演示

import numpy as np

from sklearn.cluster import KMeans

隨機構造部分數據

X = np.array([[1,2],[1,4],[1,0],
[10,2],[10,4],[10,0]])

構建模型

kmeans = KMeans(n_clusters=2, random_state=0).fit(X)

查看kmeans的分類結果

print(kmeans.labels_)
‘’’
輸出結果：
[1 1 1 0 0 0]
‘’’

查看數據集的質心點位置

kmeans.predict([[0, 0], [12, 3]])

使用km模型對未知數據集進行預測

print(kmeans.cluster_centers_)
‘’’
輸出結果：
[[10. 2.]
[ 1. 2.]]
‘’’

4.13.KMeans算法的十大應用

4.13.1.文檔分類器

根據標簽、主題和文檔內容將文檔分為多個不同的類別。這是一個非常標準且經典的K-means算法分類問題。首先，需要對文檔進行初始化處理，將每個文檔都用矢量來表示，并使用術語頻率來識別常用術語進行文檔分類，這一步很有必要。然后對文檔向量進行聚類，識別文檔組中的相似性。這里(https://www.codeproject.com/Articles/439890/Text-Documents-Clustering-using-K-Means-Algorithm?spm=a2c4e.11153959.blogcont573745.5.60cf41e2xStlfr)是用于文檔分類的K-means算法實現案例。

4.13.2.物品傳輸優化

使用K-means算法的組合找到無人機最佳發射位置和遺傳算法來解決旅行商的行車路線問題，優化無人機物品傳輸過程。這是（https://upcommons.upc.edu/bitstream/handle/2117/88986/1929-8707-1-PB.pdf?spm=a2c4e.11153959.blogcont573745.6.60cf41e2xStlfr&sequence=1&isAllowed=y）該項目的白皮書。

4.13.3.識別犯罪地點

使用城市中特定地區的相關犯罪數據，分析犯罪類別、犯罪地點以及兩者之間的關聯，可以對城市或區域中容易犯罪的地區做高質量的勘察。這是（http://www.grdjournals.com/uploads/article/GRDJE/V02/I05/0176/GRDJEV02I050176.pdf?spm=a2c4e.11153959.blogcont573745.7.60cf41e2xStlfr&file=GRDJEV02I050176.pdf）基于德里飛行情報區犯罪數據的論文。

4.13.4.客戶分類

聚類能過幫助營銷人員改善他們的客戶群（在其目標區域內工作），并根據客戶的購買歷史、興趣或活動監控來對客戶類別做進一步細分。這（https://www.researchgate.net/publication/268445170_Prepaid_Telecom_Customer_Segmentation_Using_the_K-Mean_Algorithm?spm=a2c4e.11153959.blogcont573745.8.60cf41e2xStlfr）是關于電信運營商如何將預付費客戶分為充值模式、發送短信和瀏覽網站幾個類別的白皮書。對客戶進行分類有助于公司針對特定客戶群制定特定的廣告。

4.13.5.球隊狀態分析

分析球員的狀態一直都是體育界的一個關鍵要素。隨著競爭越來愈激烈，機器學習在這個領域也扮演著至關重要的角色。如果你想創建一個優秀的隊伍并且喜歡根據球員狀態來識別類似的球員，那么K-means算法是一個很好的選擇。具體細節和實現請參照這篇文章（http://thespread.us/clustering.html?spm=a2c4e.11153959.blogcont573745.9.60cf41e2xStlfr）。

4.13.6.保險欺詐檢測

機器學習在欺詐檢測中也扮演著一個至關重要的角色，在汽車、醫療保險和保險欺詐檢測領域中廣泛應用。利用以往欺詐性索賠的歷史數據，根據它和欺詐性模式聚類的相似性來識別新的索賠。由于保險欺詐可能會對公司造成數百萬美元的損失，因此欺詐檢測對公司來說至關重要。這是（http://www.aeuso.org/includes/files/articles/Vol8_Iss27_3764-3771_Fraud_Detection_in_Automobile_Insur.pdf?spm=a2c4e.11153959.blogcont573745.10.60cf41e2xStlfr&file=Vol8_Iss27_3764-3771_Fraud_Detection_in_Automobile_Insur.pdf）汽車保險中使用聚類來檢測欺詐的白皮書。

4.13.7.乘車數據分析

面向大眾公開的Uber乘車信息的數據集，為我們提供了大量關于交通、運輸時間、高峰乘車地點等有價值的數據集。分析這些數據不僅對Uber大有好處，而且有助于我們對城市的交通模式進行深入的了解，來幫助我們做城市未來規劃。這是（https://mapr.com/blog/monitoring-real-time-uber-data-using-spark-machine-learning-streaming-and-kafka-api-part-1/?spm=a2c4e.11153959.blogcont573745.11.60cf41e2xStlfr）一篇使用單個樣本數據集來分析Uber數據過程的文章。

4.13.8.網絡分析犯罪分子

網絡分析是從個人和團體中收集數據來識別二者之間的重要關系的過程。網絡分析源自于犯罪檔案，該檔案提供了調查部門的信息，以對犯罪現場的罪犯進行分類。這是（https://thesai.org/Downloads/Volume7No7/Paper_59-Cyber_Profiling_Using_Log_Analysis_And_K_Means_Clustering.pdf?spm=a2c4e.11153959.blogcont573745.12.60cf41e2xStlfr&file=Paper_59-Cyber_Profiling_Using_Log_Analysis_And_K_Means_Clustering.pdf）一篇在學術環境中，如何根據用戶數據偏好對網絡用戶進行 cyber-profile的論文。

4.13.9.呼叫記錄詳細分析

通話詳細記錄（CDR）是電信公司在對用戶的通話、短信和網絡活動信息的收集。將通話詳細記錄與客戶個人資料結合在一起，這能夠幫助電信公司對客戶需求做更多的預測。在這篇文章（https://www.kdnuggets.com/2017/06/k-means-clustering-r-call-detail-record-analysis.html?spm=a2c4e.11153959.blogcont573745.13.60cf41e2xStlfr）中，你將了解如何使用無監督K-Means聚類算法對客戶一天24小時的活動進行聚類，來了解客戶數小時內的使用情況。

4.13.10.IT警報的自動化聚類

大型企業IT基礎架構技術組件（如網絡，存儲或數據庫）會生成大量的警報消息。由于警報消息可以指向具體的操作，因此必須對警報信息進行手動篩選，確保后續過程的優先級。對數據進行聚類（https://content.pivotal.io/blog/using-data-science-techniques-for-the-automatic-clustering-of-it-alerts?spm=a2c4e.11153959.blogcont573745.14.60cf41e2xStlfr）可以對警報類別和平均修復時間做深入了解，有助于對未來故障進行預測。

4.14.參考文章

https://www.cnblogs.com/txx120/p/11487674.html
https://www.cnblogs.com/pinard/p/6164214.html
https://www.jianshu.com/p/27eaa18ca1db
https://www.jianshu.com/p/4f032dccdcef
https://www.biaodianfu.com/k-means.html
https://www.sohu.com/a/286841039_654419
關于KMeans和MiniBatchKMeans和案例介紹的比較好的一篇文章：
https://www.cnblogs.com/pinard/p/6169370.html

總結

以上是生活随笔為你收集整理的4.K-MEANS聚类算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

算法
Means