【机器学习十大算法】--K-Means/DBSCAN聚类算法（通俗易懂保姆级讲解）

作者：迪哥谈AI发布时间：2023-08-29

机器学习中，已经分析过属于回归任务的线性回归模型，以及属于分类任务的逻辑回归模型，两者都属于有监督模型，即数据集必须包含真实值，也就是标签。如果我们的数据集没有确切的标签，这种情况下归类于无监督问题，本篇讲解机器学习中简单好用的两类无监督聚类算法。

聚类任务的本质就是分类，将相似的东西划归为同一类。由于数据集中没有标签，因此无监督聚类任务的难点在于很难直接评估模型的效果，模型调参也没有清晰的依据，K-means算法是机器学习中经典的聚类算法

K-means 算法的基本思想是将所有的数据划分为 K 个簇，K 的数值是人为设定的，簇中心的定义是质心，即该簇中所有的向量在各个维度上计算得到的平均值。 数据集中每个点计算与簇中心的欧几里得距离或者余弦相似度，并将其作为入簇的距离度量。算法整体的优化目标是希望最小化各簇中各点到簇中心的距离之和

K-means 算法的实现过程如下图所示，首先随机初始化 K 个点作为簇中心（图 b），计算数据集中所有点到 K 个簇中心的欧氏距离，并根据就近原则将其划分入簇（图 c），根据各簇中的数据重新计算簇中心的位置（图 d），再次重复上述步骤：计算欧式距离、分簇、更新簇中心等过程，直至各簇趋于稳定。

K-means 算法具备原理简单、实现快速的优点，适合常规的数据集。但 K 值需要人为设定，依赖人工经验；数据集越庞大，算法的计算量就越大；对于任意形状的簇，很难正确划分，如下图所示，本应该是中心一簇，外环一簇，却被 K-mens 划分成一左一右两个簇。

机器学习中另一个常用的聚类算法是 DBSCAN 算法，它是一种基于密度的聚类算法，主

要思想是寻找被低密度区域分离的高密度区域，数据集中特定点的密度可以通过该特定点 r邻域之内的点计数（包括本身）来估计，基于此度量方式，可以将数据集中的点划分为三类：核心点、边界点、噪音点。

（1）核心点：若某个点的密度超过算法设定的阈值，则其为核心点。即该点 r 邻域内点的数量不小于 MinPts，其中 r 值与 MinPts 值都是人为设定的先验值。

（2）边界点：若某个点的密度小于算法设定的阈值，但该点位于某个核心点的 r 邻域内，则其为边界点，边界点是核心点的邻居。

（3）噪音点：既不是核心点，也不是边界点的其余各点。

点与点之间的关系也可划分为三类：直接密度可达、密度可达、密度相连。

（1）直接密度可达：若点 p 在点 q 的 r 邻域内，且 q 是核心点，则 p 与 q 是直接密度可达。

（2）若存在一个点的序列（q0、q1、...qk），对任意 qi 与 q（i-1）是直接密度可达的，则称从 q0 到 qk 是密度可达，这实际上是直接密度可达的“传播”。

（3）若从某核心点 p 出发，点 q 和点 k 都是密度可达的，则称点 q 和点 k 是密度相连的。

DBSCAN 算法的工作流程比较清晰，主要分为以下四步：

（1）首先需要准备数据集 D，人为指定半径参数 r 以及密度阈值 MinPts。

（2）将数据集中所有点默认标记为“未访问”，从中随机选择一个点标记为“已访问”，判断该点 r 邻域内点的计数是否超过密度阈值 MinPts，若小于，则标记该点为边界点或噪音点，若超过，则创建一个新的簇 C，并将该点添加至簇 C 中。

（3）对于该点邻域内的其他点，将其添加至 N 集合中，并依次重复上述过程，循环标记、判断这些点是否为核心点，若为核心点则加入簇 C 中，邻域内的点加入集合 N 中。当簇 C遍历完成，再次从未访问的点中随机取，创建其他新的簇，整个过程重复进行，直至所有的点都已被访问。

其中仍需要人工指定两个超参数：邻域半径 r 和密度阈值 MinPts，对于给定数据集P={p(i); i=0,1,...n}，计算点 P(i)到集合 P 的子集 S 中所有点之间的距离，距离按照从小到大的顺序排序，d(k)就被称为 K 距离。根据 K 距离，寻找其中的突变点作为邻域半径 r，MinPts通常设置小一点，超参数需要多次尝试、不断观察效果进行调整。

DBSCAN 算法不再需要指定簇的数量，可以发现任意形状的簇，能够很好的检测到离群点或噪音点，但不擅长处理高纬度的数据，超参数的选择依赖经验，算法执行效率相对较慢。K-Means 算法与 DBSCAN 算法各有优劣，都是机器学习中常用的聚类算法，实际使用中需要根据自己数据集的具体情况展开尝试。