基于非負矩陣分解和模糊C均值的圖像聚類方法

陶性留，俞 璐，王曉瑩

(1.陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007；2.陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007)

0 引言

隨著物聯(lián)網(wǎng)、電子商務(wù)等技術(shù)的廣泛應(yīng)用，可收集的數(shù)據(jù)越來越多，越來越復(fù)雜，數(shù)據(jù)特征的維度也越來越高。如何快速檢索有用的相關(guān)信息，越來越成為人們關(guān)注的熱點問題。聚類是機器學(xué)習(xí)和數(shù)據(jù)挖掘中的基礎(chǔ)課題之一，它的目的是將數(shù)據(jù)樣本劃分為不同的簇，使同一簇的數(shù)據(jù)樣本具有較高的相似性。到目前為止，很多研究提出了一些有效的聚類方法，例如K-means[1-2]、FCM[3-4]、SOM聚類[5]、層次聚類[6]、譜聚類(SC)[7-8]。

人們獲得的數(shù)據(jù)普遍具有如下兩個特點：(1)數(shù)據(jù)量龐大，檢索困難；(2)數(shù)據(jù)維數(shù)巨大，處理困難。雖然高維數(shù)據(jù)也許含有更多的信息，但將其直接用于分類、聚類或概率密度估計等任務(wù)，必將付出巨大的時間和空間代價。因此降維已經(jīng)成為許多數(shù)據(jù)挖掘問題的一種預(yù)處理手段。數(shù)據(jù)降維的本質(zhì)是尋找一個低維表示來反映原始數(shù)據(jù)的內(nèi)在特征，并使后續(xù)任務(wù)在這個低維表示上的工作量更低，同時泛化性能和識別率更高。通過利用非負矩陣分解(Non-negative Matrix Factorization, NMF)的獨特優(yōu)勢，不僅可以進行降維，而且物理意義明確，能夠很好地改善聚類的效率[9]。本文將NMF與模糊C均值算法相結(jié)合，提出了新的目標(biāo)函數(shù)。由交替迭代產(chǎn)生的新的低維表示矩陣可以用來描述樣本之間的本質(zhì)關(guān)系。與傳統(tǒng)聚類方法相比，本文算法提高了聚類效果。

1 相關(guān)工作

1.1 NMF算法[10]

s.t.W≥0,HT≥0

(1)

(2)

(3)

其中，⊙是Hadamard積運算符，代表矩陣對應(yīng)元素相乘。這時用系數(shù)矩陣HT代替原始矩陣，就可以實現(xiàn)對原始矩陣進行降維，從而減少存儲所占空間，減少計算所需資源。

1.2 模糊C均值聚類(FCM)

FCM算法是一種基于劃分的聚類算法，它的思想就是使得被劃分到同一簇的對象之間相似度最大，而不同簇之間的相似度最小。模糊C均值算法是普通C均值算法的改進，普通C均值算法對于數(shù)據(jù)的劃分是硬性的，而FCM則是一種柔性的模糊劃分。硬聚類把每個待識別的對象嚴格地劃分到某類中，具有非此即彼的性質(zhì)，而模糊聚類建立了樣本對類別的不確定描述，更能客觀地反映客觀世界。

1≤i≤c;1≤j≤n

(4)

1≤i≤c;1≤j≤n

(5)

1≤i≤c;1≤j≤n

(6)

FCM算法是一個交替迭代的過程，收斂后可以得到隸屬度矩陣U和聚類中心矩陣V。通過模糊聚類分析，每個樣本不再固定地屬于某一個類，可以得到不同樣本的不確定性，并可以從樣本到類別建立不確定性描述。

2 FCM-NMF算法

本節(jié)將描述FCM-NMF算法并給出多個更新規(guī)則。在較小的矩陣上運行NMF算法可以節(jié)省更多的時間和存儲空間，但也有可能破壞數(shù)據(jù)樣本之間的本質(zhì)結(jié)構(gòu)，影響聚類效果。為了減少負面影響，本文希望在NMF壓縮樣本數(shù)據(jù)的過程中進行模糊聚類。對于大量高維數(shù)據(jù)，通過NMF提取樣本的本質(zhì)特征，保留作FCM模糊分析聚類。將NMF分解對原始數(shù)據(jù)樣本的影響加入到FCM的目標(biāo)函數(shù)中。最小化以下代價函數(shù)：

(7)

其中，λ≥0是平衡系數(shù)，第一項表示模糊C均值對聚類的影響程度，第二項表示利用NMF算法處理原始數(shù)據(jù)的過程對聚類的影響程度。很明顯，式(7)的目標(biāo)函數(shù)是非凸的，解出它的全局最優(yōu)是不實際的。因此，利用交替迭代法則去探索非凸函數(shù)的局部最優(yōu)解是一個不錯的選擇。

通過迭代以下步驟來解決優(yōu)化問題，直到收斂:

(1)固定W、H、V，通過U最優(yōu)化J。U的更新準(zhǔn)則為:

i=1,2,…,c;j=1,2,…,n

(8)

(2)固定W、H、U，通過V最優(yōu)化J。V的更新準(zhǔn)則為:

i=1,2,…,c;j=1,2,…,n

(9)

(3)固定V、H、U，通過W最優(yōu)化J。W的更新規(guī)則與NMF算法一致，為:

(10)

(4)固定W、V、U，通過H最優(yōu)化J。將目標(biāo)函數(shù)J展開：

目標(biāo)函數(shù)J對hj偏導(dǎo)數(shù)：

其中，Aδ是控制梯度下降步長的參數(shù)。令

可以得到:

H最終的更新公式為：

(11)

FCM-NMF算法描述如下：

算法1:FCM-NMF輸入:原始非負矩陣X,模糊系數(shù)f,聚類個數(shù)c,平衡系數(shù)λ;輸出:基矩陣W,系數(shù)矩陣H,隸屬度矩陣U,聚類中心矩陣V;樣本的標(biāo)簽向量Y∈R1×n。1 隨機地初始化W和H;2 循環(huán);3 通過式(8)更新U,保持W、H和V固定;4 通過式(9)更新V,保持W、H和U固定;5 通過式(10)更新W,保持U、H和V固定;6 通過式(11)更新H,保持U、W和V固定;7 直到式(7)的目標(biāo)函數(shù)收斂;8 根據(jù)U,最終獲得樣本標(biāo)簽向量Y。

3 實驗結(jié)果與分析

3.1 實驗條件

為了驗證本文方法的有效性，本文在兩個標(biāo)準(zhǔn)圖像集進行實驗。一個是GHIM-10k 圖像集,另一個是Corel-10k圖像集。每個圖像集有10 000個圖像，都來自不同的種類。從每個數(shù)據(jù)集中隨機選取5個類別的500幅圖像作為驗證集。

對于每個驗證集，提取每幅圖像的灰色共生矩陣和顏色直方圖分別作為初始樣本矩陣X。與本算法對比的5類聚類算法分別是：①在初始矩陣X上運行K均值聚類；②在初始矩陣X上運行模糊C均值聚類；③在初始矩陣X上運行MEC聚類[12]；④在經(jīng)過NMF的系數(shù)矩陣H上運行K均值聚類；⑤在經(jīng)過NMF的系數(shù)矩陣H上運行模糊C均值聚類。所有這些算法都是在MATLAB R2014a中實現(xiàn)，所有實驗都是在Windows10下的8 GB內(nèi)存的Inter Core 2.81 GHz處理器上進行。將這些算法的最大迭代次數(shù)設(shè)置為10 000次，并在接下來的所有實驗中保持不變。圖1顯示了驗證集中部分樣本。

圖1 驗證集部分樣本圖像

3.2 評價標(biāo)準(zhǔn)

對于每個數(shù)據(jù)集，選取準(zhǔn)確率(ACC)、歸一化互信息(NMI)和F度量(F-measure)作為聚類效果的評價指標(biāo)。

準(zhǔn)確性是評價聚類結(jié)果質(zhì)量的一個特別重要的指標(biāo)，表達式如下：

(12)

其中，TP是指在同一個類中聚集的兩個文檔是正確分類的，TN是指在同一個類中聚集的兩個文檔是正確分開的。FP表示不應(yīng)該屬于一個類別的文檔應(yīng)該屬于錯誤的類別，F(xiàn)N表示不應(yīng)該被分開的文檔應(yīng)該屬于錯誤的類別。

聚類中常用NMI來衡量兩種聚類結(jié)果的接近程度。

(13)

式中，PAB(a,b)表示A和B的聯(lián)合概率分布，H(A,B)表示兩類結(jié)果的聯(lián)合熵。

F-measure是一種考慮到信息檢索的精度和召回程度，以便于不同技術(shù)或系統(tǒng)之間的結(jié)果進行比較的測量方法。

(14)

在式(14)中，P和R分別表示信息的精度和召回率。上述三個聚類評價指標(biāo)的取值均在0～1之間，指標(biāo)值越大，聚類效果越好。

3.3 實驗結(jié)果與分析

針對每種算法，分別進行20次實驗，并記錄實驗數(shù)據(jù)結(jié)果平均值。

表1和表2分別是提取了標(biāo)準(zhǔn)圖像數(shù)據(jù)集驗證集樣本的灰度共生矩陣與顏色直方圖特征進行數(shù)據(jù)集聚類的實驗結(jié)果。從表1和表2中可以看出，在選定的圖像集中，提取的灰色共生矩陣和顏色直方圖這兩種全局特征在與傳統(tǒng)聚類算法對比實驗中效果表現(xiàn)頗佳,尤其在準(zhǔn)確率和標(biāo)準(zhǔn)化互信息方面有比較大的改善。如表1所示，ACC與NMI值最高可達84%和77.21%。 本算法的聚類結(jié)果依賴于實驗中兩個參數(shù)的調(diào)節(jié)，一個是模糊系數(shù)f，另一個是平衡系數(shù)λ。模糊系數(shù)f值取決于樣本數(shù)據(jù)本身的統(tǒng)計數(shù)據(jù)[13]。大量的實驗表明，f值限于1.1與2.5之間[14]。而平衡系數(shù)λ是在數(shù)量級為10-1至102的范圍內(nèi)搜索得到的最優(yōu)解。

表1 通過提取灰度共生矩陣特征， 對實驗數(shù)據(jù)集進行聚類

表2 通過顏色直方圖特征提取對 實驗數(shù)據(jù)集進行聚類

從另一個角度來看，該算法克服了傳統(tǒng)K-means和FCM算法在聚類過程中因初始條件非唯一性導(dǎo)致的聚類結(jié)果不穩(wěn)定的問題。同時，由于乘法迭代的存在，該算法的收斂速度也很快。

4 結(jié)束語

本文的數(shù)據(jù)集需要滿足負值要求，這與實際情況一致，所以利用NMF方法在一定程度上是合理的。雖然NMF方法的初始化是隨機的，但隨著迭代的進行，聚類結(jié)果趨于穩(wěn)定。本文提出了FCM-NMF算法，并在實驗中證明了聚類的有效性。它利用NMF作為特征提取的手段，為了盡可能不破壞樣本之間的本質(zhì)聯(lián)系。結(jié)合NMF和FCM算法改變目標(biāo)函數(shù)的形式，生成新的低維表示矩陣。整個過程即通過NMF來改善高維無監(jiān)督聚類。

本文方法作為聚類方法具有以下優(yōu)點:(1)由于矩陣分解的靈活性，NMF過程可以模擬不同的數(shù)據(jù)分布，對于高維數(shù)據(jù)的優(yōu)點更加明顯；(2)只要分解過程不破壞原始數(shù)據(jù)的基本結(jié)構(gòu)[15]，NMF可以與現(xiàn)有的其他聚類方法結(jié)合，作為特征提取的框架；(3)樣本的FCM處理可以更好地描述樣品對類的隸屬度，丟失信息更少。下一步考慮將少量成對約束條件加入聚類過程中，利用半監(jiān)督聚類來進一步改善效果。