浅析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.

转载请注明:《浅析Axiomatic Clustering算法 | 我爱计算机