AI60問- Q27K均值集群(K-means)算法是什麼?

by 提拔我園丁
緯育TibaMe AI小教室-Q27k均值集群(k-means)算法是什麼?

K-means 是一種聚類 (Cluster)的方式,基本上就是依照「物以類聚」的方式在進行。也可能想成,相似的東西有相似的特徵,給予一組資料,將它分為 k 類(k由使用者設定),這就是K-means的用處。

聚類的方法大多是非監督式學習,群內的對象越相似,集群的效果就越好。

*聚類 Cluster:一種將資料分類成群的方法,
為一種非監督式學習,也就是訓練資料沒有預先定義的標籤。

而什麼是非監督學習?

其實監督式學習、非監督式學習之間的差別,主要在於目標預測變數。

  • 監督學習 supervised learning:有目標變數去訓練模型,即對具有概念標記(分類)的訓練樣本進行學習,盡可能對訓練樣本集外的數據進行標記(分類)預測,所以模型評估講求準度。如:神經網絡、決策樹
  • 非監督學習 unsupervised learning:找出輸入變數間的內部關係與資料形貌,找出資料間大致分布的趨勢,沒有要預測對象。對沒有概念標記(分類)的訓練樣本進行學習,以發現訓練樣本集中的結構性知識,它只有資料本身。如:集群

K-means 不只可以拿來分類消費者,優化行銷活動、避免客戶流失;還能判斷金融交易是否異常,偵測是否詐欺;甚至幫忙歸類IT技術內的不同警訊。

K-均值(K-means)集群算法

圖27-1 K-means 依 k=3 將資料分成 3 類

集群分析(cluster analysis)試圖將相似對象歸入同一群,將不相似對象歸到不同群。

K-均值(K-means)會根據事先選擇K個初始中心點(centroid)進行集群,即得到K個群,且不同群的中心採用群中所含有的均值計算而成。

而K-均值是發現給定數據集的k個群的算法。群個數k是用戶給定的,每個群通過其質心(centroid),即群中的所有點的中心來描述。


K means 流程

K-means使用兩步驟的疊代方式求解,完整的流程如下:

Step1:隨機選取資料組中的k筆資料,當作初始群中心u1~uk

圖27-2 步驟1 隨機選取群中心

Step2:計算每個資料xi 對應到最短距離的群中心 (固定 ui 求解所屬群 Si)

圖27-3 步驟2 計算每個資料到各類別中心距離,以最短距離找出所屬群

Step3:利用目前得到的分類重新計算群中心 (固定 Si 求解群中心 ui)

圖27-4 利用分群結果重新計算群中心

Step4:重複step2跟3,直到收斂(達到最大疊代次數 或是 群中心移動距離很小)

初始值設定

大概了解「K-means」的流程後,可以發現一開始的群中心是不固定的,也就是說同一筆資料用K-means跑5次,5次的結果可能都不同。

看一個比較極端的例子:

圖27-5 不同初始群中心選擇,造成分群結果差異

由上圖可以發現,若初始群中心設定不好,有可能導致不會的結果,但就正常情況而言,「K-means」算是速度快、效果不差的演算法。

【特別注意:K個群點】

那要如何確定 K?

K個初始質心,K是預先給定的集群數,指的是「所期望的群的個數」。而K個群點的選取幾種方法:

  1. 選擇彼此距離儘可能遠的K個點
  2. 隨機選擇一個點,作為第一個初始類群中心點
  3. 選擇距離該點最遠的點,作為第二個初始類群中心點
  4. 選擇距離前兩個點的最近距離最大的點,作為第三個初始類群的中心點

以此類推,直至選出K個初始類群中心點。


初始質心的選取

隨機選取初始質心,但這樣群的質量常常很差,只是取一個樣本,並使用層次集群技術對它集群。從層次集群中提取K個群,並用這些群的質心作為初始質心。

隨機選擇第一個點,或取所有點的質心作為第一個點。然後,對於每個後來的初始質心,選擇離已經選取過的初始質心最遠的點。使用這種方法,確保選擇的初始質心不僅是隨機的,且是散開的。但是,這種方法可能選中離群點。

此外,求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題,通常該方法用於點樣本。由於離群點很少,它們多半不會在隨機樣本中出現。計算量也大幅減少。對數據用層次集群算法,得到K個群之後,從每個類群中選擇一個點,該點可以是該類群的中心點,或者是距離類群中心點最近的那個點。


距離的度量

  • 歐幾里得距離 Euclidean distance:一種簡單直觀且有效的距離度量方式(直線距離公式)
  • 餘弦相似度 Cosine similarity:藉測量兩個向量夾角的餘弦值,來度量它們之間的相似性

兩者都是評定個體間差異的大小,由於歐幾里得距離度量會受到指標不同單位刻度的影響,所以會一般需要先進行標準化,同時距離越大,個體間差異越大。而空間向量餘弦夾角的相似度度量,卻不會受指標刻度的影響,餘弦值落在區間[-1,1],值越大,差異越小。

歐幾里得距離表現數值上的絕對差異,而餘弦距離則是方向上的相對差異。


質心的計算

群的質心都是它的均值,就是用向量各維來取得「平均」即可。

圖27-6

算法停止條件

達到最大的疊代次數 或是 目標函數達到最優(群中心移動距離很小),就可停止。但對於不同的距離度量,目標函數往往不同。

當採用歐幾里得距離時,目標函數一般為最小化對象到其群質心的距離的平方和,如下:

當採用餘弦相似度時,目標函數一般為最大化對象到其群質心的餘弦相似度和,如下:

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 

AI資料科學家-三階段全方位學程班
AI資料科學家-三階段全方位學程班

每日5分鐘, 提拔我園丁陪你快速添補AI/資料科學知識與技能。

若您想了解更多AI/資料科學的小知識、及各產業的相關應用,歡迎訂閱TibaMe FB及部落格,或你有其他想了解的主題歡迎在下方留言讓我們知道唷!

緯育TibaMe FB

企業人才數位轉型FB

企業AI、數位人才or平台培訓方案請點選

參考資料

分享這篇文章:
0 comment
4

您也許會喜歡

Leave a Comment

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料