遗憾最小化查询研究综述

郑吉平,马 源,马 炜,郝志扬,王美静

1(南京航空航天大学 计算机科学与技术学院,南京 211106) 2(软件新技术与产业化协同创新中心,南京 210093)

1 引 言

随着信息技术的发展,当下每天都在产生海量的数据,而如何从这些数据中提取简洁的、关键性的信息,用来支持用户多目标决策是数据库系统的一项重要任务.显然,对于大量的信息,用户很难从中直接找出感兴趣的内容.目前,研究人员提出了一些技术与工具来解决这个问题.其中,skyline查询top-k查询是两种最常用的技术手段[1-22].Skyline查询根据“支配”的概念,剔除掉部分被其它数据支配的点,从而返回数据集中不被任何点支配的信息.Top-k查询则借助用户指定的效用函数f,给数据集中的点进行打分,得出关于f评分最高的k条数据给用户,以达到缩减查询结果的目的.然而这两种方式都存在自身固有的缺陷,skyline查询不能控制查询结果的大小,当数据点的维度d增长,skyline集合的大小急剧增加,很难达到缩减数据集的要求;而top-k查询需要用户给出效用函数,多数情况下用户只能模糊的给出自己的偏好,难以提供较为精确的效用函数,且这样也给用户带来了额外负担.因这些缺陷的存在,k代表点查询(k-representative queries)被广泛研究[23-27].特别的,对于k代表点查询,在不借助用户提供效用函数的前提下就能得到k个代表点,使得大部分用户满意;其兼顾了top-k与skyline查询的优点.典型的k代表点查询有最大支配数skyline查询、基于距离的代表skyline查询、k-遗憾(k-regret)查询与k-覆盖(k-coverage)查询.其中,由Nanongkai等人[26]提出的基于遗憾的k代表点查询,即k-遗憾查询,在过去十余年被广泛研究.其利用“遗憾”(regret)作为衡量指标,得到遗憾最小的结果集近似地代表整个数据集合.随后,一些相关的研究与解决方案相继涌出.本文对遗憾查询相关研究进行了概述,并对未来的一些可能研究方向进行了展望.

本文安排如下:第2节简要地介绍top-k查询、skyline查询及除了遗憾查询之外的k代表点查询;第3节详细地介绍了遗憾查询的概念与一些拓展研究;第4节对未来的相关研究与应用做出了展望;第5节总结了本文.

2 代表性查询

在过去二十多年里,top-k查询与skyline查询在多准则决策过程中起着重要的作用.

2.1 Top-k查询与skyline查询

Top-k查询作为较早提出的处理多准则问题的策略,具有广泛的应用领域[28，29].许多搜索引擎根据一些判断机制,展示给用户比较感兴趣的k个查询结果.而得到这样的k个查询结果的常用方法是对每条数据进行打分,从而获得评分最好的k条数据.因此,top-k查询的关键点在这类打分函数(即效用函数,utility function,亦称评分函数,score function,或偏好函数,preference function)的确定;根据效用函数,搜索引擎可以很容易反馈最佳的答案给用户.Top-k查询在之前受到了广泛的关注[11-22],针对不同场景下有不少的经典查询算法.Fagin[18]提出算法FA算法(Fagin Algorithm,FA)解决确定数据集上的top-k查询;Lian等人[19]提出概率top-k支配(Probabilistic Top-kDominating,PTD)查询响应概率数据集情景下的查询;Papadopoulos等人[20]提出了基于支配分析的查询算法等.然而,top-k查询的前提是用户必须给定效用函数,而很多情形用户无法提供效用函数或无法准确给出,因此限制了top-k的应用场景.

Börzsönyi等人[1]首次将运筹学领域中的帕累托(Pareto)概念[20]引入到数据库领域中,可以避免top-k查询需要用户提供效用函数的缺陷,提出skyline查询的概念.Skyline查询根据“支配”的概念对数据进行查询.对于一个具有d维属性的数据集D,其中的数据点p=(p[1],p[2],…,p[d])支配另外一点q=(q[1],q[2],…,q[d])需要满足在任一维度i的属性值上有p[i]不劣于q[i],且至少存在一个属性值p[j]优于q[j].对于skyline查询,不会被任何点支配的数据点构成了整个skyline集合,即skyline查询的结果.随后,高效的skyline求解算法被提出,如BNL(Block-Nested-Loops)算法[1]、BBS(Branch-and-Bound Skyline)算法[2]、D&C算法(Divide and Conquer)[1]等.其中,BBS是目前I/O最优的方法.另外一些研究则是skyline的一些变体,可大致分为两类:一类是为解决skyline返回集大小不可控的研究如约束的skyline(constrained skyline)[3]、子空间skyline(subspace skyline)[4，5]、k-skyband[6]、-skyline[7]及下节介绍的k代表点研究;另一类则是不同情景下的查询,如连续skyline查询(continuous skyline queries)[8]、概率skyline查询(probabilistic skyline queries)[4]等(详情可参考文献[9,10]).Skyline查询虽然不需要效用函数的指定,但存在输出集大小不可控制的问题,通常随维度的增加呈指数增长[9].下面通过多准则决策的一个具体实例介绍top-k与skyline查询结果集.

例:如何选购汽车是一个典型的多准则决策例子.这里考虑每辆汽车具有两维属性:马力(Horse Power,HP)与每加仑汽油可行驶英里数(Miles Per Gallon,MPG).任何一个购买者都希望自己选中的汽车动力强劲(马力大)、且耗油量小(每加仑汽油行驶里程数最大).然而,这两种属性一定程度上相互掣肘,往往不存在马力最大,而耗油量最小这样的汽车.因此,从数据库中挑选出具有代表性的汽车展示给用户,是一个值得考虑的问题.

如图1所示,假设有5辆汽车{p1,p2,p3,p4,p5}该例中的skyline集为{p1,p3,p4},而p2被p1、p3支配,p5被p3、p4支配,用户不会选择马力小则耗油量大的p3与p5.因此,skyline查询将{p1,p3,p4}作为结果集反馈给用户,以供用户更好地选择.而如果用户可以精确的给出了自己对这两个属性的偏好值,如对HP有着70%的倾向,其余30%的权重给予MPG属性上,则p1～p5的得分为{109.1,89,146,149.1,107},若k=2,则应该返回汽车{p4,p3}给用户.然而正如前面所提到,skyline查询结果不可控制、top-k查询需要用户精确的提供效用函数,研究者更多地关注k代表点查询.

图1 汽车数据集例子Fig.1 Example of car database

2.2 k代表点查询

提出k代表点查询的目的是避免skyline与top-k查询输出结果集的数量不可控或需要提供效用函数的缺陷,用一个可控制数量(k个)的子集呈现给用户.典型的k代表点查询有k-遗憾查询,top-k个skyline代表点查询,基于距离的k个skyline代表点查询以及k-覆盖查询等.

1)Top-k个skyline代表点查询.Lin等人[23]将数据点p的支配数量|Dom(p)|作为重要性程度,选取一个大小为k且具有最大支配数量的子集S,即最大化其支配的非skyline数据点的数目,即:|Dom(S)|(=|∪q∈SDom(q)|).Lin等人[23]将该问题等价为最大集合覆盖问题(Maximum Set Cover problem),证明了该问题是NP-难的,并设计了具有1-1/e近似率保证的贪婪算法.

2)基于距离的k个skyline代表点查询.Tao等人[24]提出用欧式距离作为评估的指标,返回k个中心点集合S代表skyline集合,使得被支配点到离它最近的中心点距离最小,即最小化maxq∈D〗S{minp∈S‖q,p‖}.文献[24]在2维情况下设计了精确算法,并证明了高维情况下是NP困难的(NP-hard),提出了具有1/2近似率的贪婪算法.

3)k-覆盖查询.Soholm等人[25]提出了k-覆盖(k-coverage)查询问题,通过支配区域的概念定义点的覆盖范围.通过选择具有最大覆盖范围的k个点集合,近似地替代整个skyline空间.由于k-覆盖问题是个NP-难问题,因此该查询也是NP困难的.此外,Bai等人[30]考虑的在数据流上的k支配问题与k-覆盖问题类似;Zheng等人[31]将静态数据下的k-覆盖查询扩展到数据流与数据动态变化情况.

3 k-遗憾查询

尺度不变性(Scale invariance)[26]指的是当数据集中点的属性值按比例缩放后,对查询结果不造成影响;而稳定性(Stability)指在数据集中加入或删除非skyline点不改变查询结果.上述k代表点查询中,基于距离的代表skyline查询随着属性值的扩展,距离属性受到影响,不具备尺度不变性;top-k代表skyline查询因与支配点数量有关,加入非skyline点导致支配关系的变化,因此不具有稳定性.k-遗憾查询因其自身具备尺度不变性与稳定性成为近来备受关注的k代表点查询研究.

3.1 k-遗憾查询相关概念

首先介绍遗憾与遗憾率的概念.

遗憾与遗憾率[26]对于某一效用函数f,遗憾(regret)为数据集D与用户选取的代表性子集S的效用值之差,即rD(S,f)=f(D)-f(S),而遗憾率(regret ratio)定义为遗憾与D的效用值的比值形式,即rrD(S,f)=rD(S,f)/f(D).根据定义可知,遗憾率的取值范围是[0,1]:当遗憾率越接近0,表明用户见到该结果会越高兴;而遗憾率越接近1,则表明选中的集合不符合用户的兴趣,用户越不高兴.

由于用户的效用函数未知,用符号F表示所有可能的效用函数集合,则最大遗憾率(maximum regret ratio)定义为:

其表示在效用空间F下,选中集合S后的遗憾率最大值.因此,遗憾查询的目标是找一个满足条件的集合S最小化遗憾率rrD(S,F).下面给出正式的遗憾查询定义:

k-遗憾查询[26]给定由n个d维数据点构成的数据集D,效用函数空间F,与正整数k,寻找一个大小为k的子集S⊆D,使得rrD(S,F)尽可能地小.

目前大多数研究将效用函数限制在线性效用函数空间L下,即用线性效用函数刻画用户的偏好情况.

为解决k-遗憾最小化查询问题,Nanongkai等人[26]提出了简单有效的立方体算法(Cube).算法将数据空间划分为若干个超立方体,然后分别从各超立方体中选取一个数据点加入结果集中.Cube算法可以保证在最坏情况下,最大遗憾率不会超过:

Cube算法首先在1～d-1维属性上选择值最大的点到结果集中,然后根据第d维的属性值将数据点均匀地划分在(k-d+1)个桶(bucket)中.因同一桶中的数据点在1～d-1维上的属性值十分相近,而选取最好点的直观做法就是选取桶中d维属性最大的点.这样就可以近似地选取每个桶中效用值最大的点.而算法开始时在1～d-1维上选取属性值最大的点保证了解集在任意效用函数上的效用都足够大.此外,Nanongkai等人[26]证明Cube算法的最大遗憾率存在一个下界:对于任一正整数k,有rrD(S,F)= Ω(1/k2),即Cube算法输出的结果集始终存在不小于复杂度为1/k2的遗憾率.

图2 Cube算法计算示例Fig.2 Example of cube

然而,Cube算法分配桶时根据空间距离进行划分,一些桶中会出现不含有点的现象,导致算法最终并不能返回k个点(少于k)作为结果集;且尽管Cube对最大遗憾率有一个理论上界保证,但其实际运行效果遗憾率较大,因此Cube算法并不能满足用户对于结果集的质量需求.

为解决上述问题,Nanongkai等人[26]提出了基于Ramer-Douglas-Peucker(RDP)算法框架的贪婪算法RDP-Greedy.RDP算法最初用于近似曲线与多边形,随后被借鉴于其它领域并取得了良好的效果.RDP算法的主要思想是逐步优化最差的部分.基于此思想,针对遗憾查询的算法RDP-Greedy首先选取每一维属性值最大的点;紧接着迭代选取当前状态下“最坏”点,即对导致产生当前最大遗憾率的点,加入该点可以降低最大遗憾率的值.更准确的说,每轮加入的点是使得rrD(S,F)=rrS∪p(S,F)成立的p点.而确定这样的点,需要根据下面的线性规划(Linear Programming)计算得到:

maxx

s.t. (p-q)·v≥x∀q∈S

p·v=1

v[j]≥0 ∀j≤d

x≥0

上式使得线性规划目标值x取得最大的点q即为当前轮所求点,通过确定这样的“最坏”点不断地降低遗憾率,直至选满k个点.

基于遗憾的k代表点查询,可以应用于许多领域,如推荐系统、信息推荐、搜索引擎等.但由于一些情景下无法直接应用k-遗憾查询,因此从不同角度出发的k-遗憾查询相关研究被陆续提出.

3.2 更高效的算法

研究者为进一步提高查询质量与效率,从各方面出发做了不同尝试.Peng等人[32]、Agarwal等人[33]、Cao等人[34]与Xie等人[35]从几何性质出发设计了高效算法;Agarwal等人[33]与Ausdeh等人[36]分别将查询规约到命中集与集合覆盖问题;Nanongkai等人[37]、Xie等人[38]与Zheng等人[39,40]利用交互手段提高解集质量.此外,Dong等人[41]与Zheng等人[42]分别基于遗憾率函数的单调性特征与次模性质加快查询速度.

3.2.1 从几何性质出发

Peng等人[32]在skyline集上进一步提取出更小的候选集开心点(happy points),在此上进行k-遗憾查询可以提高查询效率.Peng等人[32]从数据点的几何性质出发,提出了效率更高的GeoGreedy算法,且具有与RDP-Greedy具有一样的质量保证.

基于上述临界比,GeoGreedy首先选取每一维上属性值最大的点加入到S,然后不断选择与当前解集临界比最小的p点加入到S.当最小临界值为1或选足k个点时,算法返回解集S.

图3 临界比示例Fig.3 Critical ratio

Peng等人[32]根据效用空间为线性的前提,对候选集进行预处理,处理后的数据集是比skyline更小的子集,但可以获得相同的结果集.Peng等人[32]将这种处理后的数据集称为开心点集合,下面给出开心点的定义.

开心点[32]给定n个d维数据点组成的数据集D与点p、q∈D,在每一维坐标轴上增加一个虚拟点vpi=(0,…,1,…,0)(只在第i个分量为1,其余都为0).这些虚拟点的集合记为VP,VP∪{q}的凸包构成的超平面记为H(q),若点p在H(q)的所有超平面内或下方,并且至少在一个超平面的下方,则p被q“支配”.这里利用线性空间的特性,对skyline中支配的定义进行了放松,减小了处理后集合的规模.如图4所示,在2维坐标轴上增加了两个虚拟点(0,1)、(1,0),2维空间下的超平面对应的是直线,因此H(p3)中含有直线p3-vp1与直线vp2-p3.从图中可以看到,p2在p3的超平面下方,因此p2被p3“支配”,将p2从候选集中删除.该例中如p1、p4这样不被其它点支配的,会保留下来,构成数据集的开心点集合.开心点少于skyline集合,但保留了在线性空间下不被支配的点,降低了查询算法的计算量.

图4 开心点示例Fig.4 Happy point

Agarwal等人[33]与Cao等人[34]几乎同时提出借助-kernel(-核)的概念来解决遗憾查询问题,且可以得到优于Cube算法的理论上界.

图5 -kernel示例Fig.5 -kernel

Agarwal等人[33]与Cao等人[34]证明,若集合S是数据集D的-kernel,则S在D上的遗憾率不超过.因此遗憾查询就可转化为求解-kernel问题,根据文献[43]中的算法可以求解出数据集的-kernel,大小为可以通过二分搜索(binary search)的方式,变化的数值得到大小为k的结果集,此时根据-kernel与k的关系,可以推出结果集遗憾率上界为

图6 Basis集合示例Fig.6 Basis set

Xie等人[35]借助Basis集合的定义提出了Sphere算法.该算法首先与Cube做法类似,将每个属性上值最大的d个点加入到S;随后计算出可以代表整个线性效用空间的子集L;根据L中的效用函数,计算出D关于L中每个效用函数的Basis集合,不断的将Basis集合中的点加入到S;若做完上步后|S|仍小于k则继续通过Nanongkai等人[26]提出的RDP-Greedy算法继续计算剩下要加入的点直至遗憾率为0或|S|=k,返回结果集S.同时,Xie等人[35]给出了与Agarwal等人[33]和Cao等人[34]借助-kernel一样的遗憾率上界.

3.2.2 规约到经典问题

Agarwal等人[33]将遗憾查询转化为命中集(hitting set)问题.

命中集问题[44]给定集合系统Σ = (D,R),R为D中子集的集合,若存在子集S⊆D,对于任意集合元素R∈R,都有S∩R不为空集,那么S就为该集合系统的一个命中集.

图7 命中集/矩阵最小最大流程示意图Fig.7 Hitting Set/Min-Max matrix procedure

Ausdeh等人[36]将最大遗憾率最小化问题转化为矩阵的最小-最大问题,提出了DMM算法.转化思想如下:首先对连续效用空间进行离散化处理,利用采样的方式近似代替原连续的效用空间,采样的效用函数集合记为U.通过给定的数据集D与效用函数集合U,计算出每一点关于U中效用函数的遗憾率,构建一个|D|×|U|的矩阵M(如图8所示),矩阵中的元素Mi,j对应着点pi在效用函数uj∈U上的遗憾率,因此求k个点的最大遗憾率最小值等价于在矩阵中找k行使得每一列的最小值最大者尽可能小.进一步地,矩阵最大最小问题通过设置阈值将问题进一步转化为集合覆盖问题(矩阵中元素大于则置0表示效用函数uj不在pi点对应的集合中;否则置1,可视作uj在pi对应集合中),满足集合覆盖的对应行可保证最大遗憾率不超过.因此遗憾查询问题就转化为集合覆盖问题的求解.与上述命中集类似,可通过二分搜索确定最佳的,并返回对应的解集.由上可以看出,HittingSet和DMM具有相似性,其本质原因是因为命中集问题(Hitting Set)和集合覆盖问题(Set Cover)互为对偶问题.

图8 矩阵最小最大问题示例Fig.8 Min-Max matrix problem

除此之外,Xie等人[47]设计的开心度算法,也可看作是从几何角度构建的集合覆盖系统,并通过贪婪算法[48]进行求解;Wang等人[49]将动态数据集下的遗憾查询问题建模成动态集合覆盖问题.由此可见,通过问题的转化求解遗憾查询是较为常见、有效的做法.

3.2.3 利用交互信息

Nanongkai等人[37]首次提出引入交互机制获取用户较为满意的点集.在不借助交互手段的遗憾查询中,往往很难通过只返回k个点的集合就可达到较小的遗憾率.而借助交互方式,可以有效地提高返回集的质量.Xie等人[38]等人提出了UtilityApprox算法每轮向用户展示s个数据点,让用户从中选取最感兴趣的点,从中逐渐获取用户的偏好信息.直到输出k个点可以使得最大遗憾率不大于时,停止交互.算法保证当遗憾率上界为时,需要进行O(sdlogs(d/))轮交互.

与Nanongkai等人[37]提出的算法相比,UH-Simplex算法可以保证用户确定最满意的点,需要较少的轮数.然而UH-Simplex仍需数十轮交互才能达到遗憾率为0的结果,Zheng等人[39]提出交互过程中让用户给每轮展示的点进行排序,利用排序得到更多的信息,减小交互轮数.

3.3 扩展到k-RMS

遗憾查询的一个不足之处在于评判用户满意的标准太过严格,即每次对用户的“最好”选择具有唯一性(最大遗憾率最小的).但实际上,用户的体验会不断变化.考虑一个旅馆住宿的问题,用户可能想尝试新的旅馆,而对推荐的“最好”旅馆因去过反而感到不满意.为解决这一问题,评价用户满意的标准就要更加灵活以适应用户不同需求.Chester等人[50]基于此提出了kRMS(k-Regret Minimizing Set)问题.kRMS查询对遗憾查询的概念进行了扩展,这里的用户遗憾率指的是选中点集中最佳的点与整个数据集中第k优的点的差距.本文用kmax(S,f)表示效用函数f下集合S中第k优的效用值,则kRMS查询下的遗憾率krr(S,f)定义为:

则在整个效用函数空间F下的最大遗憾率为:

mkrr(S,F)=supf∈Fkrr(S,f)

下面给出kRMS查询的定义.

kRMS查询[50]给定数据集D,效用函数空间F,正整数k,与输出集大小r,kRMS查询的目标是找到一个集合S⊆D(|S|=r)使得mkrr(S,F)最小化.

特别的,当k=1时1RMS问题等同于Nanongkai等人[36]定义的最大遗憾率问题.Chester等人[50]证明了1RMS问题可规约到著名的集合覆盖决定性(set cover decision)问题[51],由于集合覆盖问题是NP困难的,被规约的1RMS问题也是NP困难的.进一步,他们证明了高维的kRMS问题也是NP困难的.Chester等人[50]针对2维情况,设计了一个精确算法;在高维数据查询的情景下,沿用了Nanongkai等人[26]的算法思想,基于随机分割与线性规划提出了适用于kRMS的Greedy算法.Agarwal等人[33]与Cao等人[34]利用-核心集(kernel),从几何性质出发设计算法应答kRMS查询.

表1 遗憾查询主流算法对比Table 1 Comparison among the mainstream algorithms

上述是对主要的遗憾查询核心算法的总结;除此之外,还有3个主要遗憾查询的主要变种在该领域中也备受重视,分别为:平均遗憾率查询、非线形效用函数下的遗憾查询和动态数据集下的遗憾查询.

3.4 平均遗憾率查询

一般而言,查询结果对于较多用户来说都是很满意的,只有极少数的用户偏好过于极端,而为照顾这些极少数用户,最大遗憾率查询牺牲了绝大多数人的利益(这些用户的遗憾率可以更小).Nanongkai等人[26]提出的遗憾查询会导致只关注着最不开心的用户,而忽视了其他用户的体验.Zeighami等人[52]指出在一些情景下,最大遗憾率不能很好地衡量用户满意程度,并提出了一种考虑用户效用函数概率分布的遗憾查询,即平均遗憾率查询(average regret queries)的概念.

平均遗憾率 给定数据集D,效用函数F服从概率分布η,集合S⊆D的平均遗憾率定义为:

Zeighami等人[52]指出平均遗憾率函数是超模函数(supermodular function),利用超模函数特性与劣汰的思想,设计出Greedy-shrink算法.Greedy-shrink算法置初始解S为整个数据集D,每次从数据集S中去掉影响遗憾率最小的点q,即q=argminp∈Sarr(Sp),直至|S|=k时返回S.

Qiu等人[54]将问题转化为等价的开心度(1-arr的形式)最大化问题,证明了开心度函数满足次模(submodularity)性质,据此设计出加速算法,提高了求解效率.Zeighami等人[55]在2019年又提出了剪枝与减小候选集的策略加速平均开心度的计算过程.此外,Shetiya等人[56]引入数据挖掘领域的聚类方法设计了k-MEDOID算法,基于此提出了一个统一框架,通过该框架可分别响应最大遗憾率查询与平均遗憾率查询.

3.5 非线性效用函数下的遗憾查询

之前提到Nanongkai等人[26]对用户效用函数做了线性假设,然而线性效用函数有时却不能准确地刻画出用户的偏好.在挑选汽车时,若用户想购买具有较大马力的汽车,面对马力分别为260与280马力的汽车A汽车B,由于汽车B具有更大的马力,因此用户会对B有着偏向性.但是,当用户面临选择的是汽车C与汽车D的马力值分别为460、480时,用户可能并不会太偏向与汽车D,因为C的马力已经足够高可以满足用户的期望了.可以看出,同样相距20马力,260与280,460与480,对用户而言重要程度是不同的,此时线性函数不能刻画出这一现象.这是现象是边际效益递减现象,即用户的满意程度会随着商品单位属性值的增加而降低,通常可表示为凸函数.Falukner等人[57]将Nanongkai等人[26]提出的遗憾率最小化查询扩展到非线性效用空间.他们分析了更为一般的凸、凹与可置换性函数作为效用函数,并论述了这些函数可以更好地刻画边际效益递减,风险效益,可置换性偏好等现象.下面给出这些函数的定义.

凸函数(Convex) 函数f若满足对定义域中任意两点x1、x2与λ∈[0,1],都有f(λx1+(1-λ)x2)≤f(x1)+(1-λ)f(x2),则f为凸函数.

凹函数(Concave) 若-f是凸函数,则f是凹函数.

这些函数更好地刻画了普遍存在的效用函数,使得k-遗憾查询更有说服力.Falukner等人[57]对Cube算法进行改进,提出适用于非线性效用函数的MinWidth算法,并给出了这些函数下遗憾率的理论上界.

表2对非线性下的研究结果进行了总结,其中参数t=|(k-d+1)1/(d-1)|为算法过程中划分的桶数.

从表2可以看出,当前非线性效用函数下的算法MinWidth和MinVAR得到的结果集,其遗憾率界通常比线性效用函数下遗憾率界最优的算法Sphere要差,跟Cube算法的遗憾率界是一致的,其原因是这两个算法本质上就是Cube算法在非线性效用函数上的推广.从时间复杂性的角度,跟线性效用函数下的时间复杂度异曲同工,线性时间复杂度(MinWidth)或者O(nlogn)时间复杂度(MinVar).

表2 非线性算法理论结果Table 2 Results on non-linear regret queries

3.6 动态数据集下的遗憾查询

在一些现实生活场景中,数据集中数据并非是一成不变的:航班车次会随着时间而新增与截止,商品存在上架与下架等,而数据集也会随之变化.针对存在数据点插入或删除情况下的非静态数据集,简单地重复运行已有的静态算法以获得每一次的查询结果是一个十分耗时的过程,尤其是在数据点频繁变化的应用中,因此 Wang等人[49]提出了完全动态情况下的k-遗憾查询,他们将动态的k-遗憾查询问题转换为动态集合覆盖(dynamic set cover)问题,在此基础上设计了FD-RMS(Fully-Dynamic algorithm for Regret Minimization Sets)算法,并在数据动态变化下维护一个集合覆盖问题的稳定解,可以有效地给出某一状态下的结果集.

具体地,FD-RMS算法首先随机采样一系列效用函数并计算出它们各自的top-k数据点,类似于[36]中的方式构造出集合系统,进而利用贪婪算法求得集合覆盖问题的初始解.由于数据点的插入和删除引起效用函数top-k数据点的变化进一步引起集合系统的变化,算法引入结果集稳定性的概念,并在维护过程中保证结果集的稳定性,从而算法始终能得到一个最新的结果集.该算法可以保证同静态算法Cube一样的理论界,并且在线性时间内可完成一次查询.

算法小结 基于RDP框架的方法(RDP-Greedy,GreedyK)需要大量的线性规划计算,所需查询时间较长;基于几何性质的方法(Cube,Sphere),利用欧式距离近似替代效用信息,具有较快的运行速度,但对于较小的输出集,结果质量通常很差;转化为集合覆盖、命中集和核心集问题的方法(DMM,HittingSet,ε-kernel)具有理论保证,结果质量接近于最优解,运行效率介于RDP框架与几何方法之间;交互方法(UtilityApprox,UH-Simplex,Sorting-Simplex)由于可以不断和用户交互,可以控制遗憾率的界,并且当交互轮数达到一定程度,可以让用户的遗憾率为0;由于非线性效用函数有其函数自身的特性,目前仅有基于Cube算法的MinWidth与MinVar具有遗憾率理论上界;平均遗憾查询由于其超模性质,Greedy-Shrink得到的理论结果渐近最优;动态数据集查询下的算法FD-RMS具备快速响应查询的能力,但遗憾率上界仅与Cube一致,尚未达到静态查询下的目前的最佳结果.

4 展 望

目前,遗憾查询已逐渐发展成为多准则决策的重要支撑工具,以解决复杂的决策事务.小到生活中挑选商品,大到对选举者的确定,遗憾查询都体现着其作用.在现有研究成果的基础上,本文总结了遗憾查询的一些研究问题与发展趋势,认为未来遗憾查询可能会重点关注数据流、与机器学习结合、更一般的约束与利用次模函数方法等方向,并且遗憾查询作为多准则决策工具会运用到其它应用领域.

4.1 数据流下遗憾查询

数据流下的遗憾查询存在着很大的研究空间.已有的相关查询如top-k、skyline查询都有在数据流下的相关研究[59,60],尽管Wang等人[49]已经做出了数据集动态变化下的相关研究,然而目前方法得到的遗憾率效果仍与静态算法存在一些距离.此外,Wang等人[49]提出的FD-RMS算法的时间复杂度是线性的,当数据流的流速较快时,需要设计更低复杂度的高效算法以响应查询.因此进一步的研究工作可能会是提高数据流下的查询算法质量与效率.可行的研究思路是,从结果集维护而非重新运行静态算法的角度进行处理以快速返回最新的结果集,也就是说设计的新算法无须在每次数据变化时重新计算结果集,而利用第一次计算得到的结果集增量更新.而在结果集维护过程中可以集成滑动窗口及单调队列的技术:滑动窗口可以过滤久远的数据,而单调队列能将不可能被选入结果集的元组提前排除,从而避免了算法对过多无用数据的计算,以提升处理效率.就结果集质量而言,可以结合静态算法中遗憾率效果较好的算法,例如Sphere,将其动态化,保存之前结果集时的数据结构,并在数据流下动态维护这些数据结构,从而基于这些信息快速得到最新的结果集.另外,目前动态变化下的遗憾查询研究还比较单一,如效用空间局限于线性函数,非线性效用空间下的流式查询工作还存在空白,而上述解决思路亦可应用非线性效用函数下的算法(MinWidth,MinVar)进行处理.

4.2 结合机器学习

尽管目前最好的遗憾率查询算法(如Sphere)可以返回遗憾率较小的结果,但对某一具体用户而言,仍可能对返回结果感到不满意.因为遗憾查询针对的是同一效用空间下的用户群体,给整体做出的查询结果,因而每个用户获得的结果相同,且每次查询都是相同的返回内容.因此,针对特定用户的遗憾查询问题也是一个值得关注的研究方向.相关解决思路是:考虑结合机器学习中的主动学习(Active Learning)技术[61],将用户可能的喜好看作是假设集,根据假设集去设置一系列的问题以及相应的回答,通过交互的方式主动学习用户的偏好.每轮交互中,采用一定的策略选择问题来向用户进行提问,用户则根据自己的喜好做出相应的回复,以此来筛选假设集,缩小结果集的候选范围,从而逐步降低结果的遗憾率.其中,每一轮交互的结果都会影响着后续问题的选择,所以,为了使得用户能快速得到满意的结果(遗憾率小),选择问题的策略至关重要.

从另一个角度来看,之前的研究中,对特定用户降低遗憾的方式是借助交互机制.交互方法虽然在一定程度上解决了遗憾查询存在的问题,却需要用户花费时间与精力进行判断给出反馈,这无疑增加了用户负担、降低了体验效果.一个直觉上的想法是借助历史记录、缓存等手段,根据用户的点击与浏览信息,学习得到其效用函数信息,逐渐缩小特定用户的效用函数范围,在查询时有针对性的返回结果以供用户使用.Shetiya等人[56]引入数据挖掘中的算法解决遗憾率问题具有借鉴意义,而借助机器学习手段有效地降低用户遗憾是未来研究的一个方向.

4.3 二进制约束与公平性约束下的遗憾查询

二进制约束 用户查询时往往会对一些属性值的范围进行限制,如在购买电脑时限制价格在4000与7000元之间,内存要求至少为8G等.这类约束被称为二进制约束(binary constraint),即某商品在该属性上要么满足要么不满足,查询过程中要满足用户对这些属性的需求.遗憾查询需在满足二进制约束的前提下,尽可能地最小化遗憾率.一个二进制约束可用符号c表示,若点p满足该约束,则c(p)=1否则c(p)=0.对于一组二进制约束C={c1,c2,…,cr},点p满足的约束集为C(p)={ci∈C:ci(p)=1}.因此,二进制约束下的遗憾查询可定义如下:给定数据集D,与一组二进制约束集合C={c1,c2,..,cr},返回数量至多为k的子集S,使得满足的约束集∪p∈SC(p)数量尽可能多,且集合S的遗憾率rrD(S,F)尽可能小.Dong等人[62]定义了二进制约束的支配关系,缩减了初始候选集,降低计算量,并利用线性规划设计了贪婪算法.然而Dong等人[62]的研究技术还不成熟,所提算法没有理论保证,不能保证输出解的质量,极端情况下算法所得结果可能会任意差.二进制约束下的遗憾查询仍需要具有理论保证的算法填补空白.

公平性约束 另外一种约束是当下比较热门的话题:公平性(fairness)[63-67].公平性作为评估决策、算法是否合理的依据,在不同情景下有着迥异的定义方式,而最常见且适用于查询问题的是统计公平性[66,67].具体来说,数据集可根据一些属性值划分为不同的群体,统计公平性指,最终返回的结果集中含有各群体中数量应该与其所在群体数量成正比.公平性最直观的例子是挑选候选人,受到资源分配、政策等限制,从所有候选者中直接挑选出表现最优的一部分人是不够公平的.为达到公平性要求,应根据性别、民族、年龄等因素,将候选人划分到不同的群体,在各群体中按照所分配到名额进行择优选择.因此查询问题中的公平性约束可定义为对于不同群体Gi,限制选取数据点的数量ki.公平性约束下的遗憾查询问题具体形式为:给定划分为l个群体的数据集D(={G1,…,Gl}),及各群体的数量约束{k1,…,kl},目标是找到一个子集S,在满足分组约束的前提下(即|S∩Gi|=ki)使得遗憾率rrD(S,F)尽可能地小.这类公平性约束是划分拟阵(partition matroid)的特例,因此针对划分拟阵的研究成果同样可以适用于该类约束问题.根据文献[36]的思想,可以将遗憾查询问题建模为集合覆盖问题,而划分拟阵下的集合覆盖问题有一定的研究基础,基于此,可以设计出解决公平性约束下遗憾查询的方法.因此,遗憾查询结合公平性也是有前景且可行的一个研究内容.

4.4 引入次模函数

次模效应指的是边际增益递减的一种现象,而次模函数f满足对于定义域上的集合A与B都有f(A)+f(B)≥f(A∩B)+f(A∪B)[68].超模函数是与次模相逆的概念,若-f是次模函数,则f满足超模性.Zeighami等人[52]指出平均遗憾率函数是超模函数,借助超模函数性质可以保证输出解的理论质量.Zheng等人[69]指出最小开心函数不是次模函数,但单个效用函数f下的开心度函数是次模的,这表明最小开心度函数仍具有次模的一部分性质,通过次模率(submodularity ratio)的概念可以构建出次模与遗憾查询的桥梁.覆盖函数(coverage function)亦是次模函数,因此文献[36]提出的将查询转化为集合覆盖思想可以视为次模的特例化研究,进一步论证了次模理论用于遗憾查询的可行性.基于此,次模理论下的一些技术可以引入到遗憾查询中,如最优子集的选取[70],数据流下的研究[71,72],加速算法的策略[73,74]等.未来研究或可借助次模理论,对遗憾查询的变体研究提供理论保证(如数据流下查询,公平性约束下的研究等).

4.5 遗憾查询的应用

遗憾查询可以集成到数据库SQL查询子句中.在SELECT声明时可以集成可选的子句“REGRET-SET WITH …”,通过遗憾查询进一步筛选结果.如下所示:

SELECT … FROM … WHERE …

REGRET-SET

WITH [sizek| error]

其中sizek可由用户指定输出集大小,并在查询过程中最小化遗憾率;或由用户指定遗憾率上界,查询结果返回尽可能小的候选集使得遗憾率不超过.

遗憾查询也可以作为工具用到其它问题领域中.与遗憾查询联系较为紧密的是多目标优化问题.多目标优化问题在处理过程中需满足同时优化多个目标函数(准则),这与遗憾查询不谋而合:遗憾查询将各维属性值作为优化准则,且最大遗憾率函数要求最坏情况下的效用值尽可能地好.Soma等人[75]与Feng等人[76]把遗憾查询作为衡量求解多目标优化问题算法的评价指标,类似于近似率的概念,对所提出的近似算法优劣性进行判断.Soma等人[74]率先提出多目标优化问题可以借助遗憾的概念,用遗憾率衡量算法输出解的质量好坏,进而基于Cube算法的思想设计了多目标优化问题下的算法,用以解决一般的多目标优化问题,并从几何角度进阐述算法流程与意义.Feng等人[76]为解决多目标优化问题,也借助遗憾概念提出一种基于采样的遗憾率最小化算法RRMS(Regret Ratio Minimization by Sampling),并对算法输出解的最大遗憾率进行了理论保证.此外,计算机视觉领域的视频概要(Video summarization)[77]问题是从大量帧中提取代表的若干幅图片代表整个视频,当一副图片可以从多个角度(重要性、故事性)等描述时,视频概要问题就是一个多准则决策问题.因此,可以将遗憾查询技术引入到视频概要中.另外,随着研究的不断深入,遗憾查询将为其它领域的多准则决策、多目标优化问题提供借鉴.

5 总 结

本文首先对top-k和skyline查询以及代表点查询技术做了简单介绍,然后重点介绍了遗憾最小化查询目前的研究进展情况.从遗憾查询基本的概念出发,介绍该领域的各种典型算法,并展开介绍其变种处理技术.在最后部分,对遗憾查询领域未来可能的研究点进行了展望.通过对遗憾查询较为全面的介绍和总结,为相关研究人员能够快速进入该领域展开研究提供帮助.