異常值自識別的低秩矩陣補全方法*

李可欣，徐 彬，高克寧

東北大學 計算機科學與工程學院，沈陽 110000

1 引言

當矩陣的元素存在未知或缺失的情況下，可以采用矩陣補全方法根據(jù)已知元素估計未知元素，找到與原始矩陣盡可能相似的矩陣。目前矩陣補全已經(jīng)應用到很多領域：機器學習[1]、視頻去噪[2]、壓縮感知[3]、圖像處理[4]、無線傳感[5]、目標追蹤[6]等。Cai和Candès等提出奇異值閾值（singular value thresholding，SVT）算法[7]。利用奇異值分解（singular value decomposition，SVD）找到與原始矩陣盡可能相似的目標矩陣，但該算法每一步都進行SVD分解，這意味著每一步迭代都需要重新遍歷所有樣本，這樣在處理大規(guī)模矩陣時需要巨大的計算時間和空間存儲。為了解決大規(guī)模數(shù)據(jù)的矩陣補全問題，Wen等人在此基礎上提出了低秩矩陣擬合算法（low-rank matrix fitting，LMaFit）[8]。LMaFit每一步迭代都只需解決一個最小二乘問題，因此計算速度和存儲空間優(yōu)于SVT算法。大量研究所知，目前LMaFit算法無法準確處理存在異常值的數(shù)據(jù)樣本，且計算是一個迭代過程，每一步迭代都在上一步計算的結果基礎上進行，如果計算包含異常值的樣本，將會導致不準確的結果，因此在數(shù)據(jù)處理之前識別并處理異常值將會提高算法的準確率。

為了解決上述問題，本文提出了一種新的非線性過放縮異常值自識別算法。該方法可以識別出異常值的位置并對異常值進行近似值替代，降低異常值對結果的影響，相較于已有矩陣補全算法的恢復結果也更加精確。

2 相關工作

陳蕾等人詳細地介紹了矩陣補全模型及相關算法應用研究[9]，在矩陣補全的相關算法中，大部分算法可以處理添加高斯噪聲的數(shù)據(jù)，卻對真實數(shù)據(jù)中的異常值無法進行有效的處理[10]，而現(xiàn)實生活中很多情況例如電影、書籍、游戲等的分類問題都是存在異常值的樣本問題。在這樣的情況下，如何降低異常值對最終結果的影響是提高矩陣補全算法魯棒性的重點。在之前的工作中[11]，在本校的在線平臺增加學生互評系統(tǒng)，學生之間互相評價分數(shù)反映該學生的學習情況，并利用學生平時成績衡量學生互評成績的可信度。但是在實際情況中，由于現(xiàn)實情況的不可控性，學生的成績存在缺失或存在異常點，例如學生成績超出成績區(qū)間、波動較大的異常數(shù)據(jù)等情況。當剔除不合理的成績數(shù)據(jù)后，形成了存在較多缺失值的成績矩陣。使用矩陣補全方法可以對成績數(shù)據(jù)補全，可以使數(shù)據(jù)完整，但對于存在異常值的學生成績使用矩陣補全算法，不僅與實際情況有所偏差，更有可能與真實情況背離。因此降低異常值對矩陣補全結果的影響是目前存在的重點及難點。

為了解決因異常值而導致的分析結果存在偏差問題，相關學者提出了許多有效的算法，例如Ji等人提出黎曼信賴補全方法（Riemannian trust-region method for low-rank matrix completion，RTRMC）[13]。利用低秩的幾何約束在格拉斯曼流形上重塑無約束優(yōu)化問題；Boumal等人采用非奇異值分解SVT算法[7,12]，在SVT的基礎上提出通過直接對矩陣進行牛頓迭代。由于SVT模型每一次迭代都要在全部樣本上進行SVD分解，雖然理論上可行，但是在處理大規(guī)模數(shù)據(jù)情況下的效果卻并不盡人意。Jain等人通過奇異值映射保證秩最小化方法[14]，提出一個簡單且快速的奇異值投影算法（singular value projection，SVP）映射約束來達到最小化秩的目的，從而解決限制等距約束問題。Dong等人利用最少數(shù)據(jù)恢復矩陣的算法（special matrix completion，SMC）[15-16]，但是在實驗中可以看到在矩陣數(shù)目為500左右時達到最優(yōu)，對于過少或過多的數(shù)目的矩陣處理較乏力。

為了解決上述問題并降低異常值對于矩陣補全結果的不利影響，提高算法的精確度，本文在低秩矩陣擬合算法的基礎上提出一種新的異常值自識別算法（self-identifition of outliers for low-rank matrix completion，SIOMC）。與傳統(tǒng)算法不同的是，該算法選擇直接優(yōu)化原始矩陣中的未知元素使原始矩陣趨于低秩結構，在此基礎上進行矩陣補全，通過構造誤差矩陣，識別矩陣中的異常值，降低異常值對算法魯棒性的影響。誤差矩陣在每一步的迭代中都會更新，該矩陣顯示上一步的誤差結果，并返回異常值的位置，使用近似值對異常值進行替換，增加算法的精確度。

本文分別進行了人工數(shù)據(jù)和真實數(shù)據(jù)的矩陣補全實驗分析，討論四種矩陣補全算法的時間及魯棒性能。實驗結果顯示SIOMC算法相較于其他矩陣補全算法，在處理異常值矩陣性能更加優(yōu)秀。其他方法包括奇異值閾值方法（SVT）、快速SVT方法、不精確增廣拉格朗日方法（inexact augmented Lagrange multiplier，IALM）和低秩矩陣擬合方法（LMaFit）[17-20]。

3 算法描述

在算法的描述之前，先給出一些基本的定義:

令X=(x1,x2,…,xn)為大小為m×n的矩陣，本文定義{1,2,…,m}×{1,2,…,n}是觀察到的X中的元素的位置集合，而ΩC為缺失元素的位置集合。定義PΩ為矩陣X在集合Ω上的正交投影算子：

低秩近似算法目前可以分為兩方面：最小化核范數(shù)和矩陣分解。絕大多數(shù)的矩陣補全問題都是在如下模型的基礎上提出的：

式中，X為M在Ω上的投影矩陣，大小是m×n，Ω為相應指示集，表示在Ω區(qū)域內進行矩陣補全算法的研究，rank(X)代表矩陣X的秩。明顯可以看出上述的問題是一個NP難問題，因此上述問題可以轉化為最核范數(shù)問題：

其中，M為原始矩陣，秩為r,UVT是目標矩陣，U和V分別是n1×r和n2×r的矩陣，由于上式是非凸的，考慮其拉格朗日形式：

優(yōu)化過程分別在U、V和X上最小化，得到最后的最優(yōu)值。

4 優(yōu)化算法

為了降低異常值對算法魯棒性的影響，本文提出SIOMC方法提高算法的精確度，SIOMC模型如下：

式中，X是原始矩陣，引入異常值檢測結果矩陣E，UVT是想要得到的目標矩陣，?表示分量相乘。E為上一步迭代產(chǎn)生的誤差稀疏矩陣，其中Ei,j=-U?V?T。如果Ei,j≠0 ，表明對應的Xi,j可能為異常值。在接下來的步驟中，將對異常值進行處理，具體處理過程會在后續(xù)表明。其中Λi,j代表迭代中對Xi,j的控制參數(shù)，每一步的迭代過程中，在更新的U、V的基礎上識別異常值的位置。

本文采用最小二乘法優(yōu)化上述問題，首先設置誤差矩陣E初始值為0，采用重復迭代方法固定U和V更新E和Λ，然后固定E和Λ更新U和V。

首先固定U和V，求解如下問題：

上述過程中，E為誤差矩陣，Λi,j識別異常值并記錄異常值的位置。如果Xi,j不是異常值，那么直接將Xi,j投影到Ω上，否則將其值置為0。

在算法的每一次迭代過程中，通過以下操作得到誤差矩陣：

引入誤差閾值γ=UVTij-Xij，其合理性的詳細證明可參考文獻[22]，在誤差矩陣超過定義的閾值范圍的情況下，判斷Xi,j為異常值，下一步將進行：

如果該值為異常值即Λi,j=1，將其與進行替換，上一步迭代中更新的目標矩陣中對應的值。

接下來繼續(xù)固定誤差矩陣E和Λi,j，更新U和V，解決如下問題：

更新U：

更新V：

上述過程可以定位異常值位置并自動將近似值與異常值替換，每一步都更新了數(shù)據(jù)，提高了算法處理結果的精確度，從而保證最終結果的準確性。SIOMC算法詳細描述如算法1所示。

算法1 SIOMC

Input:MatrixX,Ω,PΩ(M),r＞0,maxiter.

Initialize:Λij=1for(i,j)∈Ωand otherwise=Ω,iter.

Whileiter＜maxiterdo

5 實驗

在本章實驗部分，基于人工數(shù)據(jù)集和真實數(shù)據(jù)集比較SIOMC算法和LMaFit算法在矩陣補全問題上的效果。本校學生在線成績比較SVT、IALM、LMaFit和SIOMC算法，使用RMSE（root mean square error）和Relative error分別衡量算法的準確性。在本文實驗中，程序均用Matlab2016編程，在雙核i7-4770處理器、內存為16 GB的臺式電腦（操作系統(tǒng)為Windows 7）上運行。

5.1 合成數(shù)據(jù)實驗

首先構造兩個矩陣ML∈Rm×r和MR∈Rr×n，每一個元素都根據(jù)獨立同分布高斯采樣，生成秩為r的矩陣M，M=MLMR。令MΩ是矩陣M中可觀察得到的部分，位置集合Ω是通過隨機采樣得到的。令p是觀察得到的元素數(shù)量和矩陣M中所有m×n個元素的比例。均方根誤差和相對重構誤差經(jīng)常被用于衡量本文所述類似算法的準確性，因此實驗采用均方根誤差和相對重構誤差指標來衡量不同算法所處理矩陣的準確性。

均方根誤差的定義為：

這里的num是測試樣本數(shù)目。

相對重構誤差的定義為：

Fig.1 RMSE versus different ranks圖1 隨著秩變化RMSE的變化情況

在實驗中，設置m=n=1 500，p=0.8，c=0.05，λ=0.5，分別調節(jié)r的大小，r的取值范圍為{5,10,15,20,25}，實驗結果取10次實驗的平均值保證實驗的公平有效，對比不同秩大小的實驗的結果如圖1所示。同時為了探究噪聲的比例對算法性能的影響，驗證SIOMC相較于其他算法在異常值問題上具有更優(yōu)秀的魯棒性，在原始數(shù)據(jù)基礎上增加不同比例的噪聲（noise level）來觀察不同算法對數(shù)據(jù)處理的情況。實驗中保持矩陣的秩為5不變，逐步改變noise level取值范圍為{0.25,0.30,0.35,0.40,0.45,0.50}，noise level代表噪聲數(shù)據(jù)在實驗數(shù)據(jù)中的比例，通過觀察noise level變化過程，算法RMSE變化的趨勢如圖2所示。

Fig.2 RMSE versus noise level圖2 隨著噪聲變化RMSE變化情況

圖1為隨著秩變化SIOMC算法和SVT、IALM和LMaFit三種算法的RMSE值的曲線圖。從圖中可以看出，隨著矩陣秩增加，算法的RMSE呈下降趨勢。從圖1顯示，在矩陣秩從5遞增到25的過程中，代表SIOMC算法的曲線數(shù)值上結果優(yōu)于其他三種算法；圖2為隨著噪聲變化四種矩陣補全算法RMSE的變化曲線圖。從圖中可以看出，隨著noise level增加，SIOMC算法的曲線相較于其他算法曲線趨勢更加平緩，說明SIOMC可以更好地處理異常值情況，具有更好的魯棒性。因此可以總結為SIOMC算法在模擬數(shù)據(jù)的處理上相較于LMaFit等其他三種算法無論在增加矩陣的秩和噪聲比例的情況下，因為SIOMC在每一步迭代都對異常值進行處理，上一步的異常值沒有對下一步數(shù)據(jù)計算產(chǎn)生影響，因此有較強的魯棒性。

5.2 真實數(shù)據(jù)實驗

在本節(jié)中，將提出的算法SIOMC應用到具體的推薦系統(tǒng)問題中，分別基于公開數(shù)據(jù)集和本校在線平臺成績數(shù)據(jù)進行算法比較。公開數(shù)據(jù)集為廣泛應用的推薦系統(tǒng)數(shù)據(jù)Jester數(shù)據(jù)集（http://www.ieor.berkeley.edu/～goldberg/jester-data/）和 Movie 數(shù) 據(jù) 集（https://grouplens.org/datasets/movielens/）。Jester數(shù)據(jù)集有73 496個用戶對100個笑話開展的410萬次評分，不同的數(shù)據(jù)集代表不同大小的數(shù)據(jù)規(guī)模；Movie數(shù)據(jù)集中是用戶對自己看過電影的評分，三個數(shù)據(jù)集不同規(guī)模，用來比較實驗中算法應用于不同大小數(shù)據(jù)規(guī)模的實驗性能，數(shù)據(jù)集詳情如表1所示。第一部分實驗選用的兩個數(shù)據(jù)集是人為對笑話或電影進行評分，整個評分矩陣是高度稀疏的，不能保證所有的評分都在正常范圍內。例如在對電影的評分中，有的人可能對沒看過的電影進行評分，因此數(shù)據(jù)集中存在部分異常值的情況。

Table 1 Details of real datasets表1 真實數(shù)據(jù)集細節(jié)

實驗中將這些數(shù)據(jù)分為訓練集和測試集兩部分（采樣率為0.8），隨機選取80%評分信息作為訓練集，其余部分作為測試集。實驗中采用式（15）給定的error作為矩陣恢復準確性的度量。分別將SIOMC算法與其他三種矩陣補全算法相比較，性能比較詳情如表2所示。

Table 2 RMSE results of different algorithms on different datasets表2 不同數(shù)據(jù)集算法RMSE比較

表2顯示進行SIOMC處理后的數(shù)據(jù)error的值相較于SVT、IALM和LMaFit更小。SIOMC在過程中增加異常值處理機制，識別異常值的同時對異常值進行近似值代替處理，能夠降低異常值對結果的不利影響，提高算法的魯棒性，從而使結果更加精確。

基于MovieLen三個數(shù)據(jù)集分別采用四種矩陣補全算法對數(shù)據(jù)進行處理，并記錄運行時間，如表3所示。采樣率分別為0.3、0.5、0.8。

表3顯示，隨著訓練集規(guī)模的增加，四種算法的運行時間都相應增加，其中SVT的增加速率在四種算法中最快，LMaFit與SIOMC的速率相似。以上四種矩陣補全算法，LMaFit的運行時間比其他三種算法同等采樣率情況下小，由于本文提出的算法增加了異常值矩陣，但由于異常矩陣僅記錄補全過程中的差異，因此運行時間雖不及LMaFit，但也優(yōu)于SVT算法和IALM算法。

第二部分實驗選擇在線平臺開放課程的學習者成績，由于測試題不是強制完成項目，許多學習者只完成了部分測試題，造成數(shù)據(jù)中存在大量的缺失項。之前的工作為根據(jù)學生在線成績的互評分數(shù)構建學生成績互評系統(tǒng)，在驗證學生互評成績的可信度的過程中需要根據(jù)學生之前的在線成績判斷學生互評成績的可信度，學生的在線成績的完整性和準確性需要得到保證，因此在之前的工作中嘗試利用矩陣補全技術對缺失數(shù)據(jù)進行補全，取得良好的補全效果。為了驗證SIOMC算法能否更好地應用于在線平臺學習者成績數(shù)據(jù)，降低成績數(shù)據(jù)中異常值對結果的影響，將SIOMC算法應用于本校在線平臺一個學期內的兩門課程測試成績上，同時與其他矩陣補全算法比較性能。兩門課程的基本信息如表4所示。

Table 4 Courses information表4 課程基本信息

圖3為成績矩陣最大的特征值大小分布情況，從圖中可以看出，學生成績矩陣的信息主要分布在部分數(shù)值較大的異常值上，因此利用矩陣補全算法來恢復學生成績中缺失信息是非常合理的。

Fig.3 Grade matrix singular value distribution圖3 學生成績矩陣奇異值分布情況

Table 3 Running time of different algorithms on different datasets表3 不同數(shù)據(jù)集算法運行時間比較

基于在線平臺學習者課程成績數(shù)據(jù)進行矩陣補全算法的相關實驗，分別比較SIOMC與SVT、IALM和LMaFit三種矩陣補全算法的性能。本實驗中分別采用RMSE和error衡量算法性能，實驗結果包括的RMSE和error詳細信息分別如表5、表6顯示。表5顯示不同算法在課程成績數(shù)據(jù)上的RMSE對比，表6顯示不同算法在課程成績數(shù)據(jù)上的error指標對比。

Table 5 Comparative RMSE measurement on course data of different algorithms表5 不同算法在課程成績數(shù)據(jù)上的RMSE指標對比

Table 6 Comparative error measurement on course data of different algorithms表6 不同算法在課程成績數(shù)據(jù)上的error指標對比

從表5和表6可以看出，比較SVT、LMaFit、IALM和SIOMC對本校學生在線成績的衡量結果顯示，SIOMC相較于其他三種算法具有更高的精確度，在處理真實數(shù)據(jù)的情況中，SIOMC算法可以較為精確地處理數(shù)據(jù)。

6 結論

本文提出了一個新的能夠準確處理低秩矩陣的方法，不同于其他算法直接優(yōu)化整個矩陣，本文算法在優(yōu)化之前對異常值進行識別并處理。該過程可以將異常值自動處理，從而提高后續(xù)迭代過程的精確度。通過準確識別異常值的位置并對異常值進行處理，從而使結果更加精確。通過每一步迭代產(chǎn)生的誤差矩陣返回的異常值位置可以快速準確地識別異常值并對其進行處理。實驗證明，這個方法與LMaFit相比在增加噪聲的情況下有更好的魯棒性，并且結果更加精確。