李可欣，徐 彬，高克寧

東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110000

1 引言

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

為了解決上述問(wèn)題，本文提出了一種新的非線(xiàn)性過(guò)放縮異常值自識(shí)別算法。該方法可以識(shí)別出異常值的位置并對(duì)異常值進(jìn)行近似值替代，降低異常值對(duì)結(jié)果的影響，相較于已有矩陣補(bǔ)全算法的恢復(fù)結(jié)果也更加精確。

2 相關(guān)工作

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

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

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

本文分別進(jìn)行了人工數(shù)據(jù)和真實(shí)數(shù)據(jù)的矩陣補(bǔ)全實(shí)驗(yàn)分析，討論四種矩陣補(bǔ)全算法的時(shí)間及魯棒性能。實(shí)驗(yàn)結(jié)果顯示SIOMC算法相較于其他矩陣補(bǔ)全算法，在處理異常值矩陣性能更加優(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ù)的矩陣補(bǔ)全問(wèn)題都是在如下模型的基礎(chǔ)上提出的：

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

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

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

4 優(yōu)化算法

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

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

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

首先固定U和V，求解如下問(wèn)題：

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

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

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

如果該值為異常值即Λi,j=1，將其與進(jìn)行替換，上一步迭代中更新的目標(biāo)矩陣中對(duì)應(yīng)的值。

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

更新U：

更新V：

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

算法1 SIOMC

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

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

Whileiter＜maxiterdo

5 實(shí)驗(yàn)

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

5.1 合成數(shù)據(jù)實(shí)驗(yàn)

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

均方根誤差的定義為：

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

相對(duì)重構(gòu)誤差的定義為：

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

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

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

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

5.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)

在本節(jié)中，將提出的算法SIOMC應(yīng)用到具體的推薦系統(tǒng)問(wèn)題中，分別基于公開(kāi)數(shù)據(jù)集和本校在線(xiàn)平臺(tái)成績(jī)數(shù)據(jù)進(jìn)行算法比較。公開(kāi)數(shù)據(jù)集為廣泛應(yīng)用的推薦系統(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個(gè)用戶(hù)對(duì)100個(gè)笑話(huà)開(kāi)展的410萬(wàn)次評(píng)分，不同的數(shù)據(jù)集代表不同大小的數(shù)據(jù)規(guī)模；Movie數(shù)據(jù)集中是用戶(hù)對(duì)自己看過(guò)電影的評(píng)分，三個(gè)數(shù)據(jù)集不同規(guī)模，用來(lái)比較實(shí)驗(yàn)中算法應(yīng)用于不同大小數(shù)據(jù)規(guī)模的實(shí)驗(yàn)性能，數(shù)據(jù)集詳情如表1所示。第一部分實(shí)驗(yàn)選用的兩個(gè)數(shù)據(jù)集是人為對(duì)笑話(huà)或電影進(jìn)行評(píng)分，整個(gè)評(píng)分矩陣是高度稀疏的，不能保證所有的評(píng)分都在正常范圍內(nèi)。例如在對(duì)電影的評(píng)分中，有的人可能對(duì)沒(méi)看過(guò)的電影進(jìn)行評(píng)分，因此數(shù)據(jù)集中存在部分異常值的情況。

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

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

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

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

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

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

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

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

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

Fig.3 Grade matrix singular value distribution圖3 學(xué)生成績(jī)矩陣奇異值分布情況

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

基于在線(xiàn)平臺(tái)學(xué)習(xí)者課程成績(jī)數(shù)據(jù)進(jìn)行矩陣補(bǔ)全算法的相關(guān)實(shí)驗(yàn)，分別比較SIOMC與SVT、IALM和LMaFit三種矩陣補(bǔ)全算法的性能。本實(shí)驗(yàn)中分別采用RMSE和error衡量算法性能，實(shí)驗(yàn)結(jié)果包括的RMSE和error詳細(xì)信息分別如表5、表6顯示。表5顯示不同算法在課程成績(jī)數(shù)據(jù)上的RMSE對(duì)比，表6顯示不同算法在課程成績(jī)數(shù)據(jù)上的error指標(biāo)對(duì)比。

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

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

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

6 結(jié)論

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