基于協同過濾技術推薦系統的探究

江 水

(中國電子科技集團公司第三十二研究所，上海 201808)

1 概 述

網上商城通常對產品進行分類，并提供符合用戶需求的產品選項供用戶點選查看，然而，用戶瀏覽產品的隨機性很大，他們可能會選擇很多屬于不同類別或風格的產品，使得網上商城無論提供多少預設選項都無法滿足用戶的需求。因此，商業站點普遍通過展示特價產品、新到產品或者商家推薦產品去試圖彌補這方面的不足。在眾多的營銷手段中，從最暢銷產品和用戶關注產品的角度進行推薦往往最有效。作為其中的一種吸引人的技術實現方法，基于數據挖掘技術的推薦系統(Recommender Systems)已經廣泛應用于各類網上商城，包括其他行業需要向用戶推薦、推銷產品的在線系統中[1]。

推薦系統主要依據用戶自身的特征和過往消費情況向其推薦產品。有些推薦系統還會結合使用與產品信息相關的問題進行推薦，有些則僅僅依賴于用戶自身的特征與相似用戶的總體特征，后者一般被稱為“協同過濾”(Collaborative Filtering)系統[2-5]，不要求用戶在搜索的過程中顯示輸入過濾條件，而是通過分析當前用戶的過往消費或瀏覽行為和與其相似的用戶的總體特征來給出推薦意見。現有的推薦系統算法大致可以分為基于存儲(Memory-based)的推薦算法、基于模型(Model-based)的推薦算法和關聯規則(Association Rules)算法[1-2,5]。其中，基于模型的推薦算法又包括基于項目(Item-based)的協同過濾算法、個性診斷(Personality Diagnosis)和奇異值分解(Singular Value Decomposition，SVD)等。

文中闡述了協同過濾技術的概念內容、數據結構、評價標準和分類，著重分析對比了協同過濾技術的不同實現方式及其優缺點，為設計人員提供指導依據。

2 協同過濾算法的基本概念

2.1 協同過濾的根本假設

協同過濾技術綜合考慮用戶的歷史特征和用戶之間的相似關系，為用戶進行預測推薦[2,5]，其基本假設是：在過去有相似偏好的用戶，在未來也極有可能有相似的偏好。基于這個假設，可以根據用戶的歷史信息來預測將來該用戶可能感興趣的商品。需要注意的是，該假設并不是在任何時候都成立但對于推薦系統是足夠的，在最差情況下，與盲目的猜測相比，應用協同過濾算法設計的推薦系統能夠給出較優的結果。

2.2 顯式與隱式的數據采集

為了得到用戶的歷史偏好信息，需要進行數據采集。數據采集的過程可以分成兩種，一種是顯式的采集方式：要求用戶在現有評分體系下明確對某一對象進行打分(比如對一首流行歌曲從一顆星到五顆星的評分)；另一種是通過記錄用戶在站點上的點擊、瀏覽和停留時間長短等行為，隱式地進行數據采集。通過顯示方法采集到的數據，用戶給出的等級排名或者評分信息，能夠被直接翻譯為用戶的偏好信息，使系統容易推斷用戶將來的選擇或喜好，但是其過于依賴用戶操作，在實際情況下，用戶也許并不想去花費時間進行評分，導致采集到的數據不全或者不具有代表性。相比之下，隱式的數據采集不需要用戶的干預，依托相應的算法，系統能夠容易獲得大量用戶操作信息，然而系統無法像使用顯式的評分信息那樣，直接利用這些隱式信息進行預測推薦，需要使用精確的算法將用戶行為轉換成其偏好。由于難以辨別用戶的行為能多大程度上反映用戶的實際偏好，使得使用隱式信息進行預測和推薦的難度加大。當然，這兩種數據采集方法不是互斥的，通過融合能夠得到優化的整體結果，其中一個可行的方案是，對于用戶明確給出評級或者評分的情況，系統使用其進行預測；對于評分缺失的情況，系統抽取隱式的用戶行為進行推薦預測。

2.3 主動過濾和被動過濾

數據采集完成后需要使用協同過濾方法進行預測，協同過濾方法大致可分為被動和主動兩種方式:被動過濾僅使用數據的聚合(Data Aggregate)關系進行預測(比如某一商品的平均投票)；更加先進的方式是使用用戶歷史特征進行預測的主動過濾，比如使用與當前用戶相似的用戶的歷史信息對當前用戶進行預測。兩種方法的根本區別在于，推薦系統是否針對特定的用戶：對于被動過濾系統中的某一個商品，每位用戶會得到相同的預測結果，系統沒有針對特定的用戶；而對于主動過濾，系統需要考慮每位用戶的不同歷史特征進行推薦，Amazon.com就是其中之一。盡管被動過濾對于很多的應用來說也非常有用，對于以向用戶推薦、推銷商品為目的的大多數網上商城來說，往往只能使用主動過濾的方法，大家通常說的協同過濾，指的也都是主動過濾。

2.4 以用戶為中心和以項目為中心

所有的推薦系統需要決定是要分析用戶還是商品之間的特征進行預測。以用戶為中心的系統尋找用戶之間的相似點，然后使用相似用戶的偏好對當前用戶的選擇進行預測；以商品為中心的系統尋找商品之間的關系，然后根據這些關系和一個用戶的偏好預測其可能選擇的其他商品。盡管可以將這兩種方式組合實現，通常情況下，推薦系統會側重于其中一種。

2.5 基于存儲和基于模型的算法

推薦系統使用的預測算法也可以分為基于存儲(Memory-based)和模型(Model-based)兩類。基于存儲的算法持續使用所有的數據信息進行預測；基于模型的算法使用數據進行學習、訓練，利用得到的模型進行預測。這意味著基于存儲的算法通常需要將所有的數據存儲起來，而基于模型的算法在模型建立之后可以使用少于原始數據的量進行快速預測。

2.6 推薦系統評價標準

推薦系統或協同過濾算法的好壞主要有以下幾點評價標準[1-2,5]：

(1)預測質量：能夠做出較為準確或者符合實際用戶需求的預測或推薦。

(2)預測速度：推薦系統廣泛應用于商業站點中，其算法需要高效，能夠快速做出預測。

(3)可擴展性：推薦系統的預測算法不會因為數據庫規模的擴大而降低預測質量和速度。

(4)可維護性：在改變排名、評分或者量化標準時，已有算法能夠迅速使用新的機制進行預測，而不需要花費太多的額外人力和時間設計新的算法模型。

除此之外，還有一些其他重要的評價指標，比如“冷啟動”能力，能夠對新用戶進行準確的預測、推薦；對稀疏數據的處理能力等[4]。

3 數據結構

在開發推薦系統的早期，需要選擇使用何種數據結構對龐大的數據集合進行存儲和管理，保證能夠簡單、高效地對數據集進行訪問和管理。這個問題在測試Netflix的數據時變得更加明顯，它擁有超過10億次的投票數量，使得速度和存儲效率成為非常重要的系統評價指標。常見的兩種數據存儲技術包括：關系型數據庫和基于Hash表的主存讀取。

3.1 關系型數據庫

存儲數據最自然的方式是使用關系型數據庫管理系統，它可以實現復雜的數據結構，保持不同數據之間的關聯關系，使得用戶能夠使用結構化的查詢語言訪問各類相關數據。然而，盡管大多數的數據庫系統已經高度優化，數據存儲在硬盤上的組織方式帶來較大的訪存代價。另外，有些數據庫比如MySQL，沒有實現針對大量數據的復雜查詢算法，對于使用比如Netflix的大型推薦系統來說，效率偏低。

3.2 主存讀取(MemReader)

使用數據庫效率低的主要原因是它需要頻繁訪問磁盤，因此，通過將所有必要的數據存儲在主存中可以解決這個問題。盡管Netflix的數據集非常龐大，使用主存讀取(MemReader)技術進行仔細的處理，能夠將整個數據集限制在2 GByte內并存儲于主存中，實現數據的高效訪問[6]。如圖1所示，為了實現數據的快速訪問，將每項排名信息(Rating)存儲于兩個Hash表中，分別使用uid和mid進行索引，注意，因為性能的原因，首先為每個電影和用戶計算平均評分。這種情況下，uid和mid都只需要不超過24 bits的位數來存儲。在Java系統中，整型(int)數字使用32位來表示，于是將uid或者mid存儲于32位的高24位，然后將排名投票信息存儲于剩余的低8位。所有的操作都可以轉換成位運算，由于位運算執行效率高，這項技術能夠降低主存的使用而不會減慢訪問速度。

圖1 基于主存讀取技術的Hash表組織結構

圖2描繪了一個用戶-電影的Hash表實現方式[6]。保存了一個哈希表，其中包含了被每個用戶打過分的電影數目和所有評分的加和(類似的，還有每個電影的被評分的次數和總分)，這使得一個MemReader項目具有高效的計算效率，并且能夠高效地添加用戶。主存讀取技術在應對Netflix類似的大型數據集時非常高效。

圖2 基于主存讀取技術的用戶-電影的Hash表實現

4 協同過濾算法分類

4.1 基于存儲的推薦系統

基于存儲的算法使用整個數據集合進行協同過濾，首先找到與目標用戶相似的其他用戶，使用他們的偏好為目標用戶進行預測[5]。

4.1.1 算法描述

首先需要定義相似度的測量方法，以此確定用戶之間的關聯程度，相似度可以使用[-1，1]之間的值進行描述，1表示兩者的偏好完全相同，-1表示偏好完全相反。

有兩種方法進行相似度測量，一種是使用在樣本相關性評估中廣泛應用的皮爾遜相關系數(Pearson Correlation Coefficient)，它通過分析用戶各自的整體投票變化趨勢評估其相關性，也就是說，以用戶各自的平均投票情況為基準，分析每個商品的得票情況：對于兩個用戶共同評價過的商品，如果投票趨勢變化大致相同，兩個用戶正相關；否則，兩個用戶負相關。另一種方法稱為向量相似度，可以將兩個用戶對所有商品的投票情況看作是n維空間中的兩個向量，n是商品的數量，因此，可以計算兩個向量的夾角，直觀來說，如果兩個向量基本的方向大致相同，它們是正相關的，如果指向相反，則負相關。通過對兩個向量的夾角取余弦值，可以得到[-1，1]區間的值，以此對相似度進行量化。

為了預測當前用戶對某個商品的評分，需要根據之前計算的用戶相似度，得到其他所有用戶對某一商品的打分情況相對于當前用戶對該物品打分情況的權重關系，然后，根據已知的其他用戶對該商品的投票情況和每個用戶所占的權重，完成對當前用戶對當前商品投票情況的預測。由此也可看出，權重高的用戶對當前用戶影響較大，這種影響可以是正影響或者負影響。

以上描述的算法在實際情況中，仍需做出一定的改進。比如說，(1)在數據集相對稀疏的情況下，使用相關系數進行相似度測量會不準確，也就是說，當兩個用戶幾乎沒有共同評價過的商品的時候，他們之前的權重關系就無法表示實際的情況，相反卻能過度影響整體的投票結果，通過使用默認投票虛構一些他們共同評價過的商品能夠使投票結果更加平滑；(2)憑借直覺可以發現，那些被公眾都喜歡的物品，相對于不常見的物品來說，對于權重的影響較小。比如，如果大家每個人都喜歡看星際迷航的電影，據此得到的相似度無法用來決定兩個人喜歡一個不常見電影的相對權值。因此，可以使用翻轉投票率的方法解決這個問題；(3)還可以通過按照指數增加或者減小權重，增加權重的差別，這種方法有時會對推薦結果產生微小的改進。

4.1.2 算法優缺點

基于存儲的算法預測質量相對較好，實現算法相對簡單，由于它每次均使用整個數據集合進行預測，使得數據庫每次更新后，預測也會發生相應變化，提高預測的準確度。然而，由于需要將所有的數據存儲在主存中，大量的訪存操作限制了預測速度；在數據集稀疏的情況下，其預測表現欠佳；由于該方法使用用戶對商品的所有投票進行分析，包含所有潛在的隨機變量，而不對數據進行外加的概括處理，可能會造成數據過度擬合或過度預測，造成預測結果不準確。

4.2 基于模型的推薦系統

基于存儲的推薦系統在面對超大數據集合時，往往受限于預測速度和存儲容量的瓶頸。因此，使用基于模型的推薦系統便應運而生。

4.2.1 算法描述

基于模型的推薦系統[5,7-8]從用戶及其投票情況構成的數據集中提取特征，得到算法模型，然后使用該模型進行預測推薦，而不需要每次使用整個數據集合，在速度和支持大規模數據方面優勢明顯。基于存儲的推薦系統主要是計算用戶或者商品之間的相似度，使用其作為權重來對投票進行預測。與之類似，在基于模型的推薦系統中，用戶或商品之間的相似度關系以模型的方式進行存儲，然后使用模型進行預測推薦。

觀察組和對照組總有效率依次為96.97%和72.73%，觀察組明顯高于對照組（P＜0.05），見表 2。

基于模型的推薦系統可以使用剪枝的方法進一步支持大規模數據集合。可以選擇k個最相似的實體進行相似度分析和建模，以此進行預測推薦，研究者已經發現，限制相似實體的數目對于預測的準確性幾乎沒有影響。基于模型的推薦系統可以通過多種不同的方法來實現，可以將一個(用戶，商品)對的投票預測看作是投票數是某個值的概率，以此將其轉化為一個概率問題，Bayesian網絡和聚類算法通常根據這個思想。作為示例，文中實現了基于項目的協同過濾算法(見5.1節)。推薦系統有時候可以看作是對已有用戶和其對商品的投票構成的矩陣，進行線性代數運算，使其轉化為線性代數問題，以此實現推薦。作為示例，文中實現了奇異值分解算法(見5.3節)。

4.2.2 算法優缺點

大多數使用基于模型算法導出的計算模型比實際使用整個數據集合要小，因此，對于較大的數據集，模型可以變得足夠小以提高預測效率，具有較好的可擴展性；與基于存儲的推薦系統相比，基于模型的系統通常具有更快的預測速度，這主要是因為詢問模型的時間一般情況下要遠遠短于詢問整個數據集合的時間；如果建立的模型已經能夠準確概括真實情況下投票情況，使用該模型就能夠避免過度預測的情況。

然而，由于建立模型的過程通常會消耗大量的時間和資源，使得難以實時增加新的數據集到系統中，導致該算法靈活性變差。由于不使用整個數據集合而是選用部分數據進行預測，這可能會導致預測準確度的降低。然而，預測質量主要依賴于模型的構建方式，事實上，一個基于模型的推薦系統通常能夠獲得較好的預測表現。

4.3 關聯規則

4.3.1 算法實現

關聯規則嘗試關聯項目之間的因果關系[9-10]。關聯規則的形式為A1,A2,A3…?B1,B2,B3…，表示根據項目A1,A2,A3…可以推出B1,B2,B3…等；如果有A?B,C，表示A的成立蘊含B和C的成立。可信度是描述規則的大小在0和1之間的另一個因子。如果可信度為1，表示該關聯規則永遠適用；如果可信度為0，就表示該關聯規則永遠不會成立。

對于一個包含n個項目的數據庫，需要建立基于單項目關系的關聯可信度矩陣，單項目關系是指滿足A?B形式的關聯規則，這意味著需要查看所有的單項目關系，即對于評價了項目B的當前用戶，其評價項目A的可能性。然后使用n維空間的一個向量表示每一個用戶。將表示一個用戶的n維向量與關聯可信度矩陣相乘，就可以得到其推薦向量，即給定當前用戶的歷史評價信息，得到其將來最可能評價的項目。該推薦向量也可以被用來獲得用戶的偏好。

與其他方法相比，關聯規則主要對矩陣進行操作，執行效率高，預測結果準確，使用多級關聯規則能夠適用稀疏的數據集。缺點是無法預測評分，只能反映偏好，如果需要具體的預測評分值，則需要使用其他的算法。

5 協同過濾算法的實現方式

5.1 基于項目的協同過濾算法

基于項目的協同過濾是一種基于模型的算法[7]，數據集中不同項目的相似度通過使用某種測量的方法來獲得，然后使用這些相似值對用戶對商品的評分進行預測。

5.1.1 算法描述

通過觀測所有對兩個物品都打過分的用戶信息可以分析得出兩個項目之間的相似度，如圖3所示，兩個項目i和j的相似度依賴于對兩個項目都打過分的用戶(1，u和m)的評分。

圖3 基于項目的協同過濾示例

下面列舉幾類典型的計算兩個項目(i和j)相似度(sim(i,j))的數學方法[1-2,5]，也稱之為向量相似性算法(U表示對兩個項目都評價過的所有用戶集合)。

?余弦相似性(Cosine-based Similarity)，也稱之為基于向量的相似度(Vector-based Similarity)，將兩個項目i和j的所有評分分別記作兩個向量，其相似度可以使用向量的夾角余弦值來表示，見公式(1)。

(1)

?皮爾森相關相似性(Pearson Correlation-based Similarity)，基于所有共同用戶對兩個項目的評分相對于其平均得分的偏離程度來衡量，見公式(2)。

(2)

(3)

完成相似度建模之后，可以使用加權和(Weighted Sum)的方法為所有的(用戶，項目)對的評分進行預測，見公式(4)。首先，可以選取所有類似于目標項目，且當前用戶已經打過分的項目；然后對用戶的評分情況設置權值；最后，通過累加相似度，并按比例調整，就能夠得到一個合理的預測評分值(Pu,i)。

(4)

5.1.2 算法優缺點

使用Movielens數據庫對該方法進行測試(見第6節)，但測試結果并不理想，其中的原因主要是由于數據的稀疏性導致的[7-8]。

第一個問題發生在調整的余弦相似度計算中，當某部電影只有一個觀眾打分的情況。由于需要將觀眾對電影的平分減去用戶評分的平均值，對用戶減去了平均值，對于一個物品，在有一個共同的用戶情況下，其調整的余弦相似度為1，表示最高的可能性，使得最相似的物品實際上成為那些擁有一個共同用戶的。解決這個問題的方法是，可以規定兩個電影之間共同的用戶數目必須不小于一個特定的值。

第二個挑戰就是當使用加權和來為用戶-電影對計算評分值。因為對每個電影只存儲50個相似的電影，并且對于每個目標電影，只考慮當前用戶已經看過的相似的電影。這就使得在大多數的情況下，對于Movielens的數據庫，對于大多數的用戶，并沒有太多符合這些條件的電影。因此對于較大的測試集，具有較差的預測能力。這是由數據集稀疏性導致的。

5.2 個性診斷模型

5.2.1 基本算法

個性診斷(Personality diagnosis，PD)是一個基于概率的，模型和存儲混合算法[11]，它假設用戶具有“真實個性(True Personality)”的隱藏屬性，能夠被用來進行準確預測。對于數據庫中的每個用戶a，給定其評分向量(Ra)，根據評分向量的相似度計算當前用戶(a)是某一個用戶(i)的概率，即當前用戶的真實個性與其他用戶個性的相似度。另一方面，在其他用戶已經對某一物品(j)評過分的基礎上，當前用戶(a)也可能對該物品(j)進行評分，將這個概率與前面的概率相乘。然后針對所有的用戶，將所有的概率乘積進行累加，擁有最高概率的打分是預測的當前用戶對某個物品的打分，如公式(5)所示：

i|Ra,Ri)

(5)

其中，h是一個可能的評分，n是用戶的數目，ra(j)是當前的用戶a對項目j的評分。在實驗中，該公式可以轉換為公式(6)，其中，兩個用戶共同評價過的電影使用l到m進行編號，參數σ的值根據實際數據集進行選擇(實驗中其值為2)。

(6)

5.2.2 算法優化

上面的方法需要循環訪問所有其他用戶的信息來為當前用戶進行預測，具有基于存儲的協同過濾算法的性能缺點。因此，可以根據基于模型的算法，選擇只迭代其他一部分用戶，比如選取50個最相似的用戶，并使用調整的余弦相似度測量方法。如表1所示，與基于存儲算法實現的PD相比，基于模型的算法具有明顯的加速，而幾乎沒有丟失精度[6]。

5.3 維度縮減和奇異值分解

5.3.1 維度縮減(Dimensionality Reduction)

表1 個性診斷方法不同實現方式的比較

可以使用特征空間對數據庫進行表示，每一個特征向量可以表示一個項目，每一個向量點表示一個用戶對項目的評分。該方法可以擴展到任意數目的維度。這里需要解決維度過高的問題，進行維度縮減[12]。例如，如果每個喜歡物品A的用戶也都喜歡B，就可以將A和B歸為一組，形成特征集。然后通過查看兩個用戶對每個特征集而不是每個物品的打分，來比較這兩個用戶。

如果有一個具有30 000部電影的數據庫，每個用戶就是一個長度為30 000的向量，其存儲和比較操作速度相對較慢，且消耗大量內存。使用較小的維度不僅可以提高預測效率，還可以提高預測的準確度。比如說，假設有兩個用戶都喜歡科幻電影，如果一個用戶對《Star Wars》評價較高，而另一個用戶對《Empire Strikes Back》評價較高，這兩部電影同屬于一個電影集，據此可以推斷，這兩個用戶非常相似。相比而言，如果基于單個電影對兩個用戶進行比較，由于其喜歡的電影不同，使得他們并不是那么相似，而只有那些共同評價過的電影才會影響到他們的相似度，影響預測的準確性。

5.3.2 奇異值分解(Singular Value Decomposition)

基于信息檢索的背景，Deerwester等人曾經對維度縮減的問題進行了檢驗[13]。通常情況下，文檔的比較是通過對詞組的內容進行比較實現的，Deerwester提出創建能夠代表多個詞組的特征集，然后對其特征進行比較，他們使用了奇異值分解的數學方法。之后，Sarwar等人將這一方法應用到推薦系統中[14]。

奇異值分解[15]是將一個m×n的矩陣X分解成三個矩陣U、S和V，其中S是對角矩陣，包含矩陣X的r個奇異值，線性無關的概念正好可以用在之前的例子中，如果每個喜歡《Star Wars》的用戶都喜歡《The Matrix》，這兩個電影向量就會線性相關。

(7)

如果大多數喜歡電影A的用戶也喜歡B，為了比較A和B，可以簡單地在矩陣S中，保持前k個奇異值(k

在實際應用中，使用基于SVD的推薦系統進行預測評分，第一步將數據集表示為矩陣，其中用戶為行，項目為列，矩陣中每一個值為評分值。為了提供一個基準，對于原來的空值，使用電影的平均得分替代，然后進行奇異值的分解[13-14]。

6 不同算法實現與性能比較

針對Movielens數據庫(10萬數據項)，使用Python語言對向量相似性算法(Vec. Sim.)、個性診斷算法(PD)、奇異值分解算法(SVD)和關聯算法(Corr.)進行了實現，并與求全局平均值方法(Avg.)得到的預測結果進行比較，通過計算相對用戶實際打分的均方根誤差(Root Mean Squared Error，RMSE)對預測結果的準確性進行評估。

實驗結果如圖4所示。

可以看出，關聯算法的RMSE值最低，表示其對于小的稀疏數據集預測效果最好，向量個性診斷由于不適合小的稀疏數據集，預測結果最差。當將算法應用于較大的Netflix數據集時，奇異值分解算法的預測效果最好(RMSE=0.92)，優于向量相似度算法(RMSE=0.99)。

圖4 基于Movielens庫實現的協同過濾算法的比較

同時使用擁有13萬數據項的稀疏成績單數據庫對幾種典型的算法進行了測試，如圖5所示，稀疏數據是通過分別移除1門、5門、10門課程的成績實現的。通過比較可以發現，向量相似性算法與關聯算法取得了較好的性能，相比之下，隨著數據稀疏性的不斷增加，平均算法的表現不斷下滑。

圖5 基于成績單庫實現的協同過濾算法的比較

7 結束語

推薦系統能夠根據用戶的興趣和行為特征，為其推薦感興趣的項目，已經廣泛應用于互聯網和大數據系統。協同過濾技術綜合考慮用戶的歷史特征和用戶之間的相似關系，為用戶進行預測推薦。文中闡述了協同過濾技術的概念內容、數據結構、評價標準和分類，包括基于存儲、基于模型和關聯規則的推薦系統，對基于項目的協同過濾、個性診斷以及維數縮減和奇異值分解等技術實現進行了詳細的描述、對比，并通過實驗進行介紹，分析優缺點，為設計人員提供依據。