印桂生，崔曉暉，馬志強(qiáng)

(哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

網(wǎng)絡(luò)技術(shù)的發(fā)展帶來了信息過載［1］現(xiàn)象.作為一種信息過濾手段，協(xié)同過濾推薦系統(tǒng)［2］根據(jù)用戶對某些資源的歷史評價信息，主動提供其可能感興趣的資源列表.

現(xiàn)有協(xié)同過濾推薦系統(tǒng)，如Tapestry System［3］，Grouplens［4］，Yahoo Tomoharu［5］等，將發(fā)生于不同時刻下的歷史信息等同對待，缺乏對其時效量化分析.一種合理的思維是:距離當(dāng)前時刻越近的歷史評價信息在評價預(yù)測中具有更高的推薦效用，反之，距離當(dāng)前時刻越遠(yuǎn)的歷史評價效用越低，即時效隨時間發(fā)生衰減［6］.一些研究成果采用線性或非線性衰退函數(shù)量化評價時效隨時間變化情況.KOYCHEV［7］采用線性函數(shù)作為時效量化基礎(chǔ).KUKAR［8］采用核函數(shù)計算時效隨時間衰減情況.DIND［9］指出時效量化是一個隨時間發(fā)生梯度逐漸下降過程，故指數(shù)函數(shù)更加適合時效量化.上述模型雖然一定程度上滿足時效隨時間發(fā)生衰退的基本特征，但沒有考慮資源的時效衰退差異性問題.在推薦系統(tǒng)中，用戶興趣漂移［10］普遍存在導(dǎo)致時效衰退程度發(fā)生動態(tài)改變，表現(xiàn)為受歡迎的資源其時效衰減速率較慢.因此，如何根據(jù)用戶興趣，探索時效隨時間衰退特征，是提高時效量化在推薦系統(tǒng)中實用價值的主要途徑.

基于此，提出一種應(yīng)用遺忘曲線的協(xié)同過濾推薦模型(FC-CFRM:forgetting curve based collaborative filter recommendation model).該模型從用戶興趣漂移角度揭示資源時效遺忘速率的差異化規(guī)律，通過多階段時效量化方法和時間單位映射函數(shù)，計算具有記憶特征的歷史信息時效值，為合理量化歷史信息時效和提高推薦效果提供基礎(chǔ).

1 推薦模型

FC-CFRM 可定義為 6 元組 ＜U，O，R，P，δ，f＞.其中，U={ui}，表示用戶集合;O={oj}表示資源集合;R={ri，j}表示用戶ui對資源oj的使用評價信息;P={pj(t，k)}表示不同資源的時效量化函數(shù)，pj(t，k)?［0，1］，t表示當(dāng)前時間步，k 控制時效隨時間衰減的遺忘速率;δ稱為惰性更新因子，δ越大，同一階段用戶反饋對遺忘速率調(diào)整越小;f為效用函數(shù)，也稱推薦預(yù)測函數(shù)，用于計算用戶對于未知資源的推薦值，即f:U×O×T→R.FC-CFRM的目的是找到那些推薦值最高的資源形成評價列表L.例如:針對用戶ui，如果令其評價過的資源集合為O*，max為最大值函數(shù)，則推薦列表L的形式化表述為

FC-CFRM具體執(zhí)行過程分為2個階段:相似度計算和評價預(yù)測.

1.1 相似度計算

根據(jù)用戶資源歷史評價信息，相似度計算用于確定不同資源之間的相似程度，為后續(xù)評價預(yù)測提供基礎(chǔ).常見的相似度計算方法包括:類歐式距離法，條件概率法和皮爾森法.

1.1.1 類歐式距離法

將資源看作是用戶評價流形子空間中的點，資源間相似程度由點間距離決定.點間距離越大，相似度越低.如果令U(a，b)表示同時參與評價資源oa和ob的用戶集合，則類歐式距離法計算過程表示為

1.1.2 條件概率法

將資源相似程度看作是在某一資源受到指定用戶評價的條件下，另一資源也同時受到該用戶評價的概率p(oa|ob).如果令Freq(oa)和Freq(oa，ob)分別表示資源oa的評價用戶數(shù)和同時評價資源oa和ob的評價用戶數(shù)，則條件概率法的計算過程表示為

1.1.3 皮爾森法

皮爾森法采用數(shù)理統(tǒng)計的思想，將資源評價看作是同一樣本空間中，重復(fù)實驗下的抽樣結(jié)果.如果令r和r分別表示資源o和o資源所得到用ab戶平均評分，U(a，b)定義同類歐式距離法，則皮爾森法的計算過程表示為

與其他相似度計算方法相比，皮爾森法具有最佳的線性逼近程度，能夠應(yīng)對“分?jǐn)?shù)膨脹”和“分?jǐn)?shù)貶值”問題.

實際中，采取何種資源相似度計算方法依賴于推薦系統(tǒng)評價數(shù)據(jù)集特征.

1.2 評價預(yù)測

評價預(yù)測(效用函數(shù)f)根據(jù)相似度計算結(jié)果，對與未知評價資源oj相似的所有資源進(jìn)行評價值聚合運算，從而得到指定用戶ui對oj的評價預(yù)測值.考慮到資源歷史評價信息的時效特征，引入時效量化函數(shù)后的評價預(yù)測方法表示為

式中:O＇表示用戶ui評價過且與oj相似的資源集合;r表示這|O＇|個資源的歷史評價的平均值;pa(t，k)根據(jù)不同時間步t和控制參數(shù)k，量化oa歷史評價的時效值;pa(t，k)是模型的研究重點.

2 資源時效量化方法

德國心理學(xué)家艾賓浩斯采取無意義音節(jié)作為材料，以重學(xué)法揭示遺忘過程中，記憶時效隨時間變化特征，如圖 1［11］所示.

在推薦系統(tǒng)中，指定資源的評價信息反映了用戶對該資源的主觀認(rèn)可程度.這種主觀認(rèn)可程度必然隨時間發(fā)生與遺忘過程類似的衰減情況.同時，根據(jù)記憶心理學(xué)研究成果，不同的記憶源存在遺忘衰減程度差異，用戶感興趣的記憶材料更容易被記牢.這與推薦系統(tǒng)中不同資源存在時效衰減差異的要求相同.基于此，將描述記憶特征的遺忘曲線作為衡量資源的時效變化基礎(chǔ)，具有一定實際性和參考性.

圖1 遺忘過程遺忘曲線Fig.1 Time-utility Curve of forgetting procedure

本節(jié)首先獲得遺忘曲線的基本量化函數(shù)，該函數(shù)體現(xiàn)出單個階段內(nèi)時效隨時間變化趨勢.然后，根據(jù)用戶反饋，動態(tài)調(diào)整時效衰減程度，確定任意時刻擬合用戶興趣的多階段時效量化方法.最后，設(shè)計時間單位映射函數(shù).

2.1 單階段時效量化方法

如果將當(dāng)前時效發(fā)生體看成一個信息量儲藏室，初始時效性作為該室的輸入，則根據(jù)遺忘特征，資源歷史評價信息的時效保持量為時間步t的函數(shù)pa(t，k)，其中k用于控制時效的遺忘速率，該過程如圖2所示.

圖2 記憶的一室模型Fig.2 One-compartment model of memory

將圖2的動態(tài)過程轉(zhuǎn)換為微分方程形式，表示為

求解式(6)的原函數(shù) pa(t，k)，表示為

式中:t∈(0，∞)，表示的遺忘曲線應(yīng)取坐標(biāo)系第一象限;p0為該曲線在y軸上的截距，即時效的初始值，由于被試材料的初始記憶時效值均從100%開始進(jìn)行衰退，故取p0=1.

根據(jù)上述參數(shù)設(shè)定，資源oa的單階段時效量化方法以式(8)為基礎(chǔ)，根據(jù)當(dāng)前時間步t及遺忘速率k獲得資源歷史評價信息的時效值.

式中:遺忘速率k是反映資源遺忘曲線衰減差異的主要參數(shù).在后續(xù)內(nèi)容中，將根據(jù)用戶興趣漂移，動態(tài)學(xué)習(xí)式(8)中k的數(shù)值，建立時效多階段量化方法.

2.2 多階段時效方法

本節(jié)根據(jù)憶心理學(xué)中記憶加強(qiáng)現(xiàn)象，將控制參數(shù)k的確定方法理解為多個階段的遺忘曲線的調(diào)整過程.

針對同一被試資料，記憶加強(qiáng)是指經(jīng)過學(xué)習(xí)，記憶出現(xiàn)階躍(恢復(fù)完全記憶)并產(chǎn)生具有更低遺忘速率的新階段遺忘過程.如果令t1、t2和t3分別表示發(fā)生3次重新學(xué)習(xí)的時間步，則遺忘曲線調(diào)整過程如圖3所示.

圖3 多階段遺忘曲線調(diào)整Fig.3 Curve update in multiple procedures

圖3可看作是由用戶興趣變化而導(dǎo)致的遺忘速率動態(tài)調(diào)整過程.如果令tn－1和tn為遺忘曲線發(fā)生記憶加強(qiáng)現(xiàn)象的任意相鄰時間步，kn－1為遺忘曲線從tn－1到tn的遺忘速率，則對于資源oa，表示該遺忘階段的時效量化函數(shù)表示為式中:還需進(jìn)一步確定kn－1的學(xué)習(xí)策略.根據(jù)推薦系統(tǒng)的實際運行特征，將用戶反饋作為刺激遺忘速率發(fā)生改變的基本因素.

為便于分析相鄰階段遺忘曲線的調(diào)整方式，將遺忘速率調(diào)整后的新遺忘曲線向x軸反向平移，使之與原遺忘曲線具有共同起點.令調(diào)整前后的遺忘速率分別為kn－1和kn，則上述操作過程如圖4所示.

圖4 時效遺忘速率調(diào)整分析Fig.4 Analysis of forgetting-ratio update

在圖4中，根據(jù)用戶評價反饋，發(fā)生曲線遺忘速率調(diào)整.若令β表明在時間步tn時新舊遺忘曲線的衰退差異，則根據(jù)式(9)，β的數(shù)值大小表示為

化簡式(10)，由β建立kn－1和kn的數(shù)值關(guān)系，表示為

式中:(1－pa(tn，kn－1))為遺忘曲線在時間步tn時β取值的上限.為控制每次用戶反饋對曲線的調(diào)整程度，將(1 －pa(tn，kn－1))劃分為 δ個線段，調(diào)整程度β與時效保持程度的量化關(guān)系表示為

在推薦系統(tǒng)中，δ可設(shè)定為一個大于1的正整數(shù).將式(12)代入式(10)，消去β，得到的kn的計算公式，表示為

式中:遺忘速率的調(diào)整過程呈現(xiàn)遞歸關(guān)系，如果令初始遺忘速率為k0，結(jié)合式(9)和式(13)，可確定資源歷史評價信息在多階段遺忘過程中任意時刻的時效量化函數(shù)，從而滿足評價預(yù)測過程中相關(guān)要求.

2.3 時間單位映射函數(shù)

“時間步”是實際時間單位的一種離散化表示，常用于研究與時間特征耦合的系統(tǒng)中.在將系統(tǒng)付諸實踐時，需根據(jù)系統(tǒng)應(yīng)用背景，設(shè)計實際系統(tǒng)時間到時間步的時間單位映射函數(shù).

考慮到不同時間單位在時效量化方面的等價性，設(shè)計線性函數(shù)將系統(tǒng)時間“毫秒”映射到FCCFRM所能夠識別的時間步.時間單位映射函數(shù)的構(gòu)造過程為

1)針對單階段時效量化函數(shù)，當(dāng)pa(t，k)∈(0，1］時，f需滿足從系統(tǒng)時間 T:［0，∞)到時間步t:［0，∞)的一一映射，表示為

2)根據(jù)式(3)，當(dāng) pa(t?，k)=0.1 時，表明當(dāng)前時間步該評價記錄已基本喪失推薦效用，如果時效繼續(xù)下降，則對該記錄的時效量化過程無任何實際意義.基于此，在式(3)中引入臨界時間步 t?，表示為

如果用T?表示t?對應(yīng)的臨界系統(tǒng)時間，則結(jié)合式(15)，式(14)可進(jìn)一步表示為

根據(jù)式(16)，單階段時效量化方法的時間單位映射函數(shù)可表示為

3)針對多階段時效量化方法，將遺忘速率km代入式(15)求.根據(jù)線性函數(shù)的等價特性，利用式(17)已確定的函數(shù)形態(tài)求遺忘速率km下對應(yīng)的，表示為

式中:k0表示初始遺忘速率，ΔT表示當(dāng)前系統(tǒng)時間距上一次用戶反饋的系統(tǒng)時間增量.

3 仿真分析

3.1 數(shù)據(jù)準(zhǔn)備

將推薦系統(tǒng)中經(jīng)典的數(shù)據(jù)集MovieLens［4］用于仿真分析.MovieLens由真實網(wǎng)絡(luò)中71 567個用戶對10 681個不同電影所進(jìn)行的超過10 000 000條評價組成.每一條評價記錄包括用戶標(biāo)識，電影標(biāo)識，評價數(shù)值和時間戳.為驗證FC-CFPM系統(tǒng)的推薦效果，取原始數(shù)據(jù)集中前10 000條時間相鄰的資源歷史評價信息為初始仿真數(shù)據(jù)集.采用交叉驗證的方式將初始實驗數(shù)據(jù)集分成訓(xùn)練集和測試集，劃分百分比為0.2，即8 000條訓(xùn)練數(shù)據(jù)和2 000條測試數(shù)據(jù).其中，訓(xùn)練集用于獲取資源歷史評價信息的遺忘速率，測試集將根據(jù)訓(xùn)練得到的時效分析結(jié)果進(jìn)行評價預(yù)測.

測試過程采取增量學(xué)習(xí)的方法，其過程為:根據(jù)測試記錄中資源標(biāo)識，獲取該資源的時效遺忘速率，并根據(jù)系統(tǒng)時間差，計算時效數(shù)值進(jìn)行推薦.當(dāng)推薦結(jié)束后，針對該記錄反饋的資源進(jìn)行遺忘速率的調(diào)整，同時，將評價預(yù)測后測試記錄移入訓(xùn)練集的末尾，為后續(xù)推薦過程中計算資源間相似度提供基礎(chǔ).

平均絕對誤差(mean absolute error，MAE)作為衡量FC-CFPM在不同實驗中推薦效果，其計算方法如式(20)所示.其中，b(n)表示推薦系統(tǒng)計算得到的預(yù)測數(shù)值，bp(n)表示根據(jù)用戶反饋得到的真實評價值.MAE體現(xiàn)推薦預(yù)測值與實際用戶反饋值之間的平均差異.顯然，MAE的值越小，說明推薦系統(tǒng)的評價預(yù)測效果越優(yōu)秀.

3.2 參數(shù)設(shè)定

表1 參數(shù)設(shè)定Table 1 Setting of parameters

k0的數(shù)值在仿真過程中會發(fā)生動態(tài)調(diào)整，僅需設(shè)定初值即可.

3.3 惰性因子δ取值分析

惰性因子δ用于控制遺忘速率調(diào)整程度.δ越大，用戶評價反饋對該資源的時效遺忘速率更新效果越不明顯.惰性因子δ的取值無法同其他系統(tǒng)參數(shù)一樣，或通過計算訓(xùn)練集上相關(guān)統(tǒng)計特性獲取，如初始臨界時間，或通過訓(xùn)練過程動態(tài)調(diào)整.基于此，在惰性因子δ取10、20、50和100的基礎(chǔ)上，運行FC-CFRM，根據(jù)MAE結(jié)果，確定δ的合理取值，仿真結(jié)果如圖5所示.

圖5 δ取值對推薦效果影響Fig.5 Effects of various values ofδ on recommendation

圖5中，每條曲線表示不同δ取值下FC-CFRM的10次分段MAE采樣情況，分段長度為200.根據(jù)采樣結(jié)果，F(xiàn)C-CFRM在不同測試記錄分段上的MAE變化趨勢相同，數(shù)值上呈現(xiàn)波動狀態(tài).

其中，δ=10的MAE數(shù)值僅在第1 200～1 400條測試記錄上與其他實驗結(jié)果相當(dāng)(MAE=0.848 17)，在其他數(shù)據(jù)分段上，均具有較高的MAE值，表現(xiàn)為更差的推薦效果.

當(dāng)δ=20、50、100時，MAE在不同數(shù)據(jù)分段下的差異最大值為0.014 8，位于δ=20和δ=100的第1 600～1 800條記錄上，最小值為0.009，位于取20和50的曲線的第800～1 000條記錄上，均值為0.000 312.對 δ=20、50、100 的 MAE 曲線采取線性擬合方式做相似度分析，其擬合后的直線基本吻合.

基于上述分析，當(dāng)惰性因子δ取大于10的正整數(shù)時，F(xiàn)C-CFRM的推薦效果不因δ取值的改變而出現(xiàn)較大的波動.在后續(xù)試驗中，采用δ=50.

3.4 推薦效果對比分析

推薦效果對比分析用于衡量不同模型在測試集上推薦效果.實驗中所采取的對比方法包括:缺乏考慮資源歷史評價信息時效性的經(jīng)典協(xié)同過濾推薦模型(N-CFRM)［5］，采取簡單指數(shù)k=1時效量化的協(xié)同過濾推薦模型(E-CFRM)，基于機(jī)械遺忘曲線時效量化的協(xié)同過濾推薦模型(F-CFRM)［14］，基于遺忘曲線的協(xié)同過濾推薦模型(FC-CFRM).推薦效果分析利用式(21)計算其他推薦模型*-CFRM與N-CFRM的MAE差異程度，若該值為負(fù)數(shù)，說明其推薦效果較N-CFRM更差.反之，若該值為正數(shù)且其值越大，則推薦效果越優(yōu).實驗結(jié)果如圖6所示.

圖6 推薦效果對比分析Fig.6 Comparison analysis of effect of recommendation

在圖6中，每一分段中包含了3種推薦模型與N-CFRM的MAE差異程度，分段長度為200.總體上，所有推薦模型的推薦誤差度在不同分段數(shù)據(jù)集上呈現(xiàn)出波動狀態(tài).其中，E-CFRM有7個正數(shù)分段，3個負(fù)數(shù)分段.F-CFRM有8個正數(shù)分段，2個負(fù)數(shù)分段.FC-CFRM全部為正數(shù)分段.針對每一種推薦模型，表明其具體推薦效果的MAE統(tǒng)計特征量如表2所示.

表2 MAE統(tǒng)計分析Table 2 Statistic analysis of MAE

根據(jù)表2，各推薦方法的平均推薦效果排序:E-CFRM＜N-CFRM＜F-CFRM＜FC-CFRM.穩(wěn)定性排序:F-CFRM＜E-CFRM＜N-CFRM＜FC-CFRM.

由于E-CFRM采取人工方式設(shè)定指數(shù)函數(shù)的遺忘速率，忽略用戶興趣對不同資源在時效量化的影響，導(dǎo)致無論在推薦效果和推薦穩(wěn)定性方面，均比N-CFRM表現(xiàn)更差.

從F-CFRM的實驗結(jié)果上看，采取遺忘曲線能夠較好的擬合資源時效隨時間變化情況，表現(xiàn)為推薦平均效果較N-CFRM有所提高，但其忽略了資源時效量化存在多階段遺忘過程的特征.在用戶興趣發(fā)生變化時，F(xiàn)-CFRM的推薦效果會出現(xiàn)較大波動，即推薦過程不可控現(xiàn)象.

基于上述分析:FC-CFRM能夠采取合理的歷史信息時效量化模型，跟蹤用戶興趣變化，動態(tài)調(diào)整資源歷史評價信息的時效遺忘速率，提供穩(wěn)定且質(zhì)量較高的推薦效果.

4 結(jié)束語

針對歷史評價時效特征，提出一種用遺忘曲線協(xié)同過濾推薦模型.實驗結(jié)果表明，與其他推薦模型相比，模型能夠合理揭示遺忘速率隨用戶興趣的變化規(guī)律并提供穩(wěn)定且質(zhì)量較高的推薦效果.

現(xiàn)有推薦系統(tǒng)將用戶評價作為衡量資源效用的唯一標(biāo)準(zhǔn)，缺乏對環(huán)境等其他因素的考慮.當(dāng)推薦對象為具體網(wǎng)絡(luò)資源時，環(huán)境等因素往往更能夠反映資源實際運行狀態(tài).在后續(xù)研究中，擬將時效量化與多屬性評價相結(jié)合，設(shè)計具有時效特征的多屬性協(xié)同過濾推薦系統(tǒng).

［1］許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究［J］.軟件學(xué)報，2009，20(2):350-356.XU Hailing，WU Xiao，LI Xiaodong，et al.Comparison study of internet recommendation system ［J］.Journal of Software，2009，20(2):350-356.

［2］董麗，刑春曉，王克宏.基于不同數(shù)據(jù)集的協(xié)同過濾算法評測［J］.清華大學(xué)學(xué)報:自然科學(xué)，2009，49(4):590-594.DONG Li，XING Chunxiao，WANG Kehong.Based on different data sets of evaluating collaborative filtering algorithms［J］.Journal of Tsinghua University，2009，49(4):590-594.

［3］FOLDBERG D，NICHLOSD，OKIB M，et al.Using collaborative filtering to weave an information tapestry［J］.Communications of ACM，1992，35(12):61-70.

［4］KONSTAN J A，MILLER B N，MALTZ D，et al.Grouplens:applying collaborative filtering to usenet news［J］.Communications of the ACM，1997，40(3):77-87.

［5］PARK S，PENNOCK D.Applying collaborative filtering techniques to movie search for better ranking and browsing［C］//Proceedings of the 13th Association for Computing Machinery Special Interest Group on Knowledge Discovery in Data.San Jose，California，USA，2007:550-559.

［6］孫超.基于Agent的推薦技術(shù)的研究與應(yīng)用［D］.大連:大連海事大學(xué)，2009:35-37.SUN Chao.Research and application of recommendation technologies based on agent［D］.Dalian:Dalian Maritime University，2009:35-37.

［7］KOYCHEV I，SCHWAB I.Adaptation to drifting user’s interests［C］//Proceedings of ECML 2000 Workshop:Machine Learning in New Information Age.Barcelona，Spain，2000:39-46.

［8］KUKAR M，LJUBLJANA S.Drifting concepts as hidden factors in clinical studies［C］//Artificial Intelligence in Medicine 9th Conference on Artificial Intelligence in Medicine in Europe(AIME 2003).Protaras，Cyprus，2003:355-364.

［9］YIDing，XUE Li.Time weight collaborative filter［C］//Proceedings of the 14th ACM International Conference on Information and Knowledge Management CIKM’05.Bremen，German，2005:485-492.

［10］KATAKISG，TSOUMAKAS，VLAHAVAS I.An ensemble of classifiers for coping with recurring contexts in data streams［C］//Proceedings of the Conference on ECAI 2008:18th European Conference on Artificial Intelligence.Patras，Greece，2008:763-764.

［11］HERMANN E.Memory:a contribution to experimental psychology［EB/OL］.［2011-12-09］.http://psy.ed.asu.edu/～ classics/Ebbinghaus/index.htm.