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

徐志熹，錢洋，蘇揚

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

0 引言

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

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

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

1 用戶行為時序模型

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

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

對用戶的推薦作為用戶行為序列的預測，預測計算的目標函數表示為：

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

2 基于決策樹的參數訓練

2.1 模型概括

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

圖1 決策樹

2.2 預測參數更新

通過構造關于用戶身份和行為的目標函數記為：Id和Action來計算Q1和Q2，目標函數記為：

其中，Id函數定義為：

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

目標函數第二部分Action函數定義為：

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

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

3 實驗

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

3.1 數據集實驗對比

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

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

表1 實驗數據集

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

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

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

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

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

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

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

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

圖2 實驗結果對比

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

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

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

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

4 結語

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