K-means 是一種聚類 (Cluster)的方式，基本上就是依照「物以類聚」的方式在進行。也可能想成，相似的東西有相似的特徵，給予一組資料，將它分為 k 類（k由使用者設定），這就是K-means的用處。
聚類的方法大多是非監督式學習，群內的對象越相似，集群的效果就越好。
*聚類 Cluster：一種將資料分類成群的方法，
為一種非監督式學習，也就是訓練資料沒有預先定義的標籤。
而什麼是非監督學習？
其實監督式學習、非監督式學習之間的差別，主要在於目標預測變數。
- 監督學習 supervised learning：有目標變數去訓練模型，即對具有概念標記（分類）的訓練樣本進行學習，盡可能對訓練樣本集外的數據進行標記（分類）預測，所以模型評估講求準度。如：神經網絡、決策樹
- 非監督學習 unsupervised learning：找出輸入變數間的內部關係與資料形貌，找出資料間大致分布的趨勢，沒有要預測對象。對沒有概念標記（分類）的訓練樣本進行學習，以發現訓練樣本集中的結構性知識，它只有資料本身。如：集群
K-means 不只可以拿來分類消費者，優化行銷活動、避免客戶流失；還能判斷金融交易是否異常，偵測是否詐欺；甚至幫忙歸類IT技術內的不同警訊。
K-均值（K-means）集群算法
集群分析（cluster analysis）試圖將相似對象歸入同一群，將不相似對象歸到不同群。
K-均值（K-means）會根據事先選擇K個初始中心點（centroid）進行集群，即得到K個群，且不同群的中心採用群中所含有的均值計算而成。
而K-均值是發現給定數據集的k個群的算法。群個數k是用戶給定的，每個群通過其質心（centroid），即群中的所有點的中心來描述。
K means 流程
K-means使用兩步驟的疊代方式求解，完整的流程如下：
Step1：隨機選取資料組中的k筆資料，當作初始群中心u1~uk
Step2：計算每個資料xi 對應到最短距離的群中心 (固定 ui 求解所屬群 Si)
Step3：利用目前得到的分類重新計算群中心 (固定 Si 求解群中心 ui)
Step4：重複step2跟3，直到收斂（達到最大疊代次數 或是 群中心移動距離很小）
初始值設定
大概了解「K-means」的流程後，可以發現一開始的群中心是不固定的，也就是說同一筆資料用K-means跑5次，5次的結果可能都不同。
看一個比較極端的例子：
由上圖可以發現，若初始群中心設定不好，有可能導致不會的結果，但就正常情況而言，「K-means」算是速度快、效果不差的演算法。
【特別注意：K個群點】
那要如何確定 K？
K個初始質心，K是預先給定的集群數，指的是「所期望的群的個數」。而K個群點的選取幾種方法：
- 選擇彼此距離儘可能遠的K個點
- 隨機選擇一個點，作為第一個初始類群中心點
- 選擇距離該點最遠的點，作為第二個初始類群中心點
- 選擇距離前兩個點的最近距離最大的點，作為第三個初始類群的中心點
以此類推，直至選出K個初始類群中心點。
初始質心的選取
隨機選取初始質心，但這樣群的質量常常很差，只是取一個樣本，並使用層次集群技術對它集群。從層次集群中提取K個群，並用這些群的質心作為初始質心。
隨機選擇第一個點，或取所有點的質心作為第一個點。然後，對於每個後來的初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保選擇的初始質心不僅是隨機的，且是散開的。但是，這種方法可能選中離群點。
此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用於點樣本。由於離群點很少，它們多半不會在隨機樣本中出現。計算量也大幅減少。對數據用層次集群算法，得到K個群之後，從每個類群中選擇一個點，該點可以是該類群的中心點，或者是距離類群中心點最近的那個點。
距離的度量
- 歐幾里得距離 Euclidean distance：一種簡單直觀且有效的距離度量方式（直線距離公式）
- 餘弦相似度 Cosine similarity：藉測量兩個向量夾角的餘弦值，來度量它們之間的相似性
兩者都是評定個體間差異的大小，由於歐幾里得距離度量會受到指標不同單位刻度的影響，所以會一般需要先進行標準化，同時距離越大，個體間差異越大。而空間向量餘弦夾角的相似度度量，卻不會受指標刻度的影響，餘弦值落在區間[-1,1]，值越大，差異越小。
歐幾里得距離表現數值上的絕對差異，而餘弦距離則是方向上的相對差異。
質心的計算
群的質心都是它的均值，就是用向量各維來取得「平均」即可。
算法停止條件
達到最大的疊代次數 或是 目標函數達到最優（群中心移動距離很小），就可停止。但對於不同的距離度量，目標函數往往不同。
當採用歐幾里得距離時，目標函數一般為最小化對象到其群質心的距離的平方和，如下：
當採用餘弦相似度時，目標函數一般為最大化對象到其群質心的餘弦相似度和，如下：
K-means的優缺點
優點：
- 擅長處理球狀分佈的數據
- 簡單、易掌握
缺點：
- k的取值需要根據經驗，沒有可藉鑑性
- 對異常偏離的數據非常敏感
其他幾種集群算法
1.K-中心點集群（K-Medoids）
2.密度集群（Densit-based Spatial Clustering of Application with Noise, DBSCAN）
3.期望最大化集群（Expectation Maximization, EM）
K-means 與KNN？
K均值集群（K-means）與 Q26 K近鄰（KNN）之間沒有任何關係，KNN是另一種流行的機器學習技術。
- K-Means是無監督學習的聚類算法，沒有樣本輸出
- KNN是監督學習的分類算法，有對應的類別輸出
KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的k個點，用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到k個類別的最佳質心，從而決定樣本的群類別。
當然，兩者也有些相似點，兩個算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的這個思想。
推薦課程
【AI基礎思維2】掌握AI關鍵核心技術_機器學習及深度學習
緯育TibaMe已經有10萬人次來學習AI/資料科學知識或技術，若你想進一步了解或學習 AI / 資料科學的相關知識或技能，歡迎來TibaMe 👉 https://www.tibame.com/eventpage/ai_datascientist
每日5分鐘， 提拔我園丁陪你快速添補AI/資料科學知識與技能。
若您想了解更多AI/資料科學的小知識、及各產業的相關應用，歡迎訂閱TibaMe FB及部落格，或你有其他想了解的主題歡迎在下方留言讓我們知道唷！
參考資料