基于高效用項集挖掘和詞義歸納的新聞推薦系統

朱 亞 進

(常州交通技師學院 江蘇 常州 213147)

0 引 言

隨著移動互聯網的蓬勃發展，人們每天花費大量的時間觀看互聯網的各種信息，其中新聞是一種影響巨大的信息內容[1]。每天產生大量各種類型的新聞，并且新聞存在新穎、不可預估等特點，用戶通過搜索來查找新聞內容需要花費大量的時間和精力[2]。為了提高用戶觀看新聞的效率，許多新聞應用程序集成了新聞推薦系統。當前的主流推薦系統大多針對購物網站和音樂電影等商品而設計，通過建立“用戶-項目評分”矩陣，采用相關性指標度量用戶之間的相似性，通過協同過濾技術為用戶提供推薦列表[3-4]。新聞內容中包含了大量的文字信息[5]，利用這些信息能夠有效地緩解冷啟動問題和稀疏性問題，但是這些文字信息為相似性分析帶來了難度。

許多新聞應用將用戶點擊量作為偏好的評估指標，根據用戶的閱讀耗時對用戶偏好值做調節[6]，此類系統能夠實時更新用戶興趣模型，達到推新、推準的效果，但存在嚴重的稀疏性問題和冷啟動問題。文獻[7]將改進的層次聚類算法用于新聞事件發現問題，引入事件的多重特征計算用戶的興趣模型，該算法利用Spark框架實現了快速的響應，但對用戶的興趣評估不夠準確。文獻[8]通過已有用戶對于新聞的點擊瀏覽記錄，提取其在不同環境中的上下文信息，利用興趣分類記錄構建決策樹分類模型，該方案能夠有效緩解新聞推薦系統中用戶冷啟動問題。文獻[9]通過引入矩陣分解、標題分析和知識圖譜對新聞的標題進行了深入的分析，提出了一種細粒度的新聞推薦系統。該系統的實驗結果表現出更為準確的推薦結果，并且有效地緩解了稀疏性問題和冷啟動問題，但由于利用深度神經網絡提取新聞的特征，此過程需要大量的計算成本，并且不具備可擴展性。

新聞推薦系統有兩個特殊之處：① 目標權衡。新聞提供商需要權衡廣告收益和新聞內容，所以系統應當能夠支持不同的商業目標。② 冷啟動問題。新聞提供商連續產生大量的新聞，由此導致用戶冷啟動問題和新聞冷啟動的問題。根據文獻[9]獲得的成果，通過標題詞義的分析和新聞內容等信息能夠顯著提高推薦的準確率，可通過分布式計算解決詞義分析所帶來的計算成本。新聞推薦領域中包含了大量的詞匯和上下文信息，詞義歸納機制能夠對新聞標題和內容的詞匯做歸納處理，提高后續新聞推薦的準確率。本文從語料庫和用戶交互兩個方面分析新聞系統，將用戶點擊量和其他輔助屬性作為指標建立新聞的效用模型，通過效用模型能夠支持對系統目標的權衡，并且緩解冷啟動問題。另外，給出了基于MapReduce的分布式推薦系統實現方案，從而為用戶實時提供推薦列表。

1 新聞推薦系統的模型

設nw為新聞的正文內容，Si為會話i，D為點擊量數據集，ψ(nw)為基于nw屬性計算的新聞端度量，γ(nw,Sr)為會話Sr中nw的用戶端度量，φ(nw,Sr)為會話Sr中nw的效用，σ(nw,P)為新聞閱讀模式P中nw的內部效用，φ(P,D)為D中新聞閱讀模式P的效用。設N={nw1,nw2, …,nwn}為新聞內容的集合，點擊量數據集由若干會話組成，會話S定義為一個排列的新聞列表，每個新聞表示為相關屬性集，屬性包括：新聞標題、新聞受歡迎度和發布日期。根據用戶閱讀新聞的交互軌跡初始化屬性集，屬性稱為用戶-新聞交互屬性。本文先給出新聞的效用模型，然后提出一種從點擊量數據集到新聞效用模型的映射方案。

定義1新聞端度量。對于新聞內容nw，新聞端的度量定義為：

ψ(nw)=Fψ(f1,f2,…,fk)

(1)

式中：{f1,f2,…,fk}為新聞的屬性集;Fψ為聚合函數。

定義2用戶端度量。給定一個會話Sr和一個用戶-新聞交互屬性f′1,f′2,…,f′k，用戶端度量定義為：

γ(nw,Sr)=Fγ(f′1,f′2,…,f′k)

(2)

式中：Fγ為一個聚合函數。

定義3新聞效用模型。給定一個新聞nw和一個會話Sr，新聞效用模型定義為：

φ(nw,Sr)=Fφ(ψ(nw),γ(nw,Sr))

(3)

式中：Fφ為一個聚合函數。

上述定義并未限制聚合函數Fψ、Fγ和Fφ的形式。在不同的應用場景下，根據商業目標調整聚合函數。表1所示是包含5個會話{S1,S2,S3,S4,S5}的點擊量數據集，假設應用的目標是利用推薦的新聞增加用戶的參與度，此時新聞的日期、受歡迎度、社交媒體的活躍度則是用戶參與度的重要指標。表2是γ聚合的結果，表3是新聞的點擊量數據集，表4是ψ聚合的結果。最終定義了Fφ將γ和ψ的結果相乘，獲得最終的效用：φ(nw,Sr)=ψ(nw)×γ(nw,Sr)。

表1 會話的點擊量數據集

表2 γ聚合的結果

表3 新聞的點擊量數據集

表4 ψ聚合的結果

上述例子是新聞效用模型的一種可能實例，實際應用中存在許多的屬性。圖1所示是總結的新聞效用模型融合實例。

圖1 總結的新聞效用模型融合實例

定義4新聞閱讀模式。新聞閱讀模式P定義為用戶閱讀的新聞集{nw1,nw2,…,nwL}，L為模式長度。

2 基于效用的新聞推薦系統

設計了基于效用的新聞推薦系統，簡稱為(News Recommendation System, nwrecsys)，nwrecsys基于Apache Spark框架和MapReduce框架實現，首先基于點擊量數據集學習推薦規則集，然后根據規則集為當前的用戶會話推薦新聞列表。圖2所示是本系統的總體框架，其中發現規則的部分主要分為兩個階段：① 發現內容級別的推薦規則;② 發現標題級別的推薦規則。

圖2 新聞推薦系統的總體框架

2.1 內容級別的推薦規則

大多數基于規則的推薦系統基于數據生成關聯規則，首先發現頻率不小于最小支持度閾值的新聞閱讀模式，給定一個頻繁新聞閱讀模式P，選出置信度不小于閾值的所有規則集，記為R：A→B。置信度定義為包含模式B的會話占包含模式A會話的百分比。基于本文的新聞效用模型尋找所有內容級別的規則R：A→B。如果達到以下兩個條件，則認為推薦的結果較好：(1) 一個會話包括閱讀的新聞內容和推薦的新聞列表;(2) 推薦的新聞應當能夠提高外部效用值。定義一個內容級別的新聞推薦規則來滿足這兩個條件。給定兩個新聞閱讀模式X和Y，如果滿足以下3個條件，則認為R：X→Y為一個內容級別的新聞推薦規則：①X≠?,Y≠?,X∩Y≠?;②Y和X∪Y均為高效用新聞閱讀模式。③ 規則的效用置信度不小于用戶預設的最小閾值。規則的效用置信度定義為：

(4)

規則R：X→Y的效用置信度描述了Y對于新聞閱讀模式X∪Y的效用貢獻，假設規則推薦Y，而Y與X關聯，那么X∪Y構成高效用的新聞閱讀模式，置信度越高表示推薦的總效用值越高。發現規則由兩個部分組成：滿足條件(1)的高效用新聞閱讀模式；滿足條件(2)的內容級別的新聞推薦規則。從點擊量數據集挖掘高效用新聞閱讀模式需要消耗巨大的計算資源和存儲資源，且此情況的新聞效用模型未必單調，所以不滿足向下閉合屬性，此情況下剪枝搜索空間的難度遠遠大于傳統的頻繁項集挖掘算法。因此本文通過分布式計算提高系統的計算效率。

圖3為發現內容級別推薦規則的分布式計算框架。第一個Map-Reduce中應用定義1和定義2建立效用數據集。然后使用一個Mapper和Map-Reduce處理效用數據集，發現高效用新聞閱讀模式。最后使用一個Map-Reduce發現內容級別的推薦規則。

圖3 發現內容級別推薦規則的分布式計算 框架(基于Apache Spark 2.3.0)

算法1發現高效用新聞閱讀模式

輸入：效用數據集D，新聞效用模型Fφ，最小效用閾值δ。

1.將D分布于計算機集群的m個節點上{D1,D2,…,Dm}；

2.foreach?Si∈Djdo

3.foreach?nw∈Sido

4.φ(nw,Si)←Fφ(ψ(nw),γ(nw,Si));

6.endfor

8.endfor

9.χi= 在節點i中尋找高效用新聞閱讀模式；

//采用文獻[10]的挖掘算法

給定一個高效用新聞閱讀模式的集合，本文的目標是發現內容級別的新聞推薦規則。

給定一個新聞閱讀模式P={nw1,nw2,…,nwn}，其中σ(nw1,P)<σ(nw2,P)<σ(nwn,P)，X={nw1,nw2,…,nwk}?P，k≤n，P中新聞nwi滿足以下的關系：

uconf(〈{X-nwk}→nwi〉)>uconf(〈{X-nwk-1}→nwi〉)

(5)

式中：X-nwk表示集合X中刪除新聞nwk后的集合。

根據上述思路，提出一種發現內容級別推薦規則的算法，如算法2所示。算法的輸入為高效用新聞閱讀模式和最小支持度min_uconf，輸出為內容級別的新聞推薦規則。第2行將模式P的新聞按會話中的內部效用值升序排列，給定新聞nw，算法2產生所有的內容級別推薦規則。

算法2內容級別的規則發現算法

輸入：高效用新聞閱讀模式集Pset，最小效用置信度min_uconf。

2.Pset′←新聞內容按σ(nw,P)升序排列；

3.foreachP={nw1,nw2,…,nwn}∈PSet′do

4.foreachi= {1,2,…,n}do

5.ifnwi∈Pset′then

6.X←{nw1,nw2,…,nwi-1}；

7.Y←nwi；

9.else

10.returnNULL;

11.endif

12.endfor

13.endfor

14.return；

算法2的第8行調用算法3(algorithm3)檢查每個規則的有效性。算法3運用理論1評估內容級別的規則，遞歸地尋找所有的規則，時間復雜度為O(k)，復雜度小于窮舉搜索的復雜度O(2k)，k為輸入高效用新聞閱讀模式的長度。

算法3規則檢查算法

輸入：X,Y,,min_uconf,Pset。

1.uconf=σ(Y,X∪Y)/σ(X∪Y,X∪Y)；

2.ifuconf≥min_uconfthen

3.R←{X→Y,uconf,σ(Y,X∪Y)}

6.R加入；

7.endif

8.fornw∈Xdo

9.X’=X-nw；

10.algorithm3(X,Y,,min_uconf,Pset);

10.endfor

2.2 新聞效用模型

設nw為新聞內容，設usr為用戶，因為nw的參與度是動態變化的，nw的內容端度量計算如下：

(6)

式中：acc_date為usr點擊nw的時間；rel_date為nw的發布時間。

nw的usr用戶端度量計算為：①DwellTime：usr在nw上花費的時間；② 社交媒體活躍度(socialact)：用戶是否在社交媒體分享該內容。γ函數定義為：

γ(nw,Sr)=DwellTime(usr,nw)×socialact(usr,nw)

(7)

最終的效用模型定義如下：

socialact(usr,nw)

(8)

2.3 標題級別的推薦規則

內容級別的新聞推薦規則給出了新聞內容之間基于效用的連接，但無法推薦新發布的內容。如果直接應用基于內容的方法推薦新發布的內容，那么存在兩點不足：① 推薦質量低。推薦的內容僅考慮內容的相似性，不考慮新聞閱讀模式，用戶可能對內容無興趣。② 多樣性不足。

本文開發了基于詞匯歸納和概率模型的標題級別推薦規則，包括四個階段：

第1階段：上下文建模和上下文嵌入。

第2階段：上下文嵌入建模為復雜網絡。

第3階段：詞義歸納。

第4階段：標題級別的推薦規則。該算法無需先驗知識，利用模塊度獲得最佳的分簇結果。

2.3.1上下文建模和上下文嵌入

采用Word2vec[11]表示標題的詞匯，設計了快速的詞匯嵌入訓練方法，其次設計了詞匯預測模型和詞匯的上下文預測模型。Word2vec生成的詞匯嵌入能夠保存語法屬性和語義屬性，組合上下文所有的詞匯嵌入總結出歧義詞匯。

圖4所示是產生歧義詞匯嵌入的流程。第1步獲得目標詞匯的近鄰詞匯向量，采用Word2vec獲得嵌入的結果。將Google新聞作為訓練集，語料庫共包含1 000億個詞匯。獲得每個上下文的嵌入表示之后，將結果組合成一個向量，該向量表示了目標詞匯上下文的詞義特征。

圖4 產生歧義詞匯嵌入的流程

設wi為標題中位置i的歧義詞匯，假設上下文為ci，wi附近共有ω個詞匯，即ci=[wi-ω/2,…,wi-1,wi,wi+1,…,wi+ω/2]T，對wi的上下文嵌入結果為ci：

(9)

式中：wi為第j個詞匯在ci的嵌入，一個詞匯的上下文設為近鄰詞匯的語義特征組合。

2.3.2上下文嵌入建模為復雜網絡

上下文之間的相似性建模為復雜網絡，相似詞匯間建立連接，如果兩個上下文嵌入相似，那么對應的上下文向量間建立連接。采用k-NN算法將上下文嵌入建模為復雜網絡，選擇較小的k值能夠降低網絡的復雜度。然后，使用余弦相似性度量兩個節點間的距離。

2.3.3詞義歸納

Louvain算法的計算成本低，直接對網絡的模塊度函數做優化處理，無需附加的參數信息。所以運用Louvain社區檢測將復雜網絡分簇，每個簇為一個歸納的詞義。圖5所示是詞義歸納的一個實例，圖中“BEAR”是一個多義詞，具有兩個詞義：① 表示忍耐的動詞；② 表示熊的名詞。首先考慮上下文詞匯的嵌入，第1個句子的上下文詞匯為“PAIN”，第2個句子的上下文詞匯為“IN”和“FOREST”。通過上下文詞匯的嵌入描述多義詞，然后，建立相似性詞匯嵌入的網絡，再使用社區檢測算法將詞義分簇。

圖5 識別多義詞的實例

2.3.4標題級別的推薦規則

設計一個標題概率模型從語料庫推理出潛在的標題。設新聞標題語料庫為N，其詞匯為V，標題t是關于詞匯wi∈V的多項式分布，記為p(wi|t)。假設每個內容的標題唯一，如果p(ti|tj)較高，則認為標題級別的規則tj→ti為優質規則。新聞的概率p(ti|tj)為：

(10)

采用新聞效用模型估計p(nw)：

(11)

式中：D為點擊量數據集，Sr為D內的一個會話。 式(10)從標題概率模型獲得概率p(ti|nw)，標題級別規則R:{tj→ti}的標題效用置信度表示為p(ti|tj)。給定一個標題級別效用的置信度及一個下限值min_tconf。算法4為發現標題級別推薦規則的算法，首先獲得兩個標題ti和tj，然后計算條件概率p(tj|ti)和p(ti|tj)，如果p(tj|ti)或p(ti|tj)不小于閾值，則發現了一個新的標題規則R:{ti|→tj}或R:{tj|→ti}。

算法4發現標題級別推薦規則的算法

輸入：點擊量D，標題分布T，標題置信度下限值min_tconf。

1.foreachti,tj∈Tdo

2. 計算p(ti|tj)和p(tj,ti)；

3.ifp(ti|tj)≥min_tconfthen

4. 規則R:添加到T；

5.endif

6.ifp(tj|ti)≥min_tconfthen

7. 規則R:添加到T；

8.endif

9.endfor

10.returnT；

3 生成推薦的新聞列表

本文的新聞推薦系統共計算新聞的3種評分。

(1) 內容級別的新聞推薦評分。給定一個用戶會話Sr和閱讀模式P，內容nw的推薦評分計算為：AL(nw)=φ(P,Sr)×uconf(P→nw)，φ(P,Sr)為閱讀模式P在會話Sr的效用值。從P的所有子集中選擇最高的推薦評分作為最終的nw推薦評分。假設一個閱讀模式P包含k個內容，使用2k個P的子集產生候選推薦，選出評分最高的候選推薦作為最終的推薦。

(3) 新聞推薦總評分。綜合上述兩個評分作為新聞推薦的依據，融合方法為：com(nw)=AL(nw)×TW(nw)。

4 實驗和結果分析

4.1 實驗環境和實驗方法

實驗環境由一個master節點和6個worker節點組成，每個節點裝備了Intel Xeon 2.6 GHz處理器和128 GB的內存。分布計算平臺為Spark Release 2.3.0。

4.2 性能評價指標

為了保證實驗結果的置信度，采用5折交叉驗證的實驗方案，將數據集隨機分為5個子集，輪流選擇4個子集作為訓練集，剩余的子集作為測試集，最終將5次實驗結果的平均值作為最終的統計結果。根據訓練集獲得算法的最優參數集。

性能評價指標包括平均精度均值MAP@K和多樣性。MAP定義為相關內容數量除以數據集的內容總數量，多樣性定義為推薦列表中每對新聞的不相似性平均值，假設新聞數量為N，平均不相似性計算為：

diver(N)=

(12)

式中：p為新聞的數量；sim()為余弦相似性。

4.3 實驗數據和參數設置

實驗中采用Semeval-2013語料庫[12]，Semeval-2013共有50個詞匯，每個詞匯的樣本數量范圍為22～100。數據集包括OANC[13]的4 664個樣本，每個樣本是字典的一個短語。

采用Google新聞數據集預訓練詞匯嵌入模型，該數據集包含約1 000億個詞匯。模型共有300萬個不同的詞匯和短語，采用Word2vec方法訓練詞匯嵌入模型，詞匯嵌入的維度為300。算法的效用閾值min_util設為1萬，min_uconf設為0.6，min_tconf設為0.45。

選擇NTrecsys、LAPnwrec、PBnwrec、HARTnwrec作為對比方案。NTrecsys[14]是一種考慮新聞標題的相似性推薦系統，該系統評估標題中關鍵詞的相似性，然后簡單采用協同過濾推薦算法為用戶提供標題相似的新聞內容。LAPnwrec[15]是一種實時的網絡新聞推薦算法，該算法將用戶的位置作為相似性度量的一部分，以期緩解多樣性問題。PBnwrec[16]則提出了新聞內容的隱秘性度量指標，通過檢測新聞的隱含信息，緩解推薦系統的稀疏性問題。HARTnwrec[17]是一種基于Apache Spark框架的分布式推薦系統，與本文的實現框架相似。

4.4 推薦準確率和多樣性實驗

圖6為推薦系統的推薦MAP結果。圖中nwrecsys在不同K值下的MAP結果均優于其他的推薦算法，這是因為本文算法同時考慮了新聞內容級別的推薦規則和新聞標題級別的推薦規則，基于效用模型將兩者關聯，對新聞系統的推薦準確率實現了明顯的提高。

圖6 推薦系統的推薦MAP結果

圖7為推薦算法的平均多樣性結果，可以看出，推薦內容的數量越多則多樣性越低。原因在于選擇的新聞越多，推薦的新聞越契合用戶的興趣，推薦的新聞相似性則越高。nwrecsys的多樣性明顯高于其他幾個推薦算法。

圖7 推薦系統的平均多樣性結果

4.5 冷啟動和敏感性實驗

為了仿真新聞系統的冷啟動問題，參考文獻[18]的實驗方法：將70%的新聞內容分為訓練子集，30%的新聞內容分為測試子集。訓練集包含評分信息、點擊量、閱讀時長的反饋信息，測試集不包含任何的顯式反饋信息和隱式反饋信息，測試推薦系統在不同K值條件下的性能。新聞冷啟動問題中，因為新發布的新聞沒有被閱讀的歷史記錄，所以大多數推薦算法無法工作。圖8為推薦算法對于新聞冷啟動場景的平均MAP結果，圖中顯示，本文算法的MAP結果優于其他的推薦算法，原因在于本文算法設計了標題的概率模型，有助于向用戶推薦新發布的新聞。

圖8 推薦算法對于新聞冷啟動場景的平均MAP結果

最終評測了不同閾值參數對推薦系統性能的影響。圖9顯示了推薦系統對于閾值的敏感性，可以看出min_uconf和min_tconf的值越低，推薦規則越多，而這些多余的規則導致置信度降低。總體而言，閾值越低，推薦系統的精度越低。

(a) 參數min_uconf的敏感性結果

(b) 參數min_tconf的敏感性結果圖9 推薦系統對于閾值的敏感性

4.6 推薦系統的時間效率

作為線上應用程序的一部分，計算效率是決定實用性的關鍵因素。評估了推薦算法的響應時間，結果如圖10所示。NTrecsys算法、LAPnwrec算法、PBnwrec算法并未對時間效率做優化處理，對于大數據集的響應時間較長；HARTnwrec是一種基于Apache Spark框架的分布式推薦系統，平均執行時間約為0.4 s；本文算法的平均執行時間約為0.5 s。因此HARTnwrec與本文算法都具有較好的速度。

圖10 推薦算法的平均執行時間

5 結 語

主流的新聞推薦方法將用戶點擊量作為隱式反饋信息來理解用戶的行為，但點擊量無法反映用戶的真實興趣。本文提出了基于高效用項集挖掘和詞義歸納的新聞推薦系統，從語料庫和用戶交互兩個方面分析新聞系統，將用戶點擊量和其他輔助屬性作為指標建立新聞的效用模型，通過效用模型能夠支持對系統目標的權衡，并且緩解冷啟動問題。

本文初步研究了新聞推薦系統，因為英文語料庫的數據量較小，并且英文新聞的資源易于獲取，因此將英文新聞的資源作為研究對象。未來將收集中文語料庫，選擇合適的中文新聞數據集作為實驗數據集，針對中文新聞的推薦問題做深入研究。