一、kmeans简介
kmeans是一种无监督学习算法，该算法的目标是给定若干个无标签的样本，将这些样本根据样本间的距离聚成k个类别。
算法流程：
- 随机选择k个样本，将这k个样本当作初始的k个类的中心；
- 计算其他样本到这k个中心的距离，将这些样本归类到距离最近的类别中；
- 类别中包含的样本更新之后，类别的中心点会发生变化，更新中心点的位置之后，重新计算各个点到中心点的距离，更新各个类别；
- 如此循环往复，直到满足终止条件，通常，终止条件是类中包含的样本不再变化。
二、kmeans特点
- kmeans是基于划分的聚类方法，类别数k需要事先指定，距离的计算方式需要事先指定，以样本到其所属的类别中心的距离为优化目标，但是算法是启发式算法，不能保证得到全局最优，初始中心的选择会对结果产生比较大的影响；
- k值的选择，当k值很小的时候，类别的平均直径较大，当k值增大时，类别的平均直径会降低，继续增大k值，类别的平均直径趋于稳定，关系如下图：
- kmeans不适合non-convex的数据集。
三、dbscan简介
density-based spatial clustering of application with noise，基于密度的聚类算法，该算法是不断的对cluster进行扩展，而且dbsacn适用于任何形状的数据。不需要事先指定类别的数量。
dbscan的算法流程如下：
- 指定两个参数，epsilon和minpoint，epsilon指半径，minpoint指最小的点数。随机选中一个点P，以P为中心，epsilon为半径画圆，如果圆中的点数超过minpoint，则将这个圆作为一个cluster；
- 遍历cluster中的点，以点为中心，epsilon为半径画圆，如果圆中的点超过minpoint，就将这个新的圆扩展到新的cluster中；
- 如此递归下去，直到所有的点都被遍历了一遍。
四、dbscan特点
- 适应于任何形状的数据；
- 有可能存在某些点最后没有归到任何的cluster中，这些点可以认为是噪音；
- dbscan运行时间复杂度较高，因为需要递归的遍历所有的点。
五、kmeans和dbscan对比
如下网址dbscan和kmeans可视化的对比了kmeans和dbscan。