K 均值聚類
通過迭代方式尋找 K 個簇的一種劃分方案,使得聚類結果對應的代價函式最小。
1、缺點
- 需要人工預先確定初始 K 值,且該值和真實的資料未必吻合。
- K 均值只能收斂到區域性最優,效果受到初始值很大
- 易受到噪聲點的影響
- 樣本點只能被劃分到單一的類中。
2、演算法調優
- 資料歸一化和離群點處理
- 合理選擇 K 值
K 值選擇方法:
- 手肘法: 是一個經驗方法,缺點就是不能夠自動化。
- Gap Statistic 方法: 只需要找到最大的 Gap Statistic 所對應的 K 即可。Gap(K)可以視為隨機樣本的損失和實際樣本的損失之差。
- 採用核函式: 通過一個非線性對映,將輸入空間中的資料點對映到高位的特徵空間中,並在新的特徵空間進行聚類。非線性對映增加了資料點線性可分的概率,從而在經典聚類演算法失效的情況下,通過引入核函式可以達到更為準確的聚類結果。
3、演算法改進
- K-means++
- ISODATA
K-means++
已經選取了 n(0<n<k) 個初始聚類中心,距離當前 n 個聚類中心越遠的點會有更高的概率被選為第 n+1 個聚類中心。在選取第一個聚類中心(n=1)時同樣通過隨機的方法。
ISODATA
當 K 值的大小不確定時,可以使用 ISODATA 演算法。
ISODATA 的全稱是迭代自組織資料分析法。當屬於某個類別的樣本數過少,把該類別去除;當屬於某個類別的樣本數過多、分散度較大時,把該類分為兩個子類別。 在 K-means 基礎上增加兩個操作,一是分裂操作,對應著增加聚類中心數;二是合併操作,對應著減少聚類中心數。
超引數設定:
- 預期的聚類中心數目 K 。 具體地,最終輸出的聚類中心數目常見範圍是 K 的一半或兩倍 K。
- 每個類別要求的最少樣本數目 N。 如果分裂後會導致某個子類別所包含樣本數目小於該閾值,就不會對該類別進行分裂操作
- 最大方差 Sigma。 用於控制某個類別中樣本的分散程度。當樣本分散程度超過這個閾值,且分裂後滿足上條規則,進行分裂操作。
- 兩個聚類中心之間所允許最小距離 D。 如果兩個類靠的非常近,小於該閾值時,則對這兩個類進行合併操作。