作者：Xiaobo Shen， Weiwei Liu， Ivor Tsang， Fumin Shen， Quan-Sen Sun

AAAI 2017

原文網址：Compressed K-Means for Large-Scale Clustering

轉載請註明出處：

注：以下文章包括原paper內容和筆記僅作者個人理解，如有錯誤或出入請指正。

Abstract

大規模聚類被廣泛用於多種運用，並得到了很多的關注。大多數現存的聚類方法運用到大規模資料集的時候會遇到高額的記憶體成本和計算量大的問題。在這篇論文中，作者提出了一個新穎的聚類方法應對快速大規模聚類，被稱之為compressed k-means（CKM）。高維的資料被壓縮成短的二進位制碼，這很好地適應於快速聚類。CKM演算法有兩大關鍵好處：1）透過用二進位制碼錶示資料點儲存量可以很大程度地減少；2）在二進位制碼間用Hamming度量會使得距離運算變得很有效率。同時作者在一個框架裡聯合學習了二進位制碼和聚類。

Introduction

聚類的目標是將一個數據集劃分到不同的組裡面，相似的資料點被安排到同一組。近幾十年來，隨著網際網路的出現，資料量急劇增長。傳統聚類方法比如譜聚類不能直接引用到大規模資料集是因為它們的計算成本高。相反，k-means聚類更經常被運用於大規模聚類是因為它的簡單性和普遍適應性。k-means聚類過程中每次迭代有兩個步驟：更新聚類中心；更新每個資料點的分配。這個過程所需計算複雜度為

O(nkd)

，n為資料集大小，k為聚類數量，d為維度。但從根本上來說，直接將k-means演算法運用到大規模資料集上是很具挑戰性的。解決大規模聚類有兩大主要的挑戰：1）怎樣降低大資料的儲存；2）怎樣降低聚類方法的計算成本。

二進位制碼學習在很多大規模運用上得到了很大的關注。二進位制碼學習的主要思想是將原來高維的資料編碼到一個短二進位制碼集合，並保留其相似性。二進位制編碼的好處是在Hamming space可以以很低的儲存和計算成本執行有效的搜尋。之前的二進位制碼學習方法都是用於促進大規模檢索和分類，而不是聚類。15年有一個工作是在二進位制碼上執行聚類，這是一個簡單的兩步方法，產生二進位制碼和執行聚類的過程是分開的。實際上，這個方法產生的二進位制碼對於聚類可能不是最優的。據我們所知，在聚類中對二進位制碼學習的研究還不是很充分，這仍然是一個很具挑戰的領域。對於大規模聚類，作者提出了一個新穎的壓縮k-means方法（CKM）。CKM的目標是同時學習二進位制碼和聚類。CKM的優點在於比其他傳統聚類方法有更低的計算成本和儲存成本。

Contributions

1）作者提出了一個基於聚類方法的新穎二進位制編碼，叫做壓縮k-means方法（CKM），這是將高維資料壓縮成短的二進位制碼。CKM方法可以以低的計算成本和儲存成本被運用到大規模聚類。

2）CKM方法同時學習了二進位制碼和聚類，以致於學習後的二進位制碼對於聚類是最優的。同時受到結構預測新進展的啟發，作者提出了一個最佳化演算法經驗損失的上限。

3）相對比目前的大規模聚類方法，在四個大規模資料集上的實驗表明CKM方法更快且所需的記憶體更少。

The Proposed Compressed K-means Method

Background

存在資料集

X=[x_{1},...,x_{n}]

，對應

K

個聚類{

C_{j}

}

_{j=1}^{k}

。

k-means方法旨在最小化以下的目標函式：

(Large-Scale Clustering論文)CKM

G表示為指示矩陣，

G=[g_{1},...,g_{n}]

\in

{0，1}

^{k*n}

；如果

x_{i}

屬於

C_{j}

聚類，

g_{ij}

=1；否則

g_{ij}

=0是其它情況（

g_{i}

向量中只有一個1，其它元素為0）。

\Psi

表示這樣的指示矩陣集合。

c_{j}

表示資料集的

j

箇中點。

實際上，k-means是組合最佳化問題，是很難去解決的！作者在論文中利用了二進位制編碼技術有效地把k-means運用到大規模資料集上。

Problem Formulation

資料矩陣

X\in

R^{d*n}

，作者目標是學習一個對映b（x），將d維的實值輸入

x\in

R^{d}

對映到r維的二進位制碼

h\in

H

\equiv

{-1，1}

^{r}

。寫成二進位制編碼函式如下：

(Large-Scale Clustering論文)CKM

f（x，W）：

R^{d}\rightarrow

R^{r}

的實值轉換（W

\in

R^{d*r}

），為簡便起，

f(x)=W^{T}x

。

二進位制碼

h,e\in

H

之間的距離可寫為：

(Large-Scale Clustering論文)CKM

對於在Hamming space裡的k-means聚類方法，作者定義了第

i

個數據點的損失函式為：

(Large-Scale Clustering論文)CKM

這裡的

C=[c_{1},...,c_{k}]

\in

{-1，1}

^{r*k}

。

因此CKM的目標函式可定義如下：

(Large-Scale Clustering論文)CKM

\nu\in

R^{+}

，是一個正的正則化引數，用於限制

W

的範圍。

跟傳統k-means不同的是，CKM方法中的資料點和聚類中心都是雜湊成二進位制碼，這有助於讓作者在聚類過程中執行快速的距離計算。

式子

L

直接的整體最佳化是具有挑戰性的，是因為1）該目標函式是高非凸性的；2）

b(x,W)

是一個離散的對映。

受到隱結構SVMs的啟發，作者研究了一種最佳化技術去最佳化

L

的上限。作者首先以結構化預測的形式重新表達二進位制編碼函式：

(Large-Scale Clustering論文)CKM

基於二進位制編碼函式的結構化預測形式，作者提出了關於第

i

個數據點的損失函式的上限定理：

定理1 對任意

\alpha>0

，第

i

個數據點的損失函式也就是

l(x_{i})

，有（這個上限可透過結構SVM匯出）：

(Large-Scale Clustering論文)CKM

基於定理1，可得以下替代後的目標函式：

(Large-Scale Clustering論文)CKM

Optimization部分詳情可見於論文。

整個演算法的虛擬碼如下：

(Large-Scale Clustering論文)CKM

Experiments

大規模實驗資料集：

(Large-Scale Clustering論文)CKM

對比演算法：

(Large-Scale Clustering論文)CKM

實驗結果：

(Large-Scale Clustering論文)CKM

(Large-Scale Clustering論文)CKM

(Large-Scale Clustering論文)CKM

(Large-Scale Clustering論文)CKM

(Large-Scale Clustering論文)CKM

(Large-Scale Clustering論文)CKM

實驗結果分別從Accuracy、Time、Memory Usage、Sensitivity Study以及Case Study做出了詳細的說明分析，見於論文。從計算成本和記憶體成本上說，作者提出的CKM演算法更勝一籌。

Conclusion

作者提出了一個新穎的壓縮k-means演算法，為聚類產生最優的二進位制碼。這篇論文關注於解決大規模資料集的快速聚類問題，實驗的結果表明CKM演算法能夠在有限的記憶體條件下進行快速聚類。論文還是值得一看！