浅析Axiomatic Clustering算法

推荐语：著名计算机学家、数学家、HITS算法发明人 Jon Kleinberg 曾在《An Impossibility Theorem for Clustering 》论证过“聚不准”定理，即没有一个聚类方法能同时满足两个以上的性质。该定理深刻揭示了各种聚类算法背后的局限性。本篇文章很到位地为大家进行了科普，强烈推荐。

文章来源：https://zhuanlan.zhihu.com/p/29118501

今天我们将和大家一起来讨论下算法Axiomatic Clustering

一般解决一个clustering问题，首先我们需要对structure of data 做一些假设。其中有统计模型比如Gaussian Mixture Model，也有非统计模型比如strict separation property（target clustering中同类间的距离比非同类间的距离小）。但是我们能不能对于structure of data不做任何假设而是只考虑clustering algorithm自身的性质呢？

Axiomatic clustering 讨论的就是这个问题。 我们把clustering algorithm看成一个函数f(X,d)。它把数据的标号X和距离d作为输入，它的输出就是在X上的一个分类（partition）。那么我们希望f都有哪些性质呢？

首先，很自然的我们希望算法不会因为数据间距离的伸缩而改变分类结果。所以我们希望f有Scale Invariance的性质（或者说公理）：

Scale Invariance：对于任意 α>0,我们有 f(X,d)=f(X,αd)

其次，我们不希望算法对于任意的距离d, 永远只输出某些特定的分类（partition）。所以我们希望f有Richness的性质：

Richness：对于任意一种partition γ，都存在一个距离d，使得 f(X,d)=γ

最后，我们希望算法的分类有某种一致性（Consistency）：

Consistency：对于任意两个距离d和d′，其中γ=f(X,d)。 如果对于γ中任意两个同类的点i和j，我们有d(i,j)≥d′(i,j)，而任意两个不同类的点i和j，我们有d(i,j)≤d′(i,j)，那么我们有f(X,d)=f(X, d′)

看上去这三条在参考[1]中提出的公理要求的并不多，我们可以较容易地构造出算法满足其中任意两条，然而事实上，不存在任何一个算法能满足全部三条。而且平时用的k-centroid-based
clustering算法比如k-mean,k-median,它们不仅不满足Richness的条件（因为已经限定了k个分类），同时也不满足Consistency的性质。

那么能不能用“更弱”一点的公理来替代原本的三条，而使得至少有算法能满足所有的公理呢？ 事实上，如果我们把Richness改成k-Richness：

k-Richness：对于任意一种分成k个类的partition γ，都存在一个距离d， 使得 f(X,d)=γ

那么Single Linkage Algorithm 就满足替换后的三条，即Scale Invariance， k-Richness 和 Consistency。如果我们并不知道要分成多少个类，所以想尽可能保留Richness的性质，我们又该如何呢？ 事实上，Consistency的条件可能太强，我们可以替换成如下较弱的一致性：

Refinement-Consistency：对于任意两个距离d和d′，其中γ=f(X,d), γ′=f(X,d′)。如果对于γ中任意两个同类的点i和j，我们有d(i,j)≥d′(i,j)，而任意两个不同类的点i和j，我们有d(i,j)≤d′(i,j)，那么我们有 γ′中的任意一个类C′,都存在γ中的一个类C，使得C′属于C

那么我们可以构造出算法满足Scale Invariance，Refinement-Consistency和Richenss除去最简单的一个partition , 其中是把每个数据点都单独分成一类（n个数据点就有n个类）。

讨论到这儿，你可能会问除了之前的三条公理及其变化，还有什么公理我们可以提出然后研究的呢？我们是否能找出一组公理，不仅仅存在算法能满足所有性质，同时恰恰仅有这一类算法满足这组公理？如果有这样的关系，我们是否就可以比较且更好地理解算法之间的不同？

参考[2]中给出了部分解答。我们可以考虑以下两条公理：

Order Consistency：考虑所有(n 2)两点间的距离，如果他们的大小排序在距离d和距离d’上是相同的，那么f(X,d)=f(X, d′)。

MST-Coherence：如果两个距离d和d’所对应的MST（minimal spanning tree，最小生成树）是相同的，那么f(X,d)=f(X, d′)

参考[2]中证明了Single Linkage Algorithm是唯一的一个算法能满足如下5条公理：Scale Invariance，k-Richness，Consistency，Order Consistency和MST-Coherence。同时我们也知道MST的确和Single Linkage Algorithm关系密切。可惜的是，我们还没有找到有关其他算法这样的对应关系。

Axiomatic Clustering 在最低的限制下，给出了一个很数学化的对clustering algorithm的理解，可能也因此限制了其应用和拓展，我们对这一方面的理解依然停留在较为简单的算法上。

Reference：

[1] Jon Kleinberg. An impossibility theorem for clustering. Advances in neural information processing systems, 2003.

[2] Reza Bosagh Zadeh and Shai Ben-David. A uniqueness theorem for clustering. Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence. AUAI Press, 2009.