↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』原创

作者：华校专

作者信息：

华校专，曾任阿里巴巴资深算法工程师、智易科技首席算法研究员，现任腾讯高级研究员，《Python 大战机器学习》的作者。

编者按：

算法工程师必备系列更新啦！继上次推出了算法工程师必备的特征工程后，小编继续整理了必要的机器学习知识，全部以干货的内容呈现，哪里不会学哪里，老板再也不用担心你的基础问题！接下来，就让我们紧跟作者的步伐，一起畅游聚类世界吧！

聚类（上）

在无监督学习(unsupervised learning)中，训练样本的标记信息是未知的。
无监督学习的目标：通过对无标记训练样本的学习来揭露数据的内在性质以及规律。
一个经典的无监督学习任务：寻找数据的最佳表达(representation)。常见的有：

低维表达：试图将数据（位于高维空间）中的信息尽可能压缩在一个较低维空间中。
稀疏表达：将数据嵌入到大多数项为零的一个表达中。该策略通常需要进行维度扩张。
独立表达：使数据的各个特征相互独立。

无监督学习应用最广的是聚类(clustering) 。

给定数据集，聚类试图将数据集中的样本划分为个不相交的子集，每个子集称为一个簇cluster。其中：。
通过这样的划分，每个簇可能对应于一个潜在的概念。这些概念对于聚类算法而言，事先可能是未知的。
聚类过程仅仅能自动形成簇结构，簇所对应的概念语义需要由使用者来提供。

通常用表示样本的簇标记cluster label，即。于是数据集的聚类结果可以用包含个元素的簇标记向量来表示。

聚类的作用：

可以作为一个单独的过程，用于寻找数据内在的分布结构。
也可以作为其他学习任务的前驱过程。如对数据先进行聚类，然后对每个簇单独训练模型。

聚类问题本身是病态的。即：没有某个标准来衡量聚类的效果。

但是实际上不知道这个平均距离对应于真实世界的物理意义。

如：在图片识别中包含的图片有：红色卡车、红色汽车、灰色卡车、灰色汽车。可以聚类成：红色一类、灰色一类；也可以聚类成：卡车一类、汽车一类。

解决该问题的一个做法是：利用深度学习来进行分布式表达，可以对每个车辆赋予两个属性：一个表示颜色、一个表示型号。

可能很多不同的聚类都很好地对应了现实世界的某些属性，它们都是合理的。
可以简单的度量聚类的性质，如每个聚类的元素到该类中心点的平均距离。

一、性能度量

聚类的性能度量也称作聚类的有效性指标validity index 。
直观上看，希望同一簇的样本尽可能彼此相似，不同簇的样本之间尽可能不同。即：簇内相似度intra-cluster similarity高，且簇间相似度inter-cluster similarity低。
聚类的性能度量分两类：

聚类结果与某个参考模型reference model进行比较，称作外部指标external index 。
直接考察聚类结果而不利用任何参考模型，称作内部指标internal index 。

1.1 外部指标

对于数据集，假定通过聚类给出的簇划分为。参考模型给出的簇划分为，其中和不一定相等。
令分别表示的簇标记向量。定义：
其中表示集合的元素的个数。各集合的意义为：
由于每个样本对仅能出现在一个集合中，因此有

：包含了同时隶属于的样本对。
：包含了隶属于，但是不隶属于的样本对。
：包含了不隶属于，但是隶属于的样本对。
：包含了既不隶属于，又不隶属于的样本对。

下述性能度量的结果都在之间。这些值越大，说明聚类的性能越好。

1.1.1 Jaccard系数

Jaccard系数Jaccard Coefficient:JC：
它刻画了：所有的同类的样本对（要么在中属于同类，要么在中属于同类）中，同时隶属于的样本对的比例。

1.1.2 FM指数

FM指数Fowlkes and Mallows Index:FMI：
它刻画的是：

在中同类的样本对中，同时隶属于的样本对的比例为。
在中同类的样本对中，同时隶属于的样本对的比例为。
FMI就是和 p2 的几何平均。

1.1.3 Rand指数

Rand指数Rand Index:RI：
它刻画的是：

同时隶属于的同类样本对（这种样本对属于同一个簇的概率最大）与既不隶属于又不隶属于的非同类样本对（这种样本对不是同一个簇的概率最大）之和，占所有样本对的比例。
这个比例其实就是聚类的可靠程度的度量。

1.1.4 ARI指数

使用RI有个问题：对于随机聚类，RI指数不保证接近0（可能还很大）。
ARI指数就通过利用随机聚类来解决这个问题。
定义一致性矩阵为：
其中：

为属于簇的样本的数量，为属于簇的样本的数量。
为同时属于簇和簇的样本的数量。

则根据定义有：，其中表示组合数。数字2 是因为需要提取两个样本组成样本对。

定义ARI指数Adjusted Rand Index:

其中：

：表示同时隶属于的样本对。
：表示最大的样本对。
即：无论如何聚类，同时隶属于的样本对不会超过该数值。
：表示在随机划分的情况下，同时隶属于的样本对的期望。
(1) 随机挑选一对样本，一共有种情形。
(2) 这对样本隶属于中的同一个簇，一共有种可能。
(3) 这对样本隶属于中的同一个簇，一共有种可能。
(4) 这对样本隶属于中的同一个簇、且属于中的同一个簇，一共有种可能。
(5) 则在随机划分的情况下，同时隶属于的样本对的期望（平均样本对）为：。

1.2 内部指标

对于数据集，假定通过聚类给出的簇划分为。定义：
其中：表示两点之间的距离；表示簇的中心点，表示簇的中心点，表示簇的中心点之间的距离。
上述定义的意义为：

：簇中每对样本之间的平均距离。
：簇中距离最远的两个点的距离。
：簇之间最近的距离。
：簇中心点之间的距离。

1.2.1 DB指数

DB指数Davies-Bouldin Index:DBI：
其物理意义为：
该度量越小越好。

给定一个簇，遍历其它的簇，寻找该度量的最大值。
对所有的簇，取其最大度量的均值。
给定两个簇，每个簇样本距离均值之和比上两个簇的中心点之间的距离作为度量。

显然越小越好。

如果每个簇样本距离均值越小（即簇内样本距离都很近），则越小。
如果簇间中心点的距离越大（即簇间样本距离相互都很远），则越小。

1.2.2 Dunn指数

Dunn指数Dunn Index:DI：
其物理意义为：任意两个簇之间最近的距离的最小值，除以任意一个簇内距离最远的两个点的距离的最大值。
显然越大越好。

如果任意两个簇之间最近的距离的最小值越大（即簇间样本距离相互都很远），则越大。
如果任意一个簇内距离最远的两个点的距离的最大值越小（即簇内样本距离都很近），则越大。

1.3 距离度量

距离函数常用的有以下距离：
考虑非数值类属性（如属性取值为：中国，印度，美国，英国），令表示的样本数；表示且位于簇中的样本的数量。则在属性上的两个取值之间的 VDM距离为：
该距离刻画的是：属性取值在各簇上的频率分布之间的差异。

闵可夫斯基距离Minkowski distance：给定样本则闵可夫斯基距离定义为：
(1) 当时，闵可夫斯基距离就是欧式距离Euclidean distance：
(2) 当时，闵可夫斯基距离就是曼哈顿距离Manhattan distance：
VDM距离Value Difference Metric：

当样本的属性为数值属性与非数值属性混合时，可以将闵可夫斯基距离与 VDM 距离混合使用。

假设属性为数值属性，属性为非数值属性。则：

当样本空间中不同属性的重要性不同时，可以采用加权距离。

以加权闵可夫斯基距离为例：

这里的距离函数都是事先定义好的。在有些实际任务中，有必要基于数据样本来确定合适的距离函数。这可以通过距离度量学习distance metric learning来实现。

这里的距离度量满足三角不等式：, 。

在某些任务中，根据数据的特点可能需要放松这一性质。如：美人鱼和人距离很近，美人鱼和鱼 距离很近，但是人和鱼的距离很远。这样的距离称作非度量距离non-metric distance。

二、原型聚类

原型聚类prototype-based clustering假设聚类结构能通过一组原型刻画。
常用的原型聚类有：

k均值算法k-means 。
学习向量量化算法Learning Vector Quantization:LVQ 。
高斯混合聚类Mixture-of-Gaussian 。

2.1 k-means 算法

2.1.1 k-means

给定样本集，假设一个划分为。

定义该划分的平方误差为：
其中是簇的均值向量。

err 刻画了簇类样本围绕簇均值向量的紧密程度，其值越小，则簇内样本相似度越高。
k-means 算法的优化目标为：最小化。即：。

k-means 的优化目标需要考察的所有可能的划分，这是一个NP难的问题。实际上k-means 采用贪心策略，通过迭代优化来近似求解。

首先假设一组均值向量。
然后根据假设的均值向量给出了的一个划分。
再根据这个划分来计算真实的均值向量：
(1) 如果真实的均值向量等于假设的均值向量，则说明假设正确。根据假设均值向量给出的的一个划分确实是原问题的解。
(2) 如果真实的均值向量不等于假设的均值向量，则可以将真实的均值向量作为新的假设均值向量，继续迭代求解。

这里的一个关键就是：给定一组假设的均值向量，如何计算出的一个簇划分？

k均值算法的策略是：样本离哪个簇的均值向量最近，则该样本就划归到那个簇。

k-means 算法：

输入：
(1) 样本集。
(2) 聚类簇数。
输出：簇划分。
算法步骤：
(1) 从中随机选择个样本作为初始均值向量。
(2) 重复迭代直到算法收敛，迭代过程：
(2.1) 初始化阶段：取
(2.2) 划分阶段：令：
(2.2.1) 计算的簇标记：, 。即：将离哪个簇的均值向量最近，则该样本就标记为那个簇。
(2.2.2) 然后将样本划入相应的簇：。
(2.3) 重计算阶段：计算。
(2.4) 终止条件判断：
(2.4.1) 如果对所有的，都有，则算法收敛，终止迭代。
(2.4.2) 否则重赋值。

k-means 优点：

计算复杂度低，为，其中为迭代次数。通常和 q 要远远小于，此时复杂度相当于。
思想简单，容易实现。

k-means 缺点：

通常进行多次k-means，然后选择最优的那次作为最终聚类结果。

结果不一定是全局最优的，只能保证局部最优。
对噪声敏感。因为簇的中心是取平均，因此聚类簇很远地方的噪音会导致簇的中心点偏移。
无法解决不规则形状的聚类。
无法处理离散特征，如：国籍、性别 等。
需要首先确定聚类的数量。
分类结果严重依赖于分类中心的初始化。

k-means 性质：

k-means 实际上假设数据是呈现球形分布，实际任务中很少有这种情况。与之相比，GMM 使用更加一般的数据表示，即高斯分布。
k-means 假设各个簇的先验概率相同，但是各个簇的数据量可能不均匀。
k-means 使用欧式距离来衡量样本与各个簇的相似度。这种距离实际上假设数据的各个维度对于相似度的作用是相同的。
k-means 中，各个样本点只属于与其相似度最高的那个簇，这实际上是硬 分簇。
k-means 算法的迭代过程实际上等价于EM 算法。具体参考EM 算法章节。

2.1.2 k-means++

k-means++ 属于 k-means 的变种，它主要解决 k-means 严重依赖于分类中心初始化的问题。
k-means++ 选择初始均值向量时，尽量安排这些初始均值向量之间的距离尽可能的远。
k-means++ 算法：

输入：
(1) 样本集。
(2) 聚类簇数。
输出：簇划分。
算法步骤：
(1) 从中随机选择1个样本作为初始均值向量组。
(2) 迭代，直到初始均值向量组有个向量。
假设初始均值向量组为。迭代过程如下：
(2.1) 对每个样本，分别计算其距的距离。这些距离的最小值记做。
(2.2) 对样本，其设置为初始均值向量的概率正比于。即：离所有的初始均值向量越远，则越可能被选中为下一个初始均值向量。
(2.3) 以概率分布未归一化的）随机挑选一个样本作为下一个初始均值向量。
(3) 一旦挑选出初始均值向量组，剩下的迭代步骤与k-means 相同。

2.1.3 k-modes

k-modes 属于 k-means 的变种，它主要解决 k-means 无法处理离散特征的问题。
k-modes 与 k-means 有两个不同点（假设所有特征都是离散特征）：
其中为示性函数。
上式的意义为：样本之间的距离等于它们之间不同属性值的个数。
其中的取值空间为所有样本在第个属性上的取值。

簇中心的更新规则不同。在k-modes 算法中，簇中心每个属性的取值为：簇内该属性出现频率最大的那个值。
距离函数不同。在k-modes 算法中，距离函数为：

2.1.4 k-medoids

k-medoids 属于 k-means 的变种，它主要解决k-means 对噪声敏感的问题。
k-medoids 算法：

输入：
(1) 样本集。
(2) 聚类簇数。
输出：簇划分。
算法步骤：
(1) 从中随机选择个样本作为初始均值向量。
(2) 重复迭代直到算法收敛，迭代过程：
(2.1) 初始化阶段：取。
遍历每个样本，计算它的簇标记：。即：将离哪个簇的均值向量最近，则该样本就标记为那个簇。
然后将样本划入相应的簇：。
(2.2) 重计算阶段：
遍历每个簇：
(2.2.1) 计算簇心距离簇内其它点的距离。
(2.2.2) 计算簇内每个点距离簇内其它点的距离。
如果，则重新设置簇中心：。
(2.3) 终止条件判断：遍历一轮簇之后，簇心保持不变。

k-medoids 算法在计算新的簇心时，不再通过簇内样本的均值来实现，而是挑选簇内距离其它所有点都最近的样本来实现。这就减少了孤立噪声带来的影响。

k-medoids 算法复杂度较高，为。其中计算代价最高的是计算每个簇内每对样本之间的距离。

通常会在算法开始时计算一次，然后将结果缓存起来，以便后续重复使用。

2.1.5 mini-batch k-means

mini-batch k-means 属于 k-means 的变种，它主要用于减少k-means 的计算时间。
mini-batch k-means 算法每次训练时随机抽取小批量的数据，然后用这个小批量数据训练。这种做法减少了k-means 的收敛时间，其效果略差于标准算法。
mini-batch k-means 算法：

输入：
(1) 样本集。
(2) 聚类簇数。
输出：簇划分。
算法步骤：
(1) 从中随机选择个样本作为初始均值向量。
(2) 重复迭代直到算法收敛，迭代过程：
(2.1) 初始化阶段：取
(2.2) 划分阶段：随机挑选一个Batch 的样本集合，其中为批大小。
(2.2.1) 计算的簇标记：, 。
即：将离哪个簇的均值向量最近，则该样本就标记为那个簇。
(2.2.2) 然后将样本划入相应的簇：。
(2.3) 重计算阶段：计算。
(2.4) 终止条件判断：
(2.4.1) 如果对所有的，都有，则算法收敛，终止迭代。
(2.4.2) 否则重赋值。

2.2 学习向量量化

与一般聚类算法不同，学习向量量化Learning Vector Quantization:LVQ假设数据样本带有类别标记，学习过程需要利用样本的这些监督信息来辅助聚类。
给定样本集 ,，LVQ的目标是从特征空间中挑选一组样本作为原型向量。

每个原型向量代表一个聚类簇，簇标记。即：簇标记从类别标记中选取。
原型向量从特征空间中取得，它们不一定就是中的某个样本。

LVQ的想法是：通过从样本中挑选一组样本作为原型向量，可以实现对样本空间的簇划分。

对任意样本，它被划入与距离最近的原型向量所代表的簇中。
对于每个原型向量，它定义了一个与之相关的一个区域，该区域中每个样本与的距离都不大于它与其他原型向量的距离。
区域对样本空间形成了一个簇划分，该划分通常称作 Voronoi 剖分。

问题是如何从样本中挑选一组样本作为原型向量？LVQ的思想是：

首先挑选一组样本作为假设的原型向量。
然后对于训练集中的每一个样本，找出假设的原型向量中，距离该样本最近的原型向量：
(1) 如果的标记与的标记相同，则更新，将该原型向量更靠近。
(2) 如果的标记与的标记不相同，则更新，将该原型向量更远离。
不停进行这种更新，直到迭代停止条件（如以到达最大迭代次数，或者原型向量的更新幅度很小）。

LVQ算法：

输入：
(1) 样本集
(2) 原型向量个数
(3) 各原型向量预设的类别标记
(4) 学习率
输出：原型向量
算法步骤：
(1) 依次随机从类别中挑选一个样本，初始化一组原型向量。
(2) 重复迭代，直到算法收敛。迭代过程如下：
(2.1) 从样本集中随机选取样本，挑选出距离最近的原型向量。
(2.2) 如果的类别等于，则：。
(2.3) 如果的类别不等于，则：。

在原型向量的更新过程中：

则更新后的原型向量距离更近。

则更新后的原型向量距离更远。

如果的类别不等于，则更新后，与距离为：
如果的类别等于，则更新后，与距离为：

这里有一个隐含假设：即计算得到的样本该样本可能不在样本集中）的标记就是更新之前的标记。

即：更新操作只改变原型向量的样本值，但是不改变该原型向量的标记。

2.3 高斯混合聚类

高斯混合聚类采用概率模型来表达聚类原型。
对于维样本空间中的随机向量，若服从高斯分布，则其概率密度函数为：
其中为 n 维均值向量，是的协方差矩阵。的概率密度函数由参数决定。
定义高斯混合分布：。该分布由个混合成分组成，每个混合成分对应一个高斯分布。其中:

, 是第个高斯混合成分的参数。
是相应的混合系数，满足。

假设训练集的生成过程是由高斯混合分布给出。

令随机变量表示生成样本的高斯混合成分序号，的先验概率。

生成样本的过程分为两步：

首先根据概率分布生成随机变量。
再根据的结果，比如，根据概率生成样本。

根据贝叶斯定理，若已知输出为，则的后验分布为：

其物理意义为：所有导致输出为的情况中，发生的概率。

当高斯混合分布已知时，高斯混合聚类将样本集划分成个簇。

对于每个样本，给出它的簇标记为：

即：如果最有可能是产生的，则将该样本划归到簇。

这就是通过最大后验概率确定样本所属的聚类。

现在的问题是，如何学习高斯混合分布的参数。由于涉及到隐变量，可以采用EM算法求解。

具体求解参考EM 算法的章节部分。

相关文章推荐

往期算法工程师系列文章请点击蓝字标题，即可阅读《数据科学|算法工程师必备的机器学习--特征工程》

本文福利

可以在本公众号后台 回复关键词：“ DS “ 获取大量由我平台编辑精心整理的学习资料，如果觉得有用，请勿吝啬你的留言和赞哦！

—— 完 ——

文章须知

文章作者：华校专

责任编辑：周岩 logic 征帆

审核编辑：阿春

微信编辑：征帆

本文由『运筹OR帷幄』原创发布

如需转载请在公众号后台获取转载须知

数据科学 | 算法工程师必备的机器学习--聚类(上)