一種基于子周期社區挖掘的電視節目推薦方法

廉 飚，王 莉，裴艷艷

（太原理工大學 計算機科學與技術學院，太原030024）

20世紀是廣播電視統治世界的時代，人們主要通過它來獲取信息以及媒體娛樂資源。進入21世紀以來，數字技術開創了電視的新紀元，電視的含義已經不僅僅是傳統的音視頻廣播，而且是可以提供豐富信息和娛樂業務的雙向交互式媒體。在此背景下，數字電視機頂盒也演變為一個綜合性的家庭多媒體娛樂與信息服務平臺。目前眾多機頂盒產品中，除了提供基本的電視解碼功能外，能否提供友好、簡潔、功能強大的中文智能化用戶界面也是機頂盒產品能否有力占有市場的一個重要因素［1］。從發展趨勢來看，機頂盒為用戶提供的服務主要集中在標準化、智能化和大容量存儲三個關鍵技術方向。

筆者針對數字電視發展關鍵技術之一：數字電視節目智能個性化推薦技術進行了研究，擬在通過歷史觀看數據學習出觀看電視頻道的模型，當用戶打開電視機時，自動根據學習到的模型列出推薦列表向用戶推薦電視頻道，縮短用戶選臺時間，實現智能服務。

1 相關推薦技術研究

隨著互聯網技術的發展，越來越多的人選擇在網絡上進行娛樂或購物。面對日益擴大的用戶需求，以及越來越豐富的資源，如何能夠充分理解用戶的需求，快捷地為用戶找到自己需要的資源，成為吸引用戶的一個有力手段。基于此需求，個性化推薦技術漸漸受到重視，如今已經進入一個成熟發展的階段［2］。

推薦技術最關鍵就是高效的個性化推薦算法。目前主流的個性化推薦算法有：基于關聯規則的推薦算法［3］、基于內容的推薦算法［4］、協同過濾技術［5－7］。這些方法都沒有考慮到人們觀看電視具有周期性，比如每周末看湖南衛視快樂大本營，所以筆者提出基于子周期社區挖掘的電視節目推薦方法。

2 基于子周期社區挖掘的電視節目推薦方法

2．1 用戶數據收集

本方法在學習用戶行為時，收集數據為：在用戶觀看電視時，記錄下用戶所看電視的頻道及觀看此頻道的起始時間和時長。如用戶每晚收看新聞聯播時記錄為“1，2012－11－05 19：05，25，30”（頻道，日期，起始時間，觀看時長，此節目時長），也就是說該用戶11月5號，在19：05開始觀看新聞聯播，觀看了25分鐘，最后一個參數表示新聞聯播時長共30分鐘。若用戶每天觀看，則模型學習完成后，用戶在任何一天的19：00到19：30之間打開視機的話，此時推薦菜單就應該將1頻道放在第一位。

另外，我們可以設定系數s為最低觀看時長，如果用戶觀看時長小于s的話，則不列入學習數據集中。本文收集了2012年11月份某10個用戶家庭觀看電視節目的數據來進行仿真實驗。

2．2 子周期社區發現算法

在動態社區的研究領域中，尋找社區結構并對其進行分析是了解現實生活中各種網絡組織結構的一種很重要的方法，其在生物學、計算機科學以及社會學等領域都有著廣泛的應用［8，9］。本文分析動態社區內部元素的的周期性，利用用戶觀看電視節目的歷史數據作為動態社區，挖掘出蘊含的周期子社區作為依據來進行推薦。我們采用Mayank Lahiri等人提出的PSM（Periodic subgraph Mining）算法［10］。此算法核心是模式樹的更新，能夠支持動態的輸入數據發現所有的周期子社區。

圖1 一個動態社區圖變化的例子

圖1中是一個動態社區變化的例子，每個t是一個時間片，我們現在只考慮兩點之間的邊重現的規律（一個圖中我們如果知道邊以及邊的兩端，顯然可以得出點），然后圖2給出將圖1中的數據動態地輸入算法中的時候，算法中模式樹的更新步驟（具體內容參照文獻［10，11］）。

圖2 每個時步下模式樹更新示意圖（節點內只包含社區圖的邊）

圖2中葉子節點下都有描述符號S，S表示一個支持集，定義如下：給出一個含有t個時步的動態圖G和一個任意的圖F＝（V，E），支持集S（F）表示為

也就是S（F）集合中的時步t下，F是G的子集，則｜S（F）｜為子社區F出現的次數。

時間t＝1時，四條邊加入根節點為空的樹中并建立錨節點S＝｛1｝p＝0。t＝2時動態社區為空，沒有出現任何邊，不處理；t＝3時，四條邊重現，所以新加入一個錨節點S＝｛3｝p＝0，并且得出S＝｛1，3｝p＝2；t＝4時，邊（1，2）（1，3）重現，這兩條邊是以前四條邊的一個子集，樹的子節點中并沒有這兩條邊的節點，我們就在這個節點下新建一個樹節點，然后設定錨節點S＝｛4｝p＝0并且計算得出S＝｛1，4｝p＝3，S＝｛3，4｝p＝1；t＝5時，邊（1，4）（1，5）重現，對比發現也是四條邊的一個子集，并且在他的子節點沒有這兩條邊的節點，所以在這個四條邊的節點下重新建一個樹節點，然后設定錨節點S＝｛5｝p＝0并且計算得出出S＝｛1，3，5｝p＝2，S＝｛1，5｝p＝4。

一般情況下，我們設定一個周期子社區最少頻次應該是3，也就是周期性地出現3次才能稱為周期社區｛即：｜S｜≥3｝。可見圖2中S＝｛1，3，5｝p＝2的樹節點是邊（1，4）（1，5）。也就是圖1中邊（1，4）（1，5）是一個周期是2的子社區。其中邊（1，2）（1，3）雖然也出現了3次，但是出現的間隔時間不等，也就是說不是周期性地出現，所以不能稱為周期子社區。

2．3 生成節目推薦單

將一天內觀看的所有電視節目組成一個社區，動態地輸入算法中進行周期子社區挖掘，得出多個用戶周期性觀看節目所組成的社區。當用戶在某個時刻打開電視機的時候，根據已有周期子社區，列出有可能在當天看的電視頻道。如圖2中，當進入時間片7，根據S＝｛1，3，5｝p＝2，邊（1，4）（1，5）這個子社區就極有可能出現，所以應當列入推薦列表當中。

圖3 挖掘出周期子社區存入數據庫中截圖

將前面收集到的數據運行算法后挖掘出的子周期社區放入數據庫如圖3。start表示起始時間，frequency表示這個周期社區已經循環出現的次數，peri－od表示周期，channels表示電視頻道。如第一條數據就表示：頻道1，5，6，34從3號開始，每隔7天都會觀看并且到3＋2×7＝17號為止，已經觀看了3次，下次極有可能在3＋3×7＝24號出現。用戶如果在24號打開電視機，首先考慮的就是這幾個頻道。

我們列出有可能觀看的頻道后，要對其進行排序，當前時間跟歷史數據中觀看此頻道的時間是首要參考的。當時間沖突時候，我們利用參數frequency和period來進行對比排序，原則上周期大的穩定性比周期小的穩定性要高，比如每周末晚九點看頻道江蘇衛視非誠勿擾，周一到周五看某個頻道的連續劇。前者周期是7后者周期是1。到周末的話還是會看江蘇衛視，所以應該提前，如果周期相等那么頻率高的當然比低的靠前。

3 仿真實驗及方法對比分析

當前的主流推薦方法有基于關聯規則的推薦算法、基于內容的推薦算法和協同過濾技術三種方法。

1）基于內容的推薦方法只適用于文本內容推薦，不適合做電視節目推薦。

2）基于關聯規則的推薦算法的原理是：在超市購物中大多數用戶購買a產品的同時購買b產品，那么新的用戶在購買了a產品后，將b產品推薦給他，應用電視節目的推薦當中，可以作為一種推薦方法。我們在這里給出生成推薦列表的過程，將每個家庭、每天看的電視節目兩兩對應做邊，按邊數進行排序，邊數最多的關聯性最強，由此產生推薦列表。

3）基于協同過濾的推薦算法的原理是：根據用戶操作的歷史信息計算內容之間的相似性，根據相似性大小排序得出與目標最相似的k個鄰居。預測目標用戶的行為時可根據這k個鄰居的行為進行預測。生成推薦列表過程為：先根據歷史記錄中用戶每天觀看頻道相似度進行對比，計算出用戶相似度，對目標用戶生成推薦列表時，按用戶相似度進行由高到低排序，推薦相似度較高用戶正在觀看的頻道。

本文在實驗中設定參數s＝15（用戶觀看一個頻道超過15min就對此頻道進行記錄），收集了2012年11月份，上班人群中10個家庭（為了能夠方便地進行協同過濾推薦，選擇年齡段在40到50歲之間用戶家庭，分別編號為1—10）的觀看電視節目的數據來進行仿真對比實驗。

首先根據前三周的電視節目進行學習，然后對第四周用戶觀看電視節目做預測，對比真實數據與預測數據差異，對推薦方法進行對比分析。我們發現2012年11月1日是周四，所以我們將前三周（也就是22號之前）的數據進行算法的學習，將編號為10的家庭作為目標家庭進行推薦。將推薦列表與真實的用戶看的頻道進行對比分析，本次實驗中，由于要對算法做對比，推薦列表不宜過長，我們暫定其長度為3。在推薦的3個節目中只要用戶觀看任何一個，我們就視為推薦命中。23號到29號（周六到下周五）7天中用戶收看節目數與推薦算法的命中數對比如圖4。

圖4 推薦并且被收看的節目個數與所有收看節目的個數對比圖

結果分析：首先我們將準確度定義為：準確度＝推薦并且被收看的節目數／所有收看的節目數。可由圖中計算出本算法的準確度七天中最大為83%，最小為50%。而協同過濾推薦算法的準確度與本算法相差不多，關聯規則算法準確度最低。而且從結果中我們還能看出，到了周末（23，24號兩天）由于用戶休息時間長，看電視節目多，這幾個推薦算法的準確度都有所降低。

本算法相對于協同過濾算法，雖然在準確度上不相上下，但是由于在收集數據時，我們選擇的都是年齡段40～50的上班用戶，這本身就增加了用戶的相似度，對協同過濾算法的效果有一定的增益。而本算法只對目標用戶的數據進行分析，不需要參考其他用戶的數據（協同過濾算法要參照對比相似用戶，無論是數據收集還是實時性上都處于劣勢），體現了本算法的優勢。綜上所述，本方法作為一種推薦方法，優于現有的其他推薦算法。

4 總結

筆者通過分析歷史觀看數據，得出用戶觀看電視的周期性的規律，生成推薦列表向用戶推薦電視頻道，以達到縮短用戶選臺時間，實現智能服務的目的，并且在真實的數據上做實驗，證明了本算法比其他算法優越。但是此方法還存在不足：本算法在人們作息時間規律性較強的情況下比其他算法優越，比如上班人群。若作息時間不規律，看電視節目當然也不規律，就很難根據歷史數據學習出周期性的規律。而且由于觀看電視人群的多樣性，很難給出一種適用于所有情況，并且在所有情況下測試都效果較好的推薦方法，這就需要在后續的研究中深入分析，綜合各種推薦方法才能提高性能從而進行推廣。

［1］ 趙清華，張懿．機頂盒中文智能化用戶界面的軟件實現［J］．太原理工大學學報，2003，34（1）：93－95．

［2］ 曾春，邢春曉，周立柱．個性化服務技術綜述［J］．軟件學報，2002，13（10）：1952－1961．

［3］ Sandvig J J，Mobasher B，Robin Burke．Robustness of collaborative recommendation based on association rule mining［C］∥Proceedings of the 2007ACM conference on Recommendersystems，2007：105－112．

［4］ Michael J Pazzani，Daniel Billsus．The Adaptive Web［M］．USA，New york：Springer Berlin Heidelberg，2007：325－344．

［5］ 徐江山，盧增祥，路海明，李衍達．數字電視節目推薦系統中的統計算法［J］．清華大學學報（自然科學版），2008，68（10）：1562－1564．

［6］ 鄧愛林，左子葉，朱揚男．基于項目聚類的協同過濾推薦算法［J］．小型微型計算機系統，2004，25（9）：1665－1670．

［7］ IE Shparlinski．On some weighted Average Values of L－function［J］．Bulletin of the Australian Mathematical Society，2009，79：183－186．

［8］ 王莉，張景陽，徐李恒．動態網絡中基于局部介數的重疊社區發現算法［J］．山東大學學報，2011，45（5）：86－90．

［9］ Li wang．SoFA：An expert－driven，self－organization peerto－peer semantic communities for network resource management［J］．Expert Systems With Applications，2011，38（1）：94－105．

［10］ W Aref，M Elfeky．A elmagarmid，incremental，online and merge mining of partial periodic patterns in time－series databases［J］．IEEE Transactions Knowledge and Data Engineering，2004，16（3）：332－342．

［11］ Lahiri M，Berger－Wolf T．Periodic subgraph mining in dynamic networks［J］．Knowledge and Information Systems，2010（24）：467－497．