原理部分主要來自大牛zouxy09和trnadomeet兩個(gè)人的博客；后面的代碼詳細(xì)講解為自己精心編寫

一、概述

?????????非監(jiān)督學(xué)習(xí)的一般流程是：先從一組無標(biāo)簽數(shù)據(jù)中學(xué)習(xí)特征，然后用學(xué)習(xí)到的特征提取函數(shù)去提取有標(biāo)簽數(shù)據(jù)特征，然后再進(jìn)行分類器的訓(xùn)練和分類。之前說到，一般的非監(jiān)督學(xué)習(xí)算法都存在很多hyper-parameters需要調(diào)整。而，最近我們發(fā)現(xiàn)對(duì)于上面同樣的非監(jiān)督學(xué)習(xí)流程中，用K-means聚類算法來實(shí)現(xiàn)特征學(xué)習(xí)，也可以達(dá)到非常好的效果，有時(shí)候還能達(dá)到state-of-the-art的效果。亮瞎了凡人之俗眼。

?????????托“bag of features?”的福，K-means其實(shí)在特征學(xué)習(xí)領(lǐng)域也已經(jīng)略有名氣。今天我們就不要花時(shí)間迷失在其往日的光芒中了。在這里，我們只關(guān)注，如果要K-means算法在一個(gè)特征學(xué)習(xí)系統(tǒng)中發(fā)揮良好的性能需要考慮哪些因素。這里的特征學(xué)習(xí)系統(tǒng)和其他的Deep Learning算法一樣：直接從原始的輸入（像素灰度值）中學(xué)習(xí)并構(gòu)建多層的分級(jí)的特征。另外，我們還分析了K-means算法與江湖中其他知名的特征學(xué)習(xí)算法的千絲萬縷的聯(lián)系（天下武功出少林，哈哈）。

?????????經(jīng)典的K-means聚類算法通過最小化數(shù)據(jù)點(diǎn)和最近鄰中心的距離來尋找各個(gè)類中心。江湖中還有個(gè)別名，叫“矢量量化vector quantization”（這個(gè)在我的博客上也有提到）。我們可以把K-means當(dāng)成是在構(gòu)建一個(gè)字典D?R^nxk，通過最小化重構(gòu)誤差，一個(gè)數(shù)據(jù)樣本x⁽ⁱ⁾?Rⁿ可以通過這個(gè)字典映射為一個(gè)k維的碼矢量。所以K-means實(shí)際上就是尋找D的一個(gè)過程：

?????? 這里，s⁽ⁱ⁾就是一個(gè)與輸入x⁽ⁱ⁾對(duì)應(yīng)的碼矢量。D^(j)是字典D的第j列。K-means畢生的目標(biāo)就是尋找滿足上面這些條件的一個(gè)字典D和每個(gè)樣本x⁽ⁱ⁾對(duì)應(yīng)的碼矢量s⁽ⁱ⁾。我們一起來分析下這些條件。首先，給定字典D和碼矢量s⁽ⁱ⁾，我們需要能很好的重構(gòu)原始的輸入x⁽ⁱ⁾。數(shù)學(xué)的表達(dá)是最小化x⁽ⁱ⁾和它的重構(gòu)D s⁽ⁱ⁾。這個(gè)目標(biāo)函數(shù)的優(yōu)化需要滿足兩個(gè)約束。首先，|| s⁽ⁱ⁾||₀<=1，意味著每個(gè)碼矢量s⁽ⁱ⁾被約束為最多只有一個(gè)非零元素。所以我們尋找一個(gè)x⁽ⁱ⁾對(duì)應(yīng)的新的表達(dá)，這個(gè)新的表達(dá)不僅需要更好的保留x⁽ⁱ⁾的信息，還需要盡可能的簡(jiǎn)單。第二個(gè)約束要求字典的每列都是單位長(zhǎng)度，防止字典中的元素或者特征變得任意大或者任意小。否則，我們就可以隨意的放縮D^(j)和對(duì)應(yīng)的碼矢量，這樣一點(diǎn)用都木有。

?????????這個(gè)算法從精神層面與其他學(xué)習(xí)有效編碼的算法很相似，例如sparse coding：

???????? Sparse coding也是優(yōu)化同樣類型的重構(gòu)。但對(duì)于編碼復(fù)雜度的約束是通過在代價(jià)函數(shù)中增加一個(gè)懲罰項(xiàng)λ|| s⁽ⁱ⁾||₁，以限制s⁽ⁱ⁾是稀疏的。這個(gè)約束和K-means的差不多，但它允許多于一個(gè)非零值。在保證s⁽ⁱ⁾簡(jiǎn)單的基礎(chǔ)上，可以更準(zhǔn)確的描述x⁽ⁱ⁾。

?????????雖然Sparse coding比K-means性能要好，但是Sparse coding需要對(duì)每個(gè)s⁽ⁱ⁾重復(fù)的求解一個(gè)凸優(yōu)化問題，當(dāng)拓展到大規(guī)模數(shù)據(jù)的時(shí)候，這個(gè)優(yōu)化問題是非常昂貴的。但對(duì)于K-means來說，對(duì)s⁽ⁱ⁾的優(yōu)化求解就簡(jiǎn)單很多了：

?????????這個(gè)求解是很快的，而且給定s求解D也很容易，所以我們可以通過交互的優(yōu)化D和s（可以了解下我博客上的EM算法的博文）來快速的訓(xùn)練一個(gè)非常大的字典。另外，K-means還有一個(gè)讓人青睞的地方是，它只有一個(gè)參數(shù)需要調(diào)整，也就是要聚類的中心的個(gè)數(shù)k。

二、數(shù)據(jù)、數(shù)據(jù)預(yù)處理

2.1數(shù)據(jù)：?

下載的CIFAR-10數(shù)據(jù)庫；其中的每個(gè)data_batch都是10000x3072大小的，即有1w個(gè)樣本圖片，每個(gè)圖片都是32*32且rgb三通道的，這里的每一行表示一個(gè)樣本。

提取40W個(gè)訓(xùn)練patches：

patches = zeros(numPatches, rfSize*rfSize*3);%400000*108

for i=1:numPatches

? if (mod(i,10000) ==0) fprintf('Extracting patch: %d / %d\n', i, numPatches);end

? r= random('unid', CIFAR_DIM(1) - rfSize +1);%從1到27中采用均勻分布提取數(shù)

? c= random('unid', CIFAR_DIM(2) - rfSize +1);

? %使用mod(i-1,size(trainX,1))是因?yàn)閷?duì)每個(gè)圖片樣本，提取出numPatches/size(trainX,1)=8個(gè)patch；每個(gè)size(trainX,1)=50000為一輪，提取8輪，總計(jì)40W個(gè)patches

?patch = reshape(trainX(mod(i-1,size(trainX,1))+1, :), CIFAR_DIM);%32*32*3

?patch = patch(r:r+rfSize-1,c:c+rfSize-1,:);%6*6*3

?patches(i,:) = patch(:)';%patches的每一行代表一個(gè)小樣本

end

相當(dāng)于在原始圖片上隨機(jī)抽取8個(gè)6*6的rgb 圖像patches。

為了建立一個(gè)“完備complete”的字典（至少有256個(gè)類中心的字典），我們需要保證有足夠的用以訓(xùn)練的patches，這樣每個(gè)聚類才會(huì)包含一定合理數(shù)量的輸入樣本。實(shí)際上，訓(xùn)練一個(gè)k-means字典比其他的算法（例如sparse coding）需要的訓(xùn)練樣本個(gè)數(shù)要多，因?yàn)樵趉-means中，一個(gè)樣本數(shù)據(jù)只會(huì)貢獻(xiàn)于一個(gè)聚類的中心，換句話說一個(gè)樣本只能屬于一個(gè)類，與其他類就毫無瓜葛了，該樣本的信息全部?jī)A注給了它的歸宿（對(duì)應(yīng)類的中心）。（以上分析來自zouxy09博客）。所以本文作者用40W個(gè)隨機(jī)patches，來訓(xùn)練108維的聚類特征。

2.2、預(yù)處理?Pre-processing

?????????給定多張圖片構(gòu)成的一個(gè)矩陣（其中每張圖片看成是一個(gè)向量，多張圖片就可以看做是一個(gè)矩陣了）。要對(duì)這個(gè)矩陣進(jìn)行whitening操作，而在這之前是需要均值化的。在以前的實(shí)驗(yàn)中，有時(shí)候是對(duì)每一張圖片內(nèi)部做均值，也就是說均值是針對(duì)每張圖片的所有維度，而有的時(shí)候是針對(duì)矩陣中圖片的每一維做均值操作，那么是不是有矛盾呢？其實(shí)并不矛盾，主要是這兩種均值化的目的不同。如果是算該均值的協(xié)方差矩陣，或者將一些訓(xùn)練樣本輸入到分類器訓(xùn)練前，則應(yīng)該對(duì)每一維采取均值化操作（因?yàn)閰f(xié)方差均值是描述每個(gè)維度之間的關(guān)系）。如果是為了增強(qiáng)每張圖片亮度的對(duì)比度，比如說在進(jìn)行whitening操作前，則需要對(duì)圖片的內(nèi)部進(jìn)行均值化（此時(shí)一般還會(huì)執(zhí)行除以該圖像內(nèi)部的標(biāo)準(zhǔn)差操作）。

在訓(xùn)練之前，我們需要對(duì)所有的訓(xùn)練樣本patches先進(jìn)行亮度和對(duì)比度的歸一化。具體做法是，對(duì)每個(gè)樣本，我們減去灰度的均值和除以標(biāo)準(zhǔn)差。另外，在除以標(biāo)準(zhǔn)差的時(shí)候，為了避免分母為0和壓制噪聲，我們給標(biāo)準(zhǔn)差增加一個(gè)小的常數(shù)。對(duì)于[0, 255]范圍的灰度圖，給方差加10一般是ok的：

樣本歸一化代碼：

patches = bsxfun(@rdivide, bsxfun(@minus,patches, mean(patches,2)), sqrt(var(patches,[],2)+10));

?

?????????對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行歸一化后，我們就可以在上面運(yùn)行k-means算法以獲得相應(yīng)的聚類中心了（字典D的每一列），可視化在圖a中，可以看到，k-means趨向于學(xué)習(xí)到低頻的類邊緣的聚類中心。但不幸的是，這樣的特征不會(huì)有比較好的識(shí)別效果，因?yàn)猷徲蛳袼氐南嚓P(guān)性（圖像的低頻變化）會(huì)很強(qiáng)。這樣K-means就會(huì)產(chǎn)生很多高度相關(guān)的聚類中心。而不是分散開聚類中心以更均勻的展開訓(xùn)練數(shù)據(jù)。所以我們需要先用白化來去除數(shù)據(jù)的相關(guān)性，以驅(qū)使K-means在正交方向上分配更多的聚類中心。

??????圖a是由k-means從沒有經(jīng)過白化處理的自然圖像中學(xué)習(xí)到的聚類中心。圖b展示了沒有和有白化的效果。左邊是沒有經(jīng)過白化的，因?yàn)閿?shù)據(jù)存在相關(guān)性，所以聚類中心會(huì)跑偏。右邊是經(jīng)過白化后的，可以看到聚類中心是更加正交的，這樣學(xué)習(xí)到的特征才會(huì)不一樣。圖c展示的是從經(jīng)過白化后的圖像patches學(xué)習(xí)到的聚類中心。

?????????實(shí)現(xiàn)whitening白化一個(gè)比較簡(jiǎn)單的方法是ZCA白化（可以參考UFLDL）。我們先對(duì)數(shù)據(jù)點(diǎn)x的協(xié)方差矩陣進(jìn)行特征值分解cov(x)=VDV^T。然后白化后的點(diǎn)可以表示為：

??????? ?_zca是一個(gè)很小的常數(shù)。對(duì)于對(duì)比度歸一化后的數(shù)據(jù)，對(duì)16x16的patch，可以設(shè)?_zca=0.01，對(duì)8x8的patch，可以設(shè)?_zca=0.1?。需要注意的一點(diǎn)是，這個(gè)常數(shù)不能太小，如果太小會(huì)加強(qiáng)數(shù)據(jù)的高頻噪聲，會(huì)使特征學(xué)習(xí)更加困難。另外，因?yàn)閿?shù)據(jù)的旋轉(zhuǎn)對(duì)K-means沒有影響，所以可以使用其他的白化變換方法，例如PCA白化（與ZCA不同只在于其旋轉(zhuǎn)了一個(gè)角度）。

在白化后的數(shù)據(jù)中運(yùn)行k-means可以得到清晰的邊緣特征。這些特征和sparse coding啊，ICA啊等等方法學(xué)到的初級(jí)特征差不多。如圖c所示。另外，對(duì)于新的數(shù)據(jù)，可能需要調(diào)整歸一化的參數(shù)?和白化的參數(shù)?_zca，以滿足好的效果（例如，圖像patches具有高對(duì)比度，低噪聲和少低頻波動(dòng)）。

數(shù)據(jù)白化代碼：

C = cov(patches);%計(jì)算patches的協(xié)方差矩陣

? M= mean(patches);

?[V,D] = eig(C);

? P= V * diag(sqrt(1./(diag(D) +0.1))) * V';%P是ZCA Whitening矩陣

? %對(duì)數(shù)據(jù)矩陣白化前，應(yīng)保證每一維的均值為0

?patches = bsxfun(@minus, patches, M) * P;%注意patches的行列表示的意義不同時(shí)，白化矩陣的位置也是不同的。

?

三、用kmeans算法獲取聚類中心

詳見：k-means聚類原理代碼分析

四、特征提取

?????????我們用K-means聚類算法來從輸入數(shù)據(jù)中學(xué)習(xí)K個(gè)聚類中心c^(k)。當(dāng)學(xué)習(xí)到這K個(gè)聚類中心后，我們可以有兩種特征映射f的方法。第一種是標(biāo)準(zhǔn)的1-of-K，屬于硬分配編碼：

??????這個(gè)f_k(x)表示樣本x的特征向量f的第k個(gè)元素，也就是特征分量。為什么叫硬分配呢，因?yàn)橐粋€(gè)樣本只能屬于某類。也就是說每個(gè)樣本x對(duì)應(yīng)的特征向量里面只有一個(gè)1，其他的全是0。K個(gè)類有K個(gè)中心，樣本x與哪個(gè)中心歐式距離最近，其對(duì)應(yīng)的位就是1，其他位全是0，屬于稀疏編碼的極端情況，高稀疏度啊。

第二種是采用非線性映射。屬于軟編碼。

??????這里z_k=||x-c^(k)||₂，u(z)是向量z的均值。也就是先計(jì)算出對(duì)應(yīng)樣本與k個(gè)類中心點(diǎn)的平均距離d，然后如果那些樣本與類別中心點(diǎn)的距離大于d的話都設(shè)置為0，小于d的則用d與該距離之間的差來表示。這樣基本能夠保證一半以上的特征都變成0了，也是具有稀疏性的，且考慮了更多那些距類別中心距離比較近的值。為什么叫軟分配呢。軟表示這個(gè)樣本以一定的概率屬于這個(gè)類，它還以一定的概率屬于其他的類，有點(diǎn)模糊聚類的感覺。而硬則表示這個(gè)樣本與哪個(gè)類中心距離最近，這個(gè)樣本就只屬于這個(gè)類。與其他類沒有任何關(guān)系。

特征提取代碼：

1 ，原始圖像數(shù)據(jù)拆分變換：

im2col函數(shù)：

該函數(shù)是將一個(gè)大矩陣按照小矩陣取出來，并把取出的小矩陣展成列向量。比如說B =im2col(A,[m n],block_type):就是把A按照m*n的小矩陣塊取出，取出后按照列的方式重新排列成向量,然后多個(gè)列向量組成一個(gè)矩陣。而參數(shù)block_type表示的是取出小矩形框的方式，有兩種值可以取，分別為’distinct’和’sliding’。Distinct方式是指在取出的各小矩形在原矩陣中是沒有重疊的，元素不足的補(bǔ)0。而sliding是每次移動(dòng)一個(gè)元素，即各小矩形之間有元素重疊，但此時(shí)沒有補(bǔ)0元素的說法。如果該參數(shù)不給出，則默認(rèn)的為’sliding’模式。

代碼：

patches = [ im2col(reshape(X(i,1:1024),CIFAR_DIM(1:2)), [rfSize rfSize]) ;?

? ? ? ? ? ? ? ? ? ?im2col(reshape(X(i,1025:2048),CIFAR_DIM(1:2)), [rfSize rfSize]) ;??????????????

? ? ? ? ? ? ? ? ? ?im2col(reshape(X(i,2049:end),CIFAR_DIM(1:2)), [rfSize rfSize]) ]';

最后，通過類似“卷積拆分”變換將原始圖像變?yōu)橐粋€(gè)729*108的矩陣，每行為原始圖像提取的6*6rgb? patch的向量表達(dá)；卷積塊總共移動(dòng)729次。

2 ，數(shù)據(jù)的標(biāo)準(zhǔn)化，白化處理

標(biāo)準(zhǔn)化

patches =

bsxfun(@rdivide,bsxfun(@minus, patches, mean(patches,2)), sqrt(var(patches,[],2)+10));

白化

patches = bsxfun(@minus, patches, M) * P;

?

3 ，特征提取

此處采用是采用非線性映射，屬于軟編碼。

??????這里z_k=||x-c^(k)||₂，u(z)是向量z的均值。也就是先計(jì)算出對(duì)應(yīng)樣本與k個(gè)類中心點(diǎn)的平均距離d，然后如果那些樣本與類別中心點(diǎn)的距離大于d的話都設(shè)置為0，小于d的則用d與該距離之間的差來表示。這樣基本能夠保證一半以上的特征都變成0了，也是具有稀疏性的，且考慮了更多那些距類別中心距離比較近的值。為什么叫軟分配呢。軟表示這個(gè)樣本以一定的概率屬于這個(gè)類，它還以一定的概率屬于其他的類，有點(diǎn)模糊聚類的感覺。而硬則表示這個(gè)樣本與哪個(gè)類中心距離最近，這個(gè)樣本就只屬于這個(gè)類。與其他類沒有任何關(guān)系。

計(jì)算樣本與k個(gè)中心的距離

xx = sum(patches.^2, 2);%729列，的列向量

cc = sum(centroids.^2, 2)';%1600列，的列向量

xc = patches * centroids';%729*1600的矩陣，

z = sqrt( bsxfun(@plus, cc, bsxfun(@minus,xx, 2*xc)) ); % distances = xx^2+cc^2-2*xx*cc;

z為729*1600的矩陣，z矩陣的每行為patches中一行（patches每行為一個(gè)rgb卷積塊6*6*3=108）與1600個(gè)聚類中心的距離。因?yàn)橐粋€(gè)原始圖片有729個(gè)卷積塊，每個(gè)卷積塊都與1600個(gè)卷積中心計(jì)算距離，所以有729*1600個(gè)距離。

?

軟編碼：

其實(shí)就是也就是先計(jì)算出對(duì)應(yīng)樣本與k個(gè)類中心點(diǎn)的平均距離d，然后如果那些樣本與類別中心點(diǎn)的距離大于d的話都設(shè)置為0，小于d的則用d與該距離之間的差來表示。

這樣基本能夠保證一半以上的特征都變成0了，也是具有稀疏性的，且考慮了更多那些距類別中心距離比較近的值。

mu = mean(z, 2); % 每個(gè)卷積塊與1600個(gè)中心的平均距離

patches = max(bsxfun(@minus, mu, z), 0);%patches中每一行保存的是：小樣本與這1600個(gè)類別中心距離的平均值減掉與每個(gè)類別中心的距離，限定最小距離為0；

a=[ -1 2 3]; max(a,0)=[0 2 3];%a中的元素與0比較；若小于0，取值為0，大于0取值本身

把patches從729*1600，變形為27*27*1600；上面的軟編碼實(shí)現(xiàn)了類似用6*6的卷積塊，卷積圖像的操作，1600個(gè)中心，相當(dāng)于1600個(gè)特征提取卷積塊。如圖

Patches的每列為：

根據(jù)卷積運(yùn)算圖像原則，一個(gè)卷積塊在原圖像上依次滑動(dòng)，也就是一個(gè)特征卷積提取整個(gè)圖像；按照這個(gè)原理，patches的每列應(yīng)該是每個(gè)一個(gè)聚類中心點(diǎn)（“卷積塊”），與原圖像每個(gè)卷積模塊求距離后，再進(jìn)行軟編碼。不應(yīng)該是上面原圖像的每個(gè)卷積塊，與1600個(gè)中心點(diǎn)求距離在進(jìn)行軟計(jì)算，這里有些不明白？

?

4pool操作

prows = CIFAR_DIM(1)-rfSize+1;

pcols = CIFAR_DIM(2)-rfSize+1;

patches = reshape(patches, prows, pcols,numCentroids);

pool代碼：

halfr = round(prows/2);

halfc = round(pcols/2);

q1 = sum(sum(patches(1:halfr, 1:halfc, :), 1),2);%區(qū)域內(nèi)求和，是個(gè)列向量，1600*1

q2 = sum(sum(patches(halfr+1:end,1:halfc, :), 1),2);

q3 = sum(sum(patches(1:halfr, halfc+1:end, :),1),2);

q4 = sum(sum(patches(halfr+1:end, halfc+1:end, :),1),2);

% concatenate into feature vector

XC(i,:) = [q1(:);q2(:);q3(:);q4(:)]';%類似于pooling操作

這么pool是為了數(shù)據(jù)降維，但是這是什么pooling方式，為什么用這種方式有些不明白。總之最后向量化后，就提取完特征了。

參考文獻(xiàn)：

Deep Learning論文筆記之（三）單層非監(jiān)督學(xué)習(xí)網(wǎng)絡(luò)分析

Deep learning：二十五(Kmeans單層網(wǎng)絡(luò)識(shí)別性能)

總結(jié)

以上是生活随笔為你收集整理的经典的K-means聚类算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。