使用關(guān)聯(lián)檢索緩和推薦系統(tǒng)中的稀疏性問題

張 洋，高艷華，郭曉坤

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

1 引言

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

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

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

2 協(xié)同過濾和稀疏性問題

2.1 協(xié)同過濾

協(xié)同過濾又稱社會(huì)過濾，它通過分析用戶的興趣，在用戶群中找到特定用戶的相似用戶，綜合這些相似用戶對(duì)某一信息的評(píng)價(jià)來形成對(duì)指定用戶對(duì)此信息的喜好程度的預(yù)測。

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

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

大多數(shù)協(xié)同過濾算法可以分為兩類[12]：基于內(nèi)容的協(xié)同過濾算法和基于模型的協(xié)同過濾算法?；趦?nèi)容的協(xié)同過濾算法首先從訓(xùn)練集數(shù)據(jù)庫中找到與當(dāng)前測試用戶最相似的用戶，然后將這些相似用戶給出的評(píng)分進(jìn)行組合以獲得對(duì)測試用戶的預(yù)測。兩種最常用的方法是Pearson相關(guān)和角度余弦。Pearson相關(guān)和角度余弦已經(jīng)應(yīng)用于許多實(shí)例中，例如，缺席投票，案例擴(kuò)展，加權(quán)優(yōu)勢預(yù)測等。基于模型的算法首先收集評(píng)分?jǐn)?shù)據(jù)以進(jìn)行研究，以此推斷用戶的行為模型以及對(duì)產(chǎn)品進(jìn)行評(píng)分。

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

2.2 稀疏性

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

(1)

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

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

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

3 基于關(guān)聯(lián)檢索的協(xié)同過濾

3.1 關(guān)聯(lián)檢索

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

3.2 通過關(guān)聯(lián)檢索找到用戶之間的關(guān)系

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

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

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

根據(jù)關(guān)聯(lián)檢索理論，以用戶為一組節(jié)點(diǎn)，產(chǎn)品為一組節(jié)點(diǎn)，使用二部圖表示矩陣B，如圖1所示。

圖1 協(xié)同過濾中的傳遞關(guān)聯(lián)

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

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

定義1：直接推薦路徑表示某用戶直接推薦給目標(biāo)用戶項(xiàng)目。

定義2：間接推薦路徑表示某用戶通過一個(gè)或多個(gè)用戶推薦給目標(biāo)用戶項(xiàng)目。

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

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

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

(2)

3.3 計(jì)算直接相似矩陣

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

(3)

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

(4)

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

接下來，結(jié)合關(guān)聯(lián)檢索和直接相似度矩陣進(jìn)行計(jì)算，以便在獲得用戶相似度矩陣后獲得推薦矩陣。

3.4 計(jì)算推薦矩陣

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

推薦矩陣Martix_R定義為

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

3.5 算法介紹

基于關(guān)聯(lián)檢索的協(xié)同過濾算法：

輸入：用戶評(píng)分矩陣R，路徑長度M

輸出：推薦矩陣

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

步驟2、設(shè)置迭代次數(shù)N=1

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

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

步驟5、將矩陣B轉(zhuǎn)置BT

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

步驟7、如果N+2M

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

使用推薦系統(tǒng)的標(biāo)配實(shí)驗(yàn)數(shù)據(jù)Movielens數(shù)據(jù)集。數(shù)據(jù)集包含了943位用戶對(duì)1682部電影的100，000個(gè)評(píng)分，評(píng)分區(qū)間為1-5，每個(gè)用戶至少評(píng)價(jià)了20部電影，稀疏度為99.937%。

4.2 實(shí)驗(yàn)過程

對(duì)于每個(gè)目標(biāo)消費(fèi)者，檢索了之前查看過的全部商品，并按查看日期將它們分類。這些項(xiàng)目的前90%作為訓(xùn)練數(shù)據(jù)集輸入，通過不同的方法產(chǎn)生建議。為了進(jìn)行比較，這些項(xiàng)目的后10%作為客戶的預(yù)測數(shù)據(jù)集，并被隱藏在推薦系統(tǒng)中。

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

● 皮爾遜相關(guān)系數(shù)(Pearson Correlation Coefficient簡稱PCC)

皮爾遜相關(guān)系數(shù)方法預(yù)測用戶x對(duì)項(xiàng)目i的評(píng)分為：

(5)

(6)

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

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

(7)

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

(8)

(9)

(10)

(11)

4.3 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中，將提出的方法稱為AR-CF(基于關(guān)聯(lián)檢索的協(xié)同過濾)。根據(jù)Movielens數(shù)據(jù)集對(duì)于AR-CF，PC和COS算法分別計(jì)算準(zhǔn)確率，召回率和F值。在AR-CF中，M的值為3。表1、圖2至圖5是上述三個(gè)算法在準(zhǔn)確率、召回率、F值和覆蓋率上的綜合比較。

在準(zhǔn)確率方面，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在準(zhǔn)確率、召回率、F值和覆蓋率方面都有了很大的提高。還發(fā)現(xiàn)，在稀疏情況下，COS的表現(xiàn)最差。在覆蓋率方面，AR-CF僅比PC增長4.66%。還進(jìn)行了另一個(gè)實(shí)驗(yàn)，結(jié)果表明，當(dāng)M=5時(shí)，覆蓋率可以增加10%以上，計(jì)算的開銷大大增加，但是推薦精度的增加卻很小。本文認(rèn)為覆蓋率降低的原因有兩個(gè)，一方面是因?yàn)镸的值為3，另一方面，實(shí)驗(yàn)數(shù)據(jù)集的稀疏程度可能還不夠。

表1 綜合比較

圖2 預(yù)測準(zhǔn)確率的比較

圖3 F值的比較

圖4 召回率的比較

圖5 覆蓋率的比較

5 結(jié)論

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