乾貨：淺析Axiomatic Clustering演算法

今天我們將和大家一起來討論下演算法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

那麼能不能用「更弱」一點的公理來替代原本的三條，而使得至少有演算法能滿足所有的公理呢？ 事實上，如果我們把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.