基于用戶多種關聯(lián)信息和項目聚類的推薦算法

孫克雷，沈華理

(安徽理工大學計算機科學與工程學院，安徽 淮南 232001)

隨著科學技術的不斷進步，網絡已經慢慢變成人們獲取外界信息的重要工具，使得網絡信息正以噴井式的方式增長，大量的網絡用戶在面對巨大的網絡信息時，很難快速方便查詢到自己的需求信息。為了解決用戶需求很難得到滿足的現(xiàn)象，研究者們提出了很多的應對方案，推薦系統(tǒng)就是其中的一種。推薦系統(tǒng)[1-3]的目標是排除掉大量地無用信息，為用戶帶來個性化的推薦效果。其主要的過程是通過分析用戶的歷史行為信息，提取出用戶的偏好標簽，得到一組標簽集合，將與用戶偏好標簽集合相匹配的信息推薦給用戶，從而可以過濾掉大量跟用戶需求無關地數(shù)據(jù)，極大地提升了用戶體驗。

目前推薦技術主要采用基于關聯(lián)規(guī)則的推薦[4]、基于內容的推薦[5]、基于協(xié)同過濾推薦(CF)[6]和混合推薦[7]等。幾種常用的技術中協(xié)同過濾技術運用的最為普遍，傳統(tǒng)的協(xié)同過濾技術主要由兩部分組成：基于數(shù)據(jù)的協(xié)同過濾和基于模型的協(xié)同過濾?；谀Ｐ偷腃F通常根據(jù)數(shù)據(jù)進行建模，然后利用模型實現(xiàn)推薦?；跀?shù)據(jù)的協(xié)同過濾又可以分為：基于用戶(User-Based CF)[8]和基于項目(Item-Base CF)。隨著信息量的不斷增加，現(xiàn)在的推薦系統(tǒng)包含有大量的用戶和項目，并且系統(tǒng)中的項目和用戶數(shù)量還在持續(xù)的擴大，從而使得評分矩陣變得越來越稀疏，同時還存在新用戶的冷啟動問題[9]。

對于上述方法存在的不足，研究者們從各個方面來對其進行改善。例如文獻[10]提出的一種奇異值分解方法來降低推薦系統(tǒng)數(shù)據(jù)庫的維度，通過減小輸入矩陣的維度緩解數(shù)據(jù)稀疏性。文獻[11]采用計算項目相似度的方案用于填充評分矩陣，可以有效減小輸入矩陣的稀疏性。文獻[12]采用基于項目特征聚類的方法，其主要是按照用戶評價過的項目，找到與這些項目最近鄰的若干個聚類，并依據(jù)聚類結果進行推薦，有效地解決了稀疏性。文獻[13]利用k-means算法對項目聚類，找出目標項目的相似近鄰項目進行推薦，可以有效降低稀疏性。以上這些解決方案主要通過利用項目屬性進行評分矩陣數(shù)據(jù)填充，可以在有效降低稀疏性問題，但是其目的性主要都放在了解決數(shù)據(jù)稀疏性。

本文提出一種基于User-Based CF改進算法。該算法不僅將用戶自身固有的屬性，如用戶的年齡、性別、職業(yè)，作為計算相似用戶的因素，并且通過分析用戶與項目間的關聯(lián)信息，得到用戶偏愛項目和用戶評價過的項目數(shù)量等用戶非自身固有屬性也作為計算相似用戶的因素，以此來排除干擾近鄰用戶，提高用戶間相似度地準確度。通過用戶最近鄰對項目的評分，預測未評分項目的預評分。然后將預測評分填充到稀疏評分矩陣，再利用協(xié)同過濾算法計算得到目標用戶對未評分項目地最終預評分。最后依據(jù)最終預評分結合項目聚類產生Top-N推薦。

1 基于用戶的協(xié)同過濾算法

User-Based CF算法主要依據(jù)用戶的歷史行為數(shù)據(jù)產生推薦，如果一個用戶不存在任何歷史行為數(shù)據(jù)，那么該算法將不能計算出該用戶地相似近鄰用戶，也就不能實現(xiàn)對該用戶進行項目推薦，這種缺陷稱為新用戶的冷啟動現(xiàn)象。如果一個用戶存在歷史行為數(shù)據(jù)，那么就可以利用相似度的計算公式得到與該用戶歷史行為相似的最近鄰，依據(jù)最近鄰對項目地評分數(shù)據(jù)來給目標用戶未評分地項目進行預評分，按照預評分為目標用戶產生Top-N推薦。User-Based CF算法實現(xiàn)比較簡單，可分為三步進行描述：構建稀疏評分矩陣模型、計算得到最近鄰、預測評分并且產生Top-N推薦。

(1)構建用戶-項目評分矩陣模型

首先根據(jù)用戶歷史行為數(shù)據(jù)，可以建立稀疏評分矩陣Rm×n，如表1所示。其中，m代表用戶個數(shù)，n代表項目個數(shù)。

表1 用戶-項目評分矩陣

其中UX是用戶X，Ii是項目i，RX，i是用戶X對項目i的評分，null表示用戶還沒有評分的項目，一般初始化為0。從表1可以容易看出，該矩陣存在大量的數(shù)據(jù)冗余，數(shù)據(jù)稀疏性嚴重。

(2) 計算得到最近鄰

利用Rm，n矩陣，通過相似度計算公式得到用戶之間的相似度，從而構建出用戶相似度矩陣Sm，m，計算相似度的常見方法有很多種，例如歐幾里得距離公式、曼哈頓距離公式、余弦相似性、修正余弦相似性和Pearson相關系數(shù)。此處采用的是Pearson相關系數(shù)[14]計算法，計算方法如下

sim(X，Y)=

(1)

(3) 預測評分并且產生Top-N推薦

按照用戶之間的相似度，可以選擇出與目標用戶最相似地前k個近鄰用戶，利用近鄰用戶地歷史行為數(shù)據(jù)預判出目標用戶未評分項目地預評分，按照預評分向用戶進行Top-N推薦。此處計算預評分的方法為加權均值法[15]，公式如下

(2)

2 推薦算法的改進

根據(jù)上一節(jié)分析，基于用戶的協(xié)同過濾算法主要存在兩個問題：沒有最大化利用與用戶有關的關聯(lián)信息和準確度偏低。 為了解決上述問題，在基于用戶的協(xié)同過濾算法的基礎上進行了改進，提出一種基于用戶多種關聯(lián)信息和項目聚類的推薦算法。該算法主要分為兩部分，第一部分是利用用戶歷史行為信息和用戶關聯(lián)信息，構建用戶-項目評分矩陣、用戶相似度矩陣、填充后的用戶-項目評分矩陣。第二部分根據(jù)填充后的評分矩陣，結合User-Based CF算法，產生目標用戶的最終預評分，并且利用最終預評分通過項目聚類產生Top-N推薦列表。

2.1 填充用戶項目評分矩陣

根據(jù)用戶關聯(lián)信息能夠挖掘出用戶間共性，進而可以確定與其相似的近鄰用戶。因為用戶有些自身固有屬性特征是長期不變的，例如，地理位置、職業(yè)、年齡、性別等，這些屬性特征本身是沒有特殊含義的，但是如果和一些場景聯(lián)系起來，就能夠通過這些特征反應出一個群體的興趣偏好。除了用戶自身固有屬性可以產生用戶間相似性關聯(lián)外，還有一些用戶非固有屬性也可以挖掘出用戶之間的關聯(lián)，例如，本文將用戶偏愛項目屬性和用戶評價過的項目數(shù)量也作為計算用戶間相似度的屬性。利用用戶的屬性信息，計算出用戶之間的相似度，構建用戶相似度矩陣，然后得到用戶預評分，最后將預評分填充到稀疏評分矩陣中。

本文將計算用戶間相似度分為三部分：計算用戶固有屬性間的相似度、計算用戶非固有屬性間的相似度、計算用戶總的相似度。

2.1.1計算用戶固有屬性間的相似度

用戶各個固有屬性Ak之間的取值類型可能是不同的，一般可分為數(shù)值屬性、二元屬性、分類屬性。各個屬性間相似度的計算方法如下

1) 當Ak為二元屬性時

(3)

式中：AXk代表用戶X第k屬性地取值，AYk代表用戶Y第k屬性地取值。

2) 當Ak為數(shù)值屬性時

(4)

經過多次實驗，用戶年齡相差在5歲之內定義相似度為1比較合適。

3) 當Ak為分類屬性時

例如Ak為職業(yè)屬性時，各個職業(yè)之間具有語義上的關聯(lián)，為了獲取分類屬性間關聯(lián)度的大小，本文根據(jù)分類詞典構建出分類屬性層次樹，樹的結構圖如下

圖1 分類屬性層次樹

如圖1可知，將分類屬性按照層次劃分為4類，從上到下為包含關系，分類屬性Ak的值對應為樹中葉子結點，也就是細類。屬性間的相似度的計算思想為：對任意兩兩屬性進行深度和廣度相結合的遍歷，并且在遍歷過程中進行結點的比較，先進行樹的廣度遍歷，如果在同一層存在相同的結點，則跳轉到下一層進行樹的深度遍歷，直到在樹的某一層所有結點都不相同時，停止遍歷，記錄此時的遍歷深度，最后用遍歷深度除以樹的深度得到屬性間的相似度，計算公式如下

(5)

式中：father(AXk，AYk)代表兩個用戶AXk，AYk屬性對應樹中葉子結點地共同父節(jié)點，depth(father(AXk，AYk))代表該結點地深度，depth(T)代表樹地深度。

2.1.2計算用戶非固有屬性間的相似度

根據(jù)本文采用的數(shù)據(jù)集選取用戶偏愛的項目屬性和用戶評價過的項目數(shù)量為用戶非固有屬性。用I表示項目集合，I={i1，i2，i3，…，in}，n代表項目個數(shù)。用item-A表示項目屬性集合，item-AI={a1，a2，a3，…，ap}，p代表項目屬性個數(shù)，則項目-屬性矩陣Attr=|I|×|item-A|如表2所示。

表2 項目-屬性矩陣

在項目-屬性矩陣中如果項目ij具有屬性ak則將該屬性對應的值設置成1，否則設置成0，其中ij表示項目集合中的第j個項目，其中ak代表項目屬性集合中第k個屬性。

接下來根據(jù)用戶-項目評分矩陣和項目-屬性矩陣，通過計算提取出用戶偏愛電影項目屬性集合。主要推導過程如下：

1) 根據(jù)用戶X的歷史電影評分記錄，計算出用戶X對項目屬性集合中各個屬性的偏愛值(Bias Value)，計算公式如下

(6)

2) 計算出用戶X對項目屬性集合中各個屬性偏愛值的最大值，計算公式如下

(7)

3) 計算出用戶X對項目屬性集合中各個屬性的偏愛因子。

(8)

式中：I′表示用戶X評價過的項目集合；ak表示項目屬性集合中的第k屬性；iak表示項目i的第k個屬性，取值為0時表示該項目不具有該屬性，取值為1時表示該項目具有該屬性；B(X，ak)表示用戶X對項目屬性集合中各個屬性的偏愛值；max-B(X， item-A)表示用戶X對項目屬性偏愛值中的最大值。

用T表示用戶偏愛的項目屬性集合，定義T={t1，t2，t3，t4，…，tk，…，tp}。當γ(X，tk)≥ε舽時，則tk=1。 當γ(X，tk)<ε舽時， 則tk=0。 其中tk=1表示用戶偏愛項目屬性集合中的第k個屬性；其中tk=0表示用戶不喜歡項目屬性集合中的第k個屬性；ε舽為預設定的閾值。上述用戶非固有屬性可分為兩種：集合屬性和數(shù)值屬性。各個屬性相似度計算方法如下

1) 當Ak為集合屬性時

定義：AXk={tX1，tX2，…，tXk，…，tXp}

AYk={tY1，tY2，…，tYk，…，tYp}

式中:tXk代表用戶X是否偏愛項目屬性集合中第k個屬性，tYk代表用戶Y是否偏愛項目屬性集合中第k個屬性，tXk和tYk值為0或1，值為1表示偏愛，值為0表示不偏愛，相似度的計算方法如下

(9)

其中：

F(AXk∩AYk)=(tX1∩tY1，tX2∩tY2，…，tXk∩tYk，…，tXp∩tYp)

(10)

F(AXk∪AYk)=(tX1∪tY1，tX2∪tY2，…，tXk∪tYk，…，tXp∪tYp)

(11)

sum(F)表示將集合中的元素進行相加。

2) 當Ak為數(shù)值屬性時

(12)

式中：min[Aik，Ajk]表示取兩個值中最小值，max[Aik，Ajk] 表示取兩個值中最大值。

2.1.3計算用戶總的相似度

在計算用戶總相似度前，需要確定用戶各個屬性在相似度計算中所占的權重w(Ak)，在確定各個屬性權重后，用戶間相似度計算公式如下

(13)

式中：q代表用戶屬性地個數(shù)，a-sim(AXk，AYk)代表用戶X和用戶Y在第k個屬性上地相似度。

按照上述公式(13)可以計算任意兩個用戶間的相似度來構建用戶相似度矩陣Sm，m，依據(jù)Sm，m對目標用戶未評價過的項目進行預評分，并將用戶預評分填充到稀疏評分矩陣Rm，n中。用戶預評分的計算方法如下[16]

(14)

2.2 通過項目聚類構建推薦列表

由2.1節(jié)可得到填充后的評分矩陣，然后結合User-Based CF算法，求出目標用戶對未評分項目的最終預評分。

接下來對數(shù)據(jù)集里所有的項目進行聚類操作。通過表2的項目-屬性矩陣來求出項目間的相似度，進而將相似或相同的項目進行聚類。聚類操作需要設定項目間相似度的閾值β，即當兩個項目相似度item-sim(iu，iv)≥β時，就把這兩個項目聚為同一類。本文的項目相似度計算方法為

(15)

式中：p是項目屬性個數(shù)；aiuk是iu項目第k個屬性值；aivk是iv項目第k個屬性值。

接下來通過利用已知的聚類結果產生初始推薦列表。根據(jù)目標用戶的最終預評分，將預評分最高的項目按照公式(15)進行聚類，統(tǒng)計出相似或相同項目所在最多的項目類，本文采用的評分標準為[1-5]分制，最高分為5分。最后在對應的項目類中按照用戶預評分產生前Top-N個未評分的初始推薦項目。此時產生的推薦項目并不一定滿足推薦位越靠前推薦命中率越高的規(guī)則，所以本文引入了用戶評價項目的時間戳屬性，利用時間戳[17]屬性可以在一定程度上滿足上述規(guī)則。首先，尋找出目標用戶在訓練集里最近評價過的且喜歡的項目，然后將初始推薦列表中項目與該項目進行相似度的比較，按照相似度高低進行重排序[18]。經過重排序后的項目列表在一定程度上滿足推薦位越靠前命中率越高的規(guī)則，進而不僅可以使整個推薦列表準確度提高，還可以使每個推薦位的命中率提高。

2.3 算法的推薦步驟

算法 基于用戶多種關聯(lián)信息和項目聚類的推薦算法

輸入 待推薦的用戶ID，需要推薦的項目個數(shù)N

輸出 推薦項目列表List(Top-N)

step1 根據(jù)用戶歷史行為數(shù)據(jù)，建立稀疏評分矩陣Rm，n，利用用戶多種關聯(lián)信息依據(jù)公式(13)計算得到兩兩用戶間的相似度，建立用戶相似度矩陣Sm，m。

step2 利用Sm，m矩陣，依據(jù)公式(14)計算得到各個用戶未評分項目的預評分，并將預評分填充到Rm，n。

step3 利用填充后的評分矩陣，結合User-Based CF算法，產生目標用戶的最終預評分。

step4 對數(shù)據(jù)集中所有項目進行聚類操作，通過公式(15)求出項目間的相似度，然后按照給定的閾值β，將相似或相同的項目聚為同一類。

step5 根據(jù)得到的用戶最終預評分，將預評分最高的項目進行聚類，統(tǒng)計出相似或相同項目所在最多的項目類，在對應的項目類中按照用戶預評分產生Top-N個未評分的初始推薦項目。

step6 結合用戶評分的時間戳屬性對初始推薦項目列表重排列，產生最終推薦序列List(Top-N)。

3 實驗結果和分析

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

本實驗采用的是公共數(shù)據(jù)集，GroupLens-MovieLens數(shù)據(jù)集。該數(shù)據(jù)集中有項目信息表、用戶項目評分信息表、用戶信息表、電影的類型信息表、用戶職業(yè)信息表等。由于數(shù)據(jù)集中包含了一些與本實驗無關的噪聲數(shù)據(jù)行預處理。需要將項目信息表中，所以在使用該數(shù)據(jù)集之前需要對其進除項目屬性信息以外的其他所有信息過濾掉，并且使不同屬性值之間用空格隔開。

為了確保實驗地合理性，選擇不少于被10個用戶共同打過分地項目并且每個用戶不少于對10個項目進行評價過地用戶作為測試集合，總共選取100 000條用戶項目評分數(shù)據(jù)。把100 000條數(shù)據(jù)進行8/2劃分，80%用來作為訓練數(shù)據(jù)，20%用來作為測試數(shù)據(jù)，訓練數(shù)據(jù)中用戶評論數(shù)量為80 000條，測試數(shù)據(jù)中用戶評論數(shù)量為20 000條。為了驗證本文提出方法的有效性，分別在平均絕對誤差MAE和準確率評價標準上與其他推薦方法進行比較。使用五交叉驗證法來對上述兩種評測標準進行實驗論證，其中測試集數(shù)據(jù)互不相交。

3.2 測評指標

1) 平均絕對誤差(MAE)評價

MAE是指經過算法計算得到地用戶預評分數(shù)據(jù)與用戶地實際評分數(shù)據(jù)的誤差值，誤差值越小，說明算法預評分越是接近用戶真實的評分，進而就會使得推薦越符合用戶的興趣，準確率就越高。MAE的計算公式[19]如下

(16)

式中：n是目標用戶在測試集中評價地項目個數(shù)；Pt是目標用戶對第t個項目地預評分；Rt是目標用戶對第t個項目地真實評分。

2) 準確率評價

在推薦算法中準確率是衡量算法性能的重要指標之一，能夠反映出系統(tǒng)推薦的項目是否在一定程度上滿足用戶的需求。準確率的計算公式[20]如下所示

(17)

式中：R(u)是推薦系統(tǒng)為目標用戶u生成地項目群；T(u)是測試集中目標用戶u對某個項目評分為4分以上地項目群；U是測試集中地用戶集。

3.3 實驗結果與分析

本文選取2種對比算法如下：

1) 基于用戶的協(xié)同過濾算法(User-Based CF， UB-CF)。根據(jù)用戶評分矩陣信息，為用戶未評分的項目進行預評分，最后生成推薦列表。

2) 基于評分矩陣填充與用戶興趣的協(xié)同過濾推薦算法(Collaboration Filtering Recommendation Algorithm Based on Score Matrix Filling and User Interest，SMFUI-CF)。該算法首先是計算出用戶對項目的偏好度，然后填充用戶項目評分矩陣，最后引入時間的興趣度權重函數(shù)進和偏好度到項目相似度計算中，最終實現(xiàn)算法的推薦結果。

實驗1 在本文為了計算用戶間偏愛的項目屬性相似度，首先需要得到用戶偏愛的項目屬性集合，在這個過程中需要預先設定用戶偏愛因子閾值ε，因為閾值ε會對算法的MAE值產生較大的影響。由于ε的取值范圍是[0，1]，所以需要驗證ε在取不同值時MAE值的變化，本文取ε的值為0.1～0.9，間隔為0.1。已有研究表明當最近鄰k取[30，60]范圍內的值時會有很好的推薦效果。因此，設置k=50。此外，進過多次實驗統(tǒng)計當對應的性別、年齡、職業(yè)、偏愛的項目屬性和評價的項目數(shù)量五種用戶屬性的權值為w1=0.1，w2=0.1，w3=0.3，w4=0.3，w5=0.2本文算法會有很好的推薦效果。如圖2所示，不同的ε的取值對MAE值產生了很大的印象。

偏愛因子閥值ε圖2 偏愛因子閾值ε與MAE的關系

實驗2 參照實驗1中的結果，可以確定偏愛因子閾值ε的最優(yōu)取值為ε=0.5，然后計算出本文提出的基于用戶多種關聯(lián)信息和項目聚類的推薦算法在最近鄰數(shù)k取不同值時對應的MAE值，并且分別與UB-CF算法和SMFUI-CF算法進行比較，實驗對比結果如圖3所示。

圖3 MAE與最近鄰數(shù)k的關系

實驗3 在產生推薦結果的過程中需要進行項目聚類，而進行項目聚類需要預先確定項目相似度閾值β，因為β會對算法推薦的準確率產生重要的影響。本文中β的取值范圍是[0.1，0.9]，間隔為0.1，算法推薦項目個數(shù)取10，其他的參數(shù)設定與前兩個實驗一致。如圖4所示，項目相似度閾值β取不同值時，對算法準確率的影響。

項目相似度閥值β圖4 準確率與項目相似度閾值β的關系

實驗4 參照實驗3中的結果，可以確定項目相似度閾值β的最優(yōu)取值為β=0.9，然后計算出本文提出的基于用戶多種關聯(lián)信息和項目聚類的推薦算法在算法推薦項目個數(shù)取不同值時對應的準確率值，并且分別與UB-CF算法和SMFUI-CF算法進行比較，實驗對比結果如圖5所示。

圖5 準確率與推薦項目個數(shù)的關系

4 結論

本文提出一種基于用戶多種關聯(lián)信息和項目聚類的推薦算法，該算法可以有效的利用用戶關多種聯(lián)信息計算出兩兩用戶間地相似度，依據(jù)最近鄰計算出預評分并填入稀疏評分矩陣，其次通過協(xié)同過濾算法得到最終預評分，在此基礎上通過結合項目聚類產生初始推薦項目列表，最后融入時間戳屬性對推薦列表進行重排列，產生最終Top-N推薦。本文在MovieLens數(shù)據(jù)集驗證了該算法，實驗結果表明該算法不僅可以有效的降低MAE值，還可以提升推薦系統(tǒng)的準確率。