基于Bhattacharyya系数的改进相似度度量方法

杜茂康，王忠思，宋 强

(1.重庆邮电大学 电子商务与现代物流重点实验室，重庆 400065；2.重庆市通信管理局，重庆 401121)

0 引 言

随着“信息过载”问题的日益突出，个性化推荐服务研究备受青睐。其中，协同过滤技术得到了广泛的研究和应用，在基于近邻的协同过滤推荐算法中，相似度的计算至关重要[1-4]。G. Salton等[5]提出了运用余弦方法计算信息相似度而检索信息；B. Sarwar等[6]改进了余弦相似度方法计算项目相似度，优化了相似度的计算方法；U. Shardanand等[7]用评分值中位数替代评分值均值提高了皮尔逊系数度量相似度的准确性，即CPC(constrained pearson correlation)算法；MSD(mean square difference)算法运用均方位移表示相似度，但性能较差；J. Bobadilla等[8]结合CPC算法和Jaccard系数度量相似度方法提出了JMSD(combined Jaccard and MSD)算法，虽然解决了过度依赖共同评分项的问题，但仍然存在评分值利用率低的问题；Ahn等[9]提出了PIP(proximity impact popularity)相似度度量模型，考虑用于评分的接近、影响和普及3个方面计算用户相似性，但没有考虑用户全局偏好。相似度方法及计算公式如表1所示。

表1 常用相似度计算方法

已有的研究表明，传统的相似度计算方法存在过度依赖于共同评分项的问题。当共同评分项少时，传统方法不能准确地计算用户或项目之间的相似度。另外，在计算相似度时，上述方法利用的数据均为共同评分数据，忽略了其他的评分信息，这也在一定程度上降低了计算用户相似度的准确性。因此，传统方法在计算用户或项目之间的相似度时局限性很大，准确性有待改进。

为了解决已有相似度度量方法依赖于共同评分项的问题，Bidyut Kr. Patra等[10]提出了基于Bhattacharyya系数的相似度度量方法。然而，当项目之间相同评分值的绝对数量差异显著以及相同评分值个数占评分值总数比重小时，运用此方法得到相似度准确性不高。

针对基于Bhattacharyya系数相似度计算方法存在项目间相同评分值绝对数量差异显著的问题，本文运用权重法对其修正；对于相同评分值个数占评分值总数比重小的问题，引入拉普拉斯(Laplace)校准法解决。改进后的Bhattacharyya系数(improved Bhattacharyya coefficient，IBC)能够利用所有的评分信息，有效提升了相似度的准确性。基于IBC相似度度量方法在解决基于Bhattacharyya系数相似度度量方法存在的问题的同时，也保证了较低的时间复杂度。另外，传统相似度度量方法存在的数据稀疏性、冷启动以及可扩展性等问题严重影响了相似度计算的准确性，解决这些问题成为相似度度量方法研究的主要趋势。改进的度量方法，有效地缓解了数据稀疏性的问题。通过真实数据集实验表明，IBC描述相似度的准确性和性能更优，更有实际运用价值。

1 基于Bhattacharyya系数的相似度度量

Bhattacharyya系数在信号处理、图像处理和模式识别研究领域已得到广泛地应用[10-12]。它主要用于度量2个概率分布之间的相似度。假设p1(x)和p2(x)分别表示连续的分布密度，那么，这2个分布密度之间的相似度，即Bhattacharyya系数为

(1)

如果X表示离散数据，则

(2)

(2)式中：p1(x)和p2(x)分别表示2个离散概率分布中x出现的频率。项目I和J之间基于Bhattacharyya系数相似度可表示为

(3)

基于Bhattacharyya系数的相似度度量方法以评分值的概率密度作为计算相似度的重要依据。它能够解决传统相似度计算方法中存在的数据稀疏性和过度依赖共同评分项的问题，但是本文分析发现该方法仍然存在如下不足。

1)没有充分考虑相同评分值占比小的问题。如果2个项目之间的共同评分值个数占所有评分值个数的比重很小，那么共同评分值不能够表示2个项目的评分分布情况，项目相似度的准确性也必然值得怀疑。例如项目I和J的评分分别为I=(1,0,2,0,4,0,4,0,4,0,4,0,4,0,4,0,4,0,4,0)T和J=(0,1,0,2,0,5,0,5,0,5,0,5,0,5,0,5,0,5,0,5)T。运用Bhattacharyya系数计算项目I和J的相似度BC(I,J)为

根据项目I和J的评分分布情况可以看出，评分值(1,2)为其相同评分值，但其个数占所有评分值总数的比重很小，不能真实地表示项目I和J的评分值分布情况，所以，这种情况下基于Bhattacharyya系数的相似度度量方法计算项目I和J的相似度时会有偏差。

2)忽略了相同评分值的绝对数量差异。2个项目之间相同评分值绝对数量的显著差异表明其评分值分布情况也存在显著差异，这必然会对项目之间的相似度产生影响。例如，项目I和J的评分分别为I=(1,0,2,0,1,0,2,0,1,0,2,0,1,0,2,0,1,0,2,0)T和J=(0,1,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)T。利用Bhattacharyya系数计算项目I和J的相似度BC(I,J)为

根据项目I和J的评分可以看出，相同评分值(1,2)在项目I和J中的绝对数量存在着显著差异，在计算相似度时会产生相应影响，项目I和J不完全相似，这与现实情况相符。

2 基于IBC相似度度量

为了解决基于Bhattacharyya系数相似度度量方法存在的不足，本文提出改进的相似度度量方法，即IBC相似度度量方法。IBC相似度度量方法的具体改进如下。

1)对于相同评分值占比小的问题，引入拉普拉斯校准法。设项目属性item=(R,NR,T),其中，R表示item的评分范围，NR表示R中每个评分值的个数，T表示item评分用户数。若评分值r∉R，则R={R,r}，NR=NR+1,T=T+R。那么，项目之间的相似度可表示为

h=RI∩RJ

(4)

示例1itemI={R=(1,2,4),NR=(1,1,8),T=10}和itemJ={R=(1,2,5),NR=(1,1,8),T=10}。引入Laplace校准法，则项目I和J的属性变为itemI={R=(1,2,4,5),NR=(2,2,9,1),T=14}和itemJ={R=(1,2,4,5),NR=(2,2,1,9),T=14}。由于项目I和J的相同评分值(1,2)占评分比重很小，而评分值4和5分别在项目I和J中占主要比重，所以在计算项目I和J的相似度时更应该考虑评分值4和5的分布情况。基于IBC相似度度量方法，计算项目I和J的相似度IBC1(I,J)为

运用基于IBC相似度度量方法计算项目I和J的相似度时，项目中所有的评分值均参与了相似度的计算，能够更准确地反映项目之间的相似度。

2)对于相同评分值绝对数量差异问题，运用权重法进行修正，权重值为

(5)

(5)式中：cih和cjh分别表示项目I和J中评分为h的个数。如果项目I和J中相同评分值的绝对数量差异越大，则权值越小项目之间的相似度越小；反之，权值越大，项目之间的相似度越大。这与现实情况相符。

利用权重法计算第2节的示例二中项目I和J的相似度IBC2(I,J)如下

虽然项目I和J都只含有共有评分值(1,2)，但是相同评分值之间的绝对数量差异显著，从现实情况看，运用基于IBC相似度度量方法计算项目I和J之间的相似度更准确。

综上所述，基于IBC相似度度量方法计算项目之间的相似度为

(6)

3 实验结果与分析

基于IBC相似度度量方法不仅充分利用了项目的所有评分信息，而且解决了相同评分值在不同项目中绝对数量差异显著的问题。为了验证基于IBC相似度度量方法的有效性，将该方法用于协同过滤推荐算法(improved Bhattacharyya coefficient in CF，IBCF)中，结合基于IBC相似度度量方法和改进的余弦相似度度量方法得到最终用户相似度为

(7)

如果项目I和J的相似度高，那么IBC(·)能够提高用户U和V的相似度；反之，IBC(·)降低用户U和用户V的相似度。其中，

(8)

(8)式中，rU,med和rV,med分别表示用户U和V所有评分值的中位数。

在实验中，本文运用现有相似度计算方法实现不同的基于用户的协同过滤算法。传统相似度计算方法(如CPC，JMSD,MSD(mean-squared difference))和PIP以及BCF(bhattacharyya coefficient in CF)，并以相似度计算方法名代替协同过滤算法名称。

3.1 数据集

为了验证本文提出的IBC相似度度量方法的效果，实验选用由美国明尼苏达大学GroupLens研究项目组搜集和整理的MovieLens数据集。选用的数据集包含6 040个用户对3 799部电影1 060 000个评分信息，评分值越高，表示偏好程度越高。具体如表2。该实验选择其中的80%作为训练集，20%作为测试集。

为验证算法的有效性，本文选用了较高稀疏程度的数据子集。数据集的稀疏度即为表3中K值，即所有评分所占百分比。

表2 实验数据集

表3 数据集稀疏性

3.2 评价标准

推荐系统的研究者构建了几类评估属性比较推荐系统的质量。这些评估属性大致可以分为2类：预测准确性和分类准确性[13]。

预测准确性：统计精度度量方法中的平均绝对误差(mean absolute error, MAE)被广泛用于评价协同过滤推荐系统的推荐质量。因此，推荐质量评价采用了常见的平均绝对误差MAE。在测试集上首先运用推荐系统预测出用户的评分，然后根据测试集中用户的实际评分，计算出2者的偏差，即为MAE的值。

不同于“地平线2020”根据不同领域的研究主题招标，通过专家评审择优立项形成项目，“地平线欧洲”将在计划下推行任务/使命导向性的项目执行和评估方式，提出了“面向任务的研究和创新”，通过任务目标统领不同研究领域的研究问题，鼓励跨学科、跨领域的联合研究和创新实现既定任务目标。“任务/使命导向性”的项目设立、执行和评估方式，有利于“地平线欧洲”计划更有效地针对经济、社会亟待解决的问题提出有效的科学、技术解决方案，也将更加有效地发挥欧盟研发框架计划的影响力。

假设预测用户评分值为{p1,p2,…,pn}，对应的实际评分值为{q1,q2,…,qn}，则MAE的计算公式为

(9)

类似的，均方根误差RMSE(root mean square error)的计算公式为

(10)

分类准确性：分类准确性主要测量推荐系统的质量性能。常用的评估分类准确性的属性主要有：准确率和召回率。准确率和召回率的计算公式分别为

(11)

(12)

(11)—(12)式中：Lr表示推荐给目标用户的项目列表；Lrev表示数据集中相关项目列表。

另外，这2种评估属性必须有所取舍。例如，增加Lr，Recall增加，Precision就会减少。因此，将2种属性结合在一起对推荐系统进行评估，此种方法称作F1值，其计算公式为

(13)

3.3 实验结果与分析

本文分析了数据集子集的特征，并且认为每个用户均为活跃用户。图1和图2分别表示利用数据集子集ML中不同协同过滤算法所得到的MAE和RMSE，图中K-nearest表示目标用户最近邻居个数。从图1和图2中可以看出，本文提出的协同过滤相似度计算方法与现有的协同过滤相似度计算方法相比，误差减少，现有的协同过滤相似度计算方法在计算活跃用户的近邻时只考虑共同评分项目的评分，不能完全利用评分信息。因此，基于现有相似度计算方法的协同过滤算法在预测时出现较大误差。虽然BCF算法很大程度上显著减少了预测误差，但是其在计算相似度方面仍可改进。

图1 MAE随K-nearest的变化趋势Fig.1 MAE vs K-nearest numbers

图2 RMSE随K-nearest的变化趋势Fig.2 RMSE vs K-nearest numbers

不同协同过滤算法的F1值如图3所示。从图3中可以看出，IBCF推荐算法的性能比其他现有协同过滤算法更稳定。IBCF算法的F1值在K=300处约为0.7，BCF算法的F1值约为0.64，PIP相似度计算方法的F1值与MSD方法接近。传统的相似度计算方法(CPC)性能最差，F1值均不高于0.5。由此可以看出，IBC相似度计算方法更能准确地计算相关项目的相似度。

图3 F1值随K-nearest的变化趋势Fig.3 F1 vs K-nearest numbers

3.4 时间复杂度分析

表4 IBCF与BCF时间复杂度比较

从表4可以看出，本文提出的相似度度量方法没有增加BCF算法的时间复杂度。

4 结 论

由于现有的基于近邻的协同过滤相似度计算方法在寻找活跃用户的近邻时不能充分利用稀疏数据的评分信息，所以不能够进行可靠有效的推荐。本文提出的基于IBC相似度度量方法引入Laplace校准法和权重法，充分利用所有评分信息，改进了基于BC相似度计算方法的不足，提高了推荐的可靠性。此方法充分利用了项目的所有评分信息以及解决了相同评分值在不同项目中绝对数量差别显著的问题。通过MovieLens数据集进行实验可知，基于IBC相似度度量方法在高稀疏性数据集中能够提高相似度的计算准确性。