动手机器学习-实现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类.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\mu_1 = {1,3.5} $

$\mu_2 = {4,5} $

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

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

第三轮,步骤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三种初始化聚类中心的详细过程?