雷恒鑫，劉驚雷

(煙臺大學(xué) 計算機(jī)與控制工程學(xué)院，山東 煙臺 264005) (*通信作者電子郵箱jinglei_liu@sina.com)

利用CUR矩陣分解提高特征選擇與矩陣恢復(fù)能力

雷恒鑫，劉驚雷*

(煙臺大學(xué) 計算機(jī)與控制工程學(xué)院，山東 煙臺 264005) (*通信作者電子郵箱jinglei_liu@sina.com)

針對在規(guī)模龐大的數(shù)據(jù)中不能快速準(zhǔn)確地選擇用戶和產(chǎn)品的特征以及不能準(zhǔn)確預(yù)測用戶行為偏好的問題，提出一種CUR矩陣分解方法。該方法是從原始矩陣中選取少量列構(gòu)成C矩陣，選取少量行構(gòu)成R矩陣，然后利用正交三角分解(QR)構(gòu)造U矩陣。分解后的C矩陣和R矩陣分別是用戶和產(chǎn)品的特征矩陣，并且C和R矩陣是由真實(shí)的數(shù)據(jù)構(gòu)成的，因此能夠分析出具體的用戶和產(chǎn)品特征；為了能夠比較準(zhǔn)確地預(yù)測用戶的行為偏好，改進(jìn)了CUR算法，使其在矩陣恢復(fù)方面有更高的穩(wěn)定性和準(zhǔn)確性。最后在真實(shí)的數(shù)據(jù)集(Netflix數(shù)據(jù)集)上的實(shí)驗表明，與傳統(tǒng)的奇異值分解、主成分分析等矩陣分解方法相比：在特征選擇方面，CUR矩陣分解方法具有較高的準(zhǔn)確度和很好的可解釋性；在矩陣恢復(fù)方面，改進(jìn)的CUR矩陣分解方法具有較高的穩(wěn)定性和精確度，其準(zhǔn)確度能達(dá)到90%以上。CUR矩陣分解在推薦系統(tǒng)對用戶的推薦方面和交通系統(tǒng)預(yù)測交通流量方面有重要的應(yīng)用價值。

行列聯(lián)合選擇算法；特征選擇；矩陣恢復(fù)；可解釋性；穩(wěn)定性

0 引言

現(xiàn)實(shí)生活中，人們經(jīng)常對所購買的產(chǎn)品進(jìn)行評價。大多數(shù)商家都會在顧客購買完商品后，要求顧客對商品進(jìn)行打分和評論。系統(tǒng)收集顧客對商品的打分信息后會生成User-Item評分矩陣，然后對這個矩陣進(jìn)行分析處理，選擇出用戶的主要特征和產(chǎn)品的主要特征，以及某一類用戶主要喜歡產(chǎn)品的哪一類特征。商家拿到這些信息后，就會根據(jù)這些特征來調(diào)整庫存，系統(tǒng)就會向用戶推薦他們喜歡的產(chǎn)品等一些活動。在這一系列的分析當(dāng)中，特征選擇和預(yù)測用戶的偏好尤為重要[1]。無論是調(diào)整庫存還是預(yù)測用戶的偏好都是根據(jù)特征選擇的結(jié)果來進(jìn)行的[2-3]，當(dāng)預(yù)測用戶偏好的時候，可以對User-Item矩陣進(jìn)行分解。

傳統(tǒng)的矩陣分解方法，例如奇異值分解(Singular Value Decomposition, SVD)[4-5]、SVD++[6-7]以及主成分分析(Principal Component Analysis, PCA)[8-10]雖然能夠?qū)⒏呔S的User-Item評分矩陣分解成為低維的用戶矩陣和產(chǎn)品矩陣，但是分解出來的結(jié)果不具有可解釋性，因為分解出來的用戶矩陣和產(chǎn)品矩陣的每一行和每一列都不是原始的數(shù)值，無法用現(xiàn)實(shí)生活中的概念來解釋，也不能用實(shí)際的概念給每一行每一列命名，只能理解為潛在語義空間，因此分解后矩陣的可解釋性非常差。另外，因為分解后的矩陣中的數(shù)值并不是原始數(shù)據(jù)，通過矩陣恢復(fù)來預(yù)測用戶偏好的穩(wěn)定性和準(zhǔn)確度也較差。

本文主要利用行列聯(lián)合選擇(Column Union Row, CUR)算法實(shí)現(xiàn)特征選擇，利用改進(jìn)的CUR算法實(shí)現(xiàn)矩陣恢復(fù)。本文具有如下特點(diǎn)和貢獻(xiàn)：

1)通過CUR特征選擇方法，能夠從原始的User-Item評分矩陣選擇少量的行和列，進(jìn)而可以選擇出用戶和產(chǎn)品的主要特征，其構(gòu)造的C和R兩個矩陣是由真實(shí)的數(shù)據(jù)構(gòu)成，所以能夠通過C和R矩陣分析出具體的特征，具有較好的特征選擇能力、很好的可解釋性和較高的準(zhǔn)確度。

2)改進(jìn)了CUR算法，根據(jù)正交三角分解(OrthogonalRotation,QR)具有數(shù)值上的穩(wěn)定性的特點(diǎn)，利用QR分解方法代替原始的廣義逆方法，構(gòu)造矩陣U，提高了CUR算法進(jìn)行矩陣恢復(fù)的準(zhǔn)確性和穩(wěn)定性。

3)通過在電影評分?jǐn)?shù)據(jù)集上進(jìn)行實(shí)驗，驗證了在相同實(shí)驗條件下，CUR分解進(jìn)行特征選擇的可解釋性和特征選擇能力比SVD等矩陣分解方法要好，利用改進(jìn)的CUR進(jìn)行矩陣恢復(fù)，其穩(wěn)定性和準(zhǔn)確性要高于SVD等矩陣分解方法。

1 相關(guān)工作

1.1 特征選擇的方法和技術(shù)

特征選擇在很多書里面也叫作變量選擇或者屬性選擇，它能自動選擇出不同的屬性或者特征。特征選擇的本質(zhì)就是選擇一個特征的子集，這個特征的子集幾乎涵蓋了原始數(shù)據(jù)的所有特征。特征選擇和維度約減(降維)是不同的，雖然兩種方法都是在減少數(shù)據(jù)集特征(屬性)的數(shù)量，降維是通過創(chuàng)建一個新的特征組合來做的，數(shù)據(jù)已經(jīng)被改變。而特征選擇是通過排除或者包括特征數(shù)據(jù)來做的，數(shù)據(jù)不會被改變。降維的技術(shù)主要有主成分分析和奇異值分解[11-13]。特征選擇的方法可以幫助創(chuàng)建特征的集合，這個集合幾乎可以涵蓋原始數(shù)據(jù)所有的特征，因此可以通過這個集合來分析原始數(shù)據(jù)的特征。

特征選擇的方法可以用來識別和消除不必要的無關(guān)的和冗余的數(shù)據(jù)，特征選擇的方法有3種：第一種是過濾方法，過濾特征選擇方法應(yīng)用統(tǒng)計方法來分配每個特征的得分，每個特征根據(jù)得分和排名來確定是否可以被選擇；第二種方法是包裝方法，包裝方法考慮將一組特征作為一個搜索問題，搜索方法有使用啟發(fā)式的爬山算法或者最佳優(yōu)先搜索算法等，在搜索過程中表現(xiàn)優(yōu)異的特征子集會被選中；第三種方法是嵌入式方法，嵌入式特征選擇方法的最主要的特點(diǎn)是當(dāng)模型被創(chuàng)建的時候，這個被創(chuàng)建的模型是準(zhǔn)確的，最常見的一種特征選擇方法是正則化方法。

本文采用的CUR特征選擇方法[14-16]是第一種，即屬于過濾方法，CUR特征選擇方法就是利用統(tǒng)計影響力評分來計算每一行和每一列特征的得分，然后根據(jù)每一個行(列)特征的得分來決定行(列)是否被選擇。通過這一方法，將冗余的數(shù)據(jù)或者噪聲過濾掉，得到比較有代表性的特征的集合，通過這個集合，可以很容易和快速地分析原始數(shù)據(jù)具有的特征。本文使用CUR矩陣分解把高維數(shù)據(jù)轉(zhuǎn)到低維空間中，在低維空間[17]中來快速對用戶和電影的特征進(jìn)行選擇。

1.2 矩陣恢復(fù)

矩陣恢復(fù)是最近幾年非常流行的壓縮感知技術(shù)，在推薦系統(tǒng)數(shù)字圖像處理方面應(yīng)用得非常廣泛。通過分析近幾年舉辦的Netflixprice電影推薦大賽和百度電影推薦大賽以及阿里最近舉辦的天池大數(shù)據(jù)競賽中涉及的推薦算法，發(fā)現(xiàn)在進(jìn)行用戶偏好預(yù)測的時候，矩陣恢復(fù)應(yīng)用得非常廣泛。本文研究的一個方面是利用改進(jìn)的CUR算法進(jìn)行矩陣恢復(fù)，改進(jìn)的CUR算法比原始的CUR算法更加穩(wěn)定。2008年Bell等[18]指出矩陣分解模型是最精確的，而CUR矩陣分解保留了原始的數(shù)據(jù)，因此利用CUR進(jìn)行矩陣恢復(fù)具有準(zhǔn)確性和穩(wěn)定性。

2 CUR分解的基本概念和相關(guān)定義

原始的CUR矩陣分解中構(gòu)造中間矩陣U的時候需要用到廣義逆，所以先給出其定義。

定義1 廣義逆。若一般線性方程組:

AX=B，A∈Rm×n，X∈Rn，B∈Rm

(1)

若對任意B，都有X=A+B，則矩陣A+∈Rn×m稱為A的廣義逆。

簡單來說，廣義逆矩陣是對逆矩陣的推廣。

下面給出CUR分解的基本概念和相關(guān)定義，并通過例1加以說明。

定義2 CUR分解。CUR分解就是給定一個矩陣A∈Rm×n，然后從矩陣A里選擇c列來構(gòu)造矩陣C∈Rm×c。從矩陣A里選取r行來構(gòu)造r行n列的矩陣R，通過C和R矩陣的廣義逆來構(gòu)造矩陣U∈Rc×r：

A≈CUR

(2)

其中：C矩陣是由A矩陣的列所構(gòu)成，而列包含的是電影的特征/采樣，從C矩陣中分析出電影具體的特征。R矩陣是由A矩陣的行所構(gòu)成，而行包含的是對用戶的特征/采樣，從R矩陣中分析出用戶具體的特征，而U矩陣是表示用戶和產(chǎn)品之間的相關(guān)性。

圖1形象直觀地解釋了CUR矩陣分解的過程，即從真實(shí)矩陣A中通過列和行的特征顯著程度選擇特征顯著的行和列，然后構(gòu)成C、U和R三個維度比較低的矩陣。通過分析低維矩陣的特征來表示高維矩陣的特征。如果A矩陣代表一個User-Movie評分矩陣，圖1表示矩陣A維度較大，不容易分析用戶的行為偏好，通過CUR矩陣分解對高維矩陣A進(jìn)行降維，通過快速分析低維矩陣來快速找到用戶的行為偏好，因為CUR矩陣分解是從真實(shí)數(shù)據(jù)中按照特征的顯著程度抽取若干行和若干列進(jìn)行計算的，因此保證了分析結(jié)果的準(zhǔn)確性和可解釋性。

圖1 CUR分解示意圖

下面再來看一下偏好的類型，偏好包含定性偏好和定量偏好。例如CP-nets就是一種定性條件偏好模型[19]，它以序關(guān)系o1?o2表示o1優(yōu)于o2；而本文采用的是定量模型，即偏好用數(shù)值代表(用戶對電影的偏好是一個分?jǐn)?shù)，如表1所示)。

為了更好地理解CUR矩陣分解[20-21]的相關(guān)內(nèi)容，給出實(shí)例1說明。實(shí)例使用的數(shù)據(jù)集是由Netflix電影公司提供的數(shù)據(jù)集。為了便于理解、運(yùn)算和分析，從Netflix數(shù)據(jù)集選取了少量具有代表性的用戶和電影進(jìn)行CUR分解，通過這個例子，可以看出CUR分解的過程。

例1 如表1所示，矩陣A代表用戶對電影進(jìn)行評分的數(shù)據(jù)。通過分析CUR矩陣分解的過程，理解CUR矩陣分解的思路和原理。

表1 用戶-電影評分矩陣

如表1所示，把表中的User-movie評分矩陣稱為A。CUR算法要求需要從矩陣A中選取c列來構(gòu)造矩陣C，假如選取獅子王、灰姑娘、公主新娘這3列，這3列構(gòu)造出的C矩陣如下所示：

接下來隨機(jī)地從矩陣A中選取homemaker和student兩行，這兩行構(gòu)造出了矩陣R如下所示：

下面構(gòu)造中間矩陣U。U矩陣是3×2矩陣。構(gòu)造矩陣U需要用到廣義逆，通過上面的方法，構(gòu)造的U矩陣為：

經(jīng)過上面的步驟，已經(jīng)隨機(jī)構(gòu)造出了矩陣C、U和R。下面對C、U和R這3個矩陣相乘，進(jìn)行矩陣恢復(fù)。

根據(jù)表1寫出原始矩陣A：

ERROR=‖A-CUR‖F(xiàn)/‖A‖F(xiàn)*100%

(3)

通過計算，兩個矩陣的相似度為50.15%，通過上面的這兩個矩陣對比可以看到，利用原始的CUR矩陣分解方法進(jìn)行矩陣恢復(fù)的準(zhǔn)確度并不高，通過大量的實(shí)驗發(fā)現(xiàn)，這是因為在構(gòu)造C和R矩陣的時候有時候會把一些“不重要的行或者列”包含進(jìn)來，相當(dāng)于C矩陣和R矩陣中包含了一些干擾，因此在利用廣義逆求矩陣U時，干擾會進(jìn)一步擴(kuò)大，這就會在矩陣恢復(fù)的時候出現(xiàn)準(zhǔn)確度時好時壞不穩(wěn)定的狀況，因此下面改進(jìn)了矩陣U的求解方法，借用穩(wěn)定的QR分解來求解U，因為QR的分解的優(yōu)點(diǎn)是具有數(shù)值的穩(wěn)定性，大量的實(shí)驗證明這種方法在構(gòu)造矩陣U和進(jìn)行矩陣恢復(fù)時準(zhǔn)確性和穩(wěn)定性方面是非常高的。

3 通過CUR進(jìn)行特征選擇和矩陣恢復(fù)

本章利用改進(jìn)的CUR進(jìn)行特征選擇和矩陣恢復(fù)，通過例子和大量實(shí)驗證實(shí)了改進(jìn)的CUR能夠提高特征選擇和矩陣恢復(fù)能力，改進(jìn)后的CUR算法比原始的CUR算法在矩陣恢復(fù)方面更加地穩(wěn)定和準(zhǔn)確。

3.1 利用統(tǒng)計影響力評分提高特征選擇能力

從原始數(shù)據(jù)矩陣User-Item矩陣中選取列和行來構(gòu)造C和R矩陣時，為了提高特征選擇能力，需要選擇具有影響力的特征。比如在選擇列的時候[22-23]，需要選擇特征比較顯著的列，這些列在整個電影列中具有較大的影響力，占的權(quán)重比較大。同樣地，在選擇行的時候，需要選擇特征比較顯著的行，這些行在整個用戶行中具有比較大的影響力，占的權(quán)重比較大。

下面分析每一列的統(tǒng)計影響力評分如何計算。在線性代數(shù)中，原始矩陣的每一列可以用奇異值、左奇異向量和右奇異向量精確地表示：

(4)

當(dāng)從A中選擇小數(shù)量列構(gòu)造矩陣C的時候，就需要比較將要選擇的列在所有電影列中的影響力，也就是特征的顯著程度，這時候就需要計算每個列的統(tǒng)計影響力評分，通過統(tǒng)計影響力評分來確定為需要選擇哪些特征顯著的列，也可以把統(tǒng)計影響力評分理解正則化杠桿效應(yīng)值。

因為在奇異值分解中，右奇異向量的每一列代表具有同一類特征的電影，因此可以根據(jù)右奇異向量來計算每一列的統(tǒng)計影響力評分，也就是每一個電影列特征的顯著程度。左奇異向量的每一行代表具有同一類特征的用戶，因此可以根據(jù)左奇異向量來計算每一行的統(tǒng)計影響力評分，但是為了下面計算簡便，也為了節(jié)省運(yùn)算的時間和空間，只計算和存儲左奇異向量。在選擇行的時候，只需對矩陣作個轉(zhuǎn)置。式(5)是統(tǒng)計影響力評分的定義：

(5)

CUR算法提高特征選擇能力關(guān)鍵的步驟是利用統(tǒng)計影響力評分進(jìn)行行列選擇，先來介紹一下列選擇算法。下面是列選擇算法的執(zhí)行步驟：

算法1 列選擇算法。

輸入：任意A∈Rm×n，矩陣A的秩k，誤差元素。

輸出：C∈Rm×c。

1)計算A的前k個右奇異向量v1,v2,…,vk。

2)利用式(4)計算每一列的統(tǒng)計影響力評分。

3)選擇統(tǒng)計影響力評分最高的c=O(klgk/ε2)列(c列概率和大于80%)構(gòu)成矩陣C。

返回：C∈Rm×c。

3.2 改進(jìn)CUR算法提高矩陣恢復(fù)準(zhǔn)確性和穩(wěn)定性

通過大量的實(shí)驗，發(fā)現(xiàn)利用原始的CUR矩陣分解構(gòu)造矩陣U，也就是通過廣義逆矩陣構(gòu)造矩陣U，進(jìn)行矩陣恢復(fù)的結(jié)果非常不準(zhǔn)確，因此本文借用成熟穩(wěn)定的QR分解代替廣義逆構(gòu)造矩陣U，后面的實(shí)驗結(jié)果表明，通過QR分解來構(gòu)造矩陣U，其矩陣恢復(fù)的穩(wěn)定性和準(zhǔn)確性比原始的CUR分解和其他矩陣分解方式要高，因為QR的分解的優(yōu)點(diǎn)是具有數(shù)值的穩(wěn)定性。算法2描述了矩陣U的構(gòu)造步驟。

算法2 矩陣U的構(gòu)造。

輸入：A∈Rm×n，r行n列的矩陣R，C∈Rm×c。

輸出：U∈Rc×r。

1)對C作QR矩陣分解獲得矩陣C的基礎(chǔ)列，C=QcRc。

2)對R作QR矩陣分解獲得矩陣R的基礎(chǔ)行，R=QrRr。

返回：U∈Rc×r

3.3 利用改進(jìn)的CUR算法進(jìn)行特征選擇和矩陣恢復(fù)

CUR算法因為利用了統(tǒng)計影響力評分這個強(qiáng)有力的工具，加上其分解后的矩陣包含的是真實(shí)的行和列，數(shù)據(jù)沒有失真，因此其特征選擇能力大幅度提高，并且具有非常好的可解釋性。而且因為其分解后C和R矩陣保留了原始矩陣的數(shù)據(jù)，通過改進(jìn)的CUR進(jìn)行矩陣恢復(fù)，其矩陣恢復(fù)的穩(wěn)定性和準(zhǔn)確性大幅度增強(qiáng)。改進(jìn)的CUR特征選擇和矩陣恢復(fù)算法的偽代碼如算法3所示。

算法3 利用改進(jìn)CUR進(jìn)行特征選擇和矩陣恢復(fù)。

1)先對Netflix數(shù)據(jù)集進(jìn)行預(yù)處理，將Netflix數(shù)據(jù)集轉(zhuǎn)成User-Movie評分矩陣A∈Rm×n。

2)對矩陣A運(yùn)行列選擇算法1構(gòu)造矩陣C。

3)對矩陣AT運(yùn)行列選擇算法1構(gòu)造矩陣R。

4)利用算法2計算矩陣U。

通過在多個數(shù)據(jù)集上進(jìn)行實(shí)驗，證實(shí)改進(jìn)的CUR進(jìn)行矩陣恢復(fù)的穩(wěn)定性比原始CUR進(jìn)行矩陣恢復(fù)穩(wěn)定性好。圖2是在Netflix電影數(shù)據(jù)集下隨著選擇行和列數(shù)量的變化，改進(jìn)的CUR算法與原始的CUR算法的穩(wěn)定性和誤差對比。

圖2 原始CUR和改進(jìn)CUR穩(wěn)定性比較

3.4 算法求解實(shí)例

例1 從Netflix用戶電影評分?jǐn)?shù)據(jù)集里選取了具有3個年齡段特征人：10到25歲的青少年Joe和Jim，30到50歲的中年John、Jack和Jill，50歲到80歲的老年Jenny和Jane；同時分別從Netflix數(shù)據(jù)集里選取了具有3種特征的電影，分別是科幻電影、言情電影和傳記電影。對表2中的評分矩陣先執(zhí)行CUR矩陣分解，然后從分解后的C和R矩陣中進(jìn)行特征選擇，最后進(jìn)行矩陣的恢復(fù)。

表2 用戶-電影評分矩陣

將表2中的矩陣稱為矩陣A，然后對矩陣A運(yùn)行改進(jìn)CUR特征選擇算法進(jìn)行用戶和電影特征的選擇。首先，需要從C中選擇統(tǒng)計影響力較高的列進(jìn)行選擇，先對矩陣A計算其奇異值，找到右奇異向量，奇異值分解之后的右奇異向量如下所示：

然后根據(jù)右奇異向量計算每一列的統(tǒng)計影響力評分，在Matlab上運(yùn)行改進(jìn)CUR算法，得出每一列的統(tǒng)計影響力評分分布如圖3所示。從圖3中可以看出第1列、第4列和第5列的統(tǒng)計影響力評分比較高，說明其特征比較顯著，因此，選擇第1列、第4列和第5列構(gòu)成C矩陣：

因為C矩陣中的列是由真實(shí)數(shù)據(jù)構(gòu)成的，所以可以從真實(shí)數(shù)據(jù)中找到C中的每一列屬于哪一個具體的電影，根據(jù)真實(shí)的電影分析出C中每一列的特征。改進(jìn)CUR算法通過統(tǒng)計影響力得分提高了特征選擇能力，并且根據(jù)真實(shí)數(shù)據(jù)構(gòu)造的C矩陣具有非常好的可解釋性。

圖3 電影每一列的統(tǒng)計影響力

從圖4中可以看出第2行、第4行和第7行的統(tǒng)計影響力評分比較高，說明其特征比較顯著，因此，選擇第2行、第4行和第7行構(gòu)成R矩陣：

因為R矩陣中的行是由真實(shí)數(shù)據(jù)構(gòu)成的，所以可以從真實(shí)數(shù)據(jù)中找到R中的每一行屬于哪一個具體的用戶，根據(jù)真實(shí)的用戶分析出R中每一行的特征。改進(jìn)CUR算法通過統(tǒng)計影響力得分提高了特征選擇能力，并且根據(jù)真實(shí)數(shù)據(jù)構(gòu)造的R矩陣具有非常好的可解釋性。

圖4 用戶每一行的統(tǒng)計影響力

下面分析一下C矩陣包含哪些電影的主要特征。因為C矩陣是由真實(shí)的數(shù)據(jù)構(gòu)成的，根據(jù)C矩陣的列和Netflix數(shù)據(jù)集的電影匹配，得到的結(jié)果為：第1列屬于科幻類，第4列屬于言情類，第5列屬于傳記類。

然后分析一下R矩陣包含哪些用戶的主要特征。因為R矩陣是由真實(shí)的數(shù)據(jù)構(gòu)成的，根據(jù)R矩陣的行和Netflix數(shù)據(jù)集的用戶匹配，會得到第2行用戶的年齡是27歲，屬于青少年用戶；第4行用戶的年齡是43歲，屬于中年用戶；第7行用戶的年齡是56歲，屬于老年用戶。

通過上面這個例子，可以分析出用戶和電影的具體特征，這說明CUR特征選擇算法確實(shí)擁有較高的特征選擇和分析能力，這是傳統(tǒng)矩陣分解算法所不具有的特點(diǎn)。然后利用改進(jìn)的CUR和原始的CUR進(jìn)行矩陣恢復(fù)，原始的CUR使用廣義逆矩陣方法求U，改進(jìn)CUR使用QR分解求U，將分解后的C、U和R三個矩陣相乘，比較一下兩種方法進(jìn)行矩陣恢復(fù)的準(zhǔn)確度。利用式(3)計算改進(jìn)的CUR矩陣恢復(fù)的準(zhǔn)確度達(dá)到了83.63%。然而通過原始的CUR分解，其矩陣恢復(fù)得準(zhǔn)確度只有67.27%。所以改進(jìn)U的構(gòu)造在矩陣恢復(fù)方面是有很明顯的效果的。后面的實(shí)驗也驗證了改進(jìn)的CUR在矩陣恢復(fù)方面有較高的準(zhǔn)確性和穩(wěn)定性。

4 CUR算法的性質(zhì)分析

4.1 算法的時間復(fù)雜度分析

定理1 CUR算法的時間復(fù)雜度是O(nr2+mc2+(klgk)/ε2)。

證明 CUR算法首先需要計算每一列的統(tǒng)計影響力評分，需要的時間復(fù)雜度是O((klgk)/ε2)，利用QR矩陣分解求U的時候時間復(fù)雜度是O(nr2+mc2)，所以CUR算法總的時間復(fù)雜度為O(nr2+mc2+(klgk)/ε2)。

證畢。

4.2 算法的空間復(fù)雜度分析

定理2 CUR算法的空間復(fù)雜度是O(mc+rn+cr)。

證明 當(dāng)CUR算法構(gòu)造C矩陣和R矩陣的時候，需要將c列r行調(diào)入內(nèi)存中，因此構(gòu)造C矩陣需要O(mc)的空間，構(gòu)造R矩陣需要O(rn)的空間，構(gòu)造U矩陣需要O(cr)的空間，因此該算法的空間復(fù)雜度為O(mc+rn+cr)。

證畢。

5 實(shí)驗環(huán)境、結(jié)果與分析

本章通過公開的可獲得的真實(shí)數(shù)據(jù)集進(jìn)行測試，并且對已經(jīng)存在的偏好特征提取算法(SVD，PCA，SVD++)進(jìn)行比較。

5.1 實(shí)驗環(huán)境

本文實(shí)驗是在一臺計算機(jī)上進(jìn)行的，計算機(jī)系統(tǒng)是Windows7 64位的操作系統(tǒng)，配有8GBDDR3內(nèi)存和主頻為2.8GHz的IntelPentiumCPU，使用的軟件是Matlab7.0。每個實(shí)驗重復(fù)10次，取平均結(jié)果為最終實(shí)驗結(jié)果。

5.2 數(shù)據(jù)集

實(shí)驗使用著名電影公司Netflix提供的數(shù)據(jù)集進(jìn)行測試，Netflix數(shù)據(jù)集包含480 189個用戶，17 770部電影，100 480 507條評分記錄。利用這個數(shù)據(jù)集對改進(jìn)的CUR算法以及已知的矩陣分解算法的特征選擇性能和矩陣恢復(fù)的穩(wěn)定性及準(zhǔn)確性進(jìn)行評估。

5.3 實(shí)驗設(shè)置

為了說明CUR算法在特征選擇和矩陣恢復(fù)方面的準(zhǔn)確性和穩(wěn)定性，把CUR算法和下面三種已經(jīng)存在的特征提取和矩陣恢復(fù)算法進(jìn)行比較。

1)SVD：SVD是主要的特征構(gòu)造方式。它通過矩陣分解的方式，將數(shù)據(jù)從高維空間映射到低維空間，對數(shù)據(jù)進(jìn)行降維。

2)SVD++：SVD的一種改進(jìn)算法，SVD算法是指在SVD的基礎(chǔ)上引入隱式反饋，使用用戶的歷史瀏覽數(shù)據(jù)、用戶歷史評分?jǐn)?shù)據(jù)、電影的歷史瀏覽數(shù)據(jù)和電影的歷史評分?jǐn)?shù)據(jù)等作為新的參數(shù)。

3)PCA：PCA是最主要的一種特征提取方式。它通過特征分解能夠得到每一個維度對于整個數(shù)據(jù)的最小均方差的貢獻(xiàn)程度，從而定量判斷每一維對于數(shù)據(jù)所包含信息的貢獻(xiàn)度。然后保留最主要的一些維度，拋棄一些不顯著的維度，從而實(shí)現(xiàn)對數(shù)據(jù)進(jìn)行降維。

5.4 實(shí)驗過程

5.4.1 通過CUR進(jìn)行特征選擇

所使用的Netflix數(shù)據(jù)集包含17 770個用戶和100 480 507部電影，因為所使用的計算機(jī)內(nèi)存有限，所以選取了700個用戶和1 000部電影的評分。對700×1 000的評分矩陣運(yùn)行CUR特征選擇算法，首先計算電影的統(tǒng)計影響力評分，也就是看看電影有哪些主要的特征，通過程序計算出統(tǒng)計影響力評分最高的17列的概率和大于80%，因此這17列是所有特征列中最主要的，圖5也可以看出只有很少的列統(tǒng)計影響力評分很高。

圖5 電影每一列的統(tǒng)計影響力分布

如圖5所示，除了圖中17個特征列比較突出外，其余列的特征(統(tǒng)計影響力評分)不顯著，因此就把這17個特征列從原始矩陣中抽取出來構(gòu)成矩陣C。

矩陣C的列就代表了1 000部電影幾乎所有的特征。因為電影公司Netflix在提供數(shù)據(jù)集的同時也提供了2份文件，1份文件包含了這1 000部電影的信息，1份文件包含了這700個用戶的信息。因為矩陣C是由原始數(shù)據(jù)構(gòu)成的，每一列對應(yīng)的是一部真實(shí)的電影，將矩陣C的每一列通過和真實(shí)的電影信息比對，就能發(fā)現(xiàn)電影的具體特征。圖6就是和真實(shí)的電影信息相比較之后分析出的具體特征，而傳統(tǒng)的SVD或者SVD++是無法獲取具體特征的。從條形圖中只看到9個特征，而不是17個特征。為了保證所選的列能夠反映所有列的特征，CUR多選擇了一些列，從而提高選擇的精度。

圖6 通過CUR選擇出的電影的具體特征

然后再計算用戶的統(tǒng)計影響力評分，也就是看看用戶有哪些主要的特征，通過程序計算出統(tǒng)計影響力評分最高的10行的概率和大于80%，因此這10行是所有特征行中最主要的，圖7也可以看出只有很少的行統(tǒng)計影響力評分很高。

圖7 用戶每一行的統(tǒng)計影響力分布

如圖7所示，除了圖中的10個特征行比較突出外，其余行的特征不顯著，因此就把這10個特征行從原始矩陣中抽取出來構(gòu)成矩陣R。因為矩陣R是由原始數(shù)據(jù)構(gòu)成的，每一行對應(yīng)的是一個真實(shí)的用戶，將矩陣R的每一行通過和真實(shí)的用戶信息比對，就能發(fā)現(xiàn)用戶的具體特征。圖8就是和真實(shí)的用戶信息相比較之后分析出的具體特征。

圖8 通過CUR選擇出的用戶的具體特征

從條形圖中只看到5個特征，但是原來選擇了10行，那是因為CUR在選擇具有顯著特征的行的時候為了保證所選的行能夠代表所有列的特征，所以多選擇了一小部分，也可以理解為是為了滿足精度的要求。

下面在同樣規(guī)模的Netflix數(shù)據(jù)下用PCA進(jìn)行用戶特征的選擇發(fā)現(xiàn)直接對原始數(shù)據(jù)直接執(zhí)行PCA只能找出少數(shù)2個特征，第一個特征的貢獻(xiàn)率為72%，第二個特征的貢獻(xiàn)率為14%，這兩個特征的貢獻(xiàn)率的和達(dá)到了86%，其他特征貢獻(xiàn)率極小，PCA給忽略了。那是因為PCA將所有的樣本(特征向量集合)作為一個整體對待，去尋找一個均方誤差最小意義下的最優(yōu)線性映射投影，而忽略了類別屬性，而它所忽略的投影方向有可能剛好包含了重要的可分性信息，因此使用PCA會忽略掉很多信息。

下面在同樣規(guī)模的Netflix數(shù)據(jù)下用PCA進(jìn)行電影特征的選擇發(fā)現(xiàn)對原始數(shù)據(jù)直接執(zhí)行PCA只能找出少數(shù)3個特征，第一個特征的貢獻(xiàn)率為60%，第二個特征的貢獻(xiàn)率為24%，第三個特征的貢獻(xiàn)率為11%，這三個特征的貢獻(xiàn)率的和達(dá)到了95%，其他特征貢獻(xiàn)率極小，PCA給忽略了。原因也是因為PCA忽略了類別屬性，導(dǎo)致使用PCA會忽略掉很多信息。

表3展示了在Netflix數(shù)據(jù)集上，在相同的實(shí)驗條件下，通過運(yùn)行CUR、SVD、PCA和SVD++四種矩陣分解方法的運(yùn)行時間和誤差率對比。

表3 不同矩陣分解方法運(yùn)行時間和誤差率比較

5.4.2 通過改進(jìn)的CUR進(jìn)行矩陣恢復(fù)

使用改進(jìn)的CUR分解在Netflix電影數(shù)據(jù)集上進(jìn)行矩陣恢復(fù)。下面是在Netflix電影數(shù)據(jù)集上進(jìn)行恢復(fù)，不同的矩陣分解方法進(jìn)行恢復(fù)的穩(wěn)定性和準(zhǔn)確度對比。圖9展示了，在Netflix數(shù)據(jù)集上，CUR、PCA、SVD和SVD++恢復(fù)的精確度的變化。從圖9中可以看到，隨著矩陣規(guī)模的增加，改進(jìn)的CUR分解比PCA等矩陣分解的精確度高，在穩(wěn)定性方面改進(jìn)的CUR分解波動比SVD等矩陣分解的波動要小，其穩(wěn)定性比較高。

5.5 結(jié)果

通過上面的實(shí)驗，可以發(fā)現(xiàn)用CUR特征選擇算法能夠從數(shù)據(jù)集中比較準(zhǔn)確的選取具有較高統(tǒng)計影響力的特征，并且在選取特征行和特征列之后，通過Netflix數(shù)據(jù)集給出了用戶和電影的具體信息，能夠分析出選取的特征行和特征列有哪些具體的特征，具有非常好的可解釋性。通過改進(jìn)的CUR進(jìn)行矩陣恢復(fù)，與其他矩陣分解算法相比，其結(jié)果具有較高的穩(wěn)定性和精確度，因此改進(jìn)的CUR特征選擇和矩陣恢復(fù)算法在推薦系統(tǒng)方面的前景非常廣闊。

圖9 4種矩陣分解方法精確度的變化

6 結(jié)語

CUR算法在選取行列的時候是根據(jù)行列的實(shí)際情況比較智能地進(jìn)行選擇，在機(jī)器學(xué)習(xí)方面，可以理解為在選取行列的時候，CUR算法主動學(xué)習(xí)和判斷電影列的統(tǒng)計影響力來判斷電影特征的顯著程度，然后根據(jù)電影特征的顯著程度智能地從電影列中進(jìn)行抓取，所以構(gòu)造出的C(R)矩陣也反映了電影(用戶)的現(xiàn)實(shí)特征，通過分析C(R)矩陣就可以選擇出電影(用戶)的特征，并且因為C(R)矩陣是由真實(shí)的行列構(gòu)成，因此將C(R)矩陣中的行列數(shù)據(jù)和Netflix數(shù)據(jù)集相比對就能夠確定用戶和電影的具體特征。在矩陣恢復(fù)方面，改進(jìn)的CUR穩(wěn)定性和精確性都有了明顯提升，在進(jìn)行推薦也就是預(yù)測用戶偏好的時候，利用改進(jìn)的CUR算法具有較高的穩(wěn)定性和精確性。

未來的工作包括：1)CUR算法在面對大規(guī)模數(shù)據(jù)的時候擁有自己的優(yōu)勢，比如快速、準(zhǔn)確、具有良好的可解釋性，彌補(bǔ)了PCA在面對大規(guī)模數(shù)據(jù)的時候誤差較高的不足，但是因為用到了奇異值分解，所以運(yùn)行時間上可能會稍微遜色一點(diǎn)，因此，接下來會把CUR特征選擇算法改進(jìn)成并行算法，提高CUR算法的運(yùn)行速度。2)該CUR算法在對原始矩陣的行列進(jìn)行選擇的時候，因為原始用戶-電影評分矩陣很稀疏，選出的行和列大部分都存在很多缺失值，對缺失值的填充數(shù)值不同，近似的情況以及準(zhǔn)確度也不相同，因此，接下來的工作需要探索填充缺失值的方法有哪些，以及如何對缺失值進(jìn)行填充才能使得CUR矩陣分解的準(zhǔn)確度更高。

)

[1]BUSA-FEKETER,SZ?RéNYIB,WENGP,etal.Preference-basedreinforcementlearning:evolutionarydirectpolicysearchusingapreference-basedracingalgorithm[J].MachineLearning, 2014, 97(3): 327-351.

[2]BOBADILLAJ,ORTEGAF,HERNANDOA.Recommendersystemssurvey[J].Knowledge-BasedSystems, 2013, 46(1): 109-132.

[3] 吳金龍.NetflixPrize中的協(xié)同過濾算法[D].北京:北京大學(xué),2010:7-10.(WUJL,CollaborativefilteringalgorithminPrizeNetflix[D].Beijing:PekingUniversity, 2010:7-10.)

[4]GERBRANDSJJ.OntherelationshipsbetweenSVD,KLTandPCA[J].PatternRecognition, 1981, 14(1/2/3/4/5/6): 375-381.

[5]SHNAYDERMANA,GUSEVA,ESKICIOGLUAM.AnSVD-basedgrayscaleimagequalitymeasureforlocalandglobalassessment[J].IEEETransactionsonImageProcessing, 2006, 15(2): 422-429.

[6]KUMARR,VERMABK,RASTOGISS.SocialpopularitybasedSVD++recommendersystem[J].InternationalJournalofComputerApplications, 2014, 87(14): 33-37.

[7]JIAY,ZHANGC,LUQ,etal.Users’brandspreferencebasedonSVD++inrecommendersystems[C]//Proceedingsofthe2014IEEEWorkshoponAdvancedResearchandTechnologyinIndustryApplications.Piscataway,NJ:IEEE, 2014: 1175-1178.

[8]GAOC,ZHOUHH.Rate-optimalposteriorcontractionforsparsePCA[J].TheAnnalsofStatistics, 2015, 43(2): 785-818.

[9]BERTOLINIAC,SCHIOZERDJ.Principalcomponentanalysisforreservoiruncertaintyreduction[J].JournaloftheBrazilianSocietyofMechanicalSciencesandEngineering, 2016, 38(4):1345-1355.

[10]XUF,GUG,KONGX,etal.Objecttrackingbasedontwo-dimensionalPCA[J].OpticalReview, 2016, 23(2): 231-243.

[11]WATKINSDS.FundamentalsofMatrixComputations[M].NewYork:JohnWiley&Sons, 1991: 2-30.

[12]ACHLIOPTASD,MCSHERRYF.Fastcomputationoflow-rankmatrixapproximations[C]//Proceedingsofthe33rdAnnualACMSymposiumonTheoryofComputing.NewYork:ACM, 2001: 611-618.

[13]PFINGSTNERJ,SCHULTED,SNUVERINKJ,etal.SVD-basedfilterdesignforthetrajectoryfeedbackofCLIC[EB/OL]. [2016- 03- 10].http://epaper.kek.jp/IPAC2011/papers/mopo014.pdf.

[14]DRINEASP,MAHONEYMW,MUTHUKRISHNANS.Relative-errorCURmatrixdecompositions[J].SIAMJournalonMatrixAnalysisandApplications, 2008, 30(2): 844-881.

[15]BOUTSIDISC,WOODRUFFDP.OptimalCURmatrixdecompositions[C]//Proceedingsofthe46thAnnualACMSymposiumonTheoryofComputing.NewYork:ACM, 2014:353-362.

[16]BIENJ,XUY,MAHONEYMW.CURfromasparseoptimizationviewpoint[EB/OL]. [2016- 03- 08].http://www.stat.berkeley.edu/～mmahoney/pubs/cur-spca.pdf.

[17]WANGL,REGEM,DONGM,etal.Low-rankkernelmatrixfactorizationforlargescaleevolutionaryclustering[J].IEEETransactionsonKnowledgeandDataEngineering, 2012, 24(6): 1036-1050.

[18]BELLRM,KORENY,VOLINSKYC.TheBellKor2008solutiontotheNetflixPrize[EB/OL]. [2016- 02- 21].http://xueshu.baidu.com/s?wd=paperuri%3A%289ef8f488c3613e6a70daca0f02435bb8%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D3DFEC03FEB7FC3D400E97763E310721E%3Fdoi%3D10.1.1.448.222%26rep%3Drep1%26type%3Dpdf&ie=utf-8&sc_us=13947115770219594334.

[19] 劉驚雷.CP-nets及其表達(dá)能力研究[J].自動化學(xué)報,2011,37(3):290-302.(LIUJL.CP-netsandstudyofexpressionability[J].ActaAutomaticaSinica, 2011, 37(3): 290-302.)[20] WANG S, ZHANG Z. Improving CUR matrix decomposition and the Nystr?m approximation via adaptive sampling [J]. Journal of Machine Learning Research, 2013, 14(1): 2729-2769.

[21] WEIMER M, KARATZOGLOU A, SMOLA A. Improving maximum margin matrix factorization [J]. Machine Learning, 2008, 72(3): 263-276.

[22] GURUSWAMI V, SINOP A K. Optimal column-based low-rank matrix reconstruction [C] // Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2012: 1207-1214.

[23] BOUTSIDIS C, DRINEAS P, MAGDON-ISMAIL M. Near-optimal column-based matrix reconstruction [C]// Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 2011: 305-314.

This work is partially supported by the National Natural Science Foundation of China (61572419, 61572418, 61403328, 61403329), the Natural Science Foundation of Shandong Province (ZR2014FQ016, ZR2014FQ026, 2015GSF115009, ZR2013FM011).

LEI Hengxin, bron in 1993, M. S. candidate. His research interests include the matrix decomposition and its application.

LIU Jinglei, born in 1970, M. S., associate professor. His research interests include artificial intelligence and theoretical computer science.

Improving feature selection and matrix recovery ability by CUR matrix decomposition

LEI Hengxin, LIU Jinglei*

(SchoolofComputerandControlEngineering,YantaiUniversity,YantaiShandong264005,China)

To solve the problem that users and products can not be accurately selected in large data sets, and the problem that user behavior preference can not be predicted accurately, a new method of CUR (Column Union Row) matrix decomposition was proposed. A small number of columns were selected from the original matrix to form the matrixC,andasmallnumberofrowswereselectedtoformthematrixR.Then,thematrixUwasconstructedbyOrthogonalRotation(QR)matrixdecomposition.ThematrixesCandRwerefeaturematrixesofusersandproductsrespectively,whichwerecomposedofrealdata,andenabledtoreflectthedetailedcharactersofbothusersaswellasproducts.Inordertopredictbehavioralpreferencesofusersaccurately,theauthorsimprovedtheCURalgorithminthispaper,endowingitwithgreaterstabilityandaccuracyintermsofmatrixrecovery.Lastly,theexperimentbasedonrealdataset(Netflixdataset)indicatesthat,comparedwithtraditionalsingularvaluedecomposition,principalcomponentanalysisandothermatrixdecompositionmethods,theCURmatrixdecompositionalgorithmhashigheraccuracyaswellasbetterinterpretabilityintermsoffeatureselection,asformatrixrecovery,theCURmatrixdecompositionalsoshowssuperiorstabilityandaccuracy,withaprecisenessofover90%.TheCURmatrixdecompositionhasagreatapplicationvalueintherecommendersystemandtrafficflowprediction.

Column Union Row (CUR) algorithm; feature selection; matrix recovery; interpretability; stability

2016- 09- 28;

2016- 10- 16。

國家自然科學(xué)基金資助項目(61572419, 61572418, 61403328, 61403329)；山東省自然科學(xué)基金資助項目(ZR2014FQ016, ZR2014FQ026, 2015GSF115009, ZR2013FM011)。

雷恒鑫(1993—),男,山東陽谷人,碩士研究生,主要研究方向: 矩陣分解及其應(yīng)用; 劉驚雷(1970—),男,山西臨猗人,副教授,碩士,CCF會員,主要研究方向:人工智能、理論計算機(jī)科學(xué)。

1001- 9081(2017)03- 0640- 07

10.11772/j.issn.1001- 9081.2017.03.640

TP

A