动手机器学习->实现KMeans算法

KMeans完整代码想抄作业的同学直接点这里

一、KMeans算法简介

KMeans是经典的聚类算法

假设要在一个新的城市中,开几个大型商场,应该怎样选址才能吸引更多客户呢?如果显然都商场都建立在郊区不是最好的选择,但是商场都建立市中心也不是最好的选择。其中一种解决方案就使所有居民距离自己区域的商场距离最近。

KMeans算法,主要由两部分组成:

  1. 初始聚类中心的选择
  2. 聚类中心的迭代更新

二、初始聚类中心的选择

随机选择

随机选择是最简单的一种初始化聚类中心的方法,其步骤就是随机从数据中选取K个样本,作为初始的聚类中心。

k-means++

k-means++的步骤是:先随机选取一个点,然后在选择下一个点时,选择与已选择点距离最远的样本点。可以说"k-means++“是一种倾向于选择相互距离较远的样本点最为初始点(这个初始化的方法目前,没有在代码中实现)

三、聚类中心的迭代更新

Kmeans算法的目标为: 找到合适的聚类中心,使得所有样本到其分组中心的距离的平方最小,用数学公式表达,假设有N个样本,K个聚类中心,Kmeans的目标为:

$$ E = \sum_{i=1}^{k} \sum_{x \in C_i } distant(x - \mu_i) ^ 2 $$

其中,$ \mu_i = \frac{1}{C_i} \sum{}{x \in C_i } $,$\mu_i$是簇$C_i$的均值向量。

如果直接求最合适的聚类中心,很难,这是一个NP难问题,因此K-means算法采用贪心策略通过迭代来求近似最优解。

算法流程如下所示:

伪代码

我们可以将书中的伪代码,进一步抽象可以分为下面几个步骤

  1. 计算每个样本与每个聚类中心的距离
  2. 将样本划分到距离样本最近的聚类簇当中去
  3. 重新计算聚类中心点向量
  4. 如果新聚类中心点向量 跟 旧的聚类中心点向量不一样,更新聚类中心点向量
  5. 如果一样或者达到最大迭代次数,算法完毕

举个例子

西瓜数据集如下所示,手动模拟Kmeans算法,将数据集聚类成2类.

样本编号 密度 重量
1 1 3
2 1 4
3 3 5
4 5 5

步骤0: 随机选择两个样本作为聚类中心点

假设选择样本编号为1,2的样本最为初始聚类中心点

$\mu_1 = {1,3} $ $\mu_2 = {1,4} $

Center = {{1,3},{1,4}}

步骤1: 计算每个样本到聚类中心点的距离

欧式距离平方 $\mu_1$ $ \mu_2$
样本1 0 1
样本2 1 0
样本3 4+4=8 4+1=5
样本4 16+4=20 16+1=17

步骤2: 将样本划分到距离样本最近的聚类簇当中去

聚类簇1的样本为 {样本1}

聚类簇2的样本为 {样本2,样本3,样本4}

步骤3: 重新计算聚类中心点向量

$\mu_1 = {1,3} $ $\mu_2 = {3,4.66} $

步骤4: 判断新聚类中心是否和旧聚类中心一样

答案不一样,继续执行步骤1

第二轮,步骤1: 计算每个样本到聚类中心点的距离

Warning

注意这里$ \mu $ 已经更新了

欧式距离平方 $\mu_1$ $ \mu_2$
样本1 0 4+2.56=6.56
样本2 1 4+0.36=4.36
样本3 4+4=8 0+0.09=0.09
样本4 16+4=20 4+0.09=4.99

第二轮,步骤2: 将样本划分到距离样本最近的聚类簇当中去

聚类簇1的样本为 {样本1,样本2}

聚类簇2的样本为 {样本3,样本4}

第二轮,步骤3: 重新计算聚类中心点向量

$\mu_1 = {1,3.5} $

$\mu_2 = {4,5} $

第二轮,步骤4: 判断新聚类中心是否和旧聚类中心一样

答案不一样,继续执行步骤1

第三轮,步骤1: 计算每个样本到聚类中心点的距离

Warning

注意这里$ \mu $ 又更新了

欧式距离平方 $\mu_1$ $ \mu_2 $
样本1 0.25 9+4=13
样本2 0.25 9+1=10
样本3 4+2.25=6.25 1+0=1
样本4 16+2.25=18.25 1+0=1

第三轮,步骤2: 将样本划分到距离样本最近的聚类簇当中去

聚类簇1的样本为 {样本1,样本2}

聚类簇2的样本为 {样本3,样本4}

第二轮,步骤3: 重新计算聚类中心点向量

$\mu_1 = {1,3.5} $

$\mu_2 = {4,5} $

第三轮,步骤3: 重新计算聚类中心点向量

$\mu_1 = {1,3.5} $

$\mu_2 = {4,5} $

第三轮,步骤4: 判断新聚类中心是否和旧聚类中心一样

答案一样,迭代结束

结果: 聚类中心点为

$C_1 = {1,3.5}$

$C_2 = {4,5}$

算法结束

四、探索性问题

这即是探索性的问题,也是我自己的代办问题解答,如果有时间,我一定会完善下面的问题。

  1. Kmeans怎么对数据集属性进行加权?

  2. Kmeans三种初始化聚类中心的详细过程?