基于時間因子的個性化新聞混合推薦研究

陶永才，火 昊，石 磊，衛 琳

1(鄭州大學 信息工程學院，鄭州 450001) 2(鄭州大學 軟件技術學院，鄭州 450002) E-mail：ieyctao@zzu.edu.cn

1 引 言

互聯網信息爆發式地增長給予信息科學挑戰，信息科學需要解決大量過載但又可能包含價值的信息，互聯網用戶每天被動地接收到大量質量參差不齊的新聞，個性化推薦成為了有效解決信息負載的手段，它可以通過分析用戶和待推薦的信息，根據用戶的興趣喜好，為用戶推薦符合其閱讀興趣的數據信息.

用戶的閱讀興趣受多方面因素影響，其中時間是一個不可忽略的因素，每個用戶都有其獨有的生活工作規律，受限于每個人固有的作息生活規律，用戶的閱讀習慣也有潛在的規則可以挖掘，譬如用戶在中午午休時間是不會理會系統推送的，而當晚上回家休息時，則會更多地閱讀輕松休閑的話題.如何挖掘出這些規律，配合改進的推薦算法為用戶推薦符合其閱讀興趣的新聞信息是本文研究的重點.

目前個性化推薦技術中協同過濾算法是推薦系統技術中應用最早也是最為成熟的技術[1].然而傳統的協同過濾技術并不能考慮到用戶隨著時間不斷變化的閱讀興趣，并且隨著新聞網站規模不斷擴大，用戶和新聞數量也不斷激增，導致推薦系統的效率和推薦質量嚴重下降.為了能準確預測用戶的興趣并產生高質量的推薦結果，本文研究基于時間因子的混合推薦算法(Hybrid news recommendation based on time factor，HTF)，該算法將基于內容的推薦和協同過濾推薦結合，同時考慮時間因子對用戶興趣分布的影響，按照時間分布規律生成更符合該用戶個性化需求的推薦列表，從而提高推薦精度.

2 相關工作

2.1 傳統推薦算法

本文研究的推薦算法HTF是基于內容的推薦和協同過濾相結合的混合推薦算法.混合推薦算法結合了基于內容的推薦和協同過濾推薦算法的優點，同時又規避了兩者的主要缺點，在現如今的推薦系統中得到了廣泛的應用.

基于內容的推薦[4,5]是根據用戶歷史閱讀記錄構造其興趣向量，然后將待推薦的信息跟用戶興趣向量進行相似性計算，經排序將相似度最高的Top-N條信息推薦給用戶.算法優點是：只需分析用戶的興趣向量，評分矩陣無稀疏性問題；推薦合情合理，均是按用戶的閱讀興趣推薦；對新加入的待推薦項目比較友好.算法缺點是：過度規范，不能挖掘用戶潛在的動態的興趣；新加入的用戶沒有數據就無法合理推薦.

典型的協同過濾技術是基于用戶的(user-based)，通過研究用戶興趣分布的相似性，將有相同興趣愛好的用戶閱讀內容作為推薦資源[6].算法優點是：不需要考慮待推薦內容形式，能對圖片、文字和音頻統一處理；能發現用戶的潛在興趣點.算法缺點是：稀疏性，系統規模擴大后，待推薦項目和新用戶激增，導致評分矩陣稀疏，影響算法效率；冷啟動，對新加入的待推薦項目和用戶無法合理分類推薦.

基于內容推薦和協同過濾相結合的混合推薦算法綜合以上兩種算法[2,3]，擁有兩者的優點：推薦精度高，善于發現用戶潛在興趣.但是也存在不足：未深挖用戶的隱藏興趣愛好.用戶在日常生活中有動態的閱讀習慣，這些習慣跟用戶的生活工作學習狀態等方方面面因素存在一定的關聯性，分析用戶在不同時間的不同閱讀習慣，能夠定制更加個性化的推薦內容.

2.2 推薦算法的研究現狀

目前國內在個性化推薦算法的研究中已經取得很高的成就，相關文獻中已提出較多的改進算法，文獻[7-16]分別選取不同的方法提高推薦結果的準確度.文獻[7]分別計算用戶及項目間的相似性，自適應地選擇合適對象作為預測對象的候選推薦，在候選推薦中計算選擇信任度高的子群，通過不確定近鄰的動態度量方法，對預測結果進行合理推薦.文獻[9]認為用戶閱讀興趣動態變化，需要實時分析用戶模型，以響應用戶實時、連續和個性化的服務請求.但是尚未有研究考慮將用戶的閱讀習慣跟時間聯系起來，分析用戶的閱讀興趣規律.針對這個問題，本文提出一種基于時間因素的個性化混合推薦算法HTF，抓取用戶在不同時間的閱讀行為，通過選取合適的文本分析和聚類算法得出包含時間因素的用戶興趣分布模型，讓推薦系統能夠在用戶不同的閱讀時間里推薦符合其習慣的內容，提高推薦精度.

3 基于時間因子的混合推薦模型

針對上述傳統混合推薦算法的不足，本文選用如下方法解決這個問題：抓取用戶行為數據，對用戶閱覽過的新聞采用LDA主題分析模型，得出概率主題分布，再聚類用戶行為時間，將一天的行為時間分為t個簇，分別計算每個簇的概率主題分布.根據用戶的閱讀行為和時間點將該行為分入某簇中，預測其興趣分布，然后根據推薦算法，將待推薦列表的top-N 推薦給用戶.圖1為推薦過程的流程圖.1)抓取用戶數據，收集足夠數量的用戶群體在一段時間內的新聞瀏覽記錄，記錄包含用戶唯一標志id、閱讀時間time、閱讀新聞標題內容content等.2)對閱讀的新聞內容LDA文本分析，得出對應的主題分布.根據時間對用戶的行為聚類，然后對每個時間簇內的興趣分布聚類，得出有相似閱讀興趣的用戶群.3)得出用戶興趣分布模型后為用戶推薦新聞結果，其中推薦情況可分兩種：a) 用戶主動閱讀行為，即用戶主動打開新聞媒體，此時將當前時間聚類入某時間簇中，根據該時間簇的興趣分布預測用戶閱讀喜好，采用協同過濾的方法推薦新聞給用戶.b)新聞客戶端將熱門新聞推送給用戶.推薦需考慮用戶閱讀興趣的時間段，設置權值權衡得出用戶對待推薦列表的評分，采用基于內容的推薦方法生成推薦列表.

圖1 推薦流程示意圖Fig.1 Recommended flow diagram

3.1 用戶閱讀時間模型

用戶在不同的時間有不同的閱讀興趣分布，考慮用戶不同時間段的閱讀習慣可以更合理化個性化推薦信息.本文收集N個用戶在不同的時間點的閱讀數據，對時間點聚類分析將用戶的閱讀行為添加時間標簽并分為多段，同時對每次閱讀的內容文本解析，得到主題概率分布，將時間和主題分布相結合，最終得出用戶在不同的時間段內的閱讀興趣分布情況.

對于時間的聚類采用DBSCAN算法.最終可以看出用戶在主動閱讀時閱讀行為主要存在于積極閱讀的時間段內，閱讀行為比較密集，但也存在消極閱讀時間，閱讀行為較分散且稀疏，部分閱讀行為可視為噪點.

DBSCAN聚類算法[17-19](Density-Based Spatial Clustering of Applications with Noise)是一種基于密度的空間聚類算法.該算法將具有足夠密度的區域劃分為簇，并在具有噪聲的數據集中發現任意形狀的簇，它將簇定義為密度相連的點的最大集合.優點是聚類結果受噪點影響小且聚類速度快.缺點是當數據量較大時算法對內存的需求較高，當空間密度不均勻、聚類間距較大時聚類效果不理想，即對人工輸入的參數Eps鄰域和minPts敏感.算法思想是掃描整個數據集，找到任意一個核心點，對該核心點進行擴充.擴充的方法是尋找從該核心點出發的所有密度相連的數據點，即依次遍歷該核心點的α鄰域內的所有核心點，尋找與這些數據點密度相連的點，直到沒有可以擴充的數據點為止.最后聚類成的簇的邊界點都是非核心數據點.之后就是重新掃描數據集(不包括之前尋找到的簇中的任何數據點)，尋找沒有被聚類的核心點，再重復上面的步驟，對該核心點進行擴充直到數據集中沒有新的核心點為止.數據集中沒有劃分到任何簇中的數據點就成了噪點.

DBSCAN算法的主要缺點在于對輸入參數Eps和minPts敏感，根據經驗直接取固定數值會導致聚類準確度下降，聚類結果不理想.本文對輸入參數的取值參考了文獻[21]的I-DBSCAN算法，該算法通過分析收集的用戶行為數據集的統計特性來動態確定輸入參數Eps和minPts.

首先要計算數據集的元素距離矩陣：

DISTn×n={dist(i，j)|1≤i≤n，1≤j≤n}

(1)

其中，n 表示數據集中的對象個數.DISTn×n是n行n列的實對稱矩陣，元素dist(i，j)表示矩陣D中第i個對象到第j個對象的距離.依次求出矩陣DISTn×n中每行的值，并對DISTn×n中每行的值從小到大進行排序，記DISTn×i為排序后距數據點n最近的第i個距離值.由于DISTn×i中所有點的第i個距離值在數軸上服從泊松分布，此處可以用極大似然估計法來對整個第i個距離值的泊松分布進行參數估計：

(2)

得到λ的期望值即為 Epsi的取值.在Eps 確定的情況下，計算出數據集中每個點的 Eps 域內點的個數，然后對整個數據集中每個點的Eps域內點的數目求數學期望得到MinPts，此時的MinPts為每個聚類中核心對象 Eps內的數據點個數的最優值.MinPts 的計算公式為：

(3)

其中Pi為點i的Eps鄰域內點的個數.

在本文中，對用戶閱讀過的新聞進行DBSCAN聚類分析，由公式(1)計算得出用戶閱讀新聞較多的時間集合tU=(tl1，tl2，…，tlk)，其中tlk(k=1，2，…)為聚類后所形成時間簇的中心點．同時獲取用戶在相應時間段內閱讀過的新聞集合A={a1，a2，…，ak}，其中ai(i=1，2，…，k)是用戶在tlk時間段內閱讀的新聞集合.

(4)

其中ti是以tlk為中心的時間聚類簇中的某一時間點，m為該時間簇內的時間點的個數.對時間信息DBSCAN聚類過程如算法1 所示：

算法1.DBSCAN聚類算法

輸入：D，待聚類的時間節點集合；

Eps，聚類簇的半徑；

MinPts，核心點以Eps為半徑的區域內最少點的個數；

輸出：所有點的聚類結果.

1.C=0

2.for each point P in dataset D {//遍歷數據集

3. If P is visited

4. continue next point；

5. Else NeighborPts=regionQuery(P，Eps)//查詢p的鄰域內的所有點

6. if sizeof(NeighborPts) < MinPts

7. mark P as NOISE//非核心點標記為噪聲

8. else

9. C=next cluster

10. expandCluster(P，NeighborPts，C，Eps，MinPts)//若是核心點，則擴展該類

11. end if；

12.end for；

其中對DBSCAN算法的expandCluster()函數實現中，如算法2所示.

算法2.DBSCAN聚類算法expandCluster()函數

輸入：SetOfPoints，待聚類的時間節點集合；

P，待歸類的某個時間節點

Eps，聚類簇的半徑；

MinPts，核心點以Eps為半徑的區域內最少點的個數；

輸出：點P的聚類結果.

1.Seeds=SetOfPoints.regionQuery(P，Eps)；

2.If Seeds，size

3. Mark P as Noise //視為噪點

4. Else Set Seeds belong to ClId；

5. Delete P from Seeds；

6. While Seeds < > Empty Do

7. currentP=Seeds.first()；// 依次循環歸類

8. Result=SetOfPoints.regionQuery(currentP)；

9. If result.size >=MinPts then//視為核心對象

10. For i from 1 to result.size do

11. resultP=result.get(i)；

12. If resultP.ClId in Unclassified or Noise then

13. If resultP.ClId=Unclassified then

14. resultP join in Seeds

15. Else resultP is In anothercluster；

16. preClId=resultP.ClId；

17. Record preClId is connect with ClId

18. END if；

19. END for；

20. END if；

21. Delete currentP from Seeds；

22. END while；

23.END if；

最終聚類結果類似于圖2、圖3所示：

圖2 時間time1用戶u1的興趣分布Fig.2 Interest distribution of User u1 in time1

3.2 生成推薦列表

對2.1節中得到的新聞集合A={a1，a2，…，ak}進行文本特征提取，可以得出用戶在時間集合tU=(tl1，tl2，…，tlk)中的閱讀興趣分布.用戶的閱讀行為受其主觀和客觀因素影響可分為用戶積極閱讀行為和被動閱讀行為：當用戶瀏覽刷新新聞頁面時，閱讀行為是出于用戶的主動性，可視為用戶的積極閱讀行為；當推薦系統給用戶推薦熱門最新的推送時，用戶是被動接受推薦信息，可視為用戶被動閱讀.通過區分用戶的閱讀行為，有針對性的對其興趣分布向量添加權重，可以更加合理的為用戶生成個性化推薦.

3.2.1 積極閱讀興趣模型

用戶處于積極閱讀狀態時，多數情況下都是在大量的閱讀新聞內容，對新聞頁面的推薦請求較頻繁，因而對推薦新聞的數據量和多樣性要求較高，需采用協同過濾的方法生成推薦列表，同時積極閱讀是用戶的在線閱讀模式，需保證推薦算法的及時性，降低算法的時間復雜度.

圖3 時間time2用戶u1的興趣分布Fig.3 Interest distribution of User u1 in time2

計算出用戶的閱讀興趣向量之后，需要與其他用戶的閱讀興趣相似性比較，通過比較得出與用戶閱讀興趣相似的前N個用戶鄰居，作為對用戶行為的預測興趣分布生成最終的推薦結果.其中，項目(用戶)α和β的相似度計算方法主要有3種：

余弦相似性計算：

(5)

pearson相似性計算：

(6)

加權相似性計算：

(7)

通過將用戶群模型的閱讀興趣向量同項目的主題分布向量進行相似度比較，可以預測用戶群未來行為，按相似度降序排列，對待推薦列表的N條新聞生成K條推薦信息.對于每個用戶而言，通常對K值的選取為用戶已關注的主題數或該數量的一半.

3.2.2 被動閱讀興趣模型

推薦系統在更新待推薦列表時，會根據當前時間查詢比較用戶的閱讀興趣，然后將其同待推薦新聞進行相似度比較，在考慮用戶時間習慣的前提下將最符合用戶閱讀興趣的Top-K推送給用戶，這是用戶的被動閱讀興趣模型.此類推薦主要考慮新聞的時效性和用戶對其的預測評分，因而采用基于內容的推薦方法.

推薦系統在時間點t0更新了待推薦列表，通過LDA技術得出該條新聞的文本主題分布pn，并查詢待推薦用戶u的興趣分布pu，相似度比較為：

(8)

取相似度最高的K條信息作為待推薦信息.

4 實 驗

4.1 實驗數據集

本次實驗選取的數據集來自互聯網某新聞網站16年3月18日至4月30日的部分用戶數據，數據包含用戶id、新聞標題、新聞內容、發布時間、用戶瀏覽時間等信息，篩選掉閱讀行為過少的用戶信息，最終提取出41名用戶的閱讀行為.實驗數據分為兩部分，取前31天的數據集作為訓練集，后12天的數據集用來測試實驗對比數據.

4.2 算法評價標準

在推薦系統的各項評價標準中，最直觀準確的標準是推薦結果是否被用戶瀏覽、是否符合用戶的閱讀興趣．準確率是在推薦結果中用戶閱讀的新聞數量占推薦總數的比率，召回率是在用戶閱讀的新聞中推薦新聞所占的比率，F 值是準確率和召回率的調和平均值．本文通過準確率P( Precision) 、召回率Rc( Recall) 、和 F 值來度量推薦結果的精確度，其計算公式分別為：

(9)

(10)

(11)

其中Ru為用戶u被推薦的新聞列表，Tu為該用戶閱讀的新聞列表.最終得出的推薦情況可分為4種，如表1所示.

表1 推薦系統推薦情況比較Table 1 Recommendation system comparison

4.3 HTF與其他算法比較

HTF算法按照時間的變化劃分用戶的閱讀興趣分布，并結合用戶的積極閱讀行為和消極閱讀行為，生成了用戶的個性化推薦數據，對個性化推薦的精準度有較大提高.為驗證HTF算法的推薦結果，本文實驗選取基于內容的推薦(Content-based)、基于用戶特征和項目屬性的協同過濾推薦算法(UCIACF)和基于用戶聚類的異構社交網絡推薦算法(GCCR)作為參考算法.其中基于內容的推薦Content-based采用主題向量的語句相似度計算衡量相似性，參照開源的機器學習庫Apache Mahout的算法實現.UCIACF算法是基于用戶特征和項目屬性的協同過濾算法，通過引入用戶興趣度來衡量用戶的閱讀興趣隨時間而變化的情況，通過度量鄰居用戶評分的權重和準確度來設定他們對于目標用戶的推薦比重，并計算用戶閱讀興趣與項目屬性的相似度來實現新項目的推薦.GCCR算法是基于圖摘要和內容相似混合聚類的推薦方法，具有很好的參考對比價值.

4.4 實驗結果

實驗結果分兩部分，一部分是算法關于在線推薦的算法評判，另一部分是模擬新聞系統主動推薦熱門信息的用戶召回率.綜合以上兩部分的實驗結果數據比較，得出各對比算法的P值、Rc召回率、F值，圖4顯示為綜合實驗結果得到的各指數對比：

圖4 各指數對比結果Fig.4 Comparison results of each index

從實驗結果來看，UCIACF算法和基于內容的推薦Content-based算法相比較其他兩種算法的推薦準確率略低，而基于內容的推薦Content-based算法在用戶召回率上略低，為用戶推薦時只用一種方法得到的推薦結果遠差于混合推薦算法.GCCR算法采用混合推薦的方法，比傳統的推薦算法有明顯提高，但是未研究時間地點等因素對用戶閱讀興趣的影響，算法各方面略低于HTF算法，HTF對比GCCR的準確度P、召回率Rc、F值分別提高了16.1%、22.6%、19.4%，對比UCIACF算法的各方面指數也提高了33.3%、11.8%、23.3%.綜上可得出結論：對用戶推薦新聞時采用包含時間因子的混合推薦方法，確實能大幅度提高推薦結果的精度，為用戶提供更個性化的推薦.

5 結束語

個性化推薦目前在許多領域中得到廣泛的應用，有著十分重要的現實意義.個性化推薦的推薦精度受多方面的影響，其中用戶在不同時間段的行為習慣極大地影響了其閱讀興趣.本文通過研究時間因素對用戶閱讀興趣的關聯性，深挖用戶的日常行為習慣對其閱讀行為的影響，得出結論：用戶在不同的時間段內有著不同的閱讀興趣.推薦系統結合用戶不同時間段的閱讀習慣生成推薦列表，更符合用戶的閱讀興趣，顯著提高了推薦精度.

本文設計了包含時間因子的用戶模型，將用戶的閱讀興趣根據其習慣按時間劃分.為了劃分時間行為采用DBSCAN算法作為聚類算法，參考I-DBSCAN算法動態設定輸入參數Eps和MinPts，提保證了DBSCAN聚類的魯棒性，提升了聚類結果的準確度，弱化了噪點對聚類結果的影響.

但是本算法默認認為用戶的閱讀行為具有普遍規律性，對節假日或臨時出差等行為做了模糊處理，部分數據在聚類時被等效視為噪點.如果能考慮GPS采集用戶地理位置[20]以及節假日信息等數據，可以更好的為用戶在“噪點行為”時提供更合理的推薦，這也是本文下一步的研究工作.