kmeans 算法_kmeans优化算法：二分Kmeans聚类算法

算法的理解

​ Bi这里是的意思就是Binary，二进制的意思，所以有时候叫这个算法为二进Kmeans算法。为什么我们需要用BiKmeans呢，就是为了解决初始化k个随机的质心点时其中一个或者多个点由于位置太极端而导致迭代的过程中消失的问题。BiKmeans只是Kmeans其中一个优化方案，其实还是有很多优化的方案，这里BiKmeans容易讲解和理解，并且容易用numpy, pandas实现。

​ 那为什么二进Kmeans算法可以有效的解决这个问题呢。我们需要从二进Kmeans的基础看是讲起。其实BiKmeans的迭代过程类似于一个决策树。首先我们看一下Kmeans算法的步骤。

​ 利用之前写好的Kmeans算法包，设置k为2。所以每次传入一个数据集的时候，都是进行2分类。

假设我们预先想分出K个簇。

1. 使用Kmeans(k=2)将数据集分成2个簇，记录SSE
2. 对于每一个簇来说，都有自己当前的SSE，取名为父节点SSE
   a. 对这些簇都进行Kmeans二分类，并且记录分出的2个簇的SSE只和，称之为子节点总SSE
   b. 记录这个簇被2分类之后SSE的差值，SSE差值 = 父节点SSE - 子节点SSE
3. 选择SSE差值最大的那个簇进行划分，而其他的簇不进行划分。
4. 重复第二的步骤，直到簇的总个数达到K

用决策树的方法理解BiKmeans

​ 那这个算法其实就是非常的类似决策树的算法。在决策树节点由父节点划分成子节点的过程中，用的是gini不纯度来判断是否需要划分，我们选择不纯度差值最大的那个特征来做划分。这里也类似，我们最后的目标是最小化SSE，所以对每一个簇来说，都可以得出该簇在划分出成2个簇之后总体上SSE降低了多少，我们需要做的就是保持其他的簇不变，选取的就是那个能够最大程度的降低SSE的那个簇进行Kmeans二分类。

​ 那个算法里面还是有个缺陷，就是在算法的过程中，会对每个簇重复计算划分后SSE的差值，所以这里我在对每个簇做划分后，记录下它的SSE差值，后期就可以直接使用SSE，不用重新再计算一遍了。

​ 我们首先用决策树的概念来看下BiKmeans，我们目标是分成4个簇，首先有我们有我们的根节点，也就是我们的整体的数据集，假设这个数据集的SSE为100.

1. 使用Kmeans对根节点做2分类。得出2个簇，簇内SSE分别为40和30，也就是说如果我们对整体数据集做一次Kmeans二分类的话，我们的整体SSE会下降100-(30+40)=30

1. 在此时可以对每个叶节点的数据集进行二分类，查看这个簇做二分Kmeans后，SSE下降多少。从这里可以看出，对簇1来说，SSE的变化为40-(20+15)=5，对簇2来说，SSE的变化为30-(10+10)=10。所以说对这2个簇来说的话，应该保留簇1，对簇2进行二分Kmeans。这样的话可以最大程度的减少总体SSE，因为簇2二分Kmeans后SSE下降的最快。结果就是以下的情况，当前叶节点有3个，也就是说当前我们有3个簇，还没有达到我们的目标，4个簇，继续对每个叶节点进行划分。注，这里原来的簇2就不复存在了，变成了小一点的簇2和簇3。