陳 建,王子磊,奚宏生

(中國科學(xué)技術(shù)大學(xué) 自動化系,合肥 230027)

0 概述

目前,大多數(shù)的電視節(jié)目推薦系統(tǒng)直接采用網(wǎng)站視頻推薦方法。文獻(xiàn)[1]采用基于內(nèi)容的推薦方法,利用聚類技術(shù)訓(xùn)練出向量空間模型形式的用戶興趣;文獻(xiàn)[2]使用協(xié)同過濾推薦方法中的SVD模型,研究如何為用戶推薦電視視頻。還有一些電視推薦系統(tǒng)采用了混合策略[3-4],將協(xié)同過濾和基于內(nèi)容的推薦方法結(jié)合使用。然而廣播電視和網(wǎng)站視頻的觀看場景存在著很大的差異。首先,電視用戶為多成員用戶,家庭用戶的收視興趣是所有成員用戶收視興趣的復(fù)合形式;其次,成員自由組合,形成了多種觀看模式,用戶的收視興趣存在頻繁遷移的現(xiàn)象。因此,直接應(yīng)用網(wǎng)站視頻推薦方法來實現(xiàn)電視節(jié)目推薦,效果難以保證。

針對廣播電視用戶的多成員用戶問題,一些工作通過識別家庭成員來改善電視推薦系統(tǒng)的性能[5]。ACM在2010年和2011年舉辦了情境感知電影推薦競賽[6](CAMRa),參賽者以家庭為群組單位,實現(xiàn)對家庭成員的識別,并向一個家庭推薦節(jié)目。參賽者大多采用分類預(yù)測模型,取得了一定的效果。但是這些工作都是建立在家庭成員構(gòu)成已知的情況下,在實際情況下,成員組成情況往往是難以獲得的。另外,家庭用戶的某個觀看模式,不一定只對應(yīng)單個成員,而是某些成員組合而成的觀看群組[7]。因此,在家庭成員組成未知的情況下,是無法采用分類模型來解決電視推薦問題的。

在家庭用戶結(jié)構(gòu)未知的情況下,在特定的時段,多個成員組合形成觀看群組,觀看群組的收視興趣可以代表家庭用戶在此時段的收視興趣。文獻(xiàn)[8]利用時間信息,將收視記錄按照時段進(jìn)行聚類操作;文獻(xiàn)[9]利用時間維度信息,將家庭的總興趣模擬為多個“偽用戶”興趣的組合,通過識別每個家庭的“偽用戶”來提高推薦系統(tǒng)精確度。這些研究工作利用時間情境信息將復(fù)合的家庭用戶收視興趣劃分為分時段的用戶子興趣,在一定程度上緩解了因用戶興趣的復(fù)合特征而造成推薦精度下降的問題。但是,僅考慮用戶的時段興趣效應(yīng)是不充足的,電視節(jié)目類型十分豐富,致使相同時段播放的節(jié)目也可能是不同類別的成員所感興趣的,興趣復(fù)合性問題依然存在。

為解決廣播用戶收視興趣復(fù)合性問題,并發(fā)現(xiàn)收視興趣相似的多家庭用戶群組,本文提出一種基于時間情境感知的電視用戶群組發(fā)現(xiàn)策略。其中,收視記錄中的觀看時間是本文所使用的情境參量。具體為采用張量分解來獲取節(jié)目和收視時間的隱性特征矩陣,無需使用深度EPG中的節(jié)目本體數(shù)據(jù)[10];利用馬爾可夫聚類算法實現(xiàn)對收視記錄的分類,并根據(jù)記錄分類結(jié)果發(fā)現(xiàn)用戶群組。用戶群組以家庭為單位,群組內(nèi)每個家庭的收視興趣在收視時間和收視內(nèi)容上均相似。

1 問題描述

電視群組推薦系統(tǒng)的目標(biāo)是為群組推薦電視節(jié)目或視頻,群組構(gòu)建的基本原則是各成員在收視興趣上保持相似。因此,如何確定用戶群組是實現(xiàn)群組推薦系統(tǒng)的關(guān)鍵。本文所要解決的問題是:有效利用時間情境和節(jié)目特征信息,發(fā)現(xiàn)在收視時間和收視內(nèi)容上均相似的用戶群組。表1為本文中所定義的概念符號及其簡略解釋。

表1 符號定義及描述

典型家庭用戶群組觀看模式的一般場景為:單個家庭用戶由多個家庭成員組成,在某個時段s,某些家庭用戶對節(jié)目組ps感興趣,這些家庭用戶構(gòu)成了一個用戶群組。另外可以認(rèn)為在時間段s,這些家庭用戶均具有相似的興趣。在其他時段,同樣對應(yīng)著相應(yīng)的用戶群組。一個家庭用戶可以被劃分到多個用戶群組中。圖1給出了電視用戶分時段群組構(gòu)成的一個概念例子:4個電視用戶在3個時段上觀看了電視節(jié)目,每個時段對應(yīng)著一組節(jié)目。某些用戶由于在同一時段體現(xiàn)了對同一組節(jié)目的興趣,因此這些用戶被劃分為一個用戶群組(如圖1所示的3個群組)。

圖1 電視用戶分時段群組構(gòu)成示例

基于以上考慮,將收視時間特征和收視內(nèi)容特征作為重要的數(shù)據(jù)源。輸入的數(shù)據(jù)集中包括每個家庭用戶的收視情況。通過數(shù)據(jù)預(yù)處理,可以得到用戶-節(jié)目-時間-觀看時長這樣的記錄模式。為了精簡地表達(dá)時間信息,需要手動將時間維度信息進(jìn)行離散化處理,即將24 h劃分為不相交的若干時段,即:

(1)

根據(jù)離散化的時段,計算用戶在每個時段sl對節(jié)目的評分,并構(gòu)建三維的評分張量R∈NU×NP×|S|。第一步所要完成的是以R為輸入,訓(xùn)練出節(jié)目特征矩陣V以及時間特征矩陣T。矩陣V和矩陣T為后續(xù)分析記錄之間的相似性提供了依據(jù)。記錄a∈A具有2個屬性,即記錄所對應(yīng)的節(jié)目a.p和對應(yīng)的收視時段a.s。

設(shè)在時段集合Sb?S,興趣相似的家庭用戶分為一組,形成了用戶數(shù)為Nb的用戶群組:

(2)

其中,csi表示時段集合s對應(yīng)的用戶簇cs中的第i個用戶,則對于時段集合S而言,用戶群組總集合可表示為:

(3)

本文的主要目標(biāo)就是以記錄集合A為輸入來發(fā)現(xiàn)用戶群組總集合C,并針對C中的每一個群組推薦節(jié)目。實現(xiàn)這個過程需要解決2個關(guān)鍵問題:在沒有深度EPG數(shù)據(jù)的情況下實現(xiàn)對節(jié)目的聚類;發(fā)現(xiàn)觀看時間和觀看內(nèi)容均相似的用戶群組。

2 群組發(fā)現(xiàn)策略

為解決問題定義中提出的2個主要問題:本文采用張量Tucker分解模型獲取用戶、節(jié)目以及時間這3個維度的特征矩陣;以時間、節(jié)目特征矩陣分別作為收視記錄的屬性特征,應(yīng)用馬爾可夫聚類(MCL)算法完成群組發(fā)現(xiàn)工作。

2.1 隱性特征獲取

在基于內(nèi)容的推薦方法中,通常需要使用項目的特征信息,以便于通過聚類、TF-IDF等算法來訓(xùn)練用戶的特征偏好。在電視節(jié)目推薦問題中,一般也是根據(jù)深度EPG數(shù)據(jù)來訓(xùn)練用戶對節(jié)目的偏好模型[7,10-12]。由于節(jié)目本體信息存在于深度EPG數(shù)據(jù)中,而深度EPG數(shù)據(jù)通常難以獲取,因此本文未使用節(jié)目的本體信息,而是利用張量分解模型來自動學(xué)習(xí)出節(jié)目的特征向量,這些特征是通常被稱為隱性特征。同理,還可以學(xué)習(xí)出時間維度上的特征向量。隱性特征可以代表節(jié)目和時間的屬性特征,這樣不同的節(jié)目和時間就可以進(jìn)行相似比較,在此基礎(chǔ)上就能實現(xiàn)對節(jié)目和時間的聚類。

張量分解模型是矩陣分解模型在多維空間上的推廣。張量分解有多種形式,目前比較流行的分解有Tucker分解和CP分解。本文選擇Tucker分解模型來獲取隱性特征矩陣。Tucker分解將張量分解成為一個核心張量沿每一階乘上一個矩陣。本文在用戶-節(jié)目-時間3個維度所構(gòu)建的評分張量R∈NU×NV×|S|上做Tucker分解,其中rups∈R表示為用戶u在時段s對節(jié)目p的偏好評分。R是一個稀疏的張量,每一個元素都對應(yīng)著一條隱式評分記錄,采用式(4)計算R中的非空值:

(4)

其中,nups表示用戶u在時段s觀看節(jié)目p的次數(shù),dupsi為用戶u第i次觀看節(jié)目p所占用的時間,ts為時段s所占的總時長(以分鐘計)。最終計算得到的評分的范圍區(qū)間為[0,10]。

對于張量R,其分解式為:

R=M×UU×VV×TT

(5)

即張量R可分解為矩陣U∈NU×dU,T∈|T|×dT,V∈NP×dV和核心稠密張量M∈dU×dV×dT,×U表示張量與矩陣的乘法。矩陣V表示的是節(jié)目的隱式特征矩陣,其每一行代表著一個節(jié)目的隱性特征,節(jié)目之間的特征相似度可以通過比較它們各自的隱性特征來獲得。同理,對于矩陣T也是如此。學(xué)習(xí)上述3個矩陣和核心張量,需要最小化式(6)所示的損失函數(shù):

(6)

其中,第2項和第3項是為了避免模型過擬合而設(shè)置的正則項,且有:

(7)

本文采用隨機梯度下降法(SGD)來學(xué)習(xí)隱性特征矩陣V、T。首先定義矩陣V、T中的行向量,即vj*表示V的第j行,tk*表示T的第k行。SGD首先計算損失函數(shù)的梯度,如式(8)～式(11)所示。

(8)

(9)

(10)

(11)

根據(jù)上述計算得到的梯度可以用來更新特征行向量和核心張量,更新行向量的公式為:

(12)

(13)

(14)

(15)

其中,η為學(xué)習(xí)率,它表示SGD的學(xué)習(xí)速率。在實際執(zhí)行SGD時,首先是選定一個迭代次數(shù)d,根據(jù)評分矩陣R的評分項劃分好訓(xùn)練集和測試集,并用隨機值初始化矩陣U、V、T以及核心張量M。然后針對評分矩陣R中的每一項評分,根據(jù)式(12)～式(15)計算梯度并更新行向量和核心張量。經(jīng)過d次迭代,可以獲得矩陣U、V中的任意行向量。

在隱性特征獲取的過程中,dU、dV和dT的值可以自由選擇,但為了保證M的稠密性,一般都設(shè)置為較小的值,本文將它們設(shè)置為10。另外,可以用區(qū)間[0,1]之間的隨機值來實現(xiàn)隱性特征矩陣和核心張量的初始化過程。

2.2 基于MCL算法的用戶群組發(fā)現(xiàn)策略

利用張量Tucker分解訓(xùn)練出節(jié)目和時間2個維度上的隱性特征向量,為發(fā)現(xiàn)用戶的聚簇效應(yīng)提供了必要的條件。廣播電視用戶群組具有一些重要特征:每個家庭用戶的收視興趣是復(fù)合的,隨時間呈現(xiàn)周期變化;有些家庭用戶雖整體興趣不同,但在某些時段上是相似的;在相似的時段內(nèi),觀看相似節(jié)目的用戶表現(xiàn)出的興趣是相似的。根據(jù)用戶群組的特征,本文將相同的時段收看相似節(jié)目的所有用戶歸為一個用戶群組。

經(jīng)過處理的觀看記錄包含時間和節(jié)目2個屬性,根據(jù)記錄和用戶的關(guān)聯(lián)關(guān)系可以鎖定觀看同一類記錄的用戶。為了實現(xiàn)用戶群組發(fā)現(xiàn),本文采用的做法是:首先采用MCL算法[13]分別對收視時間和收視節(jié)目進(jìn)行聚類;然后根據(jù)聚類結(jié)果對記錄進(jìn)行分類,即將時間和節(jié)目屬性均相似的記錄歸為一類;最后利用記錄分類結(jié)果確定對同一類記錄有偏好的用戶群體。

以節(jié)目聚類為例,給定2個已經(jīng)過零-均值規(guī)范化處理的節(jié)目特征向量v1和v2,且v1,v2∈V,采用余弦相似度來度量2個特征向量的距離:

(16)

根據(jù)式(16),可以構(gòu)建節(jié)目特征的狀態(tài)轉(zhuǎn)移矩陣B∈NP×NP。其第i行第j列元素bij表示節(jié)目i和節(jié)目j之間的相似度。同理可構(gòu)建時間特征的狀態(tài)轉(zhuǎn)移矩陣L∈|S|×|S|,這2個矩陣即是MCL算法的輸入矩陣?；贛CL算法的用戶群組發(fā)現(xiàn)算法過程如下:

算法基于MCL的用戶群組發(fā)現(xiàn)

輸入B,L

輸出C

1.給定相似度門檻值θ ,迭代次數(shù)MaxIter ,擴展系數(shù)e ,膨脹系數(shù)r

2.B=MCL(B,θ)/*執(zhí)行MCL算法*/

3.初始化節(jié)目聚簇集CP,cpi∈CP /*節(jié)目聚簇歸類*/

4.for i←1 to NPdo

5. for j←1 to NPdo

6. if B(i,j)>0 then

7.cpi←cpi+B(i,j)

8./*接著對時間維度執(zhí)行MCL算法即聚簇歸類*/

9.CT=get_time_cluster(L)

10./*對記錄進(jìn)行分類*/

11.初始化AC /*初始化分類記錄結(jié)果*/

12.for i←1 to A.size do

13. set ACi←ai

14. for j←i+1 to A.size do

15. if ai.nP=aj.nPand ai.nT=aj.nTthen

16. ACi←ACi+ai

17.AC←AC+ACi

18.rm_repeat(AC)/*去除重復(fù)的分類記錄*/

19.初始化用戶群簇集C /*確定用戶群*/

20.for ACiin AC do

21. 遍歷所有對ACi中記錄產(chǎn)生過高評分的用戶Ci

22. C←C+Ci

23.returnC

MCL是群組發(fā)現(xiàn)算法的核心部分,它的重點是迭代并交替地執(zhí)行expansion和inflation操作。在迭代執(zhí)行MCL算法的擴展和膨脹操作時,有一個去除噪聲的步驟,即設(shè)定相似度門檻值θ,將特征矩陣中低于θ的所有值置為0,以去除噪聲,加快收斂速度。經(jīng)過足夠次數(shù)的迭代過程,特征矩陣趨于穩(wěn)定的收斂狀態(tài)。通過觀察矩陣中每一行的正值點,就可以確定節(jié)目聚簇和時間聚簇。最后,通過對記錄進(jìn)行分類來發(fā)現(xiàn)用戶群組。對每一條記錄ai∈A,它有2個屬性:ai.nP表示該記錄所屬的節(jié)目群簇標(biāo)號;ai.nT表示該記錄所屬的時間群簇標(biāo)號。當(dāng)2條記錄的這2個屬性均在同一個簇(即相似)時,可以將這2條記錄劃分為一類。對每一類記錄產(chǎn)生過高評分的用戶聚集起來,即是最終要發(fā)現(xiàn)的用戶群組。這樣通過MCL算法,就成功實現(xiàn)了分段用戶群組的發(fā)現(xiàn)。

3 實驗評估

3.1 實驗設(shè)置

本文實驗所使用的數(shù)據(jù)集的主體內(nèi)容為廣播電視用戶收視記錄,主要包括我國某地區(qū)廣播電視家庭用戶從2016年3月1日—3月26日的收視數(shù)據(jù)。其中,用戶均為廣播電視家庭用戶,沒有家庭成員結(jié)構(gòu)信息:收視內(nèi)容主要為廣播節(jié)目,節(jié)目類型豐富,包括電視劇、動畫、紀(jì)錄片、電影等。該數(shù)據(jù)集匹配本文所要解決的問題,可以用于驗證本文所提出的策略的效果。從數(shù)據(jù)集隨機抽取9 965個用戶的收視數(shù)據(jù),經(jīng)過數(shù)據(jù)預(yù)處理過程,最終的數(shù)據(jù)集中包括3 424 815條記錄,10 492個廣播節(jié)目。訓(xùn)練集包括3月1號—19號的數(shù)據(jù),剩余的數(shù)據(jù)則作為訓(xùn)練集。

(17)

3.2 實驗結(jié)果

3.2.1 性能分析

在MCL算法執(zhí)行的過程中,相似度門檻系數(shù)θ和膨脹系數(shù)r均會對群組發(fā)現(xiàn)的結(jié)果產(chǎn)生影響。實驗過程中執(zhí)行了2次MCL算法,分別是基于特征相似度的時間聚類和時段聚類。這2個過程涉及以下參數(shù):即膨脹系數(shù)rv、rt以及相似度門檻系數(shù)θv、θt。

圖和DG隨θv的變化趨勢(非情境)

圖和DG隨θt的變化趨勢

群組發(fā)現(xiàn)的結(jié)果是節(jié)目特征聚類結(jié)果和時間特征聚類結(jié)果的交集,調(diào)整參數(shù)使得最終發(fā)現(xiàn)的群組呈現(xiàn)出不同的結(jié)構(gòu)。MCL算法在執(zhí)行基于時間特征的記錄聚類時,當(dāng)θt=0.4時,群組推薦效果達(dá)到最優(yōu)。

3.2.2 性能比較

為了驗證本文所提出的群組發(fā)現(xiàn)策略的性能,本文選擇TDP[8]算法和TCC[9]算法實現(xiàn)群組發(fā)現(xiàn)策略,并比較它們與本文所提策略在性能方面的差異。這2種算法都采用了時間情境感知的推薦思想,充分考慮到了電視用戶的多成員屬性,利用時間情境信息參與建模過程的方式將復(fù)合的電視用戶收視興趣劃分為時段子興趣。相比于基于家庭的興趣特征分析方法,它們是目前更有效的電視用戶興趣模型分析方法。

圖4 3種算法在和DG指標(biāo)上的對比實驗結(jié)果

根據(jù)上述實驗和分析結(jié)果可以看出,本文所提出的MCL群組發(fā)現(xiàn)策略成功地發(fā)現(xiàn)了在收視時間和收視興趣均相似的用戶群體,且達(dá)到了更好的群組推薦性能。

4 結(jié)束語

本文提出一種基于情境感知的廣播電視群組發(fā)現(xiàn)策略。該策略以家庭用戶為單位,可以識別出特定時段具有相似觀看興趣的所有家庭用戶,并針對家庭用戶群組實現(xiàn)節(jié)目推薦功能。群組發(fā)現(xiàn)策略可為廣電運營商在個性化付費頻道的設(shè)計、客戶細(xì)分的研究等工作提供重要的參考。此外,由于本文僅考慮了廣播電視節(jié)目群組發(fā)現(xiàn)問題,而目前大多電視用戶也傾向于在電視上觀看點播視頻,因此用戶的廣播興趣和點播興趣之間的相互作用關(guān)系,將是后續(xù)工作的重點內(nèi)容。

[1] BJELACA M.Towards TV recommender system:experiments with user modeling[J].IEEE Transactions on Consumer Electronics,2010,56(3):1763-1769.

[2] WANG X,NIE X,WANG X,et al.A new recommender system framework for TV video[C]//Proceedings of the 6th International Conference on Information Science and Technology.Washington D.C.,USA:IEEE Press,2016:147-152.

[3] BARRAGANS-MARTINEZ A B,COSTA-MONTENEGRO E,BURGUILLO J C,et al.A hybrid content-based and item-based collaborative filtering approach to recommend TV programs enhanced with singular value decomposition[J].Information Sciences,2010,180(22):4290-4311.

[4] 黃 慧.云媒體電視智能推薦系統(tǒng)的設(shè)計與實現(xiàn)[D].南京:東南大學(xué),2015.

[5] CAMPOS P G,BELLOGIN A,DIEZ F,et al.Time feature selection for identifying active household members[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management.New York,USA:ACM Press,2012:2311-2314.

[6] SAID A,BERKOVSKY S,de LUCA E W,et al.Challenge on context-aware movie recommendation:CAMRa2011[C]//Proceedings of the 5th ACM Conference on Recommender Systems.New York,USA:ACM Press,2011:385-386.

[7] LI H,ZHU H,GE Y,et al.Personalized TV recommendation with mixture probabilistic matrix factorization[C]//Proceedings of 2015 SIAM International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2015:352-360.

[8] OH J,SUNG Y,KIM J,et al.Time-dependent user profiling for TV recommendation[C]//Proceedings of the 2nd International Conference on Cloud and Green Computing.Washington D.C.,USA:IEEE Press,2012:783-787.

[9] WANG Z,HE L.User identification for enhancing IP-TV recommendation[J].Knowledge-based Systems,2016,98:68-75.

[10] 李 寧,王子磊,吳 剛,等.個性化影片推薦系統(tǒng)中用戶模型研究[J].計算機應(yīng)用與軟件,2010,27(12):51-54.

[11] KIM J,KWON E,CHO Y,et al.Recommendation system of IPTV TV program using ontology and k-means clustering[C]//Proceedings of International Conference on Ubiquitous Computing and Multimedia Applications.Berlin,Germany:Springer,2011:123-128.

[12] 陳天昊,帥建梅,朱 明.一種基于協(xié)作過濾的電影推薦方法[J].計算機工程,2014,40(1):55-58,62.

[13] VAN D S.A cluster algorithm for graphs[J].Report-information Systems,2000 (10):1-40.

[14] 張玉潔,杜雨露,孟祥武.組推薦系統(tǒng)及其應(yīng)用研究[J].計算機學(xué)報,2016,39(4):745-764.

[15] GARCIA I,PAJARES S,SEBASTIA L,et al.Preference elicitation techniques for group recommender systems[J].Information Sciences,2012,189(20):155-175.