基于局部相似性的非平滑非負(fù)矩陣分解

張逸群，彭 沖

(青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，青島 266071)

隨著網(wǎng)絡(luò)信息時(shí)代的到來，人們?cè)谑褂没ヂ?lián)網(wǎng)時(shí)產(chǎn)生了海量的數(shù)據(jù)，這些數(shù)據(jù)可以使用高維矩陣形式存儲(chǔ)于計(jì)算機(jī)中。處理高維數(shù)據(jù)矩陣時(shí)，矩陣分解算法可以找到兩個(gè)或多個(gè)低維矩陣來近似原始數(shù)據(jù)，用低維數(shù)據(jù)來表示高維數(shù)據(jù)，這項(xiàng)技術(shù)廣泛應(yīng)用于圖像識(shí)別、信號(hào)識(shí)別和視頻處理等領(lǐng)域[1]。針對(duì)條目為非負(fù)元素的數(shù)據(jù)如圖像和文檔，非負(fù)矩陣分解(Nonnegative Matrix Factorization，NMF)算法尋求兩個(gè)非負(fù)的因子矩陣，使二者乘積可以逼近原始矩陣[2]。在面部識(shí)別問題中，學(xué)習(xí)的基礎(chǔ)圖像是局部的而不是整體的，類似于面部某個(gè)抽象的部分，將基矩陣和系數(shù)矩陣進(jìn)行線性組合即可由部分組成整體[2]。因此NMF算法在表示原有數(shù)據(jù)信息時(shí)所需數(shù)據(jù)元素更少，存儲(chǔ)數(shù)據(jù)所需空間資源就更少，便于簡(jiǎn)化計(jì)算。該算法的非負(fù)約束能使分解所得矩陣具有隨機(jī)稀疏性即局部特征更加明顯，若要保證更穩(wěn)定的稀疏性，還需要添加相應(yīng)的約束條件[3]。Liu等[4]基于Hoyer[5]提出的非負(fù)稀疏編碼方法，引入KL散度，提出稀疏非負(fù)矩陣分解(Sparse Nonnegative Matrix Factorization)。Hoyer[6]在此基礎(chǔ)上又引入一種非線性稀疏函數(shù)來約束分解后矩陣的稀疏性。上述算法單獨(dú)對(duì)基向量與編碼向量稀疏性進(jìn)行約束，而由于矩陣分解后兩個(gè)矩陣“相乘”的性質(zhì)，施加稀疏約束一般只能使其中一個(gè)矩陣具有稀疏性。基于此問題，非平滑非負(fù)矩陣分解算法(Non-smooth Nonnegative Matrix Factorization，nsNMF)在目標(biāo)函數(shù)中引入了一個(gè)“平滑”矩陣，使基矩陣和編碼矩陣都具有稀疏性[7]。該算法假設(shè)數(shù)據(jù)都是線性分布的，如果數(shù)據(jù)分布在非線性結(jié)構(gòu)例如流形結(jié)構(gòu)時(shí)，聚類效果會(huì)受到影響。實(shí)際應(yīng)用中，高維數(shù)據(jù)通常駐留在低維子空間中，恢復(fù)這些子空間需要一個(gè)自我表達(dá)性假設(shè)?，F(xiàn)有研究表明，數(shù)據(jù)內(nèi)的局部結(jié)構(gòu)非常重要[8]。本文提出一種新的非平滑非負(fù)矩陣分解算法，將局部相似性學(xué)習(xí)作為約束項(xiàng)整合到算法模型中，同時(shí)加入核函數(shù)，以期解決數(shù)據(jù)線性不可分時(shí)聚類效果差的問題。

1 相關(guān)工作介紹

經(jīng)典NMF算法無法控制分解后矩陣的稀疏程度，無法有效挖掘數(shù)據(jù)間的幾何結(jié)構(gòu)。nsNMF可以保證稀疏性，但沒有考慮數(shù)據(jù)間的幾何結(jié)構(gòu)。本文提出基于局部相似性的非光滑非負(fù)矩陣分解算法，通過局部相似性約束項(xiàng)和核函數(shù)，深度挖掘原始數(shù)據(jù)間的幾何結(jié)構(gòu)，提高聚類精度。

1.1 局部相似性

高維數(shù)據(jù)通常會(huì)駐留在低維子空間中，恢復(fù)這些子空間通常需要一個(gè)自我表達(dá)性的假設(shè)，即數(shù)據(jù)可以用表示矩陣Z和原矩陣X的乘積來近似表示原數(shù)據(jù)X，表示為

X≈XZ

(1)

將數(shù)據(jù)限制為列的凸組合，如果兩個(gè)數(shù)據(jù)點(diǎn)xi和xj彼此接近，那么它們的相似性Zij應(yīng)該很大；否則，Zij應(yīng)該很小[9-10]。因此引出如下優(yōu)化問題。

(2)

用矩陣形式可以表示為

(3)

其中，1n代表長(zhǎng)度為n，元素全為1的向量；diag()代表取括號(hào)內(nèi)矩陣的對(duì)角矩陣；Tr()代表括號(hào)內(nèi)矩陣的跡。由于本文的基本問題是將X分解為X*W*VT，因此用W*VT來代替Z，再引入上文所述的平滑矩陣S，因此得到Z=WSVT。

1.2 nsNMF

非平滑非負(fù)矩陣分解引入了一個(gè)平滑矩陣，將數(shù)據(jù)矩陣X進(jìn)行如下分解

X=USVT

(4)

引入的平滑矩陣用S表示

(5)

其中，I是單位矩陣，參數(shù)θ取值范圍滿足0≤θ≤1，q為矩陣的列數(shù)。當(dāng)θ=0時(shí)，式(5)為普通NMF算法；當(dāng)θ=1時(shí)，S與其他任意的矩陣相乘，得到的矩陣具有如下性質(zhì)：矩陣中的元素是與S相乘的矩陣的均值。由于S的平滑性，即可使得基矩陣U和編碼矩陣V具有一定的稀疏性。

2 本文算法

2.1 目標(biāo)函數(shù)

首先，算法的目標(biāo)函數(shù)為

(6)

將目標(biāo)函數(shù)展開，得

O=Tr[φ(X)Tφ(X)]-2Tr[φ(X)Tφ(X)WSVT]+Tr[φ(X)Tφ(X)WSVTVSTWT]+λTr(WTDVST)

(7)

2.2 目標(biāo)函數(shù)的迭代求解

設(shè)計(jì)乘性迭代算法來迭代求解W和V，目標(biāo)的拉格朗日方程表示為

L=O+Tr(ΩWT)+Tr(ΨVT)

(8)

其中，Ψ=[ψij]，Ω=[φij]是兩個(gè)矩陣，ψij和φij分別是約束uij≥0,vij≥0的拉格朗日乘子。將W和V取偏導(dǎo)，令φ(X)Tφ(X)=K[11]，得

(9)

(10)

由Karush Kuhn Tucker(KKT)條件及Ωijwij=0，ψijvij=0，得

(-2KVST+2KWSVTVST+λDVST)wij=0

(11)

(-2KWS+2VSTWTKWS+λDWS)vij=0

(12)

整理式(12)得到如下迭代規(guī)則

(13)

(14)

此迭代規(guī)則概括為算法1：

輸入：原始數(shù)據(jù)X，初始化W和V，模型的參數(shù)λ，平滑矩陣參數(shù)θ。

(1) 設(shè)置最大的迭代次數(shù)和閾值,開始迭代計(jì)算；

(2) 設(shè)置t=1，計(jì)算目標(biāo)函數(shù)值，判斷是否收斂；

(3) 根據(jù)式(17)計(jì)算W；

(4) 根據(jù)式(18)計(jì)算V；

(5)t=t+1,跳轉(zhuǎn)至第二步直到收斂；

返回W，V。

3 實(shí)驗(yàn)結(jié)果與分析

對(duì)比實(shí)驗(yàn)在MatlabR2018a，Intel(R)Core(TM)i5-8500T CPU環(huán)境下完成。對(duì)比算法選取經(jīng)典的NMF[2]算法及其變體RMNMF[12]、CNMF[10]和ONMF[13]。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

選取3個(gè)開源數(shù)據(jù)集，包括1個(gè)手寫數(shù)字?jǐn)?shù)據(jù)集Semeion[14](收集約80人書寫的1 593個(gè)手寫數(shù)字，掃描拉伸尺寸為16×16)，兩個(gè)人臉圖像數(shù)據(jù)集Jaffe[15](收集10名日本女性拍攝的含有7種面部表情圖片，共213張，每張像素為26×26)和PIX10[16](包含10名拍攝者100張灰度圖像，每名拍攝者包含10張100×100像素的圖片)。上述數(shù)據(jù)集的圖像經(jīng)處理后以灰度值形式存于二維矩陣中，受篇幅所限，僅展示部分?jǐn)?shù)據(jù)集，如圖1所示。

圖1 三種數(shù)據(jù)集(a)Semeion數(shù)據(jù)集；(b)Jaffe數(shù)據(jù)集；(c)PIX數(shù)據(jù)集

3.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

選用Accuracy(ACC)、Normalized Mutual Information(NMI)、Purity這三種評(píng)價(jià)指標(biāo)[17]來衡量圖像聚類效果。ACC：對(duì)于實(shí)例xi，令li,ti分別為聚類所得標(biāo)簽和真實(shí)標(biāo)簽其中，n為數(shù)據(jù)集中實(shí)例樣本數(shù)量；當(dāng)x=y時(shí)，Delta函數(shù)δ(x,y)值為1，在其他情況下為0。

(15)

(16)

(17)

Purity：測(cè)量每個(gè)集群包含主要來自一個(gè)類的數(shù)據(jù)點(diǎn)的程度。聚類解的純度是作為單個(gè)聚類純度值的加權(quán)和，表示為

(18)

(19)

其中，Si是一個(gè)大小為ni的特定簇，nij是分給第j個(gè)類的第i個(gè)輸入類的樣本數(shù)量，K是類數(shù)量，n是點(diǎn)總數(shù)。一般來說，純度值越大，聚類結(jié)果就越好。

3.3 聚類結(jié)果

本文所提算法與其他四種算法在三種數(shù)據(jù)集上的聚類效果對(duì)比見表1～表3?？芍?，在Jaffe數(shù)據(jù)集上，本文算法除RMNMF外聚類效果最佳，ACC提高3%～19%，NMI提高1%～18%，Purity提高3%～14%；在Semeion數(shù)據(jù)集上，本文算法聚類效果最佳，ACC提高2%～10%，NMI和Purity提高4%～15%；在PIX數(shù)據(jù)集上，本文算法聚類結(jié)果也最佳，三種聚類指標(biāo)都提高3%～18%。同時(shí)，新算法在三種數(shù)據(jù)上的聚類性能比較穩(wěn)定，其他算法穩(wěn)定性較差。RMNMF雖然在樣本相對(duì)簡(jiǎn)單的Jaffe數(shù)據(jù)集上聚類結(jié)果最佳，優(yōu)于本文算法，但在其他兩種數(shù)據(jù)集上的聚類效果低于本文算法約10%。這說明實(shí)驗(yàn)中不同數(shù)據(jù)集對(duì)會(huì)算法效果產(chǎn)生影響，RMNMF算法的聚類效果有較大波動(dòng)，而本文算法受影響較小。

表1 不同算法的Accuracy對(duì)比(%)

表2 不同算法的NMI對(duì)比(%)

表3 不同算法的Purity對(duì)比(%)

3.4 參數(shù)選擇

在目標(biāo)函數(shù)求解迭代時(shí)，參數(shù)取值非常重要，會(huì)影響最終的聚類效果。本文算法的目標(biāo)函數(shù)包括2個(gè)參數(shù)λ和θ。由于新算法是一種無監(jiān)督算法，不能提前確定最優(yōu)參數(shù)值，因此通過遍歷法選擇參數(shù)。λ的遍歷區(qū)間設(shè)置為{0.001、0.01、0.1、1、10、100、1000}，θ的遍歷區(qū)間設(shè)置為{0、0.1、0.2、…、0.9、1}。為保證實(shí)驗(yàn)公平，對(duì)比算法中若有相應(yīng)的約束項(xiàng)參數(shù)，也做相同的遍歷區(qū)間設(shè)置。通過實(shí)驗(yàn)發(fā)現(xiàn)當(dāng)θ為0.5時(shí)效果最佳，當(dāng)λ等于0.01或0.1時(shí)效果最佳。

3.5 收斂性分析

為驗(yàn)證本文所提算法是否具有收斂性，實(shí)驗(yàn)記錄了不同數(shù)據(jù)集上迭代過程中的目標(biāo)函數(shù)值，受篇幅所限，僅展示部分迭代過程，如圖2所示。在迭代次數(shù)達(dá)到500次左右時(shí)，本文所提的模型已經(jīng)達(dá)到收斂。

圖2 目標(biāo)函數(shù)迭代圖(a)Jaffe數(shù)據(jù)集上的迭代圖；(b)PIX數(shù)據(jù)集上的迭代圖

4 結(jié)論

本文基于非平滑非負(fù)矩陣分解算法，提出了一種新算法，在目標(biāo)函數(shù)中加入了核函數(shù)和局部相似性約束項(xiàng)來處理非線性數(shù)據(jù)，彌補(bǔ)了傳統(tǒng)非光滑非負(fù)矩陣分解未考慮數(shù)據(jù)間幾何結(jié)構(gòu)的局限。針對(duì)非凸問題優(yōu)化求解困難的特點(diǎn)，本文實(shí)驗(yàn)優(yōu)化過程中設(shè)計(jì)了乘性迭代方法進(jìn)行迭代求解。新算法在Jaffe、Semeion、PIX三種開源數(shù)據(jù)集上的聚類效果良好，并能夠在迭代過程中達(dá)到收斂，驗(yàn)證了該算法的可行性和有效性。下一步研究考慮將新算法擴(kuò)展至其他應(yīng)用場(chǎng)景如有噪聲的數(shù)據(jù)聚類領(lǐng)域，優(yōu)化算法的時(shí)間復(fù)雜度和收斂速度。