当前位置:首页|资讯|机器学习

【机器学习十大算法】--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 算法各有优劣,都是机器学习中常用的聚类算法,实际使用中需要根据自己数据集的具体情况展开尝试。

内容对你有帮助记得三连支持一下,up主后面详细更新AI相关的知识点


Copyright © 2024 aigcdaily.cn  北京智识时代科技有限公司  版权所有  京ICP备2023006237号-1