轉載請註明出處：

論文來源：

AAAI 2017

論文連結：

Twin Learning for Similarity and Clustering： A Unified Kernel Approach

論文原作者：Zhao Kang， Chong Peng， Qiang Cheng

Abstract

許多基於相似性的聚類方法有倆步驟：第一步是相似性矩陣的運算；第二部是隨後的譜聚類演算法。然而，相似性的度量是具有挑戰性的，它會受到很多因素的影響比如相似性度量方法、鄰域（

k,\epsilon

），資料維度噪聲和極端值等。學習得到的相似性矩陣經常是不合適的，這會使得最後的譜聚類演算法結果變得不是最優。此外，非線性相似性在真實世界資料中也經常出現，如果用現有的方法去解決，效果可能沒那麼好。為了解決這倆挑戰，作者提出的模型在核空間裡同時學習了聚類指示矩陣和相似性矩陣。為解決怎樣選擇一個最合適的核問題，作者將模型進一步拓展到了具有多核學習能力。有了這個組合模型，作者可以同時完成三個子任務：第一，找到最好的聚類指示矩陣；第二，找到最準確的相似性關係；第三，找到最優的多核組合（選到最合適的核）。任務與任務之間是相互影響的。

Introduction

聚類就是將資料分離到不同的堆，以致於同一個堆的資料彼此之間相似，不同堆間的資料不相似。k-means演算法因其簡易性和效率性而被廣泛使用，但它不能夠區分任意形狀（shape）的聚類。kernel k-means是用於捕捉資料集的非線性結構資訊。基於核的學習方法要求確定一個核，這意味著須假設一個明確的底層資料空間形狀。因此基於核的方法的效果很大程度上是被核的選擇所影響。

譜聚類是在執行k-means聚類之前，對資料的相似性矩陣做了一個低維的embedding（實際是降維）。基於相似性的聚類方法通常呈現比k-means演算法更好的效果，因為基於相似性的聚類方法利用了每對點的相似性資訊作為輸入，這利用了多種資訊。然而，這種基於相似性的方法效果很大程度上由相似性矩陣所決定。相似性測量比如度量、鄰域大小、資料維度等可能會讓效果變得不是最優。

Contributions

1。在這篇論文中，作者在“self-expression”的思想上執行聚類，每個資料點是用其他的點來表達。

2。這個方法提取資料的全域性結構而不是區域性結構，可拓展至核空間。

3。不同於現存的聚類演算法，作者透過在拉普拉斯矩陣（學習相似性矩陣後得到）實行秩限制（rank constraint）同時學習了相似性矩陣和聚類指示矩陣。

4。作者直接將方法發展於核空間，為捕捉現實世界資料集的非線性結構資訊。

5。作者提出多核學習演算法為找到最合適的核。

Model

1.Clustering with Single Kernel

依據self-expressive特性：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

Z_{ij}

是第j個樣本的權重。更相似的樣本應該得到更大的權重，反之亦然。因此，

Z

也叫相似性矩陣，這表示了資料的全域性結構。為得到

Z

，作者須解決以下問題：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

第一項是重構誤差，第二項是正則項為避免平凡解

Z=I

。

（2）有一個缺點：它假設了樣本之間的線性關係。為揭露資料點之間的非線性關係，作者透過利用一個廣義核框架將（2）拓展到了核空間：

\phi:R^{D}\rightarrow

H

（將輸入空間的資料樣本對映到核空間），因此

X=[X_{1},...,X_{n}]\Rightarrow

\phi(X)=[\phi(X_{1}),...,\phi(X_{n})]

。

資料樣本

X_{i}

和

X_{j}

間的核相似性：

K_{X_{i},X_{j}}=<\phi(X_{i}),\phi(X_{j})>

因此（2）變成如下（3），可代入換算得到：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

理想化情況下，作者期望

Z

中的連通區域數為

c

如果給定的資料集

X

包含

c

個聚類（

Z

是塊對角的）。而（3）中的

Z

可能不滿足這個特性，須要加多個限制：

rank(L)=n-c

，

L

為

Z

的拉普拉斯矩陣。（3）變成：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

帶有秩約束的最佳化問題是有名的組合複雜度問題。為解決這個問題，將秩約束以正則化方式加入到目標函式。由於

rank(L)=n-c\Leftrightarrow

\Sigma

_{i=1}^{c}

\sigma_{i}=0

，則（4）變成：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

由Ky Fan’s Theorem得，

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

綜上，SCSK模型用公式表示為：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

不斷反覆更新

Z

和

P

，（7）會得到最佳化。詳細可見論文。

2.Clustering with Multiple Kernels

（7）的效果很大程度上決定於核的選擇，要找到最合適的核。多核學習演算法能夠整合資訊，區分出給定任務的最合適的核。

假設有r種不同的核函式 {

K^{i}

}

_{i=1}^{r}

。對應地，有r個不同的核空間{

H^{i}

}

_{i=1}^{r}

，擴張的Hilbert space可以透過連線所有的核空間

\tilde{H}=\oplus

_{i=1}^{r}H^{i}

。因此：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

資料的對映（帶不同權重）

則組合的核函式為：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

綜上，SCMK模型用公式表示為：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

反覆更新

Z,P,w

，最後達到最優。最佳化詳情見於論文。

Experiment

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

對於單核方法，作者比較了核k-means（KKM），譜聚類（SC），魯棒核k-means（RKKM）以及提出的SCSK演算法；

對於多核演算法（本論文中設定了12個核），作者比較了MKKM（Multiple Kernel K-means）演算法、AASC（Affinity aggregation for SC）演算法、RMKKM（Robust Multiple Kernel K-means Using L21-norm）演算法以及提出的SCMK演算法。

實驗結果如下：

Twin Learning for Similarity and Clustering: A Unified Kernel Approach

Conclusion

最近看的論文大多是將聚類和核函式結合在一起，與這篇論文聯絡緊密且思想相近的是AAAI2018上的一篇Unified Spectral Clustering with Optimal Graph，即是我的上一篇筆記。有興趣可詳細翻閱原論文！