簡彩仁,施瀟磊,呂書龍
(1.廈門大學嘉庚學院,福建 漳州 363150;2.福州大學 數(shù)學與計算機科學學院,福建 福州350116)
隨著互聯(lián)網(wǎng)的普及,數(shù)據(jù)的數(shù)量和傳播途徑越來越多,對高維數(shù)據(jù)的有效處理成為人們的迫切需要。直接使用高維數(shù)據(jù),會使數(shù)據(jù)的后期處理變得非常困難。因此,在對數(shù)據(jù)的使用之前,有必要對高維數(shù)據(jù)進行預處理,其中重構數(shù)據(jù)可以有效減少冗余信息。為了能有效地進行數(shù)據(jù)分析,需要對這些高維數(shù)據(jù)進行有效地表示,使數(shù)據(jù)的低維表示能體現(xiàn)高維數(shù)據(jù)的本質信息。
現(xiàn)實中的數(shù)據(jù)通常用矩陣形式進行表示,因此矩陣中含有大量的信息。對這些矩陣進行數(shù)據(jù)處理,將主要的重要的信息保留,形成新的數(shù)據(jù)集,這就是數(shù)據(jù)重構。重構后的數(shù)據(jù)集可應用在數(shù)據(jù)挖掘、信息壓縮等領域。傳統(tǒng)的數(shù)據(jù)重構方法有主成分分析和奇異值分解等[1]。這兩種經(jīng)典方法在數(shù)據(jù)處理研究中都有重要的應用?,F(xiàn)實生活中廣泛存在非負數(shù)據(jù)集,如圖像數(shù)據(jù)和文本數(shù)據(jù)等。研究非負數(shù)據(jù)集的重構問題具有重要的現(xiàn)實意義。
非負矩陣分解是一種對高維數(shù)據(jù)進行處理的算法,也是圖像處理和數(shù)據(jù)挖掘等領域的研究的熱點問題。1999年,Lee和Seung[2]在Nature上首次提出了非負矩陣分解的概念,并將其應用于人臉圖像的表示。從此各種非負矩陣分解及其擴展算法有著廣泛的應用,非負矩陣分解方法在圖像處理[3-7]、文獻檢索[8]、基因表達數(shù)據(jù)識別[9-10]等領域取得了巨大成功。現(xiàn)有的文獻研究[3-10]大都基于非負矩陣分解理論對非負數(shù)據(jù)集進行降維研究。本文從一種新的角度研究非負矩陣,利用非負矩陣的迭代求解過程得到的低秩矩陣,然后重構原始非負數(shù)據(jù)集,達到降低冗余信息、減少噪聲的目的,從而使重構數(shù)據(jù)集更適合模式識別研究。
非負矩陣分解就是把一個原非負矩陣分解成兩個非負矩陣,并且使這兩個非負矩陣的乘積與原非負矩陣的相似度最高。非負矩陣分解算法如下:有一個m×n的非負矩陣X,找到m×r的非負矩陣U和n×r的非負矩陣V,得
其中,U和V分別叫做基矩陣和系數(shù)矩陣。一般情況下,r的取值為(m+n)r≤mn,得出非負矩陣U和非負矩陣V的秩小于矩陣X的秩。非負矩陣分解算法是一種降秩分解算法,其分解結果具有明確的物理意義。
為了測量出原始矩陣X和重構矩陣UVT的相似度,即逼近程度,構造目標函數(shù)來衡量分解準確度的迭代規(guī)則,一般使用歐氏距離?;跉W氏距離的非負矩陣分解方法的目標函數(shù)為
其中,║·║F為矩陣的Frobenius范數(shù)。當X=UVT時,兩者間的距離為0,即歐式距離為0,得到最優(yōu)解,顯然,無法獲得該模型的解析解。
通過交叉迭代的方式可以求解非負矩陣分解問題,即固定U和V這兩個變量然后將它轉換成兩個凸優(yōu)化問題。最終,NMF的迭代公式為
利用(3)和(4)交替迭代可以得到低秩非負矩陣U和V。
高維數(shù)據(jù)是非線性、多噪聲的。高維數(shù)據(jù)對數(shù)據(jù)分析的識別準確率和處理運行時間有重大的影響,因此需要減少數(shù)據(jù)的冗余信息,降低數(shù)據(jù)非線性和多噪聲的影響。非負矩陣分解算法能減少非負數(shù)據(jù)集的冗余信息,將有用的信息保留下來。因此利用非負矩陣分解方法將數(shù)據(jù)進行重構,可以實現(xiàn)高維數(shù)據(jù)的低秩逼近,減少冗余信息。
非負矩陣分解的目標是尋找兩個低秩矩陣U和V,使X≈UVT,重構數(shù)據(jù)的過程必然存在信息損失,當這些損失信息是冗余信息時,重構后的數(shù)據(jù)集可以明顯地減少噪聲。本文利用非負矩陣分解算法研究數(shù)據(jù)集的重構問題。
對一個非負數(shù)據(jù)集X,用非負矩陣分解方法重構數(shù)據(jù)集,其主要思想是利用非負矩陣分解模型的目標函數(shù)衡量非負矩陣分解方法的抗噪能力。非負矩陣分解在求解過程中,利用低秩矩陣迭代求解,得到分解矩陣U和V。這個過程會產生重構誤差,而這些誤差代表了冗余信息。為此利用UVT可以重構數(shù)據(jù)集X,得到新數(shù)據(jù)集Xnew=UVT,新的數(shù)據(jù)集可以在一定程度上降低高維數(shù)據(jù)多噪聲的影響。于是,可以對重構數(shù)據(jù)集Xnew=UVT進行識別研究。
基于以上討論,提出基于非負矩陣分解的數(shù)據(jù)重構方法:
Input:非負數(shù)據(jù)集X
Output:重構數(shù)據(jù)集Xnew
Step1:標準化數(shù)據(jù)集X,使每個樣本具有單位L2范數(shù);
Step2:利用公式(3)和(4)交叉迭代得到 U 和 V;
Step3:重構數(shù)據(jù) Xnew=UVT。
為驗證非負矩陣分解的數(shù)據(jù)重構的有效性,選用兩個常用的人臉圖像數(shù)據(jù)集:ORL數(shù)據(jù)集和Yale數(shù)據(jù)集為研究對象。主要信息如下:
ORL(Olivetti Research Laboratory)人臉數(shù)據(jù)庫是由劍橋大學AT&T實驗室花費兩年時間拍攝的。該數(shù)據(jù)庫包含40個人400張人臉圖像,每張圖像維度4 096。ORL人臉圖像內這些人臉圖像有少許的不同,如佩戴眼鏡時嘴巴是或合或開,臉上的表情是開心或失落等。人臉的姿態(tài)也有相當程度的不同,人臉尺度和面朝方向等。ORL的一些人臉圖像如圖1所示。
圖1 ORL數(shù)據(jù)庫上兩人的部分人臉圖像
將ORL人臉數(shù)據(jù)庫進行處理,將每個人臉圖像按64×64采樣,將這些像素點,重新排成一行成為一維向量,從而整個ORL人臉圖像數(shù)據(jù)庫變成了400×4 096的數(shù)據(jù)集。這個數(shù)據(jù)集包含400個樣本每個樣本共4 096維,本文將用該數(shù)據(jù)集研究數(shù)據(jù)的重構,依然命名為ORL。
Yale數(shù)據(jù)庫總共有165張圖像,這些圖像數(shù)據(jù)來自15個人,且每個人有11張不同的人臉圖像。每個人的每張人臉圖像都存在一些不同,例如光照不同、表情不同和有無佩戴眼鏡,每張圖像的維度為4 096。圖2給出了Yale數(shù)據(jù)庫上兩個人的圖像的變化。
圖2 Yale數(shù)據(jù)庫上兩人的部分人臉圖像
將Yale人臉數(shù)據(jù)庫進行處理,將每個人臉圖像64×64按采樣,將這些像素點,重新排成一行成為一維向量,從而整個Yale人臉圖像數(shù)據(jù)庫變成了165×4 096的數(shù)據(jù)集。這個數(shù)據(jù)集包含165個樣本每個樣本共4 096維,本文將用該數(shù)據(jù)集研究數(shù)據(jù)的重構,依然命名為Yale。
主要研究非負矩陣分解實現(xiàn)數(shù)據(jù)重構,為驗證該方法的效果。從有監(jiān)督學習和無監(jiān)督學習兩個角度研究人臉圖像識別。為此,做了兩個實驗,實驗1利用kmeans聚類算法對原始數(shù)據(jù)和重構后的數(shù)據(jù)集進行聚類分析,比較聚類準確率。實驗2利用K最近鄰分類法對原始數(shù)據(jù)和重構后數(shù)據(jù)集進行分類,對比分類準確率。
實驗1:聚類。
采用聚類準確率(ACC)評價實驗結果,ACC的計算公式如下:
對給定樣本,令ri和si分別為聚類算法得到的類標簽和樣本自帶的類標簽,那么準確率的計算公式[6]為
其中,n 為樣本總數(shù),δ(x,y)是一個函數(shù),當 x=y 時,值為 1,否則為 0,map(ri)是一個置換函數(shù),將每一個類標簽ri映射成與樣本自帶的類標簽等價的類標簽。
原始數(shù)據(jù)用K-means聚類的方法(K-means)和非負矩陣分解后重構數(shù)據(jù)用K-means聚類的方法(NMF-K-means)的聚類準確率如表1所示。
從表1看出在ORL人臉圖像數(shù)據(jù)集中,K-means的聚類準確率為58.25%,而NMF-K-means的聚類準確率為61%,數(shù)據(jù)的聚類準確率提高2.75%。在Yale數(shù)據(jù)集中,K-means的聚類準確率為48.484 8%,而NMF-K-means的聚類準確率為52.121 2%,數(shù)據(jù)的聚類準確率提高3.6364%,數(shù)據(jù)的聚類準確率得到了提高。實驗結果表明,非負矩陣分解方法重構數(shù)據(jù)集可以減少冗余信息,降低噪聲對無監(jiān)督學習的影響。
表1 聚類準確率對比
實驗2:分類。
利用K最近鄰分類法對比兩種方法在不同交叉驗證折數(shù)下的分類準確率。原始數(shù)據(jù)用K最近鄰分類法的方法(KNN)和非負矩陣分解后重構數(shù)據(jù)用K最近鄰分類法的方法(NMF-KNN)的分類準確率如圖3~4。
圖3 ORL分類準確率
圖4 Yale分類準確率
圖3~4給出了在不同的交叉驗證折數(shù)下,ORL和Yale兩個數(shù)據(jù)集利用K最近鄰分類方法分類的準確率。從圖中明顯的發(fā)現(xiàn)NMF-KNN的分類準確率明顯優(yōu)于KNN的分類準確率。實驗結果表明,非負矩陣分解方法重構數(shù)據(jù)集可以減少冗余信息,降低噪聲對有監(jiān)督學習的影響。
從實驗1和實驗2的結果不難發(fā)現(xiàn),基于非負矩陣分解的數(shù)據(jù)重構方法可以在有監(jiān)督學習和無監(jiān)督學習方面改進原始數(shù)據(jù)的識別準確率。因此通過非負矩陣分解算法重構數(shù)據(jù),可以減少數(shù)據(jù)的冗余信息,降低多噪聲的影響,從而提高數(shù)據(jù)識別準確率。
利用非負矩陣分解方法構非負數(shù)據(jù)。從實驗結果看出重構后數(shù)據(jù)集能提高人臉圖像的聚類準確率和分類準確率。從而得出,通過非負矩陣分解方法進行數(shù)據(jù)重構是可行的,而且重構后的數(shù)據(jù)能減少冗余信息、降低數(shù)據(jù)多噪聲的影響,提高數(shù)據(jù)識別準確率。該方法的主要局限是非負數(shù)據(jù)集的限制,因此克服這一不足的研究將在以后的研究中給出。