深度学习（二十四）矩阵分解之基于k-means的特征表达学习
矩陣分解之基于k-means的特征表達學習
原文地址：http://blog.csdn.net/hjimce/article/details/50429317
作者：hjimce
一、相關理論
? ? ?因為最近搞的項目，要么沒有數據、要么訓練數據很少，精度老是提高不上去，另一方面最近看到網上一篇推薦文章:《Convolutional Clustering for Unsupervised Learning》，于是就操起家伙，學習CNN無監督學習方面的文章，看能不能把精度提高上去。
? ?本篇博文主要講解2012年大神吳恩達他們曾發表的一篇paper:《Learning?Feature?Representations?with?K-means》。可能大家對于k均值聚類，這個算法之前已經非常熟悉了，覺得這個算法是一個很簡單的算法，估計會覺得沒什么可以學的東西，因此對其不感興趣。然而其實很多人只是表層理解的k-means算法，對于k-means怎么用于圖片分類無監督特征表達學習、k-means與矩陣分解的關系、與壓縮感知相關理論之間的關系，卻極少有人去深究理解。曾經的我，看到這篇文獻題目的時候，曾心想:“這種文獻肯定很水，連k-means這種算法也好意思拿出來發表文章”。好吧，這也許就是所謂的：坐井觀天，慚愧啊。人生只有意識到自己是菜鳥的時候，才會去努力，才會進步。
? ?本篇博文我將從k-means與矩陣分解開始講起，矩陣分解推導部分主要參看文獻：《k-Means Clustering Is Matrix Factorization》，對公式的推導過程不感興趣的可以跳過，個人感覺推導公式枯燥乏味。矩陣分解部分是為了對k-means有進一步的了解。因為后面要講的特征表達學習，文獻給出的公式也是一個矩陣分解的公式。第三部分，我們將詳細講解文獻：《Learning?Feature?Representations?with?K-means》，深入學習如何利用k-means算法進行圖片特征學習，并提高圖片分類的精度，領略k-means的牛逼之處。
二、k-means與矩陣分解
這幾天剛好看到這篇paper：《k-Means Clustering Is Matrix Factorization》，因此就用這篇文獻進行思路講解。最近突然領悟到矩陣分解威力好強大，好多機器學習的算法都根源于矩陣分解，如PCA、NMF、ICA、LDA、稀疏編碼等，所以就決定對矩陣分解的奧義做一個總結，決定寫一個系列博文，做一個總結，不然算法一多，就會亂掉。下面的的講解，主要翻譯自文獻：《k-Means Clustering Is Matrix Factorization》。
1、k-means算法回顧
k均值算法可以說是機器學習中，最常用的一個聚類算法，給定數據集X∈Rm，我們的目的就是把它們分成C1，C2……CK，其中k就是我們要聚類的個數。我們知道k-means算法的原理就是最小化下面的函數：
?
其中，xj是每一個數據點，ui是聚類中心，當xj聚類為Ci時，那么zij的值就是1，如果不是那么就是為0，即：
?
2、證明
（1）證明題目
開始前我們先明確一下我們的目標，我們的目標是證明k-means的目標函數可以被分解成如下矩陣形式：
?
其中，X是數據樣本矩陣，每一列表示一個樣本。M是聚類中心矩陣，它的每一列就是我們的聚類中心ui，Z表示一個編碼矢量：
?
就像上初中的時候，考試考證明題一樣，我們的目標就是要證明上面的等式成立。也就是k-means的過程就相當于矩陣分解的過程。如果對證明過程不感興趣的可以跳過，因為證明過程確實是挺枯燥的。而且這也不是本篇博文的重點，這只是為了讓大家先對k-means的求解其實是可一個歸結為一個矩陣分解問題的。
(2)定義
為了后面推導方便起見，我們先對一些代號，做一下定義。我們定義：數據樣本矩陣X，X的每一列表示一個樣本xj，我們把矩陣X的L2范數定義為所有樣本向量的長度平方和，即：
?
OK,啰嗦了這么多，我們要大干一場了，下面開始證明等式：
?
成立。
(3)證明成立
我們先把等式左邊展開：
?
然后上面的T1、T2、T3項我們可以進一步化簡為：
?
?
我們把等式右邊也展開：
?
這個時候，我們可以看到T4=T1，T2=T5。因此接著我們只需要證明:T3=T6，證明過程如下：
T6項等價于：
據此，我們可以進一步推導：
?
其中Z*Z^T是一個對角矩陣。至此T3=T6證明成立，因此我們最后所要證明的等式也就成立了，證畢。
啰嗦了這么多，無非就是想要說一句話：k-means也是一個矩陣分解的求解過程。
三、特征表達學習
? ? OK，言歸正傳，前面啰嗦了一大堆，僅僅只是為了說明一個問題：k-means的求解過程是一個矩陣分解的過程。本部分要講的利用k-means做特征學習，才是我們要關注的東西。接著我們要講的東西就是文獻：《Learning?Feature?Representations?with?K-means》到底是怎么實現無監督特征學習。本部分同時也參考了前輩zouxy的博文：http://blog.csdn.net/zouxy09/article/details/9982495?，感謝前輩。
? ? 開始前先要講一下spherical?K-means算法，這個算法與我們平時學到的k-means算法稍微有點不同，是k—means算法的一個進化版。所以需要先熟悉一下這個算法。spherical?K-means故名思議，意思應該是我們的數據點集全部分布在一個球面上，然后進行聚類。因此在采用這個算法的時候，需要對每個數據點歸一化處理，使得我們要聚類的數據，分布在一個球面上，然后我的個人理解這一個球面聚類，應該是用了余弦相似度度量替代了歐式距離度量（具體沒有細看，只是個人淺薄理解，可能有誤）。
1、字典與矢量量化
首先文獻采用的k—means算法是：spherical?K-means，其滿足如下條件：
?
其中，D我們由稱之為字典，字典這個詞把我難住了，我不是信息專業的，從沒聽過字典，好高大上的名字。然而其實說白了D就是一個變換矩陣。D(j)就是表示D的第j每一列，D的每一列就是我們k均值的聚類中心向量，因為我們的聚類是在單位球面上，所以聚類中心的模長等于1。
S又稱之為特征向量編碼，當D的第j列（聚類中心）與x(i)最近的時候，s(i)對應的元素不為0，其余全部為0。這個就是對x(i)的一個編號罷了，比如我們對X進行聚類，聚類為5個類，最后如果xi被聚類為第3個類別，那么編碼矢量si=（0,0,1,0,0）。編碼這個詞聽起來好像也有點牛逼的樣子，其實我們也可以把s理解為特征。而k-means特征提取的過程，說白了就是計算s。
???K-mean無監督學習的過程，說白了就是為了學習字典D，也就是每個聚類中心。然后當我們輸入一個新數據x的時候，我們就用D去計算S，計算公式如下：
?
簡單理解一下上面的那個符號：argmax。因為我們是在一個球面上，兩點間如果最近，那么Dj*Xi應該是最大的(點積、余弦)。
2、算法流程
至今為止，我們都還沒扯到圖像，扯到圖像的特征學習，接著我們就要開始結合實際應用，講訴k-means的特征學習過程。
（1）數據獲取
對于圖像，我們要如何進行k-means無監督特征學習？我們從一堆的圖片中，隨機的抽取出一大堆的圖片塊（16*16大小的塊），然后把這些16*16的圖片塊（這個是灰度圖），拉成一個一維的向量xi，也就是256維的特征向量，這就是我們的訓練數據了。文獻抽取出了100000個16*16的圖片塊，進行字典學習。
（2）數據預處理
a、亮度和對比度歸一化。采用如下公式對樣本xi進行歸一化：
?
這個簡單，搞過機器學習的人都知道，上面公式分母加了一個數：10，是為了避免除數是0。
b、白化
這個我們可以采用PCA白化也可以采用ZCA白化，不過我們需要注意的是：白化的過程對于我們的結果非常重要，所以千萬不要忘了白化。這個文獻對是否采用白化進行了對比：
?
左邊是沒用使用白化，聚類出來的中心。右邊則是我們采用白化，學習得到的字典。
(3)最后就是spherical?k-means的聚類過程了。
最后算法總流程如下：
3、圖片識別應用
前面我們介紹了，給定一堆無標簽圖片，我們通過K-means算法，進行學習字典D。接著我們就要知道它具體是怎么用于圖片識別分類的。下面是算法的總流程：
(1)通過無監督學習，學習到一系列的字典D。
(2)接著我們利用學習到的字典，把一張輸入圖片，進行函數映射：
我們可以把這個過程看成是卷積，比較容易理解。這個映射過程不一定是非重疊的。
(3)采用pooling進行降維。
(4)如果是構建多層網絡，那么就重復上面的過程。如果單層網絡，那么我們就后面接一個分類器，比如svm。
后面就不再細講了，個人感覺：http://blog.csdn.net/zouxy09/article/details/9982495?講的很好，覺得自己再怎么細講，也沒有前輩講的很細，自嘆不如啊，所以本篇博文到此結束。
參考文獻：
1、《k-Means Clustering Is Matrix Factorization》
2、《Learning?Feature?Representations?with?K-means》
3、http://blog.csdn.net/zouxy09/article/details/9982495?
4、《An Analysis of Single-Layer Networks in?Unsupervised Feature Learning》
5、《Convolutional Clustering for Unsupervised Learning》
**********************作者：hjimce ? 時間：2015.12.12 ?聯系QQ：1393852684 ? 地址：http://blog.csdn.net/hjimce? ?原創文章，版權所有，轉載請保留本行信息（不允許刪除）
總結
以上是生活随笔為你收集整理的深度学习（二十四）矩阵分解之基于k-means的特征表达学习的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 深度学习（二十三）Maxout网络学习-
- 下一篇： 深度学习（二十五）基于Mutil-Sca