聚类算法：kmeans和dbscan

---

一、kmeans简介

kmeans是一种无监督学习算法，该算法的目标是给定若干个无标签的样本，将这些样本根据样本间的距离聚成k个类别。
算法流程：

1. 随机选择k个样本，将这k个样本当作初始的k个类的中心；
2. 计算其他样本到这k个中心的距离，将这些样本归类到距离最近的类别中；
3. 类别中包含的样本更新之后，类别的中心点会发生变化，更新中心点的位置之后，重新计算各个点到中心点的距离，更新各个类别；
4. 如此循环往复，直到满足终止条件，通常，终止条件是类中包含的样本不再变化。

二、kmeans特点

1. kmeans是基于划分的聚类方法，类别数k需要事先指定，距离的计算方式需要事先指定，以样本到其所属的类别中心的距离为优化目标，但是算法是启发式算法，不能保证得到全局最优，初始中心的选择会对结果产生比较大的影响；
2. k值的选择，当k值很小的时候，类别的平均直径较大，当k值增大时，类别的平均直径会降低，继续增大k值，类别的平均直径趋于稳定，关系如下图：
   
3. kmeans不适合non-convex的数据集。

 

三、dbscan简介

density-based spatial clustering of application with noise，基于密度的聚类算法，该算法是不断的对cluster进行扩展，而且dbsacn适用于任何形状的数据。不需要事先指定类别的数量。
 
dbscan的算法流程如下：

1. 指定两个参数，epsilon和minpoint，epsilon指半径，minpoint指最小的点数。随机选中一个点P，以P为中心，epsilon为半径画圆，如果圆中的点数超过minpoint，则将这个圆作为一个cluster；
2. 遍历cluster中的点，以点为中心，epsilon为半径画圆，如果圆中的点超过minpoint，就将这个新的圆扩展到新的cluster中；
3. 如此递归下去，直到所有的点都被遍历了一遍。
    

四、dbscan特点

1. 适应于任何形状的数据；
2. 有可能存在某些点最后没有归到任何的cluster中，这些点可以认为是噪音；
3. dbscan运行时间复杂度较高，因为需要递归的遍历所有的点。
    

五、kmeans和dbscan对比

如下网址dbscan和kmeans可视化的对比了kmeans和dbscan。