聚类算法详解

发布时间:2024年01月03日

K-maens & DBSCAN
与分类、回归任务不同,聚类任务事先并不知道任何样本标签,通过数据之间的内在关系把样本划分为若干类别,使得同类别之间的相似度高,不同类别之间的样本相似度低。
K-means
基本思想
K-means算法的基本思想是,通过迭代寻找K个簇(Clusterd)的一种划分方案,使得聚类结果对应的损失函数最小。
其中,损失函数可以定义为各个样本距离所属簇中心点的误差平方和:
J ( c , μ ) = ∑ i = 1 M ∣ ∣ x i ? μ c i ∣ ∣ 2 J(c,\mu) = \sum_{i=1}^M|| x_i -\mu_{c_i} || ^2 J(c,μ)=i=1M?∣∣xi??μci??2
其中Xi代表第i个样本,Ci是Xi所属的簇,U代表簇对应的中心点,M是样本的总数
具体步骤
K-means的核心目标是将数据集划分为K个簇,并给出的每个簇的中心点。具体步骤分为四步:

  • 数据预处理。主要将数据标准化、异常点过滤
  • 随机选取K个中心点
    μ 1 ( 0 ) , μ 2 ( 0 ) , . . . , μ k ( 0 ) \mu_1^{(0)},\mu_2^{(0)},...,\mu_k^{(0)} μ1(0)?,μ2(0)?,...,μk(0)?
  • 定义损失函数
    J ( c , μ ) = ∑ i = 1 M ∣ ∣ x i ? μ c i ∣ ∣ 2 J(c,\mu) = \sum_{i=1}^M|| x_i -\mu_{c_i} || ^2 J(c,μ)=i=1M?∣∣xi??μci??2
  • 令t=0,1,2。。。为迭代步数,重复以下步骤直到损失函数收敛:
    • 对于每一个样本xi,将其分配到距离最近的中心
      c i t < ? a r g m i n k ∣ ∣ x i ? μ k t ∣ ∣ 2 c_i^t <- argmin_k|| x_i - \mu_k^t||^2 cit?<?argmink?∣∣xi??μkt?2
    • 对于每一个类中心k,重新计算该类的中心
      μ k t + 1 < ? a r g m i n μ ∑ i : c i t = k b ∣ ∣ x i ? μ ∣ ∣ 2 \mu_k^{t+1} <- argmin_{\mu} \sum_{i:c^t_i=k}^b|| x_i - \mu||^2 μkt+1?<?argminμ?i:cit?=kb?∣∣xi??μ2
      DBSCAN
  1. 寻找核心点形成临时聚类簇。
    扫描全部样本点,如果某个样本点R半径范围内点数目>=MinPoints,则将其纳入核心点列表,并将其密度直达的点形成对应的临时聚类簇。
  2. 合并临时聚类簇得到聚类簇。
    对于每一个临时聚类簇,检查其中的点是否为核心点,如果是,将该点对应的临时聚类簇和当前临时聚类簇合并,得到新的临时聚类簇。
    重复此操作,直到当前临时聚类簇中的每一个点要么不在核心点列表,要么其密度直达的点都已经在该临时聚类簇,该临时聚类簇升级成为聚类簇。
    继续对剩余的临时聚类簇进行相同的合并操作,直到全部临时聚类簇被处理。
    聚类算法的各自缺点:
    K-means 问题:
  • 第一个就是对簇的数量的选择,我们希望指定一个簇数K,以使每个点和其最近的簇的距离之和最小。但是在实际情况中,我们很难找到一个合适的K值,因为我们不知道应该将数据分为几类。
  • Kmeans 算法会把所有的数据点都进行分类,但是很多情况下,会有一些离群点,这些点应该被剔除的,但是 Kmeans 算法还是会把它们归为某一类。
  • k均值聚类假设对每个簇来说,所有的方向都同等重要。这也就意味着k均值聚类主要适用于球形分布的数据,对于其他分布的数据分类可能不好。
    DBSCAN缺点:
  • 如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差,这时用DBSCAN聚类一般不适合。
  • 如果样本集较大时,聚类收敛时间较长,此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
  • 调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值??,邻域样本数阈值MinPoints联合调参,不同的参数组合对最后的聚类效果有较大影响。
    聚类算法的优点:
    K-means:
  • 高效可伸缩,计算复杂度接近于线性(N是数据量,K是聚类总数,t是迭代轮数)。
  • 收敛速度快,原理相对通俗易懂,可解释性强。
    BDSCAN:
  • 可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。
  • 可以在聚类的同时发现异常点,对数据集中的异常点不敏感。
  • 聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响
文章来源:https://blog.csdn.net/weixin_43186779/article/details/135347586
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。