k均值是基于划分的聚类技术，其特征为聚类的结果趋向于类球形，而k值就是需要发现的k个类，一般由使用者指定。

k-means

k均值通常用于n维连续空间（数值类型）中的数据，其算法思想比较简单：

选择k个初始质心，然后将样本中的每个点指派到最近的质心，指派的方法一般是计算距离，以每个质心和所属他的点为一个簇，重新计算出该簇的质心，重复下去，直到簇不变（也可以是质心不变）

该算法思想有两大需要解决的问题：
1. k的大小该如何选择
2. k个初始点该如何选择

k的大小无疑会影响聚类的效果，并且k的位置选择不好会导致局部局部最小，如下图：

上述两个问题将在最后介绍解决方法。

层次聚类

一般我们说的层次聚类包含两种方法：凝聚层次聚类，分裂层次聚类。
区别在于，前者从每个点作为一个簇开始，每次合并两个簇，后者相反。
从方法上来说，凝聚层次聚类一开始就又n个簇，每个簇是一个点，每次聚类都减小一个簇。
这意味着，簇的个数从0到n（对比k-means，肯定包含k在内）。
和k-means一样，层次聚类也面临着合并指标的选取，一般来说有如下选取指标：

• min：两个簇中最近点之间的距离
• max：两个簇中最远点之间的距离
• 组平均：两个簇的点之间的距离的平均值
• 质心：两个簇的质心的距离
  

簇评估

关于聚类，有一个问题尤为重要，即簇评估。
类似软件开发中的标准，对于簇的好坏评价，同样我们遵从：高内聚低耦合。
我们希望一个簇内的点的相似性尽可能大，而簇之间的相似性尽可能小。
这里的相似性，我们可以使用简单的距离来表示。
于是就有如下指标：

其中，ci表示Ci的质心，dist()表示距离函数。
即cohesion越小越好，separation越大越好。

SSE(Sum of Squares for Error)是凝聚度和分离度的另一种数值表示。
如，单个簇的SSE如下：

另一种评价指标是使用轮廓系数。
轮廓系数针对单个样本点而论。
其定义如下：
1. 对于样本点S,计算他到所属簇的其他对象的平均距离即为d1
2. 计算S到所有其他簇的对象的距离，并针对其他簇计算平均距离，取最小的平均距离，记为d2
3. S的轮廓系数是：s=d2−d1d2
一般我们假定d2>d1。
由上述公式可得，d1显然是越小越好，d2显然是越大越好，即s越接近1越好，越接近0越不好。
有了单个点的轮廓系数，就可以求得整个簇的平均轮廓系数。

DBSCAN

DBSCAN和上述两种聚类具有完全不同的使用场景，层次聚类和k-means都是倾向于发现类球形的数据，但DBSCAN是用于找出不同密度的类。
这里不过多介绍，可参考数据挖掘导论里的介绍。
只提一下两个参数作为备忘录：
- MinPts：可作为簇的个数阈值
- eps：作为判定点类型的距离半径

通常来说，MinPts越大，对于可以组成簇的点的个数要求越大，找到的簇的点的个数也越大；eps越小，对于簇的密度的要求越大，找到的簇的密度越大。
利用DBSCAN的这种性质，可以使用DBSCAN进行降噪处理。

关于k的两个问题

最后探讨下上面提到的两个关于k-means的两个景点问题：k如何选取，和k个初始质心的选择。

k个质心的选择

我们先讨论假设k值选定后，如何选择k个合适的初始质心，具体来说有如下方法可供选择

选择尽可能远的点

已知k，首先任意选择一个点，计算每个点到该质心的距离，选择距离最远的点为第二个质心，重新将其他点分配到这两个质心，再选出距离最大的点，知道质心个数达到k。

使用层次聚类

上面提到，层次聚类从开始到结束，簇的个数有n减小到1.毫无疑问k是包含在里面的，进行凝聚层次聚类时，到簇的个数为k时停止，从这k个簇中分别选择一个点出来作为初始质心。

二分k均值

所谓二分k-means就是选择一个簇，然后分裂该簇为两个簇。
一般来说，选择的簇是最大的簇，或者最大SSE的簇。
其实二分k-means有点类似分裂层次聚类。

k大小的选择

之所以先讲如何选择k个质心，是因为k大小的选择可以用通过使用k个质心的位置来评判。

轮廓系数法和SSE

上文中，我们提出轮廓系数法是作为一种评价聚类效果的度量，但同样的我们可以延伸出：k如果选择的不好，那么其对应的轮廓系数必然较小。
即，选择使得轮廓系数最大的k值。
同样的，SSE也可以采用类似的思想，由于k越大，SSE必然越小，比如当k=n时，SSE=0.因此对于SSE，我们选择使得SSE减小图像的拐点。
图形表示吐如下：