「AI科技」機器學習算法之K-means算法原理及缺點改進思路

https://www.toutiao.com/a6641916717624721933/

2019-01-03 08:00:00

K-means算法是使用得最為廣泛的一個算法，本文将介紹K-means 聚類算法、原理、特點及改進思路。

K-means聚類算法簡介

K-means 聚類算法，是基于距離的一種無監督式的學習算法。在1967年首次由MacQueen提出，常用于模式識别和資料挖掘中，其目的是對一組資料進行幾何等價劃分進行分類。

K-means算法是使用得最為廣泛的一個算法，其應用場景遍及醫學、經濟學、行為學、決策科學等領域。算法以樣本均值（質心）代表該類，定義簡單具有清晰明了的幾何和統計意義。

K-means聚類算法原理

算法的基本思路：

1. 從 一組資料對象随機選擇 m 個對象作為初始聚類中心；
2. 根據每個聚類資料對象的均值（質心），計算每個資料對象與這些質心的距離；并根據最小距離重新對相應資料對象進行劃分；
3. 重新計算每個（有變化）聚類的均值（質心）；
4. 計算标準測度函數，當滿足函數收斂時，則算法終止；如果條件不滿足則回到步驟2

算法的工作流程

距離算法及準則函數

一般情況下我們都是以歐拉距離公式來計算兩個資料對象間的距離，但還有其他的一些方法可以用于計算，算法如下：

①明氏距離（Minkowski Distance）

這裡的xi=( i1，xi2，…，xip)和xj=( j1，xj2，…，xjp)是兩個p維的資料對象并且 i≠j。
           

②歐式距離（Euclidean Distance）

當明氏距離中q=2時，公式1即歐式距離。
           

③蘭式距離（Canberra Distance）：

（2）準則函數E

對于K-means算法，通常使用準則函數E，也就是誤差平方和（Sum of Squared Error，SSE）作為度量聚類品質的目标函數。

其中，d( )表示兩個對象之間的距離，可以利用明氏、歐式或蘭氏距離求得。

對于相同的k值，更小的SSE說明簇中對象越集中。對于不同的k值，越大的k值應該越小的SSE。

K-means聚類算法特點

K-means算法優點：

• 原理簡單、運算快速
• 處理大資料集，該算法保持可伸縮性及高效性
• 當資料接近高斯分布時，聚類效果最好。

K-means算法缺點：

• 需要事先給定聚類的數量K 值；
• 對初始聚類中心敏感，不同的初始值會對結果産生不同效果
• 若資料中含有異常點和孤立點，将導緻分類偏離嚴重
• 不适用于非高斯分布的資料。

針對以上确定，最後兩點屬于資料問題，無法解決，但是前兩點還是可以進行改進的。針對第一個缺點，可以通過肘部算法來确定K的數量，具體步驟如下：

• ① 取K的範圍1至10
• ② 分别統計每個K類的 畸變程度（每個質點到其組内的每個元素的距離之和）
• ③ 畫圖呈現，看看在第幾點出現畸變緩（肘部），該點就是最優的K值

針對第二個缺點，可以對初始聚類中心的選擇進行優化。優化思想為：選擇批次距離盡可能遠的K個點。具體選擇步驟如下：

• ① 随機選擇一個點作為第一個初始類簇中心點，
• ② 選擇距離該點最遠的那個點作為第二個初始類簇中心點，
• ③ 然後再選擇距離前兩個點的最近距離最大的點作為第三個初始類簇的中心點，
• ④ 以此類推，直至選出K個初始類簇中心點。

後續将通過python代碼對K-means聚類算法進行實作。