基于马尔可夫聚类和混合协同过滤的电视节目推荐

赵 宇 刘 凤 舒巧媛 韦鹏程

(重庆第二师范学院数学与信息工程学院 重庆 400065)

0 引 言

自从电视诞生以来，观看电视节目一直都是人类精神生活中的重要组成部分。如今，由于计算机技术和网络技术的飞速发展，人们越来越习惯于在互联网平台上观看视频节目，这也对传统广播电视运营商带来了冲击。对于广播电视运营商而言，客户的流失虽然为其带来了许多挑战，但也带来了新的机遇。现在，付费频道是广播电视的主要业务，也是收入的重要来源。如果广播电视运营商可以准确地知道每个用户的收视偏好，为其推荐相似的电视节目，从而挖掘潜在的付费用户，那么广播电视的竞争力就能得到显著提高。另一方面，大量数据的产生、推荐算法和数据挖掘等技术的发展，为广播电视运营商实现精准推荐提供了技术支持。因此，研究个性化的电视节目推荐算法具有重要意义[1-4]。

目前广泛使用的推荐系统都是通过搜集用户的个人行为信息，然后使用基于用户的推荐算法或者基于物品的推荐算法帮助用户筛选出其可能感兴趣的物品。Karabadji等[5]关注用户特征搜索空间的增长，提出了一个基于多目标优化的推荐系统来提取用户信息，使其与活跃用户的相似性达到最大化，提升推荐准确率。Liang等[6]提出了一种基于概率的算法，将用户对物品的曝光程度直接融合到协同过滤中，并把此曝光程度建模为一个潜在变量，算法通过数据推断此变量的值，以此来提升推荐结果的准确度。为了解决推荐过程里的数据的稀疏性和高维度问题，Koohi等[7]通过使用基于子空间聚类的方法来进行邻居用户查找，此算法在推荐时将数据划分为三个不同的子集：感兴趣集合、既不感兴趣也不厌恶集合、厌恶集合，基于这三个集合，为被推荐用户创建三个层次的邻居树，然后进行推荐。Papneja等[8]提出了一种基于扩展激活的上下文感知个性化内容推荐算法，通过分析物品和用户信息之间的关系，将有意义的物品推荐给用户。Wan等[9]提出了一个同时建模显示特征与隐式特征的推荐框架，将用户对物品的一系列动作抽象成单调行为链，用来描述物品的信息，从而按照物品的相似度为用户进行推荐。

以上这些研究在推荐系统领域都取得了令人满意的推荐准确率，然而这些研究在关注推荐准确率的同时，却存在一个潜在的问题：忽略了推荐结果的惊喜度和推荐结果的相关性对于用户体验的改善。一般而言，基于物品的推荐算法由于推荐的是相似物品，其推荐结果的惊喜程度比较低，而基于用户的推荐算法由于是按照相似用户进行推荐，其推荐结果和目标用户的历史偏好的相关性会降低，这两点因素都会影响推荐系统的用户转化率[10]。为了解决这个问题，本文提出了一种基于马尔可夫聚类和混合协同过滤的推荐算法MCL-HCF。首先，使用马尔可夫聚类算法[11]对各个时间段内的用户进行聚类，得到多个用户群组，降低群组内用户和整个群组之间的偏好差异性，然后以群组为单位进行推荐。在推荐阶段，本文使用IUF(inverse user frequence)[12]和IIF(inverse item frequence)[13]参数来修正用户相似度和物品相似度的计算。最后，加权融合两种协同过滤算法的结果，解决推荐结果的惊喜度和相关性的矛盾问题。

1 MCL-HCF推荐算法

MCL-HCF算法是结合了马尔可夫聚类与混合协同过滤的推荐算法。首先，MCL-HCF利用马尔可夫聚类算法找出在各个时间段内具有相似偏好的用户，然后将其看作一个群组，重新定义这个群组的观看信息，最后再通过混合协同过滤算法来获得最终的推荐结果，达到推荐惊喜度和相关性的平衡。

1.1 建立相似用户的群组

一般而言，一个家庭里多个成员的电视节目观看模式为：单个家庭由多个家庭成员组成，在某一个时间段St，某些成员对节目Pi感兴趣，那么，这些成员将在这个时间段构成一个新的群组Ub。同理，在其他的时间段，同样对应着其他的群组，并且从聚类的结果来看，一个家庭里的不同成员可以被划分到多个群组中。

如图1所示，用户1、用户2和用户3在时段1观看了节目1，所以将他们归为群组1；用户1、用户2在时段2观看了节目2，那么将他们归为群组2；用户3、用户4在时段3观看了节目3，那么将他们归为群组3。由此可以看出，同一个用户在不同时段被划分到不同的群组。

图1 分时段用户群组示例

本文使用马尔可夫聚类算法来建立各个时间段内的群组。马尔可夫聚类算法基于图进行聚类，其通过多次扩展和膨胀操作，使得最后聚族达到稳定状态。

1.1.1建立同一时段的邻接矩阵

本文筛选出在同一时间段内观看节目的用户，当两个用户同时观看了同一个节目时，其邻接矩阵对应元素加上1。由此可建立如下所示的邻接矩阵:

1.1.2消除奇偶性依赖

基于图的马尔可夫聚类算法的核心操作之一是扩展操作。扩展操作模拟了流对象在图上的随机游走行为。流对象在具有某些特定结构的图上执行随机游走时，会产生奇偶性依赖效应。为了解决扩展操作所产生的这种问题，需要在对图的状态转移矩阵进行处理之前，为每个顶点增加自循环，即矩阵对角线的值置为1，得到如下所示改进的邻接矩阵：

1.1.3标准化概率矩阵

利用改进的邻接矩阵，可以使用下式来计算得到概率矩阵：

(1)

1.1.4对概率矩阵进行扩展和膨胀交替操作

扩展和膨胀的交替操作是聚类过程的核心内容，首先执行的是扩展。如下式所示，扩展操作是使概率矩阵自乘e次，让流对象扩展到图的不同区域，其指数e的大小决定游走区域的大小。

P=Pe

(2)

然后，对概率矩阵P进行膨胀操作，膨胀操作的作用是增强聚簇节点内部的关联，弱化非聚簇节点之间的关联，即增大当前大概率，减小当前小概率。膨胀操作在作用于概率矩阵时，其参数r将会决定这种作用的强度，进而影响聚簇的粒度。其具体计算公式如下：

(3)

式中：ΓrP表示膨胀操作，pij∈P表示位于P的第i行、第j列的元素。

1.1.5聚类过程优化

为减小算法的迭代次数，加快马尔可夫聚类过程，本文为其设置一个阈值θ。概率矩阵经过扩展膨胀操作后，遍历所有pij，当pij≤θ时，令pij=0。这样的操作可以有效地过滤掉矩阵内部的噪声并加快马尔可夫聚类过程的收敛速度。对于θ和r的取值见2.1节的实验结果分析。

1.2 基于加权融合的混合推荐

协同过滤推荐算法可以分为两大类：基于物品的协同过滤算法ItemCF(item-based collaborative filtering)、基于用户的协同过滤算法UserCF(user-based collaborative filtering)。在此基础上，本文分别引入IUF参数和IIF参数来修正改进两种算法。

1.2.1基于物品的推荐

ItemCF-IUF算法的主要步骤如下：

Step1通过电视节目的历史播放信息，建立电视节目的相似度矩阵。

Step2根据用户的历史观看行为，为该用户推荐与其观看历史相似的节目。

在进行推荐之前，本文先对数据进行预处理。

1) 数据预处理：

(1) 数据合并。将群组内所有用户的观看记录合并在一起，以便计算群组的偏好。以下涉及的用户的各个指标全部是以群组为单位进行计算。

(2) 除噪。删去观看时间低于5分钟的记录。

(3) 分组。将每个时间段的用户分组。本文共分为5个时间段，如表1所示。

表1 观看时间段

(4) 评分计算。计算各个群组对每个节目的评分。由于一般的广播电视很少会有评分系统，所以，本文利用各个群组观看每个节目的时长、次数、付费金额经过加权融合得到加权总频率，并以此作为群组对节目评分的量化，得到评分矩阵D。其计算公式如下：

(4)

式中：Dij表示第i个群组对第j个节目的评分，a1、a2和a3分别表示观看时长、次数和金额的权重，tij、fij和dij分别表示第i个群组观看第j个节目的时长、次数和金额。在本文实验中，取a1=1，a2=1，a3=2。

2) 计算节目相似度矩阵。考虑到用户活跃度对节目相似度的影响，即活跃的用户相比不活跃的用户，对节目之间相似度的贡献更小。例如，一个喜欢多个节目的人，比一个只喜欢节目的人，对节目的相似度贡献较小，所以本文加入了IUF参数来修正相似度的计算。其计算公式如下：

(5)

式中：KIUF表示IUF参数，Nu表示用户u喜欢的节目总数，Nu越大表示该用户的活跃度越高，其对节目相似度的贡献越小。

所以，节目相似度矩阵的计算公式如下：

(6)

式中:Wij表示节目i与节目j的相似度，Ni表示喜欢节目i的用户数，Nj表示喜欢节目j的用户数。

3) 节目相似度归一化。为了提高推荐结果的准确度，本文遵循Karypis的研究[14-15]，将ItemCF-IUF的相似度矩阵按最大值归一化。其计算公式如下：

(7)

4) 基于兴趣度生成推荐列表。在评分矩阵D中，找到各个群组观看历史记录里评分最高的节目，再按照与该节目兴趣度的差异大小来进行排序，生成其他节目的推荐列表，推荐给这一群组里的用户。在ItemCF-IUF算法中，通过如下公式计算群组u对一个节目j的兴趣度：

(8)

Iuj越大，表示此群组对这个节目的兴趣度越高，因此可以将推荐列表里兴趣度较高的前几个节目推荐给群组里的用户。

1.2.2基于用户的推荐

UserCF-IIF算法的主要步骤如下：

Step1找到和目标用户兴趣相似的用户集合，即建立用户相似度矩阵。

Step2在这个集合中查找目标用户没有观看过的节目推荐给目标用户。

1) 计算用户相似度矩阵。节目受众程度对用户相似度的计算存在影响。受众程度高的节目，相对于受众程度低的节目而言，其对用户相似度的贡献更小。例如，一个受众程度高的节目，两个用户都看过，但这并不能表明这两个用户兴趣相似，反之，如果这两个用户都看过受众程度很低的节目，那就可以认为这两个用户兴趣比较相似。为了解决上述问题，我们在相似度计算过程里引入IIF参数，用于对热门节目进行一定的惩罚。IIF参数的计算公式如下：

(9)

式中：KIIF表示IIF参数，Ni表示喜欢看i节目的群组个数，Ni越大表示这个节目的受众程度越高，其对用户相似度的贡献就越小。

结合式(9)，可以得到如下的用户相似度矩阵计算公式：

(10)

式中：Wuv表示用户u与用户v的相似度，Nu表示用户u喜欢的节目集合，Nv表示用户v喜欢的节目集合。

2) 用户相似度归一化。为了提高推荐准确率，我们依然对用户相似度进行归一化，其计算公式如下：

(11)

3) 生成推荐列表。通过马尔可夫聚类，将聚在一类的用户看作一个群组，对群组进行推荐。在UserCF-IIF算法中，通过下式计算群组u对节目i的兴趣度：

(12)

Iui越大，表示此群组对这个节目的兴趣度越高，则可以将兴趣度较高的前几个节目推荐给此群组里的用户。

1.2.3混合推荐

混合推荐方法是在考虑不同推荐方法的缺点的基础上建立的。混合推荐方法的准则是组合多种方法，发挥不同推荐方法的优点，消除各自的缺点。由于ItemCF-IUF给用户推荐的是相似物品，所以其推荐的节目的惊喜度比较低。UserCF-IIF根据用户相似度来推荐，其推荐惊喜度较高，但推荐结果的相关性较弱。

推荐节目的惊喜度可以这样理解：用户对某一类节目很少涉及，但是用户在接收到此类节目的推荐后愿意观看它。本文定义如下公式来表示推荐节目的惊喜度：

(13)

式中：Ps表示推荐的惊喜度，NG表示群组总数，PLEA(i)表示第i个群组的推荐分类中排名最低的分类节目总数，GEN表示推荐总数。

推荐节目的相关性可以这样理解：为用户推荐的节目与用户观看过的节目间的相关程度，即这两方面节目是否属于同一类。本文定义下式来表示推荐节目的相关性：

(14)

式中：Co表示推荐结果的相关性，NG表示群组总数，REC(i)表示第i个群组的推荐结果中每一个节目所属类别总数的集合，GEN表示推荐总数。

为了在推荐节目的惊喜度和相关性之间取得一个平衡，本文使用了混合推荐方法，把ItemCF-IUF算法和UserCF-IIF算法所获得的推荐结果，按M∶N的比例进行加权融合，形成最终的推荐结果，其过程如算法1所示。其中，Gk表示目标群组，Total为推荐列表的长度，topk表示筛选前k个推荐结果，k的值由输入参数确定，cascade表示级联操作，用于将筛选后的ItemCF-IUF和UserCF-IIF两种算法的推荐结果进行组合。本文就ItemCF-IUF和UserCF-IIF两种算法结果的推荐比例M∶N的最佳取值进行了探讨，具体见2.2节的实验结果分析。

算法1混合推荐

Input: Gk,Total,M,N

Output: Result

1: while j=1,2,…,Total do

2: resItem[j]←ItemCF-IIF(Gk)

3: resUser[j]←UserCF-IUF(Gk)

4: end while

5: resM←topk(resItem,(M*Total)/(M+N))

6: resN←topk(resUser,(N*Total)/(M+N))

7: Result←cascade(resM,resN)

8: return Result

2 实验结果及分析

为了验证提出的算法的有效性，本文使用了泰迪杯数据挖掘挑战赛的公开数据集[16]。使用的数据集包含250位志愿者在3个月内，对100个节目观看时产生的15 375条数据。实验在拥有Intel i5处理器、8 GB内存的计算机上进行，计算环境为MATLAB 2018。

2.1 群组划分结果分析

本文按照群组为单位进行电视节目推荐，群组划分时聚类结果是否良好对最终的推荐结果会产生不同影响。本文关注的重点是各个群组内不同成员收视偏好的一致性，即追求在不同时间段内聚类得到的各个群组的组员与它所属的群组的偏好差异最小化。首先，本文采用平均绝对误差MAE[17-18]来衡量一个群组内的组员和群组整体的偏好差异，其定义如下：

(15)

式中：Dui表示用户u对i的评分，DGi表示群组G对节目i的评分，N表示推荐节目的个数。

由于MAE仅仅是衡量单个群组与组内个体的偏好差异，而本文是按照群组为单位在不同时间段进行电视节目推荐的，所以本文定义一个新的衡量各个群组在不同时间段内的偏好差异的指标——群组平均绝对误差MAEG，其计算公式如下：

(16)

利用上述公式，讨论了马尔可夫聚类参数θ和r的不同取值对于算法的收敛速度和群组划分效果的影响，其结果如图2和图3所示。

图2 迭代次数随聚类参数的变化趋势

图3 MAEG指标随聚类参数的变化趋势

由图2可以看出，马尔可夫聚类的收敛速度由θ和r的大小决定，θ与r越大，其收敛速度越快，且随着θ的变大逐渐趋于稳定。由图3可以看出，当θ较小时，MAEG变化缓慢，当θ增加到一定值时，MAEG开始降低。结合图2和图3的结果可以看出，当θ=0.009，r=5时，群组平方绝对误差MAEG=0.14，此时聚类得到的各个群组取得组内差异最小化，这表明此时的群组划分达到最优，有利于提高最终的推荐准确率，且聚类过程也能达到较理想的收敛速度。

2.2 混合推荐比例分析

为了确定混合推荐比例M∶N的最佳值，以达到推荐结果惊喜度和相关性的平衡，本文对不同的比例组合进行了对比，分别计算在不同M∶N取值下的推荐结果惊喜度和相关性，结果如图4和图5所示。

图4 推荐惊喜度对比

图5 推荐相关性对比

在图4和图5中，time1-time5表示时间段，各个时间段对应的具体时刻见表1。由图4可以看出，各个时间段的惊喜度在M∶N取1 ∶3处达到最大。由图5可以看出，各个时间段在M∶N取1 ∶2处达到最高的推荐相关性，在1 ∶3处达到次高的推荐相关性。

通过对惊喜度和相关性的综合比较，当ItemCF-IUF和UserCF-IIF的推荐节目个数比例M∶N达到1 ∶3时，推荐节目的惊喜程度和节目间的相关程度均达到相对较高的值，所以本文的混合推荐比例M∶N确定为1 ∶3。

2.3 推荐结果分析

为检验提出的推荐方法的有效性，本文在公开数据集[16]上进行了实验，得到推荐的准确率、新鲜度和个体多样性。结合如表2所示的混淆矩阵定义，本文通过下式来计算节目推荐的准确率：

(17)

式中：Acc表示推荐方法的准确率。

表2 混淆矩阵

除了推荐的准确率之外，推荐结果的新鲜度和个体多样性也是衡量推荐算法性能的重要指标。新鲜度反映了推荐算法向用户推荐非流行物品的能力；个体多样性反映了推荐算法为用户推荐相似度低且符合其兴趣偏好的物品的能力。本文采用下式来定义推荐结果的新鲜度：

(18)

式中：Fre表示新鲜度，NG表示群组总数，λ(u)表示推荐节目是否是流行节目，若是，λ(u)=1，否则，λ(u)=0。而一个节目的流行度采用下式定义：

(19)

此外，本文采用下式来定义推荐结果的个体多样性：

(20)

式中：Div表示个体多样性，LN(u)表示群组u的推荐列表，N代表推荐节目个数，Wjk表示节目j和节目k的相似度。

通过使用250位实验者观看电视节目的行为数据进行实验，本文对提出的MCL-HCF混合推荐算法进行了准确率、新鲜度和个体多样性的分析。在实验中，本文将电视节目划分为综艺、电视剧、电影、动画、纪录片、其他，共六大类。对于群组内单个用户是否喜欢某个推荐节目的判断依据是：在用户历史观看记录的评分矩阵中找出其喜欢的几个节目类型，通过判断推荐节目是否属于用户的偏好节目类型，确定用户是否喜欢推荐的节目。推荐节目的准确率如表3和图6所示。

表3 推荐准确率

图6 准确率对比

表3中的time1-time5表示时间段，各个时间段对应的具体时刻见表1。Acc2表示用户喜欢两个节目类型时的准确率，Acc3表示用户喜欢三个节目类型时的准确率。通过表3可以看出，使用MCL-HCF混合推荐算法对这250位用户进行电视节目推荐的准确率总体比较高，Acc2各个时间段的均值为0.93，Acc3各个时间段的均值为0.96，这表明本文提出的先聚类得到群组再进行混合推荐的策略在电视节目推荐问题上能取得令人满意的推荐准确率。

同时，从表3和图6可以看出，各个时间段的Acc3比Acc2要大，这是因为当用户喜欢的节目类型增加时，相当于扩大用户的偏好范围，这会提升对此用户的推荐准确率。

推荐结果的新鲜度和个体多样性如表4和表5所示，其中time1-time5表示的时间段具体范围见表1。通过表4可以看出，除了time3时段外，本文提出的算法能取得较高的推荐新鲜度，具备为用户推荐非流行节目的能力。通过分析time3(14:00-20:00)时段的观看记录，我们发现此时段播出的节目主要是以受众程度较高的综艺、电视剧和动画类节目为主，这些类型的节目具备更高的普适观众的能力，这是在此时段进行推荐时新鲜度低于其他时段的原因。从表5可以看出，本文提出的算法在各个时段都能取得令人满意的个体多样性，能够为用户推荐更多不同类型的且符合其偏好的节目，从而能够提升用户的使用体验。

表4 推荐新鲜度

表5 推荐个体多样性

3 结 语

本文主要关注为家庭用户进行电视节目的个性化推荐问题。为此，本文提出了MCL-HCF混合推荐算法。首先，使用马尔可夫聚类算法对各个时间段内的用户进行聚类，得到不同的用户群组。为了衡量聚类结果的有效性，我们引入了组平均绝对误差MAEG，在追求MAEG最小的策略下，优化了群组划分的结果。然后，本文以群组为单位进行电视节目推荐，在使用ItemCF-IUF和UserCF-IIF两种算法得到各自的推荐列表后，我们使用加权融合的方式进行了混合推荐，以此来解决传统推荐算法在推荐结果的惊喜度和相关性上的矛盾。在公开数据集上的实验结果表明本文提出的MCL-HCF算法具有如下优点：(1) 能够降低群组内用户和群组整体之间的偏好差异程度，提升对整个家庭的用户推荐节目时的准确率；(2) 混合推荐的最终结果能够在保持推荐准确率的同时，使推荐节目的惊喜度和相关性达到平衡。在后续研究中将主要关注寻找新的群组划分策略，提升群组成员的内聚程度，进一步提高推荐效果。