使用關聯檢索緩和推薦系統中的稀疏性問題

張 洋，高艷華，郭曉坤

(1.中國航天科工二院，北京 100039;2.北京控制與電子技術研究所軟件研發(fā)中心，北京 100038)

1 引言

隨著互聯網的快速發(fā)展，連接到互聯網的服務器數量和WWW上的Web數量呈指數級增長趨勢。同時互聯網的快速發(fā)展為人們提供了大量信息，例如，Netflix擁有成千上萬部電影，亞馬遜擁有數百萬本書，Del.icio.us擁有超過100億個頁面集，因此很多信息不可能一次全部給出。傳統的搜索算法僅向所有用戶提供相同的有序結果，不能根據用戶的不同興趣向不同的用戶提供不同的服務，信息爆炸降低了信息的使用率，這種現象稱為信息過載。個性化推薦(包括個性化搜索)被認為是解決信息過載問題的最有效工具之一。從根本上說，推薦系統是替代用戶來評估各種產品，包括書籍，電影，CD，Web等，這是一個從已知到未知的過程[1]。

推薦作為一種社會過程，在消費者的許多應用中起著重要作用，因為對于每個消費者而言，獨立地了解所有可能的替代方案的成本過高。根據特定的應用程序設置，消費者可能是買家，信息搜索者或正在搜索某些專業(yè)知識的組織[2]。

目前，推薦算法主要包括協同過濾算法、基于內容的算法、基于用戶產品的二元關系圖推薦算法[3]和混合推薦算法[4]，在對于稀疏性方面的研究還處于起步階段。本文著眼于稀疏性和精度問題，通過用戶評分之間的相對距離來計算相似矩陣，并創(chuàng)造性地使用關聯檢索技術，來實現一種新的協同過濾算法，此算法對緩和數據集的稀疏性方面有很明顯的效果。

2 協同過濾和稀疏性問題

2.1 協同過濾

協同過濾又稱社會過濾，它通過分析用戶的興趣，在用戶群中找到特定用戶的相似用戶，綜合這些相似用戶對某一信息的評價來形成對指定用戶對此信息的喜好程度的預測。

迄今為止，協同過濾是最成功的推薦系統方法，并且已廣泛應用于各種應用程序中。其中，Grundy被認為是第一個協同過濾系統[5]。Grundy系統可以建立用戶的偏好模型，以向每個用戶推薦相關的書籍。 Tapestry郵件處理系統，處理用戶之間的相似性。用戶越多，精度越低[6]。 GroupLens建立用戶的信息組，用戶組內的用戶可以發(fā)布自己的信息，并與其他用戶進行協同推薦[7]。 Ringo利用相同的社交信息過濾方法向用戶推薦音樂[8]。還有其它一些典型的協同過濾推薦系統，例如Amazon.Com[9]，Jester[10]，Phoaks[11]等。

協同過濾的推薦系統主要可分成三個步驟：①輸入資料表示：將用戶過去的行為及興趣用一個m×n的矩陣R來表示，亦即n個用戶層利用m項產品的歷史資料，矩陣元素rij則表示第i個用戶購買第j個產品。②相似度的建立：是協同過濾推薦系統中最重要的一個步驟，可以計算出用戶間的相似程度，以作為將來推薦的依據。③產生推薦：從社群成員中衍生出對目標用戶的前n項推薦產品。

大多數協同過濾算法可以分為兩類[12]：基于內容的協同過濾算法和基于模型的協同過濾算法。基于內容的協同過濾算法首先從訓練集數據庫中找到與當前測試用戶最相似的用戶，然后將這些相似用戶給出的評分進行組合以獲得對測試用戶的預測。兩種最常用的方法是Pearson相關和角度余弦。Pearson相關和角度余弦已經應用于許多實例中，例如，缺席投票，案例擴展，加權優(yōu)勢預測等。基于模型的算法首先收集評分數據以進行研究，以此推斷用戶的行為模型以及對產品進行評分。

但是協同過濾方法也具有幾個主要限制，包括稀疏性、可伸縮性和同義詞問題。當事務或反饋數據稀疏且不足以標識鄰居時，就會出現稀疏性問題，這是一個主要問題，通常會限制建議的質量和協同過濾的適用性。研究重點是即使沒有足夠的數據，也要開發(fā)一種有效的方法來提供高質量的建議。

2.2 稀疏性

在協同過濾系統中，用戶或消費者通常由他們購買或評價的物品代表。例如，在電影院中有300萬部電影，則每個使用者都由300萬個元素的布爾特征向量表示。每個元素的值取決于該消費者過去是否觀看過相應的電影。通常，值1到5表示發(fā)生了事件，值0表示沒有發(fā)生這種事件。當涉及多個消費者時，可以使用由代表這些消費者的所有向量組成的矩陣來捕獲過去的觀看事件。稱此矩陣為消費者與產品的交互矩陣。在本文中，用C表示消費者集合，用I表示項目集合。用矩陣R=|C|×|I|=(rij)代表消費者-產品交互矩陣，其中

(1)

在許多大型應用中，物品的數量和消費者的數量都很大。在這種情況下，即使記錄了許多事件，消費者與產品的交互矩陣仍然可以非常稀疏，即R中的非0元素很少。此問題通常稱為稀疏性問題，對協同過濾方法的有效性產生很大負面影響。由于稀疏性，兩個給定用戶之間的相似性(或相關性)極有可能為零，從而使協同過濾失效[13]。即使對于正相關的用戶對，此類相關度量也可能不可靠。而冷啟動問題進一步說明了解決稀疏性問題的重要性。冷啟動問題是指新用戶或新項目剛剛進入系統的情況[14]。由于缺乏足夠的先前評級或購買，協同過濾無法為新用戶生成有用的推薦。同樣，當有新商品進入系統時，協同過濾系統不太可能將其推薦給大多數用戶，因為很少有用戶對該商品進行評分或購買。從概念上講，冷啟動問題可以看作是稀疏性問題的一個特殊實例，即消費者與產品交互矩陣A的某些行或列中的大多數元素為0[2]。許多研究人員已嘗試緩解稀疏性問題。在文獻[14]中，作者提出了一種基于項目的方法來解決可伸縮性和稀疏性問題。另一種緩解稀疏性的方法是降維，旨在直接降低消費者-產品交互矩陣的維。減少維度的一種簡單策略是形成項目或用戶的集群，然后將這些集群用作預測中的基本單位。也可以應用更先進的技術來實現降維，包括統計技術(例如主成分分析(PCA)[10])和信息檢索技術(例如潛在語義索引(LSI))。本質上，降維方法通過生成更密集的用戶-項目交互矩陣來處理稀疏性問題，然后使用此精簡矩陣進行預測。實驗研究表明，降維可以在某些應用程序中顯著提高推薦質量，但在有些應用程序中卻表現不佳，在此縮減過程中可能會丟失潛在有用的信息[15]。

研究人員還嘗試將協同過濾與基于內容的推薦方法相結合以緩解稀疏性問題[16][17]。除了用戶項目交互之外，此類技術還考慮了從其內容派生的項目之間的相似性，這使他們可以做出更準確的預測。但是，混合方法需要有關產品的附加信息以及用于計算產品之間有意義的相似度的度量。在實踐中，這種產品信息和相關的相似性度量可能很難獲得。另一類方法是將數據視為二部圖，其中節(jié)點代表用戶和項目，如果用戶i評價過項目j，則在用戶i和項目j之間存在一條邊(i，j)。此外，邊(i，j)的權重對應于i到j的等級。然后使用圖形理論測度得出用戶或項目之間的全局相似性。例如，將兩個用戶之間的相似度計算為在圖的隨機游走中其各自節(jié)點之間的平均通勤時間。還研究了其它圖形理論量度，例如圖形節(jié)點之間的最小跳躍距離，以及圖形中節(jié)點的擴展激活。這些方法的主要缺點是：在預測問題的背景下，通常對相似性度量沒有很好的解釋[18]。

研究的重點是開發(fā)一種計算方法，以探索用戶之間的關聯來解決稀疏性問題，并在協同過濾的前提下提高準確性。

3 基于關聯檢索的協同過濾

3.1 關聯檢索

在文本分析中，關聯檢索將詞語和文檔之間的關聯關系進行統計和研究。關聯檢索背后的基本思想是：建立文檔、索引項、查詢的圖模型或網絡模型，然后使用該模型探索詞語與文檔之間的傳遞關聯性，以提高信息檢索的質量。這種關系也反映在人們的日常生活中，例如，UA是UB的朋友，UC是UA的朋友，則UB可以向UC推薦電影A，因此，UC和UB之間存在關聯關系。發(fā)現推薦系統可以利用用戶之間的這種關系來解決稀疏性問題。

3.2 通過關聯檢索找到用戶之間的關系

首先假設一個用戶集C={c1，c2，c3}包含了三個用戶，和一個電影集I={i1，i2，i3，i4}包括了四部電影。R=|C|×|I|代表用戶的評分矩陣，包含了3×4=12個元素。

其中行代表用戶，列代表電影。例如，第一行代表用戶c1觀看了電影i2和i4，等級分別為3和4．

從矩陣B的第二行可以發(fā)現用戶c2觀看了電影i2，i3和i4，從矩陣R和矩陣B中很容易發(fā)現用戶c1和c2都觀看了電影i2和i4。根據相似性理論，可以確定用戶c1與用戶c2相似，因此可以通過用戶c2將電影i3推薦給用戶c1，但不能將電影i1推薦給c1。以上示例僅包含4部電影，然而當前在線電影提供商超過百萬部電影，如果僅通過直接相似度進行用戶推薦，就會出現“暗信息”，某些電影將無法推薦給某些用戶，無法滿足用戶的需求。

根據關聯檢索理論，以用戶為一組節(jié)點，產品為一組節(jié)點，使用二部圖表示矩陣B，如圖1所示。

圖1 協同過濾中的傳遞關聯

根據圖1，關聯路徑的長度假定為3，這里有c1-i2-c2-i3和c1-i4-c2-i3兩條路徑，電影i3應該推薦給用戶c1，但在i1和c1之間沒有一個長度為3的路徑，所以i1不會推薦給c1。如果路徑長度拓展到5，發(fā)現電影i1可以通過路徑c1-i2-c2-i3-c3-i1和c1-i4-c2-i3-c3-i1推薦給用戶c1。

針對以上分析，本文作了一些定義如下：

定義1：直接推薦路徑表示某用戶直接推薦給目標用戶項目。

定義2：間接推薦路徑表示某用戶通過一個或多個用戶推薦給目標用戶項目。

定義3：用戶直接相似度表示直接推薦路徑中用戶之間的相似度。

定義4：用戶間接相似度表示間接推薦路徑中推薦用戶與目標用戶之間的相似度。

通過以上分析可知，關聯檢索方法可以探索用戶之間的傳遞，以獲得一組路徑以及直接或間接的相似度。通過式(2)計算稀疏矩陣中rij的值以解決稀疏性問題。

(2)

3.3 計算直接相似矩陣

在用戶直接相似度矩陣的計算中，沒有使用Pearson相關系數和余弦相似度。通過研究，發(fā)現用戶觀看電影后，無論用戶的評分高低，在一定程度上都可以表達用戶之間在個人偏好和評分偏好上的相似之處。例如，在矩陣R中，用戶c1和c2分別為i2和i4打分，c1的等級為3和4，c2的等級為2和5，可以使用式(3)計算c1和c2對同一電影的相似度等級sim_2(12)=0.8，sim_4(12)=0.8．

(3)

其中max是最大值函數，abs是絕對值函數，R代表評級的集合，例如R={0，1，2，3，4，5}，rik代表用戶i對產品k的評價值。獲得相似度等級后，使用式(4)計算i和j之間的用戶相似度

(4)

注意到，m為產品數量。以評分矩陣R為例，用戶相似度aij=(0.8+0.8)÷4=0.4，根據此方式，可以得到用戶相似度矩陣Asim如下

接下來，結合關聯檢索和直接相似度矩陣進行計算，以便在獲得用戶相似度矩陣后獲得推薦矩陣。

3.4 計算推薦矩陣

使用3.2節(jié)提供的數據推薦給用戶c1。當M=3時，從數據中可以發(fā)現c1有兩個推薦路徑c1-i2-c2-i3和c1-i4-c2-i3。根據3.3節(jié)的相似度矩陣，c1和c2之間的相似度為0.4，路徑權重為0.4;因此得到i3的相關度是0.4×2=0.8; 由于c1和c2具有最高的相似性，因此c2對i3的評分值為3，因此推薦值為0.8。當M=5時，有兩個推薦路徑c1-i2-c2-i3-c3-i1和c1-i4-c2-i3-c3-i1，權重為a12×a23=0.4×0.25=0.1，相關度的值為0.1×2=0.2，用戶c3對i1的評分為4，所以推薦值是0.2×4=0.8。

推薦矩陣Martix_R定義為

其中R是評分矩陣，Asim是相似度矩陣，B是標記矩陣。利用3.2節(jié)的數據，通過式(4)，在M=3和M=5時，可以分別得到推薦矩陣Matrix_R3和Matrix_R5

3.5 算法介紹

基于關聯檢索的協同過濾算法：

輸入：用戶評分矩陣R，路徑長度M

輸出：推薦矩陣

步驟1、B=R， 如果rij≠0，那么bij=1

步驟2、設置迭代次數N=1

步驟3、原始推薦矩陣Matrix_RN=R

步驟4、根據式(3)和(4)計算直接相似矩陣Asim

步驟5、將矩陣B轉置BT

步驟6、根據式(5)計算矩陣Matrix_RM

步驟7、如果N+2M

4 實驗與分析

4.1 實驗數據集

使用推薦系統的標配實驗數據Movielens數據集。數據集包含了943位用戶對1682部電影的100，000個評分，評分區(qū)間為1-5，每個用戶至少評價了20部電影，稀疏度為99.937%。

4.2 實驗過程

對于每個目標消費者，檢索了之前查看過的全部商品，并按查看日期將它們分類。這些項目的前90%作為訓練數據集輸入，通過不同的方法產生建議。為了進行比較，這些項目的后10%作為客戶的預測數據集，并被隱藏在推薦系統中。

在實驗中，比較了基于Pearson相關系數推薦、基于余弦相似度推薦和本文所提出的方法。使用準確率(Precision)、召回率(Recall)、覆蓋率(Coverage)和F值(F-Measure)來衡量給定推薦方法的有效性，這些方法在信息檢索和推薦系統研究中被廣泛接受。

● 皮爾遜相關系數(Pearson Correlation Coefficient簡稱PCC)

皮爾遜相關系數方法預測用戶x對項目i的評分為：

(5)

(6)

● 余弦相似度(Vector Similarity簡稱VS)

該方法與PCC非常相似，不同之處在于相關系數sim(x，y)的計算公式為：

(7)

準確率(Precision)、召回率(Recall)、覆蓋率(Coverage)和F值(F-Measure)的定義如下：

(8)

(9)

(10)

(11)

4.3 實驗結果

在實驗中，將提出的方法稱為AR-CF(基于關聯檢索的協同過濾)。根據Movielens數據集對于AR-CF，PC和COS算法分別計算準確率，召回率和F值。在AR-CF中，M的值為3。表1、圖2至圖5是上述三個算法在準確率、召回率、F值和覆蓋率上的綜合比較。

在準確率方面，AR-CF與PC相比增長了18.40%，比COS增長了33.48%；在召回率方面，AR-CF與PC相比增長了17.55%，與COS相比增長了66.78%。在F值方面，AR-CF與PC相比增長了18.29%，與COS相比增長了34.23%；在覆蓋率方面，AR-CF與PC相比增長了4.66%，與COS相比增長了24.78%。綜上所述，AR-CF在準確率、召回率、F值和覆蓋率方面都有了很大的提高。還發(fā)現，在稀疏情況下，COS的表現最差。在覆蓋率方面，AR-CF僅比PC增長4.66%。還進行了另一個實驗，結果表明，當M=5時，覆蓋率可以增加10%以上，計算的開銷大大增加，但是推薦精度的增加卻很小。本文認為覆蓋率降低的原因有兩個，一方面是因為M的值為3，另一方面，實驗數據集的稀疏程度可能還不夠。

表1 綜合比較

圖2 預測準確率的比較

圖3 F值的比較

圖4 召回率的比較

圖5 覆蓋率的比較

5 結論

本文旨在緩解稀疏性問題來提高協同過濾系統中的推薦精度。使用關聯檢索技術緩解稀疏性問題，并提出了一種新的協同過濾算法以提高推薦精度；使用Movielens數據集中的數據通過第4章實驗，得到AR-CF算法在推薦過程中是可以正常運行的，論證了該方法的有效性；通過實驗表明，與標準協同過濾方法相比AR-CF算法的準確率、F-值、召回率和覆蓋率都有了明顯提升，該方法緩解了稀疏性問題，并獲得了更好的推薦質量。同時，本文提出的方法也存在問題。這些系統利用的數據量將隨著時間的推移繼續(xù)增加。在這種情況下，此方法將導致數據過載問題。最終，它將對協同過濾推薦器的可伸縮性提出重大挑戰(zhàn)。因此，在接下來的研究中，將考慮協同過濾推薦器的可伸縮性問題。