聚类算法详解

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

• 数据预处理。主要将数据标准化、异常点过滤
• 随机选取K个中心点
  $${\mu }_1^{(0)},{\mu }_2^{(0)},...,{\mu }_k^{(0)}$$
• 定义损失函数
  $$J(c,\mu )=\sum _{i=1}^M||x_i?{\mu }_{c_i}|{|}^2$$
• 令t=0，1，2。。。为迭代步数，重复以下步骤直到损失函数收敛：
  • 对于每一个样本xi，将其分配到距离最近的中心
    $$c_i^t<?argmi{n}_k||x_i?{\mu }_k^t|{|}^2$$
  • 对于每一个类中心k，重新计算该类的中心
    $${\mu }_k^{t+1}<?argmi{n}_{\mu }\sum _{i:c_i^t=k}^b||x_i?\mu |{|}^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之类的聚类算法初始值对聚类结果有很大影响