基于Skyline Query的高声誉用户识别方法研究

刘晓露，贾书伟，王建民

（1.复旦大学a.经济学院，b.泛海国际金融学院，上海 200433；2.河南农业大学信息与管理科学学院，郑州 450002；3.安徽理工大学经济与管理学院，安徽淮南 232001）

0 引言

准确评估用户声誉对在线评分系统的产品质量排名具有重要意义[1-3]。随着科学技术的发展，许多在线网站都使用评分系统，用户在网上浏览、购买产品后，可以根据产品的质量对产品的体验给出一个打分[4-5]。由于系统中用户的不诚实或不熟悉，通过简单地对评分取平均来排列产品可能不那么准确[6-7]。因此，建立用户声誉系统是非常重要的一环[8-10]。本文给出在线评分系统中的声誉(reputation)的定义：一个用户的声誉是在特定的时间段和上下文环境中，依据用户对产品的历史评分，对该用户可以对相应产品做出准确评价(符合大众认知)的感知。基于用户对产品的评分对用户声誉的研究近几年取得了非常显著的成果。目前三种主要的用户声誉度量方法有：声誉和质量不断迭代的方法[6,11-16]、分组方法[17-18]和贝叶斯方法[19]。声誉和质量不断迭代的方法中用户声誉和产品质量是相互影响、相互依赖的；在分组方法和贝叶斯方法中，用户声誉通过评分计算得到，不依赖于产品质量。

不同的方法从不同角度对用户声誉进行度量，同时不同方法度量用户声誉和产品质量的效果也是不同的。如何综合不同方法的结果对用户声誉有一个总体的认识是一个很重要的问题，最直接的处理方法就是给每一个度量方法的结果赋予一个权重，用权重平衡每一种方法的声誉结果，最终得到一个加权平均的用户声誉。然而，这样处理的前提是每个方法的声誉值是可以归一化的，这样各个方法是可比较的。这几乎是不可能的，因为有的方法得到的声誉值是没有上限的。同时，每种方法的权重的设置没有一个统一的标准，随意的设置显然是不合理的。还有一种方法就是解决“排序聚合”问题[20-21]，选择适合的调整方法将不同方法计算得到的排序列表融合成一种排序结果，同样的问题是所选取的调整方法存在是否适合和公平的问题。同时，随着科学技术的发展，在线评分系统中海量的数据被采集和记录，无时无刻不在增加海量数据，世界上90%以上的数据是最近几年才产生出来的，大数据时代的到来对在线用户声誉的总体认知提出了更多的挑战。

海量数据爆炸式增长，不同声誉度量方法产生不同的排序列表，可以不必生成一个总的排序列表，根据不同方法度量得到的用户声誉找到一部分声誉高的用户，这部分用户不被其他用户所支配。鉴于此，本文引入有效处理海量数据的SkylineQuery的方法来解决这个问题，提出一种基于Skyline Query的高声誉用户识别方法，找到的Skyline集合中不被其他用户所支配的用户，即为高声誉用户。同时在实证数据集中分析不同时间段上得到的集合Skyline中高声誉用户的规律，实验结果表明基于SkylineQuery得到的高声誉用户对于大家公认的质量比较高的产品可以给予更高的评价。

1 Skyline Query方法

Skyline Query(Skyline查询)是一种典型的多目标优化的问题[22-24]，也称为帕累托最优(在不损害他方利益的情况下，自身已达最优)或极大向量问题。在数据库领域中，Skyline查询最早是由Borzsony等[25]在2001年提出，自此一直是研究的热点之一。Skyline查询是在给定的n维数据集合U中选择一个子集，这个子集中的任何一个点都不能被U中的其他点所控制，也叫支配。所谓的支配关系是指U中的两个点p和q，p在每一维上都优于或等于q，并且p至少在其中某一维上优于q，则称p支配q，这里的优于并不是严格意义上的大小，而是根据实际需要而定。Skyline查询返回的是一个集合，其中的每一点都称为SP(Skyline Point)，这些SP的集合称为Skyline。

图1 饭店的选择入住的skyline查询问题[25]Fig.1 Skyline query of hotel choice

Skyline查询问题在生活中是很常见的，如学校的选择、股票的选择、房子的选择等等。以一个经典的例子——饭店的选择入住问题[25]来说明Skyline方法的应用。假设某个游客到一个地方旅游时，想找一家价格便宜且距海滨近的饭店入住。图1中的每个小圆点都代表一家饭店，X轴表示饭店的价格，单位是美元，Y轴表示饭店到海滨的距离，单位是千米。可以看出，该游客只需要考虑位于折线上的那些点就可以了。至于不在折线上的点，总是可以在折线上找到一点，价格上更便宜或者距海滨更近。折线上的点支配了所有其他不在折线上的点，而折线上的点之间不存在支配关系。位于折线上的点就是Skyline查询的结果集。

下面介绍一下关于Skyline查询的定义和性质。

1)支配：给定一组n维空间D中数据点的集合U，数据集中的任意两个点p(p[1],p[2],…,p[n])和q(q[1],q[2],…,q[n])，如果在所有维度上p[i]≥q[i],(1≤i≤n)，并且至少在某一维j上p[j]>q[j]，则称p支配q。

2)Skyline：给定一组n维空间D中数据点的集合U，Skyline就是所有不被其他点支配的点的集合。

Skyline查询有以下性质：

1)反自反：数据集U中的两个点p(p[1],p[2],…,p[n])和q(q[1],q[2],…,q[n])，如果在所有维度上p[i]=q[i],(1≤i≤n)，那么这两个点不存在支配关系。

2)反对称：数据集U中的两个点p(p[1],p[2],…,p[n])和q(q[1],q[2],…,q[n])，如果p支配q，那么q不支配p。

3)传递性：数据集U中的3个点p(p[1],p[2],…,p[n])和q(q[1],q[2],…,q[n])以及r(r[1],r[2],…,r[n])，如果p支配q，q支配r，那么p支配r。

Skyline查询依据不同的条件从集合中得到候选集合，即满足人们条件的最佳的结果集，从结果集中再根据自身喜好选择最想要的结果。在数据库领域中，Skyline查询得到了广泛的关注和研究。文献[24]是对于数据量小、可以放入内存时的Skyline查询提出的算法。在数据量大、无法放入内存的情况下，为准确高效解决Skyline查询的问题，研究学者提出了诸多Skyline查询方法，包括集中式Skyline算法和分布式Skyline算法。其中集中式Skyline算法有块嵌套循环算法BN[25]、分治算法D&C[25]、位图算法Bitmap[26]、最近邻算法NN[27]、排序过滤算法SFS[28]、分枝界限算法BBS[29]、BBS+算法[30]等。分布式Skyline算法主要有P2P对等网络环境下的Skyline算法、Web应用环境下的Skyline算法[31,32]和基于MapReduce的Skyline算法[33,34]。P2P对等网络环境下的Skyline算法有基于CAN网络拓扑的DSL算法[35]、基于BATON网络拓扑的SSP算法[36]、iSky算法[37]、SSW算法[38]、基于路由索引DDS算法[39]等。

下面介绍一些本文中基于Skyline查询方法寻找高声誉用户时采用的排序过滤算法SFS[28]：

1)将所有数据先进行一次预排序，当数据点全部按单调函数排序时，排在前面的点便不会被排在后面的点所支配，提前剪枝掉不可能属于Skyline结果的数据点，此时数据点集合设为T；

2)在内存中用一个窗口S保存暂时不被其它点所支配的点，初始设S=0；

3)依次遍历每一个数据点，使之与窗口S内的所有的点一一比较，最终窗口S中的点集合即为Skyline。

2 二部分网络中声誉度量算法

2.1 声誉度量算法

在复杂网络中，在线评分系统可以建模成用户—产品二部分网络，结构图如图2所示。其中有两类节点，圆圈代表用户，方框代表产品，用户和产品之间的连线表示用户对产品的打分，也可表示用户浏览、购买或收藏过产品。下面介绍目前在线评分系统中三种主要的用户声誉度量方法：声誉和质量不断迭代的方法[6,11-16]、分组方法[17,18]和贝叶斯方法[19]。

图2 用户—产品二部分网络的结构图Fig.2 Structure diagram of the user-object bipartite networks

1)声誉和质量不断迭代的方法。用户声誉和产品质量是相互影响、相互依赖的。假设产品有其内在的质量，通过用户评分与产品质量的关系(距离或相关系数)度量用户的声誉，再通过用户声誉和评分(以用户声誉为权重)度量产品质量，如此迭代直到用户声誉和产品质量达到稳定为止。代表性方法有：Iterative refinement algorithm[11](简称IR方法)、Correlation-based ranking algorithm[6](简称CR方法)、Iterative algorithm with reputation redistribution[13](简称IARR方法)、IARR2方法[13]和Iterative ranking algorithm via user activity[16](简称IRUA方法)等。声誉和质量不断迭代的方法利用用户声誉和产品质量相互依赖的迭代过程来计算，优点是计算用户声誉和产品质量的准确性高，不足之处在于迭代方法的时间比较长，且这几种方法在某些数据集上不收敛。

2)分组方法。用户声誉的度量是通过评分计算得到，不依赖于产品质量，从打分分组的角度度量声誉。通过评分分组的方法，把对某一产品做出相同评分的用户分组，用组数来表示这一评分的可信度，每个用户的声誉用该用户的每一个评分的可信度的均值与标准差的比值来表示。代表性方法是Group-based method[17](简称GR方法)和Iterative Group-based method[18](简称IGR方法)。GR方法突破了已有迭代方法中用户声誉与产品质量相互依赖的思想，提出分组的方法度量用户的声誉，计算时间较短。缺点是用做出相同评分的用户个数所占的比例表示这一评分的可信度容易造成民主暴力，且该方法在度量用户声誉时只考虑了相同评分的用户个数，没有考虑具体的评分。

3)基于贝叶斯分析的方法。贝叶斯方法是用概率论来度量用户声誉。用户声誉表示成一种概率，被评价者下次提供满意服务/做出合理评分的概率(表示成参数θ)，用户声誉可以根据参数θ的后验分布得到的期望来度量。参数θ的后验分布综合了总体信息，样本信息和先验信息。二部分网络中的代表性方法是Ranking algorithm via the Beta probability distribution[19](简称RBPD方法)。其中每一个打分用一个二进制来刻画：“合理打分”(表示为1)和“不合理打分”(表示为0)。合理打分(Fair rating)的定义是：用户i对产品γ有一个打分riγ，这个打分将会被判断是否与对产品γ打分的大部分观点一致，这里的大部分取过半数即可。同时，参数θ的先验概率分布设定为Beta概率分布。RBPD方法的时间复杂度与网络规模(打分总数)呈线性关系，在处理增量数据及大规模数据上可以快速有效地度量用户声誉。略显不足之处在于度量声誉的准确性与传统的迭代方法相比差别不大，没有明显的准确性上的优势。

2.2 声誉度量方法分类

在上述声誉度量方法中，有的方法之间存在联系，因此综合多种声誉度量方法进行用户行为分析时，先对上述几种方法[6,11,13,16-17,19]用K-means算法来得到声誉度量方法的分类，选取代表性的算法用于本文的分析。

2.2.1 数据集

本文为了分析用Skyline查询识别高声誉用户的结果，采用一个对电影评分的网站的数据集来进行实证研究：MovieLens。MovieLens是一个对电影进行在线评分的网站(http://www.grouplens.org)，用户可以对电影进行打分，网站可以对用户提供个性化推荐服务。用户对自己浏览、收藏过的产品按照5分制进行打分，其中最低分1分表示最不喜欢，最高分5分表示最喜欢。如果用户看了一部电影并且对它进行了打分，用户与电影之间就会产生一条连边。本文需要分析随时间变化的Skyline查询结果，选取的MovieLens数据集中共包含69878个用户、10677个电影和10000054条打分，时间跨度为13年，统计特性如表5-1所示。

表1 Skyline查询识别高声誉用户采用的MovieLens数据集的统计特性Tab.1 Basic statistical properties of the MovieLens date set

表2 对声誉度量方法进行K-means算法聚类的结果Tab.2 The clustering results by K-means for reputation measurement algorithms

2.2.2 声誉度量方法聚类结果

本文将声誉度量算法分为三类：迭代方法、分组方法和贝叶斯方法。在MovieLens数据集上根据多种声誉度量方法(IR、CR、IARR、IARR2、IRUA、RBPD、GR方法)分别进行用户声誉度量，根据得到的各方法上的用户声誉进行K-means算法[22]聚类的结果与本文的分类一致，K-means算法聚类的结果如表2所示。表2中可以看出，分类1有多种方法，从中取一种典型的方法CR方法来代表这一类方法，分类2和分类3中只有一种方法，所以本文取CR、RBPD和GR方法作为下面分析中用到的用户声誉度量方法。

3 基于Skyline查询方法识别高声誉用户

3.1 基于Skyline查询方法识别高声誉用户基本思想

本文用CR、RBPD和GR方法分别计算MovieLens数据集上用户的声誉，用Skyline查询的方法找到高声誉用户。其中，每个用户可以看成是一个三维空间的点，而三个维度上的数据分别是CR、RBPD和GR方法计算得到的用户声誉。所有用户的集合用U表示，Skyline查询是在用户集合U中选择一个子集，这个子集中的任何一个用户都不能被U中的其他用户所支配。所谓的支配关系是指集合U中的两个用户p和q，p在CR、RBPD和GR方法中任意一种方法上得到的用户声誉都高于或等于q，并且p至少在其中某一种方法上得到的用户声誉高于q，则称p支配q。Skyline查询返回的集合称为Skyline，即为高声誉用户。

3.2 实证数据集中高声誉用户识别结果

Skyline查询方法采用SFS方法，将MovieLens数据集按照时间标以1年为时间间隔取出多个数据子集，如1997年的数据集为1997年之前的打分数据构成的集合；2009年的数据集为2009年之前的打分数据构成的集合(总的数据集)。这样从1997年到2009年可以按时间取出13个数据子集。分别在划分的数据子集上计算得到的集合Skyline即为不同时间段上的高声誉用户，如表3所示。从表3可以看出，不同时间段上得到的集合Skyline中高声誉用户的数量和用户都不完全一样，发现以下规律：

1)会有新的用户加入到Skyline中；如2384、3854号用户等。

2)有的用户会离开Skyline；如71、1466号用户等。

3)Skyline不会每年都会有大的变化，而是会一个周期变化；大约三四年一个周期。

4)有一些用户一直在Skyline中；如12776号用户。

接下来，类似于第三章和第四章中选取数据集中的benchmark产品，在本文采用的MovieLens数据集中选择获得奥斯卡最佳影片奖提名的电影归类到benchmark产品集合，共选取277个benchmark产品。benchmark产品是大家公认的质量比较高的产品，比较Skyline用户对benchmark产品打4分或5分的平均比例与所有用户对benchmark产品打4分或5分的平均比例[τ]，如图3a所示。从中可以看出，Skyline用户对benchmark产品打4分或5分的平均比例高于所有用户对benchmark产品打4分或5分的平均比例，表明从集群行为层面来看，Skyline查询得到的高声誉用户对于大家公认的质量比较高的产品给予更高的评价。

表3的实验结果中Skyline查询中数据维度为3，不同维度不同声誉度量方法得到的Skyline集合会有所不同，用两种声誉度量方法(RBPD和GR方法)得到的用户声誉作为用户在两个维度上的数据进行Skyline查询得到的集合Skyline(高声誉用户)如表4所示。而用CR和RBPD方法得到的用户声誉作为用户在两个维度上的数据进行Skyline查询得到的集合Skyline(高声誉用户)如表5所示。可以看出，表4和表5中的结果(高声誉用户)中也存在上述四种规律。而且两种Skyline结果中高声誉用户的数量和用户也有区别，可以看出当声誉度量方法的数量和方法不同时，Skyline查询的结果(高声誉用户)也是不同的。而且，声誉度量方法的数量越多，即Skyline查询中数据维度越大时，得到的集合Skyline中高声誉用户越多。同时，比较表4和表5中的Skyline用户对benchmark产品打4分或5分的平均比例与所有用户对benchmark产品打4分或5分的平均比例，如图3b所示，结果同图3a结果一致，表明Skyline查询得到的高声誉用户对于大家公认的质量比较高的产品会给予更高的评价。同时，本文以CR、RBPD和GR方法作为用户声誉度量的代表性算法基于Skyline查询方法来识别高声誉用户，也可以将基于Skyline查询的高声誉识别推广到其他声誉度量算法，如IR、IARR、IARR2、IRUA方法等。

图3 Skyline用户与所有用户对benchmark产品打4分或5分的比例Fig.3 The ratio of rating 4 or 5 to benchmark objets for users in skyline set and all users

表4根据RBPD和GR方法计算得到的用户声誉进行Skyline查询得到的集合Skyline
Tab.4SkylinesetbasedonuserreputationobtainedbyRBPDandGRmethod

年份Skyline用户1997718 358 12 77614 58616 78017 01022 86322 96423 68428 34733 62919982 9037 1499 52011 16013 28614 58616 27317 18033 62950 097199925 42137 09337 54144 48650 0972000712574792 384 3 1729 52011 16012 77613 28614 24215 07316 78016 83219 06737 33720012 384 3 698 5 8197 80410 51411 16012 77614 34016 780 18 75826 6082002712 384 4 35212 776 13 05213 22714 3402003712 384 3 854 5 8197 11811 16012 77613 22714 34020043 854 4 953 7 14410 09812 77613 06631 30620054 953 7 52210 09810 51412 77616 78021 65631 30620067120621129630142747031 30620073 510 5 68631 30631 59835 71637 54156 35620081 652 3 5105 68616 78031 30631 59835 71644 48620091 652 3 510 5 686 9 671 17 19131 306 31 598 35 716 44 486

表5 根据CR和RBPD方法计算得到的用户声誉进行Skyline查询得到的集合SkylineTab.5 Skyline set based on user reputation obtained by CR and RBPD method

4 结语

不同声誉度量方法从不同角度对用户声誉进行度量，同时不同方法度量用户声誉和产品质量的效果也是不同的。为了在海量数据中综合不同方法的声誉结果对用户声誉有一个总体的认识，本文引入Skyline查询方法综合不同声誉度量方法，将选取的有代表性的算法得到的用户声誉用到Skyline查询中，找到的集合Skyline(不被其他用户所支配的用户)即为高声誉用户。分析不同时间段上得到的集合Skyline中高声誉用户的规律，实证实验结果可以看出，得到的Skyline集合受不同维度不同声誉度量方法影响。所以选择合适的声誉度量方法应用到Skyline查询中是一个重要的问题。同时，以获奖电影作为benchmark产品，发现Skyline查询得到的高声誉用户对于大家公认的质量比较高的产品会给予更高的评价。本文的工作为在线评分系统中用户声誉的定性研究提供了一个新的思路。