非負(fù)矩陣分解算法綜述

王宇辰

(蘭州財(cái)經(jīng)大學(xué)統(tǒng)計(jì)學(xué)院,甘肅蘭州 730020)

0 引言

隨著大規(guī)模海量數(shù)據(jù)的不斷產(chǎn)生,圖像、音頻等非結(jié)構(gòu)化數(shù)據(jù)通常表示為取值非負(fù)的高維數(shù)據(jù)矩陣。處理高維數(shù)據(jù)矩陣時(shí),通過(guò)對(duì)矩陣進(jìn)行分解可完成數(shù)據(jù)壓縮與聚類(lèi)等任務(wù)。非負(fù)矩陣分解(Non-negative Matrix Factorization,NMF)是一種簡(jiǎn)潔直觀、效果優(yōu)良的矩陣分解技術(shù)[1],其核心思想是在一定約束條件下將原始數(shù)據(jù)分解為低維的基矩陣和系數(shù)矩陣,并在低維矩陣中能夠更好地體現(xiàn)出數(shù)據(jù)本身所隱含的性質(zhì),對(duì)數(shù)據(jù)挖掘具有重要的意義。非負(fù)矩陣分解是高維數(shù)據(jù)聚類(lèi)的新方法,在機(jī)器學(xué)習(xí)、生物信息[2]等領(lǐng)域具有廣泛的應(yīng)用。

本文旨在對(duì)非負(fù)矩陣分解方法的基本原理和發(fā)展現(xiàn)狀進(jìn)行綜述。本文所用符號(hào)的具體說(shuō)明見(jiàn)下表1。

1 非負(fù)矩陣分解的基本原理

矩陣分解方法是應(yīng)用數(shù)學(xué)領(lǐng)域的研究重點(diǎn),其目的在于對(duì)原始矩陣在一定約束條件下進(jìn)行分解,從而簡(jiǎn)化矩陣運(yùn)算效率并取得良好的解讀性。在工程計(jì)算領(lǐng)域中,矩陣的QR分解、Cholesky分解在求解線性方程等問(wèn)題上效果良好;在機(jī)器學(xué)習(xí)領(lǐng)域中,矩陣的奇異值分解可完成對(duì)數(shù)據(jù)的特征提取與壓縮,并廣泛應(yīng)用于圖像處理、推薦系統(tǒng)等實(shí)際問(wèn)題。

1999年,Lee[3]在《Nature》上發(fā)表了關(guān)于非負(fù)矩陣分解的相關(guān)研究,非負(fù)矩陣分解算法的基本思想是:在對(duì)矩陣元素的非負(fù)約束條件下,將原有的數(shù)據(jù)矩陣X分解為基矩陣U和系數(shù)矩陣V,基矩陣U的每一列代表一個(gè)局部特征,系數(shù)矩陣V的每一列代表一個(gè)樣本在低維空間中的表示。具體定義如下:

給定m維的非負(fù)隨機(jī)向量x,其n個(gè)觀測(cè)樣本表示為xj,j=1,2,...,n,m維的n個(gè)列向量x組成數(shù)據(jù)矩陣X。NMF算法是將X分解成非負(fù)的m×r維的基矩陣U和非負(fù)的r×n維的系數(shù)矩陣V,使得:

m×n維的噪聲矩陣E表示逼近誤差,一般要求較小且快速收斂。r表示矩陣Y的秩,通常根據(jù)實(shí)際情況確定并滿足 (m+n)r＜mn,即利用少量的基向量便可表示高維數(shù)據(jù)。若采用歐式距離來(lái)度量矩陣分解的損失,則NMF可表述為式(2)所示的優(yōu)化問(wèn)題:

表1 符號(hào)說(shuō)明Tab.1 Symbol description

2005年,Ding[4]等對(duì)非負(fù)矩陣與聚類(lèi)算法的等價(jià)性進(jìn)行探討,并以K-means算法為例對(duì)非負(fù)矩陣分解的聚類(lèi)特性加以說(shuō)明。

假設(shè)X=[x1,x2,...,xn]為n個(gè)數(shù)據(jù)點(diǎn),K-means算法將其劃分為k個(gè)類(lèi)。K-means算法的目標(biāo)函數(shù)可寫(xiě)成:

其中uk為每一類(lèi)的類(lèi)中心,k為預(yù)先設(shè)定的聚類(lèi)類(lèi)別數(shù)目。

若將K-means算法得到的類(lèi)中心表述為U=(u1,...,,uk),將聚類(lèi)結(jié)果用矩陣H表示,hki= 1 表示xi屬于第k類(lèi)ck,否則hki= 0。此時(shí),可將K-means算法的目標(biāo)函數(shù)寫(xiě)為:

不難看出,K-means算法的目標(biāo)函數(shù)與NMF之間存在某種等價(jià)關(guān)系。U可理解為聚類(lèi)中心矩陣,V可理解為聚類(lèi)標(biāo)簽矩陣。當(dāng)約束矩陣V為正交矩陣時(shí),NMF分解問(wèn)題與K-means聚類(lèi)問(wèn)題等價(jià),如下式(4)所示。

2 非負(fù)矩陣分解方法的發(fā)展現(xiàn)狀

根據(jù)實(shí)際問(wèn)題的需要,近些年出現(xiàn)了大量非負(fù)矩陣分解的拓展研究與算法。主要圍繞以下幾個(gè)方面:(1)矩陣分解約束條件的設(shè)計(jì),其目的是放松非負(fù)性約束使得更符合實(shí)際問(wèn)題求解需要;(2)迭代更新算法的設(shè)計(jì),其目的是在求解NMF時(shí)更快更穩(wěn)定收斂;(3)實(shí)際應(yīng)用。

2.1 矩陣分解約束條件的設(shè)計(jì)

在原始NMF算法的基礎(chǔ)上,根據(jù)實(shí)際問(wèn)題的需要,研究者們提出一系列改進(jìn)的非負(fù)矩陣分解方法。

2001年,Guillamet[5]使用對(duì)角矩陣Q對(duì)原始數(shù)據(jù)矩陣X進(jìn)行加權(quán),分解問(wèn)題變?yōu)閄Q≈UVQ,得到加權(quán)的矩陣分解結(jié)果。2004年,Hoyer借助稀疏編碼思想,提出了稀疏約束的非負(fù)矩陣分解模型,對(duì)分解后的矩陣U和V施加稀疏性約束,從而取得更好的聚類(lèi)精度。2008年,Cai[6]提出流形上的非負(fù)矩陣分解算法。其核心思想是,在非負(fù)矩陣分解度量歐式空間距離的基礎(chǔ)上,附加幾何流形上度量的數(shù)據(jù)親疏程度,使得聚類(lèi)時(shí)所考慮特征的距離度量方式更加全面,優(yōu)化目標(biāo)函數(shù)變?yōu)?

由于現(xiàn)實(shí)問(wèn)題中存在大量混合符號(hào)的數(shù)據(jù),Ding提出Semi-NMF算法,其核心思想是當(dāng)數(shù)據(jù)矩陣X元素有正有負(fù)時(shí),僅約束系數(shù)矩陣V元素非負(fù),基矩陣U中的元素可正可負(fù),優(yōu)化目標(biāo)函數(shù)則變?yōu)?可將Semi-NMF視為K-means算法的“軟聚類(lèi)”版本。2010年,Lee提出了半監(jiān)督非負(fù)矩陣分解算法,使得預(yù)先具備相同標(biāo)簽信息的數(shù)據(jù)點(diǎn)被聚為一類(lèi)。2017年,Trigeorgis[7]提出了深度矩陣分解框架,對(duì)分解出的矩陣V進(jìn)行多次矩陣分解,從而得到可反映深層次聚類(lèi)信息的矩陣。

2.2 迭代更新算法的設(shè)計(jì)

非負(fù)矩陣分解的求解過(guò)程較為復(fù)雜。已有研究者對(duì)非負(fù)矩陣分解的求解優(yōu)化方法進(jìn)行設(shè)計(jì),總體上可分為三大類(lèi):乘性更新方法、投影梯度法和交替非負(fù)最小二乘方法,其中乘性迭代算法應(yīng)用最為廣泛。

Lee在非負(fù)矩陣分解框架下給出了乘性更新算法。在原有的非負(fù)矩陣分解問(wèn)題中,同時(shí)求解矩陣U和V是非凸問(wèn)題,求解較為困難。乘性更新算法原理是在固定U或V的情況下更新求解另一矩陣,此時(shí)為凸優(yōu)化問(wèn)題。在預(yù)設(shè)迭代次數(shù)時(shí),可完成對(duì)矩陣U、V的近似求解。矩陣U和V的更新公式如下式(5)所示。

2.3 實(shí)際應(yīng)用

非負(fù)矩陣分解可用于解決數(shù)據(jù)的聚類(lèi)問(wèn)題,是目前機(jī)器學(xué)習(xí)、模式識(shí)別等領(lǐng)域的研究熱點(diǎn),在人臉識(shí)別、文本挖掘[8]等方面應(yīng)用廣泛。

人臉識(shí)別是基于人臉特征信息進(jìn)行身份識(shí)別的識(shí)別技術(shù),是計(jì)算機(jī)視覺(jué)領(lǐng)域的重要研究問(wèn)題。人臉識(shí)別任務(wù)中關(guān)鍵步驟可理解為圖像聚類(lèi)的過(guò)程。將每張圖像數(shù)據(jù)矩陣元素規(guī)范化至[0,1],并轉(zhuǎn)換為列向量形成數(shù)據(jù)矩陣X,對(duì)數(shù)據(jù)矩陣X進(jìn)行非負(fù)矩陣分解,可得到具有人臉識(shí)別信息的矩陣V完成人臉識(shí)別。

文本聚類(lèi)包括根據(jù)文本內(nèi)容對(duì)文本主題進(jìn)行劃分。在多視角聚類(lèi)問(wèn)題中,同一文檔可能由不同語(yǔ)言進(jìn)行表述,問(wèn)題則變?yōu)閷?duì)多種不同語(yǔ)言不同主題的文本進(jìn)行聚類(lèi)。假設(shè)文本中具有v種語(yǔ)言,每種語(yǔ)言的數(shù)據(jù)矩陣記為X(v),多視角聚類(lèi)[9]通過(guò)非負(fù)矩陣分解得到各視角的聚類(lèi)結(jié)果V(v),再通過(guò)正則化方法求出聚類(lèi)結(jié)果的一致表述V*,完成多視角的文本聚類(lèi)。

3 非負(fù)矩陣分解進(jìn)一步研究的方向

盡管已有諸多學(xué)者對(duì)非負(fù)矩陣分解的分解形式、求解方法進(jìn)行研究,但非負(fù)矩陣分解中仍存在一些細(xì)節(jié)問(wèn)題待研究與討論。

3.1 矩陣初始化

非負(fù)矩陣分解的優(yōu)化過(guò)程是迭代更新求解,最終的收斂解依賴于矩陣初始值。傳統(tǒng)的非負(fù)矩陣分解初始化采用均勻隨機(jī)數(shù)填充,這種方法并沒(méi)有考慮數(shù)據(jù)本身的信息,當(dāng)矩陣初始值與最優(yōu)解距離較遠(yuǎn)時(shí),所需的計(jì)算成本較大。如何設(shè)計(jì)出計(jì)算成本較小、收斂性較快、更具理論依據(jù)的矩陣初始化方法是后續(xù)待研究的問(wèn)題。

3.2 分解的秩 r的確定

非負(fù)矩陣分解是將Xm×n分解為Um×r和Vr×n,分解后的秩r要滿足條件(m+n)r＜mn,數(shù)據(jù)壓縮程度與秩r的值關(guān)系密切。目前確定秩r的方法往往基于實(shí)驗(yàn)效果與人為經(jīng)驗(yàn),并沒(méi)有完善的理論對(duì)秩r的取值進(jìn)行客觀評(píng)價(jià)。如何采用先驗(yàn)信息來(lái)完成秩r的最優(yōu)值選擇還需進(jìn)一步討論。

4 結(jié)論

本文對(duì)非負(fù)矩陣分解的思想、算法和應(yīng)用等方面進(jìn)行了詳細(xì)說(shuō)明,指出了現(xiàn)有研究的不足,展望了進(jìn)一步研究的方向。