魯棒圖局部坐標(biāo)編碼*

印爽

(遼寧師范大學(xué)數(shù)學(xué)學(xué)院，遼寧大連116029)

魯棒圖局部坐標(biāo)編碼*

印爽

(遼寧師范大學(xué)數(shù)學(xué)學(xué)院，遼寧大連116029)

文章將局部坐標(biāo)編碼(NGLF)和圖非負(fù)矩陣分解(GNMF)合并形成新框架，并用L2，1范數(shù)代替原始L2范數(shù)構(gòu)成新的目標(biāo)函數(shù)，提出新的魯棒圖局部坐標(biāo)分解(RGLCF)算法.新算法在使數(shù)據(jù)行稀疏的同時也確保數(shù)據(jù)在幾何結(jié)構(gòu)上具有魯棒性，給出了算法的更新規(guī)則并對算法的收斂性進(jìn)行了證明.

非負(fù)矩陣分解;局部坐標(biāo);圖正則;聚類

近幾年特征提取已經(jīng)受到廣泛關(guān)注，特征提取的變體模型如主成分分析(PCA)［1］，奇異值分解(SVD)，非負(fù)矩陣分解(NMF)［2－3］和CF［4］被研究用于找到高維數(shù)據(jù)的一個低維表示.然而，在實際應(yīng)用程序中總會涉及到數(shù)據(jù)，當(dāng)測量重組誤差時，成平方的損失對異常點和噪聲是敏感的，最近一些提高NMF魯棒性的模型已經(jīng)被提出，Zhang et al提出了魯棒非負(fù)矩陣分解，將數(shù)據(jù)矩陣分解成一個稀疏誤差矩陣和兩個非負(fù)矩陣的和.Kong et al提出了基于L21范數(shù)的魯棒NMF，能夠解決噪聲和異常點.Zhang et al提出的魯棒非負(fù)圖嵌入(GNGE)可以同時解決噪聲數(shù)據(jù)及其分布.

本文中，提出了一個新的矩陣分解方法，魯棒圖局部坐標(biāo)編碼(RGLCF).圖正則方法構(gòu)造樣本間的相似關(guān)系圖刻畫數(shù)據(jù)的流形結(jié)構(gòu).然而GNMF模型的目標(biāo)函數(shù)采用的是L2范數(shù)的平方誤差，在實際應(yīng)用中數(shù)據(jù)容易受到噪聲數(shù)據(jù)的干擾，無法準(zhǔn)確反映應(yīng)有的特征，嚴(yán)重降低了聚類效果，NLCF模型同樣對噪聲和異常點非常敏感，分類效果都不十分理想.本文采用比L2范數(shù)更具有魯棒性的L21范數(shù)，解決了數(shù)據(jù)中的噪聲干擾，異常點及不良圖對原始數(shù)據(jù)的影響，聚類效果得到顯著增強.

1 相關(guān)工作

本文中，對于向量，x∈R，x的Lp范數(shù)定義為;矩陣X=(xij)中，用x(i)，x(j)分別代表矩陣X的第i行和第j列，xij表示矩陣X的第i行第j列數(shù).Tr［X］代表矩陣X的跡.矩陣X∈RM×N的F范數(shù)記為矩陣的2，1范數(shù)可看成是L1范數(shù)的旋轉(zhuǎn)不變量，定義為以看出2，1范數(shù)對旋轉(zhuǎn)矩陣R的行保持旋轉(zhuǎn)不變性，幾乎處處有‖XR‖2，1.X中與非零行有關(guān)的特征被選擇下來，特征選擇通過這種方法來實現(xiàn).

給定一個非負(fù)矩陣X=［X(1)，X(2)，…，XN］∈RM+×K，X的每列可看為一個數(shù)據(jù)點.NMF是要找到兩個非負(fù)矩陣，使得目標(biāo)函數(shù)最小，V≥0，這里‖·‖F(xiàn)是F范數(shù).目標(biāo)函數(shù)對U或V分別是凸函數(shù)，但對U和V不再是凸函數(shù).因此，很難找到解決上述問題的一個全局最優(yōu)解.Lee et al.提出了如下的更新規(guī)則對目標(biāo)函數(shù)進(jìn)行優(yōu)化←

2 RGLCF框架

2.1 魯棒局部坐標(biāo)編碼

局部坐標(biāo)編碼可定義為一個概念對(γ，C)，其中C是具有d維的錨點集合，γ是從x∈Rd到［γv(x)］v∈C∈R|C|的映射.NMF模型可以看成一個坐標(biāo)編碼，這里基矩陣U的列向量就是錨點的集合，系數(shù)矩陣V的列向量則包含了對應(yīng)于每個錨點的系數(shù).為了獲得稀疏編碼，每一個數(shù)據(jù)點需要被表示成由附近少數(shù)錨點的線性組合.通過下面介紹的局部坐標(biāo)約束能夠做到這一點:

局部坐標(biāo)編碼采用的平方誤差對噪聲和異常值都很敏感，為了減少不相關(guān)和噪聲數(shù)據(jù)的影響，我們提出如下局部坐標(biāo)編碼的聚類問題.

局部坐標(biāo)編碼不帶平方項，因此較大異常值和噪聲不會影響目標(biāo)函數(shù).

2.2 魯棒圖非負(fù)矩陣分解

NMF可找到一組歐氏距離最能夠接近原始數(shù)據(jù)的基向量，卻不能反映本征數(shù)據(jù)結(jié)構(gòu)，為了使局部約束能很好地反映本征數(shù)據(jù)結(jié)構(gòu)，需要考慮數(shù)據(jù)空間中的流形幾何結(jié)構(gòu)，而且已經(jīng)證明數(shù)據(jù)的局部幾何結(jié)構(gòu)可用分散數(shù)據(jù)的近鄰圖刻畫，因此提出如下目標(biāo)函數(shù)

從上式可以看出兩個問題，第一，樣本重組誤差是帶平方的，較大誤差的噪聲樣本容易影響目標(biāo)函數(shù).第二，圖非負(fù)矩陣分解也受不良解構(gòu)圖的影響.為了使目標(biāo)函數(shù)對噪聲數(shù)據(jù)和不良圖具有魯棒性，提出如下公式

2.3 RNLCF的目標(biāo)函數(shù)

將魯棒局部坐標(biāo)編碼(1)和魯棒圖非負(fù)矩陣分解(3)合并形成一個新的框架.RNLCF的整體目標(biāo)函數(shù)被定義為這里μ是權(quán)系數(shù)，稱(4)為魯棒圖局部坐標(biāo)編碼.

3 優(yōu)化

優(yōu)化問題(4)涉及的L2，1范數(shù)是非平滑的，為了解決這個問題，應(yīng)用L2，1范數(shù)的變體形式.由矩陣性質(zhì)有，Tr(A)，其中∧i=diag(|vi|)∈RK×K.

考慮到U和V的非負(fù)限制，目標(biāo)函數(shù)(4)可以改寫成

其中A，B，C為對角矩陣，對應(yīng)的對角線元素分別為

目標(biāo)函數(shù)(5)對于U和V是非凸的，因此不能找到一個可算出全局最小值的算法，下面介紹一種能夠找到局部最小值的更新規(guī)則，通過計算目標(biāo)函數(shù)可被寫成:

令φij，φij是限制uij≥0和vij≥0相應(yīng)的拉格朗日乘數(shù)，Ψ=［φij］，Φ=［φij］.其拉格朗日函數(shù)L可寫成

這里H是由V的行之和組成的對角矩陣.

定義g=diag(XTBX)∈RN，令G=(g，…，g)T是K×N維矩陣;定義d=diag(UTBU)∈RK，令D =(d，…，d)是K×N維矩陣.按照KKT條件φijuij=0和φijvij=0.可得到如下等式:

解決式子(9)和(10)，有如下更新規(guī)則

定義1 Z(h，h')為F(h)的輔助函數(shù)，滿足Z(h，h')≥F(h)，Z(h，h)=F(h).

引理1 如果Z(h，h')是F的輔助函數(shù)，那么F在如下更新規(guī)則是單調(diào)遞減函數(shù)

引理2 對任意非負(fù)矩陣A∈Rn×n、B∈Rk×k、S∈Rn×k、S'∈Rn×k且A和B是對稱矩陣，則滿足不等式

本文算法收斂性正確性如下:

對于給定的X，固定U，用O(V)表示目標(biāo)函數(shù)中至于V相關(guān)的部分，則

定理1 函數(shù)Z(V，V')=－2Tr(UTAXVT)－+ μ∑Gij是 O(V)的一個輔助函數(shù).

因為Z(V，V')滿足輔助函數(shù)的定義，那么它對v來說是一個凸函數(shù)，則有全局極小值

證明 Z(V，V')=O(V)是顯然的，只需證Z(V，V')≥O(V).

對于(12)(13)式子，運用引理3，可以得到

綜上可得Z(V，V')≥O(V)，因此Z(V，V')是O(V)的輔助函數(shù).

為了得到Z(V，V')的極小值，求出其Hessian矩陣這里Yij是正定的對角矩陣，且

由Hessian矩陣性質(zhì)知Z(V，V')是關(guān)于V的凸函數(shù)，用求導(dǎo)得到全局極小值.

［1］R.O.Duda，P.E.Hart，and D.G.Stork.Pattern classification ［M］.New York:John Wiley＆Sons，2012.

［2］D.D.Lee and H.S.Seung.“Learning the parts of objects by nonnegative matrix factorization”［J］.1999，401(6755):788－791.

［3］H.Liu，Z.Wu，X.Li，D.Cai，and T.S.Huang.“Constrained nonnegative matrix factorization for image representation”［J］.Pattern A－nalysis and Machine Intelligence，IEEE Transactions on，2012，34(7): 1299－1311.

［4］W.Xu and Y.Gong.“Document clustering by concept factorization”［J］.in Proceedings of the 27th annual international retrieval.ACM，2004:202－209.

(責(zé)任編輯:陳衍峰)

O152.5

A

1008－7974(2016)06－0031－03

10.13877/j.cnki.cn22－1284.2016.12.010

2016－05－12

遼寧省自然基金項目“大數(shù)據(jù)環(huán)境下高維視覺信息魯棒表示方法研究”(60875029)

印爽，女，遼寧遼陽人，遼寧師范大學(xué)數(shù)學(xué)學(xué)院在讀碩士.