聚类(K-means,DBSCAN)面试整理

发表于 | 分类于 | 阅读次数:

介绍聚类

聚类是无监督学习算法，想要将样本数据集划分为多个不相交的簇。

聚类的性能如何评价？—— 度量性能的指标

我们是希望聚类的结果：簇内相似度高，簇间相似度低。

所以聚类性能度量主要是两种：1. 将聚类结果与某个参考模型进行比较，这叫做“外部指标”；2. 直接考察聚类结果而不利用任何参考模型，这叫做“内部指标”

对于外部指标：

数据集中的任意两个样本点，在聚类中的给出的簇划分，和参考模型给出的簇划分，共四种情况：

  1. 在聚类中分在了同一个簇中，在参考模型中也在同一个簇内，这样的样本对数量为 a
  2. 在聚类中分在了用一个簇内，但在参考模型中不在同一个簇内，这样的样本对数量为 b
  3. 在聚类中不在同一个簇内，但在参考模型中在同一个簇内，这样的样本对数量为 c
  4. 在聚类中不在同一个簇内，在参考模型中也不在同一个簇内，这样的样本对数量为 d

所以 a + b + c + d = m(m-1)/2，m 是样本的数量，这个时候可以有如下的外部指标：

  1. Jaccard 系数

    $JC = a / (a + b + c)$

  2. FM 指数

    $FMI = \sqrt {\frac {a}{a+b} \cdot \frac{a}{a+c}}$

  3. Rand 指数

    $RI = \frac{2(a+d)}{m(m-1)}$

这三个值都在 0 和 1 之间，值越大说明聚类的效果越好

对于内部指标：

主要是依据距离来的，比如簇内的平均距离、最远距离、最近距离等等。

K-means 学习与面试问题汇总

1. 介绍 K-means

K-means 是一种聚类算法，是一种无监督学习算法，目标是将相似的对象归到同一蔟中。蔟内的对象越相似，聚类的效果就越好。

聚类与分类最大的不同在于，分类是监督学习，分类的目标已经确定；聚类是无监督学习，类别是未知的

2. K-means 的算法原理

目标：使各个样本与所在簇的质心的均值的平方和达到最小（这也是 K-means 最后聚类效果的评价标准）

$SSE = \sum_{i=1}^k{\sum_{x \in C_i}{||x-u_i||_2^2}}$

步骤：

  1. 创建 k 个点作为 k 个簇的起始质心（通常是随机选择）
  2. 分别计算剩下的元素到 k 个簇中心的距离，将这些元素分别划到距离最近的蔟
  3. 根据聚类的结果，重新计算 k 个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数
  4. 将 D 中全部元素按照新的中心重新聚类
  5. 重复第 4 步，直到聚类结果不再发生变化
  6. 最后，输出聚类结果

3. K-means 的优缺点

优点：

  1. 原理简单，实现简单
  2. 聚类效果优
  3. 算法的可解释性比较强
  4. 需要调的参数只有 K

缺点：

  1. k 需要事先给定，但是这个 k 值很难估计

    • 各种估计 K 的方法

  2. 需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果，不能保证 k_means 算法收敛到全局最优解

    目前有如下的解法方法：

    • 针对这个问题，在 K-means 的基础上提出了二分 K-means算法。该算法首先将所有点都看作是一个簇，然后一分为二，找到最小 SSE 的聚类质心。接着选择其中一个簇继续一分为二，此处哪一个簇需要，根据划分后的 SSE 来判断
    • K-means++ 算法：假设已经选去了 n 个初始聚类中心，则在选择第 k+1 个聚类中心时：距离当前 n 个聚类中心越远的点越有可能呗选为第 n+1 个簇中心
    • 先计算出整理样本的中心，然后根据样本点到中心的距离，由近至远采样作为初始聚类中心
    • 初步将数据分成 K 个区域，将每个区域的中心作为初始聚类中心
    • 计算出每个点的“密度”，认为“密度”较大的是聚类中心。先把“密度”最大的挑出来作为第一个聚类中心，然后从剩下点中挑出密度最大，且离所有已选择的聚类中心大于一定距离的点作为下一个聚类中心，直到选择了 k 个

  3. 对离群点敏感

    • 数据预处理

  4. 结果不稳定（受输入顺序影响）

  5. 计算量大

    • 利用 kd-tree 进行加速

4. K-means 的 K 值应该如何选择

给定一个合适的类簇指标，比如直径（簇内任意两点之间的最大距离）或者半径（簇内所有点到簇中心距离的最大值），只要我们假设的类簇的数目等于或者大于真实的类簇数目时，该指标上升会很缓慢，而一旦试图得到少于真实数目的类簇时，该指标就会急剧上升

5. K-means 的初始簇中心怎么选

  • 在 K-means 的基础上提出了二分 K-means算法。该算法首先将所有点都看作是一个簇，然后一分为二，找到最小 SSE 的聚类质心。接着选择其中一个簇继续一分为二，此处哪一个簇需要，根据划分后的 SSE 来判断
  • K-means++ 算法：假设已经选去了 n 个初始聚类中心，则在选择第 k+1 个聚类中心时：距离当前 n 个聚类中心越远的点越有可能呗选为第 n+1 个簇中心
  • 先计算出整理样本的中心，然后根据样本点到中心的距离，由近至远采样作为初始聚类中心
  • 初步将数据分成 K 个区域，将每个区域的中心作为初始聚类中心
  • 计算出每个点的“密度”，认为“密度”较大的是聚类中心。先把“密度”最大的挑出来作为第一个聚类中心，然后从剩下点中挑出密度最大，且离所有已选择的聚类中心大于一定距离的点作为下一个聚类中心，直到选择了 k 个

6. 手写伪代码

创建 K 个点作为 K 个初始聚类中心

当任意一个点的簇分配结果发生结果时

对数据集中的每个数据点，重新分配质心

    对每个质心：

        计算质心到数据点之间的距离

    将数据点分配到距其最近的簇

对每个簇，计算簇中所有点的均值并将其均值作为新的质心

7. K-means 与 KNN

  • K-means 是无监督学习的聚类算法，没有样本输出；KNN 是监督学习的分类算法，有对应的类别输出
  • KNN 基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的 K 个点，用这 K 个点的类别投票决定测试点的类别；而 K-means 有训练过程，要找到 K 个类别的最佳质心，从而决定样本的簇类别
  • 两个算法的相似之处是都包含同一个过程：即找出和某个点最近的点

8. K-means 与 EM（期望最大化算法） 的关系

简单理解 EM 算法

在求解概率模型参数的时候，如果需要的变量全部都是观测变量，不涉及到隐藏变量的话，可以使用极大似然函数来求解模型的参数。但是模型如果同时包含观测变量和隐藏变量的话，传统的方式就不行了，这个时候就需要 —— EM 算法。

EM 的学习目标是（目标函数）：

$L(\theta) = \log P(Y|\theta) = \log \sum _z P(Y,Z|\theta) = \log (\sum _zP(Y|Z,\theta)P(Z|\theta))$

其中，Y 表示观测变量，Z 表示隐变量。由于包含隐变量 Z，所以无法正常求解。

EM 算法的思想

利用最大似然求 $L(\theta)$ ，得到参数 $\theta$ ，其实是没有解析解的，所以通过迭代的方法来求解。

  1. 给 $\theta$ 一个初值
  2. E 步（求期望）：求隐变量 Z 的条件概率分布的期望 $Q(\theta, \theta ^{(i)}) = E_Z[\log P(Y,Z|\theta | Y, \theta ^{i})]$
  3. M 步（求极大化）：求使得 $Q(\theta, \theta ^{(i)})$ 极大化的 $\theta$，就是第 i+1 次的参数

K-means 与 EM 算法

在 K-means 中，每个聚类的簇中心是隐变量，我们会自己初始化这 K 个簇中心，也就是 EM 算法的 E 步；然后在 K-means 中，会计算每个样本到样本最近的簇中心，并把样本聚类到最近的这个簇中心，这个就是 EM 算法的 M 步。重复这个 E 步和 M 步，直到簇中心不再发生变化，这就完成了 K-means 算法。

DBSCAN

1. 简单介绍

DBSCAN 是经典的基于密度的聚类算法。DBSCAN 是基于一组邻域来描述样本集的紧密程度的，参数 $(\epsilon, MinPts)$ 用来描述邻域的样本分布紧密程度。其中，$\epsilon$ 是邻域距离阈值，MinPts 是领域内样本数量阈值。

用简单语言来解释书上提到的几个概念：

  • 核心对象：如果一个样本 x 在 $\epsilon$-领域内的样本数量 $\ge$ minPts，则这个样本点就是核心对象
  • 密度直达：若样本 j 位于 样本 i 的 $\epsilon$-领域内，且样本 i 是核心对象，则样本 i 与样本 j 密度直达
  • 密度可达：若样本 i 与 j 密度直达，样本 j 与 k 密度直达，则样本 i 与 样本 k 密度可达
  • 密度相连：若样本 i 与 j 密度可达，样本 i 与 k 也密度可达，则样本 i 与 样本 k 密度相连

DBSCAN 的聚类思想就是：由密度可达关系导出的最大密度相连样本集合。这个簇满足连接性和最大性。

2. 如何找到簇样本集合

任意选择一个没有类别的核心对象作为种子，然后找打哦所有这个核心对象密度可达的样本集合，即为一个聚类簇。接着继续选择一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

3. 算法有三个问题没有考虑

  1. 一些异常样本或者少量游离在簇外的样本点，这些点不在任何一个核心对象的范围内，DBSCAN 将这些点看作燥点
  2. 距离度量的问题，如何计算某样本和核心对象样本的距离？在 DBSCAN 中，一般采用最近邻思想，采用一种距离度量来衡量样本距离，比如欧式距离
  3. 某些样本可能到两个核心对象的距离都小于 $\epsilon$，但是这两个核心样本由于都不是密度直达的，不属于同一个聚类簇，那么如何判断这个样本的类别呢？在 DBSCAN 中，采用先来后到的思想，先进行聚类的类别簇会标记这个样本为它的类别。所以DBSCAN 是不完全稳定的算法（每次得到的结果可能不一样）

4. 算法描述

首先遍历样本集合，找出所有的核心对象

循环操作，直到核心对象集合为空

随机选取一个核心对象 a，然后从未被访问的核心对象集合中找到 a 密度可达的所有集合

5. DBSCAN 的优缺点

优点

  1. 可以对任意形状的数据集进行聚类
  2. 可以在聚类的同时发现异常点，对数据集中的异常点不敏感

缺点

  1. 如果数据很稀疏时，DBSCAN 聚类效果会比较差
  2. 如果样本数据集较大时，聚类收敛时间较长
  3. 调参比较麻烦，对 $\epsilon, MinPts$ 进行联合调参，不同的参数组合对最后的聚类效果有较大的影响

DBSCAN 与 K-Means 比较

1. DBSCAN 与传统的 K-means 的区别

  1. K-means 使用簇的基于原型的概念；DBSCAN 使用基于密度的概念
  2. K-means 需要制定簇的个数作为参数；DBSCAN 不需要簇的数量，是自动确定的，但是需要给定参数 $(\epsilon, MinPts)$
  3. 与 K-means 相比，DBSCAN 可以发现任意形状的簇类
  4. K-means 可以发现不是明显分离的簇，即便簇有重叠，也可以发现；但是 DBSCAN 会合并那些有重叠的簇（先到先得
  5. K-means 可以聚类稀疏数据，但是 DBSCAN 不可以

Reference

http://www.csuldw.com/2015/06/03/2015-06-03-ml-algorithm-K-means/ （基本 K-means 算法介绍）

https://zhuanlan.zhihu.com/p/25032944 （初始簇中心选择）

http://www.cnblogs.com/kemaswill/archive/2013/01/26/2877434.html （K 值介绍）

https://www.cnblogs.com/pinard/p/6164214.html （优点，K-means与KNN）

https://www.cnblogs.com/pinard/p/6208966.html （DBSCAN）

https://blog.csdn.net/weixin_39599711/article/details/78167232 （K-means 与 DBSCAN 的区别）

https://www.cnblogs.com/pinard/p/6912636.html （EM算法介绍，EM与K-means）