聚类

在无监督学习（unsupervised learning）中，训练样本的标记信息是未知的，学习的目的是揭示数据的内在性质及规律，为进一步的数据分析提供基础。这类学习任务中研究最多，应用最广的是聚类（clustering）。

这一章的内容大致如下：

  • 聚类任务：聚类过程是怎样的？聚类有什么用途？聚类的两个基本问题是什么？

  • 性能度量：聚类的目标是什么？聚类性能度量的两大类指什么？各包含哪些度量指标？

  • 距离计算：距离度量需要满足哪些基本性质？怎样度量有序属性？怎样度量无序属性？相似度度量和距离度量有什么区别？

  • 原型聚类：什么是原型聚类？k均值算法是怎样的？学习向量量化算法是怎样的？高斯混合聚类是怎样的？

  • 密度聚类：什么是密度聚类？DBSCAN算法是怎样的？

  • 层次聚类：什么是层次聚类？AGNES算法是怎样的？

聚类任务

聚类（clustering）

定义

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个簇（cluster）。通常来说每个簇可能对应一些特征，比方说音乐可以聚类成古典音乐、摇滚乐、流行乐等等。但聚类过程仅产生簇结构，簇对应的概念语义需要使用者来定义。

简单来说，聚类可以分为两种用途：

  • 作为一个单独过程，用于寻找数据内在的分布结构；
  • 作为其他学习任务的前驱过程，比方说根据聚类结果定义类标记，然后再进行分类学习；

聚类算法的两大基本问题是性能度量和距离计算。

数学定义

参数设定：

假定样本集 D={x1,x2,...,xm}D=\{ \boldsymbol{x}_1,\boldsymbol{x}_2,...,\boldsymbol{x}_m \} 包含 mm 个无标记样本，每个样本 xi={xi1,xi2,...,xin}\boldsymbol{x}_i=\{ x_{i1},x_{i2},...,x_{in} \} 是一个 nn 维特征向量，聚类算法将样本集划分为 kk 个不相交的簇 {Cl∣l=1,2,...,k}\{ C_l|l=1,2,...,k \} ，用 λj∈{1,2,...,k}\lambda_j \in \{ 1,2,...,k \} 表示样本 xj\boldsymbol{x}_j 的“簇标记”。

则存在以下公式

  • 簇不相交：Cl′∩l′≠lCl=∅C_{l'}\cap_{l' \neq l}C_l = \varnothing
  • 并集为样本集：D=∪l=1kClD=\cup_{l=1}^kC_l
  • 聚类结果：λ=(λ1;λ2;...;λm)\boldsymbol{\lambda} = (\lambda_1;\lambda_2;...;\lambda_m)

聚类和分类的区别

  • 聚类(Clustering)：是指把相似的数据划分到一起，具体划分的时候并不关心这一类的标签，目标就是把相似的数据聚合到一起，聚类是一种无监督学习(Unsupervised Learning)方法。
  • 分类(Classification)：是把不同的数据划分开，其过程是通过训练数据集获得一个分类器，再通过分类器去预测未知数据，分类是一种监督学习(Supervised Learning)方法。

 

性能度量（讲的相当简略）

性能度量亦称聚类“有效性指标”（validity index）

主要用途

  • 对聚类的结果的好坏进行评估
  • 作为聚类过程的优化目标

“物以类聚”

两个方向进行衡量：簇内相似度（intra-cluster similarity）高 和 簇间相似度（inter-cluster similarity）低

度量方式

外部指标（external index）

将聚类结果于某个“参考模型”（reference model）进行比较

参数定义

数据集 D={x1,x2,...,xm}D=\{ \boldsymbol{x}_1,\boldsymbol{x}_2,...,\boldsymbol{x}_m \} ，聚类的划分结果为 C={C1,C2,...,Ck}\mathcal{C}=\{ C_1, C_2,...,C_k \}，参考模型划分结果为 C∗={C1∗,C2∗,...,Cs∗}\mathcal{C}^* = \{ C_1^*,C_2^*,...,C_s^* \} ，λ\boldsymbol{\lambda} 和λ∗\boldsymbol{\lambda}^* 分别表示聚类和参考模型的簇标记向量。

度量定义：

  • a=∣SS∣,SS={(xi,xj)∣λi=λj,λi∗=λj∗,i<j}a = |SS|, \quad SS = \{ (\boldsymbol{x}_i,\boldsymbol{x}_j)|\lambda_i = \lambda_j, \quad \lambda_i^* = \lambda_j^*, \quad i < j \}

    表示两两样本在聚类结果和参考模型中都属于相同的簇

  • b=∣SD∣,SD={(xi,xj)∣λi=λj,λi∗≠λj∗,i<j}b=|SD|, \quad SD = \{ (\boldsymbol{x}_i,\boldsymbol{x}_j) | \lambda_i = \lambda_j, \quad \lambda_i^* \neq \lambda_j^*, \quad i < j \}

    表示样本对中在聚类结果中属于相同簇但在参考模型中不属于相同的簇

  • c=∣DS∣,DS={(xi,xj)∣λi≠λj,λi∗=λj∗,i<j}c=|DS|, \quad DS = \{ (\boldsymbol{x}_i,\boldsymbol{x}_j) | \lambda_i \neq \lambda_j, \quad \lambda_i^* = \lambda_j^*, \quad i < j \}

    表示样本对中在聚类结果中不属于相同簇但在参考模型中属于相同簇

  • d=∣DD∣,DD={(xi,xj)∣λi≠λj,λi∗≠λj∗,i<j}d = |DD|, \quad DD = \{ (\boldsymbol{x}_i,\boldsymbol{x}_j) | \lambda_i \neq \lambda_j, \quad \lambda_i^* \neq \lambda_j^*, \quad i < j \}

    表示两两样本在聚类结果和参考模型中都不属于相同的簇

常见的聚类性能度量外部指标

Jaccard 系数（Jaccard Coefficient，简称JC）：

JC=aa+b+cJC=\frac{a}{a+b+c}

FM 指数（Fowlkes and Mallows Index，简称FMI）：

FMI=aa+b⋅aa+c\text{FMI}=\sqrt{\frac{a}{a + b} · \frac{a}{a + c}}

Rand 指数（Rand Index，简称RI）：

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

这些值得结果值在 [0,1][0, 1] 之间，越大越好

内部指标（internal index）

直接考察聚类结果而不利用任何参考模型

参数定义

聚类的划分结果为 C={C1,C2,...,Ck}\mathcal{C} = \{ C_1, C_2,...,C_k \} ，簇 CiC_i 的中心点 μi=1∣Ci∣∑1≤k≤∣C∣xik\boldsymbol{\mu}_i = \frac{1}{|C_i|}\sum_{1 \le k \le |C|} \boldsymbol{x}_{i_k}

度量定义:

  • avg(C)=2∣C∣(∣C∣−1)∑1≤i<j≤∣C∣dist(xi,xj)\text{avg}(C) = \frac{2}{|C|(|C| - 1)} \sum_{1 \le i < j \le |C|} \text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j)

    对应于簇内样本间的平均距离

  • diam(C)=max⁡1≤i<j≤∣C∣dist(xi,xj)\text{diam}(C) = \max_{1 \le i < j \le |C|} \text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j)

    簇内样本间的最远距离

  • dmin⁡(Ci,Cj)=min⁡xi∈Ci,xj∈Cjdist(xi,xj)d_{\min}(C_i,C_j) = \min_{\boldsymbol{x}_i \in C_i, \boldsymbol{x}_j \in C_j} \text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j)

    簇间最近样本的间距

  • dcen(Ci,Cj)=dist(μi,μj)d_{\text{cen}}(C_i,C_j) = \text{dist}(\boldsymbol{\mu}_i, \boldsymbol{\mu}_j)

    簇间中心点的间距

常用的聚类性能度量内部指标

DB 指数（Davies-Bouldin Index，简称DBI）：

DBI=1k∑i=1kmax⁡j≠i(avg(Ci)+avg(Cj)dcen(Ci,Cj))DBI = \frac{1}{k}\sum_{i=1}^k\max_{j \neq i}\left( \frac{\text{avg}(C_i) + \text{avg}(C_j)}{d_{\text{cen}}(C_i, C_j)} \right)

这里是值越小越好

Dunn 指数（Dunn Index，简称DI）：

DI=min⁡1≤i≤kmin⁡j≠i(dmin⁡(Ci,Cj)max⁡1≤l≤kdiam(Cl))DI = \min_{1 \le i \le k} \\{ \min_{j \neq i} \left( \frac{d_{\min}(C_i, C_j)}{\max_{1 \le l \le k} \text{diam}(C_l)} \right) \\}

这里是值越大越好

 

距离度量

讲过，其实

距离函数 dist(⋅,⋅)\text{dist}(·,·)

定义：它是一个距离度量（distance measure）

基本性质

  • 非负性：dist(xi,xj)≥0\text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) \ge 0
  • 同一性：dist(xi,xj)=0\text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) = 0 当且仅当 xi=xj\boldsymbol{x}_i = \boldsymbol{x}_j
  • 对称性：dist(xi,xj)=dist(xj,xi)\text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) = \text{dist}(\boldsymbol{x}_j, \boldsymbol{x}_i)
  • 直递性：dist(xi,xj)≤dist(xi,xk)+dist(xk,xj)\text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) \le \text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_k) + \text{dist}(\boldsymbol{x}_k,\boldsymbol{x}_j)

这些性质也可以用来检测一个函数是否可以用来作为距离度量函数

  • 通常基于某种形式的距离来定义“相似度度量”（similarity measure），距离越大，相似度越小
  • 但是一定条件下可以不满足所有的基本性质，尤其是直递性
    • 在一些特殊情况下可以使三角结构中不相似的距离边达到一定程度的大小突破直递性的性质
    • 这种距离成为“非度量距离”（non-metric disttance）
  • 此外也可以基于数据样本来确定合适的距离计算公式——距离度量学习（distance metric learning）

属性划分

  • 连续属性（continuous attribute）
  • 离散属性（categorical attribute）
    • 有序属性（ordinal attribute）
    • 无序属性（non-ordinal attribute）

闵可夫斯基距离（Minkowski distance）

公式定义：

distmk(xi,xj)=(∑u=1n∣xiu−xju∣p)1p\text{dist}_{mk}(\boldsymbol{x}_i,\boldsymbol{x}_j) = \left( \sum_{u=1}^n |x_{iu} - x_{ju}|^p \right)^{\frac{1}{p}}

也称为 xi−xj\boldsymbol{x}_i - \boldsymbol{x}_j 的 Lp\text{L}_p 范数 ∥xi−xj∥p{\Vert \boldsymbol{x}_i - \boldsymbol{x}_j \Vert}_p

常见变形：

  • 曼哈顿距离（Manhattan distance）—— L1\text{L}_1 范数：

    disted(xi,xj)=∥xi−xj∥2=∑u=1n∣xiu−xju∣2\text{dist}_{ed}(\boldsymbol{x}_i, \boldsymbol{x}_j) = {\Vert \boldsymbol{x}_i - \boldsymbol{x}_j \Vert}_2 = \sqrt{\sum_{u=1}^n{|x_{iu} - x_{ju}|}^2}

  • 欧氏距离（Euclidean distance） —— L2\text{L}_2 范数：

    distman(xi,xj)=∥xi−xj∥1=∑u=1n∣xiu−xju∣\text{dist}_{man}(\boldsymbol{x}_i, \boldsymbol{x}_j) = {\Vert \boldsymbol{x}_i - \boldsymbol{x}_j \Vert}_1 = \sum_{u=1}^n{|x_{iu} - x_{ju}|}

  • 切比雪夫距离（Chebyshev distance）—— L∞\text{L}_{\infty} 范数：

    distche=∥xi−xj∥∞=max⁡u=1n(∣xiu−xju∣)\text{dist}_{che} = {\Vert \boldsymbol{x}_i - \boldsymbol{x}_j \Vert}_{\infty} = \max_{u=1}^n{(|x_{iu} - x_{ju}|)}

适用有序属性，当属性重要性不同时，可适用”加权距离“（weighted distance）

VDM（Value Difference Metric）

公式定义：

VDM_p(a,b)=∑i=1k∣mu,a,imu,a−mu,b,imu,b∣p\text{VDM}\_p(a,b) = \sum_{i=1}^k {\left| \frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}} \right|}^p

参数说明：

  • mu,am_{u,a} 表示在属性 uu 上取值为 aa 的样本数
  • mu,a,im_{u,a,i} 表示在第 ii 个样本簇中在属性 uu 上取值为 aa 的样本数
  • kk 为样本簇数

适用无序属性，当属性重要性不同时，可适用”加权距离“（weighted distance）

将两者结合到一起

MinkovDM_p(x_i,x_j)=(∑u=1nc∣xiu−xju∣p+∑u=nc+1nVDMp(xiu,xju))1p\text{MinkovDM}\_p(\boldsymbol{x}\_i,\boldsymbol{x}\_j) = \left( \sum_{u=1}^{n_{c}} |x_{iu} - x_{ju}|^p + \sum_{u = n_c + 1}^n \text{VDM}_p(x_{iu}, x_{ju}) \right)^{\frac{1}{p}}

 

原型聚类

很自然的一个问题：什么是原型聚类？

定义：“原型”（prototype）是指样本空间中具有代表性的点

以 西瓜数据集4.0 为例子书中介绍了三种原型聚类算法：kk-均值算法（k-means）、学习向量化（LVQ）和 高斯混合聚类（GMM）。

kk-均值算法

K-means 是我们最常用的基于欧式距离的聚类算法，其认为两个目标的距离越近，相似度越大。

牧师-村民模型

K-means 有一个著名的解释：牧师—村民模型：

有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的村民，于是每个村民到离自己家最近的布道点去听课。
听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的村民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。
牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个村民又去了离自己最近的布道点……
就这样，牧师每个礼拜更新自己的位置，村民根据自己的情况选择布道点，最终稳定了下来。

我们可以看到该牧师的目的是为了让每个村民到其最近中心点的距离和最小。

算法定义

给定样本集 D={x1，x2,...,xm}D = \{\boldsymbol{x}_1，\boldsymbol{x}_2, ..., \boldsymbol{x}_m \}，“kk - 均值” （k-means）算法针对聚类所得簇划分 C={C1,C2,...,Ck}C = \{C_1, C_2,..., C_k \} 最小化平方误差

E=∑i=1k∑x∈Ci∥x−μi∥22E = \sum_{i=1}^k\sum_{\boldsymbol{x} \in C_i} \Vert \boldsymbol{x} - \boldsymbol{\mu}_i \Vert_2^2

其中 μi=1∣Ci∣∑x∈Cix\boldsymbol{\mu}_i = \frac{1}{|C_i|} \sum_{\boldsymbol{x} \in C_i} \boldsymbol{x} 是簇 CiC_i 的均值向量。

最小化上式并不容易，找到它的最优解需考察样本集 DD 所有可能的簇划分，这是一个 NP 难问题[Aloise et al., 2009]。

K-means 的算法步骤为：

  1. 选择初始化的 k 个样本作为初始聚类中心 a=a1,a2,…aka={a_1,a_2,…a_k} ；
  2. 针对数据集中每个样本 xix_i 计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
  3. 针对每个类别 aja_j ，重新计算它的聚类中心 aj=1∣ci∣∑x∈cixa_j=\frac{1}{\left| c_i \right|}\sum_{x\in c_i}x （即属于该类的所有样本的质心）；
  4. 重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

算法描述

经典k-means源代码，下左图是原始数据集，通过观察发现大致可以分为 4 类，所以取 k=4k=4，测试数据效果如下右图所示。

看起来很顺利，但事情并非如此，我们考虑k-means算法中最核心的部分，假设 xi(i=1,2,…,n)x_i(i=1,2,…,n) 是数据点，μj(j=1,2,…,k)\mu_j(j=1,2,…,k) 是初始化的数据中心，那么我们的目标函数可以写成

min⁡∑i=1nmin⁡j=1,2,...,k∣∣xi−μj∣∣2\min\sum_{i=1}^{n} \min \limits_{j=1,2,...,k}\left |\left | x_i -\mu_j\right | \right |^2

这个函数是非凸优化函数，会收敛于局部最优解，可以参考证明过程。举个 ，μ1=[1,1],μ2=[−1,−1]\mu_1=\left [ 1,1\right ] ,\mu_2=\left [ -1,-1\right ] ，则

z=min⁡j=1,2∣∣xi−μj∣∣2z=\min \limits_{j=1,2}\left |\left | x_i -\mu_j\right | \right |^2

该函数的曲线如下图所示

可以发现该函数有两个局部最优点，当初始质心点取值不同的时候，最终的聚类效果也不一样，接下来我们看一个具体的实例。

在这个例子当中，下方的数据应该归为一类，而上方的数据应该归为两类，这是由于初始质心点选取的不合理造成的误分。而 kk 值的选取对结果的影响也非常大，同样取上图中数据集，取 k=2,3,4k=2,3,4，可以得到下面的聚类结果：

优点

  • 容易理解，聚类效果不错，虽然是局部最优， 但往往局部最优就够了；
  • 处理大数据集的时候，该算法可以保证较好的伸缩性；
  • 当簇近似高斯分布的时候，效果非常不错；
  • 算法复杂度低。

缺点

  • K 值需要人为设定，不同 K 值得到的结果不一样；
  • 对初始的簇中心敏感，不同选取方式会得到不同结果；
  • 对异常值敏感；
  • 样本只能归为一类，不适合多分类任务；
  • 不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类。

调优

针对 K-means 算法的缺点，我们可以有很多种调优方式：如数据预处理（去除异常点），合理选择 K 值，高维映射等。

数据预处理

K-means 的本质是基于欧式距离的数据划分算法，均值和方差大的维度将对数据的聚类产生决定性影响。所以未做归一化处理和统一单位的数据是无法直接参与运算和比较的。常见的数据预处理方式有：数据归一化，数据标准化。

此外，离群点或者噪声数据会对均值产生较大的影响，导致中心偏移，因此我们还需要对数据进行异常点检测。

合理选择 K 值

K 值的选取对 K-means 影响很大，这也是 K-means 最大的缺点，常见的选取 K 值的方法有：手肘法、Gap statistic 方法。

手肘法：

当 K <3 时，曲线急速下降；当 K> 3 时，曲线趋于平稳，通过手肘法我们认为拐点 3 为 K 的最佳值。

手肘法的缺点在于需要人工看不够自动化，所以我们又有了 Gap statistic 方法，这个方法出自斯坦福大学的几个学者的论文：Estimating the number of clusters in a data set via the gap statistic

Gap(K)=E(log⁡Dk)−log⁡DkGap(K)=\text{E}(\log D_k)-\log D_k

其中 DkD_k 为损失函数，这里 E(logDk)E(logD_k) 指的是 logDklogD_k 的期望。这个数值通常通过蒙特卡洛模拟产生，我们在样本里所在的区域中按照均匀分布随机产生和原始样本数一样多的随机样本，并对这个随机样本做 K-Means，从而得到一个 DkD_k 。如此往复多次，通常 20 次，我们可以得到 20 个 logDklogD_k 。对这 20 个数值求平均值，就得到了 E(logDk)E(logD_k) ​ 的近似值。最终可以计算 Gap Statisitc。而 Gap statistic 取得最大值所对应的 K 就是最佳的 K。

由图可见，当 K=3 时，Gap(K) 取值最大，所以最佳的簇数是 K=3。

Github 上一个项目叫 gap_statistic ，可以更方便的获取建议的类簇个数。

采用核函数

基于欧式距离的 K-means 假设了了各个数据簇的数据具有一样的的先验概率并呈现球形分布，但这种分布在实际生活中并不常见。面对非凸的数据分布形状时我们可以引入核函数来优化，这时算法又称为核 K-means 算法，是核聚类方法的一种。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

训练结果

PS：kk - 均值算法应该算是聚类算法中特别好理解和掌握的一种了，因此书上也没有详细的介绍其内容。

学习向量量化（Learning Vector Quantization，简称LVQ）（没讲）

学习向量量化（Learning vector quantization，LVQ）是一种有监督学习的分类算法，可以用于多类别分类问题。它将输入数据映射到一个离散的输出空间中，并利用欧几里德距离或余弦相似度等度量方法来计算样本向量和类中心之间的距离，并根据距离分配分类标签。

在 LVQ 算法中，在训练过程中会生成若干个代表性向量作为分类中心，这些代表性向量通常被称为原型向量（prototype），每个原型向量所代表的类别即是它所属的类别。 在训练集上，LVQ 通过对每个实例的特征向量与原型进行比较，逐渐调整每个原型的位置，最终得到了一组使得分类误差达到最小的原型向量。

在预测新数据时，可以使用与训练相同的度量来计算新数据向量和每个原型向量之间的距离，将其归类于距离最近的原型向量所代表的类别。

与其他分类算法相比，LVQ具有简单且易于解释的模型、快速训练和局部更新等优点。然而，需要手动设置原型数量、节选合适的训练集等超参数，容易受到“噪声”数据的影响等问题。因此，在实际使用时需要根据具体场景选择合适的参数和优化策略来提高算法性能。

学习向量量化算法（或简称LVQ）是一种人工神经网络算法，允许选择要挂起的训练实例数量，并准确了解这些实例应该是什么样子。

算法定义

同样是试图找到一组原型向量来刻画聚类结构，不同的是 LVQ 假设数据样本带有类别标记，学习过程中利用样本的这些监督信息来辅助聚类。

给定样本集 D={(x1,y1),(x2,y2),...,(xm,ym)}D=\{ (\boldsymbol{x}_1,y_1), (\boldsymbol{x}_2,y_2),...,(\boldsymbol{x}_m,y_m) \}，yj∈Yy_j \in \mathcal{Y} 是样本 xj\boldsymbol{x}_j 的类别标记，LVQ 目标是学得一组 nn 维原型向量 {p1,p2,...,pq}\{ \boldsymbol{p}_1, \boldsymbol{p}_2, ..., \boldsymbol{p}_q \}，

每个原型向量代表一个聚类簇，簇标记 ti∈Yt_i \in \mathcal{Y}。

引发一个问题：向量是如何划分空间的？

对任意样本，它将被划入与其距离最近的原型向量所代表的的簇中。

每个原型向量 pi\boldsymbol{p}_i 定义了一个与之相关的一个区域 RiR_i ，该区域中每个样本与 pi\boldsymbol{p}_i 的距离不大于它与其他原型向量之间的距离

Ri={x∈X∣∥x−pi∥2≤∥x−pi′∥2,i′≠i}R_i = \{ \boldsymbol{x} \in \mathcal{X} | {\Vert \boldsymbol{x} - \boldsymbol{p}_i \Vert}_2 \le {\Vert \boldsymbol{x} - \boldsymbol{p}_{i'} \Vert}_2, i' \neq i \}

即完成了对样本空间 X\mathcal{X} 的簇划分 {R1,R2,...,Rq}\{R_1,R_2,...,R_q \}

该划分通常称为“Voronoi剖分”（Voronoi tessellation）

算法描述

其中第七行和第九行都是源自 p′\boldsymbol{p}' 与 xj\boldsymbol{x}_j 之间的距离推导 ∥p′−xj∥2{\Vert \boldsymbol{p}' - \boldsymbol{x}_j \Vert}_2

  • 当类别标记相同时

    p′=pi∗+η⋅(xj−pi∗)\boldsymbol{p}' = \boldsymbol{p}_{i^*} + \eta ·(\boldsymbol{x}_j - \boldsymbol{p}_{i^*})

    ∥p′−xj∥2=∥pi∗+η⋅(xj−pi∗)−xj∥2=(1−η)⋅∥pi∗−xj∥2{\Vert \boldsymbol{p}' - \boldsymbol{x}_j \Vert}_2 = {\Vert \boldsymbol{p}_{i^*} + \eta ·(\boldsymbol{x}_j - \boldsymbol{p}_{i^*}) - \boldsymbol{x}_j \Vert}_2 = (1 - \eta)·{\Vert \boldsymbol{p}_{i^*} - \boldsymbol{x}_j \Vert}_2

  • 当类别标记不同时

    p′=pi∗−η⋅(xj−pi∗)\boldsymbol{p}' = \boldsymbol{p}_{i^*} - \eta ·(\boldsymbol{x}_j - \boldsymbol{p}_{i^*})

    ∥p′−xj∥2=∥pi∗−η⋅(xj−pi∗)−xj∥2=(1+η)⋅∥pi∗−xj∥2{\Vert \boldsymbol{p}' - \boldsymbol{x}_j \Vert}_2 = {\Vert \boldsymbol{p}_{i^*} - \eta ·(\boldsymbol{x}_j - \boldsymbol{p}_{i^*}) - \boldsymbol{x}_j \Vert}_2 = (1 + \eta)·{\Vert \boldsymbol{p}_{i^*} - \boldsymbol{x}_j \Vert}_2

最终学得一组原型向量 {p1,p2,...,pq}\{ \boldsymbol{p}_1, \boldsymbol{p}_2,...,\boldsymbol{p}_q \} 后，即可实现对样本空间 X\mathcal{X} 的簇划分。

训练结果

学习目的是找到5个原型向量 p1,p2,p3,p4,p5\boldsymbol{p}_1,\boldsymbol{p}_2,\boldsymbol{p}_3,\boldsymbol{p}_4,\boldsymbol{p}_5

其分别对应的类别标记假定为 c1,c2,c2,c1,c1c_1, c_2, c_2, c_1, c_1，其中 c1c_1 为好瓜， c2c_2 为坏瓜

高斯混合聚类

高斯混合模型（GMM）可以看做是k-means模型的一个优化。它既是一种工业界常用的技术手段，也是一种生成式模型。高斯混合模型试图找到多维高斯模型概率分布的混合表示，从而拟合出任意形状的数据分布。

高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型

  • 高斯混合聚类是采用概率模型对原型进行刻画
  • 簇划分则由原型对应后验概率确定

多元高斯分布的定义

  • μ\boldsymbol{\mu} 是 nn 维均值向量
  • Σ\boldsymbol{\Sigma} 是 n×nn \times n 的协方差矩阵

多元高斯高斯分布由这两个参数确定

概率密度记为：p(x∣μ,Σ)p(\boldsymbol{x}|\boldsymbol{\mu}, \boldsymbol{\Sigma})

为了凸显相应参数的依赖关系

高斯混合分布

pM=∑i=1kαi⋅p(x∣μi,Σi)p_{\mathcal{M}} = \sum_{i=1}^k \alpha_i · p(\boldsymbol{x}|\boldsymbol{\mu}_i,\boldsymbol{\Sigma}_i)

参数说明

  • 该分布由 kk 个混合成分组成，每个成分对应一个高斯分布
  • μi\boldsymbol{\mu}_i 与 Σi\boldsymbol{\Sigma}_i 是第 ii 个高斯混合成分的参数
  • αi>0\alpha_i > 0 为相应的“混合系数” （mixture coefficient）， ∑i=1kαi=1\sum_{i=1}^k \alpha_i = 1

算法过程

训练集生成方式

首先，根据 α1,α2,...,αk\alpha_1,\alpha_2,...,\alpha_k 定义的先验分布选择高斯混合成分，其中 αi\alpha_i 为选择第 ii 个混合成分的概率，然后，根据被选择的混合成分的概率密度函数进行采样，从而生成相应的样本。

高斯混合成分生成的后验概率确定

令随机变量 zj∈{1,2,...,k}z_j \in \{ 1,2,...,k \} 表示生成样本 xj\boldsymbol{x}_j 的高斯混合成分，其取值未知，显然，zjz_j 的先验概率 P(zj=i)P(z_j=i) 对应于 αi(i=1,2,...,k)\alpha_i(i=1,2,...,k)，根据贝叶斯定理，zjz_j 的后验概率分布对应于

pM(zj=i∣xj)=P(zj=i)⋅pM(xj∣zj=i)pM(xj)=αi⋅p(xi∣μi,Σi)∑l=1kαl⋅p(xj∣μl,Σl)p_{\mathcal{M}}(z_j=i|\boldsymbol{x}_j) = \frac{P(z_j=i)·p_{\mathcal{M}}(\boldsymbol{x}_j|z_j=i)}{p_{\mathcal{M}}(\boldsymbol{x}_j)} = \frac{\alpha_i·p(\boldsymbol{x}_i|\boldsymbol{\mu}_i,\boldsymbol{\Sigma}_i)}{\sum_{l=1}^k\alpha_l·p(\boldsymbol{x}_j|\boldsymbol{\mu}_l,\boldsymbol{\Sigma}_l)}

记为 γji(i=1,2,...,k)\gamma_{ji}(i=1,2,...,k)

簇标记确定

当高斯混合分布已知时，高斯混合聚类将把样本集 DD 划分为 kk 个簇 C={C1,C2,...,Ck}\mathcal{C}=\{ C_1,C_2,...,C_k \}

每个样本 xj\boldsymbol{x}_j 的簇标记 λj\lambda_j 如下确定 λj=arg⁡max⁡i∈{1,2,...,k}γji\lambda_j = \underset{i \in \{1,2,...,k \}}{\arg\max} \gamma_{ji}

参数求解

给定样本集 DD，可采用极大似然估计，即最大化（对数）似然

LL(D)=ln⁡(∏j=1mpM(xj))=∑j=1mln⁡(∑i=1kαi⋅p(xj∣μi,Σi))LL(D) = \ln\left( \prod_{j=1}^m p_{\mathcal{M}}(\boldsymbol{x}_j) \right) = \sum_{j=1}^m \ln \left( \sum_{i=1}^k\alpha_i · p(\boldsymbol{x}_j|\boldsymbol{\mu}_i,\boldsymbol{\Sigma}_i) \right)

EM算法求解:

  • 根据当前参数来计算每个样本属于每个高斯成分的后验概率（E步）
  • 再根据极大似然估计极值条件，更新参数（M步）

PS：这一部分在前面章节贝叶斯分类器中介绍过

算法描述

 

密度聚类

密度聚类亦称“基于密度的聚类”（density-based clustering），此类算法假设聚类结构能通过样本分布的紧密程度确定。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）

最著名的密度聚类算法

PS：这里算法名字中 密度 是基于 Spatial（空间上）的，而另一种 谱聚类（Spectral Clustering）算法 是基于 Spectral（频谱上）的。

原理简单总结就是：基于一组“邻域”参数 (ϵ,MinPts)(\epsilon,MinPts) 来刻画样本分布的紧密程度

概念定义

ϵ\epsilon - 领域：

对 xj∈D\boldsymbol{x}_j \in D，其 ϵ\epsilon - 领域包含样本集 DD 中与 xj\boldsymbol{x}_j 的距离不大于 ϵ\epsilon 的样本，即 Nϵ(xj)={xi∈D∣dist(xi,xj)≤ϵ}N_{\epsilon}(\boldsymbol{x}_j) = \{ \boldsymbol{x}_i \in D | \text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \le \epsilon \}

密度 (desity) xx 的密度为

ρ(x)=∣Nε(x)∣\rho (x)=\left | N_{\varepsilon }(x)\right |

核心对象：

若 xj\boldsymbol{x}_j 的 ϵ\epsilon - 领域至少包含 MinPtsMinPts 个样本，即 ∣Nϵ(xj)∣≥MinPts|N_{\epsilon}(\boldsymbol{x}_j)| \ge MinPts ，则 xj\boldsymbol{x}_j 是一个核心对象

结点间关系

密度直达（directly density-reachable）：

若 xj\boldsymbol{x}_j 位于 xi\boldsymbol{x}_i 的 ϵ\epsilon - 领域中，且 xi\boldsymbol{x}_i 是核心对象，则称 xj\boldsymbol{x}_j 由 xi\boldsymbol{x}_i 密度直达

密度直达关系通常不满足对称性：核心对象有交集的情况比较特殊

密度可达（density-reachable）：

对 xi\boldsymbol{x}_i 与 xj\boldsymbol{x}_j ，若存在样本序列 p1,p2,...,pn\boldsymbol{p}_1,\boldsymbol{p}_2,...,\boldsymbol{p}_n ，其中 p1=xi,pn=xj\boldsymbol{p}_1=\boldsymbol{x}_i,\boldsymbol{p}_n=\boldsymbol{x}_j 且 pi+1\boldsymbol{p}_{i+1} 由 pi\boldsymbol{p}_i 密度直达，则称 xj\boldsymbol{x}_j 由 xi\boldsymbol{x}_i 密度可达

密度可达关系满足直递性，但不满足对称性：同样因为有核心对象的参与

密度相连（density-connected）：

对 xi\boldsymbol{x}_i 与 xj\boldsymbol{x}_j ，若存在 xk\boldsymbol{x}_k 使得 xi\boldsymbol{x}_i 与 xj\boldsymbol{x}_j 均由 xk\boldsymbol{x}_k 密度可达，则称 xi\boldsymbol{x}_i 与 xj\boldsymbol{x}_j 密度相连

密度相连关系满足对称性

DD 中不属于任何簇的样本被认为是噪声（noise）或异常（anomaly）样本，如下图N

簇的定义

由密度可达关系导出的最大的密度相连样本集合

形式化定义

给定领域参数 (ϵ,MinPts)(\epsilon,MinPts)，簇 C⊆DC \subseteq D 是满足以下性质的非空样本子集

应满足性质:

  • 连接性（connectivity）：xi∈C，xj∈C⇒xi\boldsymbol{x}_i \in C，\boldsymbol{x}_j \in C \Rightarrow \boldsymbol{x}_i 与 xj\boldsymbol{x}_j 密度相连
  • 最大性（maximality）：xi∈C，xj\boldsymbol{x}_i \in C，\boldsymbol{x}_j 由 xi\boldsymbol{x}_i 密度可达 ⇒xj∈C\Rightarrow \boldsymbol{x}_j \in C

算法描述

构建ε\varepsilon 邻域的过程可以使用kd-tree进行优化，循环过程可以使用Numba、Cython、C进行优化，DBSCAN的源代码，使用该节一开始提到的数据集，聚类效果如下

聚类的过程示意图

当设置不同的 ε\varepsilon 时，会产生不同的结果，如下图所示

当设置不同的 MM 时，会产生不同的结果，如下图所示

一般来说，DBSCAN算法有以下几个特点：

  1. 需要提前确定 ε\varepsilon 和 MM 值
  2. 不需要提前设置聚类的个数
  3. 对初值选取敏感，对噪声不敏感
  4. 对密度不均的数据聚合效果不好

 

层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构。

两种策略方式：

  • “自底向上”的聚合策略
  • “自顶向下”的分拆策略

AGNES（AGglomerative NESting）

著名的自底向上聚合策略的层次聚类算法

核心思想

它先将数据及中的每个样本看做一个初始聚类簇，然后再算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，知道达到预设的聚类簇个数

常用的距离计算

  • 最小距离

    dmin(Ci,Cj)=min⁡x∈Ci,z∈Cjdist(x,z)d_{min}(C_i,C_j)=\underset{\boldsymbol{x} \in C_i, \boldsymbol{z} \in C_j}{\min} \text{dist}(\boldsymbol{x},\boldsymbol{z})

    AGNES称为“单链接”（single-linkage）

  • 最大距离

    dmax(Ci,Cj)=max⁡x∈Ci,z∈Cjdist(x,z)d_{max}(C_i,C_j) = \underset{\boldsymbol{x} \in C_i, \boldsymbol{z} \in C_j}{\max}\text{dist}(\boldsymbol{x}, \boldsymbol{z})

    AGNES称为“全链接”（complete-linkage）

  • 平均距离

    davg(Ci,Cj)=1∣Ci∣∣Cj∣∑x∈Ci∑z∈Cjdist(x,z)d_{\text{avg}}(C_i,C_j) = \frac{1}{|C_i||C_j|}\sum_{\boldsymbol{x} \in C_i} \sum_{\boldsymbol{z} \in C_j} \text{dist}(\boldsymbol{x}, \boldsymbol{z})

    AGNES称为“均链接”（average-linkage）

算法描述

层次聚类的合并算法通过计算两类数据点间的相似性，对所有数据点中最为相似的两个数据点进行组合，并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性，距离越小，相似度越高。并将距离最近的两个数据点或类别进行组合，生成聚类树。

相比于Hierarchical K-means算法存在的问题，Agglomerative Clustering算法能够保证距离近的对象能够被聚类到一个簇中，该算法采用的“自底向上”聚类的思路。

训练结果

 

参考

https://zhuanlan.zhihu.com/p/134089340

https://github.com/Vay-keen/Machine-learning-learning-notes

https://github.com/familyld/Machine_Learning

https://zhuanlan.zhihu.com/p/25994179

https://leovan.me/cn/2018/12/ensemble-learning/

https://easyai.tech/ai-definition/ensemble-learning/

https://zhuanlan.zhihu.com/p/72415675

https://www.zhihu.com/question/63492375

https://www.zhihu.com/question/27068705

https://www.zhihu.com/question/19725590/answer/241988854

https://tangshusen.me/2018/10/27/SVM/

https://www.joinquant.com/view/community/detail/a98b7021e7391c62f6369207242700b2

https://zhuanlan.zhihu.com/p/79531731

https://github.com/Charmve/PaperWeeklyAI/blob/master/03_Maiwei AI PaperWeekly/03_机器学习%26深度学习理论/机器学习算法之——K最近邻(k-Nearest Neighbor，KNN)分类算法原理讲解.md

https://blog.csdn.net/zc02051126/article/details/49618633

https://zhuanlan.zhihu.com/p/127022333

https://0809zheng.github.io/2020/03/30/ridge.html

https://www.cnblogs.com/wuliytTaotao/p/10837533.html

https://link.springer.com/referenceworkentry/10.1007/978-1-4899-7687-1_910#Sec13186

http://palm.seu.edu.cn/zhangml/files/mla11-mll.pdf

https://blog.csdn.net/zwqjoy/article/details/80431496

https://ryuchen.club/posts/0x000034/ (推荐）

https://zhuanlan.zhihu.com/p/78798251

https://zhuanlan.zhihu.com/p/622244758

https://www.biaodianfu.com/hierarchical-clustering.html

https://zhuanlan.zhihu.com/p/411533418

https://zhuanlan.zhihu.com/p/33196506

https://www.cnblogs.com/wry789/p/13125658.html

https://blog.csdn.net/qq_41485273/article/details/113178117

https://www.jianshu.com/p/7d4323c28716

http://lunarnai.cn/2019/01/02/watermelon-chap-13/

【周志华机器学习】十三、半监督学习

https://zhuanlan.zhihu.com/p/411533418

https://www.huaxiaozhuan.com/统计学习/chapters/12_semi_supervised.html

https://blog.csdn.net/tyh70537/article/details/80244490

https://zhuanlan.zhihu.com/p/37747650

7125messi.github.io

https://blog.csdn.net/qq_40722827/article/details/104515955

https://www.cnblogs.com/dyl222/p/11055756.html

https://www.zhihu.com/tardis/zm/art/392908965

https://blog.csdn.net/j123kaishichufa/article/details/7679682

https://www.cnblogs.com/heaad/archive/2011/01/02/1924088.html

https://www.cnblogs.com/stevenlk/p/6543628.html

baidinghub.github.io-PCA

baidinghub.github.io-LDA

等等