常用聚类算法

k均值算法

算法步骤：这个算法需要事先知道数据有几类。假设我们的数据一共有k类。然后从数据样本点中任取k个点。作为每一个类的中心点。然后计算每一个样本点到每一个中心点的距离。对于每一个样本点，找到与他距离最近的中心点。然后把他归于这个中心点所在的类。最后计算每一个类别的均值。把这个均值作为新的中心点。递归前面的操作。直到中心点不在变动。

这个算法是对初始值敏感的。取不同的中心点，可能将会有不同的结果。下面的k-means++算法将会弥补这一缺点

k-means++

算法步骤：在数据集中任取一个点作为初始类中心。计算所有样本点到这一个类中心的距离。把距离中心最远的样本点作为第二个类中心。重复这个步骤知道选出k个中心。然后利用前面的k-means算法实现聚类。

密度最大值聚类

这个用来做离群值和中心点检测的。

首先定义局部密度  。表示到样本点 i 的距离小于等于某一个阀值m的样本点个数。由于该算法只对ρi 的相对值敏感, 所以对m的选择是稳健的，一种推荐做法是选择m ，使得平均每个点的邻居数为所有点的1%-2%。

定义高局部密度点距离。表示在所有的局部密度比 j 点大的点中。到点 j 的距离的最小值。 即比我高的局部密度点到我的最小距离。

然后得到这两个指标我们就可以判断中心点和离散点了。小大，可以判定 i 点是离散点。大大可以判定是中心点。如下图

 

 基于密度聚类 DBSCAN 算法

有以下定义

核心点：给定半径 r 。给定最少点的个数m。  对于样本点 i 。如果在以 i 为圆心以r为半径的圆内的样本点的个数大于m。那么 i 就叫做核心点。

边界点：对于样本点 j .如果在以 i 为圆心以r为半径的圆内的样本点的个数小于m。并且j在核心点 i的圆域内。那么j就叫做边界点。

直接密度可达：如果 i 是核心点，任意的j样本点落在了 i 的圆域里。那么 i 是直接密度可达 j 的。

密度可达：i 是直接密度可达 j 的j是直接密度可达 m 的那么 i 是密度可达m的。（其中i，j 都是核心点）

密度相连：核心点o是密度可达m，n的 。那么m，n是密度相连的。

DBSCAN 算法就是把所有能够，直接密度可达，密度相连，密度可达的点。合并为一个集合。最后得到多个集合。形成多个分类。聚类效果如下