復(fù)雜情境感知下用戶(hù)聚類(lèi)協(xié)同推薦算法

畢孝儒

（四川外國(guó)語(yǔ)大學(xué)重慶南方翻譯學(xué)院國(guó)際商貿(mào)與管理學(xué)院，重慶401120）

0 引言

隨著Web2.0 互聯(lián)網(wǎng)技術(shù)普及和飛速發(fā)展，網(wǎng)絡(luò)上的資源正在爆炸式地增長(zhǎng)，致使用戶(hù)從網(wǎng)絡(luò)大量數(shù)據(jù)中獲取感興趣的信息需要耗費(fèi)大量時(shí)間。因此，各種形式的推薦技術(shù)應(yīng)運(yùn)而生。作為當(dāng)前主流的推薦技術(shù)，協(xié)同過(guò)濾推薦技術(shù)由于其算法實(shí)現(xiàn)簡(jiǎn)單、魯棒性強(qiáng)等優(yōu)點(diǎn)，已經(jīng)廣泛應(yīng)用到各個(gè)行業(yè)和領(lǐng)域。其基本思想是基于用戶(hù)-項(xiàng)目評(píng)分?jǐn)?shù)據(jù)集，通過(guò)收集相似用戶(hù)的興趣信息進(jìn)而對(duì)目標(biāo)用戶(hù)推薦。但隨著用戶(hù)和項(xiàng)目數(shù)量的指數(shù)增長(zhǎng)，該算法存在計(jì)算量大、數(shù)據(jù)稀疏性、推薦質(zhì)量不高的問(wèn)題[1]。

針對(duì)以上問(wèn)題，李濤[2]提出了一種基于用戶(hù)聚類(lèi)的協(xié)同過(guò)濾推薦算法；王曉耘[3]將基于粗糙理論和用戶(hù)聚類(lèi)相結(jié)合以提高協(xié)同過(guò)濾推薦算法精度；郭弘毅[4]在融合社區(qū)結(jié)構(gòu)和興趣聚類(lèi)基礎(chǔ)上，實(shí)現(xiàn)協(xié)同過(guò)濾推薦；段元波[5]通過(guò)對(duì)基于項(xiàng)目評(píng)分與類(lèi)型評(píng)分進(jìn)行聚類(lèi)分析，降低了協(xié)同過(guò)濾推薦算法計(jì)算量；許鵬遠(yuǎn)[6]提出一種基于聚類(lèi)系數(shù)的推薦算法，將推薦系統(tǒng)抽象為一個(gè)有向加權(quán)二分圖并考慮聚類(lèi)系數(shù)因素的影響重新定義相似度計(jì)算方法；以上算法較好地解決了以上傳統(tǒng)協(xié)同過(guò)濾推薦算法計(jì)算量大的不足，但由于其并未考慮用戶(hù)對(duì)項(xiàng)目評(píng)分時(shí)的復(fù)雜情境信息，因此推薦精度不高。

基于上述分析，提出了一種復(fù)雜情境感知下用戶(hù)聚類(lèi)協(xié)同推薦算法（Collaborative Filtering Recommendation Algorithm of User Clustering based on Complex Circumstance Awareness,UCCA-CF）。實(shí)驗(yàn)結(jié)果表明，該算法在降低推薦計(jì)算量的同時(shí)，提升了推薦質(zhì)量。

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

基于用戶(hù)的協(xié)同過(guò)濾算法通過(guò)在用戶(hù)-項(xiàng)目評(píng)分矩陣上計(jì)算用戶(hù)間相似性，以確定目標(biāo)用戶(hù)的的鄰居集，并將目標(biāo)用戶(hù)所感興趣的項(xiàng)目通過(guò)一定推薦方法返回用戶(hù)。

1.1 用戶(hù)對(duì)項(xiàng)目評(píng)分?jǐn)?shù)據(jù)

推薦系統(tǒng)中存儲(chǔ)的用戶(hù)評(píng)分?jǐn)?shù)據(jù)包括用戶(hù)id、項(xiàng)目id 和用戶(hù)對(duì)項(xiàng)目的評(píng)分。設(shè)有m 個(gè)用戶(hù)和n 個(gè)項(xiàng)目，U={U1,U2,…Um}表示用戶(hù)集，I={I1,I2,…In}表示項(xiàng)目集，則用戶(hù)評(píng)分?jǐn)?shù)據(jù)可采用一個(gè)m×n 階的用戶(hù)-項(xiàng)目評(píng)分矩陣R={rm,n}表示。其中，rm,n表示用戶(hù)Um對(duì)項(xiàng)目In的評(píng)分值，rm,n值越大，說(shuō)明用戶(hù)對(duì)其越感興趣。

1.2 用戶(hù)相似性度量

當(dāng)前，常用的相似性度量方法有Pearson 相關(guān)系數(shù)和修正余弦相似性。設(shè)為用戶(hù)Ui評(píng)過(guò)分的項(xiàng)目集合為用戶(hù)Ui產(chǎn)生的評(píng)分均值。則Pearson 相關(guān)系數(shù)計(jì)算用戶(hù)Ui與Uj相似性方法如式（1）所示：

修正余弦相似性計(jì)算用戶(hù)相似性方法如式（2）所示：

1.3 預(yù)測(cè)評(píng)分

根據(jù)用戶(hù)間的相似度可以獲取目標(biāo)用戶(hù)的最近鄰居集合，并將其相似性作為權(quán)重預(yù)測(cè)目標(biāo)用戶(hù)對(duì)未評(píng)分項(xiàng)目的評(píng)分，故目標(biāo)用戶(hù)Ui對(duì)項(xiàng)目i 的評(píng)分Put,i預(yù)測(cè)如式（3）所示：

2 復(fù)雜情境感知下用戶(hù)聚類(lèi)協(xié)同推薦算法

2.1 基本定義

情境是指用于表征與交互環(huán)境相關(guān)的實(shí)體狀態(tài)的信息集合，它包括空間、時(shí)間、物理環(huán)境狀態(tài)、人的情緒、心理狀態(tài)及相互關(guān)系等。

定義1 復(fù)雜情境協(xié)同過(guò)濾推薦系統(tǒng)中用戶(hù)情感、社交圈、用戶(hù)位置、基礎(chǔ)設(shè)施和物理?xiàng)l件等信息的集合，用向量表示為

定義2 情境感知協(xié)同過(guò)濾推薦系統(tǒng)通過(guò)對(duì)用戶(hù)的復(fù)雜情境信息進(jìn)行推理和分析、挖掘以實(shí)現(xiàn)推薦預(yù)測(cè)。

以下通過(guò)表1 分析用戶(hù)在不同情境組合下的項(xiàng)目評(píng)分對(duì)對(duì)推薦結(jié)果產(chǎn)生的影響。

表1 不同情境信息對(duì)推薦結(jié)果影響

表1 中復(fù)雜情境包括社交圈、位置、時(shí)間和情感4大類(lèi)。而每一類(lèi)又分成若干子類(lèi)。推薦系統(tǒng)可以通過(guò)情境感知不同的情境層次為用戶(hù)推薦不同的項(xiàng)目。譬如，User1 和User2 在家人，圖書(shū)館、下午和愉快情境下Id1 和Id4 偏好一致，User1 和User2 在朋友，購(gòu)物商場(chǎng)、上午和悲傷情境下Id1 和Id4 對(duì)項(xiàng)目評(píng)分相同，因此，可認(rèn)為在相同情境下User1 和User2 具有較高相似性。故可以根據(jù)User1 在其他情境下對(duì)項(xiàng)目的評(píng)分為User2 在相同情境下進(jìn)行推薦，比如，在家人、工作區(qū)、下午和愉快情境下可為User2 推薦Id3。

通過(guò)以上分析，在引入復(fù)雜情境信息后協(xié)同推薦函數(shù)F 可表示為：

F:User×Item×Circums tan ce →Rating

其中，User 表示用戶(hù),Item 表示項(xiàng)目，Circumstance表示復(fù)雜情境信息,Rating 表示用戶(hù)對(duì)項(xiàng)目的評(píng)分。

2.2 用戶(hù)復(fù)雜情境信息相似因子

在協(xié)同過(guò)濾推薦系統(tǒng)中，可對(duì)用戶(hù)的復(fù)雜情境信息進(jìn)行細(xì)粒度劃分，產(chǎn)生不同層次的環(huán)境信息。例如，將社交圈情境細(xì)分為家人、同事、朋友、陌生人等；將位置情境劃分為商場(chǎng)、實(shí)驗(yàn)室、工作區(qū)等。在此基礎(chǔ)上，形 成 復(fù)雜情境向 量CUCCA-CF 算法在對(duì)各個(gè)情境信息取值量化、歸一化后，定義用戶(hù)復(fù)雜情境信息相似因子為：

2.3 改進(jìn)的用戶(hù)相似度度量

針對(duì)傳統(tǒng)戶(hù)相似度計(jì)算公式未考慮用戶(hù)情境信息的不足，UCCA-CF 算法依據(jù)式（1）和式（2），給出改進(jìn)的Pearson 相關(guān)系數(shù)用戶(hù)相似度度量公式為：

改進(jìn)的修正余弦用戶(hù)相似度度量公式如下：

2.4 考慮復(fù)雜情境信息的用戶(hù)聚類(lèi)分析

對(duì)于文獻(xiàn)[2]在僅在User-Item 矩陣上對(duì)用戶(hù)進(jìn)行聚類(lèi)，而并未考慮用戶(hù)當(dāng)時(shí)評(píng)分的復(fù)雜情境信息的問(wèn)題。UCCA-CF 算法在User-Item 矩陣上加入用戶(hù)評(píng)分時(shí)的復(fù)雜情境信息維度，并采用改進(jìn)C 均值聚類(lèi)算法，實(shí)現(xiàn)用戶(hù)評(píng)分信息和復(fù)雜情境信息聚類(lèi)分析，生成用戶(hù)類(lèi)別所屬度矩陣。

算法1 復(fù)雜情境信息下用戶(hù)聚類(lèi)算法

輸入：用戶(hù)聚類(lèi)的類(lèi)別數(shù)目k，原始數(shù)據(jù)source=（User,Item,Circumstance,Rating），用戶(hù)相似性閾值t。

Step1：確定初始聚類(lèi)中心；

Step2：for r=1:m{

（1）采用式（5）或（6）計(jì)算第r 個(gè)用戶(hù)的評(píng)分和情境信息與各個(gè)聚類(lèi)中心的相似度；

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

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

將用戶(hù)r 所屬類(lèi)別歸入該聚類(lèi)類(lèi)別;

Step3：將屬于同一類(lèi)別的所有用戶(hù)評(píng)分和情境信息平均值作為該類(lèi)中心；返回Step2，直到聚類(lèi)中心不再發(fā)生變化。

依據(jù)上述用戶(hù)聚類(lèi)結(jié)果，定義用戶(hù)類(lèi)別所屬度矩陣如下：

其中，n 為用戶(hù)數(shù)量，k 代表用戶(hù)聚類(lèi)中心數(shù)。

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

2.4 最近鄰用戶(hù)確定

UCCA-CF 算法在用戶(hù)聚類(lèi)分析的基礎(chǔ)上，通過(guò)算法2 確定目標(biāo)用戶(hù)的l 個(gè)最近鄰用戶(hù)。

算法2 目標(biāo)用戶(hù)的最近鄰用戶(hù)確定算法

輸出:目標(biāo)用戶(hù)的L 個(gè)最近鄰用戶(hù)。

Step1：依據(jù)公式（5）或（6）計(jì)算目標(biāo)用戶(hù)與k 個(gè)聚類(lèi)中心之間的相似性，得到相似度向量V={ v1,v2,v3,…,vk}。

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

Step3:將上述歐氏距離最小的前L 個(gè)用戶(hù)作為目標(biāo)用戶(hù)的最近鄰用戶(hù)。

2.5 預(yù)測(cè)評(píng)分計(jì)算

考慮到改進(jìn)的用戶(hù)相似度度量公式，以及算法2確定的目標(biāo)用戶(hù)L 個(gè)最近鄰用戶(hù)，UCCA-CF 算法對(duì)項(xiàng)目評(píng)分預(yù)測(cè)公式修改為：

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)準(zhǔn)則

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

3.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)硬件環(huán)境為Intel Core i5 系列CPU、2.2GHz 主頻、2GB 內(nèi)存；實(shí)驗(yàn)軟件環(huán)境為Windows 7 操作系統(tǒng)、Microsoft VS 2008、SQL Server 2010 數(shù)據(jù)庫(kù)。

3.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)將平均絕對(duì)誤差（Mean Absolute Error，MAE）作為算法性能評(píng)價(jià)標(biāo)準(zhǔn)。MAE 通過(guò)計(jì)算預(yù)測(cè)的用戶(hù)評(píng)分與實(shí)際的用戶(hù)評(píng)分之間的偏差度量預(yù)測(cè)的準(zhǔn)確性,MAE 越小,推薦質(zhì)量越高。假設(shè)預(yù)測(cè)的用戶(hù)評(píng)分集為{ p1,p2,…,pn} ，對(duì)應(yīng) 實(shí) 際 評(píng)分集 為{q1,q2,…,qn},則MAE 計(jì)算公式如式（19）所示：

3.4 仿真實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)將數(shù)據(jù)按75%和25%的比例劃分為訓(xùn)練集和測(cè)試集，在分別采用改進(jìn)的Pearson 相關(guān)系數(shù)用戶(hù)相似度和改進(jìn)的修正余弦用戶(hù)相似度公式計(jì)算用戶(hù)相似性的同時(shí)，將本文提出的UCCA-CF 算法與傳統(tǒng)基于用戶(hù)的協(xié)同過(guò)濾算法U-CF、文獻(xiàn)[2]基于用戶(hù)聚類(lèi)的協(xié)同過(guò)濾算法UC-CF、文獻(xiàn)[3]基于粗糙集聚類(lèi)協(xié)同過(guò)濾推薦算法RC-CF、文獻(xiàn)[4]融合社區(qū)結(jié)構(gòu)和興趣聚類(lèi)的協(xié)同過(guò)濾推薦算法CIC-CF、文獻(xiàn)[5]基于項(xiàng)目評(píng)分與類(lèi)型評(píng)分進(jìn)行聚類(lèi)的推薦算法ITC-CF 進(jìn)行了對(duì)比實(shí)驗(yàn)。

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

圖1 改進(jìn)的Pearson相關(guān)相似性公式下的MAE值

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

表2 算法運(yùn)行效率對(duì)比（單位：秒）

由表2 的數(shù)據(jù)可以看出，隨著訓(xùn)練數(shù)據(jù)數(shù)目增加，與傳統(tǒng)的基于用戶(hù)協(xié)同過(guò)濾算法U-CF 相比較，UCCA-CF 算法運(yùn)行效率具有明顯優(yōu)勢(shì)。

4 結(jié)語(yǔ)

本文從減少協(xié)同推薦算法計(jì)算量、提高推薦質(zhì)量角度出發(fā)，提出復(fù)雜情境感知下用戶(hù)聚類(lèi)協(xié)同推薦算法，首先，本文在定義用戶(hù)復(fù)雜情境信息相似因子基礎(chǔ)上，現(xiàn)對(duì)傳統(tǒng)用戶(hù)相似性度量公式改進(jìn)。然后，對(duì)用戶(hù)歷史評(píng)分信息與復(fù)雜情境信息進(jìn)行聚類(lèi)分析以產(chǎn)生用戶(hù)類(lèi)別所屬度矩陣；最后，在類(lèi)別所屬度矩陣上確定目標(biāo)用戶(hù)最近鄰居，進(jìn)行項(xiàng)目推薦。實(shí)驗(yàn)結(jié)果表明本文算法是有效的。