【机器学习】聚类:K-Meams和DBSCAN

K-Meams和DBSCAN教程。

---

聚类

聚类：将多个对象按各自的特征，分成不同的几个类，即相似的分为一类。 无监督：不需要标签，只用对象本身。

K-Meams（K均值聚类）

• 思想：相同类的对象应该集中在一起。

  定义

• 质心：即均值，距离各维的平均值。
• 距离度量：欧氏距离或余弦相似度(标准化)。

  K-Meams算法

• 初始化：先根据类(簇)的个数指定k值，任选k个点做质心，其他点加入距离最小的簇；
  1. 对k个簇更新质心；
  2. 重新遍历所有点，加入最近簇；
• 循环1,2进行迭代即可。

优点

• 简单快速，无需标签，适合常规Dataset；
• 只有一个参数k.

  缺点

• K值难确定；
• 不能对任意形状成立(比如环)。

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

• 思想：相同类的对象应该比较密的分布（连接）在一起。

定义

• Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域；
• 核心对象：如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象；
• 直接密度可达：对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达。
• 密度可达：对于样本集合D，给定一串样本点p1,p2….pn，p= p1,q= pn,假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。
• 密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相连。

DBSCAN算法

• 初始化：设定n个类，半径e，最少数目MinPts;
  1. 抽出一个未处理的点；
  2. 抽出的点是核心点——找出所有从该点密度相连的对象，形成一个簇； 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一个点；
• 循环1，2直到所有点被处理。

优点

• 不需要直到簇的个数；
• 可以对任意形状的分布生效；
• 离群点比较好找；
• 只有两个参数：半径e，最少数目MinPts.

  缺点

• 高维处理比较困难（降维）；
• 初始参数比较难选，对结果影响较大。

---