K-Means算法

作者: 格物致知Lee | 来源:发表于2019-02-17 22:14 被阅读0次

K-Means算法是无监督算法之一，主要用于样本的聚类。其思想很简单，对于给定的样本集，按照样本与聚类中心之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连接在一起让簇间的距离尽量的大。上述是一个综合性的描述，你可能会有点不理解，不用担心，让我们带着这个问题继续进行学习。

1.K-Means的原理

在样本空间中有n个样本 $(\vec{x_{1} } ，\vec{x_{2} } ...\vec{x_{n} } )$ ，假设我们要把样本分为 $(C_1,C_2,...C_k)$ K个簇，首先我们在n个样本中随机选取K个样本，以K个样本作为个K个簇的聚类中心 $(\vec{\mu } _1,\vec{\mu } _2,...\vec{\mu } _k)$ ，而后聚类中心的更新按公式计算：

$\vec{\mu_i} = \frac{1}{|C_i|}\sum\limits_{\vec{x} \in C_i}\vec{x}$

我们的目标是最小化平方误差E：

$E = \sum\limits_{i=1}^k\sum\limits_{\vec{x} \in C_i} ||\vec{x} -\vec{\mu_i} ||_2^2$

我们采用迭代的方式来逐步减小平方误差E，迭代的过程如下图所示：

2.传统K-Means迭代算法流程

输入：簇的数目k和包含n个样本 $(\vec{x_{1} } ，\vec{x_{2} } ...\vec{x_{n} } )$ 的数据。

输出：k个簇 $C=\{C_1,C_2,...C_k\}$ 。

算法步骤：

1.为每个聚类确定一个初始的聚类中心，这样就有K 个初始聚类中心 $(\vec{\mu } _1,\vec{\mu } _2,...\vec{\mu } _k)$ 。

2.将样本集中的样本按照最小距离原则分配到最邻近聚类。即分别按公式 $d_{ij} = ||\vec{x} _i - \vec{\mu } _j||_2^2$ ，计算样本 $\vec{x_{i} }$ 与各聚类中心 $\vec{\mu _{j} }$ 间的距离，将样本与离其最近的聚类中心分为同一个簇。

3.按聚类中心的计算公式 $\vec{\mu_i} = \frac{1}{|C_i|}\sum\limits_{\vec{x} \in C_i}\vec{x}$ ，计算每个簇的聚类中心作为新的聚类中心。

4.重复步骤2.3直到聚类中心不再变化。

5.结束，得到K个簇 $C=\{C_1,C_2,...C_k\}$ 。

算法执行状况如下图所示：

3.K-Means初始的优化K-Means++

在K-Means算法中，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心。如果仅仅是完全随机的选择，有可能导致算法收敛很慢。K-Means++算法就是对K-Means随机初始化质心的方法的优化。

K-Means++对初始聚类中心的优化如下：

1.从样本集 $(\vec{x_{1} } ，\vec{x_{2} } ...\vec{x_{n} } )$ 中随机选择一个点作为第一个聚类中心 $\vec{\mu _{1} }$

2.对于样本集 $(\vec{x_{1} } ，\vec{x_{2} } ...\vec{x_{n} })$ 中的每一个样本 $\vec{x_{i} }$ ，计算其与已存在的各个聚类中心的距离，取最近的距离为 $D(\vec{x_{i} } )$

$D(\vec{x_{i} } ) = arg\;min||\vec{x_{i} } - \vec{\mu _{r} } ||_2^2\;\;r=1,2,...k_{selected}$

3.按照 $D(\vec{x_{i} } )$ 较大的点被选为聚类中心概率较大的原则，选取一个新的数据点作为聚类中心。

4.重复2和3直到选出K个聚类中心 $(\vec{\mu } _1,\vec{\mu } _2,...\vec{\mu } _k)$ 。

5.用 $(\vec{\mu } _1,\vec{\mu } _2,...\vec{\mu } _k)$ 作为初始聚类中心运行K-Means迭代过程。

4.elkan K-Means算法

elkan K-Means算法是对K-Means算法中距离计算的优化，ekkan K-Means利用了三角形中两边之和大于第三边，两边之差小于第三边的性质，来减少距离的计算。

规律一：对于一个样本点 $\vec{x_{i} }$ 和两个聚类中心 $\vec{\mu } _i,\vec{\mu } _j$ 所形成的三角形中，如果我们预先计算出了两个聚类中心间的距离 $D(\vec{\mu } _i,\vec{\mu } _j)$ ，如果计算发现 $2D(\vec{x_{i} } ,\vec{\mu _{i} }) \leq D(\vec{\mu _{i} },\vec{\mu _{j} })$ ，我们立即知道 $D(\vec{x_{i} } ,\vec{\mu _{i} }) \leq D(\vec{x_{i} } ,\vec{\mu _{j} })$ 。这样我们就不必要计算 $D(\vec{x_{i} } ,\vec{\mu _{j} })$ 。

规律二：对于一个样本点 $\vec{x_{i} }$ 和两个聚类中心 $\vec{\mu } _i,\vec{\mu } _j$ 所形成的三角形中， $D(\vec{x_{i} } ,\vec{\mu _{i} }) \geq max\{0, D(\vec{x_{i} } ,\vec{\mu _{j} })- D(\vec{\mu _{i} },\vec{\mu _{j} })\}$

利用上边的两个规律，elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果我们的样本的特征是稀疏的，有缺失值的话，这个方法就不使用了，此时某些距离无法计算，则不能使用该算法。

以上为建立K-Means模型的相关理论知识，如果有需要用python建立K-Means模型进行聚类的小伙伴的可以上访问我的github：

https://github.com/Rocky1ee/KMeans-Model

小伙伴们如果觉得文章还行的请点个赞呦！！同时觉得文章哪里有问题的可以评论一下谢谢你！

K-Means算法

1.K-Means的原理

2.传统K-Means迭代算法流程

3.K-Means初始的优化K-Means++

4.elkan K-Means算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读