融合時序的決策樹推薦算法研究

徐志熹，錢洋，蘇揚

（1.四川省圖書館信息技術(shù)部，成都610015；2.電子科技大學(xué)計算機科學(xué)與工程學(xué)院，成都611731；3.電子科技大學(xué)外國語學(xué)院，成都611731）

0 引言

推薦算法[1]會通過對用戶畫像，發(fā)現(xiàn)用戶的喜好或偏好，找到內(nèi)容與用戶之間的深層聯(lián)系[2]，將與用戶有關(guān)系的內(nèi)容主動介紹給用戶。如何建立一套優(yōu)質(zhì)推薦模型使其能更快更準(zhǔn)地預(yù)測用戶對于某些內(nèi)容的偏好程度[3]是一項具有挑戰(zhàn)性的工作。

傳統(tǒng)的推薦算法思路[4-5]是在推斷用戶瀏覽過網(wǎng)頁中對象是偏好時，將用戶的所有歷史行為認(rèn)為有同樣重要性占比。對用戶在過去很久訪問的對象和最近訪問的對象，都是以同樣的權(quán)重來計算關(guān)聯(lián)矩陣[6-7]，最后得出的是用戶較長時間段里的平均興趣偏好。這類方法沒有考慮到用戶的興趣可能隨著時間的變化發(fā)生改變，其結(jié)果不能準(zhǔn)確地反映當(dāng)下用戶喜好，隨著時間跨度越大，偏差也會越大[8-10]，最終使得其推薦內(nèi)容無法滿足用戶需求。

本文提出的推薦算法考慮了時間變化的影響，加入用戶行為時序，構(gòu)建行為時序模型。通過收集用戶對推薦內(nèi)容的反饋，可實時更新用戶偏好，從而改善下一次推薦內(nèi)容。研究的主要內(nèi)容與創(chuàng)新點有：①融合用戶行為的時序?qū)τ脩羝玫挠绊?，提出時序模型；②采用機器學(xué)習(xí)方法，建立推薦內(nèi)容計算目標(biāo)函數(shù)；③使用決策樹和優(yōu)化損失函數(shù)更新預(yù)測參數(shù)。

1 用戶行為時序模型

將用戶的訪問過的項目和系統(tǒng)推薦給用戶的項目以時間順序排列記錄下來，通過對用戶訪問過和推薦過的項目序列進行計算，得到行為之間的關(guān)系值的大小和用戶與行為偏好值。

用戶在某n個連續(xù)時刻下有著如下的歷史行為序列Xi與X（ji≠j）可以是相同或者不同的訪問項目，形成時序項目集，即X1,X2,…，表示在n個時間窗口里用戶曾經(jīng)訪問過的項目。通過用戶的身份變化，當(dāng)前的行為特征以及對象關(guān)聯(lián)度權(quán)重矩陣計算出下一個能滿足用戶偏好的訪問項目Xn+1，并將它推薦給用戶。將用戶的歷史行為記錄存儲，推薦系統(tǒng)需要提取其中下每次向用戶推薦時間點的前幾次的用戶行為和推薦后的用戶行為。

對用戶的推薦作為用戶行為序列的預(yù)測，預(yù)測計算的目標(biāo)函數(shù)表示為：

其中Xn表示上一次推薦給用戶的項目,Xn+1表示下一個時刻給用戶的推薦項，表示通過用戶當(dāng)前的行為給出的推薦選項；Q1和Q2表示上次行為對當(dāng)前行為的影響參數(shù)。

2 基于決策樹的參數(shù)訓(xùn)練

2.1 模型概括

通常在推薦系統(tǒng)中，會有多種用戶參數(shù)作為推薦算法的輸入，針對公式（1），如何計算出最優(yōu)的Xn+1主要取決對于Q1和Q2的計算方法。首先構(gòu)造一顆決策樹，如圖1所示，采用多項指標(biāo)來判斷，參數(shù)Q1和Q2是否需要修改。在本文的圖書館導(dǎo)讀推薦系統(tǒng)中會采用如下幾個維度，分別是：用戶的角色變化，瀏覽行為的變化以及是否接受上次的推薦內(nèi)容。通過對系統(tǒng)已有數(shù)據(jù)的訓(xùn)練，可以得到如圖1所示的決策樹模型來計算 Q1和 Q2。

圖1 決策樹

2.2 預(yù)測參數(shù)更新

通過構(gòu)造關(guān)于用戶身份和行為的目標(biāo)函數(shù)記為：Id和Action來計算Q1和Q2，目標(biāo)函數(shù)記為：

其中，Id函數(shù)定義為：

Id函數(shù)主要是針對參數(shù)Q1來進行的決策判斷，主要依據(jù)是用戶角色屬性的是否有變化，在實際中用戶角色變化包括身份屬性的變化，用戶評分升級等都可以用來作為評估屬性。

目標(biāo)函數(shù)第二部分Action函數(shù)定義為：

R（An+1）采用協(xié)同過濾算法[12-14]計算所有項目兩兩之間的關(guān)系權(quán)重。最后對于參數(shù)Q1和Q2，分別對公式（3）求導(dǎo)可以得到預(yù)測參數(shù)的更新值。

通過計算得到的Q1和Q2，能夠作為下一次給用戶推薦所使用的更新參數(shù)。

3 實驗

實驗部分主要分為兩個部分，一個是本文所提出的算法和傳統(tǒng)算法在通用數(shù)據(jù)集上的對比；另一個部分是本文算法在四川省圖書館導(dǎo)讀系統(tǒng)中的推薦效果。

3.1 數(shù)據(jù)集實驗對比

實驗需要使用的數(shù)據(jù)集的兩個來源：Gowalla[15]、Last.fm[16]。Gowalla是一個基于位置的社交網(wǎng)站，用戶可以通過登錄來共享他們的位置。用戶友誼關(guān)系網(wǎng)絡(luò)是無向的，使用公共API收集，由196591個節(jié)點和950327條邊組成。在2009年2月至2010年10月期間，Gowalla總共收集了6442890個用戶的簽到。

數(shù)據(jù)集一共分成兩部分。第一部分loc-gowal?la_totalCheckins.txt文件中包含有用戶簽時產(chǎn)生數(shù)據(jù)段，內(nèi)容包括時間、地點、用戶的ID，總共有6,442,890條數(shù)據(jù)項；另一部分為loc-gowalla_edges.txt。Gowalla文件存儲有用戶的社會關(guān)系，該文件包含有196,591個用戶信息。Last.fm數(shù)據(jù)集收集了Last.fm網(wǎng)站上的上千名用戶的音樂鑒賞記錄信息，可以為研究者提供關(guān)于音樂推薦的數(shù)據(jù)集。該數(shù)據(jù)集記錄每一個用戶在網(wǎng)站中收聽過的藝術(shù)家以及他們的作品，提取了最受歡迎的藝術(shù)家和音樂播放次數(shù)。本文用每種數(shù)據(jù)中的70%的數(shù)據(jù)用戶訓(xùn)練，而剩下的30%的數(shù)據(jù)作為測試數(shù)據(jù)。所用到的篩選過后的數(shù)據(jù)如表1所示。

表1 實驗數(shù)據(jù)集

用于對比的傳統(tǒng)推薦算法包括：

隨機推薦法[17]：從距離用戶當(dāng)前時刻最近的多個訪問過的對象中隨機選擇一個項目推薦給用戶。

流行度推薦法[18]：根據(jù)每個項目的流行度，將所有項目按照大小排列，流行度的計算方法是ln（1+nv），nv為項目v的出現(xiàn)頻率。

Δtuv最近項目推薦法[17]：該方法假設(shè)最近被訪問過的項目有著更大的可能性再次被用戶訪問，需要使用指數(shù)最近性測量法e-Δtuv，是推薦的時間點和用戶u上次訪問項目v時間點的間隔。該推薦方法的計算主要基于加權(quán)項e-Δtuv。

協(xié)同推薦算法[19]：基于余弦相似度，計算公式（4），為用戶建立數(shù)學(xué)模型，找出與目標(biāo)用戶最近的鄰居用戶，推薦鄰居的偏好項目。

推薦準(zhǔn)確的評估需要用到平均正確率（Average Precision）的計算方法，首先定義對于用戶u的推薦出正確的項目的概率為：

其中，Rut是用戶u在t時刻的推薦組合。使用宏平均 MaAP（Macro-Average）和微平均 MiAP（Micro-Average）作為評估指標(biāo)[17]，MaAP衡量評估中全部正確推薦的分?jǐn)?shù)，而MiAP是評估中所有用戶的平均推薦準(zhǔn)確率，兩者主要區(qū)別在是否要考慮用戶序列長度的不均衡。

實驗結(jié)果的情況如圖2所示?；谟脩魰r序決策模型的推薦在Gowalla和Last.fm兩個數(shù)據(jù)集上使用MaAP和MiAP計算出的的測試準(zhǔn)確率都高于與之比較的基礎(chǔ)方法。Gowalla數(shù)據(jù)集中訪問序列的長度比Last.fm數(shù)據(jù)集更不均衡，MaAP計算出的結(jié)果中，基于用戶時序決策模型的推薦方法相對于基本方法準(zhǔn)確率提高的比率比MiAP的計算結(jié)果更高。

圖2 實驗結(jié)果對比

3.2 導(dǎo)讀系統(tǒng)推薦實驗

本文算法已應(yīng)用于四川省圖書館智能導(dǎo)讀系統(tǒng)，為用戶提供咨詢問題推薦，運行結(jié)果如圖3所示。在該系統(tǒng)中，推薦算法會根據(jù)用戶針對同類問題在歷史時序上進行模型構(gòu)造，訓(xùn)練出與歷史咨詢問題相關(guān)聯(lián)系較高的推薦列表。

圖3 導(dǎo)讀系統(tǒng)咨詢問題推薦實例

圖3 的問題推薦中，左圖（a）為第一次測試結(jié)果，用戶在反饋滿意后，該推薦系統(tǒng)在右圖（b）第二次測試同類問題時，給用戶提供的答案更聚焦“充電”，更準(zhǔn)確地為用戶提供答案。

4 結(jié)語

本文提出了用戶歷史行為對當(dāng)下行為的影響基礎(chǔ)上，提出了行為時序概念，從而構(gòu)建了時序模型，將到用戶的興趣可能會隨著時間發(fā)生偏移的問題，用系統(tǒng)與用戶交互的反饋結(jié)果來構(gòu)建決策樹模型，通過機器學(xué)習(xí)來實時學(xué)習(xí)用戶的動態(tài)興趣偏好這一目標(biāo)函數(shù)，讓算法結(jié)果更能匹配用戶的當(dāng)前狀態(tài)的偏好。本文所提出的算法，已在實際智能咨詢系統(tǒng)中運行，并取得了較好的實際效果。