一種基于子周期社區(qū)挖掘的電視節(jié)目推薦方法

廉 飚，王 莉，裴艷艷

（太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原030024）

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

筆者針對(duì)數(shù)字電視發(fā)展關(guān)鍵技術(shù)之一：數(shù)字電視節(jié)目智能個(gè)性化推薦技術(shù)進(jìn)行了研究，擬在通過歷史觀看數(shù)據(jù)學(xué)習(xí)出觀看電視頻道的模型，當(dāng)用戶打開電視機(jī)時(shí)，自動(dòng)根據(jù)學(xué)習(xí)到的模型列出推薦列表向用戶推薦電視頻道，縮短用戶選臺(tái)時(shí)間，實(shí)現(xiàn)智能服務(wù)。

1 相關(guān)推薦技術(shù)研究

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，越來越多的人選擇在網(wǎng)絡(luò)上進(jìn)行娛樂或購物。面對(duì)日益擴(kuò)大的用戶需求，以及越來越豐富的資源，如何能夠充分理解用戶的需求，快捷地為用戶找到自己需要的資源，成為吸引用戶的一個(gè)有力手段?；诖诵枨?，個(gè)性化推薦技術(shù)漸漸受到重視，如今已經(jīng)進(jìn)入一個(gè)成熟發(fā)展的階段［2］。

推薦技術(shù)最關(guān)鍵就是高效的個(gè)性化推薦算法。目前主流的個(gè)性化推薦算法有：基于關(guān)聯(lián)規(guī)則的推薦算法［3］、基于內(nèi)容的推薦算法［4］、協(xié)同過濾技術(shù)［5－7］。這些方法都沒有考慮到人們觀看電視具有周期性，比如每周末看湖南衛(wèi)視快樂大本營(yíng)，所以筆者提出基于子周期社區(qū)挖掘的電視節(jié)目推薦方法。

2 基于子周期社區(qū)挖掘的電視節(jié)目推薦方法

2．1 用戶數(shù)據(jù)收集

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

另外，我們可以設(shè)定系數(shù)s為最低觀看時(shí)長(zhǎng)，如果用戶觀看時(shí)長(zhǎng)小于s的話，則不列入學(xué)習(xí)數(shù)據(jù)集中。本文收集了2012年11月份某10個(gè)用戶家庭觀看電視節(jié)目的數(shù)據(jù)來進(jìn)行仿真實(shí)驗(yàn)。

2．2 子周期社區(qū)發(fā)現(xiàn)算法

在動(dòng)態(tài)社區(qū)的研究領(lǐng)域中，尋找社區(qū)結(jié)構(gòu)并對(duì)其進(jìn)行分析是了解現(xiàn)實(shí)生活中各種網(wǎng)絡(luò)組織結(jié)構(gòu)的一種很重要的方法，其在生物學(xué)、計(jì)算機(jī)科學(xué)以及社會(huì)學(xué)等領(lǐng)域都有著廣泛的應(yīng)用［8，9］。本文分析動(dòng)態(tài)社區(qū)內(nèi)部元素的的周期性，利用用戶觀看電視節(jié)目的歷史數(shù)據(jù)作為動(dòng)態(tài)社區(qū)，挖掘出蘊(yùn)含的周期子社區(qū)作為依據(jù)來進(jìn)行推薦。我們采用Mayank Lahiri等人提出的PSM（Periodic subgraph Mining）算法［10］。此算法核心是模式樹的更新，能夠支持動(dòng)態(tài)的輸入數(shù)據(jù)發(fā)現(xiàn)所有的周期子社區(qū)。

圖1 一個(gè)動(dòng)態(tài)社區(qū)圖變化的例子

圖1中是一個(gè)動(dòng)態(tài)社區(qū)變化的例子，每個(gè)t是一個(gè)時(shí)間片，我們現(xiàn)在只考慮兩點(diǎn)之間的邊重現(xiàn)的規(guī)律（一個(gè)圖中我們?nèi)绻肋呉约斑叺膬啥?，顯然可以得出點(diǎn)），然后圖2給出將圖1中的數(shù)據(jù)動(dòng)態(tài)地輸入算法中的時(shí)候，算法中模式樹的更新步驟（具體內(nèi)容參照文獻(xiàn)［10，11］）。

圖2 每個(gè)時(shí)步下模式樹更新示意圖（節(jié)點(diǎn)內(nèi)只包含社區(qū)圖的邊）

圖2中葉子節(jié)點(diǎn)下都有描述符號(hào)S，S表示一個(gè)支持集，定義如下：給出一個(gè)含有t個(gè)時(shí)步的動(dòng)態(tài)圖G和一個(gè)任意的圖F＝（V，E），支持集S（F）表示為

也就是S（F）集合中的時(shí)步t下，F(xiàn)是G的子集，則｜S（F）｜為子社區(qū)F出現(xiàn)的次數(shù)。

時(shí)間t＝1時(shí)，四條邊加入根節(jié)點(diǎn)為空的樹中并建立錨節(jié)點(diǎn)S＝｛1｝p＝0。t＝2時(shí)動(dòng)態(tài)社區(qū)為空，沒有出現(xiàn)任何邊，不處理；t＝3時(shí)，四條邊重現(xiàn)，所以新加入一個(gè)錨節(jié)點(diǎn)S＝｛3｝p＝0，并且得出S＝｛1，3｝p＝2；t＝4時(shí)，邊（1，2）（1，3）重現(xiàn)，這兩條邊是以前四條邊的一個(gè)子集，樹的子節(jié)點(diǎn)中并沒有這兩條邊的節(jié)點(diǎn)，我們就在這個(gè)節(jié)點(diǎn)下新建一個(gè)樹節(jié)點(diǎn)，然后設(shè)定錨節(jié)點(diǎn)S＝｛4｝p＝0并且計(jì)算得出S＝｛1，4｝p＝3，S＝｛3，4｝p＝1；t＝5時(shí)，邊（1，4）（1，5）重現(xiàn)，對(duì)比發(fā)現(xiàn)也是四條邊的一個(gè)子集，并且在他的子節(jié)點(diǎn)沒有這兩條邊的節(jié)點(diǎn)，所以在這個(gè)四條邊的節(jié)點(diǎn)下重新建一個(gè)樹節(jié)點(diǎn)，然后設(shè)定錨節(jié)點(diǎn)S＝｛5｝p＝0并且計(jì)算得出出S＝｛1，3，5｝p＝2，S＝｛1，5｝p＝4。

一般情況下，我們?cè)O(shè)定一個(gè)周期子社區(qū)最少頻次應(yīng)該是3，也就是周期性地出現(xiàn)3次才能稱為周期社區(qū)｛即：｜S｜≥3｝?？梢妶D2中S＝｛1，3，5｝p＝2的樹節(jié)點(diǎn)是邊（1，4）（1，5）。也就是圖1中邊（1，4）（1，5）是一個(gè)周期是2的子社區(qū)。其中邊（1，2）（1，3）雖然也出現(xiàn)了3次，但是出現(xiàn)的間隔時(shí)間不等，也就是說不是周期性地出現(xiàn)，所以不能稱為周期子社區(qū)。

2．3 生成節(jié)目推薦單

將一天內(nèi)觀看的所有電視節(jié)目組成一個(gè)社區(qū)，動(dòng)態(tài)地輸入算法中進(jìn)行周期子社區(qū)挖掘，得出多個(gè)用戶周期性觀看節(jié)目所組成的社區(qū)。當(dāng)用戶在某個(gè)時(shí)刻打開電視機(jī)的時(shí)候，根據(jù)已有周期子社區(qū)，列出有可能在當(dāng)天看的電視頻道。如圖2中，當(dāng)進(jìn)入時(shí)間片7，根據(jù)S＝｛1，3，5｝p＝2，邊（1，4）（1，5）這個(gè)子社區(qū)就極有可能出現(xiàn)，所以應(yīng)當(dāng)列入推薦列表當(dāng)中。

圖3 挖掘出周期子社區(qū)存入數(shù)據(jù)庫中截圖

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

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

3 仿真實(shí)驗(yàn)及方法對(duì)比分析

當(dāng)前的主流推薦方法有基于關(guān)聯(lián)規(guī)則的推薦算法、基于內(nèi)容的推薦算法和協(xié)同過濾技術(shù)三種方法。

1）基于內(nèi)容的推薦方法只適用于文本內(nèi)容推薦，不適合做電視節(jié)目推薦。

2）基于關(guān)聯(lián)規(guī)則的推薦算法的原理是：在超市購物中大多數(shù)用戶購買a產(chǎn)品的同時(shí)購買b產(chǎn)品，那么新的用戶在購買了a產(chǎn)品后，將b產(chǎn)品推薦給他，應(yīng)用電視節(jié)目的推薦當(dāng)中，可以作為一種推薦方法。我們?cè)谶@里給出生成推薦列表的過程，將每個(gè)家庭、每天看的電視節(jié)目?jī)蓛蓪?duì)應(yīng)做邊，按邊數(shù)進(jìn)行排序，邊數(shù)最多的關(guān)聯(lián)性最強(qiáng)，由此產(chǎn)生推薦列表。

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

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

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

圖4 推薦并且被收看的節(jié)目個(gè)數(shù)與所有收看節(jié)目的個(gè)數(shù)對(duì)比圖

結(jié)果分析：首先我們將準(zhǔn)確度定義為：準(zhǔn)確度＝推薦并且被收看的節(jié)目數(shù)／所有收看的節(jié)目數(shù)?？捎蓤D中計(jì)算出本算法的準(zhǔn)確度七天中最大為83%，最小為50%。而協(xié)同過濾推薦算法的準(zhǔn)確度與本算法相差不多，關(guān)聯(lián)規(guī)則算法準(zhǔn)確度最低。而且從結(jié)果中我們還能看出，到了周末（23，24號(hào)兩天）由于用戶休息時(shí)間長(zhǎng)，看電視節(jié)目多，這幾個(gè)推薦算法的準(zhǔn)確度都有所降低。

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

4 總結(jié)

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

［1］ 趙清華，張懿．機(jī)頂盒中文智能化用戶界面的軟件實(shí)現(xiàn)［J］．太原理工大學(xué)學(xué)報(bào)，2003，34（1）：93－95．

［2］ 曾春，邢春曉，周立柱．個(gè)性化服務(wù)技術(shù)綜述［J］．軟件學(xué)報(bào)，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］ 徐江山，盧增祥，路海明，李衍達(dá)．?dāng)?shù)字電視節(jié)目推薦系統(tǒng)中的統(tǒng)計(jì)算法［J］．清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，68（10）：1562－1564．

［6］ 鄧愛林，左子葉，朱揚(yáng)男．基于項(xiàng)目聚類的協(xié)同過濾推薦算法［J］．小型微型計(jì)算機(jī)系統(tǒng)，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］ 王莉，張景陽，徐李恒．動(dòng)態(tài)網(wǎng)絡(luò)中基于局部介數(shù)的重疊社區(qū)發(fā)現(xiàn)算法［J］．山東大學(xué)學(xué)報(bào)，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．