周末AI课堂 聚类的几个重要问题 理论篇

AI课堂开讲，就差你了！

很多人说，看了再多的文章，可是没有人手把手地教授，还是很难真正地入门AI。为了将AI知识体系以最简单的方式呈现给你，从这个星期开始，芯君邀请AI专业人士开设“周末学习课堂”——每周就AI学习中的一个重点问题进行深度分析，课程会分为理论篇和代码篇，理论与实操，一个都不能少！

来，退出让你废寝忘食的游戏页面，取消只有胡吃海塞的周末聚会吧。未来你与同龄人的差异，也许就从每周末的这堂AI课开启了！

读芯术读者交流群，请加小编微信号：zhizhizhuji。等你。后台回复“周末AI课堂”，查阅相关源代码。

全文共2723字，预计学习时长5分钟

机器学习技术主要分为有监督学习和无监督学习，前者需要利用样本的标签，后者则没有。某种程度上来说，有标签的学习是一种目标导向的学习，而机器学习的根本任务就是预测，标签就可以将学习过程与结果结合在一起，这和我们人类本身的学习过程是吻合的。而所谓的无监督学习，事实上我们也并不陌生，在《线性降维》和《非线性降维》中，我们就已经把降维方法分作监督降维和无监督降维，我们也看到有监督的LDA的表现是比无监督的PCA要好，那么无监督学习的意义在哪里？

数学准备

属性的序（ordinal ）：属性值可以比较，叫做有序属性，属性无法比较，叫做无序属性。有序属性不一定是数值的，但可以根据序来数值化。

聚类的动机

聚类可能是最流行的无监督学习方法，简单的说，它把相似的样本做归为一类。

其中最重要的原因是我们很多时候不能也不想对数据进行类别标记，而我们又不得不处理一些类别化问题。比如现在流行的推荐系统，音乐和购物网站会收集我们对歌曲和商品的信息，网站希望能预测出我们的偏好，从而推荐给我们未知但会更喜欢的东西，但是人群是不好做分类的，而可能的分类方式与类别的偏好的组合数将会是一个非常庞大的数字，所以我们无法寄托于监督学习，而只是根据用户的行为去对用户群做聚类，相似度更高的为一个簇（cluster），所以我们会经常发现购物和音乐网站上出现一行小字：购买了此商品的用户也够购买了XXX。

如果只从这个角度来看，聚类似乎成为了数据没有标注下的无奈之举，事实上，聚类揭示了未标注数据的内在结构，因为我们有一个很自然的假设：相似的样本具有相似的输出。现实中经常发生的是，我们只有少量被标记的样本，我们就可以根据聚类的结果来判断未被标记的样本的性质，这就是半监督学习（Semi-Supervised Learning ）的一种范式。

无监督学习主要技术并不只局限于聚类和降维，还有生成对抗网络（GAN）和自组织映射（SOM)。因为聚类是个庞大的领域，有些细节不会详细讲解，我们将在此文中主要讲解聚类技术中比较难理解的几点。

聚类的重要细节

任何聚类算法都会涉及到三个基本问题：

相似度估计，它决定了同一簇内和不同簇间的标准

数据的组织形式，它决定了算法的结构

性能评估，它决定了算法的优劣程度

相似度评估：距离

我们一般采用距离作为相似度的指标，距离越近，相似度越高，同类的样本一般彼此邻近。就像我们在《非参数模型（理论篇）》中提到的KNN算法，它依赖的假设就是，相似的样本距离也会邻近，所以未知样本要依靠周围邻近的K个样本的输出。我们在《非参数模型（代码篇）》介绍了欧几里得距离，闵科夫斯基距离，曼哈顿距离，以及切比雪夫距离，但这些只适用于处理有序属性，因为距离的计算需要利用属性值之间的差，无序属性的差无法定义。

取而代之，我们利用一般使用VDM（Value Difference Metric）来度量无序属性的距离：

其中，是在属性u上取值为a的样本数，

是在属性u上取值为a，并且属于i簇的样本数，当p=1时，VDM计算的本质是在同一属性上两个不同取值对簇的影响，同一个簇内，某一个取值占比越高，说明这两个属性取值对簇划分是有用的，那么VDM的值也会很大，如果属性取值占比相近，说明这两个属性值对于簇划分是没有用的，VDM的值就会变得很小，背后同样隐藏着距离度量着相似度，因为距离越近，相似度越高，越倾向于归于一个簇。

对于每个样本，可能存在n个属性，我们需要对属性数求和：

其中，

是指样本在属性u上的取值，相当于a.

组织形式

最著名的聚类算法可能就是K均值算法（K-means），很多材料上都会反复讲解这个经典的算法，所以，我在这里不会详细讲解它，反之，我们来探究一下聚类算法的主要的几种组织形式：

基于原型的聚类，它的假设是聚类的结果可以通过原始的数据点来表达。以k-means为例，它指定好类别数，随机选择初始样本点作为簇的均值向量，然后迭代更新这些均值向量，直到所有的簇被划分好，表现为均值向量不再更新。

这类方法非常高效，但只考虑了独立样本，无法应付非凸形状的数据分布，尤其是当数据分布为环形时，k-means聚类效果就会把整个环形散成几个部分。

基于密度的聚类，它的假设是聚类的结果要通过密度的高低来表达。以DBSCAN（density-based Spatial Clustering ofApplications with Noise）为例，它不需要指定类别数，但需要指定领域参数和定义核心对象所需要的最小样本数，然后对于每个数据判断其领域内包含的样本是否大于最小样本数，如果大于那么将其加入核心对象，然后寻找核心对象所有密度可达的样本，将其划分为一个簇，直到遍历完所有的样本。

密度聚类不需要制定类别数，一定程度上解决了非凸形状的聚类，同时还可以将孤立的噪声点分离出来，而不是将它们强行融合到其他的簇中，但其对于参数的微小变化就会引起聚类结果的不同，非常不稳定。

基于集合的聚类，它的假设是聚类的结果是通过集合来表达。以层次聚类（hierarchical clustering）为例，与普通距离计算不同，它定义了集合之间的距离，从上到下法说的是，一开始将所有样本都看作一个大类，然后通过集合距离逐渐的分离成指定的类别数；从下到上说的是，一开始将每个样本都看作一个类，然后通过集合距离逐渐融合成制定的类别数。

它不仅可以解决上述的问题，而且研究也证明采取不同的集合距离可以适应复杂的数据，但是它运算的复杂度较高，因为它要计算每一对样本的距离。

此外，我们还有基于网格的聚类，其中涉及到的网格是一种典型的连续空间离散化的手段，我们通过计算网格上的包含的样本个数定义稠密单元和稀疏单元，由邻近与否判断是否应该划为一类。同时，还有基于概率生成模型的聚类，典型的是高斯混合模型，亮点是不再有划分明显的分界，而是计算每样本的属于某一分布的后验概率。

性能度量

聚类并没有统一的标准去比较准确性，因为任何聚类都可能是合理的。比如，一堆苹果，香蕉和芒果，我们既可以通过颜色来划分，也可以通过某一元素的含量划分，还可以通过体积划分，即使划分的结果不同，但任何划分都是有道理的。

我们可以大致意识到，聚类的结果应该是相同簇的样本尽可能的相似，不同簇的样本尽可能的不同。常见的度量指标有DBI（Davies-Bouldin Index）和DI(Dunn Index)，但如果我们想将其与一个标准模型做对比，我们还可以得到更靠谱的度量指标，比如Jaccard Coefficient和Rand Index。

读芯君开扒

课堂TIPS

• 在《非参数模型初步》中提到了我们可以通过马氏距离去学习一种最适合数据的距离，同样在聚类中，我们也可以在特定的聚类算法中嵌入这样的学习。

• 为了解决k-means无法处理非凸结构的问题，我们还可以在k-means中引入kernel trick，使得原始的特征空间映射到高维空间，将非凸分布变成凸分布。

• 聚类也可以进行集成，对基学习器添加数据扰动、特征扰动、参数扰动，同样可以适应复杂的数据分布。

• 聚类和分监督降维一般都可以很紧密的结合在一起，因为维数灾难的问题，会使得距离计算变得非常困难，所以在著名的谱聚类（Spectral Clustering）中，会把数据先进行降维处理，然后再使用聚类。

留言 点赞 发个朋友圈

我们一起探讨AI落地的最后一公里

作者：唐僧不用海飞丝

如需转载，请后台留言，遵守转载规范