【AIDL专栏】方以类聚，物以群分，吉凶生矣 | 于剑：聚类理论与算法选讲

一、聚类简述

1、聚类的定义

聚类的思想起源非常早，中国可以追溯到《周易·系辞上》中的“方以类聚，物以群分，吉凶生矣”。但聚类的算法却是上世纪50年代才出现，这是因为聚类依赖于数据，数据量小不行，数据量大的时候只能由计算机解决，而计算机1946年才出现。

至今没有对聚类严格的定义，但有一个泛化定义能反映聚类的功能：给定N个对象，将其分成K个子集，使得每个子集内的对象相似，不同子集之间的对象不相似。

实际中对于“相似”的定义会引出诸多问题。如图1所示，给定六个对象，分别按照形状相似和颜色相似得到两种划分方法，两种方法都对，不同的是对“相似”的定义。所以“主观”是相似性最大的问题。

图1 不同“相似”标准下的聚类结果

2、聚类分析的基本步骤

聚类分析的步骤分为四个方面：数据表示，聚类判据，聚类算法和聚类评估。

数据表示是设计聚类算法的第一步。同一个聚类算法不可能用不同的数据表示。第二是聚类判据，算法通过判据确定搜索方向。第三是聚类算法，即得到搜索方向后设计算法。聚类评估是聚类和分类不一样的地方，分类有明确的外界标准，而聚类相对更为主观。

3、聚类的应用和挑战

聚类的应用很常见，如图2所示的“主题发现”，又如图像分割，协同滤波推荐算法等。“马甲”多是聚类算法的特点之一，但同时又会带来新的问题。

图2 聚类应用示例

问题之一是聚类算法的理论很多。依据概率理论的，依据信息论的，依据图论的（如谱聚类），依据模糊论的，依据博弈论的，量子力学的等等。理论的不统一导致研究聚类算法的复杂性。

二、聚类公理

聚类算法的公理化研究是聚类分析理论发展过程中重要的研究方向之一。

文献上有三种研究聚类公理化的方法：聚类判据(目标函数)的公理化，聚类映射的公理化，聚类有效性函数的公理化。

1、聚类判据的公理化

Karayiannis在1999年首先进行了聚类判据公理化的尝试。如下面的函数公式：

他认为公理化指下面三个公式：

但以上公式涉及到的聚类算法非常有限，因为其只适合这种类型的判据。

2、聚类映射的公理化

聚类映射是指将聚类算法看成从输入到输出的映射。

Kleinberg提出的12条公理是聚类映射公理化研究中最出名的，包括平移不变性、旋转不变性、尺度不变性等。但这些公理都是针对度量研究的，而且证明发现几乎没有能满足的算法。

3、聚类公理化研究新思路

聚类算法的基本要求并没有直接涉及聚类函数，聚类判据，或者聚类有效性，这是人为引入的。换一种思路，聚类只是归类的一种，没有标签时叫聚类，有标签时叫分类或者其他。如果归类有普遍遵循的原理，聚类也遵循。

4、归类问题的简化定义

归类是从某些概念的外延子集得到这些概念的内涵表示。归类和聚类相似，考虑数据表示，归类判据，归类算法和归类评估四部分。聚类公理化的探讨说明归类公理化研究只能从数据表示下手，其他三者行不通。

5、数据表示

实际的数据表示研究外显和内在两部分。在伯牙子期的故事中，子期接受到外在的琴声，而琴声的内在表示是“高山和流水”。现实中一般只有数据的外显表示，而没有其内在的部分。内在的部分需要算法学习。

图3 数据表示形象标识

N个对象特征向量构成的特征矩阵，相异度矩阵和相似性矩阵，以及图像，语音，文本等都是数据外显表示的常见形式。

亚里士多德的经典理论：当每个类都由内涵表示，那么这个类就是命题，是数据内在表示的最早研究。20世纪后，又提出了原型理论，量子理论，支持理论等。2016年4月论文《大脑与地图》指出概念在大脑中表示的位置可以标记出来。

归根到底，归类问题是数据的类表示问题。

6、归类公理

类表示存在公理：如果一个归类算法的归类外显输入输出给定，则其对应的类内部表示存在。
类表示唯一公理：对一个归类算法，其输入输出对应的类表示（语义）相同。
样本可分性公理：一个对象总有唯一一个类与其最相似。
类可分性公理：一个类至少有一个对象与其最相似。
归类等价公理：对于任意一个类, 其对应的算法内部表示与外显表示的归类能力等价。

7、小结

本节首先叙述了目前文献中存在的三种研究聚类公理化的方法，并指出目前文献中的聚类公理化体系与聚类的基本要求联系不紧密。在此基础上叙述了数据表示和归类的公理。聚类是归类的一种，所以聚类遵循归类的五个公理。

三、聚类算法设计准则

1、类紧致性准则

类内方差最小或者类内相似度最大。

2、类分离性准则

不同类之间距离越大越好。

3、类一致性准则

对于聚类，类表示唯一公理必须强制成立。

4、奥卡姆剃刀准则

原始的奥卡姆剃刀准则指“如无必要，勿增实体”。对于聚类算法，性能相同的前提下，如果很多类表示都可行，选择简单的。

四、聚类算法简述

聚类算法有多种分类方式：在线、离线；硬聚类、软聚类；分布式聚类、集中式聚类等。下文将从类认知表示的简单性出发探讨。

1、层次聚类

层次聚类的类认知表示最简单，其外显即内在，类认知表示即其对应的类划分。层次聚类因其可视化成为最广泛应用的聚类方法。

图4 层次聚类

2、 C(K)-Means聚类和模糊C(K)-Means聚类

层次聚类相对较为简单，外在即内在，类认知表示没有进行学习，但因为现实需要希望能得到类的内在表示，如用一个点来表示一个类。这是C-Means的做法。

根据类紧致性准则和其类认知表示方式，可以直接写出C-Means的目标函数：

公式中u_i即类中心，也即类认知（内在）表示。这时只需要最小化目标函数。C-Means的聚类步骤如下所示：

图5 C-Means聚类算法

C-Means将样本以概率为1划分为某一类，对于类的隶属度非1即0。如果把划分原则改为以某一介于0和1的概率隶属于某一类，样本将不再直接划分为某一类。此即模糊C(K)-Means聚类，此时目标函数变为：

上述两种算法是将一个点作为类认知表示，此外，还有线，椭圆，函数等比较复杂的类表示方法。

3、基于密度估计的聚类方法

层次聚类算法计算复杂度高，原型聚类算法如C(K)-Means要求有极强的先验估计，基于密度估计的聚类算法对这两者进行了折中。密度估计分为有参估计和无参估计。

有参密度估计聚类方法

聚类算法的类表示唯一公理成立，因此，类认知表示满足类紧致性准则，即最大化如下目标函数,也即最大化似然函数：

有参估计中经典的高斯混合密度估计将上述公式中概率表示为高斯公式形式：

von Mises-Fisher混合密度聚类算法将概率表述为下面形式：

它将输入约束在高维球上，读者可以参阅论文《Clustering on the unit hypersphere using von Mises Fisher Distributions》进行深入阅读。

无参密度估计聚类方法

当不知道数据分布的任何先验时用无参估计。此时，类认知表示定义为密度峰值的对应点。

1993年提出的削峰聚类法是第一个此类算法。削峰聚类法先计算出当前密度函数的最大峰值，通过削去最大峰值来修改当前密度函数，得到新的密度函数，重复上述步骤，直到得到足够多的聚类中心。

削峰聚类法主要用来找出聚类中心。削峰聚类法暗含类紧致准则，因为密度最高的点与周围的点最紧致。但只要求紧致并非最优，根据类分离准则，还要求不同的类越远越好。同时，原始的削峰聚类算法虽然想法直观，但由于数据维度通常高于3维，算法的直观性难以展现。基于这两点原因，2014年Alex Rodriguez在Science上提出了描峰聚类法。

其思想是同时考虑类紧致性准则和类分离性准则。每个样本点计算密度值和分离值，类中心具有高密度值和分离值。

描峰聚类法流行的重要原因之一是它是划分聚类算法中第一个可视化聚类算法。