一種基于知識樹的推薦算法及其在移動電子商務上的應用

趙 華，林 政,方 艾，楊翊平

（1.中國電信股份有限公司廣東研究院 廣州 510630；2.海量信息技術有限公司 北京 100190）

一種基于知識樹的推薦算法及其在移動電子商務上的應用

趙 華1，林 政2,方 艾1，楊翊平1

（1.中國電信股份有限公司廣東研究院 廣州 510630；2.海量信息技術有限公司 北京 100190）

本文提出了一種有別于傳統方法的、新穎的基于知識樹的文檔推薦算法，首先利用互聯網資源構建基于詞的知識樹，然后運用EM算法不斷用待分類的新文檔自動更新知識樹，使得詞分類和文檔分類結果同時達到最優，該算法不依賴于標注好的訓練語料，是一種半監督的機器學習算法。在實際應用中，根據用戶在移動互聯網的互動行為，映射到知識樹的相關分類，將同類的商品推薦給用戶。在移動電子商務網絡社區項目中，實驗表明了該算法具有較高的執行效率，推薦結果的用戶滿意度約為83%。

移動電子商務；個性化推薦；知識樹；EM算法

1 引言

近年來，隨著3G網絡的建設，移動互聯網和移動電子商務得到飛速發展。據易觀國際發布的分析報告顯示，2010年中國移動互聯網用戶達2.88億人，環比2009年增速達40.5%，預計2012年中國移動互聯網用戶數將超過互聯網用戶數[1]。而移動電子商務也得到了極速發展。據中國電子商務研究中心發布的 《2010年中國電子商務市場數據監測報告》顯示，截至2010年12月，中國移動電子商務實物交易規模（實物交易規模包括家電、日用品、服飾等實體商品的交易總額）達到26億元人民幣，同比增長370%[2]。

因此，電子商務、微博、轉帖、視頻等主流互聯網模式將占據大量資源和市場，如何利用數據挖掘技術從大量的網絡信息中挖掘出對人們最有用、最關注的資源，已經成為研究的熱點問題。在這種背景下，個性化推薦系統[3]（personalized recommender systems）應運而生。

個性化推薦是根據用戶的特征，比如興趣愛好，推薦滿足用戶要求的資源并可以實時更新推薦。個性化推薦系統為客戶提供智能化、個性化的服務，它能夠向客戶推薦產品或提供信息，來引導客戶有針對性地對網上商品或其他信息進行關注，使互聯網從過去的“人找信息”發展到“信息找人”的智能階段。

2 研究現狀與解決思路

目前存在有許多個性化推薦系統，它們提出了各種思路以實現個性化推薦服務。個性化推薦系統根據其所采用的推薦技術可以分為3種。

（1）基于規則的系統

根據用戶的靜態特征來制定規則，規則決定了在不同的情況下如何提供不同的服務，例如IBM的WebSphere(www.ibm.com/websphere)和BroadVision(www.broadvision.com)，其優點是簡單直接，缺點是規則不具有普適性，隨著規則數量的增多，系統將變得越來越難以管理。

（2）基于內容的過濾系統

利用資源與用戶興趣的相似性來過濾信息，如Web Personalizer[4]，其優點是簡單有效，缺點是難以辨別資源內容的質量，而且只能發現和用戶已有興趣相似的資源，不能為用戶發現新的感興趣的資源。

（3）協同過濾推薦系統

利用客戶的個人信息、歷史、喜好計算用戶之間的距離，目標客戶對特定頁面或商品的喜好程度由最近鄰居對商品的評價的加權平均值來計算，如Let’s Browse[5]，一個比較成熟的系統。基于協同過濾系統的優點是能為用戶發現新的感興趣的信息，缺點是存在兩個很難解決的問題，一個是系統具有資源依賴性，另一個是隨著系統用戶和資源的增多，系統的性能會越來越低。

與上述各方法不同，文本提出了一種全新的解決思路——基于知識樹的Web文檔推薦算法。這種算法可以克服以上方法的不足，既不依賴于人工制定的規則，也不依賴于大量的有類別標記的語料資源，而且隨著時間的累積，系統性能還會逐漸提高并最終趨于穩定。該算法是一種半監督的機器學習算法：首先利用Web資源構建一棵基于詞的知識樹，然后運用EM迭代的思想不斷用待分類的新文檔自動更新知識樹，使得詞分類和文檔分類結果同時達到最優。

3 知識樹的初始化

百度百科（http://baike.baidu.com）是全球最大的中文百科全書之一，已收錄超過300萬個詞條。本文以百度百科收錄的詞條為基礎，通過挖掘詞與詞之間的層級關系，建立起一棵基于標簽的知識樹。標簽[6]（Tag）又稱“自由分類”、“分眾分類”或“開放分類”，是用戶根據自己對事物的理解所添加的描述詞。因此，標簽可以很好地描述用戶的喜好、興趣，可以借助標簽來提供個性化推薦服務。

對于知識樹，首先給出如下幾個定義：

·知識樹的非葉子節點，在系統中被命名為標簽詞，它是一個有限集合，完全依賴用戶的定義或者所使用的原型知識樹的非葉子節點；

·知識樹的葉子節點是由文本提取的錨點詞集合逐步添加的；

·定義虛擬節點“萬象”為0級，往下級別累加；

·任意一節點（非根節點）所指語義都可以被其上層節點所代表的路徑的語義解釋，則認為該節點可以加入知識樹；

·允許某節點與其父節點有相同的詞形，不同層級含義不同。

通過對百度百科詞條的關鍵詞提取以及對詞條與標簽的層級關系的挖掘，可以構建一棵知識樹，如圖1所示。

圖1 知識樹示例

在圖1的示例中，這棵初始化的知識樹有4層，總計30萬個節點。樹中的父子關系可以很好地描述詞的類別歸屬，如“奧運會”屬于“體育”類別。

4 知識樹的更新

基于知識樹的個性化推薦系統的實質是不斷從待推薦（分類）的文本中學習新的知識以更新知識樹，并通過調用新的知識樹，使單文本的標注（分類）更加準確，從而提高個性化推薦服務的質量。

知識樹更新、優化的過程借鑒了期望最大化（expectationmaximization，EM）算法[7]的思想，是一個迭代的半監督學習的過程。EM算法可以從非完整數據集中對參數進行最大似然估計，主要包括以下兩個步驟。

·E步驟：估計期望值（estimate the expected value）。

·M步驟：最大化期望參數（re-estimate parameter）。

知識樹的更新過程迭代使用E、M步驟，直至收斂。在本系統中E步驟是對一個新文本進行類別標注的過程，M步驟是參照標注的文本重新對關鍵詞進行類別標注的過程。對有待分類的新文本首先根據現有知識樹進行類別標注，然后利用該文本提供的信息更新知識樹，使得對新本文的標注更準確。

這里，E步驟實際上是對文本進行類別標注，M步驟是從標注文本中獲得關鍵詞的類別信息以更新知識樹。因此，本文提出了文本以及詞的類別標注算法，如下面所述。

4.1 文本的類別標注

文本的類別標注主要通過對現有知識樹的查找和分析來進行未標注文本的標簽標注，在介紹具體算法之前先引入3個概念。

（1）路徑穩定性

路徑穩定性描述了樹中一條自上至下的路徑的穩定程度，計算方式見式（1）：

其中，a1為葉子節點即關鍵詞所在節點，aj為標簽詞所在節點，j為路徑長路。

（2）樹的穩定性樹的穩定性

描述了整棵樹的穩定程度，它表達為穩定路徑占所有路徑的比例，計算方式見式（2）：

（3）內容關鍵詞

本文采用信息檢索中經典的tf·idf的計算方法來獲取內容關鍵詞。該方法賦予文檔D中項i的權重wi為：

其中，tfi為特征項在文檔中出現的頻率（term frequency,TF），idfi為倒文檔率（inverse document frequency,IDF），N 為訓練集合中總的文檔數，dfi為含有項i的文檔數。tf·idf的計算方法是很直觀的：如果某個詞或短語在一篇文章中出現的頻率越高，并且在其他文章中很少出現，則認為此詞或者短語具有很好的類別區分能力，適合用來分類。

計算過程如下：通過內容關鍵詞不斷加入路徑構造樹，針對所有非葉子節點構成的路徑，逐漸刪除不穩定路徑，直到整棵樹穩定下來，具體分兩個步驟進行。

（1）初始化知識樹

①使用文本內容關鍵詞，獲取所有路徑，nMaxMulty為所有詞形中對應節點最多的那個詞形所對應的節點數（路徑數），nCurMulty為當前詞形對應的節點數 （路徑數），每個路徑的權重為：

②形成整棵樹，計算樹中每個節點的權重，計算方法如下：

其中，nSubCnt為樹的總結點數。

（2）對樹進行迭代剪枝

①計算所有非葉節點的路徑權重（只包括葉節點的上一級節點），計算當前樹的穩定度。

②如果穩定度達到1，則迭代結束。

③如果穩定度小于1，則刪除當前權重最低的路徑，返回 i。

4.2 詞的類別標注

在對文本進行了類別標注之后，接下來是用這篇文本所提供的知識優化知識樹。

首先，對標注后的文本進行特征提取。單文本特征提取主要是針對單一的非結構化文本提取有效的特征向量，特征向量由關鍵詞集組成。

其次，對已有的多文本進行詞關系提取以及聚類。多文本詞關系的提取是在多文本間對詞進行同現統計，本文采用卡方檢驗方法獲得詞與詞之間的相關系數。聚類采用基于圖論的聚類方法，該方法原理如下。

基礎假設：網絡中兩個頂點間有K個以上的通路，且通路路徑長度≤2，且合并后在派系中任何兩個頂點間的距離不大于L（L==5表示6度空間，即無限制，任何兩個可聚類點都可以作為派系成員），則稱該兩點可以合并在一個派系 C中。在派系 C 中，如果集合 c’屬于 C，v1，v2，v3…vn（隸屬于c’）中任意一個節點連接的鄰節點數為n-1個，則稱該集合為C內的全連通集合。

在實際應用中，可以定義C為一個派系，c’為派系C內的一個全連通集合。

該關系拆解后的聚類結果是：在派系參數定為K=3時，考察該圖的派系可以劃分為：AD；DMLNOP；FXY；FHIKJ；GTSQ，如圖 2 所示。

5 實驗結果與分析

在前面介紹的文本以及詞類別標注方法的基礎上展開實驗。包括利用未標注文本更新知識樹以及根據用戶興趣結合知識樹查詢的結果向用戶推薦相關文檔，并進行用戶滿意度評測。

5.1 知識樹更新實驗

圖2 聚類示例

如前面所述，初始的知識樹包含約30萬個節點。通過對從新浪新聞采集到的包含財經、科技、體育、娛樂、汽車、生活等6個頻道的約4000篇未標注新聞文本用§4.1介紹的方法運營，知識樹已經增加到了80萬個節點，極大地豐富了原有的百度百科的知識。以經濟類展開為例，如圖3所示。

圖3 知識樹擴展

從圖3可見，原有的知識樹中僅有“經濟學家”、“經濟學派”、“西方經濟學”這3個詞條，經過運營，又增加了“房地產泡沫”、“格林斯潘”、“經濟學”、“美國經濟”、“美聯儲”這些詞條，豐富了知識。除此以外，這些詞條還極其具有時效性，能反映最近一段時間發生的熱點新聞。

5.2 個性化推薦滿意度評測

在個性化推薦滿意度評測中，筆者通過“問卷”的形式人工進行評測。讓用戶選擇喜歡的類別，系統默認給用戶提供初始化關鍵詞。抽樣選取130個目標客戶，每日給用戶提供一定數量的推薦數據（不超過50條），讓用戶進行閱讀并給本次推薦選擇滿意度。將滿意度分為5個刻度：1：符合；2：較符合；3：一般；4：不太符合；5：完全不符合。評測周期為期3周（21天），每天評測一次。

考慮評測對用戶的友好性、真實性，不能強迫用戶閱讀完每日推薦的所有文章，所以將評測指標分為兩類：閱讀的文章是否符合用戶興趣；推薦的文章是否符合用戶興趣。

對于這兩類指標，分別對用戶每個時段的反饋進行統計。兩類指標（指占統計結果的比例）隨時間變化的統計結果見表1和表2。

表1 閱讀的文章是否符合用戶興趣數據統計

表2 推薦的文章是否符合用戶興趣數據統計

縱向比較隨著時間的遷移用戶滿意度評測的結果，表 1和表2中可以看出，“符合”和“較符合”兩個指標的滿意度在評測初期較低，隨著評測的開展滿意度逐漸提高，而不滿意度則逐漸降低。在評測初期因為用戶閱讀量小，用戶的興趣（profile）的預測還沒有完全形成，待用戶的閱讀量增加后，興趣慢慢預測成型，所以推薦效果會提升。

如果將“符合”和“較符合”都視為滿意的情況，那么可以得到用戶滿意度（“符合”、“較符合”占統計結果的比例）隨時間變化的柱狀圖，閱讀的文章每日滿意度以及推薦的文章每日滿意度分別如圖4和圖5所示。

評測結果基本符合預期，推薦滿意度最初增長得比較快，最后趨于平穩。推薦結果的用戶滿意度約為83%。

圖4 閱讀的文章每日滿意度

圖5 推薦的文章每日滿意度

6 總結與展望

本文提出了一種全新的基于知識樹的個性化文檔推薦算法，該算法已成功應用于實際工程項目中。本文的主要貢獻和創新之處體現在以下幾方面：

·提出了一種新穎的個性化推薦解決方案并應用于實踐；

·提出了一種半監督學習算法，既不依賴于規則也不依賴于標注好的語料；

·提出了知識樹的結構用于組織資源。

在今后的工作中，希望能將以下兩個方面做得更細致：

·解決知識樹添加父子關系難的問題，因為知識樹的更新主要擴展的是兄弟關系；

·進一步提高知識樹的檢索效率和穩定性，并在大規模用戶中進行推廣。

1 易觀智庫.2010年第4季度移動互聯網用戶達2.88億 全年營收637億元.http://www.analysys.com.cn/cache/1338/97059.html,2011-2-12/2011-5-18

2 中國電子商務研究中心.2010年度中國電子商務市場數據監測報告.http://b2b.toocle.com/zt/upload_data/down/2010dsjc.doc,2011-1-18/2011-5-18

3 Yoon H C,Jae K K,Soung H K.A personalized recommender system based on web usage mining and decision tree induction.Expert Systems with Applications,2002,23(3):329～342

4 Bamshad Mobasher, Robert Cooley, Jaideep Srivastava.Automatic personalization based on Web usage mining.Communications of the ACM,2000,43(8):142～151

5 Lieberman H,DykeN V,VivacquaA.Let’sbrowse:a collaborative web browsing agent. In: the International Conference on Intelligent User Interfaces,Los Angeles,CA:ACM Press,1999

6 Robert J schke,Leandro Marinho,et al.Tag Recommendations in Folksonomies.Lecture Notes in Computer Science,2007(4702):506～514

7 Borman S.The expectation maximization algorithm:a short tutorial.University of Notre Dame,Tech Rep,July 2004

8 金鐸，徐雄，梁冰，李云.號百電子商務平臺架構建設探討.電信科學，2010，26（8）

9 楊震，陳曉勤.電信企業開展個性化信息服務的研究.電信科學，2009，25（10）

Knowledge Tree Based Recommendation Algorithm With Its Applications to Mobile e-Commerce

Zhao Hua1，Lin Zhen2,Fang Ai1，Yang Xuping1
(1.Guangdong Research Institute of China Telecom Co.,Ltd.,Guangzhou 510630,China;2.Hylanda Information Technology Co.,Ltd.,Beijing 100190,China)

This paper presents a novel knowledge tree based recommendation algorithm,which is different from traditional approaches.At first we construct a word based knowledge tree using resources from the Internet,and then we employ EM algorithm to the tree.We automatically update the knowledge tree using unlabeled documents,making classification of both the terms and document optimized at the same time.Since the algorithm does not rely on any human annotations,it is an un-supervised machine learning algorithm.In real applications,user interactions in the mobile Internet are mapped to certain categories of the knowledge tree,and similar products are recommended to users according categories in the tree.Experiments in the mobile e-commerce network community project indicate the high efficiency of our algorithm,and the performance of user satisfaction achieves about 83%.

mobile e-commerce，personalized recommendation，knowledge tree，EM algorithm

2011-05-12）