復雜情境感知下用戶聚類協同推薦算法

畢孝儒

（四川外國語大學重慶南方翻譯學院國際商貿與管理學院，重慶401120）

0 引言

隨著Web2.0 互聯網技術普及和飛速發展，網絡上的資源正在爆炸式地增長，致使用戶從網絡大量數據中獲取感興趣的信息需要耗費大量時間。因此，各種形式的推薦技術應運而生。作為當前主流的推薦技術，協同過濾推薦技術由于其算法實現簡單、魯棒性強等優點，已經廣泛應用到各個行業和領域。其基本思想是基于用戶-項目評分數據集，通過收集相似用戶的興趣信息進而對目標用戶推薦。但隨著用戶和項目數量的指數增長，該算法存在計算量大、數據稀疏性、推薦質量不高的問題[1]。

針對以上問題，李濤[2]提出了一種基于用戶聚類的協同過濾推薦算法；王曉耘[3]將基于粗糙理論和用戶聚類相結合以提高協同過濾推薦算法精度；郭弘毅[4]在融合社區結構和興趣聚類基礎上，實現協同過濾推薦；段元波[5]通過對基于項目評分與類型評分進行聚類分析，降低了協同過濾推薦算法計算量；許鵬遠[6]提出一種基于聚類系數的推薦算法，將推薦系統抽象為一個有向加權二分圖并考慮聚類系數因素的影響重新定義相似度計算方法；以上算法較好地解決了以上傳統協同過濾推薦算法計算量大的不足，但由于其并未考慮用戶對項目評分時的復雜情境信息，因此推薦精度不高。

基于上述分析，提出了一種復雜情境感知下用戶聚類協同推薦算法（Collaborative Filtering Recommendation Algorithm of User Clustering based on Complex Circumstance Awareness,UCCA-CF）。實驗結果表明，該算法在降低推薦計算量的同時，提升了推薦質量。

1 基于用戶的協同過濾算法

基于用戶的協同過濾算法通過在用戶-項目評分矩陣上計算用戶間相似性，以確定目標用戶的的鄰居集，并將目標用戶所感興趣的項目通過一定推薦方法返回用戶。

1.1 用戶對項目評分數據

推薦系統中存儲的用戶評分數據包括用戶id、項目id 和用戶對項目的評分。設有m 個用戶和n 個項目，U={U1,U2,…Um}表示用戶集，I={I1,I2,…In}表示項目集，則用戶評分數據可采用一個m×n 階的用戶-項目評分矩陣R={rm,n}表示。其中，rm,n表示用戶Um對項目In的評分值，rm,n值越大，說明用戶對其越感興趣。

1.2 用戶相似性度量

當前，常用的相似性度量方法有Pearson 相關系數和修正余弦相似性。設為用戶Ui評過分的項目集合為用戶Ui產生的評分均值。則Pearson 相關系數計算用戶Ui與Uj相似性方法如式（1）所示：

修正余弦相似性計算用戶相似性方法如式（2）所示：

1.3 預測評分

根據用戶間的相似度可以獲取目標用戶的最近鄰居集合，并將其相似性作為權重預測目標用戶對未評分項目的評分，故目標用戶Ui對項目i 的評分Put,i預測如式（3）所示：

2 復雜情境感知下用戶聚類協同推薦算法

2.1 基本定義

情境是指用于表征與交互環境相關的實體狀態的信息集合，它包括空間、時間、物理環境狀態、人的情緒、心理狀態及相互關系等。

定義1 復雜情境協同過濾推薦系統中用戶情感、社交圈、用戶位置、基礎設施和物理條件等信息的集合，用向量表示為

定義2 情境感知協同過濾推薦系統通過對用戶的復雜情境信息進行推理和分析、挖掘以實現推薦預測。

以下通過表1 分析用戶在不同情境組合下的項目評分對對推薦結果產生的影響。

表1 不同情境信息對推薦結果影響

表1 中復雜情境包括社交圈、位置、時間和情感4大類。而每一類又分成若干子類。推薦系統可以通過情境感知不同的情境層次為用戶推薦不同的項目。譬如，User1 和User2 在家人，圖書館、下午和愉快情境下Id1 和Id4 偏好一致，User1 和User2 在朋友，購物商場、上午和悲傷情境下Id1 和Id4 對項目評分相同，因此，可認為在相同情境下User1 和User2 具有較高相似性。故可以根據User1 在其他情境下對項目的評分為User2 在相同情境下進行推薦，比如，在家人、工作區、下午和愉快情境下可為User2 推薦Id3。

通過以上分析，在引入復雜情境信息后協同推薦函數F 可表示為：

F:User×Item×Circums tan ce →Rating

其中，User 表示用戶,Item 表示項目，Circumstance表示復雜情境信息,Rating 表示用戶對項目的評分。

2.2 用戶復雜情境信息相似因子

在協同過濾推薦系統中，可對用戶的復雜情境信息進行細粒度劃分，產生不同層次的環境信息。例如，將社交圈情境細分為家人、同事、朋友、陌生人等；將位置情境劃分為商場、實驗室、工作區等。在此基礎上，形 成 復雜情境向 量CUCCA-CF 算法在對各個情境信息取值量化、歸一化后，定義用戶復雜情境信息相似因子為：

2.3 改進的用戶相似度度量

針對傳統戶相似度計算公式未考慮用戶情境信息的不足，UCCA-CF 算法依據式（1）和式（2），給出改進的Pearson 相關系數用戶相似度度量公式為：

改進的修正余弦用戶相似度度量公式如下：

2.4 考慮復雜情境信息的用戶聚類分析

對于文獻[2]在僅在User-Item 矩陣上對用戶進行聚類，而并未考慮用戶當時評分的復雜情境信息的問題。UCCA-CF 算法在User-Item 矩陣上加入用戶評分時的復雜情境信息維度，并采用改進C 均值聚類算法，實現用戶評分信息和復雜情境信息聚類分析，生成用戶類別所屬度矩陣。

算法1 復雜情境信息下用戶聚類算法

輸入：用戶聚類的類別數目k，原始數據source=（User,Item,Circumstance,Rating），用戶相似性閾值t。

Step1：確定初始聚類中心；

Step2：for r=1:m{

（1）采用式（5）或（6）計算第r 個用戶的評分和情境信息與各個聚類中心的相似度；

（2）取出這些相似性中最大值；

（3）if（該最大值>t）

將用戶r 所屬類別歸入該聚類類別;

Step3：將屬于同一類別的所有用戶評分和情境信息平均值作為該類中心；返回Step2，直到聚類中心不再發生變化。

依據上述用戶聚類結果，定義用戶類別所屬度矩陣如下：

其中，n 為用戶數量，k 代表用戶聚類中心數。

Sij,i=1,2,3,…,n,j=1,2,3,…,k 表示采用式（5）或（6）計算的第i 個用戶到與第j 個聚類中心的相似度。

2.4 最近鄰用戶確定

UCCA-CF 算法在用戶聚類分析的基礎上，通過算法2 確定目標用戶的l 個最近鄰用戶。

算法2 目標用戶的最近鄰用戶確定算法

輸出:目標用戶的L 個最近鄰用戶。

Step1：依據公式（5）或（6）計算目標用戶與k 個聚類中心之間的相似性，得到相似度向量V={ v1,v2,v3,…,vk}。

Step2：計算向量V={v1,v2,v3,…,vk} 與類別所屬程度矩陣S（n,k）各行的歐氏距離；

Step3:將上述歐氏距離最小的前L 個用戶作為目標用戶的最近鄰用戶。

2.5 預測評分計算

考慮到改進的用戶相似度度量公式，以及算法2確定的目標用戶L 個最近鄰用戶，UCCA-CF 算法對項目評分預測公式修改為：

3 實驗與分析

3.1 實驗數據集及評價準則

實驗采用GroupLens 研究小組提供的MovieLens（http://movieslens.umn.edu）數據集，它包括943 個用戶對1 682 個項目的10 萬條投票記錄。其中，用戶屬性有年齡、性別、郵編和職業。實驗將用戶屬性和電影評價時間作為情境信息，驗證UCCA-CF 算法有效性。

3.2 實驗環境

實驗硬件環境為Intel Core i5 系列CPU、2.2GHz 主頻、2GB 內存；實驗軟件環境為Windows 7 操作系統、Microsoft VS 2008、SQL Server 2010 數據庫。

3.2 評價指標

實驗將平均絕對誤差（Mean Absolute Error，MAE）作為算法性能評價標準。MAE 通過計算預測的用戶評分與實際的用戶評分之間的偏差度量預測的準確性,MAE 越小,推薦質量越高。假設預測的用戶評分集為{ p1,p2,…,pn} ，對應 實 際 評分集 為{q1,q2,…,qn},則MAE 計算公式如式（19）所示：

3.4 仿真實驗結果與分析

實驗將數據按75%和25%的比例劃分為訓練集和測試集，在分別采用改進的Pearson 相關系數用戶相似度和改進的修正余弦用戶相似度公式計算用戶相似性的同時，將本文提出的UCCA-CF 算法與傳統基于用戶的協同過濾算法U-CF、文獻[2]基于用戶聚類的協同過濾算法UC-CF、文獻[3]基于粗糙集聚類協同過濾推薦算法RC-CF、文獻[4]融合社區結構和興趣聚類的協同過濾推薦算法CIC-CF、文獻[5]基于項目評分與類型評分進行聚類的推薦算法ITC-CF 進行了對比實驗。

由圖1、圖2 可知，無論采用改進的Pearson 相關相似性公式，還是改進的修正余弦相似性公式，在鄰居數目相同的前提下，UCSA-CF 算法的MAE 值均明顯小于其他算法，表明文本提出算法的有效性。

圖1 改進的Pearson相關相似性公式下的MAE值

圖2 修正余弦相似性公式下的MAE值

表2 算法運行效率對比（單位：秒）

由表2 的數據可以看出，隨著訓練數據數目增加，與傳統的基于用戶協同過濾算法U-CF 相比較，UCCA-CF 算法運行效率具有明顯優勢。

4 結語

本文從減少協同推薦算法計算量、提高推薦質量角度出發，提出復雜情境感知下用戶聚類協同推薦算法，首先，本文在定義用戶復雜情境信息相似因子基礎上，現對傳統用戶相似性度量公式改進。然后，對用戶歷史評分信息與復雜情境信息進行聚類分析以產生用戶類別所屬度矩陣；最后，在類別所屬度矩陣上確定目標用戶最近鄰居，進行項目推薦。實驗結果表明本文算法是有效的。