于世彩, 謝穎華, 王 巧

?

協(xié)同過濾的相似度融合改進算法①

于世彩, 謝穎華, 王 巧

(東華大學信息科學與技術學院, 上海 201620)

針對傳統(tǒng)協(xié)同過濾推薦在數(shù)據(jù)稀疏性條件下性能不佳的問題, 在相似度計算上做出了優(yōu)化, 提出了一種基于項目類別和用戶興趣相似度融合的協(xié)同過濾算法, 算法將相似度的計算分解為兩個方面進行: 用戶-項目類別評分相似度和用戶-項目類別興趣相似度, 將兩者用合適的權值加以融合得到最終相似度, 參與最終預測評分的計算. 利用MovieLens公用數(shù)據(jù)集對改進前后的算法進行對比. 結果表明, 基于項目類別和用戶興趣的協(xié)同過濾改進算法有效地緩解了數(shù)據(jù)稀疏性問題的影響, 提高了推薦的準確性.

協(xié)同過濾; 數(shù)據(jù)稀疏性; 項目類別; 用戶興趣; 相似度融合

互聯(lián)網(wǎng)的發(fā)展帶來了便利的同時, 也造成了信息量的急速增長和膨脹, 出現(xiàn)了“信息過載”[1]現(xiàn)象. 互聯(lián)網(wǎng)信息過于豐富甚至超出了瀏覽者能夠有效利用的范圍, 導致了信息的利用率低下, 人們必須耗費大量的時間和精力才能找到需要的信息. 為緩解這一個問題, 多種方法被提了出來, 信息檢索在其中扮演著重要的角色, 然而“一視同仁”的特性致使它忽略了用戶特性, 其輸出結果僅與輸入的關鍵字有關, 對用戶來說, 仍需要耗費大量時間篩選出所需信息, 信息過載問題并沒有得到有效的解決. 個性化推薦系統(tǒng)能夠在信息過載的大環(huán)境下, 幫助用戶快速從海量數(shù)據(jù)中找到所需信息.

推薦過程依賴于3個要素: 推薦候選對象、用戶和推薦方法[2]. 推薦系統(tǒng)使用戶擺脫了單向的搜索服務, 實現(xiàn)了用戶和系統(tǒng)的雙向溝通, 在電子商務中扮演著重要的角色. 為了不斷提高推薦效果的精確性與有效性, 提升推薦系統(tǒng)的整體性能, 不同的推薦技術陸續(xù)被提了出來, 其中包括基于用戶統(tǒng)計信息的推薦、基于內容的推薦、協(xié)同過濾推薦以及基于混合模型的推薦等[3].

協(xié)同過濾推薦技術是目前最廣為應用也是效果最理想的推薦技術[4], 它通過用戶-項目評分矩陣來計算并確定目標用戶的最近鄰居用戶集合, 根據(jù)集合中各鄰居對各項目的評分得到目標用戶的預測評分, 最終將評分最高的項目推薦給用戶. 協(xié)同過濾推薦技術不需要提供領域的知識, 并且會隨著時間的推移, 用戶對項目評分的完善, 推薦的質量和準確度也會大幅提升; 另一方面, 由于協(xié)同過濾推薦對用戶評分的依賴性很強, 網(wǎng)絡結構、用戶和項目數(shù)量的急劇增長使得數(shù)據(jù)稀疏等問題漸漸暴露了出來.

根據(jù)有關資料的統(tǒng)計[5], 大型電子商務系統(tǒng)中, 所有用戶購買過并給出評分的商品數(shù)只占到系統(tǒng)中商品總量的 1%~2%左右. 面對這種數(shù)據(jù)極端稀疏的情況, 在為用戶找到鄰居集合的方面, 協(xié)同過濾算法就變得力不從心, 這也就進一步導致了推薦質量的大幅降低, 這一問題也成為了制約協(xié)同過濾應用與發(fā)展的最主要問題.

1 數(shù)據(jù)稀疏性問題[6]

由于網(wǎng)站結構的日漸復雜, 用戶和項目數(shù)量的急劇增長, 使評價過的項目數(shù)占系統(tǒng)中項目總數(shù)的比例越來越小, 導致相似度計算時沒有足夠的輸入數(shù)據(jù), 從而得不到準確的相似度, 進而降低了系統(tǒng)的推薦質量. 假設一個稀疏的評分矩陣如表1.

表1 稀疏的評分矩陣

由該表可以看出, 用戶1和2沒有共同評分的項目, 因此由傳統(tǒng)的協(xié)同過濾算法計算的二者相似度為0, 但是用戶1與2、2和3之間的相似度都是不為0的, 換句話說就是3同時與1、2相似, 由相似的傳遞性可知用戶1、2之間并不是完全不相關的, 這說明數(shù)據(jù)稀疏性影響了用戶鄰居的確定, 不僅降低了推薦質量, 也嚴重影響了推薦精度.

不少研究者從很早就意識到了數(shù)據(jù)稀疏性的對于推薦質量的制約, 研究并提出了多種方法來緩解數(shù)據(jù)稀疏性造成的影響. 其中應用較廣泛的有矩陣填充技術、矩陣降維技術和基于聚類的方法[7].

1) 矩陣填充技術

所謂矩陣填充技術, 就是將用戶-項目評分矩陣中沒有評分的項目用特定的數(shù)值替換掉, 以此直接的降低數(shù)據(jù)的稀疏性, 提高推薦質量和精度. 在這種情況下, 閾值的選取就顯得尤為重要, 一般來說, 這個值常取評分區(qū)間的中間值或者是所有評分的平均值. 這就產(chǎn)生了一個問題, 雖說這種方法改善了數(shù)據(jù)的稀疏性問題, 但是他忽略了用戶的個性和評分習慣的差異, 并沒能使數(shù)據(jù)稀疏問題從根本上得到解決.

2) 矩陣降維技術

矩陣降維技術, 就是降低用戶-項目評分矩陣的維數(shù), 將系統(tǒng)中未被評分的項目或者是未評過分的用戶刪掉就是最簡單也是最直接矩陣降維方法, 但是, 這種方法應用起來會導致沒有評過分的用戶就不會接收到系統(tǒng)的推薦, 沒有被評過分的項目也不會被推薦給用戶.

3) 基于聚類的方法

聚類方法中, 系統(tǒng)用特定的標準將各個項目集合劃分到若干個聚類中, 相同聚類是具有相似屬性的若干個不同項目的集合, 不同的聚類中的各個項目則具有不同的屬性. 通常采用的聚類方法[8]主要有: K-Means 聚類、基于網(wǎng)格的聚類、基于密度的聚類和 PAM 算法等.

以上幾種方法的主要思想是對矩陣進行降維或者填充, 然而單純的填充忽略了用戶個性, 而降維技術又不可避免的導致了某些信息的丟失, 都不能較好的解決數(shù)據(jù)稀疏性問題. 因此需要尋求一種方法, 不改變評分矩陣稀疏性程度, 卻能達到有效提高推薦算法精度的目的, 于是本文提出了基于項目類別和用戶興趣相似度融合的協(xié)同過濾算法.

2 協(xié)同過濾的相似度融合改進算法

考慮到數(shù)據(jù)稀疏性的影響, 本文對相似度的計算做出優(yōu)化, 將傳統(tǒng)的計算過程一分為二, 分別在項目類別評分矩陣和量化的用戶興趣矩陣上計算用戶相似度并融合, 引入兩個調節(jié)項來進行相似度的修正.

2.1 傳統(tǒng)用戶相似度的計算

用戶相似度的計算是推薦算法中最核心的部分, 傳統(tǒng)計算的相似度的方法主要有三種: 余弦相似度、修正的余弦相似度和相關相似度[9].

用戶評分數(shù)據(jù)用矩陣表示, 其中,表示用戶個數(shù),r表示用戶u對項目的評分, 于是用戶相似度可以簡單地利用余弦相似度計算得到.

在這種情況下, 要求相似性的兩個項目被看作𝑚維用戶空間的兩個向量. 向量代表用戶對所有項目的評分所構成的向量, 向量代表用戶對所有項目的評分所構成的向量, 用戶和用戶之間的相似度為:

本文采用的是調整余弦相似度, 并在基本的計算方法上加以改進. 基本的余弦方式在計算相似度的方面有很多的不足和缺陷, 不同用戶會有不同的評分習慣, 因而它們的評分范圍可能存在較大差異, 此方法卻沒有考慮到這點. 調整余弦相似度通過從每個評分中減去該用戶對所有項目評分的平均分值, 從而只考慮評分的偏差值, 這種方法計算的用戶和之間的相似度為:

(2)

2.2 相似度計算的改進算法

2.2.1 用戶-項目類別興趣相似度

用戶-項目類別興趣相似度描述了不同用戶之間的興趣與關注點的相似性. 這一指標可以采用用戶對該項目類別中所有項目的評價次數(shù)之和來表示, 這個值越高, 就表明用戶對這個項目類別中的項目興趣度越高, 它的值是一個有限的整數(shù).

用戶興趣描述的是用戶對某個項目類別的總體感興趣程度. 由上文的分析可知, 單純的通過降低維度的方式不能很好地解決數(shù)據(jù)稀疏性問題, 還需要一種方法與之結合, 彌補其精度上的不足. 建立一個興趣矩陣T用來表現(xiàn)用戶對各個類別的感興趣程度.

其中,代表用戶總數(shù),代表項目類別總數(shù), 元素t代表第個用戶給第個項目類別所包含的所有項目評價次數(shù)的和, 這個值可以用來描述用戶對這個項目類別感興趣的程度.

此外, 為了提高興趣相似度的準確程度, 本文還考慮到了用戶年齡可能產(chǎn)生的影響, 就日常經(jīng)驗來講, 年齡越接近的用戶擁有相同興趣的可能性越大, 而年齡相差越大的用戶之間很可能有著截然不同的興趣與關注點. 就音樂來講, 青年人更喜歡搖滾或流行歌曲, 中年人多喜歡抒情類的歌曲, 而老年人更喜歡年代性歷史性比較強的歌曲. 因此, 除了要考慮到用戶歷史評分次數(shù)之外, 本文加入了年齡調節(jié)項以達到更高的相似精度. 由此可得到用戶、之間的項目類別興趣相似度計算公式如下:

(4)

其中,C是一個集合, 它由用戶、評過分的所有項目類別構成;t代表用戶對項目類別所包含的項目的累計評價次數(shù);t表示用戶對所有項目類別的評價次數(shù)的平均值;u表示用戶的年齡, 另外設置了一個年齡調節(jié)參數(shù)來調節(jié)相似度計算的精度, 最佳的參數(shù)值可以在試驗中進行對比選取和驗證.

2.2.2 用戶-項目類別評分相似度

用戶-項目類別評分相似度通過計算用戶的評分傾向和偏好來確定他們之間的相似程度, 即若用戶對相同項目類別的評分越接近, 就對應有更高的相似度. 考慮到用戶打分習慣與范圍的差別, 將對項目類別的評分用這個用戶對此項目類別中所有項目評分的平均值來表示, 它的取值范圍與評分范圍一致, 通常在區(qū)間[0, 5]中.

所有的商品都帶有自身的屬性, 可以根據(jù)其本身的屬性把它們歸入多個不同的類別中, 這樣, 同一個類別當然也會包含多個不同的商品, 即項目與項目類別是多對多的關系. 因此, 項目類別是一個集合, 其中包含了多個具有某個相同屬性的項目. 項目類別這個概念的應用, 其實是通過聚類的方式降低了用戶-項目評分矩陣的維度, 從而在一定程度上達到了緩解數(shù)據(jù)稀疏性的目的. 用戶與項目類別的關系由用戶-項目類別評分矩陣P來進行描述.

其中,代表用戶總數(shù),代表項目類別總數(shù), 元素p代表第個用戶給第個項目類別中所包含的項目分數(shù)的平均值, 可以用這個值來衡量用戶對此項目類別中包含的所有項目的滿意程度.

同樣地, 為了提高評分相似度的準確程度, 本文還考慮到了用戶評價的項目的一致性. 考慮一個極端的情況, 若兩個用戶對同一項目類別進行過評分, 且分值接近, 但是兩人評價的項目完全不相交, 此時不能說兩人具有較高的相似性. 因此, 除了考慮用戶對項目類別的歷史評分之外, 還加入了調節(jié)項表示用戶評分項目一致性來達到更高的相似度精度.

項目類別評分相似度利用改進后的皮爾森相似度來進行計算, 改進后的用戶-項目類別評分相似度的具體計算如下:

其中,C是一個集合, 它由用戶評過分的所有項目類別構成;r由用戶對項目類別中的所有項目的平均評分;r表示用戶給分的平均值. 調節(jié)項表示在項目類別中, 用戶與用戶共同評價的項目數(shù)與二人評價的項目總數(shù)的比值.

2.2.3 相似度融合

3 實驗結果與分析

3.1 實驗數(shù)據(jù)集

本文的實驗數(shù)據(jù)集采用由明尼蘇達州大學在GroupLens研究項目中收集的MovieLens公用數(shù)據(jù)集[10], 它是一個基于網(wǎng)頁的推薦研究系統(tǒng), 提供了用戶信息表、電影信息表和評分信息表三張表. 這個數(shù)據(jù)集包含了943個獨立的用戶信息. 這些用戶共曾標記過1682部電影, 為數(shù)據(jù)庫中的電影的評分更是超過了10萬. 特別的, 只考慮為20部以上的電影評過分的用戶, 并將數(shù)據(jù)庫分為70%的訓練集和30%的測試集, 然后將數(shù)據(jù)集轉換成一個有943行(用戶)和1682列(用戶中至少有一人評過分的電影)構成的用戶-電影矩陣.

3.2 實驗評價標準

推薦系統(tǒng)研究者們用許多不同的方式評價推薦或者是預測是否成功, 本文采用了一個普遍應用的統(tǒng)計學的準確性度量, 叫做平均絕對誤差(MAE)[11]. 這種方法就是衡量推薦與真實的用戶賦給值的偏差. 對于每一對評分預測數(shù)據(jù)的具體誤差也就是進行處理. 平均絕對誤差的計算方法是先計算N對評分-預測數(shù)據(jù)對的誤差之和, 然后計算平均值, 如下式:

一般來說, 平均絕對誤差越小, 推薦結果越準確, 系統(tǒng)性能就越好.

3.3 確定未知參數(shù)的值

3.3.1 年齡調節(jié)參數(shù)ω的確定

在實驗過程中, 以1: 4的比例隨機地將數(shù)據(jù)集分成兩組不同的測試集和訓練集, 分別用D1、D2表示, 然后分別在D1、D2上進行仿真實驗. 在算法執(zhí)行過程中, 將形成的用戶最近鄰居集的大小(K)分別設為10、20和30, 進行對比試驗. 推薦質量的高低用平均絕對誤差MAE的大小來描述. 得到的實驗結果分別如圖1、圖2.

圖1 數(shù)據(jù)集D1上的實驗結果

圖2 數(shù)據(jù)集D2上的實驗結果

由以上的實驗結果不難發(fā)現(xiàn): 平均絕對誤差值的大小, 也就是推薦系統(tǒng)推薦質量的高低跟用戶的最近鄰居集合大小有關, 鄰居數(shù)量越大, 推薦越精確.

年齡調節(jié)參數(shù)ω的改變也能影響推薦系統(tǒng)的推薦精度. 在ω的值從1變化至20的過程中, MAE的值隨之先減小后增大, 在三個數(shù)據(jù)集上都呈現(xiàn)出相同的變化趨勢, 并且在ω值取8的時候得到最小的MAE值, 也就是說, 當年齡調節(jié)參數(shù)ω的值取8時, 推薦系統(tǒng)能夠達到最高的精度. 綜上所述, 可以將年齡調節(jié)參數(shù)ω的值確定為8.

3.3.2 相似度融合參數(shù)α的確定

在對用戶項目評分相似度和興趣相似度進行融合得到最終相似度的過程中, 參數(shù)α的值是不確定的, 在區(qū)間[0, 1]之間取得, 可以將α作為變量, 分別在數(shù)據(jù)集D1、D2上研究MAE隨著α值變化而變化的趨勢, 從而得到最佳的融合參數(shù)值. 此次將鄰居集數(shù)目(K)分別設置為10、20和30, 進行對比試驗, 實驗結果分別如圖3、圖4.

圖3 數(shù)據(jù)集D1上的實驗結果

圖4 數(shù)據(jù)集D2上的實驗結果

由以上的實驗結果可得: 首先, 平均絕對誤差值得大小跟用戶的最近鄰居集合中鄰居的數(shù)量有關, 鄰居集數(shù)量越大, MAE越小, 推薦越精確.

相似度融合參數(shù)α的改變也能影響推薦系統(tǒng)的推薦精度. 在α的值從0變化至1的過程中, MAE的值隨之先減小后增大, 在三個數(shù)據(jù)集上都呈現(xiàn)出相同的變化趨勢, 并且在α值取0.3的時候得到最小的MAE值, 也就是說, 當參數(shù)α的值取0.3時, 推薦系統(tǒng)能夠達到最高的推薦精度. 由此可以取相似度融合參數(shù)α的值為0.3. 也就是說, 在總的用戶相似度中, 用戶項目類別興趣相似度所占的比重為0.3, 對應的評分相似度所占的比重為0.7.

3.4 算法有效性驗證

在年齡調節(jié)參數(shù)ω的值為8, 相似度融合參數(shù)α的值為0.3的情況下, 將傳統(tǒng)的協(xié)同過濾算法與本文提出的基于數(shù)據(jù)稀疏性的改進協(xié)同過濾算法分別在數(shù)據(jù)集D1、D2上進行仿真實驗, 比較兩種算法性能隨著鄰居集數(shù)量(K)的增大的變化趨勢, 驗證改進算法的有效性. 實驗結果如圖5、圖6.

圖5 數(shù)據(jù)集D1上的實驗結果

圖6 數(shù)據(jù)集D2上的實驗結果

由以上實驗結果不難發(fā)現(xiàn), 推薦系統(tǒng)的推薦質量隨著鄰居集的不斷增大, 推薦質量也不斷提高, 最終趨于一個穩(wěn)定值, 由此結果也可以幫助在應用推薦系統(tǒng)時選擇合適的鄰居集大小. 通過實驗可以看出改進后的協(xié)同過濾算法對推薦系統(tǒng)的推薦質量是有明顯的提升的, 也就是說, 本文提出的基于數(shù)據(jù)稀疏性的協(xié)同過濾算法能夠在一定程度上達到緩解數(shù)據(jù)稀疏性問題的目的.

4 結語

本文重點針對協(xié)同過濾中的數(shù)據(jù)稀疏現(xiàn)象, 引入項目類別的概念, 進行數(shù)據(jù)壓縮, 將傳統(tǒng)的相似度轉化為融合相似度來計算, 有效地緩解了數(shù)據(jù)稀疏性的不利影響. 本文從用戶評分和興趣兩方面分別計算相似性, 引入年齡調節(jié)因子和用戶評分一致性因子兩個調節(jié)項來對用戶相似度進行進一步的修正, 最后選取合適權值進行相似度融合得到最終用戶相似度.

利用MovieLens標準數(shù)據(jù)集進行實驗仿真, 對結果進行比較分析, 從而確定了改進算法中參數(shù)ω和α的取值, 驗證了改進算法的有效性. 本文提出的改進算法在同樣的數(shù)據(jù)環(huán)境中能夠選出相似度更高的用戶, 為用戶提供更加理想的推薦, 提高了推薦質量.

1 劉魯,任曉麗.推薦系統(tǒng)研究進展及展望.信息系統(tǒng)學報, 2008,4(1):82–90.

2 李珊.個性化推薦系統(tǒng)研究綜述.科技致富向導,2014(11): 157–157.

3 鄧曉亮.基于數(shù)據(jù)稀疏性的協(xié)同過濾推薦算法研究[碩士學位論文].重慶:重慶郵電大學,2013.

4 丁卯.基于協(xié)同過濾的推薦系統(tǒng)研究[碩士學位論文].天津:河北工業(yè)大學,2013.

5 Hu JM. Application and research of collaborative filtering in e-commerce recommendation system. International Conference on Computer Science and Information Technology. 2010, 4. 686–689.

6 郭少聃.數(shù)據(jù)稀疏和隱性反饋條件下用戶偏好挖掘方法[碩士學位論文].武漢:華中科技大學,2012.

7 Xia WW, He L, Chen MH, Ren L, Gu JZ. A new collaborative filtering approach utilizing item’s popularity. IEEE International Conference on Industrial Engineering and Engineering Management. 2009. 1480–1484.

8 王駿,王士同,鄧趙紅.聚類分析研究中的若干問題.控制與決策,2012,27(3):321–328.

9 鄧愛林.電子商務推薦系統(tǒng)關鍵技術研究[博士學位論文]. 上海:復旦大學,2003.

10 Zhao K, Lu PY. Improved collaborative filtering approach based on user similarity combination. International Conference on Management Science & Engineering. 2014. 238–243.

11 Zhang L, Qin T, Teng PQ. An improved collaborative filtering algorithm based on user interest. Journal of Software, 2014, 9(4).

Improved Collaborative Filtering Algorithm of Similarity Integration

YU Shi-Cai, XIE Ying-Hua, WANG Qiao

(School of Information Science and Technology, Donghua University, Shanghai 201620, China)

Aiming at the poor recommendation quality due to the data sparsity problem of traditional collaborative filtering recommendation, this paper puts forward an improved collaborative filtering algorithm. The improved algorithm proposes a collaborative filtering algorithm based on the similarity integration of item categories and user interests to make optimization on the similarity calculation. The algorithm does not simply concentrate on similarity calculation, but divides it into two aspects: users-item category interest similarity and users-item category rating similarity, which will finally be integrated with appropriate weights to get the final similarity. After a series of verification and comparison carried out on the MovieLens public data set, it is concluded that the improved algorithm based on data sparsity of collaborative filtering indeed plays a positive role in reducing the influence caused by data sparsity and improves the accuracy of recommendation.

collaborative filtering; data sparsity; item category; user interest; similarity integration

2016-04-20;收到修改稿時間:2016-06-01

[10.15888/j.cnki.csa.005551]