[讀論文]fast-and-provably-good-seedings-for-k-means

01-25

fast-and-provably-good-seedings-for-k-means

大家好我是zyy，本人是機器學習和深度學習的初學愛好者，想跟大家一起分享我的學習經驗，大家一起交流。我寫的東西不一定全對，但肯定是我一步一步走出來的坑，嚼爛了的經驗，可以供大家直接「吸收」

我的文章主要會涉及各種機器學習和深度學習演算法的推導和輪子的實現，以及一些小的應用demo，偶爾還會有一些論文的演算法實現。

文中出現的所有代碼都可以在我的GitHub上找到。

[GitHub]

這篇文章是今年，哦不，是去年nips上一篇關於k-means演算法改進的文章。

順便在此祝各位新年快樂，萬事如意，身體健康。

順便抱怨一句，越來越看不懂現在看客們的口味了，那些一篇速成xxx、XXX預測模型（其實就是簡單模型套用不知哪來的數據）、一篇文章看懂XXX、簡析XXX（翻來覆去的演算法來回說）大行其道，真是心涼。所以我決定，從這片開始，封面放小黃圖，以吸引各位看官(? ??_??)?

哦對了，我還要做個廣告，我最近翻譯了吳恩達Andrew Ng的新書《Machine Learning Yearning》（他還在寫，我也還在繼續翻譯），是一本用在工業界的機器學習參考書，是大家非常好的廁所讀物，鏈接在此。

k-means

先說說最簡單的k-means演算法。

k-means是最簡單的聚類演算法之一，主要思想是，隨機初始化 $k$ 個中心點，一個中心點代表一類，計算數據點到各中心點的距離，將離數據點最近的中心點定位該數據點的類別，之後計算每一類點的中心位置，為新的中心點位置，迭代一定次數後，中心點位置會趨於收斂，由此得到聚類的位置。

演算法步驟如下：

隨機選擇 $k$ 個中心點 $C={c_1,c_2,...,c_k}$ ;
令離 $c_i$ 最近的數據 $X$ 為聚類簇 $C_i$ ，其中 $i=1,2,3...,k$ ;
令 $c_i$ 為每個聚類簇的中心 $c_i=frac{1}{|C|}sum_{xin C_i}{x}$ ;
重複2和3直至 $C$ 不再變化。

k-means演算法也算是EM應用，一種特殊的GMM模型，只不過簡化了需要估計的參數和對類別的判斷，從一個軟分類的概率判斷（看屬於哪個類的概率大）變成了直接找最近的指示函數。話說起來，好像EM那篇還沒寫完...

咳咳，言歸正傳。顯而易見，我們最初選擇的初始位置，會很大程度影響這個演算法準確度和收斂程度，所以，我們又有了k-means++。

k-means++

k-means++: The Advantages of Careful Seeding 這篇文章提出了一種基於採樣方法的中心點初始化方法。具體做法的思想是選取使各個中心點儘可能地遠離，來減少由於中心點相鄰而導致的誤差（也不算是誤差，錯誤？大概是這個意思，筆者語文學的還不如英語）。

具體的做法就是隨機先選取一個初始中心點，然後計算各個數據點到這個中心點的距離，最後用距離做比值，隨機抽取一個點，此時抽取的點，有很大概率離初始化的中心點較遠，重複此步驟，然後按k-means來迭代，直至收斂。

演算法步驟如下：

任意選取一個數據點作為中心點 $c_1$ ;
以 $frac{D(x)^2}{sum_{xin X}D(x)^2}$ 的概率選取其餘的中心點 $c_i$ ;
重複2直到選滿 $k$ 個中心點
其餘步驟與標準k-means相同

這個方法稱為 $D^2-sampling$ 。這麼做可以很大程度上避免初始選初始選中心點的問題。

近似k-means++

k-means++的好處我們已經提了，但仍然存在很多問題：計算複雜度。隨著 $k$ 的增加和樣本數量的增大，在計算距離的時候，計算量會逐步增加。所以又有人提出了近似k-means++的演算法，Approximate K-Means++ in Sublinear Time這篇文章，用MCMC的方法來近似抽樣選擇中心點，用Metropolis-Hastings來進行採樣中心點。隨機選取一個中心點 $c_1$ ，然後用MCMC的方法採樣出長為 $m$ 的數列，取最後 $k-1$ 個數作為中心點，採樣分布為 $p(x)=frac{D(x)^2}{sum_{xin X}D(x)^2}$ ，其中提案分布選擇 $q(x)=frac{1}{n}$ 來簡化，剩下部分與傳統k-means相同。

具體演算法步驟如下：

隨機選出第一個中心點 $c_1$ ；
隨機抽取一個數據點 $x$ 並計算距離 $d_x$ ；
用MH採樣出一個長為 $m$ 的序列，取最後 $k-1$ 個作為中心點；
其餘步驟與k-means相同。

由此可見，計算複雜度從 $O(nd)$ 到 $O(mk^2d)$ ，這樣就允許有更多的數據參與聚類，這在圖像領域極為有用。

改進的k-mc^2

終於講到老大哥了，每次寫東西，要講的東西總是寫到最後了，下次開個專題梳理基礎。

Fast and Provably Good Seedings for k-Means這篇文章跟上面那篇是同一撥人，恩，同一撥人搞得同一個大事情，挺有才的，一篇發了AAAI，一篇發了nips，不得不說，厲害了我的哥。

這篇也沒幹別的事情，換了一個提案分布 $p(x|c_1)=frac{1}{2}frac{d(x,c_1)^2}{sum_{x$ ，可以滿足更多數據分布假設下的魯棒性，同時還有一系列的優點。

不要問我優點是啥，都是理論上的優點以及在數據集上表現好的優點。喜歡理論或者學CS的同學可以自己download下來自己仔細看看，我也不在這仔細說了（我才不會說筆者看不懂這些理論證明呢 (。?`ω′?)，PAC那些還是留給專業人員去琢磨吧，我就不摻和了）。

以及，這兩篇文章的作者提供了一個python庫，是拿C寫的，python可以調，大家可以下下來用一下，這是github地址。

Reference

Arthur D, Vassilvitskii S. k-means++: The advantages of careful seeding[C]//Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2007: 1027-1035.
Bachem O, Lucic M, Hassani S H, et al. Approximate K-Means++ in Sublinear Time[C]//AAAI. 2016: 1459-1467.
Bachem O, Lucic M, Hassani H, et al. Fast and Provably Good Seedings for k-Means[C]//Advances in Neural Information Processing Systems. 2016: 55-63.
Celebi M E, Kingravi H A, Vela P A. A comparative study of efficient initialization methods for the k-means clustering algorithm[J]. Expert Systems with Applications, 2013, 40(1): 200-210.