網絡電視推薦系統框架及協同過濾算法的研究

黃 喬，尹四清

(中北大學 電子與計算機科學技術學院，山西 太原030051)

隨著互聯網迅猛發展，網絡電視媒體也逐漸走入了千家萬戶，面對其日趨成熟的發展，媒體內容不斷豐富，資源量也在不斷的增大，給用戶在查找感興趣內容時帶來了不便。為解決了這個問題，引入了個性化推薦系統，其中的協同過濾推薦技術［1］應用比較廣泛，它是假設用戶A和用戶B具有相似的興趣度，即用戶A感興趣的內容，用戶B同樣感興趣。在網絡電視推薦系統中的協同過濾算法，是根據所有用戶對已評分視頻的評分記錄來預測某一未評分視頻的評分，把用戶和視頻之間的評分記錄整理成一個用戶—項目評分矩陣，再通過評分矩陣獲取有價值的信息，進行一系列的計算之后產生一個推薦列表。但這種傳統的推薦技術存在一些固有缺陷，例如，“稀疏性”問題、“冷啟動”問題、“實時性”問題等［2-3］，針對這些問題，很多人都進行了研究，并提出了一系列的改進算法。本文提出了一種將聚類、用戶相似—信任關系和項目屬性關系相組合的協同過濾推薦算法，該推薦算法能夠有效改善或克服傳統協同過濾技術中出現的問題，為目標用戶提供更好的推薦結果。實驗結果表明，該算法能夠降低預測與實際用戶評分之間的平均絕對偏差，提高網絡電視推薦系統的推薦質量。

1 網絡電視推薦系統框架

網絡電視推薦系統［4］框架如圖1所示。

圖1 網絡電視推薦系統

1)Web服務器用來收集個人用戶信息并儲存到數據庫服務器中，也可將產生的推薦頁面呈現給用戶。

2)數據庫服務器主要用來存儲各類數據信息數據庫、用戶信息數據庫和用戶資料數據庫。

3)協同過濾推薦技術是該推薦系統的關鍵組成部分，主要通過對數據的處理，為用戶產生滿意的推薦結果。

2 改進的協同過濾推薦技術相關概念

本文提出的改進算法是將聚類、用戶相似—信任關系和項目屬性關系相組合的協同過濾推薦算法。首先，聚類用于縮小原始數據集，獲得更有效的搜索空間，緩解推薦算法的實時性問題。其次，用戶信任關系與用戶相似度相結合，用于搜尋最近鄰居用戶，解決算法稀疏性、冷啟動等問題。最后，基于項目屬性的算法用于預測評分計算，得到影片推薦結果。

2.1 聚類

2.2 用戶相似—信任關系

相對于推薦技術，人們更愿意通過朋友的介紹或向熟人打聽有用的推薦信息，如果把信任的用戶加到推薦技術的用戶群里，那么利用該推薦技術推薦的信息就會更有價值。基于這個思想，把信任關系引入到推薦系統中。本文中的信任主要是表示當前用戶對其他用戶提供服務的評論。在本文中，信任度計算的數據來自于用戶之間主觀的信任評分，用戶信任被評用戶，值為1，否則為0，所構成的評分矩陣即為用戶信任度矩陣Trust(i，j)。

根據某種相似度計算方法來計算用戶之間的相關性sim(i，j)，得到用戶之間的相似度矩陣Sim(i，j)。其實對于評分矩陣來說，就是計算兩個行向量的相關性。計算相似度的方法［7］很多，通常用修正的余弦相似度公式，即

式中:Ric為用戶i對項目c的評分，為用戶i對項目的平均評分，為用戶j對項目的平均評分。

經過各種研究表明，在同一應用領域下，用戶的相似度和信任度存在相關性［8］。故將相似度和信任度線性結合，得到相似—信任度矩陣Q(i，j)=α×Sim(i，j)+(1-α)×Trust(i，j)，α＞0，其中α表示相似度的權重。再利用Q(i，j)來搜索當前用戶的k個最近鄰居用戶。

2.3 項目屬性關系

網絡電視推薦系統中，影片的屬性有類型、導演、主演、關鍵字等。本文將影片類型按照愛情片、喜劇片、驚悚片、科幻片、戰爭片等進行分類，每個分類作為項目屬性矩陣的一維，如果影片屬于該分類，則相應的值為1，否則為0，所構成的項目屬性關系矩陣為Item(i，j)。

3 基于改進協同過濾的網絡電視推薦系統的算法設計

3.1 數據準備

用戶的注冊信息、對視頻的瀏覽記錄和評分記錄均被保存在數據庫服務器中，根據數據庫中的數據信息進行建模，產生用戶—項目評分矩陣U×I［9］。

3.2 聚類

根據用戶—項目評分矩陣進行聚類。聚類算法描述如下:

大石油公司圍繞核心業務、重點資源類型構建勘探資產。埃克森美孚主要圍繞深水、LNG和非常規在全球開展勘探業務。殼牌注重LNG和深水，巨資并購BG也是看中BG在深水和天然氣領域的優質資產。埃尼、道達爾等規模相對較小的大石油公司重點發展深水。國際大石油公司在非常規領域并不占有先機，但通過并購有技術專長的美國本土小石油公司及自身研發來增強在非常規領域的技術實力。埃克森美孚、雪佛龍等美國本土公司都將頁巖油氣作為未來重回增長的重要領域，BP最近以105億美元的價格擊敗殼牌獲得了必和必拓在北美的頁巖油氣資產[9]。這都體現了國際大石油公司力圖引領非常規的決心。

1)從數據源中隨機選取h個用戶作為聚類中心，記作{W1，W2，…，Wh}。并將h個聚類C1，C2，…，Ch初始化為空。

2)計算其余用戶與聚類中心用戶的相似性(距離)，選擇相似性最高(即距離最短)的用戶，劃分到相應的聚類中。

3)根據聚類用戶中所有對象的均值來確定一個新的聚類中心，轉入步驟2)。

4)當每個聚類達到穩定后，即可得到所求的用戶聚類C1，C2，…，Ch。

3.3 k最近鄰用戶搜索

1)在h個聚類用戶C1，C2，…，Ch中檢索目標用戶u所在的聚類Cβ;

2)通過用戶—用戶信任矩陣T檢索聚類Cβ的用戶—用戶信任矩陣T0=Trust(u，v)，即為信任度矩陣T0;

3)通過用戶—項目評分矩陣S檢索聚類Cβ的用戶—項目評分矩陣D0，并進行相似度計算，得到相似度矩陣S=Sim(u，v);

4)由Q(i，j)=α×Sim(i，j)+(1-α)×Trust(i，j)，α＞0，得到信任—相似矩陣Q(i，j)，由Q(i，j)進行k最近鄰用戶搜索［9］，得到k個最近鄰用戶。

3.4 預測評分 產生推薦

1)由k最近鄰用戶整理出相關的項目屬性關系矩陣Item(i，j)，利用基于項目屬性的協同過濾推薦算法［9］對還未評分的項目進行預測評分計算。用戶u對未評分項c的預測評分為［10］

式中:D為項目c的k個最近鄰居集合;Rud表示用戶u對項目d的評分;和分別表示用戶c和用戶d對項目的平均評分。

2)計算出項目的預測評分后，通過比較，選擇評分最低的前N個項目作為最終的推薦結果，傳送給Web服務器，反饋給用戶。

4 實驗及結果分析

實驗平臺使用CPU(Intel T2080 D-0 1.73G)，1 Gbyte內存，操作系統為Windows XP，語言為C++標準庫和MATLAB。

4.1 實驗數據

此次實驗的數據集是一個著名的站點MovieLens提供的(http://movielens.umn.edu)，MovieLens是一個基于Web的研究型推薦系統，主要是用來記錄用戶對電影的評分等。數據集中包括用戶關于視頻的評分數據(評分值從1～5的整數)，用戶之間信任關系評分數據(用戶之間存在信任關系評分為1，否則為0)，整理出視頻的屬性關系(視頻屬于某一分類則值為1，否則為0)。

4.2 度量標準

本文采用的評價推薦系統推薦質量的標準是平均絕對偏差(Mean Absolute Error，MAE)［11］。通過計算用戶的預測評分和實際評分之間的偏差，來評價預測的精確性，偏差值MAE越小，推薦質量就越高。設用戶的預測評分集合為{p1，p2，…，pn}，用戶實際評分為{s1，s2，…，sn}，平均絕對偏差MAE可通過下式計算得到

4.3 實驗結果及分析

4.3.1 實驗1

實驗選取不同的權重值α來獲得不同的推薦效果。取定推薦視頻數n的值10。取最近鄰居數k的值為15，20，25，30。設置控制相似度和信任度比例的變量α的取值為0，0.2，0.4，0.6，0.8，1.0，MAE值隨著α值的變化而變化。結果如圖2所示。

圖2 實驗1結果

從圖2的實驗結果，可以看出最近鄰用戶數目越多，預測評分和實際評分的平均絕對偏差MAE值最小，即推薦效果越好。在不同的鄰居用戶數下，當α取值接近0.7時都取得最好的推薦效果。

4.3.2 實驗2

根據實驗1中的結果，取推薦結果最好時，α的值為0.7。對改進的協同過濾推薦算法和傳統的協同過濾推薦算法的性能進行比較。取最近鄰居數k的值為10，15，20，25，30，觀察MAE值。實驗結果如圖3所示。

圖3 兩種算法實驗結果對比

MAE值越小，推薦效果越好，從實驗結果可以看出，改進的協同過濾組合推薦算法的MAE值最小，可見本文提出的改進算法推薦性能優于傳統算法。

5 結束語

網絡電視正在快速發展，如何為用戶提供更加準確和有效的信息是很重要的任務，個性化推薦系統是完成這一任務的關鍵。本文提出的改進算法，把聚類分析用于協同過濾推薦中，相對于原始用戶空間而言，由聚類產生的用戶搜索空間變小，從而使得最近鄰用戶搜索的效率變高，有效提高推薦算法的實時響應速度。首先，使用信任度與相似度結合作為搜索最近鄰用戶的標準將更加精確。其次，信任度的計算并不依賴于用戶對視頻的評分數量，即使評分數量不多，只要有用戶之間的信任評分，就可以搜索到一定數量的鄰居用戶，并做出推薦，解決了“冷啟動”問題。實驗研究結果也表明，組合推薦算法更加精確，達到了更好的推薦效果。

［1］ADOMAVICIUS Q TUZHILIN A.Toward the next generation of recommender systems:a survey of the state-of-the-art and possible extensions［J］.IEEE Trans.on Knowledge and Data Engineering，2005，17(6):734-749.

［2］SARWAR B M.Sparsity，scalability，and distribution in recommender systems［D］.Minneapolis，MN:University of Minnesota，2001.

［3］YU Li，LIU Lu，LI Xuefeng.A hybrid collaborative filtering method for multiple-interests and multiple-content recommendation in e-commerce［J］.Expert Systems with Applications，2005，17(4):67-77.

［4］陳萌，楊成，王歡，等.交互式電視中個性化推薦系統的研究［J］.電視技術，2012，36(14):37-40.

［5］BRIN S，MOTWANI R，ULLMAN J D，et al.Dynamic itemset counting and implicate on rules for market basket data［C］//Proc.SIGMOD Record.California:［s.n.］，2007:33-43.

［6］譚勇，榮秋生.一個基于K-means的聚類算法的實現［J］.湖北民族學院學報，2004，22(1):69-71.

［7］ZHOU Qiang.Researches into recommendatory algorithm of coordinated filtration in view of consummers［J］.Journal of Nanchang Junior College，2006，15(3):88-89.

［8］GOLBECK J.Computing and applying trust in web-based social networks［D］.Maryland:University of Maryland，2005.

［9］曾子明，余小鵬.電子商務推薦系統與智能談判技術［M］.武漢:武漢大學出版社，2008.

［10］徐翔，王煦法.協同過濾算法中的相似度優化方法［J］.計算機工程，2010，36(6 ):52-54.

［11］MCLAUGHLIN M R，HERLOCKER J L.A collaborative filtering algorithm and evaluation metric that accurately model the user experience［C］//Proc.27th annual international ACM SIGIR conference on Research and development in information retrieval.Sheffield，United Kingdom:ACM，2004:329-336.