【海量数据挖掘/数据分析】之 K-Means 算法（K-Means算法、K-Means 中心值计算、K-Means 距离计算公式、K-Means 算法迭代步骤、K-Means算法实例）

一、基于划分的聚类方法

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

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

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

2 . 典型的基于划分的聚类方法 :

K-Means 方法 ( K 均值方法 ) , 聚类由分组样本中的平均均值点表示 ;
K-medoids 方法 ( K 中心点方法 ) , 聚类由分组样本中的某个样本表示 ;

3 . 硬聚类 :

K-Means 是最基础的聚类算法 , 是基于划分的聚类方法 , 属于硬聚类 ;

在这个基础之上 , GMM 高斯混合模型 , 是基于模型的聚类方法 , 属于软聚类 ;

二、 K-Means 算法

1、K-Means 简介 :

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

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

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

2、 K-Means 算法步骤

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

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

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

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

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

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

3、K-Means 算法图示说明

1 . 已知条件 :

下面的点是二维平面上的样本 , 有 5 个点 { X 1 , X 2 , X 3 , X 4 , X 5 } , 将其分成 2 个聚类，如下图

2 、首先设置初始中心点 :

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

这里在空白处任意设置 2 个中心点 {K1,K2} ;

3、计算距离 :

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

4、距离表示说明 :

下面公式中的 d(K1,X1) 指的是 K1 点到 X1 点的距离：

1） d(K1,X1)=1816.6，d(K2,X1)=14056.5，X1 点分到 K1 对应的聚类分组中 ;

2）d(K1,X2)=3646.6，d(K2,X2)=1405.3，X2 点分到 K2 对应的聚类分组中 ;

3）d(K1,X3)=1818.2，d(K2,X3)=5101.3，X3 点分到 K 1 K_1 K1 对应的聚类分组中 ;

4）d(K1,X4)=12940.3，d(K2,X4)=7859.2，X4 点分到 K 2 K_2 K2 对应的聚类分组中 ;

5）d(K1,X5)=11775.1，d(K2,X5)=6539.1，X5 点分到 K 2 K_2 K2 对应的聚类分组中 ;

5 、初步分组 :

为每个样本分组 , 将样本点 Xi 分到最近的中心点对应的聚类分组中 , 下面是分组结果 :

X1,X3 分组到 K1 中心点对应的分组 , X5,X4 分到 K2 对应的分组 ;

当前聚类分组 : {X1,X3} , {X2,X5,X4} ;

6、重新计算中心点位置 :

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

7、重新计算中心点位置 :

图中的 X2 的聚类分组 , 出现了改变 , X2 样本的距离 , 明显距离 K1 点比较近 ;

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

d(K1,X2)=2696.3
d(K2,X2)=4204.1

X2 点分到 K1 对应的聚类分组中 ;

8、重新分组 :

X 2 X_2 X2 点分到 K 1 K_1 K1 对应的聚类分组中 ;

当前聚类分组 : {X1,X2,X3} , {X5,X4} ;

9、继续计算中心点位置 :

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

最终聚类分组 : {X1,X2,X3} , {X5,X4} ;

最终中心点如下图所示 , K1 在三角形中心 , K2 在两点中心点 ;

三、K-Means 一维数据的数据样本及初始值

1 ）数据集样本 : 14 个人 , 根据其年龄 , 将数据集分成 3 组 ;

2 ）选定初始的中心值 : 1 , 20 , 40 ;

四、K-Means 一维数据距离计算

1、计算方式

距离公式选择 :

一维数据 直接使用 曼哈顿距离 计算即可 ,
二维数据 需要使用 欧几里得距离 计算 ;

2、曼哈顿距离 :

这里直接使用曼哈顿距离 , 即样本值 , 直接相减得到的值取绝对值 , 就是曼哈顿距离 ;

3、算法实现步骤

K-Means 算法步骤 :

给定数据集 X , 该数据集有 n 个样本 , 将其分成 K 个聚类 ;

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

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

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

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

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

五、K-Means 一维数据曼哈顿距离计算实例

计算 14 个样本与 3 个中心点的距离。

1、第一次迭代 :

1）步骤 ( 1 ) 计算距离

① 表格含义 :

如下 P1 与 C1 对应的表格位置值是 P1 样本与 C1 中心点的曼哈顿距离 , 即 两个值相减取绝对值 ;

② 计算方式 :

计算 Pi 与 Cj 之间的距离 , 直接将两个数值相减取平均值即可 ;i 取值范围 , {1,2,⋯,14} , j j j 的取值范围 {1,2,3} ;

③ 计算示例 : 如 P3 样本与 C2 中心点的距离计算 , P3 样本的年龄属性值是 5 , C2 中心点值为 20 ; d(P3,C2) 表示两个点之间的距离 ;

d(P3,C2)=∣5−20∣=15

下表中的 P3 行 C2 列对应的值是 15 , 即上面计算出来的距离值：

2）步骤 ( 2 ) 聚类分组

（1） 为 {P1,P2,⋯,P14} 这 14 14 14 个样本分组 :

P1 与{C1,C2,C3} 三个中心点中的 C1 距离最近 , 距离是 0 , P1 样本分组到 K1 组 ;
P2 与 {C1,C2,C3} 三个中心点中的 C1 距离最近 , 距离是 2 , P2 样本分组到 K1 组 ;
P3 与 {C1,C2,C3} 三个中心点中的 C1 距离最近 , 距离是 4 , P3 样本分组到 K1 组 ;
P4 与 {C1,C2,C3} 三个中心点中的 C1 距离最近 , 距离是 7 , P4 样本分组到 K1 组 ;
P5 与 {C1,C2,C3} 三个中心点中的 C1 距离最近 , 距离是 8 , P5 样本分组到 K1 组 ;

P6 与 {C1,C2,C3} 三个中心点中的 C2 距离最近 , 距离是 9 , P6 样本分组到 K2 组 ;
P7 与 {C1,C2,C3} 三个中心点中的 C2 距离最近 , 距离是 8 , P7 样本分组到 K2 组 ;
P8 与 {C1,C2,C3} 三个中心点中的 C2 距离最近 , 距离是 7 , P8 样本分组到 K2 组 ;

P9 与 {C1,C2,C3} 三个中心点中的 C3 距离最近 , 距离是 3 , P9 样本分组到 K3 组 ;
P10 与 {C1,C2,C3} 三个中心点中的 C3 距离最近 , 距离是 3 , P10 样本分组到 K3 组 ;
P11 与 {C1,C2,C3} 三个中心点中的 C3 距离最近 , 距离是 5 , P11 样本分组到 K3 组 ;
P12 与 {C1,C2,C3} 三个中心点中的 C3 距离最近 , 距离是 9 , P12 样本分组到 K3 组 ;
P13 与{C1,C2,C3} 三个中心点中的 C3 距离最近 , 距离是 11 , P13 样本分组到 K3 组 ;
P14 与{C1,C2,C3} 三个中心点中的 C3 距离最近 , 距离是 25 , P14 样本分组到 K3 组 ;

（2） 当前分组依据的中心点 : {1,20,40}

（3）当前分组结果 :

K1={P1,P2,P3,P4,P5}
K2={P6,P7,P8}
K3={P9,P10,P11,P12,P13,P14}

3）步骤 ( 3 ) 计算中心值

根据新的聚类分组计算新的中心值 :

① 计算 K1 分组的中心值 : K1={P1,P2,P3,P4,P5} , 计算过程如下 :

② 计算 K2 分组的中心值 : K2={P6,P7,P8} , 计算过程如下 :

③ 计算 K3 分组的中心值 : K3={P9,P10,P11,P12,P13,P14} , 计算过程如下 :

最新计算出的 C1,C2,C3 中心点是 {5,12,48}

2、第二次迭代