結合用戶聚類與改進用戶相似性的協同過濾推薦

顧明星，黃偉建，黃 遠，生 龍，申 超，張夢甜

河北工程大學 信息與電氣工程學院，河北 邯鄲056038

1 引言

隨著互聯網和電子技術的快速發展，以用戶和商品為核心的信息生產模型使得網絡信息量呈現爆炸式增長，人類進入了“信息過載”的時代。推薦算法作為解決“信息過載”的最有效手段之一，得到了廣泛的應用[1-2]。但是隨著用戶和項目規模的擴大，推薦算法面臨著嚴重的數據稀疏性問題[3]。以推薦系統在電子商務中的應用為例，通常用戶購買的商品總量只占據網站商品總量的1%，并且用戶僅僅對其中的極少數項目進行評分，用戶項目評分矩陣極其稀疏[4]。同時，傳統的協同過濾算法在計算用戶間相似性時往往只強調用戶間的評分相似度，使得推薦算法在實際應用中面臨著用戶相似性計算不準確，商品推薦的實時性低的問題[5]，嚴重影響了推薦算法預測準確率。

為了解決上述問題，國內外的相關學者提出了多種改進方案。首先為了解決數據矩陣的稀疏性問題，大量基于聚類的推薦算法被提出。文獻[6]采用譜聚類算法，利用譜聚類將興趣類似的用戶劃分為一簇，然后在簇內為目標用戶進行項目推薦。文獻[7]首先采用Kmeans算法對用戶屬性特征進行聚類，然后利用SlopeOne算法對矩陣進行缺值填充，最后利用協同過濾思想進行評分預測。文獻[8]采用吸引子傳播算法對用戶屬性進行聚類，相比于一般聚類算法而言，該算法不需要提供聚類中心數，因此聚類效果較好，但時間和內存開銷過高。其次，為了改善推薦算法的預測準確性和推薦物品的實時性，文獻[9]在傳統的皮爾遜相似度中引入懲罰因子和時間權重。文獻[10]先采用密度峰值聚類算法（Clustering by Fast search and find of Density Peaks，CFDP）對項目進行聚類以降低數據稀疏性，然后在計算項目評分時引入時間權重，降低了用戶的興趣動態變化的影響。文獻[11]引入了社交網絡中的用戶信任關系，將傳統的用戶評分相似度與用戶信任度進行融合，從而獲得更加精確的用戶相似度計算方式。

上述算法雖然在一定程度上提高了預測準確性，但對用戶信息的挖掘仍然不夠充分。因此本文提出了一種結合用戶屬性聚類與改進用戶相似性的協同過濾推薦算法。算法首先利用K-means++算法對用戶屬性進行聚類，從而獲得目標用戶所在的評分矩陣；其次對用戶的評分相似性引入時間因素，以增大用戶最近行為項目的協同推薦能力；然后引入用戶信任誤差，計算改進后的用戶直接信任度和間接信任度；最后將基于時間因素的用戶評分相似性和改進的用戶信任度合理地結合，從而改善用戶間的相似性。通過改進后的用戶相似性公式，利用協同過濾思想對目標用戶未評分項目進行預測評分，產生推薦列表。

2 傳統的協同過濾算法

傳統的協同過濾算法基本步驟是：首先利用已有的用戶歷史行為數據信息，構建用戶-項目評分矩陣；然后計算用戶之間的相似度并選取相似度較高的用戶作為目標用戶的近鄰集；最終在進行評分預測后按照Top-N原則對用戶進行推薦[12]。該算法的流程如圖1所示。

圖1 Item_CF算法流程圖

2.1 構建用戶-項目評分矩陣

本文構建用戶-項目評分矩陣Cm×n,users:{u1,u2,…,um}表示擁有m 個用戶的集合；items:{i1,i2,…,in}表示擁有n 個項目的集合；cij表示用戶i 對項目j 的實際評分，若用戶i 對項目j 未評分，則cij記0。評分矩陣C如下：

2.2 用戶評分相似性的計算

用戶評分相似性的計算是以用戶-評分矩陣為基礎的，將評分矩陣中的每一行作為用戶的評分向量來表示用戶的實際興趣。因此，計算用戶評分相似性的本質就是計算用戶評分向量之間的距離。傳統的協同過濾算法中，計算相似度的方式有很多，主要包括余弦相似度、修正余弦相似度和皮爾遜相關系數[13]。本文采用最為常用且效果更好的皮爾遜相關系數作為用戶間相似度計算公式[14]，如式（1）所示。

其中，sim(a,b)表示用戶a 與b 的相似度，I 表示用戶a與用戶b 評分項目的交集，分別表示用戶a 與b的平均評分。

2.3 預測評分

在獲得用戶a 與所有用戶的相似度后，將相似度最高的前h 個用戶作為其近鄰集，并根據式（2）對a 未評分的項目預測評分。

其中，pa,i表示用戶a 對項目i 的預測評分，G 表示用戶a 的近鄰集。

3 本文算法

3.1 基于K-means++的用戶屬性聚類

為了降低用戶評分矩陣的稀疏性，本文首先對用戶屬性進行聚類分析，將屬性相似的用戶劃分到同一簇內。K-means++算法是一種基于質心的聚類算法，是在K-means算法的基礎上優化了初始質心的選擇方式，使初始質心相互間距離盡可能得遠[15]。 K-means++算法具有算法高效率、易實現、適合挖掘大規模數據集的特點[16]，因此本文選取K-means++算法作為聚類手段。

在對用戶屬性進行K-means++聚類前，首先需要對用戶的屬性信息進行預處理，過程如下。

步驟1 從數據集中獲取用戶的屬性信息：UserAttr={age,sex,job}。

步驟2 對非數值的離散型數據進行編碼，將文本特征進行數值化。在用戶屬性中，根據埃里克森八階段理論[17]，將年齡劃分為以下4個年齡段（數據集中用戶年齡最小為15歲）：“15～18歲”編碼為“1”，“19～40歲”編碼為“2”，“41～65 歲”編碼為“3”，“66 歲以上”編碼為“4”；性別為“F”和“M”，編碼為“0”和“1”；職業屬性一共包含21種類別，因此構建長度為5的“01”編碼串(21 ＜25)，并按照職業出現的順序進行編碼。例如在本文選用的數據集中，首先出現“technician”職業，則該職業編碼為“00001”，其次出現為“writer”，則該職業編碼為“00010”，然后出現“executive”，則該職業編碼為“00011”，其余職業的編碼以此類推。最后對用戶的屬性編碼進行拼接。例如：用戶屬性為“age=42||sex=M||job=executive”，則該用戶的屬性編碼串為“3100011”。

步驟3 對用戶屬性編碼進行Embedding。Embedding通過將原稀疏向量與固定轉換矩陣做內積變化，從而將高維稀疏特征向量向低維稠密特征向量轉換。

步驟4 對用戶屬性進行預測處理后，最后得到用戶屬性矩陣p。

算法1 K-means++聚類算法

輸入：用戶屬性矩陣p，聚類數目k。

輸出：k 個聚類。

步驟1 隨機選取一個樣本作為初始質心center1；

步驟2 選取p 中的每一個樣本點dx，計算該點與當前最近一個質心的距離dist(dx)；

步驟3 利用式（3）計算每一個樣本點dx作為下一個質心的概率：

步驟4 將概率最高的點，作為下一個聚類質心點centeri；

步驟5 重復步驟2～步驟4直至找到預設的k 個質心；

步驟6 得到k 個用戶簇并輸出。

采用K-means++算法對用戶屬性進行聚類后，將目標用戶所在的用戶簇對應至用戶評分矩陣，從而得到縮小規模的用戶-項目評分矩陣。如果不經過該預處理，則評分數據會占用較大的內存，且嚴重降低協同推薦算法的執行效率和推薦準確性。

3.2 時間因素

傳統的協同過濾算法計算用戶間的相似度時僅僅考慮用戶對項目的歷史評分記錄，忽略了用戶對項目興趣的動態變化，在當前各類的用戶行為數據集中，用戶行為的時間通常是被系統準確記錄的，因此可以考慮用戶對某一項目的興趣程度會受到時間因素的影響。一般而言，用戶最近訪問的項目往往更能準確反映用戶當前的興趣特征。因此本文引入時間因素增大用戶最近訪問商品的協同推薦能力，相關定義如下。

定義1 Tfirst：用戶第一次對商品進行評分的時間。

定義2 Ti：用戶對商品i 進行評分的時間。

定義3 Tall：用戶使用該系統的總時長。

根據分析，用戶對某一項目的興趣會隨著時間的推移逐漸弱化，并趨于一個穩定值，即用戶興趣與時間呈現非線性負相關關系，這與心理學家艾賓浩斯發現的遺忘規律相似[18]，因此本文采用遺忘規律來量化時間因素，則用戶u 對項目i 的時間因素權值的計算公式如下所示：

然后將時間權重與皮爾遜相似度計算公式結合，公式如下所示：

3.3 改進用戶信任度

傳統的用戶間信任關系中，用戶a 信任用戶b，則用戶b 也會信任用戶a，并且雙方的信任值是相同的。但結合實際，用戶a 與用戶b 之間的信任是不一定對等的。因為兩者的評分項目的數量不一定相同，用戶的評分尺度也不一定相同[19]。

3.3.1 直接信任度的計算

直接信任度是目標用戶與其他用戶的直接信任關系，對于用戶a 與用戶b，用戶a 對用戶b 的直接信任度可由下列公式計算。

其中，DTrust(a,b)表示用戶a 對用戶b 的直接信任度值。但是用戶之間的信任度僅從用戶共同評分項目的數量上來判斷是不準確的，如表1所示。

表1 極端評分數據

由式（6）可得DTrust(a,b)=1，即用戶a 與用戶b 是極其信任的。但實際情況是，用戶a 對列舉的4種物品評價極高，用戶b 則極低。說明單從用戶間共同評分項目的數量上計算用戶間的相似度是不準確的。

為了緩解用戶間對物品的實際評分存在的差異對用戶信任度的影響，本文定義信任誤差值，公式如下所示：

其次，根據信任誤差值定義用戶交互響應因子數，公式如下所示：

其中，t 表示正響應因子數，記錄用戶a 與用戶b 間的評分差異較小的次數；f 表示負響應因子數，記錄兩者評分差異較大的次數。若兩者評分差異小，則t+1 →t，反之f+1 →f 。

用戶間的信任是隨著正負響應因子數呈非線性變化的量，用戶間正響應因子數越多，相互信任程度越高，反之越低。因此，可以利用Logistic 函數將正負響應因子數進行恰當融合。Logistic函數是一種”S”形函數，在區間（0，1）變化，能充分抑制兩端的值，且對中間值變化敏感[20-21]，公式如下所示：

則改進的直接用戶信任度公式如下：

根據式（10）可以得出，用戶間信任度隨著正響應因子數的增加而提高，隨著負響應因子數的增加而降低。

3.3.2 間接信任度的計算

若用戶a 與用戶c 共同評分的項目交集為空集，則用戶a 與用戶c 之間不存在用戶直接信任度，此時可以采用信任傳遞的方式獲取兩位用戶的間接信任度：假設至少存在一個中間用戶群user={ub,ud,ue,…,uv}，使得用戶a 與用戶ub存在直接信任關系，用戶群user 中相鄰的用戶存在直接信任關系，用戶uv與用戶c 存在直接信任關系，則可以推論出用戶a 與用戶c 之間存在間接信任度[22]。在計算用戶間的間接信任度時，若存在多個用戶群，則選取傳遞人數最少的中間用戶群來計算間接信任度。用戶間接信任度計算公式如下所示：

其中，| user|表示傳播路徑最短的中間用戶群的人數。

同時，根據“六度區隔”理論[23]，設定| user|+1 ≤6，若大于6則PTrust*(a,c)=0。

綜合了用戶直接信任與用戶間接信任，則用戶間的最終信任表達公式如式（12）所示：

3.4 改進的用戶相關性

在利用式（5）獲得基于時間因素的用戶評分相似度與式（12）獲得改進的用戶信任度后，本文將兩種影響推薦效果的因素相結合，得到最終的用戶間的相關性，公式如下：

當用戶間的評分相似度為0時，則利用信任度表示用戶間相關性；當用戶間沒有信任度時，則用戶間不存在相關性；當兩種因素均不為0 時，則用戶間的相關性會隨著兩種因素的增加而提高。

最后預測出用戶對項目的評分，公式如下所示：

其中，G*表示與用戶a 相關性最高的前h 個近鄰用戶。

3.5 本文算法流程

算法2 結合用戶屬性聚類與改進用戶相似性的協同過濾算法

輸入：目標用戶a，用戶-用戶評分矩陣C，用戶評分時間信息T 。

輸出：目標用戶a 的推薦列表。

步驟1 利用算法1 的K -means++聚類算法獲得目標用戶a 所在的用戶-用戶屬性簇S，并對應到相應的用戶-評分矩陣中得到簇S′。

步驟2 在簇S′中，遍歷除了用戶a 外的用戶，利用式（5）計算與用戶a 的相似度。

步驟3 在簇S′中，遍歷除了用戶a 外的用戶，利用式（12）計算與用戶a 的信任度。

步驟4 在計算出其他用戶與用戶a 的相似度與信任度后，利用式（13）計算與用戶a 的相關性。

步驟5 將與用戶a 相關性最高的前h 個用戶作為a 的近鄰集。

步驟6 在用戶a 的近鄰集內，利用式（14）預測目標用戶a 對未評分項目的評分。

步驟7 將預測評分最高的項目由高到低排序，并將前Top-N 個項目作為目標用戶a 的推薦項目集。

4 實驗與討論

4.1 數據集

本文選取MovieLens ml-100K 電影數據集[24]，該數據集由明尼蘇達大學GroupLens學習組發布，用戶評分數據集中包含943名用戶對1 682部電影的共約10萬條記錄，其中包括用戶ID、電影ID、用戶對項目的評分以及相應評分的時間。用戶的評分區間為[1，5]，評分越高，則評價越高。用戶屬性數據集包括用戶的ID、年齡、性別、職業。本文采用五折交叉實驗法，將80%的數據用作訓練樣本，20%的數據用作測試樣本。

4.2 評價指標

本文采用推薦算法實驗中最為廣泛的評價準則——平均絕對誤差（Mean Absolute Error，MAE）作為實驗的評分預測指標[25]，公式如下：

4.3 實驗結果與分析

為了獲取最佳聚類數k，將目標用戶的近鄰數從20變化到90，間隔為10。根據文獻[7]和文獻[26]的研究情況，本文將用戶劃分為k=5,6,7,8,9 個聚類，然后在對應不同的聚類數下計算不同用戶近鄰數下的MAE 值，重復實驗10 次，并取其結果的平均值作為最終結果。實驗結果如圖2所示。

圖2 不同聚類數下本文算法的MAE對比圖

通過圖2 可以得出，當聚類數目k=7 時，本文算法的推薦準確性更高。因此，本文實驗聚類簇設定為7，聚類后每個簇中用戶的數量如表2所示。

表2 不同類中的用戶量

同時為了驗證不同聚類數k 下K-means++算法的實際聚類效果，本文采用輪廓系數[27]作為評價聚類質量的標準。不同聚類數k 下的輪廓系數值如表3所示。

表3 不同聚類數下的輪廓系數

由表3可知，當聚類數k 為7時，K-means++算法的輪廓系數最高，即聚類效果最佳。

在確定了用戶聚類數為7后，對用戶相似性的分布進行實驗。本文分別將皮爾遜相關系數與改進的用戶相關性作為協同過濾推薦算法的相似度計算公式，實驗統計了這兩種方法得到不同相似度出現的次數，分布如圖3所示。

圖3 不同公式對應的用戶相似性分布

通過圖3可以看出，本文改進的用戶相關性得到的相似性分布曲線沒有皮爾遜相關性得到的分布曲線平穩和均勻，說明本文的相關性得到的用戶相似性更具有個性化。在相似度[0.1，1.0]的范圍內，皮爾遜相關系數得到相似度分布在[0.2，0.6]的次數占比69.8%，而本文改進的用戶相關性僅占比63.5%。因為改進的用戶相關性通過增加用戶的評分時間信息和用戶信任度，降低了用戶評分尺度和評分時間的差異對用戶相似性的影響。

為了驗證本文提出的算法能有效提高協同過濾算法的推薦質量，本文選取傳統的基于用戶的協同過濾算法（User-CF）、文獻[7]提出的CFUI-CF算法、文獻[10]提出的CFDP-CF算法、文獻[11]提出的UTLDA-CF算法作為對比算法，僅結合時間因素的本文算法以及僅結合改進用戶信任的本文算法對比結果如圖4所示。

圖4 不同算法的MAE值對比

通過圖4可以看出，所有算法的MAE 值，均隨著目標用戶近鄰數的增加而逐漸減少，直到趨于平緩。首先通過觀察可以發現，僅結合時間因素的本文算法和僅結合改進用戶信任的本文算法能有效改善推薦算法的預測效果，分別比User-CF 的準確率高1.2%和2.9%，但預測效果不如將兩者結合的本文算法。在實驗范圍內的用戶近鄰數下，本文提出的算法能夠提高User-CF的準確率達5.6%，且分別比CFDP-CF、CFUI-CF、UTLDA-CF、僅結合時間因素的本文算法和僅結合改進用戶信任的本文算法的MAE 值低0.6%、1.4%、3.1%、4.6%和3.1%，說明本文算法能有效提高推薦系統預測質量。

5 結束語

本文提出了結合用戶屬性聚類與改進用戶相似性的協同過濾算法。首先利用K-means++對用戶特征信息進行聚類，其次對皮爾遜相關系數引入用戶對項目的評分時間信息，然后改進用戶之間的信任關系，最后將引入時間信息的皮爾遜相關系數與改進的用戶信任關系進行結合，最終得到改進的用戶相關性。實驗表明，本文提出的算法能有效提高推薦算法的預測準確性，且有一定的實際意義。