K-Means

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

目标函数：

其中是簇的均值向量，也叫质心

利用启发式方法，首先随机选取K个点，计算其他点和k个点的距离，进而得到K个类，计算K个类的质心，然后再次迭代聚类，知道质心不在发生明显变化或者迭代到一定次数结束。

参数选取

K-Means 算法需要根据数据的先验经验来选择一个合适的K值，对于不确定性的数据集或者流式数据集，则不适合使用该种方法

算法流程

输入是样本集D={x1,x2,...xm},聚类的簇树k,最大迭代次数N

输出是簇划分C={C1,C2,...Ck}

1) 从数据集D中随机选择k个样本作为初始的k个质心向量： {μ1,μ2,...,μk}
　　　　2）对于n=1,2,...,N

a) 将簇划分C初始化为Ct=∅t=1,2...k
　　　　　　b) 对于i=1,2...m,计算样本xi和各个质心向量μj(j=1,2,...k)的距离：dij=||xi−μj||22，将xi标记最小的为dij所对应的类别λi。此时更新Cλi=Cλi∪{xi}
　　　　　　c) 对于j=1,2,...,k,对Cj中所有的样本点重新计算新的质心μj=1|Cj|∑x∈Cjx
　　　　　　e) 如果所有的k个质心向量都没有发生变化，则转到步骤3）

3） 输出簇划分C={C1,C2,...Ck}

衍生算法

（1）K-Means++

初始化质心的优化

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

K-Means++的对于初始化质心的优化策略也很简单，如下：

a) 从输入的数据点集合中随机选择一个点作为第一个聚类中心μ1
　　　　b) 对于数据集中的每一个点xi，计算它与已选择的聚类中心中最近聚类中心的距离D(xi)=argmin||xi−μr||22r=1,2,...kselected
　　　　c) 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
　　　　d) 重复b和c直到选择出k个聚类质心
　　　　e) 利用这k个质心来作为初始化质心去运行标准的K-Means算法

（2）elkan K-Means

距离计算优化

在传统的K-Means算法中，我们在每轮迭代时，要计算所有的样本点到所有的质心的距离，这样会比较的耗时。那么，对于距离的计算有没有能够简化的地方呢？elkan K-Means算法就是从这块入手加以改进。它的目标是减少不必要的距离的计算。那么哪些距离不需要计算呢？

elkan K-Means利用了两边之和大于等于第三边,以及两边之差小于第三边的三角形性质，来减少距离的计算。

第一种规律是对于一个样本点x和两个质心,。如果我们预先计算出了这两个质心之间的距离，则如果计算发现,我们立即就可以知道。此时我们不需要再计算,也就是说省了一步距离计算。

第二种规律是对于一个样本点x和两个质心。我们可以得到。这个从三角形的性质也很容易得到。

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

（3）Mini Batch K-Means

大样本优化

在统的K-Means算法中，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时，就算加上elkan K-Means优化也依旧。在大数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。

顾名思义，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。

在Mini Batch K-Means中，我们会选择一个合适的批样本大小batch size，我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本怎么来的？一般是通过无放回的随机采样得到的。

为了增加算法的准确性，我们一般会多跑几次Mini Batch K-Means算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。

小结

K-Means是个简单实用的聚类算法，这里对K-Means的优缺点做一个总结。

K-Means的主要优点有：

1）原理比较简单，实现也是很容易，收敛速度快。

2）聚类效果较优。

3）算法的可解释度比较强。

4）主要需要调参的参数仅仅是簇数k。

K-Means的主要缺点有：

1）K值的选取不好把握

2）对于不是凸的数据集比较难收敛

3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。

4） 采用迭代方法，得到的结果只是局部最优。

5） 对噪音和异常点比较的敏感。

BIRCH

BIRCH(Balanced Iterative Reducing and Clustering Using Hierarchies, 利用层次方法的平衡迭代规约和聚类)算法提供了一种类似B树的数据结构，能够在单次扫描完所有的数据就能实现聚类。

聚类特征CF(cluster feature)

每一个CF是一个三元组，可以用（N，LS，SS）表示。其中N代表了这个CF中拥有的样本点的数量，这个好理解；LS代表了这个CF中拥有的样本点各特征维度的和向量，SS代表了这个CF中拥有的样本点各特征维度的平方和。

CF满足线性性，即:

聚类特征树CFT（cluster feature tree）

生成过程参考B树的生成过程。构建CFT的过程，需要定义内部节点的最大CF数量B，叶子节点的最大CF数L，叶子节点每个CF的最大样本半径阈值T。T值的大小能够确定CFTree的规模，如果T太小，簇的数量将会非常的大，导致树节点数量也会增大，内存消耗较大。

参考文档

• BIRCH聚类算法原理
• 层次聚类算法