一、 基于划分的聚类方法

1 . 基于划分的聚类方法 : 又叫 基于分区的聚类方法 , 或 基于距离的聚类方法 ;

① 概念 : 给定数据集有 $n$ 个样本 , 在满足样本间距离的前提下 , 最少将其分成 $k$ 个聚类 ;

② 参数 $k$ 说明 : 表示聚类分组的个数 , 该值需要在聚类算法开始执行前 , 需要指定好 ,

2 . 典型的基于划分的聚类方法 : K-Means 方法 ( K 均值方法 ) , 聚类由分组样本中的平均均值点表示 ; K-medoids 方法 ( K 中心点方法 ) , 聚类由分组样本中的某个样本表示 ;

3 . 硬聚类 : K-Means 是最基础的聚类算法 , 是基于划分的聚类方法 , 属于硬聚类 ; 在这个基础之上 , GMM 高斯混合模型 , 是基于模型的聚类方法 , 属于软聚类 ;

二、 K-Means 算法 简介

K-Means 简介 :

① 给定条件 : 给定数据集 $X$ , 该数据集有 $n$ 个样本 ;

② 目的 : 将其分成 $K$ 个聚类 ;

③ 聚类分组要求 : 每个聚类分组中 , 所有的数据样本 , 与该分组的中心点的距离之和最小 ; 将每个样本的与中心点距离计算出来 , 分组中的这些距离累加 , $K$ 个分组的距离之和 也累加起来 , 总的距离最小 ;

三、 K-Means 算法 步骤

K-Means 算法 步骤 : 给定数据集 $X$ , 该数据集有 $n$ 个样本 , 将其分成 $K$ 个聚类 ;

① 中心点初始化 : 为 $K$ 个聚类分组选择初始的中心点 , 这些中心点称为 Means ; 可以依据经验 , 也可以随意选择 ;

② 计算距离 : 计算 $n$ 个对象与 $K$ 个中心点 的距离 ; ( 共计算 $n\times K$ 次 )

③ 聚类分组 : 每个对象与 $K$ 个中心点的值已计算出 , 将每个对象分配给距离其最近的中心点对应的聚类 ;

④ 计算中心点 : 根据聚类分组中的样本 , 计算每个聚类的中心点 ;

⑤ 迭代直至收敛 : 迭代执行 ② ③ ④ 步骤 , 直到 聚类算法收敛 , 即 中心点 和 分组 经过多少次迭代都不再改变 , 也就是本次计算的中心点与上一次的中心点一样 ;

四、 K-Means 方法的评分函数

1 . K-Means 方法的评分函数 : 该评分函数本质是 误差平方和 ;

$$\sum _{m=1}^k\sum _{t_{mi}\in K_m}(C_m-t_{mi}{)}^2$$

2 . 公式元素说明 :

$C_m$ 表示中心点 ;

$t_{mi}$ 表示每个数据对象 ;

$C_m-t_{mi}$ 表示每个对象到中心的距离 ;

$K_m$ 表示第 $m$ 个聚类中的点的个数 ;

${\sum }_{t_{mi}\in K_m}$ 表示单个聚类中点的个数的累加和

$k$ 表示聚类 ( 分组 ) 的个数

${\sum }_{m=1}^k$ 表示 $k$ 个聚类的累加和

3 . 公式 拆解 解析 :

$C_m-t_{mi}$ 计算每个元素距离其中心点的距离

$(C_m-t_{mi}{)}^2$ 计算 每个元素距离其中心点的距离的平方 , 目的是为了消除符号干扰

${\sum }_{t_{mi}\in K_m}(C_m-t_{mi}{)}^2$ 将一个聚类分组中的 [ ( 每个元素距离其中心点的距离 ) 的平方 ] 相加 ;

${\sum }_{m=1}^k{\sum }_{t_{mi}\in K_m}(C_m-t_{mi}{)}^2$ 整体公式就是将所有的聚类分组的 { [ ( 每个元素距离其中心点的距离 ) 的平方 ] 累加和 } 再次累加

五、 K-Means 算法 图示

1 . 已知条件 : 下面的点是二维平面上的样本 , 有 $5$ 个点 $\{X_1,X_2,X_3,X_4,X_5\}$ , 将其分成 $2$ 个聚类 ;

2 . 首先设置初始中心点 : 中心点可以选择已有的样本作为中心点 ( 称为 : 实点 ) , 也可以在空白处设置中心点 ( 称为 : 虚点 ) ;

这里在空白处任意设置 $2$ 个中心点 $\{K_1,K_2\}$ ;

3 . 计算距离 : 计算 $5$ 个点到 $2$ 个中心点的距离 , 每个点都要计算 $2$ 次 , 共计算 $10$ 次 ;

距离表示说明 : 下面公式中的 $d(K_1,X_1)$ 指的是 $K_1$ 点到 $X_1$ 点的距离 ;

$d(K_1,X_1)=1816.6$
$d(K_2,X_1)=14056.5$

$X_1$ 点分到 $K_1$ 对应的聚类分组中 ;

$d(K_1,X_2)=3646.6$
$d(K_2,X_2)=1405.3$

$X_2$ 点分到 $K_2$ 对应的聚类分组中 ;

$d(K_1,X_3)=1818.2$
$d(K_2,X_3)=5101.3$

$X_3$ 点分到 $K_1$ 对应的聚类分组中 ;

$d(K_1,X_4)=12940.3$
$d(K_2,X_4)=7859.2$

$X_4$ 点分到 $K_2$ 对应的聚类分组中 ;

$d(K_1,X_5)=11775.1$
$d(K_2,X_5)=6539.1$

$X_5$ 点分到 $K_2$ 对应的聚类分组中 ;

4 . 初步分组 : 为每个样本分组 , 将 样本点 $X_i$ 分到最近的中心点对应的聚类分组中 , 下面是分组结果 :

$X_1,X_3$ 分组到 $K_1$ 中心点对应的分组 , $X_2,X_5,X_4$ 分到 $K_2$ 对应的分组 ;

当前聚类分组 : $\{X_1,X_3\}$ , $\{X_2,X_5,X_4\}$ ;

5 . 重新计算中心点位置 : 根据上述聚类分组 , 确定新的中心点位置 , 如下图 :

6 . 重新计算中心点位置 : 图中的 $X_2$ 的聚类分组 , 出现了改变 , $X_2$ 样本的距离 , 明显距离 $K_1$ 点比较近 ;

距离表示说明 : 下面公式中的 $d(K_1,X_1)$ 指的是 $K_1$ 点到 $X_1$ 点的距离 ;

$d(K_1,X_2)=2696.3$
$d(K_2,X_2)=4204.1$

$X_2$ 点分到 $K_1$ 对应的聚类分组中 ;

7 . 重新分组 : $X_2$ 点分到 $K_1$ 对应的聚类分组中 ;

当前聚类分组 : $\{X_1,X_2,X_3\}$ , $\{X_5,X_4\}$ ;

8 . 继续计算中心点位置 : 此时该中心点就比较稳定了 , 下一次计算 , 仍然是这个中心点 , 因此 聚类收敛 , 此时的分组就是最终的聚类分组 ;

最终聚类分组 : $\{X_1,X_2,X_3\}$ , $\{X_5,X_4\}$ ;

最终中心点如下图所示 , $K_1$ 在三角形中心 , $K_2$ 在两点中心点 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/105899688