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

雷恒鑫，劉驚雷

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

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

雷恒鑫，劉驚雷*

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

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

行列聯合選擇算法；特征選擇；矩陣恢復；可解釋性；穩定性

0 引言

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

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

本文主要利用行列聯合選擇(Column Union Row, CUR)算法實現特征選擇，利用改進的CUR算法實現矩陣恢復。本文具有如下特點和貢獻：

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

2)改進了CUR算法，根據正交三角分解(OrthogonalRotation,QR)具有數值上的穩定性的特點，利用QR分解方法代替原始的廣義逆方法，構造矩陣U，提高了CUR算法進行矩陣恢復的準確性和穩定性。

3)通過在電影評分數據集上進行實驗，驗證了在相同實驗條件下，CUR分解進行特征選擇的可解釋性和特征選擇能力比SVD等矩陣分解方法要好，利用改進的CUR進行矩陣恢復，其穩定性和準確性要高于SVD等矩陣分解方法。

1 相關工作

1.1 特征選擇的方法和技術

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

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

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

1.2 矩陣恢復

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

2 CUR分解的基本概念和相關定義

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

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

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

(1)

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

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

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

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

A≈CUR

(2)

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

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

圖1 CUR分解示意圖

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

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

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

表1 用戶-電影評分矩陣

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

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

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

經過上面的步驟，已經隨機構造出了矩陣C、U和R。下面對C、U和R這3個矩陣相乘，進行矩陣恢復。

根據表1寫出原始矩陣A：

ERROR=‖A-CUR‖F/‖A‖F*100%

(3)

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

3 通過CUR進行特征選擇和矩陣恢復

本章利用改進的CUR進行特征選擇和矩陣恢復，通過例子和大量實驗證實了改進的CUR能夠提高特征選擇和矩陣恢復能力，改進后的CUR算法比原始的CUR算法在矩陣恢復方面更加地穩定和準確。

3.1 利用統計影響力評分提高特征選擇能力

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

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

(4)

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

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

(5)

CUR算法提高特征選擇能力關鍵的步驟是利用統計影響力評分進行行列選擇，先來介紹一下列選擇算法。下面是列選擇算法的執行步驟：

算法1 列選擇算法。

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

輸出：C∈Rm×c。

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

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

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

返回：C∈Rm×c。

3.2 改進CUR算法提高矩陣恢復準確性和穩定性

通過大量的實驗，發現利用原始的CUR矩陣分解構造矩陣U，也就是通過廣義逆矩陣構造矩陣U，進行矩陣恢復的結果非常不準確，因此本文借用成熟穩定的QR分解代替廣義逆構造矩陣U，后面的實驗結果表明，通過QR分解來構造矩陣U，其矩陣恢復的穩定性和準確性比原始的CUR分解和其他矩陣分解方式要高，因為QR的分解的優點是具有數值的穩定性。算法2描述了矩陣U的構造步驟。

算法2 矩陣U的構造。

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

輸出：U∈Rc×r。

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

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

返回：U∈Rc×r

3.3 利用改進的CUR算法進行特征選擇和矩陣恢復

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

算法3 利用改進CUR進行特征選擇和矩陣恢復。

1)先對Netflix數據集進行預處理，將Netflix數據集轉成User-Movie評分矩陣A∈Rm×n。

2)對矩陣A運行列選擇算法1構造矩陣C。

3)對矩陣AT運行列選擇算法1構造矩陣R。

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

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

圖2 原始CUR和改進CUR穩定性比較

3.4 算法求解實例

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

表2 用戶-電影評分矩陣

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

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

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

圖3 電影每一列的統計影響力

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

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

圖4 用戶每一行的統計影響力

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

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

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

4 CUR算法的性質分析

4.1 算法的時間復雜度分析

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

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

證畢。

4.2 算法的空間復雜度分析

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

證明 當CUR算法構造C矩陣和R矩陣的時候，需要將c列r行調入內存中，因此構造C矩陣需要O(mc)的空間，構造R矩陣需要O(rn)的空間，構造U矩陣需要O(cr)的空間，因此該算法的空間復雜度為O(mc+rn+cr)。

證畢。

5 實驗環境、結果與分析

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

5.1 實驗環境

本文實驗是在一臺計算機上進行的，計算機系統是Windows7 64位的操作系統，配有8GBDDR3內存和主頻為2.8GHz的IntelPentiumCPU，使用的軟件是Matlab7.0。每個實驗重復10次，取平均結果為最終實驗結果。

5.2 數據集

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

5.3 實驗設置

為了說明CUR算法在特征選擇和矩陣恢復方面的準確性和穩定性，把CUR算法和下面三種已經存在的特征提取和矩陣恢復算法進行比較。

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

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

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

5.4 實驗過程

5.4.1 通過CUR進行特征選擇

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

圖5 電影每一列的統計影響力分布

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

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

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

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

圖7 用戶每一行的統計影響力分布

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

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

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

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

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

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

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

5.4.2 通過改進的CUR進行矩陣恢復

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

5.5 結果

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

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

6 結語

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

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

)

[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中的協同過濾算法[D].北京:北京大學,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及其表達能力研究[J].自動化學報,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。

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

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

1001- 9081(2017)03- 0640- 07

10.11772/j.issn.1001- 9081.2017.03.640

TP

A