Twin Learning for Similarity and Clustering: A Unified Kernel Approach

05-19

來自專欄每周一篇機器學習論文筆記

轉載請註明出處：

每周一篇機器學習論文筆記?

zhuanlan.zhihu.com

論文來源：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特性：

$Z_{ij}$ 是第j個樣本的權重。更相似的樣本應該得到更大的權重，反之亦然。因此， $Z$ 也叫相似性矩陣，這表示了數據的全局結構。為得到 $Z$ ，作者須解決以下問題：

第一項是重構誤差，第二項是正則項為避免平凡解 $Z=I$ 。

（2）有一個缺點：它假設了樣本之間的線性關係。為揭露數據點之間的非線性關係，作者通過利用一個廣義核框架將（2）拓展到了核空間： $phi:R^{D} ightarrow$ $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），可代入換算得到：

理想化情況下，作者期望 $Z$ 中的連通區域數為 $c$ 如果給定的數據集 $X$ 包含 $c$ 個聚類（ $Z$ 是塊對角的）。而（3）中的 $Z$ 可能不滿足這個特性，須要加多個限制： $rank(L)=n-c$ , $L$ 為 $Z$ 的拉普拉斯矩陣。（3）變成：

帶有秩約束的優化問題是有名的組合複雜度問題。為解決這個問題，將秩約束以正則化方式加入到目標函數。由於 $rank(L)=n-cLeftrightarrow$ $Sigma$ $_{i=1}^{c}$ $sigma_{i}=0$ ，則（4）變成：

由Ky Fan』s Theorem得，

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

不斷反覆更新 $Z$ 和 $P$ ，（7）會得到優化。詳細可見論文。

2.Clustering with Multiple Kernels

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

假設有r種不同的核函數 { $K^{i}$ } $_{i=1}^{r}$ 。對應地，有r個不同的核空間{ $H^{i}$ } $_{i=1}^{r}$ ,擴張的Hilbert space可以通過連接所有的核空間 $ilde{H}=oplus$ $_{i=1}^{r}H^{i}$ 。因此：

數據的映射（帶不同權重)

則組合的核函數為：

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

反覆更新 $Z,P,w$ ，最後達到最優。優化詳情見於論文。

Experiment

對於單核方法，作者比較了核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演算法。

實驗結果如下：

Conclusion

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