层次分析算法及优化在网络视频评比中的实践①

李 凡, 杜义华

1(中国科学院 计算机网络信息中心, 北京 100190)

2(中国科学院大学, 北京 100049)

手机的普及, 使网络信息的传播变得更加方便, 微视频、微博、微信等在新媒体时代下成为大量用户信息交互的平台. 合理利用网络渠道往往能提升活动的影响力. 近些年, 中科院及其附属单位开展了多次网上宣传评比活动, 诸如“镜头中的最美科学家”视频征集活动、科普短片征集评比活动等. 然而, 此类网上评比活动缺乏有效的评估方法.

对视频进行征集评比时, 一方面要考虑专家们的综合意见, 另一方面也要考虑网上网友们对视频播放点赞转发等互动行为. 目前的多维指标综合评价模型主要使用用户自主赋予权重、均等分配权重等方法[1],存在很大的劣势, 诸如人为主观因素对权值分配干扰过强、指标太多时导致评价实施的复杂性等等. 网上评比需要考虑多维度的参考指标, 因此基于视频的多维交互量, 本文分析了评比影响要素并构建了层次分析模型, 引入层次分析法并加以算法改进, 确立了具体的指标权值, 给出了合理的评比方法.

1 视频网上评比模型

现有的视频网上评比方案存在许多问题. 用户投票评比法存在刷票、真正观看视频人数存在水分等数据失真问题. 仅依靠播放量等数据的评比法, 指标集比较粗糙, 数据不能够全面客观反映视频在观众中的传播影响力. 经过充分的问卷调查以及与专业人士的探讨, 得出如下结论: 视频网上评比, 不仅需要考虑直接的播放指标, 也需要考虑体现视频人气属性以及社交影响力的评论点赞以及转发等指标, 才能更全面科学地评测视频的传播效果及用户的喜好性. 利用层次分析法能很好地解决此问题. 因此本文主要从播放指标、评论点赞指标、转发指标这三个方面综合考虑视频评比问题.

各一级指标下的二级指标应客观真实且较易获取.对于播放次数, 只有播放记录超过2分钟时才会在后台记录为一次播放, 以减少视频点击后短期内退出等现象对指标的影响. 平均播放时长指标一定程度上反映出视频对用户的吸引力, 质量更好的视频往往会吸引用户观看更长时间. 用户对于偏喜好的视频, 倾向于留下表达自己想法的评论并点赞, 因此总评论数、总评论用户数、总点赞数指标能体现出一定偏好性. 转发功能能让视频更方便地在网络中传播, 用户对喜爱的视频可以随意转发, 因此总转发次数和总转发用户数可以反映视频的传播程度, 是一定程度上影响力的体现.

由上分析, 确立如表1的评比层次分析模型.

表1 视频网上评比层次分析模型

表1中左侧栏为目标层, 对应的是评比模型中视频的综合得分, 中间栏和右侧栏对应的是评比模型的准则层, C11、C12是播放指标的二级指标, C21、C22、C23是评论点赞指标的二级指标, C31、C32是转发指标的二级指标.

选取样本集合为S 需要对样本集中数据的每一个指标进行归一化处理. 归一化处理如公式(1)所示.

其中x为指标的原有值,xmax、xmin分别为样本集中该指标的最大值和最小值. 归一化后的指标数值范围在[0, 1], 便于量化计算.

视频评比最终得分用公式(2)表示:

式中x(j)为样本集中某元素的第j个指标归一化后的数值,w(j)为第j个指标的权值, 通过层次分析法获取某指标对应的权值.

2 层次分析法

2.1 层次分析法权值计算

日常生活中人们经常遇到需要考虑多维多层次因素的决策问题, 由美国运筹学家托马斯·塞蒂提出的层次分析(AHP)能很好地解决此类问题, 它是一种定性和定量相结合的、系统化、层次化的分析方法[2]. 一般会根据需要达到的最终目标剥离出问题的影响因素,按照因素间的逻辑关系将各因素层次化划分, 形成一个层次分析模型. 之后逐步进行定性和定量分析, 确定从目标层到最低因素层的权值分配方案, 提供最终的决策方法.

层次分析法具体主要步骤如下:

1) 分析层次模型

分解出影响因素, 充分考虑因素间的内在关联, 将问题中遇到的各个因素进行逻辑分层, 建立起从最终决策到底层因素的多级层次. 在层次分析法中一般将层级划分为目标层、准则层、方案层等. 上层因素的权值等于其下属层各因素的权值之和.

2) 构造判断矩阵

对指标进行两两比较, 用1到9这9个数值表示指标间的相对重要程度[3]. 每个数字级别代表的重要度含义如表2所示.

判断矩阵是否合理直接影响到最终结果的可信度.由专家提供权威的判断, 对所有指标两两对比后, 得到该目标的判断矩阵A.

表2 重要度比较表

3) 计算矩阵的特征值与特征向量

在层次分析法分析过程中, 矩阵的特征值、特征向量并非需要完全精确的数值, 只需要求出近似的结果即可满足要求. 此处采用“方根法”近似计算判断矩阵的特征值与特征向量[4,5].

求解过程如下:

① 求出判断矩阵每一行元素乘积的n次方根, 表示为:

③ 求出矩阵当前对应的最大特征值:

4) 一致性检验

在判断矩阵A中, 满足如下关系:

一致性检验中需要用到一致性指标CI, 其表示当前判断矩阵不一致性的程度,CI的值与最大特征向量λm以及判断矩阵的阶数n有关,CI值越小的判断矩阵越趋向于完全一致性[6,7]. 计算CI的方法如公式(8)所示:

其中,n为判断矩阵的阶数,λm为当前判断矩阵的最大特征值.

计算一致性比例CR:

其中,RI为平均随机一致性指标, 查阅相关资料, 得到常用的RI数据如表3所示.

表3 一致性指标

所有阶数小于等于2的判断矩阵都满足完全的一致性. 此外, 当CR＜0.1时, 矩阵满足一致性要求, 否则需对矩阵元素进行调整来重新计算矩阵的特征值与特征向量, 直到该判断矩阵达到最终的一致性要求.

2.2 基于PageRank的AHP优化算法

上述层次分析法, 依靠判断矩阵实现了指标的权值分配. 但是, 它仅仅反映了各指标间的独立比较关系,并没有考虑到各指标间的依赖关系. 因此, 本文在对指标分析权重时, 考虑指标间的依赖关系, 参考谷歌PageRank算法, 对原始AHP算法加以优化.

1) PageRank算法介绍

PageRank算法是一种应用广泛的链接分析算法,由Larry Page和Sergey Brin在研究网页排序算法时提出的, 是一种评估网页重要性的测量方法[8].

其基本思想是: 访问越多的网页, 其网页质量偏向于越高. 某一页面的PageRank值是通过递归算法计算所有链入它的页面的因子的和得到的[9]. 因而一个网页要想有较高的等级, 必须具有较多的链入页面, 高质量的链入页面越多, 会导致等级越高[10].

2) 改进AHP指标权值

通过普通层次分析法得到的指标权值分配, 初步体现了指标间层次因果关系, 但是还存在一些局限性,比如没有考虑到同级指标间的依赖关系. 因此参考PageRank算法对已得到的权值向量加以改进.

对于某个指标A1, 如果它依赖于指标A2, 则认为A1需要将自己的部分权值因子分配给A2. 诸如视频的播放量指标就依赖于转发数、点赞数等指标, 所以需要将播放量指标的权值分一部分给转发数、点赞数等指标. 这和PageRank算法的链接传递关系很相似.

对于某一指标i, 将它的被依赖指标集记为S, 考虑依赖关系得到:

每一轮更新后, 指标权值就会发生相应变化. 需要对更新后的权值作归一化处理:

重复步骤(10)和(11)作迭代运算, 直到数值趋于稳定.

矩阵变更运算是否已经收敛的判定条件是:

当δ≤0.1时, 可以认为矩阵的变更已趋于稳定, 可以停止迭代运算.

经过PageRank算法思想改进的指标权值, 体现了各指标间的内在关联, 符合整体性考虑的要求.

3 AHP权值计算

1) 构造层次分析模型

构建出如表1的层次分析模型.

2) A-B层间的权向量

首先需要建立合理的判断矩阵, 它是指标元素两两重要性比较的直观数据体现. 根据反映指标相对重要性的九级度量法, 初步构造出目标层与一级指标层之间的判断矩阵如表4所示.

表4 判断矩阵A-B

下面计算矩阵特征向量与特征值.

根据公式(4)可以得到:

根据公式(5)可以得到:

同理,w2= 0.4054,w3= 0.1140.

即A-B的特征向量为:

由公式(6)可以得到:

下面检验该判断矩阵是否满足一致性要求. 由公式(8)、(9)可以得到:

因为CR＜0.1, 故矩阵满足一致性要求.

3) B-C层间的权向量

参照2)所示步骤, 分别求出以下几个B-C层次间特征向量为:

4) 计算综合权重表

根据以上步骤, 利用权向量对权值的分配, 得到综合权重表如表5所示.

表5 综合权重表

5) 基于PageRank的优化算法对权重表修正

考虑各指标间的依赖与被依赖关系, 得到指标依赖关系图如图1所示.

图1 指标依赖关系图

图1中总播放次数C11指标依赖于总评论数C21、总点赞数C23、总转发次数C31、总转发用户数C32, 同时C11也被总转发数C31指标所依赖. 其他指标也都存在各自的依赖指标集以及被依赖指标集.

根据公式(10)、(11)、(12)作多次迭代运算, 直到各指标权值实现稳定收敛.

经过基于PageRank的优化算法, 得到更新后的权值表如表6所示.

表6 AHP优化后的综合权重表

4 实验分析

为验证本文提出的评比模型的有效性, 进行了模拟实验. 从数据集中选取了十个征选视频, 首先由相关工作人员进行打分, 得出专家评估分. 再分别用本文的层次分析法模型以及均等权重法进行量化打分, 计算出各自的综合评比分数. 由实验结果表7看出, 本文评比模型计算出的评分数据与工作人员给出的评分数据更为接近, 说明其具有一定合理性.

5 结语

本文提出了基于层次分析优化算法的视频网上评比方法, 首先分析了评比因素并建立了层次分析模型,通过层次分析优化算法得出各指标的被赋予权重, 最后计算出在该模型下的综合得分, 经实验验证该方法具有良好的分析效果. 与传统的人为主观赋予权重方法相比, 减少了主观因素的不利影响, 合理有效地解决了多指标应用场景的综合评比问题. 本文引入的方法简单、易于操作, 能很好地解决视频网上评比问题, 为新媒体时代其他传播工作的研究也提供了一些参考价值.

表7 实验结果