无监督聚类——从 K-Means 说起

达人课

---

---

0. 前言

　　在第一章中，我们就介绍了机器学习最主要的两大类就是 有监督学习(Supervised Learning) 和 无监督学习(Unsupervised Learning)。而到目前为止，我们介绍的算法全都是有监督学习方法，因此本节就来介绍一下无监督学习算法。
　　
　　首先，我们回顾一下什么叫无监督学习。在机器学习任务中，如果训练样本的标记信息是未知的，目标是通过对无标记训练样本的的学习来揭示数据内在的性质和规律。简单来说它与有监督学习方法的差别就在于无监督学习训练样本没有类别标签。

　　无监督学习方法在现实场景中还是有很多应用的，例如在金融和计算广告等反欺诈场景中，我们是不可能能够获取大量的标签数据的，因为欺诈用户不会告诉你他是欺诈用户的。这时候，如果想要利用机器学习方法检测出他们来，只能使用无监督方法。
　　
　　对于无监督学习方法，基于不同的学习策略，人们已经设计出多种类型的聚类算法：原型聚类、密度聚类以及层次聚类等。为了更好地学习不同的聚类算法，我们首先共同探讨一下聚类方法涉及的两个问题：评价指标 和 距离计算。

1. 评价指标

　　众所周知，对于有监督学习方法的分类预测结果，我们有很多种不同的评价指标来度量分类效果的好坏。例如，召回率、精准率、准确率、F1-Score以及AUC值等等。但是，由于无监督学习方法与有监督学习不同，绝大多数情况下，我们根本不知道它的真实类别标签，所以我们不可能完全依据有监督学习方法的评价指标来度量聚类算法。

图1. scikit-learn中聚类算法效果对比

　　无监督聚类算法的评价指标大致可以分为两大类：一类是，聚类的结果具有某个参考模型作为人为基准进行比较，称之为外部指标；第二种是：直接考察聚类结果而不参考任何模型，称之为内部指标。

1.1 外部指标

　　对数据集 $D=\{x_1, x_2,\cdots,x_m\}$, 假定通过聚类算法将样本聚为 $C=\{C_1,C_2,\cdots,C_k\}$, 参考模型给出的簇划分为$C^*=\{C_1^*,C_2^*,\cdots,C_s^*\}$。相应的，令 $\lambda$ 与 $\lambda^*$ 分别表示与 $C$ 与 $C^*$ 对应的簇标记向量。我们将样本两两配对考虑，定义如下：

$$\begin{align} &a=|S_1|, S_1=\{(x_i,x_j)|\lambda_i=\lambda_j,\lambda_i^*=\lambda_j^*,i<j\} \\ &b=|S_2|, S_2=\{(x_i,x_j)|\lambda_i=\lambda_j,\lambda_i^*\ne\lambda_j^*,i<j\} \\ &c=|S_3|, S_3=\{(x_i,x_j)|\lambda_i\ne\lambda_j,\lambda_i^*=\lambda_j^*,i<j\} \\ &d=|S_4|, S_4=\{(x_i,x_j)|\lambda_i\ne\lambda_j,\lambda_i^*\ne\lambda_j^*,i<j\} \end{align}$$

其中集合 $S_1$ 包含了在 $C$ 中属于相同的簇并且在 $C^*$ 中也属于相同的簇的样本； $S_2$ 包含了在 $C$ 中属于相同的簇并且在 $C^*$ 中不属于相同的簇的样本……以此类推。对每个样本对 $(x_i,x_j)$ (i < j) 仅能出现在一个集合中，因此有 $a+b+c+d = m(m-1)/2$。

　　基于以上定义，对无监督聚类算法的聚类结果我们有如下的性能度量指标：

• Jaccard系数（简记为JCI）

$$\begin{align} JCI = \frac{a}{a+b+c} \end{align}$$

• FM指数（简记为FMI）

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

• Rand指数（简记为RI）

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

很显然，上述指数值都在[0,1]之间，并且值越大越好。

1.2 内部指标

　　对于聚类结果 $C=\{C_1,C_2,\cdots,C_k\}$, 作如下定义：

$$\begin{align}&avg(C)=\frac{2}{|C|(|C|-1)}\sum_{1\le i \le j \le |C|}dist(x_i,x_j) \\& diam(C)=\max_{1\le i \le j \le |C|}dist(x_i,x_j) \\& d_{min}(C_i,C_j)=\min_{x_i \in C_i, x_j \in C_j} dist(x_i,x_j) \\& d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j) \end{align}$$

其中，$dist(x_i,x_j)$用于计算两个样本间的距离$\mu_i$代表类$C_j$的样本中心。基于以上定义如下内部指标：

• DB指数（简称DBI）

$$\begin{align} DBI=\frac{1}{k}\sum_{i=1}^k\max_{j\ne i}\bigl(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)}\bigl) \end{align}$$

• Dunn指数（简称DI）

$$\begin{align} DI=\min_{i\le i\le k} \Bigl\{ \min_{j \ne i}\frac{d_{min}(C_i,C_j)}{\max_{1 \le l \le l}diam(C_l)} \Bigl\} \end{align}$$

显然，DBI的值越小越好，而DI值越大越好。

2. 距离度量

　　样本空间中两个点之间的距离度量表示的是两个样本点之间的相似程度：距离越短，表示相似程度越高；相反，距离越大，表示两个样本的相似程度低。
　　
　　常用的距离度量方式有：1）闵可夫斯基距离；2）欧氏距离；3）曼哈顿距离；4）切比雪夫距离；5）余弦距离。

2.1 闵可夫斯基距离

　　闵可夫斯基距离不是一种距离，而是一类距离的定义。对于n维空间中的两个点 $x(x_1,x_2,...,x_n)$ 和 $y(y_1,y_2,...,y_n)$ ，那么$x$ 和 $y$两点之间的闵可夫斯基距离为：

$$\begin{align}d_{xy}=\sqrt[p]{\sum_{k=1}^n(x_k-y_k)^p} \end{align}$$

其中p是一个可变参数：
- 当p=1时，被称为曼哈顿距离；
- 当p=2时，被称为欧氏距离；
- 当p=$\infty$时，被称为切比雪夫距离。

2.2 欧氏距离

　　由以上说明可知，欧式距离的计算公式为：

$$\begin{align} d_{xy}=\sqrt{\sum_{k=1}^n(x_k-y_k)^2} \end{align}$$

欧式距离（L2范数）是最易于理解的一种距离计算方法，源自欧式空间中两点间的距离公式，也是最常用的距离度量方式。

2.3 曼哈顿距离

　　由闵可夫斯基距离定义可知，曼哈顿距离的计算公式为：

$$\begin{align} d_{xy}=\sum_{k=1}^n|x_k-y_k| \end{align}$$

3. K-Means算法

　　对给定的样本集 $D=\{ x_1,x_2,\cdots,x_m\}$，K均值算法根据聚类结果划分 $C=\{C_1,C2,\cdots,C_k\}$ 最小化平方误差

$$\begin{align} MSE=\sum_{i=1}^k\sum_{x \in C_i}||x-u_i||_2^2 \end{align}$$

其中 $u_i=\frac{1}{|C_i|}\sum_{x \in C_i}x$ 是类 $C_i$ 的均值向量。

　　上式刻画了类内样本到类中心点 $u_i$ 的紧密程度，MSE值越小，说明类内样本相似度越高。但是最优化上式的值是一个NP难问题，因为要精确地找到它的最优解需要对样本集D的所有划分的情况进行一一列举。因此，K-Means算法最终采用的是贪心的策略，通过迭代优化的方式来来近似求解最优 $MSE$ 值。算法流程如下：

• 输入： 样本集 $D=\{ x_1,x_2,\cdots,x_m\}$，最终聚类的类别树k；
• 算法流程：
  随机选择k个样本点作为类标中心；
  Repeat
  　　　计算每个样本点到所有类标中心点的距离；
  　　　将所有样本点划分到距离最近的类标中心所在的类标；
  　　　重新计算每个类的类标中心
  Until 样本点类别划分不发生变化或者达到指定的最大迭代次数

图2. K-Means聚类过程示意图（a）~（f）

4. 密度聚类方法

　　基于密度的聚类（Density-Based Clustering）方法主要考虑的是样本分布的紧密程度，这里的紧密程度主要是用样本间的距离来衡量的。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连续性，并基于可连续样本不断地扩展聚类簇以获得最终的聚类结果。接下来我们以典型的基于密度的聚类方法 DBSCAN算法 来进行讲解，帮助大家理解密度聚类算法。
　　
　　DBSCAN是一种著名的密度聚类算法，它基于一组 “邻域”参数（$\epsilon,mps$）来刻画样本分布的紧密程度。对给定样本集$D=\{x_1,x_2,\cdots,x_m\}$,进行如下定义：

• $\epsilon$ 邻域
  对于样本集D中样本点 $x_i$，它的 $\epsilon$ 邻域定义为与$x_i$距离不大于 $\epsilon$ 的样本的集合，即 $N_\epsilon(x_i)=\{x \in D|dist(x,x_i)\le \epsilon \}$；

• 核心对象
  如果样本 $x$ 的 $\epsilon$ 邻域内至少包含 $mps$ 个样本，即 $|N_\epsilon(x_i)| \ge mps$，则称 $x$ 为核心对象；

• 密度直达
  如果 $x_i$ 是一个核心对象，并且 $x_j$ 位于它的 $\epsilon$ 邻域内，那么我们称 $x_j$ 由 $x_i$ 密度直达；

• 密度可达
  对于任意的两个不同的样本点 $x_i$ 与 $x_j$，如果存在这样的样本序列 $p_1,p_2,\cdots,p_n$，其中 $p_1=x_i,p_n=x_j 且 p_{i+1}由p_i$密度直达，则称 $x_i$ 与 $x_j$密度可达；

• 密度相连
  对对于任意的两个不同的样本点 $x_i$ 与 $x_j$，如果存在第三个样本点 $x_k$ 使得 $x_i$ 与 $x_j$ 均由 $x_k$ 密度可达，则称 $x_i$ 与 $x_j$ 密度相连。

图3. DBSCAN算法工作示意图

　　基于以上概念的定义，那么DBSCAN中簇的定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。形式化的定义如下：给定邻域参数（$\epsilon,mps$），簇 $C \subseteq D$ 如下性质的非空样本子集：

• 连接性（Connectivity）
  对任意样本 $x_i \in C$ 与 $x_j \in C$ $\Rightarrow$ $x_i$ 与 $x_j$ 密度相连；

• 最大性（Maximality）
  $x_i \in C$ $x_j$ 由 $x_i$密度可达 $\Rightarrow$ $x_j \in C$。

　　那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子（Seed），然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。算法形式化的描述如下：

输入： 样本集 $D=\{x_1,x_2,\cdots,x_m\}$，邻域参数（$\epsilon,mps$）

输出： 类别划分 $C=\{C_1,C_2,\cdots,C_k\}$

执行步骤：

1. 确定每个样本点$x_i(i=1,2,\cdots,m)$ 的 $\epsilon$ 邻域 $N_\epsilon(x_i)$；
2. 将所有满足条件 $|N_\epsilon(x_i)|\ge mps$ 的样本点标记为核心对象, 并将所有核心对象集合记为 $\Omega$；
3. 分别初始化聚类类别数 $k=0$ 和未访问样本数 $\Gamma=D$
4. $while\quad \Omega \ne \phi \quad do:$
   　　记录当前未访问集合：$\Gamma'=\Gamma$
   　　随机选取一个核心对象 $o\in \Omega$，初始化队列 $Q=<o>$
   　　$\Gamma=\Gamma\setminus\{o\}$
   　　$while \quad Q \ne \phi \quad do:$
   　　　去除队列 $Q$ 的第一个样本 $q$
   　　　$if \ |N_\epsilon(x_i)|\ge mps \ then:$
   　　　　令 $\Delta=N_\epsilon(q)\cap \Gamma$
   　　　　$Q=Q+\Delta$
   　　　　$\Gamma=\Gamma \setminus \Delta$
   　　　$end\ if$
   　　$end\ while$
   　　$k=k+1$，生成类簇 $C_k=\Gamma'\setminus \Gamma$
   　　$\Omega=\Omega \setminus C_k$
   $end\ while$

　　基本上这就是DBSCAN算法的主要内容了，是不是很简单？但是我们还是有三个问题没有考虑。

　　第一个是一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。

　　第二个是距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。如果大家对于最近邻的思想，距离度量，KD树和球树不熟悉，建议参考之前写的另一篇文章K近邻法(KNN)原理小结。

　　第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说BDSCAN的算法不是完全稳定的算法。

5. 层次聚类方法

　　
　　我们知道对于聚类最经典的方法K-Means算法，虽然简单好用，但是始终存在K值选择和初始聚类中心选择的问题需要解决。并且，这些问题对聚类的最终结果将产生至关重要的影响。而本节介绍的层次聚类算法就可以避免这些问题的困扰。
　　
　　层次聚类（Hierarchical Clustering）是聚类算法家族中的重要的成员，他致力于通过合并和分裂构建树状的类簇。对数据的划分主要有两种方式： 自顶向下 的分裂和 自底向上 的聚合。每棵树的根是一个聚集所有样本的独有的类。
　　
　　$AGNES$ 是一种采用自底向上聚合策略的层次聚类算法。他先将数据集中的每个样本看成是一个初始的聚类簇，然后在算法运行的每一步中找出距离最近的两个簇进行合并。该过程不断重复，直至达到预设的聚类簇的个数。因此，这里的关键又是如何计算两个聚类簇之间的距离。
　　
　　众所周知，对于两个点之间的距离我们按照相应的距离公式直接计算两个点之间的距离即可。但是对于两个包含很多点的聚类簇，想计算他们之间的距离就并不是那么简单了。为此，人们定义了如下几种关于两个聚类簇 $C_i$ 和 $C_j$ 的不同距离度量及其计算方式：

$$\begin{align} d_{min}(C_i,C_j) &= \min_{x_i\in C_i\ ,\ x_j\in C_j} dist(x_i,x_j) \\ d_{max}(C_i,C_j) &= \max_{x_i\in C_i\ ,\ x_j\in C_j} dist(x_i,x_j) \\ d_{avg}(C_i,C_j) &= \frac{1}{|C_i||C_j|}\sum_{x_i\in C_i}\sum_{x_j\in C_j}dist(x_i,x_j) \\ d_{avg}'(C_i,C_j) &= dist(\hat x_i,\hat x_j),\quad \hat x_i=\frac{1}{|C_i|}\sum_{k=1}^{|C_i|} x_k,\hat x_j=\frac{1}{|C_j|}\sum_{k=1}^{|C_j|} x_k \end{align}$$

具体采用哪种距离取决于具体的业务，一般情况下为了防止噪声点的影响，建议采用后两种距离度量。

AGNES聚类算法的形式化描述如下：

算法输入： 训练集 $D = \{x_1,x_2,\cdots,x_m\}$,
　　　　　 类簇距离度量公式：$d(C_i,C_j)$
　　　　　 局类簇数目：$k$
算法输出： 聚类结果划分: $C=\{C_1,C_2,\cdots,C_k\}$

详细步骤：

$\qquad for\ i=1,2,\cdots,m:$
$\qquad \qquad C_i = \{x_i\}$
$\qquad end\ for$

$\qquad for\ i=1,2,\cdots,m:$
$\qquad \quad for\ j=i,i+1,\cdots,m:$
$\qquad \qquad D(i,j)=d(C_i, C_j)$
$\qquad \qquad D(j,i)=D(i,j)$
$\qquad \quad end\ for$
$\qquad end\ for$

$\qquad //初始化当前聚类簇数目$
$\qquad K=m \quad$

$\qquad while \ K>k:$
$\qquad \quad find\ nearest\ class \ C_{x} \ C_{y}$
$\qquad \quad C_x=C_x \cap C_y \quad // merge\ into\ C_x$

$\qquad \quad for\ i=y+1,y+2,\cdots,K :$
$\qquad \qquad C_{i-1} = C_{i}$
$\qquad \quad end\ for$

$\qquad \quad delete\ row\ y\ and\ col\ y\ in\ D$

$\qquad \quad for\ j=1,2,\dots,K-1:$
$\qquad \qquad D(x,j)=d(C_x,C_j)$
$\qquad \quad end\ for$

$\qquad \quad K=K-1$
$\qquad end\ while$

6. 聚类算法应用与实战

6.1 聚类算法的应用

　　在互联网领域，尤其是电商、金融公司等涉及金融最明显的领域，网络欺诈行为非常猖獗。为此，”异常检测”成为这些公司十分重要的任务。国内外著名的欺诈检测公司“同盾科技”、“DataVisor” 在该领域做得都非常好。
　　
　　笔者曾经就职于国内一家大型电商公司的安全部门，负责恶意订单检测任务，这时候其实我们有多种可行的方案：1）规则引擎；2）有监督学习；3）无监督学习。接下来我分别介绍一下以上各种方案在欺诈检测领域的优缺点：

• 规则引擎

  规则引擎是一种将一系列规则方法按照不同的优先级并行或者串行的方式集成在一个系统中。对于任意输入的行为数据都需要经过规则引擎的过滤，将命中规则引擎中任意规则的行为数据报警并拦截过滤。

  优点： 规则引擎的优点是配置简单灵活，检测结果直观可解释，规则修改简单；

  缺点： 规则引擎的缺点主要是固定死板容易被绕过，规则的发现需要运营人员投入大量的时间和精力进行长时间大数据量的分析和业务判断导致成本过高，并且很难应对欺诈用户的行为变化；

• 有监督学习

  有监督学习的方式应用于异常检测主要是利用运营人员标记的正常与异常订单样本，然后将订单相关数据（如IP，设备指纹，操作系统等信息）进行特征向量化，然后使用有监督学习进行二分类（正常与异常）学习。

  优点： 模型构建简单，训练成本低，模型检测结果准确高效；

  缺点： 样本标记成本大，负样本(异常样本)不全面导致模型检测异常的漏检率很高，也就是说算法检测的负样本召回率非常低；

• 无监督学习

  无监督学习的方式应用于欺诈检测在特征抽取上是一致的。但是，它无需人工进行样本标记，省去了大量的劳动力。并且，由于训练时是全量数据进行训练，因此可以适应任意的欺诈手段的变化。

  优点：模型构建简单，无需人工进行样本标记节省大量人力投入，能够自动适应欺诈手段的变化而无需修改模型；

  缺点：训练数据集大，计算成本高；

6.2 聚类算法实战

　　本节以聚类算法在欺诈检测为例，介绍无监督学习方法的实战案例的讲解。但是由于数据保密等原因，不能使用真实数据。为此，我们使用人为制造的正负样本进行检测。
　　
　　首先，为了展示方便，我们使用二维特征作为样本。首先随机产生1000个正样本，然后产生100个负样本。在真实场景中，一般正样本分布比较均匀集中，而负样本一般情况下远离正样本。源程序如下：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
x = np.random.normal(0, 2, 1000)
y = np.random.normal(0, 2, 1000)
x1 = np.random.normal(10, 1, 100)
y1 = np.random.normal(10, 1, 100)
x = np.append(x, x1)
y = np.append(y, y1)
x = np.append(x, y)
X = x.reshape(1100, 2)
plt.figure(figsize=(10, 4))
plt.subplot(121)
plt.scatter(X[:, 0], X[:, 1], s=5)
y_pred = KMeans(n_clusters=2, random_state=170).fit_predict(X)
plt.subplot(122)
plt.scatter(X[:, 0], X[:, 1], s=5, c=y_pred)
plt.show()

运行结果：

图4. KMeans异常检测示意图（黄色为离群异常点）

　　本节只是使用KMeans对简单的分布的异常点进行检测，本文的目的只是告诉读者聚类算法的应用以及sklearn中KMeans接口的简单调用。更加专业的异常检测算法请看下一章的 IForest 算法。

---

参考文献

[1] Friedman J, Hastie T, Tibshirani R. The elements of statistical learning[M]. New York: Springer series in statistics, 2001.

[2] 周志华. 机器学习 : = Machine learning[M]. 清华大学出版社, 2016.