基于情境感知的广播电视群组发现策略

陈 建,王子磊,奚宏生

(中国科学技术大学 自动化系,合肥 230027)

0 概述

目前,大多数的电视节目推荐系统直接采用网站视频推荐方法。文献[1]采用基于内容的推荐方法,利用聚类技术训练出向量空间模型形式的用户兴趣;文献[2]使用协同过滤推荐方法中的SVD模型,研究如何为用户推荐电视视频。还有一些电视推荐系统采用了混合策略[3-4],将协同过滤和基于内容的推荐方法结合使用。然而广播电视和网站视频的观看场景存在着很大的差异。首先,电视用户为多成员用户,家庭用户的收视兴趣是所有成员用户收视兴趣的复合形式;其次,成员自由组合,形成了多种观看模式,用户的收视兴趣存在频繁迁移的现象。因此,直接应用网站视频推荐方法来实现电视节目推荐,效果难以保证。

针对广播电视用户的多成员用户问题,一些工作通过识别家庭成员来改善电视推荐系统的性能[5]。ACM在2010年和2011年举办了情境感知电影推荐竞赛[6](CAMRa),参赛者以家庭为群组单位,实现对家庭成员的识别,并向一个家庭推荐节目。参赛者大多采用分类预测模型,取得了一定的效果。但是这些工作都是建立在家庭成员构成已知的情况下,在实际情况下,成员组成情况往往是难以获得的。另外,家庭用户的某个观看模式,不一定只对应单个成员,而是某些成员组合而成的观看群组[7]。因此,在家庭成员组成未知的情况下,是无法采用分类模型来解决电视推荐问题的。

在家庭用户结构未知的情况下,在特定的时段,多个成员组合形成观看群组,观看群组的收视兴趣可以代表家庭用户在此时段的收视兴趣。文献[8]利用时间信息,将收视记录按照时段进行聚类操作;文献[9]利用时间维度信息,将家庭的总兴趣模拟为多个“伪用户”兴趣的组合,通过识别每个家庭的“伪用户”来提高推荐系统精确度。这些研究工作利用时间情境信息将复合的家庭用户收视兴趣划分为分时段的用户子兴趣,在一定程度上缓解了因用户兴趣的复合特征而造成推荐精度下降的问题。但是,仅考虑用户的时段兴趣效应是不充足的,电视节目类型十分丰富,致使相同时段播放的节目也可能是不同类别的成员所感兴趣的,兴趣复合性问题依然存在。

为解决广播用户收视兴趣复合性问题,并发现收视兴趣相似的多家庭用户群组,本文提出一种基于时间情境感知的电视用户群组发现策略。其中,收视记录中的观看时间是本文所使用的情境参量。具体为采用张量分解来获取节目和收视时间的隐性特征矩阵,无需使用深度EPG中的节目本体数据[10];利用马尔可夫聚类算法实现对收视记录的分类,并根据记录分类结果发现用户群组。用户群组以家庭为单位,群组内每个家庭的收视兴趣在收视时间和收视内容上均相似。

1 问题描述

电视群组推荐系统的目标是为群组推荐电视节目或视频,群组构建的基本原则是各成员在收视兴趣上保持相似。因此,如何确定用户群组是实现群组推荐系统的关键。本文所要解决的问题是:有效利用时间情境和节目特征信息,发现在收视时间和收视内容上均相似的用户群组。表1为本文中所定义的概念符号及其简略解释。

表1 符号定义及描述

典型家庭用户群组观看模式的一般场景为:单个家庭用户由多个家庭成员组成,在某个时段s,某些家庭用户对节目组ps感兴趣,这些家庭用户构成了一个用户群组。另外可以认为在时间段s,这些家庭用户均具有相似的兴趣。在其他时段,同样对应着相应的用户群组。一个家庭用户可以被划分到多个用户群组中。图1给出了电视用户分时段群组构成的一个概念例子:4个电视用户在3个时段上观看了电视节目,每个时段对应着一组节目。某些用户由于在同一时段体现了对同一组节目的兴趣,因此这些用户被划分为一个用户群组(如图1所示的3个群组)。

图1 电视用户分时段群组构成示例

基于以上考虑,将收视时间特征和收视内容特征作为重要的数据源。输入的数据集中包括每个家庭用户的收视情况。通过数据预处理,可以得到用户-节目-时间-观看时长这样的记录模式。为了精简地表达时间信息,需要手动将时间维度信息进行离散化处理,即将24 h划分为不相交的若干时段,即:

(1)

根据离散化的时段,计算用户在每个时段sl对节目的评分,并构建三维的评分张量R∈NU×NP×|S|。第一步所要完成的是以R为输入,训练出节目特征矩阵V以及时间特征矩阵T。矩阵V和矩阵T为后续分析记录之间的相似性提供了依据。记录a∈A具有2个属性,即记录所对应的节目a.p和对应的收视时段a.s。

设在时段集合Sb⊆S,兴趣相似的家庭用户分为一组,形成了用户数为Nb的用户群组:

(2)

其中,csi表示时段集合s对应的用户簇cs中的第i个用户,则对于时段集合S而言,用户群组总集合可表示为:

(3)

本文的主要目标就是以记录集合A为输入来发现用户群组总集合C,并针对C中的每一个群组推荐节目。实现这个过程需要解决2个关键问题:在没有深度EPG数据的情况下实现对节目的聚类;发现观看时间和观看内容均相似的用户群组。

2 群组发现策略

为解决问题定义中提出的2个主要问题:本文采用张量Tucker分解模型获取用户、节目以及时间这3个维度的特征矩阵;以时间、节目特征矩阵分别作为收视记录的属性特征,应用马尔可夫聚类(MCL)算法完成群组发现工作。

2.1 隐性特征获取

在基于内容的推荐方法中,通常需要使用项目的特征信息,以便于通过聚类、TF-IDF等算法来训练用户的特征偏好。在电视节目推荐问题中,一般也是根据深度EPG数据来训练用户对节目的偏好模型[7,10-12]。由于节目本体信息存在于深度EPG数据中,而深度EPG数据通常难以获取,因此本文未使用节目的本体信息,而是利用张量分解模型来自动学习出节目的特征向量,这些特征是通常被称为隐性特征。同理,还可以学习出时间维度上的特征向量。隐性特征可以代表节目和时间的属性特征,这样不同的节目和时间就可以进行相似比较,在此基础上就能实现对节目和时间的聚类。

张量分解模型是矩阵分解模型在多维空间上的推广。张量分解有多种形式,目前比较流行的分解有Tucker分解和CP分解。本文选择Tucker分解模型来获取隐性特征矩阵。Tucker分解将张量分解成为一个核心张量沿每一阶乘上一个矩阵。本文在用户-节目-时间3个维度所构建的评分张量R∈NU×NV×|S|上做Tucker分解,其中rups∈R表示为用户u在时段s对节目p的偏好评分。R是一个稀疏的张量,每一个元素都对应着一条隐式评分记录,采用式(4)计算R中的非空值:

(4)

其中,nups表示用户u在时段s观看节目p的次数,dupsi为用户u第i次观看节目p所占用的时间,ts为时段s所占的总时长(以分钟计)。最终计算得到的评分的范围区间为[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表示的是节目的隐式特征矩阵,其每一行代表着一个节目的隐性特征,节目之间的特征相似度可以通过比较它们各自的隐性特征来获得。同理,对于矩阵T也是如此。学习上述3个矩阵和核心张量,需要最小化式(6)所示的损失函数:

(6)

其中,第2项和第3项是为了避免模型过拟合而设置的正则项,且有:

(7)

本文采用随机梯度下降法(SGD)来学习隐性特征矩阵V、T。首先定义矩阵V、T中的行向量,即vj*表示V的第j行,tk*表示T的第k行。SGD首先计算损失函数的梯度,如式(8)～式(11)所示。

(8)

(9)

(10)

(11)

根据上述计算得到的梯度可以用来更新特征行向量和核心张量,更新行向量的公式为:

(12)

(13)

(14)

(15)

其中,η为学习率,它表示SGD的学习速率。在实际执行SGD时,首先是选定一个迭代次数d,根据评分矩阵R的评分项划分好训练集和测试集,并用随机值初始化矩阵U、V、T以及核心张量M。然后针对评分矩阵R中的每一项评分,根据式(12)～式(15)计算梯度并更新行向量和核心张量。经过d次迭代,可以获得矩阵U、V中的任意行向量。

在隐性特征获取的过程中,dU、dV和dT的值可以自由选择,但为了保证M的稠密性,一般都设置为较小的值,本文将它们设置为10。另外,可以用区间[0,1]之间的随机值来实现隐性特征矩阵和核心张量的初始化过程。

2.2 基于MCL算法的用户群组发现策略

利用张量Tucker分解训练出节目和时间2个维度上的隐性特征向量,为发现用户的聚簇效应提供了必要的条件。广播电视用户群组具有一些重要特征:每个家庭用户的收视兴趣是复合的,随时间呈现周期变化;有些家庭用户虽整体兴趣不同,但在某些时段上是相似的;在相似的时段内,观看相似节目的用户表现出的兴趣是相似的。根据用户群组的特征,本文将相同的时段收看相似节目的所有用户归为一个用户群组。

经过处理的观看记录包含时间和节目2个属性,根据记录和用户的关联关系可以锁定观看同一类记录的用户。为了实现用户群组发现,本文采用的做法是:首先采用MCL算法[13]分别对收视时间和收视节目进行聚类;然后根据聚类结果对记录进行分类,即将时间和节目属性均相似的记录归为一类;最后利用记录分类结果确定对同一类记录有偏好的用户群体。

以节目聚类为例,给定2个已经过零-均值规范化处理的节目特征向量v1和v2,且v1,v2∈V,采用余弦相似度来度量2个特征向量的距离:

(16)

根据式(16),可以构建节目特征的状态转移矩阵B∈NP×NP。其第i行第j列元素bij表示节目i和节目j之间的相似度。同理可构建时间特征的状态转移矩阵L∈|S|×|S|,这2个矩阵即是MCL算法的输入矩阵。基于MCL算法的用户群组发现算法过程如下:

算法基于MCL的用户群组发现

输入B,L

输出C

1.给定相似度门槛值θ ,迭代次数MaxIter ,扩展系数e ,膨胀系数r

2.B=MCL(B,θ)/*执行MCL算法*/

3.初始化节目聚簇集CP,cpi∈CP /*节目聚簇归类*/

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./*接着对时间维度执行MCL算法即聚簇归类*/

9.CT=get_time_cluster(L)

10./*对记录进行分类*/

11.初始化AC /*初始化分类记录结果*/

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)/*去除重复的分类记录*/

19.初始化用户群簇集C /*确定用户群*/

20.for ACiin AC do

21. 遍历所有对ACi中记录产生过高评分的用户Ci

22. C←C+Ci

23.returnC

MCL是群组发现算法的核心部分,它的重点是迭代并交替地执行expansion和inflation操作。在迭代执行MCL算法的扩展和膨胀操作时,有一个去除噪声的步骤,即设定相似度门槛值θ,将特征矩阵中低于θ的所有值置为0,以去除噪声,加快收敛速度。经过足够次数的迭代过程,特征矩阵趋于稳定的收敛状态。通过观察矩阵中每一行的正值点,就可以确定节目聚簇和时间聚簇。最后,通过对记录进行分类来发现用户群组。对每一条记录ai∈A,它有2个属性:ai.nP表示该记录所属的节目群簇标号;ai.nT表示该记录所属的时间群簇标号。当2条记录的这2个属性均在同一个簇(即相似)时,可以将这2条记录划分为一类。对每一类记录产生过高评分的用户聚集起来,即是最终要发现的用户群组。这样通过MCL算法,就成功实现了分段用户群组的发现。

3 实验评估

3.1 实验设置

本文实验所使用的数据集的主体内容为广播电视用户收视记录,主要包括我国某地区广播电视家庭用户从2016年3月1日—3月26日的收视数据。其中,用户均为广播电视家庭用户,没有家庭成员结构信息:收视内容主要为广播节目,节目类型丰富,包括电视剧、动画、纪录片、电影等。该数据集匹配本文所要解决的问题,可以用于验证本文所提出的策略的效果。从数据集随机抽取9 965个用户的收视数据,经过数据预处理过程,最终的数据集中包括3 424 815条记录,10 492个广播节目。训练集包括3月1号—19号的数据,剩余的数据则作为训练集。

(17)

3.2 实验结果

3.2.1 性能分析

在MCL算法执行的过程中,相似度门槛系数θ和膨胀系数r均会对群组发现的结果产生影响。实验过程中执行了2次MCL算法,分别是基于特征相似度的时间聚类和时段聚类。这2个过程涉及以下参数:即膨胀系数rv、rt以及相似度门槛系数θv、θt。

图和DG随θv的变化趋势(非情境)

图和DG随θt的变化趋势

群组发现的结果是节目特征聚类结果和时间特征聚类结果的交集,调整参数使得最终发现的群组呈现出不同的结构。MCL算法在执行基于时间特征的记录聚类时,当θt=0.4时,群组推荐效果达到最优。

3.2.2 性能比较

为了验证本文所提出的群组发现策略的性能,本文选择TDP[8]算法和TCC[9]算法实现群组发现策略,并比较它们与本文所提策略在性能方面的差异。这2种算法都采用了时间情境感知的推荐思想,充分考虑到了电视用户的多成员属性,利用时间情境信息参与建模过程的方式将复合的电视用户收视兴趣划分为时段子兴趣。相比于基于家庭的兴趣特征分析方法,它们是目前更有效的电视用户兴趣模型分析方法。

图4 3种算法在和DG指标上的对比实验结果

根据上述实验和分析结果可以看出,本文所提出的MCL群组发现策略成功地发现了在收视时间和收视兴趣均相似的用户群体,且达到了更好的群组推荐性能。

4 结束语

本文提出一种基于情境感知的广播电视群组发现策略。该策略以家庭用户为单位,可以识别出特定时段具有相似观看兴趣的所有家庭用户,并针对家庭用户群组实现节目推荐功能。群组发现策略可为广电运营商在个性化付费频道的设计、客户细分的研究等工作提供重要的参考。此外,由于本文仅考虑了广播电视节目群组发现问题,而目前大多电视用户也倾向于在电视上观看点播视频,因此用户的广播兴趣和点播兴趣之间的相互作用关系,将是后续工作的重点内容。

[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] 黄 慧.云媒体电视智能推荐系统的设计与实现[D].南京:东南大学,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] 李 宁,王子磊,吴 刚,等.个性化影片推荐系统中用户模型研究[J].计算机应用与软件,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] 陈天昊,帅建梅,朱 明.一种基于协作过滤的电影推荐方法[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] 张玉洁,杜雨露,孟祥武.组推荐系统及其应用研究[J].计算机学报,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.