【数据挖掘】基于划分的聚类方法 ( K-Means 算法简介 | K-Means 算法步骤 | K-Means 图示 )
文章目錄
- 一、 基于劃分的聚類方法
- 二、 K-Means 算法 簡介
- 三、 K-Means 算法 步驟
- 四、 K-Means 方法的評分函數
- 五、 K-Means 算法 圖示
一、 基于劃分的聚類方法
1 . 基于劃分的聚類方法 : 又叫 基于分區的聚類方法 , 或 基于距離的聚類方法 ;
① 概念 : 給定數據集有 nnn 個樣本 , 在滿足樣本間距離的前提下 , 最少將其分成 kkk 個聚類 ;
② 參數 kkk 說明 : 表示聚類分組的個數 , 該值需要在聚類算法開始執行前 , 需要指定好 ,
2 . 典型的基于劃分的聚類方法 : K-Means 方法 ( K 均值方法 ) , 聚類由分組樣本中的平均均值點表示 ; K-medoids 方法 ( K 中心點方法 ) , 聚類由分組樣本中的某個樣本表示 ;
3 . 硬聚類 : K-Means 是最基礎的聚類算法 , 是基于劃分的聚類方法 , 屬于硬聚類 ; 在這個基礎之上 , GMM 高斯混合模型 , 是基于模型的聚類方法 , 屬于軟聚類 ;
二、 K-Means 算法 簡介
K-Means 簡介 :
① 給定條件 : 給定數據集 XXX , 該數據集有 nnn 個樣本 ;
② 目的 : 將其分成 KKK 個聚類 ;
③ 聚類分組要求 : 每個聚類分組中 , 所有的數據樣本 , 與該分組的中心點的距離之和最小 ; 將每個樣本的與中心點距離計算出來 , 分組中的這些距離累加 , KKK 個分組的距離之和 也累加起來 , 總的距離最小 ;
三、 K-Means 算法 步驟
K-Means 算法 步驟 : 給定數據集 XXX , 該數據集有 nnn 個樣本 , 將其分成 KKK 個聚類 ;
① 中心點初始化 : 為 KKK 個聚類分組選擇初始的中心點 , 這些中心點稱為 Means ; 可以依據經驗 , 也可以隨意選擇 ;
② 計算距離 : 計算 nnn 個對象與 KKK 個中心點 的距離 ; ( 共計算 n×Kn \times Kn×K 次 )
③ 聚類分組 : 每個對象與 KKK 個中心點的值已計算出 , 將每個對象分配給距離其最近的中心點對應的聚類 ;
④ 計算中心點 : 根據聚類分組中的樣本 , 計算每個聚類的中心點 ;
⑤ 迭代直至收斂 : 迭代執行 ② ③ ④ 步驟 , 直到 聚類算法收斂 , 即 中心點 和 分組 經過多少次迭代都不再改變 , 也就是本次計算的中心點與上一次的中心點一樣 ;
四、 K-Means 方法的評分函數
1 . K-Means 方法的評分函數 : 該評分函數本質是 誤差平方和 ;
∑m=1k∑tmi∈Km(Cm?tmi)2\sum_{m=1}^k \sum_{t_{mi}\in K_m} ( C_m - t_{mi} )^2m=1∑k?tmi?∈Km?∑?(Cm??tmi?)2
2 . 公式元素說明 :
CmC_mCm? 表示中心點 ;
tmit_{mi}tmi? 表示每個數據對象 ;
Cm?tmiC_m - t_{mi}Cm??tmi? 表示每個對象到中心的距離 ;
KmK_mKm? 表示第 mmm 個聚類中的點的個數 ;
∑tmi∈Km\sum_{t_{mi}\in K_m}∑tmi?∈Km?? 表示單個聚類中點的個數的累加和
kkk 表示聚類 ( 分組 ) 的個數
∑m=1k\sum_{m=1}^k∑m=1k? 表示 kkk 個聚類的累加和
3 . 公式 拆解 解析 :
Cm?tmiC_m - t_{mi}Cm??tmi? 計算每個元素距離其中心點的距離
(Cm?tmi)2( C_m - t_{mi} )^2(Cm??tmi?)2 計算 每個元素距離其中心點的距離的平方 , 目的是為了消除符號干擾
∑tmi∈Km(Cm?tmi)2\sum_{t_{mi}\in K_m} ( C_m - t_{mi} )^2∑tmi?∈Km??(Cm??tmi?)2 將一個聚類分組中的 [ ( 每個元素距離其中心點的距離 ) 的平方 ] 相加 ;
∑m=1k∑tmi∈Km(Cm?tmi)2\sum_{m=1}^k \sum_{t_{mi}\in K_m} ( C_m - t_{mi} )^2∑m=1k?∑tmi?∈Km??(Cm??tmi?)2 整體公式就是將所有的聚類分組的 { [ ( 每個元素距離其中心點的距離 ) 的平方 ] 累加和 } 再次累加
五、 K-Means 算法 圖示
1 . 已知條件 : 下面的點是二維平面上的樣本 , 有 555 個點 {X1,X2,X3,X4,X5}\{X_1 , X_2 , X_3 , X_4 , X_5 \}{X1?,X2?,X3?,X4?,X5?} , 將其分成 222 個聚類 ;
2 . 首先設置初始中心點 : 中心點可以選擇已有的樣本作為中心點 ( 稱為 : 實點 ) , 也可以在空白處設置中心點 ( 稱為 : 虛點 ) ;
這里在空白處任意設置 222 個中心點 {K1,K2}\{K_1 , K_2\}{K1?,K2?} ;
3 . 計算距離 : 計算 555 個點到 222 個中心點的距離 , 每個點都要計算 222 次 , 共計算 101010 次 ;
距離表示說明 : 下面公式中的 d(K1,X1)d(K_1, X_1)d(K1?,X1?) 指的是 K1K_1K1? 點到 X1X_1X1? 點的距離 ;
d(K1,X1)=1816.6d(K_1, X_1) = 1816.6d(K1?,X1?)=1816.6
d(K2,X1)=14056.5d(K_2, X_1) = 14056.5d(K2?,X1?)=14056.5
X1X_1X1? 點分到 K1K_1K1? 對應的聚類分組中 ;
d(K1,X2)=3646.6d(K_1, X_2) = 3646.6d(K1?,X2?)=3646.6
d(K2,X2)=1405.3d(K_2, X_2) = 1405.3d(K2?,X2?)=1405.3
X2X_2X2? 點分到 K2K_2K2? 對應的聚類分組中 ;
d(K1,X3)=1818.2d(K_1, X_3) = 1818.2d(K1?,X3?)=1818.2
d(K2,X3)=5101.3d(K_2, X_3) = 5101.3d(K2?,X3?)=5101.3
X3X_3X3? 點分到 K1K_1K1? 對應的聚類分組中 ;
d(K1,X4)=12940.3d(K_1, X_4) = 12940.3d(K1?,X4?)=12940.3
d(K2,X4)=7859.2d(K_2, X_4) = 7859.2d(K2?,X4?)=7859.2
X4X_4X4? 點分到 K2K_2K2? 對應的聚類分組中 ;
d(K1,X5)=11775.1d(K_1, X_5) = 11775.1d(K1?,X5?)=11775.1
d(K2,X5)=6539.1d(K_2, X_5) = 6539.1d(K2?,X5?)=6539.1
X5X_5X5? 點分到 K2K_2K2? 對應的聚類分組中 ;
4 . 初步分組 : 為每個樣本分組 , 將 樣本點 XiX_iXi? 分到最近的中心點對應的聚類分組中 , 下面是分組結果 :
X1,X3X_1 , X_3X1?,X3? 分組到 K1K_1K1? 中心點對應的分組 , X2,X5,X4X_2 , X_5 , X_4X2?,X5?,X4? 分到 K2K_2K2? 對應的分組 ;
當前聚類分組 : {X1,X3}\{ X_1 , X_3 \}{X1?,X3?} , {X2,X5,X4}\{ X_2 , X_5 , X_4 \}{X2?,X5?,X4?} ;
5 . 重新計算中心點位置 : 根據上述聚類分組 , 確定新的中心點位置 , 如下圖 :
6 . 重新計算中心點位置 : 圖中的 X2X_2X2? 的聚類分組 , 出現了改變 , X2X_2X2? 樣本的距離 , 明顯距離 K1K_1K1? 點比較近 ;
距離表示說明 : 下面公式中的 d(K1,X1)d(K_1, X_1)d(K1?,X1?) 指的是 K1K_1K1? 點到 X1X_1X1? 點的距離 ;
d(K1,X2)=2696.3d(K_1, X_2) = 2696.3d(K1?,X2?)=2696.3
d(K2,X2)=4204.1d(K_2, X_2) = 4204.1d(K2?,X2?)=4204.1
X2X_2X2? 點分到 K1K_1K1? 對應的聚類分組中 ;
7 . 重新分組 : X2X_2X2? 點分到 K1K_1K1? 對應的聚類分組中 ;
當前聚類分組 : {X1,X2,X3}\{ X_1 , X_2 , X_3 \}{X1?,X2?,X3?} , {X5,X4}\{ X_5 , X_4 \}{X5?,X4?} ;
8 . 繼續計算中心點位置 : 此時該中心點就比較穩定了 , 下一次計算 , 仍然是這個中心點 , 因此 聚類收斂 , 此時的分組就是最終的聚類分組 ;
最終聚類分組 : {X1,X2,X3}\{ X_1 , X_2 , X_3 \}{X1?,X2?,X3?} , {X5,X4}\{ X_5 , X_4 \}{X5?,X4?} ;
最終中心點如下圖所示 , K1K_1K1? 在三角形中心 , K2K_2K2? 在兩點中心點 ;
總結
以上是生活随笔為你收集整理的【数据挖掘】基于划分的聚类方法 ( K-Means 算法简介 | K-Means 算法步骤 | K-Means 图示 )的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 【数据挖掘】聚类算法 简介 ( 基于划分
- 下一篇: 【数据挖掘】K-Means 二维数据聚类