基于協(xié)同過濾技術(shù)推薦系統(tǒng)的探究

江 水

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

1 概 述

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

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

文中闡述了協(xié)同過濾技術(shù)的概念內(nèi)容、數(shù)據(jù)結(jié)構(gòu)、評價標(biāo)準(zhǔn)和分類，著重分析對比了協(xié)同過濾技術(shù)的不同實(shí)現(xiàn)方式及其優(yōu)缺點(diǎn)，為設(shè)計(jì)人員提供指導(dǎo)依據(jù)。

2 協(xié)同過濾算法的基本概念

2.1 協(xié)同過濾的根本假設(shè)

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

2.2 顯式與隱式的數(shù)據(jù)采集

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

2.3 主動過濾和被動過濾

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

2.4 以用戶為中心和以項(xiàng)目為中心

所有的推薦系統(tǒng)需要決定是要分析用戶還是商品之間的特征進(jìn)行預(yù)測。以用戶為中心的系統(tǒng)尋找用戶之間的相似點(diǎn)，然后使用相似用戶的偏好對當(dāng)前用戶的選擇進(jìn)行預(yù)測；以商品為中心的系統(tǒng)尋找商品之間的關(guān)系，然后根據(jù)這些關(guān)系和一個用戶的偏好預(yù)測其可能選擇的其他商品。盡管可以將這兩種方式組合實(shí)現(xiàn)，通常情況下，推薦系統(tǒng)會側(cè)重于其中一種。

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

推薦系統(tǒng)使用的預(yù)測算法也可以分為基于存儲(Memory-based)和模型(Model-based)兩類?；诖鎯Φ乃惴ǔ掷m(xù)使用所有的數(shù)據(jù)信息進(jìn)行預(yù)測；基于模型的算法使用數(shù)據(jù)進(jìn)行學(xué)習(xí)、訓(xùn)練，利用得到的模型進(jìn)行預(yù)測。這意味著基于存儲的算法通常需要將所有的數(shù)據(jù)存儲起來，而基于模型的算法在模型建立之后可以使用少于原始數(shù)據(jù)的量進(jìn)行快速預(yù)測。

2.6 推薦系統(tǒng)評價標(biāo)準(zhǔn)

推薦系統(tǒng)或協(xié)同過濾算法的好壞主要有以下幾點(diǎn)評價標(biāo)準(zhǔn)[1-2,5]：

(1)預(yù)測質(zhì)量：能夠做出較為準(zhǔn)確或者符合實(shí)際用戶需求的預(yù)測或推薦。

(2)預(yù)測速度：推薦系統(tǒng)廣泛應(yīng)用于商業(yè)站點(diǎn)中，其算法需要高效，能夠快速做出預(yù)測。

(3)可擴(kuò)展性：推薦系統(tǒng)的預(yù)測算法不會因?yàn)閿?shù)據(jù)庫規(guī)模的擴(kuò)大而降低預(yù)測質(zhì)量和速度。

(4)可維護(hù)性：在改變排名、評分或者量化標(biāo)準(zhǔn)時，已有算法能夠迅速使用新的機(jī)制進(jìn)行預(yù)測，而不需要花費(fèi)太多的額外人力和時間設(shè)計(jì)新的算法模型。

除此之外，還有一些其他重要的評價指標(biāo)，比如“冷啟動”能力，能夠?qū)π掠脩暨M(jìn)行準(zhǔn)確的預(yù)測、推薦；對稀疏數(shù)據(jù)的處理能力等[4]。

3 數(shù)據(jù)結(jié)構(gòu)

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

3.1 關(guān)系型數(shù)據(jù)庫

存儲數(shù)據(jù)最自然的方式是使用關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，它可以實(shí)現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，保持不同數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系，使得用戶能夠使用結(jié)構(gòu)化的查詢語言訪問各類相關(guān)數(shù)據(jù)。然而，盡管大多數(shù)的數(shù)據(jù)庫系統(tǒng)已經(jīng)高度優(yōu)化，數(shù)據(jù)存儲在硬盤上的組織方式帶來較大的訪存代價。另外，有些數(shù)據(jù)庫比如MySQL，沒有實(shí)現(xiàn)針對大量數(shù)據(jù)的復(fù)雜查詢算法，對于使用比如Netflix的大型推薦系統(tǒng)來說，效率偏低。

3.2 主存讀取(MemReader)

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

圖1 基于主存讀取技術(shù)的Hash表組織結(jié)構(gòu)

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

圖2 基于主存讀取技術(shù)的用戶-電影的Hash表實(shí)現(xiàn)

4 協(xié)同過濾算法分類

4.1 基于存儲的推薦系統(tǒng)

基于存儲的算法使用整個數(shù)據(jù)集合進(jìn)行協(xié)同過濾，首先找到與目標(biāo)用戶相似的其他用戶，使用他們的偏好為目標(biāo)用戶進(jìn)行預(yù)測[5]。

4.1.1 算法描述

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

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

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

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

4.1.2 算法優(yōu)缺點(diǎn)

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

4.2 基于模型的推薦系統(tǒng)

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

4.2.1 算法描述

基于模型的推薦系統(tǒng)[5,7-8]從用戶及其投票情況構(gòu)成的數(shù)據(jù)集中提取特征，得到算法模型，然后使用該模型進(jìn)行預(yù)測推薦，而不需要每次使用整個數(shù)據(jù)集合，在速度和支持大規(guī)模數(shù)據(jù)方面優(yōu)勢明顯?；诖鎯Φ耐扑]系統(tǒng)主要是計(jì)算用戶或者商品之間的相似度，使用其作為權(quán)重來對投票進(jìn)行預(yù)測。與之類似，在基于模型的推薦系統(tǒng)中，用戶或商品之間的相似度關(guān)系以模型的方式進(jìn)行存儲，然后使用模型進(jìn)行預(yù)測推薦。

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

基于模型的推薦系統(tǒng)可以使用剪枝的方法進(jìn)一步支持大規(guī)模數(shù)據(jù)集合?？梢赃x擇k個最相似的實(shí)體進(jìn)行相似度分析和建模，以此進(jìn)行預(yù)測推薦，研究者已經(jīng)發(fā)現(xiàn)，限制相似實(shí)體的數(shù)目對于預(yù)測的準(zhǔn)確性幾乎沒有影響?；谀Ｐ偷耐扑]系統(tǒng)可以通過多種不同的方法來實(shí)現(xiàn)，可以將一個(用戶，商品)對的投票預(yù)測看作是投票數(shù)是某個值的概率，以此將其轉(zhuǎn)化為一個概率問題，Bayesian網(wǎng)絡(luò)和聚類算法通常根據(jù)這個思想。作為示例，文中實(shí)現(xiàn)了基于項(xiàng)目的協(xié)同過濾算法(見5.1節(jié))。推薦系統(tǒng)有時候可以看作是對已有用戶和其對商品的投票構(gòu)成的矩陣，進(jìn)行線性代數(shù)運(yùn)算，使其轉(zhuǎn)化為線性代數(shù)問題，以此實(shí)現(xiàn)推薦。作為示例，文中實(shí)現(xiàn)了奇異值分解算法(見5.3節(jié))。

4.2.2 算法優(yōu)缺點(diǎn)

大多數(shù)使用基于模型算法導(dǎo)出的計(jì)算模型比實(shí)際使用整個數(shù)據(jù)集合要小，因此，對于較大的數(shù)據(jù)集，模型可以變得足夠小以提高預(yù)測效率，具有較好的可擴(kuò)展性；與基于存儲的推薦系統(tǒng)相比，基于模型的系統(tǒng)通常具有更快的預(yù)測速度，這主要是因?yàn)樵儐柲Ｐ偷臅r間一般情況下要遠(yuǎn)遠(yuǎn)短于詢問整個數(shù)據(jù)集合的時間；如果建立的模型已經(jīng)能夠準(zhǔn)確概括真實(shí)情況下投票情況，使用該模型就能夠避免過度預(yù)測的情況。

然而，由于建立模型的過程通常會消耗大量的時間和資源，使得難以實(shí)時增加新的數(shù)據(jù)集到系統(tǒng)中，導(dǎo)致該算法靈活性變差。由于不使用整個數(shù)據(jù)集合而是選用部分?jǐn)?shù)據(jù)進(jìn)行預(yù)測，這可能會導(dǎo)致預(yù)測準(zhǔn)確度的降低。然而，預(yù)測質(zhì)量主要依賴于模型的構(gòu)建方式，事實(shí)上，一個基于模型的推薦系統(tǒng)通常能夠獲得較好的預(yù)測表現(xiàn)。

4.3 關(guān)聯(lián)規(guī)則

4.3.1 算法實(shí)現(xiàn)

關(guān)聯(lián)規(guī)則嘗試關(guān)聯(lián)項(xiàng)目之間的因果關(guān)系[9-10]。關(guān)聯(lián)規(guī)則的形式為A1,A2,A3…?B1,B2,B3…，表示根據(jù)項(xiàng)目A1,A2,A3…可以推出B1,B2,B3…等；如果有A?B,C，表示A的成立蘊(yùn)含B和C的成立?？尚哦仁敲枋鲆?guī)則的大小在0和1之間的另一個因子。如果可信度為1，表示該關(guān)聯(lián)規(guī)則永遠(yuǎn)適用；如果可信度為0，就表示該關(guān)聯(lián)規(guī)則永遠(yuǎn)不會成立。

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

與其他方法相比，關(guān)聯(lián)規(guī)則主要對矩陣進(jìn)行操作，執(zhí)行效率高，預(yù)測結(jié)果準(zhǔn)確，使用多級關(guān)聯(lián)規(guī)則能夠適用稀疏的數(shù)據(jù)集。缺點(diǎn)是無法預(yù)測評分，只能反映偏好，如果需要具體的預(yù)測評分值，則需要使用其他的算法。

5 協(xié)同過濾算法的實(shí)現(xiàn)方式

5.1 基于項(xiàng)目的協(xié)同過濾算法

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

5.1.1 算法描述

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

圖3 基于項(xiàng)目的協(xié)同過濾示例

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

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

(1)

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

(2)

(3)

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

(4)

5.1.2 算法優(yōu)缺點(diǎn)

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

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

第二個挑戰(zhàn)就是當(dāng)使用加權(quán)和來為用戶-電影對計(jì)算評分值。因?yàn)閷γ總€電影只存儲50個相似的電影，并且對于每個目標(biāo)電影，只考慮當(dāng)前用戶已經(jīng)看過的相似的電影。這就使得在大多數(shù)的情況下，對于Movielens的數(shù)據(jù)庫，對于大多數(shù)的用戶，并沒有太多符合這些條件的電影。因此對于較大的測試集，具有較差的預(yù)測能力。這是由數(shù)據(jù)集稀疏性導(dǎo)致的。

5.2 個性診斷模型

5.2.1 基本算法

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

i|Ra,Ri)

(5)

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

(6)

5.2.2 算法優(yōu)化

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

5.3 維度縮減和奇異值分解

5.3.1 維度縮減(Dimensionality Reduction)

表1 個性診斷方法不同實(shí)現(xiàn)方式的比較

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

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

5.3.2 奇異值分解(Singular Value Decomposition)

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

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

(7)

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

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

6 不同算法實(shí)現(xiàn)與性能比較

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

實(shí)驗(yàn)結(jié)果如圖4所示。

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

圖4 基于Movielens庫實(shí)現(xiàn)的協(xié)同過濾算法的比較

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

圖5 基于成績單庫實(shí)現(xiàn)的協(xié)同過濾算法的比較

7 結(jié)束語

推薦系統(tǒng)能夠根據(jù)用戶的興趣和行為特征，為其推薦感興趣的項(xiàng)目，已經(jīng)廣泛應(yīng)用于互聯(lián)網(wǎng)和大數(shù)據(jù)系統(tǒng)。協(xié)同過濾技術(shù)綜合考慮用戶的歷史特征和用戶之間的相似關(guān)系，為用戶進(jìn)行預(yù)測推薦。文中闡述了協(xié)同過濾技術(shù)的概念內(nèi)容、數(shù)據(jù)結(jié)構(gòu)、評價標(biāo)準(zhǔn)和分類，包括基于存儲、基于模型和關(guān)聯(lián)規(guī)則的推薦系統(tǒng)，對基于項(xiàng)目的協(xié)同過濾、個性診斷以及維數(shù)縮減和奇異值分解等技術(shù)實(shí)現(xiàn)進(jìn)行了詳細(xì)的描述、對比，并通過實(shí)驗(yàn)進(jìn)行介紹，分析優(yōu)缺點(diǎn)，為設(shè)計(jì)人員提供依據(jù)。