基于記憶曲線的數(shù)據(jù)密集型動態(tài)用戶行為建模*

尹子都，岳　昆+，武　浩，付曉東，劉惟一

1.云南大學 信息學院，昆明 650504

2.昆明理工大學 信息工程與自動化學院，昆明 650504

基于記憶曲線的數(shù)據(jù)密集型動態(tài)用戶行為建模*

尹子都1，岳昆1+，武浩1，付曉東2，劉惟一1

1.云南大學 信息學院，昆明 650504

2.昆明理工大學 信息工程與自動化學院，昆明 650504

分析用戶行為的歷史數(shù)據(jù)，使用特定方法建立用戶的偏好模型，是目前研究的熱點和關鍵?？紤]了數(shù)據(jù)產(chǎn)生的時序特征，以及具有時間特征的變量在用戶行為模型中的影響，以心理學中的記憶曲線模型為依據(jù)，從用戶的行為數(shù)據(jù)出發(fā)，給出了用戶偏好的表示，并為用戶的每個偏好建立一個記憶曲線模型，實時地表示用戶的偏好。針對海量的用戶行為數(shù)據(jù)，提出了基于MapReduce的模型參數(shù)增量更新算法和動態(tài)用戶偏好計算方法，從而使得模型能反映動態(tài)變化的用戶偏好。建立在真實數(shù)據(jù)上的實驗結果表明，提出的模型和算法具有高效性、正確性和可用性。

動態(tài)用戶行為模型；用戶偏好；記憶曲線；增量更新；MapReduce

1　引言

自媒體的產(chǎn)生與云計算的成熟，使用戶在互聯(lián)網(wǎng)中的作用不斷提升。用戶的行為會產(chǎn)生大量數(shù)據(jù)，獲取和分析這些用戶行為數(shù)據(jù)能得到用戶個人信息，可用于推薦、行為評判和預測等多個方面，因此以用戶行為數(shù)據(jù)為核心的應用越來越多，基于云計算的“數(shù)據(jù)即服務”也日益流行[1]。用戶偏好的表示與建模是數(shù)據(jù)分析的重點與研究的核心，用戶偏好可理解為用戶想與之交互或已經(jīng)交互的對象，如某個商品、某條廣告或某種言論等，而交互可以是用戶的點擊、評論、購買與關注等，統(tǒng)稱用戶行為。分析用戶行為的歷史數(shù)據(jù)，使用特定的方法建立用戶的偏好模型（也稱用戶行為模型），成為當前研究的熱點和相關應用的基礎。

經(jīng)典的用戶建模方法中，研究人員用形式化的結構表達用戶偏好，將用戶的偏好表示為對商品或新聞的喜好程度的向量[2-3]，從而方便計算和處理。但是，這些方法往往基于一段時間內的用戶行為數(shù)據(jù)來構建用戶偏好模型，不區(qū)分數(shù)據(jù)生成的時間先后，對表達時間變量的影響關注較少。為了合理地表達時間特征，動態(tài)地反映用戶的偏好，已有越來越多的研究關注基于帶有時間特征的用戶行為數(shù)據(jù)來構建用戶行為模型。例如，Marin等人[4]利用用戶的交互行為，提出反饋型的用戶偏好模型，偏好隨用戶的交互行為改變，并提出一種自動檢測相關參數(shù)準確性的方法。Hawalah等人[5]提出一種動態(tài)表示用戶偏好的方法，考慮用戶偏好隨時間推移所產(chǎn)生的消減和去除特性，用Sugiyama等人[6]提出的方法給出用戶偏好的動態(tài)變化過程，這一思路為本文動態(tài)用戶行為模型的研究提供了參考。然而，鑒于數(shù)據(jù)本身不確定性、隨時間變化的特點，從帶有時間特征的數(shù)據(jù)出發(fā)的用戶行為模型要實現(xiàn)用戶偏好的合理表達，仍存在如下挑戰(zhàn)：

（1）用戶的偏好往往會隨著時間的推移而不斷變化，并且往往呈現(xiàn)出一定的規(guī)律，因此需要構建一個合理的模型來反映用戶偏好隨時間變化的特征。

（2）隨著用戶行為數(shù)據(jù)的不斷產(chǎn)生，需要根據(jù)新產(chǎn)生的數(shù)據(jù)，以增量的方式更新現(xiàn)有模型中的參數(shù)，使其能較好地反映新產(chǎn)生的數(shù)據(jù)對模型的影響。

（3）大量的用戶產(chǎn)生海量的行為數(shù)據(jù)，需要采用有效的數(shù)據(jù)密集型計算策略對這些海量行為數(shù)據(jù)進行處理分析，進而實現(xiàn)前述（1）和（2）中動態(tài)偏好的建模與增量更新。

針對用戶偏好隨著時間不斷變化的特征，邢春曉等人[7]為了及時反映用戶興趣變化，提出了基于時間和資源的數(shù)據(jù)權重，以及基于資源的協(xié)同過濾推薦算法。該方法考慮用戶偏好隨時間呈線性變化的情形，反映了用戶偏好建模中的時間特征。事實上，從心理認知角度，用戶偏好反映了其對特定對象（如商品、新聞和博客等）的欲望。已有研究針對用戶的心理特性，得出了用戶行為的特點以及用戶偏好隨時間變化的一般規(guī)律。例如，Khader等人[8]指出人的判斷大多基于記憶而得出，偏好作為人對事物的判斷同樣基于記憶，即記憶的變化將導致偏好的變化，且這種變化未必呈線性趨勢。由此，本文借鑒用戶心理與記憶描述及建模機制，討論從海量的行為數(shù)據(jù)中發(fā)現(xiàn)體現(xiàn)用戶心理特性的偏好模型及其增量更新機制。

艾賓浩斯記憶遺忘曲線（也稱記憶曲線）模型考慮用戶自然遺忘的客觀規(guī)律[9]，近年來被廣泛用于數(shù)據(jù)分析領域，涉及協(xié)同過濾與推薦[10-11]、機器學習[12]和圖/網(wǎng)絡[13-15]等方面。特別地，在基于記憶曲線的用戶偏好建模方面，于洪等人[10]提出基于遺忘曲線的協(xié)同過濾推薦算法，根據(jù)記憶曲線將用戶偏好分為長期和短期偏好，從而匹配不同用戶間的偏好，進而完成協(xié)同過濾任務。印桂生等人[11]建立了遺忘曲線的協(xié)同過濾推薦模型。這些方法為基于記憶曲線的用戶偏好研究提供了參考，但是用戶的長期和短期偏好劃分并不容易，并且面向海量的用戶行為數(shù)據(jù)，這些方法仍需進一步擴展。

因此，針對挑戰(zhàn)（1）和（2），本文以記憶曲線為依據(jù)，從用戶行為數(shù)據(jù)出發(fā)，給出用戶偏好的表示，為用戶的每個偏好建立一個記憶曲線模型，實時地表示用戶的各個偏好。同時，針對新產(chǎn)生的用戶行為數(shù)據(jù)，本文提出了一種模型參數(shù)的增量更新方法，使新的模型能反映變化的用戶偏好。

MapReduce編程模型是眾所周知和業(yè)界公認的海量處理計算框架和編程模型[16-17]，近年來廣泛應用于用戶建模領域。例如，Liang等人[18]討論并提出了一種高效的基于MapReduce的并行用戶建模方法；Shmueli-Scheuer等人[12]提出一種基于MapReduce實現(xiàn)的從大規(guī)模數(shù)據(jù)中建立用戶行為模型的方法。因此，針對挑戰(zhàn)（3），為了對海量的用戶行為數(shù)據(jù)進行處理和分析，本文給出了基于MapReduce的參數(shù)增量更新和動態(tài)用戶偏好建模的算法。

為了測試本文方法的有效性，爬取了新聞網(wǎng)站Engadget中國版[19]的真實用戶行為數(shù)據(jù)，使用基于Hadoop的MapReduce數(shù)據(jù)密集型計算平臺，編程實現(xiàn)并測試了本文提出的模型與算法。實驗結果表明，本文方法具有高效性、正確性和可用性。

本文組織結構如下：第2章給出動態(tài)用戶行為模型的表示；第3章給出從用戶行為數(shù)據(jù)構建動態(tài)行為模型的算法；第4章給出實驗結果；第5章總結全文并展望將來的工作。

2　動態(tài)用戶行為模型的表示

2.1用戶行為數(shù)據(jù)

本文用U={u1,u2,…,un}表示用戶的集合，其中ui（1≤i≤n）表示第i個用戶。用戶ui的行為將以某個對象為目標，例如用戶瀏覽新聞時會將一個新聞對象作為瀏覽的目標，用戶評論時會將一個評論對象作為目標。針對目標對象集合，為了反映用戶偏好的特點，可使用分布式近鄰傳播聚類方法[20]（首先提取關鍵詞，再使用此聚類的方法將相似的對象歸為一類），并用一個代表性關鍵詞作為一類的標簽，從而得到由關鍵詞構成的標簽集合。例如，瀏覽新聞時每條新聞為一個對象，通過提取關鍵詞將相似的新聞歸為一類，并用其中一個關鍵詞作為這一類的標簽。用L={l1,l2,…,lm}表示用戶偏好標簽集合，其中l(wèi)j（1≤j≤m）為第j個標簽，表示用戶瀏覽對象的第j個類別。

本文將從用戶行為數(shù)據(jù)構建用戶偏好模型，用戶行為數(shù)據(jù)包含用戶、時間和偏好。

定義1（用戶行為數(shù)據(jù)）用戶的一條行為數(shù)據(jù)記錄Item可表示為{ui,TB,lj}，其中ui用以標識用戶，TB為瀏覽時刻，lj為用戶瀏覽的偏好對應的偏好標簽。

表1給出了定義1中用戶行為數(shù)據(jù)的示例。

Table 1　Example of user behavior data表1　用戶行為數(shù)據(jù)示例

2.2模型的基本思想

根據(jù)心理學相關研究，人對事物的遺忘過程可由記憶曲線模型描述，下面給出相關定義和概念。

定義2（記憶曲線模型）記憶曲線模型表示為[9]：

其中，Δx=x′-x，x′和x分別表示目標時刻和最近一次記憶對象的時刻；v為時刻x′的記憶強度，為正確記憶的信息占全部信息的比例；b為相對記憶強度（取正整數(shù)），長期記憶b值大于短期記憶的b值。

式（1）表示Δx隨著時間推移而增大，記憶的影響作用會下降，不同b值在區(qū)間[0,100]上的記憶曲線如圖1所示。Khader等人[8]指出人的偏好或判斷大多是基于記憶而得出的，不難看出，對于某個偏好而言，記憶過程可表達為偏好的強化過程；同時隨著記憶的衰減，用戶的偏好也會隨之遞減；偏好隨著?x的增加會下降，長期偏好與短期偏好的衰減速度不同，短期偏好對應短期記憶，較小的b值使偏好的影響作用下降較快；反之，長期偏好對應的b值較大，對應長期記憶，影響作用下降得慢。因此，將記憶對象與用戶的偏好進行類比，記憶曲線體現(xiàn)了用戶偏好隨著時間變化的動態(tài)性，可表示用戶偏好隨時間的衰減。

Fig.1　Forgetting curve with different b圖1　不同b值的記憶曲線

定義3（用戶行為模型）ui的用戶行為模型可表示為一個偏好的有序集合Pi={pi1,pi2,…,piz}，pij（1≤j≤z）表示ui的第j個偏好。pij可表示為一個五元組，其中l(wèi)為偏好標簽，x為最近一次用戶行為的時刻，b為相對記憶強度，c為用戶對偏好l的重復記憶次數(shù)，v為偏好l的影響作用（即偏好的強度），表達用戶某個時刻對偏好l的關注度。

定義3中的b和c值隨著用戶行為數(shù)據(jù)增長而動態(tài)更新，決定偏好變化速度的快慢，x和b用于生成用戶某個偏好的強度v，參數(shù)的計算將在第3章詳細討論。用戶行為模型的動態(tài)性包含如下兩個層面：（1）模型參數(shù)的動態(tài)性。偏好的記憶曲線模型中，參數(shù)會隨著用戶行為數(shù)據(jù)的增長而不斷改變，例如用戶的短期偏好可能隨著瀏覽行為逐漸成為長期偏好，使得b值增加，如圖2（a）所示。（2）偏好強度的動態(tài)性。當pia中的各個參數(shù)相對穩(wěn)定時，偏好強度的大小會隨著時間的推移逐漸衰減，若產(chǎn)生一個時間增量?x，則偏好的強度將從v變?yōu)関′（變化量為?v），如圖2（b）所示。第3章將分別討論參數(shù)b和v的計算方法。

Fig.2　Dynamic preference model圖2　動態(tài)偏好模型

3　動態(tài)用戶偏好模型的構建

3.1模型參數(shù)的增量計算

如前所述，模型的參數(shù)決定了用戶偏好變化的特點，針對新產(chǎn)生的用戶行為數(shù)據(jù)，需要更新用戶偏好的相關參數(shù)，為用戶每個偏好確定新的記憶曲線，并有效地區(qū)分用戶的長期或短期偏好，為個性化服務奠定基礎。為了表示用戶偏好本身的變化，本節(jié)討論動態(tài)用戶行為模型中參數(shù)b的增量更新方法，即根據(jù)新數(shù)據(jù)Itemnew={ui，TB，lj}，更新某個用戶ui對應的用戶偏好集Pi。用Label(pij)表示Pi中偏好pij的標簽，對于新的行為數(shù)據(jù)中所包含的用戶偏好lj，按照Pi中是否包含lj，可分為如下兩種情況：（1）不存在Label (pij)=lj，（2）存在Label(pij)=lj，分別對應初始情況和更新情況。下面分別討論這兩種情況下偏好模型參數(shù)的增量更新方法。

情況（1）：對于ui來說，新出現(xiàn)的偏好不在Pi中，因此首先根據(jù)定義3建立一個新增偏好的五元組，并根據(jù)Itemnew中的lj確定該五元組中各參數(shù)的值。x為Itemnew中的TB，c=1代表一次記憶行為，平均記憶強度B是由經(jīng)驗獲得的記憶曲線模型中b值的平均值，可在偏差較小的前提下表達大部分偏好的變化。根據(jù)實際中不同情形下偏好的強度可以對B賦予不同的值，一般地，若以“天”作為記憶強度的單位，B取值為10可以反映人對事物的平均記憶強度，因此也以此作為b的初值。

例如，從初始狀態(tài)開始，使用表1中記錄編號為1、2、4和6的4條記錄建立用戶u1、u2和u3的偏好模型，結果如表2所示。

情況（2）：由于偏好lj在Pi中已存在，增量更新的目標為pij中的b值，該參數(shù)受到以下兩方面因素的影響：一是偏好記憶的深刻程度。該因素與記憶強度成反比，表示長時間不發(fā)生某事還能回憶的能力，兩次成功回憶之間的時間間隔（TB-x）越大，這種能力越強，v衰減越慢，與v成反比，比例為k，實驗顯示k取1可以得到較好的結果。二是偏好重復記憶次數(shù)c。用戶對重復越多的事往往印象也越深，因此重復次數(shù)越多，c增加越多，且越傾向為長期偏好。以上兩方面的因素相互獨立，因此總的b值應為上述兩部分之和，給出如下更新b值的方法：

針對海量的用戶行為數(shù)據(jù)本文基于MapReduce給出增量更新算法。Map函數(shù)并行地選取每個用戶的行為記錄到一個單獨的集合；Reduce函數(shù)首先按照時間先后對輸入的用戶行為數(shù)據(jù)記錄列表進行排序，依次處理，每條記錄對應一個偏好類別，從Pi中查找相同類別的元組，判斷Pi與新數(shù)據(jù)Itemnew的關系，若沒有找到，則用initTuple函數(shù)向Pi中添加新的五元組，否則用updateTuple函數(shù)更新此元組中b、x和c的值。算法1給出了以上思想。

例如，對于表2中的用戶偏好，若新增表1中編號為3和5的兩條記錄，需要更新u1和u2的偏好。根據(jù)算法1，在用戶u1對應的P1中使用findByLabel函數(shù)查找對應偏好為“5”的元組，發(fā)現(xiàn)已有元組存在，再使用updateTuple函數(shù)對記憶重復次數(shù)加1，得到c值為2。接著計算兩次行為之間的時間差為3。最后根據(jù)式（2）計算1/exp(-3/10)+2，得到b值為3.3956。類似得到u2和u3的偏好，參數(shù)更新后的用戶行為如表3所示。

Table 3　User behaviors after updating variables表3　參數(shù)更新后的用戶行為

由算法1可得到動態(tài)用戶行為模型中的各參數(shù)，算法的時間復雜度取決于Reduce函數(shù)，每個Reduce函數(shù)處理一個用戶的行為數(shù)據(jù)集。其中For循環(huán)執(zhí)行次數(shù)為O(s)，排序時間復雜度為O(s lb s)，因此算法1的時間復雜度為O(s lb s)，s為用戶的行為數(shù)據(jù)記錄數(shù)。

3.2動態(tài)偏好計算

根據(jù)3.1節(jié)對參數(shù)的計算結果，當前用戶偏好的強度v由目標時刻距離上次用戶行為的時間長度決定。因此，以式（1）為基礎，給出用戶偏好強度的定義。

定義4（用戶偏好強度）目標時刻用戶偏好強度的定義如下：

其中：v表示當前時刻偏好強度的大小；TD表示目標時刻，是x之后的某個時刻。

可知，用戶的偏好強度在模型參數(shù)確定之后，會隨時間遞減，最終趨于0，代表用戶的某一偏好被遺忘而消失。算法2實現(xiàn)了從海量用戶行為數(shù)據(jù)動態(tài)獲取用戶的偏好強度，其基本思想如下：遍歷U并找到其中每個ui對應的Pi，計算Pi中每個元素的v值。具體而言，算法中的Map函數(shù)獲取用戶偏好集合，Reduce函數(shù)并行地計算Pi中的v值。

算法2的時間復雜度為O(s)，取決于Reduce函數(shù)，其中s為用戶的行為數(shù)據(jù)記錄數(shù)。

例如，基于算法2計算用戶偏好在2014-5-15時刻的強度。以計算p11為例，其最近一次用戶行為到此時刻的時間長度為15-7=8，再根據(jù)式（3）計算偏好的強度v=exp(-8/3.395 6)=0.094 7。同理計算其他用戶的偏好，如表4所示。

Table 4　User behaviors at 2014-5-15表4　2014-5-15時刻的用戶行為

動態(tài)用戶行為模型能表示偏好隨時間推移不斷變化的過程，體現(xiàn)偏好強度的動態(tài)性，并且模型的參數(shù)會根據(jù)新的行為數(shù)據(jù)不斷更新，體現(xiàn)參數(shù)的動態(tài)性，為個性化服務提供支持。

4　實驗結果

為了測試本文方法的有效性，從Engadget中國版[18]網(wǎng)站上隨機選取超過4 000名用戶，通過解析站內所有新聞頁面獲取用戶的評論信息。具體而言，收集了所有相關用戶從2014年1月1日到2015年5月1日共1 919 925條評論信息，作為本實驗中的用戶行為。實驗環(huán)境如下：1臺CPU主頻2.3 GHz，內存2 GB的機器作為主節(jié)點（NameNode），6臺CPU主頻3.4 GHz，內存 1 GB的機器作為計算節(jié)點（DataNode），路由器總帶寬450 Mb/s，基于此構建HadoopMapReduce環(huán)境。本文測試了所構建的動態(tài)用戶行為模型的有效性，以及算法1和算法2的執(zhí)行時間、加速比和并行效率。實驗中對每個指標取多次測試結果的平均值。

4.1模型有效性測試

為了測試所構建模型的有效性，本文將所提出的動態(tài)用戶行為模型用于新聞推送。從歷史行為數(shù)據(jù)中計算得到的用戶行為，若偏好pij中的v大于給定閾值，則將l類的新聞推送給用戶ui；若用戶點擊瀏覽了推送的新聞，說明新聞推送成功。

本文使用50 000條用戶行為數(shù)據(jù)，70%用于建模，30%用于測試，對查準率（Precision）、查全率（Recall）和F值[21]進行了測試。為了對用戶偏好的建模及測試具有一致性，選取整段時間內對新聞都進行了評論的用戶（即前70%建模數(shù)據(jù)和后30%測試數(shù)據(jù)中都涉及到的用戶），進而選取這些用戶的行為數(shù)據(jù)，并且給定用戶偏好強度閾值，因此實驗中用戶數(shù)約為350。首先，對傳統(tǒng)的用戶點擊模型（不基于用戶行為歷史數(shù)據(jù)，稱為“靜態(tài)模型”）、文獻[7]提出的基于線性權重函數(shù)的用戶模型（稱為“線性模型”）以及基于本文所提出模型（稱為“動態(tài)模型”）得到的新聞推送結果，針對查準率和查全率進行了比較。其中，查準率定義為基于用戶偏好成功推送的新聞數(shù)占為用戶推送新聞總數(shù)的比例；查全率定義為基于用戶偏好成功推送的新聞數(shù)與用戶實際瀏覽新聞總數(shù)的比例。由于各模型下得到的測試結果差距較大，本文對查準率和查全率取對數(shù)刻度，分別如圖3和圖4所示。由于用戶對新聞的海量評論信息本身具有稀疏性（即用戶往往評論了給定新聞頁面集合中一個較小的部分），基于不同模型得到的查全率和查準率都不高，圖3和圖4中的結果與這一實際情形相吻合。不難看出，動態(tài)模型的查全率與查準率均高于靜態(tài)模型，具有較高的新聞推送成功率。

Fig.3　Precision圖3　查準率

Fig.4　Recall圖4　查全率

接著，比較了靜態(tài)模型和動態(tài)模型在進行新聞推送時的F值，F(xiàn)值計算公式如下：

兩種模型下F值（對數(shù)刻度）的比較如圖5所示。可以看出，基于動態(tài)模型能得到與傳統(tǒng)靜態(tài)模型相同的穩(wěn)定性，但基于動態(tài)模型的F值明顯高于基于靜態(tài)模型的F值。F值可以反映在新聞推送中推送成功的程度，即使提升很小的幅度，都會對全體用戶帶來較大的影響，因此動態(tài)模型遠優(yōu)于靜態(tài)模型。

Fig.5　F score圖5　F值

4.2模型參數(shù)增量更新算法測試

本文使用855 MB、共7 679 700條用戶行為數(shù)據(jù)，在不同計算節(jié)點數(shù)情形下，對算法1的總執(zhí)行時間（簡稱執(zhí)行時間）進行了測試，結果如圖6所示?？梢钥闯?，算法1的執(zhí)行時間隨著測試數(shù)據(jù)集增長呈對數(shù)趨勢增長，且數(shù)據(jù)量越大，計算節(jié)點越多，算法1的優(yōu)勢越顯著。這說明算法1能針對海量用戶行為數(shù)據(jù)進行偏好模型參數(shù)的增量更新，具有較好的可擴展性。

Fig.6　AT ofAlgorithm1圖6　算法1的執(zhí)行時間

進一步，對4個計算節(jié)點下隨著數(shù)據(jù)量增加算法1中Map函數(shù)的執(zhí)行時間（MT）、Reduce函數(shù)的執(zhí)行時間（RT）以及算法1執(zhí)行時間（AT）進行了測試，結果如圖7所示。由于Hadoop平臺處理任務時性能存在波動性，從而可能導致算法執(zhí)行時間上的波動性（如圖7中數(shù)據(jù)量為153 MB時的情況）?？偟膩碚f，在絕大多數(shù)情形下，RT都大于MT。這說明算法1的執(zhí)行時間主要來自其中Reduce函數(shù)的執(zhí)行，與3.1節(jié)中的理論分析結論一致。

Fig.7　MT,RT andAT ofAlgorithm1圖7　算法1的MT、RT和AT

加速比（Speedup）是算法并行執(zhí)行時間與串行執(zhí)行時間的比值，算法1隨著測試數(shù)據(jù)集增大的加速比如圖8所示?？梢钥闯?，加速比隨著測試數(shù)據(jù)規(guī)模增加而增加，且逐漸接近理論最大值（機器數(shù)量），這進一步說明算法1具有較好的并行性和可擴展性。并行效率（parallel efficiency）是加速比與處理器數(shù)量的比值，算法1隨著測試數(shù)據(jù)集增大的并行效率如圖9所示?？梢钥闯?，并行效率隨著測試數(shù)據(jù)集增加而增加，并穩(wěn)定在0.8左右，這也說明算法1具有較好的并行性。

Fig.8　Speedup ratio ofAlgorithm1圖8　算法1加速比

Fig.9　Parallel efficiency ofAlgorithm1圖9　算法1的并行效率

4.3動態(tài)偏好計算算法測試

類似地，本文測試了算法2隨著測試數(shù)據(jù)集增加，在不同計算節(jié)點數(shù)情形下的執(zhí)行時間，如圖10所示?？梢钥闯?，在不同計算節(jié)點數(shù)下，算法2的執(zhí)行時間基本呈線性趨勢，與3.2節(jié)中的理論分析結論一致，且數(shù)據(jù)量越大，計算節(jié)點越多，算法2的優(yōu)勢越顯著。算法2執(zhí)行時的MT、RT和AT如圖11所示，與算法1的MT和RT相比較，雖然存在如前所述由于Ha-doop平臺的特點而存在執(zhí)行時間的波動性（如數(shù)據(jù)規(guī)模為390 MB時RT），絕大多數(shù)情形下MT和RT占AT的比例基本相同，這說明算法2的Map函數(shù)和Reduce函數(shù)的執(zhí)行時間相差不大，計算量基本相當。

Fig.10　AT ofAlgorithm2圖10　算法2的執(zhí)行時間

Fig.11　MT,RT andAT ofAlgorithm2圖11　算法2的MT、RT和AT

進一步，也測試了算法2隨著測試數(shù)據(jù)集增大的加速比和并行效率，分別如圖12和圖13所示?？梢钥闯?，加速比隨著計算節(jié)點增加而提升，計算節(jié)點數(shù)越多，加速比越高；但隨著數(shù)據(jù)量的提升，并行效率隨著計算節(jié)點數(shù)增加而逐漸提升。

Fig.12　Speedup ratio ofAlgorithm2圖12　算法2的加速比

Fig.13　Parallel efficiency ofAlgorithm2圖13　算法2的并行效率

5　結束語

本文針對用戶行為模型的動態(tài)性，基于記憶曲線模型，提出了一種從海量的用戶行為數(shù)據(jù)中構建用戶偏好模型的方法，并給出了基于MapReduce的算法，最后通過建立在真實數(shù)據(jù)上的實驗結果驗證了本文方法的高效性、可擴展性和有效性。本文的研究為針對帶有時間特征的用戶行為數(shù)據(jù)分析和偏好發(fā)現(xiàn)提供了一種思路，但作為這一問題的初步探索，針對一段時間內多個時間片的用戶行為模型構建、用戶不同偏好之間的聯(lián)系，仍需進一步研究，也是人們將要開展的工作。

References:

[1]Vu Q H,Pham T V,Truong H L,et al.DEMODS:a description model for data-as-a-service[C]//Proceedings of the 2012 IEEE 26th International Conference on Advanced Information Networking and Applications,Fukuoka,Japan,Mar 26-29,2012.Piscataway,USA:IEEE,2012:605-612.

[2]Zhang Yongzheng,Pennacchiotti M.Predicting purchase behavior from social media[C]//Proceedings of the 22nd International World Wide Web Conference,Rio de Janeiro,Brazil,May 13-17,2013.New York:ACM,2013:1521-1532.

[3]Pennock D,Horvitz E,Lawrence S,et al.Collaborative filtering by personality diagnosis:a hybrid memory-and modelbased approach[C]//Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence,Stanford,USA,Jun 30-Jul 3,2000.San Francisco,USA:Morgan Kaufmann Publishers Inc,2000:473-480.

[4]Marin L,Isern D,Moreno A.Dynamic adaptation of numer-ical attributes in a user profile[J].Applied Intelligence, 2013,39(2):421-437.

[5]Hawalah A,Fasli M.Dynamic user profiles for Web personalisation[J].Expert Systems with Applications,2015,42 (5):2547-2569.

[6]Sugiyama K,Hatano K,Yoshikawa M.Adaptive Web search based on user profile constructed without any effort from users[C]//Proceedings of the 13th International Conference on World Wide Web,New York,May 17-20,2004.New York:ACM,2004:675-684.

[7]Xing Chunxiao,Gao Fengrong,Zhan Sinan,et al.A collaborative filtering recommendation algorithm incorporated with user interest change[J].Journal of Computer Research and Development,2007,44(2):2547-2569.

[8]Khader P H,Pachur T,Meier S,et al.Memory-based decisionmaking with heuristics:evidence for a controlled activation of memory representations[J].Journal of Cognitive Neuroscience,2011,23(11):3540-3554.

[9]Ebbinghaus H.Memory:a contribution to experimental psychology[J].Annals of Neurosciences,1913,20(4):155-156.

[10]Yu Hong,Li Zhuanyun.A collaborative filtering recommendation algorithm based on forgetting curve[J].Journal of Nanjing University:Natural Science Edition,2010,46(5): 520-527.

[11]Yin Guisheng,Cui Xiaohui,Ma Zhiqiang.Forgetting curvebased collaborative filtering recommendation model[J]. Journal of Harbin Engineering University,2012,33(1):85-90.

[12]Shmueli-Scheuer M,Roitman H,Carmel D,et al.Extracting user profiles from large scale data[C]//Proceedings of the 2010 International Workshop on Massive Data Analytics over the Cloud,Raleigh,USA,Apr 26,2010.New York: ACM,2010:4.

[13]Feng Naiqin,Tian Yong,Wang Xianfang,et al.Logarithmic and exponential morphological associative memories[J]. Journal of Software,2010,33(1):157-166.

[14]Kudelka M,Horak Z,Snasel V,et al.Weighted co-authorship network based on forgetting[J].Future Information Technology:Communications in Computer and Information Science,2011,185:72-79.

[15]Ye Xiaoming,Lin Xiaozhu,Dai Xiaojuan.The ART2 network based on memorizing-forgetting mechanism[C]//LNCS 6675:Proceedings of the 8th International Symposium on Neural Networks,Guilin,China,May 29-Jun 1,2011.Berlin,Heidelberg:Springer,2011:60-67.

[16]Wang Shan,Wang Huiju,Qin Xiongpai,et al.Architecting big data:challenges,studies and forecasts[J].Chinese Journal of Computers,2011,34(10):1741-1752.

[17]Dean J,Ghemawat S.MapReduce:a fiexible data processing tool[J].Communications of theACM,2010,53(1):72-77.

[18]Liang H,Hogan J,Xu Y.Parallel user profiling based on folksonomy for large scaled recommender systems:an implementation of cascading MapReduce[C]//Proceedings of the 10th IEEE International Conference on Data Mining Workshops,Sydney,Australia,Dec 13,2010.Piscataway,USA: IEEE,2010:154-161.

[19]Engadget[EB/OL].(2015)[2015-06-28].http://cn.engadget. com/.

[20]Lu Weiming,Du Chenyang,Wei Baogang,et al.Distributed affinity propagation clustering based on MapReduce[J]. Journal of Computer Research and Development,2012,49 (8):1762-1772.

[21]Baeza-Yates R A,Ribeiro-Neto B.Modern information retrieval[M].[S.l.]:Addison Wesley,2011:75-79.

附中文參考文獻：

[7]邢春曉,高鳳榮,戰(zhàn)思南,等.適應用戶興趣變化的協(xié)同過濾推薦算法[J].計算機研究與發(fā)展,2007,44(2):296-301.

[10]于洪,李轉運.基于遺忘曲線的協(xié)同過濾推薦算法[J].南京大學學報:自然科學版,2010,46(5):520-527.

[11]印桂生,崔曉暉,馬志強.遺忘曲線的協(xié)同過濾推薦模型[J].哈爾濱工程大學學報,2012,33(1):85-90.

[13]馮乃勤,田勇,王鮮芳,等.對數(shù)-指數(shù)形態(tài)學聯(lián)想記憶[J].軟件學報,2010,33(1):157-166.

[16]王珊,王會舉,覃雄派,等.架構大數(shù)據(jù):挑戰(zhàn)、現(xiàn)狀與展望[J].計算機學報,2011,34(10):1741-1752.

[20]魯偉明,杜晨陽,魏寶剛,等.基于MapReduce的分布式近鄰傳播聚類算法[J].計算機研究與發(fā)展,2012,49(8):1762-1772.

YIN Zidu was born in 1990.He is a Ph D.candidate at Yunnan University.His research interests include knowledge representation and reasoning,massive data analysis and services.

尹子都（1990—），男，甘肅天水人，云南大學博士研究生，主要研究領域為知識的表示與推理，海量數(shù)據(jù)分析與服務。

YUN Kun was born in 1979.He received the M.S.degree in computer science from Fudan University in 2004,and the Ph.D.degree in computer science from Yunnan University in 2009.Now he is a professor and Ph.D.supervisor of Yunnan University,and the member of CCF.His research interests include massive data analysis and services.

岳昆（1979—），男，云南曲靖人，2004年于復旦大學獲得計算機碩士學位，2009年于云南大學獲得計算機博士學位，現(xiàn)為云南大學教授、博士生導師，CCF會員，主要研究為海量數(shù)據(jù)分析與服務。

WU Hao was born in 1979.He received the Ph.D.degree in computer science from Huazhong University of Science and Technology in 2007.Now he is an associate professor at Yunnan University.His research interests include information retrieval,recommendation system and service computing.

武浩（1979—），男，河南平頂山人，2007年于華中科技大學獲得計算機博士學位，現(xiàn)為云南大學副教授，主要研究領域為信息檢索，推薦系統(tǒng)，服務計算。

FU Xiaodong was born in 1975.He received the M.S.degree in computer science from Kunming University of Science and Technology in 2000,and the Ph.D.degree in management from Kunming University of Science and Technology in 2008.Now he is a professor at Kunming University of Science and Technology,and the senior member of CCF.His research interests include service computing and intelligent decision.

付曉東（1975—），男，云南鎮(zhèn)雄人，2000年于昆明理工大學獲得計算機碩士學位，2008年于昆明理工大學獲得管理學博士學位，現(xiàn)為昆明理工大學教授，CCF高級會員，主要研究領域為服務計算，智能決策。

LIU Weiyi was born in 1950.He graduated from Huazhong University of Science and Technology in 1976.Now he is a professor and Ph.D.supervisor at Yunnan University,and the senior member of CCF.His research interests include artificial intelligence,data and knowledge engineering.

劉惟一（1950—），男，云南昆明人，1976年畢業(yè)于華中科技大學，現(xiàn)為云南大學教授、博士生導師，CCF高級會員，主要研究領域為人工智能，數(shù)據(jù)與知識工程。

Data Intensive Modeling of Dynamic User Behaviors Based on Forgetting Curve*

YIN Zidu1,YUE Kun1+,WU Hao1,FU Xiaodong2,LIU Weiyi1
1.School of Information Science and Engineering,Yunnan University,Kunming 650504,China
2.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650504,China

E-mail:kyue@ynu.edu.cn

Analyzing historical user behavior data and establishing user preference model by some certain method is the critical subject with great attention.This paper considers the time series characteristics of data generation and the influence of the variables with temporal characteristics on user behavior models.Based on the forgetting curve in psychology,this paper starts from user behavior data and gives the representation of user p

.Thus,a forgetting curve model can be established for each preference and user preferences can be represented by real time manner. Aiming at massive user behavior data,this paper proposes the MapReduce-based algorithms for the incremental update of model parameters and the computation of dynamic user preferences.Thus,inherently dynamic user preferences can be reflected by the constructed user behavior model.The experimental results conducted on real data show that the proposed model and algorithms are efficient,correct and applicable.

dynamic user behavior model;user preference;forgetting curve;incremental update;MapReduce

用戶u 1u 2u 3偏好P1= { p11= <“i P h o n e”，2 0 1 4 -5 -4，1 0，1，0 >，p12= <“A M D顯卡”，2 0 1 4 -5 -6，1 0，1，0 > } P2= { p21= <“小米電視”，2 0 1 4 -5 -3，1 0，1，0 > } P3= { p31= <“智能手環(huán)”，2 0 1 4 -5 -9，1 0，1，0 > }

2015-08,Accepted 2015-11.

10.3778/j.issn.1673-9418.1508049

A

TP311

*The National Natural Science Foundation of China under Grant Nos.61472345,61163003,61462056,61562090(國家自然科學基金);the Natural Science Foundation of Yunnan Province under Grant Nos.2014FA023,2014FA028(云南省應用基礎研究計劃);the Yunnan Provincial Foundation for Leaders of Disciplines in Science and Technology under Grant No.2012HB004(云南省中青年學術和技術帶頭人后備人才培養(yǎng)計劃);the Program for Innovative Research Team in Yunnan University under Grant No.XT412011 (云南大學創(chuàng)新團隊培育計劃);the Program for Excellent Young Talents of Yunnan University under Grant No.XT412003(云南大學青年英才培養(yǎng)計劃).

CNKI網(wǎng)絡優(yōu)先出版:2015-12-02,http://www.cnki.net/kcms/detail/11.5602.TP.20151202.1349.002.html

YIN Zidu,YUE Kun,WU Hao,et al.Data intensive modeling of dynamic user behaviors based on forgetting curve.Journal of Frontiers of Computer Science and Technology,2016,10(10):1376-1386.