王志遠 王興芬
1(北京信息科技大學計算機學院 北京 100101)2(北京信息科技大學信息管理學院 北京 100192)
當今大數據時代面臨的主要問題之一是如何從龐大的數據海洋中尋找到用戶需要的信息,即信息過載問題。個性化推薦技術逐漸興起,相比于信息系統、搜索引擎等技術,個性化推薦技術有著精準定位、因人而異的優點,它往往不需要用戶搜索式地輸入信息,而是通過用戶的歷史行為記錄或歷史評價信息為用戶提供個性化的信息推送和智能決策。個性化推薦技術在很大程度上能解決傳統搜索中的信息冗余問題,盡可能地避免用戶瀏覽大量的無關信息和不感興趣的信息,極大地提升了用戶的體驗。以往推薦算法的功能是在當數據中沒有滿足用戶需求的信息時,向用戶推薦盡可能接近用戶需求的信息。而目前推薦算法需要解決的問題是,當數據中有大量符合用戶需求的信息時,根據用戶的歷史數據推測出用戶的潛在需求,然后根據用戶的潛在需求進一步從數據庫中篩選出用戶可能需要的信息,排序后推薦給用戶。這種潛在的需求可能是用戶自身都沒有察覺到的個人偏好,但它是真實存在的,就蘊藏在數據之中。
推薦技術的出現和不斷成熟使得這些網絡平臺的內容提供商的個性化服務功能不斷完善,用戶的實際體驗也逐步攀升,甚至對推薦系統產生依賴性,增加了用戶的黏性,帶來了巨大的經濟價值。而對于廣大的用戶來說,一個高度智能的推薦系統不僅節約了大量寶貴的時間,快捷高效地獲得想要的信息數據,而且極大地降低了尋找感興趣的信息的難度。因此無論是對信息服務的提供商還是對于廣大的普通用戶,推薦技術的應用都有著其獨特的重要意義。
協同過濾算法是個性化推薦中使用最為廣泛的方法,然而在用戶和項目的數量十分龐大但是用戶只在很少的項目上有評分記錄時就會導致數據稀疏性問題。在協同過濾算法中,數據稀疏會使得用戶之間計算相似度時可以用來進行計算的數據過少,導致求得的用戶相似度不準確,最終影響預測評分的準確度。
針對協同過濾中存在的數據稀疏性問題,國內外學者進行了大量的研究。在融合多源數據方面,王建芳等[1]針對用戶交叉評分項較少的情況,提出一種相似度與社交網絡中信任因子結合的協同過濾算法,在對評分矩陣填充時存在誤差的項目通過信任因子動態調整,獲得更符合實際的相似度;萬惠等[2]根據社區劃分的思想,采用凝聚式層次聚類算法對電影類別劃分為不同的社區,在目標用戶所屬的社區里通過用戶的標簽和評分數據計算用戶間的相似度,進而對目標用戶進行推薦,提高了推薦的效果;肖成龍等[3]融合社交網絡和關鍵用戶信息,在用戶-項目矩陣的基礎上得到了社交信任矩陣和關鍵用戶評分矩陣,然后分別賦予這三個矩陣不同的權重,協同計算出用戶對目標項目的預測評分,有效地緩解了數據的稀疏性問題。在矩陣分解方面,李曉菊等[4]提出了一種基于變分循環自動編碼器的概率矩陣分解方法,將商品的描述文本編碼成一個特征向量,然后將該特征向量融合到概率矩陣分解模型中,在評分矩陣極其稀疏的情況下,能更有效地預測用戶感興趣的商品列表,提高推薦準確性;畢閏芳[5]提出了一種基于SVR的矩陣填充模型,首先通過對原始的用戶評分矩陣中的空缺值使用預測值填充,然后采用協同過濾算法形成初步的推薦列表,最后借助用戶興趣偏好畫像對推薦列表進行二次篩選;羅國前等[6]通過融入情境偏置和全局偏置在矩陣分解算法的基礎上對目標項目預測評分,一方面使得矩陣規模大大下降,另一方面通過情境因素對預測評分的修正,提高預測的準確度;蔡念等[7]通過加入用戶和項目的影響因子改進傳統的矩陣分解模型,同時與跨通道卷積神經網絡結合,提高了預測模型的準確度。在融合多模型方面,于歡[8]采用多模型融合的算法深層次提取了用戶的偏好,同時重點關注用戶的近期偏好,使得模型在推薦結果的準確度和驚喜度上更加靈活,為不同用戶提供的推薦更個性化,有助于進一步提升用戶的真實體驗;胡芳燚[9]全面分析了用戶評分所造成的全局影響,并且利用物品相似度與用戶之間的映射關系提高了用戶間相似度計算的準確性,同時根據用戶評分時間通過引入艾賓浩斯遺忘曲線調整評分數據的權重,挖掘用戶的興趣變化規律,分析群體性行為對用戶興趣偏好的影響;湯穎等[10]針對傳統的推薦算法難以捕捉用戶興趣偏好的問題,設計了一種基于用戶局部模型加權融合的算法,該算法借助LDA主題模型于語義層次計算用戶的特征向量實現用戶聚類,進而提高了電影的個性化推薦效果。
以上改進研究在一定程度上提高了推薦的效果,但沒有充分挖掘分析在實際應用場景中用戶屬性和項目內容相較于其他領域的特殊性及其對推薦結果的影響。本文聚焦于電影推薦領域,針對協同過濾算法只考慮用戶評分而忽略用戶屬性和項目內容的缺點,研究不同用戶的興趣差異,在對用戶未評分項目進行預測時,著重分析了用戶興趣差異和項目屬性對預測結果的影響。經過在電影評分數據集上的實驗驗證,本文算法在數據稀疏的情況下仍能保持預測評分的準確度,有效地提升了算法的推薦性能。具體的算法模型如圖1所示。

圖1 改進矩陣填充的推薦算法模型
把不同用戶對商品的評分數據轉化為用戶-商品矩陣,每一行為一個用戶,每一列為一個商品,矩陣的每一個取值為該行對應用戶對該列對應商品的評分,若無對應評分則為空值。但是因為商品數量眾多,對于每個用戶來講,他所評價過的商品只占所有商品很小的一部分,所以生成的用戶-商品矩陣是極度稀疏的。KNN算法的假設是:喜歡相似物品的用戶具有相似性,在商品推薦中即為對商品有相近評分的用戶具有相似性,有相近評分的商品越多兩位用戶的相似度越高。所以通過KNN算法計算得到的相似的用戶往往在兩者的商品評分列表中需要有足夠的交集。這就導致有許多相似用戶因為相交部分過少甚至沒有相交部分而被忽略,但是這種情況會隨著用戶有評分的商品的數量的增加而減少。因此本文對用戶-商品矩陣進行填充,降低用戶-商品矩陣的稀疏程度,推高商品推薦的準確度。
在經典的Slope One算法中,每一個被填充的項目的分值都受到所有其他項目的影響,然而實際上其他項目可以分為與被填充項目相似的項目和無關的項目兩部分,如果能準確地將其劃分,那么一方面可以大大減少許多不必要的計算量,提高矩陣填充的速度,另一方面,由于減少了無關項的干擾,也可以使預測評分的準確度得到提高。因此,在采用Slope One算法進行矩陣填充之前,要先計算出不同項目之間的相似度。
在計算電影之間的相似度時,若以電影的標簽為基準則顆粒度過于粗糙,只能籠統地分為幾類或是十幾類。所以,為了提高電影的相似度計算結果的精度,本文采用了電影的關鍵詞數據來進行計算。表1展示了部分數據的關鍵詞,可以看出,電影的關鍵詞對電影的主題以及包含的元素都有較為細致的體現,因此通過對關鍵詞的計算可以衡量不同電影之間內容的相似度。

表1 電影關鍵詞表
在本文使用的數據集中,每部電影有10個左右的關鍵詞,關鍵詞滿足約束條件:每個關鍵詞僅包含一個明確語義,不同關鍵詞語義之間可以有交叉,但不完全重復。以上約束可以保證,兩個關鍵詞的語義越相似則相關度越大。將所有的關鍵詞k組成一個集合K,每一部電影對應的全部關鍵詞看作一個事件T,則每個事件都是項集的一個子集。統計所有的事件T中不同的ki和kj共同出現的頻數,計算ki和kj的相關度cori,j,表示為:
(1)
兩部電影之間的相似度frei,j,即為這兩部電影的關鍵詞列表中相關度最高的前m項的平均值,計算式如下:
(2)
用戶在選擇商品時,往往會對某一類或某幾類的商品情有獨鐘,在選擇電影時也是如此,即當用戶在選擇看電影時有對電影種類的傾向性。同時,當用戶給某部電影一個很低的評分時,事實上對于這位用戶而言,他已經給這部電影投過贊成票,也就是說在沒有觀看之前,他對這部電影是感興趣的。據此可以推斷出用戶對這類型電影的標簽是感興趣的,但是由于這部電影本身的質量不佳或與該用戶的預期不符導致最終該用戶對這部電影的評分不高。因此,雖然用戶對電影的評分很直觀地反映出了該用戶對這部電影的最終評價,但仍可以通過對其行為規律的挖掘,找到隱藏在評分背后的用戶興趣傾向。用戶對電影類型的選擇傾向度計算式如下:
(3)
式中:I為電影的類型集合;NA,i為用戶A觀看過的i類電影數;treA,i為用戶A對i類電影的選擇傾向度。計算出每位用戶對不同類型的電影的選擇傾向度之后,得到了一個用戶—電影類型矩陣,矩陣中的每個值為對應用戶對相應電影的選擇傾向度。矩陣的結構如表2所示。

表2 用戶選擇傾向度
表2中的每一行代表不同用戶,每一列代表不同的電影類型,共有二十種,分別為:Action,Adventure,Animation,Comedy,Crime,Documentary,Drama,Family,Fantasy,Foreign,History,Horror,Music,Mystery,Romance,Science Fiction,TV Movie,Thriller,War,Western。基于這個矩陣,就可以根據用戶對不同類型電影的選擇傾向度采用k-means聚類算法將用戶聚類。
k-means聚類算法是基于劃分的聚類算法,使用最為廣泛,有著簡單準確的優點,在各領域備受歡迎。其基本思想是,通過度量不同點之間的距離,迭代地調整聚類中心的位置,直到中心點的位置變化差值小于某一閾值。經典的k-means算法的缺點是選取聚類個數和聚類中心具有盲目性,使得聚類結果容易收斂到局部最優解并且收斂速度緩慢??紤]到在協同過濾算法計算用戶相似度時,兩名用戶都有評價的項目越多,計算結果就會越準確。因此,結合用戶相似度計算的特殊性在采用k-means算法選擇初始的聚類中心時,首先篩選出評分數據中評分數量最多的極小部分用戶,計算他們的相似度,然后采用兩兩之間相似度差值最大的k位用戶作為初始的聚類中心。在選擇聚類個數的時候,可以通過多次實驗對比結果的辦法,找到效果最佳的聚類個數。
Slope One算法最早由Daniel Lemire教授于2005年提出,該算法假設兩個項目的評分之間存在線性關系,只要計算出兩項目的評分的平均偏差以及兩位用戶的評價尺度偏差,就可以計算出對某項目的預測值。用戶對項目的評分用矩陣Rm×n表示,Ru,i為用戶u對項目i的評分,Iu為用戶u的所有評分項目,Ui為對項目i有評分的所有用戶的集合,Ui,j=Ui∩Uj為對項目i和項目j都有評分的用戶的交集,Ni,j為集合中元素的個數,則項目i和項目j之間的評分偏差Devi,j以及目標用戶x對項目i的預測評分prex,i的計算公式為:
(4)
(5)
經典的Slope One算法簡單高效并且易于擴展,但是沒有考慮到用戶的興趣偏好和項目的內容之間存在的相似性,隨著數據規模的不斷增大,會導致內存占用大、運算效率低并且預測結果的準確度也會變低。因此,利用前面得到的基于選擇傾向度的用戶聚類結果和電影的相似度計算結果,在對用戶-電影評分矩陣進行填充時,只使用同類型用戶中與待填充項相似的電影評分進行計算,可以大大減少預測某一評分時所需的其他評分數據量,提高系統的運行速度。另外,只采用同類用戶和相似項目的評分進行預測,可以使預測更加準確更有說服力,同時提高整個推薦系統的個性化程度。
協同過濾是推薦系統中被最廣泛采用的推薦方法,它大致可以分為三類:基于用戶的協同過濾、基于項目的協同過濾和基于模型的協同過濾。本文采用基于用戶的協同過濾算法,它基于與某用戶相似的用戶喜歡的物品該用戶也會喜歡的基本假設,通過對用戶的歷史數據進行分析,找到與該用戶最相似的用戶群,然后根據該用戶群里的其他用戶對項目的評分情況,找到該用戶可能感興趣的項目。
基于用戶的協同過濾首先要計算用戶之間的相似度,主流的相似度方法有歐式距離、皮爾遜系數、余弦相似度以及它們的變種。在電影推薦系統中,皮爾遜系數往往比其他計算方法更為有效,因為皮爾遜系數在計算相似度時充分考慮了不同用戶的評價準則不同對相似度計算結果的影響。在經過多次對比實驗,在其他條件都相同時,基于皮爾遜系數的相似度有較小的MAE值,且較為穩定。在計算某兩名用戶的相似度時,只需要把他們共同評價過的n部電影取出來,用對應的評分值作為這n維向量每個維度的值,即可根據公式計算兩向量的皮爾遜相關系數得到兩位用戶的相似度。
(6)

由于對于每個用戶來說,有評價的電影只占很小的一部分,將所有用戶的評分轉化為用戶-評分矩陣是極其稀疏的。同時,利用皮爾遜系數計算出的相似用戶的必要條件是兩位用戶都有評分的電影有足夠大的交集,若都打過分的電影數量不足時,計算出的相似度就會不準確。因此,本文采用矩陣填充的方法,將用戶對電影的預測評分插入評分矩陣中,拓展用戶向量的維度,彌補交集數量不足的影響。但是預測評分往往和真實評分之間存在誤差,而用兩個有誤差的數據進行計算顯然會造成誤差的累積。因此,首先找到兩位用戶有真實評分的電影集合的并集,然后對并集中沒有某一用戶評分的電影采用對應的預測值進行補全,最后用補全后的集合計算兩位用戶的相似度。

(7)
根據電影的標簽,將A對電影的評分轉化為對標簽的評分,得到A的偏好列表。然后根據電影m的標簽,修正用戶A對電影m的評分預測值:
(8)
式中:rA,g為用戶A對電影m對應的標簽g的偏好值,α為修正系數,修正系數的取值為使得真實評分值與類型標簽加權后的評分預測值間的平均誤差ε取得最小值時的權重系數。具體的計算公式如下:
(9)
式中:Num為該用戶的評價電影數。
改進后的協同過濾算法步驟如下:
輸入:用戶A,評分矩陣Rm×n。
輸出:針對用戶u的Top-N推薦列表。


Step3根據最近鄰居集UA里用戶的評分,利用式(7)計算出用戶A對待預測項目的預測評分。
Step4利用式(8)對用戶A的預測評分進行修正,將修正評分后的項目降序排列,把前N個項目推薦給用戶A。
本文的實驗數據來源于Kaggle網站上的The Movies Dataset,在該數據集中包括270 000位用戶對超過45 000部電影的約2 600萬條評分數據,根據式(10)計算出數據的稀疏度為1-26 000 000/(270 000×45 000)=0.997 8。
(10)
式中:spares為矩陣的稀疏度;Nr表示總評分數;Nu表示數據包括的總用戶數;Ni表示數據包括的總項目數。
該數據集包括了5個數據文件:存儲包括海報、背景、發布日期等元數據信息的文件movies_metadata.csv,存儲電影情節關鍵詞信息的文件keywords.csv,存儲演員和制作人員信息的文件credits.csv,存儲所有評分數據的文件ratings.csv,以及該數據集中所有電影對應的TMDB id和IMDB id文件links.csv。在實驗中采用五折交叉法進行驗證以避免偶然性,將數據集中每位用戶的評分數據隨機分為大致均勻的5份,每次實驗取其中4份為訓練集,剩余的1份為測試集,經過獨立的5次實驗后,取結果的平均值作為最后的實驗結果。
對聚類的效果進行評判的標準一般為各個樣本之間的距離或相似度,對于聚類生成的不同簇來說,將簇內的距離或相似度稱為凝聚度,將簇間的距離或相似度稱為分離度。通常簇內距離越小或者相似度越高則凝聚度越大,反之則越小;簇間距離越大或者相似度越低則分離度越大,反之則越小。然而凝聚度和分離度兩者并不獨立,其和等于每個樣本到總均值距離的平方和,因此不應該單獨地使用凝聚度或分離度作為聚類效果的評價標準,在本文中采取結合了凝聚度和分離度的輪廓系數作為聚類效果的度量標準。
輪廓系數的計算可以分為以下兩步:
第一步計算樣本個體的輪廓系數,假設樣本di被劃分到簇A中,ai為該樣本到它所屬的簇中其他所有樣本的平均距離(體現凝聚度),bi為該樣本與不包含它的任意簇中其他所有樣本的平均距離(體現分離度),則該樣本的輪廓系數silhouettei的計算公式為:
(11)
第二步計算這次聚類結果的平均輪廓系數silhouettek,n為樣本的總數,k為聚類的個數,則silhouettek的計算公式為:
(12)
樣本的輪廓系數可以衡量該樣本劃分的匹配程度,其取值silhouettei∈[-1,1],值越接近1表示該樣本與它所屬的簇內的其他樣本越相似,越接近0表示該樣本越靠近簇的邊緣,越接近-1則表示該樣本更應該被分到其他的簇中。平均輪廓系數silhouettek可以用于評估本次聚類的效果,通過比較所有可能的分類個數,取其中silhouettek最大的分類數k為最終的聚類個數。
本文對用戶可能的聚類個數進行實驗,得到選擇不同聚類個數k時的輪廓系數走勢,如圖2所示??梢钥闯觯垲惤Y果的輪廓系數隨著聚類的個數增多有下降的趨勢,在等于2時取得最大值,但只是簡單地將用戶分為兩類并不能將用戶的興趣偏好多元化地呈現出來,因此考慮第二個波峰,即聚類個數等于5或6的情況。由于后續的步驟中會在不同興趣偏好的用戶群組的內部進行計算,又希望不同群組中包含的用戶數量盡可能均勻,因此參考不同聚類個數下的方差,經計算在聚類個數為6時簇內方差的平均值比聚類個數為5時小。綜合以上兩點考慮,本文選取的聚類個數k為6。

圖2 不同聚類個數時的輪廓系數
Slope One算法的實質是預測用戶對某一個項目的評分,它依賴于用戶與用戶評分尺度的差值以及項目與項目之間平均評分的差值,有著準確率高、易于實現的優點。但傳統的Slope One算法存在盲目性,它并不對參與預測計算的值進行篩選,對于某兩位興趣偏好截然不同的用戶或者某兩個內容毫不相關項目顯然并沒有可比性,使用所有數據進行計算一方面會使計算量比較大,另一方面數據來源并不精準會導致預測結果的個性化程度降低。
傳統的Slope One算法可以根據用戶-項目評分矩陣對矩陣中絕大部分的空缺值計算出預測值,但是本文在這一步中的目標并不是計算出所有空缺值的預測評分,而是希望降低用戶-項目評分矩陣的稀疏程度。因此利用用戶以及項目之間的相似度對Slope One產生的預測值數量進行限制,在預測精度與預測數量之間進行取舍,將高準確度的預測值填充進用戶項目矩陣。
根據式(5),對于某一待預測的項目添加限制條件:待預測項目和與它相似項目的共同評分用戶數量需大于閾值Nu。通過對閾值Nu進行調整即可控制預測評分的數量,根據不同的閾值計算出填充后的矩陣稀疏度如圖3所示??梢钥闯?,當閾值取8時矩陣的稀疏度為0.952 3,最接近理論值,因此本文選擇將Nu=8時計算出的預測值填入用戶-評分矩陣。原始數據對應的用戶-評分矩陣的稀疏度為0.997 8,填充后對比原始矩陣的稀疏程度降低了(1-0.952 3)/(1-0.997 8)=21.68倍,有效地降低了評分矩陣的稀疏度。

圖3 閾值與矩陣稀疏度的關系
個性化推薦算法性能的指標非常豐富,不同的指標側重于推薦結果的不同方面,主要有覆蓋率、多樣性、新穎性和驚喜度等。而對于離線實驗往往采用評分預測準確度來進行衡量,常用的指標主要有平均絕對誤差和均方根誤差。
平均絕對誤差MAE和均方根誤差RMSE都是根據用戶的實際評分值和預測評分值來進行誤差度量的,MAE或RMSE的值越小則評分的預測值越準確。假設P為用戶的預測評分集合,R為用戶的實際評分集合,pi和ri為某用戶對某一電影對應的一組評分預測值和真實值,pi∈P且ri∈R,N為數據集中的評分總數,MAE和RMSE的計算公式如下:
(13)
(14)
本文選擇平均絕對誤差MAE和均方根誤差RMSE作為評分預測準確度的度量指標,從現有方法中挑選了最具代表性的SVD++[12]、NNMF[13]、FML[14]3種方法作為基線,與本文提出的方法分別在MovieLens 100k數據集[11]和The Movies Dataset上進行對比實驗。
1)SVD++:在考慮用戶和商品偏差項的矩陣分解模型的基礎上引入了隱反饋。
2)NNMF:使用多層感知機來對用戶和商品間的關系建模,實驗中使用了4個隱藏層。
3)FML:引入了度量學習對用戶和商品間的關系建模。
MovieLens 100k數據集是電影推薦領域最常用的數據集,它包括來自1 000個用戶對1 700部電影的100 000個評分,根據式(10)計算得出其稀疏度為0.941 2,The Movies Dataset的稀疏度為0.997 8,是前者的(1-0.941 2)/(1-0.997 8)=26.73倍。
最近鄰的個數k也是影響推薦結果的一個重要因素,實驗一將本文算法SFCF與其他3種算法在MovieLens 100k數據集上比較,結果如圖4所示。可以看出:隨著最近鄰數目增大,各算法的MAE值都迅速下降,當超過某個值時,會趨于穩定并有一定波動。以SVD++算法為例,在最近鄰數目40左右時MAE取得最小值,之后會有明顯回升,其他2種算法與它類似。而本文提出的SFCF算法在最近鄰數目增大時較為穩定,起伏不大,說明填充后的矩陣中每位用戶的相似用戶數目較多,不會因為相似用戶數目過多而導致選取低相似度用戶進行評分預測計算,有效地保持了預測評分的精度,這一特性也符合為解決數據稀疏性而對評分矩陣進行填充的效果預期。

圖4 4種算法隨最近鄰數目變化對比
實驗二將本文算法SFCF與其他3種算法分別在MovieLens 100k數據集和The Movies Dataset上進行對比實驗,結果如圖5和圖6所示。

圖5 4種算法在MovieLens 100k的MAE和RMSE對比

圖6 4種算法在The Movies Dataset的MAE和RMSE對比
通過對比可以看出在數據相對稠密的數據集MovieLens 100k上,本文算法的MAE和RMSE均比NNMF算法和SVD++低,與FML算法基本相同。但在數據更為稀疏的The Movies Dataset上,本文算法的MAE和RMSE均低于其他3種算法。同時,當數據的稀疏性增大時,其他3種算法的準確度都有大幅度下降,而本文算法仍能保持較高的準確度,證實了本文算法通過深入分析用戶和電影的各維度屬性數據,將挖掘出的不同用戶的興趣差異與協同過濾算法結合,有效地緩解了數據稀疏性問題對協同過濾算法的影響。
本文針對經典的協同過濾算法由于數據的稀疏性導致的推薦結果質量下降的問題[15-17],提出一種基于用戶興趣差異改進矩陣填充的個性化推薦算法。首先利用優化項目選取的Slope One算法對用戶-評分矩陣進行填充,然后使用填充后的矩陣形成Top-N推薦列表,最后根據用戶的興趣偏好對推薦列表再次過濾,得到最終的推薦結果。實驗通過與其他協同過濾算法的比較,驗證了本文算法可以緩解數據稀疏性的問題,在數據規模及其稀疏性不斷增大的情況下,能有效地提高系統的推薦質量。本文提出的推薦算法在計算用戶和項目的相似度時還有提升空間,在下一步的研究中,將考慮更多的用戶的年齡、職業、地域,以及電影的導演信息、演員構成等更多維度的數據,以提高用戶以及項目的相似性度量結果,從而提高最終的推薦質量。