基于用戶實(shí)時(shí)行為的Slope One模型與算法

陳 潔， 潘 郁， 張振海， 潘 芳

(1.南京工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，江蘇 南京 211816； 2.南京工業(yè)大學(xué) 國家大學(xué)科技園，江蘇 南京 210009; 3.南京中醫(yī)藥大學(xué) 經(jīng)貿(mào)管理學(xué)院，江蘇 南京 210046)

?

基于用戶實(shí)時(shí)行為的Slope One模型與算法

陳 潔1， 潘 郁1， 張振海2， 潘 芳3

(1.南京工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，江蘇 南京 211816； 2.南京工業(yè)大學(xué) 國家大學(xué)科技園，江蘇 南京 210009; 3.南京中醫(yī)藥大學(xué) 經(jīng)貿(mào)管理學(xué)院，江蘇 南京 210046)

以技術(shù)創(chuàng)新平臺(tái)為背景，針對(duì)原有協(xié)同過濾算法推薦滯后以及算法可擴(kuò)展性差的問題，根據(jù)用戶的實(shí)時(shí)反饋，在Slope One算法的基礎(chǔ)上，提出了更新增量機(jī)制，分解出固定因子以及增量因子，當(dāng)用戶對(duì)項(xiàng)目的評(píng)分改變時(shí)，只需更新增量因子，提高了算法的可擴(kuò)展性，更精確地反應(yīng)了用戶的興趣變化。經(jīng)算例驗(yàn)證，該算法在保證推薦精度的同時(shí)可以有效地縮短推薦時(shí)間。

管理科學(xué)與工程；增量更新機(jī)制；Slope One 算法；用戶行為；實(shí)時(shí)推薦

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，技術(shù)創(chuàng)新平臺(tái)日益成為目前的研究熱點(diǎn)之一。其中技術(shù)推薦模塊通過學(xué)習(xí)用戶的偏好屬性，將適當(dāng)?shù)募夹g(shù)推薦給用戶，這樣的個(gè)性化推薦也日益成為各學(xué)科研究的焦點(diǎn)[1～3]。然而，隨著用戶的不斷增多，原有的協(xié)同過濾算法存在可擴(kuò)展性差的問題。并且，個(gè)性化推薦的要求越來越高，要求實(shí)時(shí)反映用戶的興趣變化，因?yàn)橛脩舻臍v史興趣并不代表其當(dāng)前興趣。

Slope One[4]算法是基于已有評(píng)分的協(xié)同過濾算法，該算法假設(shè)兩個(gè)項(xiàng)目之間的評(píng)分滿足線性y=x+b的關(guān)系，通過對(duì)這兩個(gè)項(xiàng)目評(píng)分過的評(píng)分?jǐn)?shù)據(jù)擬合該線性函數(shù)，獲得參數(shù)b的估計(jì)值[5]，從而估計(jì)目標(biāo)項(xiàng)目的評(píng)分。因此，該算法簡單、高效，可擴(kuò)展性強(qiáng)，常被用來做實(shí)時(shí)推薦。

目前，針對(duì)反應(yīng)用戶興趣變化的問題，文獻(xiàn)[6]借鑒了心理學(xué)遺忘規(guī)律，提出了線性逐步遺忘過濾算法，依據(jù)評(píng)價(jià)時(shí)間線性逐步減小每項(xiàng)評(píng)分的重要性，但是線性逐步減小比較粗糙。在此基礎(chǔ)上，文獻(xiàn)[7]提出了在預(yù)測(cè)評(píng)分的過程中增加指數(shù)時(shí)間函數(shù)，數(shù)據(jù)越新，指數(shù)時(shí)間函數(shù)值越大，但依然沒有解決數(shù)據(jù)的實(shí)時(shí)更新問題。文獻(xiàn)[8]提出的基于項(xiàng)目的協(xié)同過濾增量更新機(jī)制以及文獻(xiàn)[9]提出的基于用戶實(shí)時(shí)反饋的協(xié)同過濾算法解決了數(shù)據(jù)的在線實(shí)時(shí)更新問題，但是由于該算法計(jì)算相似性時(shí)涉及到整個(gè)User-Item矩陣，時(shí)間和空間的復(fù)雜度較大。

鑒于此，本文在已有的Slope One算法的基礎(chǔ)上，根據(jù)用戶的實(shí)時(shí)評(píng)分行為，分解出固定因子以及隨評(píng)分改變的增量因子，改變了原有的推薦更新時(shí)需要對(duì)整個(gè)數(shù)據(jù)空間進(jìn)行重新計(jì)算的做法，只對(duì)增量因子做出改動(dòng)，提高了算法的可擴(kuò)展性。

1 Slope One算法

(1)

根據(jù)用戶u對(duì)技術(shù)項(xiàng)目i的評(píng)分預(yù)測(cè)用戶對(duì)技術(shù)項(xiàng)目j的評(píng)分：

(2)

(3)

圖1 增量更新機(jī)制流程

2 基于用戶實(shí)時(shí)反饋的增量更新機(jī)制

2.1 基于用戶實(shí)時(shí)反饋的增量更新機(jī)制推薦模型

當(dāng)用戶對(duì)技術(shù)項(xiàng)目進(jìn)行進(jìn)行評(píng)分時(shí)，需要觸發(fā)相應(yīng)的增量因子，以達(dá)到數(shù)據(jù)實(shí)時(shí)更新的目的。圖1為增量更新機(jī)制推薦模型。

2.2 基于用戶實(shí)時(shí)反饋的增量更新機(jī)制描述

當(dāng)用戶對(duì)技術(shù)項(xiàng)目提交了評(píng)分或者重新評(píng)分時(shí)，系統(tǒng)需要觸發(fā)更新機(jī)制來更新技術(shù)項(xiàng)目之間的平均差異度，從而更新用戶對(duì)技術(shù)項(xiàng)目的預(yù)測(cè)評(píng)分。

于消毒供應(yīng)室中，表現(xiàn)出繁瑣的日常工作以及較大的工作量，選擇傳統(tǒng)護(hù)理方式進(jìn)行護(hù)理干預(yù)，無法實(shí)現(xiàn)護(hù)理的細(xì)節(jié)化以及有效化，難以獲得理想護(hù)理效果。對(duì)此確定有效方法展開消毒供應(yīng)室護(hù)理工作存在顯著意義[5] 。

(4)

(5)

(6)

公式(6)可以化簡為：

(7)

(2)用戶對(duì)技術(shù)項(xiàng)目m進(jìn)行了初次評(píng)分，此時(shí)要分兩種情況：

①目標(biāo)用戶對(duì)技術(shù)項(xiàng)目進(jìn)行了初次評(píng)分

則新評(píng)分技術(shù)項(xiàng)目與預(yù)測(cè)技術(shù)項(xiàng)目之間的差異度為：

(8)

用戶u對(duì)技術(shù)項(xiàng)目j的預(yù)測(cè)評(píng)分為：

(9)

(10)

②其他用戶k對(duì)技術(shù)項(xiàng)目m進(jìn)行了初次評(píng)分

a)目標(biāo)用戶未對(duì)該技術(shù)項(xiàng)目進(jìn)行評(píng)分，則不會(huì)觸動(dòng)增量更新機(jī)制

b)目標(biāo)用戶已對(duì)該技術(shù)項(xiàng)目進(jìn)行評(píng)分，則：

(11)

(12)

2.3 基于用戶實(shí)時(shí)反饋的增量更新機(jī)制實(shí)現(xiàn)

Rm,n為用戶評(píng)分矩陣

步驟1 若用戶對(duì)技術(shù)項(xiàng)目i進(jìn)行重新評(píng)分，則計(jì)算Δui，并使用公式(7)計(jì)算用戶對(duì)技術(shù)項(xiàng)目j的預(yù)測(cè)評(píng)分；

步驟2 若用戶對(duì)技術(shù)項(xiàng)目m進(jìn)行初次評(píng)分，則判斷該用戶是目標(biāo)用戶還是其他用戶，若該用戶為目標(biāo)用戶，則轉(zhuǎn)向步驟3；若該用戶為其他用戶，則轉(zhuǎn)向步驟4；

步驟4 判斷目標(biāo)用戶是否已對(duì)該技術(shù)項(xiàng)目進(jìn)行評(píng)分，若目標(biāo)用戶已對(duì)該技術(shù)項(xiàng)目進(jìn)行評(píng)分，則轉(zhuǎn)向步驟5；否則不觸動(dòng)增量更新機(jī)制；

表1 IU-S與T-S的MRT比較

3 算例

本文擬用創(chuàng)新驛站數(shù)據(jù)庫中的技術(shù)供需方—技術(shù)對(duì)接項(xiàng)評(píng)分?jǐn)?shù)據(jù)。將從其中隨機(jī)選取300個(gè)用戶對(duì)272個(gè)技術(shù)項(xiàng)目的25340個(gè)評(píng)分記錄，分值為1～5，分?jǐn)?shù)越高，表示用戶對(duì)該技術(shù)項(xiàng)目越偏好。

對(duì)于算法的評(píng)估，本文采用了平均絕對(duì)誤差(Mean Absolute Time ,MAE)以及平均評(píng)估時(shí)間(Mean Assess Time, MAT)作為度量標(biāo)準(zhǔn)。將實(shí)驗(yàn)數(shù)據(jù)分為訓(xùn)練集以及測(cè)試集。

設(shè)預(yù)測(cè)的用戶評(píng)分集合表示為{p1,p2,K,pN}，對(duì)應(yīng)的實(shí)際用戶評(píng)分集合為{q1,q2,…,qN}，則平均絕對(duì)偏差MAE定義為：

設(shè)用戶i發(fā)出請(qǐng)求時(shí)間為Tis用戶得到推薦結(jié)果時(shí)間為Tie，則平均推薦時(shí)間定義為：

實(shí)驗(yàn)將本文提出的基于增量更新機(jī)制的Slope One算法(Incremental Updating Slope One, IU-S)與傳統(tǒng)的Slope One協(xié)同過濾算法(Traditional Slope One , T-S)進(jìn)行比較。

通過實(shí)驗(yàn)得到以下的結(jié)果。

圖2 IU-S與T-S的MAE比較

圖3 IU-S與T-S的MRT比較

通過實(shí)驗(yàn)結(jié)果可知，算法的推薦精度受用戶數(shù)量的影響較大， IU-S算法的推薦精度與T-S算法相比，并無多大差異。但是，平均推薦時(shí)間明顯低于T-S算法，并隨著樣本數(shù)的增加，IU-S 算法在推薦時(shí)間上的優(yōu)勢(shì)也在逐步擴(kuò)大?？梢?，本文提出的IU-S算法在保證推薦精度的情況下，對(duì)于用戶的實(shí)時(shí)反饋縮短了推薦時(shí)間，更精確地反應(yīng)了用戶的實(shí)時(shí)興趣變化。

4 結(jié)束語

本文在原有Slope One算法的基礎(chǔ)上，根據(jù)用戶的實(shí)時(shí)行為，對(duì)Slope One算法做出改進(jìn)：分解出算法中的固定因子以及增量因子。使得用戶在提交評(píng)價(jià)時(shí)實(shí)時(shí)地更新增量因子，避免了傳統(tǒng)的算法中需要對(duì)整個(gè)數(shù)據(jù)空間進(jìn)行重新計(jì)算的做法，使得算法能夠以較小的代價(jià)及時(shí)地反映出用戶的興趣變化，從而做出更精確的推薦。由于一些評(píng)分的改變并不會(huì)對(duì)推薦結(jié)果產(chǎn)生影響，但是卻會(huì)占用系統(tǒng)開銷，因此本文下一步的研究將對(duì)此展開，即如何劃分出有效評(píng)分以及無效評(píng)分。

[1] Liu J G, Zhou T, Che H, et al. Effects of high-order correlations on personalized recommendations for bipartite networks[J]. Physica A, 2010, 389: 881- 886.

[2] Liu J G, Wang B H, Guo Q. Improved collaborative filtering algorithm via information transformation[J]. International Journal of Modern Physics C, 2009, 20: 285-293.

[3] Guo Q, Liu J G. Clustering effect of user-object bipartite network on personalized recommendation[J]. International Journal of Modern Physics C, 2010, 21: 891-901.

[4] Lemire D, Maclachlan A. Slope one predictors for online rating-based collaborative filtering[C]. SIAM: Proc of SIAM Data Mining Conf, 2005: 21-23.

[5] 王毅，樓恒越.一種改進(jìn)的Slope One協(xié)同過濾算法[J].計(jì)算機(jī)科學(xué)，2011，38(10)：192-194.

[6] 鄭先榮，曹先彬.線性逐步遺忘協(xié)同過濾算法的研究[J].計(jì)算機(jī)工程，2007，33(6) ：72-73，82.

[7] 劉芳先,宋順林.改進(jìn)的協(xié)同過濾推薦算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47(8)：72-75.

[8] 李聰，梁昌勇.適應(yīng)用戶興趣變化的協(xié)同過濾增量更新機(jī)制[J].情報(bào)學(xué)報(bào)，2010，29(1)：59-66．

[9] 傅鶴崗,李冉.基于用戶實(shí)時(shí)反饋的協(xié)同過濾算法[J].計(jì)算機(jī)應(yīng)用，2011，31(7)：1744-1747.

Slope One Model and Algorithm Based on Real-time User Behavior

CHEN Jie1, PAN Yu1, ZHANG Zhen-hai2, PAN Fang3

(1.SchoolofEconomicsandManagement,NanjingUniversityofTechnology,Nanjing211816,China; 2.NationalUniversitySciencePark,NanjingUniversityofTechnology,Nanjing210009,China; 3.SchoolofEconomicsandManagement,NanjingUniversityofChineseMedicine,Nanjing210023,China)

Set in technology innovation platform, traditional collaborative filtering algorithm which has the problem of lagged recommendation and bad scalability is focused on. According to users’ real-time feedback, incremental update mechanism is introduced, which detaches fixed factor and incremental factor. When the score is changed, only incremental factor needs to be changed, which improves the scalability of the algorithm and reflects the users’ interest change more accurately. The experimental results indicate that the algorithm ensures accuracy of the recommendation and at the same time reduces the recommendation time.

management science and engineering; incremental updating mechanism; slope one algorithm; user behavior; real-time recommendation

2013- 09-26

中國博士后基金(2013M531259)；教育部人文社科青年基金項(xiàng)目(13YJC630116)；江蘇省博士后基金(1202103C)；江蘇省教育廳科技項(xiàng)目(2012JSSPITP0904)；南京市鼓樓區(qū)科技計(jì)劃項(xiàng)目(2013018)

陳潔(1990-)，女，江蘇蘇州人，碩士研究生，研究方向：技術(shù)創(chuàng)新與商務(wù)智能；潘郁(1955-)，男，江蘇南通人，教授,博士，研究方向：計(jì)算管理與商務(wù)智能。

TP311

A

1007-3221(2015)01- 0089- 04