鄭吉平,馬 源,馬 煒,郝志揚,王美靜

1(南京航空航天大學 計算機科學與技術(shù)學院,南京 211106) 2(軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心,南京 210093)

1 引 言

隨著信息技術(shù)的發(fā)展,當下每天都在產(chǎn)生海量的數(shù)據(jù),而如何從這些數(shù)據(jù)中提取簡潔的、關(guān)鍵性的信息,用來支持用戶多目標決策是數(shù)據(jù)庫系統(tǒng)的一項重要任務(wù).顯然,對于大量的信息,用戶很難從中直接找出感興趣的內(nèi)容.目前,研究人員提出了一些技術(shù)與工具來解決這個問題.其中,skyline查詢top-k查詢是兩種最常用的技術(shù)手段[1-22].Skyline查詢根據(jù)“支配”的概念,剔除掉部分被其它數(shù)據(jù)支配的點,從而返回數(shù)據(jù)集中不被任何點支配的信息.Top-k查詢則借助用戶指定的效用函數(shù)f,給數(shù)據(jù)集中的點進行打分,得出關(guān)于f評分最高的k條數(shù)據(jù)給用戶,以達到縮減查詢結(jié)果的目的.然而這兩種方式都存在自身固有的缺陷,skyline查詢不能控制查詢結(jié)果的大小,當數(shù)據(jù)點的維度d增長,skyline集合的大小急劇增加,很難達到縮減數(shù)據(jù)集的要求;而top-k查詢需要用戶給出效用函數(shù),多數(shù)情況下用戶只能模糊的給出自己的偏好,難以提供較為精確的效用函數(shù),且這樣也給用戶帶來了額外負擔.因這些缺陷的存在,k代表點查詢(k-representative queries)被廣泛研究[23-27].特別的,對于k代表點查詢,在不借助用戶提供效用函數(shù)的前提下就能得到k個代表點,使得大部分用戶滿意;其兼顧了top-k與skyline查詢的優(yōu)點.典型的k代表點查詢有最大支配數(shù)skyline查詢、基于距離的代表skyline查詢、k-遺憾(k-regret)查詢與k-覆蓋(k-coverage)查詢.其中,由Nanongkai等人[26]提出的基于遺憾的k代表點查詢,即k-遺憾查詢,在過去十余年被廣泛研究.其利用“遺憾”(regret)作為衡量指標,得到遺憾最小的結(jié)果集近似地代表整個數(shù)據(jù)集合.隨后,一些相關(guān)的研究與解決方案相繼涌出.本文對遺憾查詢相關(guān)研究進行了概述,并對未來的一些可能研究方向進行了展望.

本文安排如下:第2節(jié)簡要地介紹top-k查詢、skyline查詢及除了遺憾查詢之外的k代表點查詢;第3節(jié)詳細地介紹了遺憾查詢的概念與一些拓展研究;第4節(jié)對未來的相關(guān)研究與應(yīng)用做出了展望;第5節(jié)總結(jié)了本文.

2 代表性查詢

在過去二十多年里,top-k查詢與skyline查詢在多準則決策過程中起著重要的作用.

2.1 Top-k查詢與skyline查詢

Top-k查詢作為較早提出的處理多準則問題的策略,具有廣泛的應(yīng)用領(lǐng)域[28，29].許多搜索引擎根據(jù)一些判斷機制,展示給用戶比較感興趣的k個查詢結(jié)果.而得到這樣的k個查詢結(jié)果的常用方法是對每條數(shù)據(jù)進行打分,從而獲得評分最好的k條數(shù)據(jù).因此,top-k查詢的關(guān)鍵點在這類打分函數(shù)(即效用函數(shù),utility function,亦稱評分函數(shù),score function,或偏好函數(shù),preference function)的確定;根據(jù)效用函數(shù),搜索引擎可以很容易反饋最佳的答案給用戶.Top-k查詢在之前受到了廣泛的關(guān)注[11-22],針對不同場景下有不少的經(jīng)典查詢算法.Fagin[18]提出算法FA算法(Fagin Algorithm,FA)解決確定數(shù)據(jù)集上的top-k查詢;Lian等人[19]提出概率top-k支配(Probabilistic Top-kDominating,PTD)查詢響應(yīng)概率數(shù)據(jù)集情景下的查詢;Papadopoulos等人[20]提出了基于支配分析的查詢算法等.然而,top-k查詢的前提是用戶必須給定效用函數(shù),而很多情形用戶無法提供效用函數(shù)或無法準確給出,因此限制了top-k的應(yīng)用場景.

B?rzs?nyi等人[1]首次將運籌學領(lǐng)域中的帕累托(Pareto)概念[20]引入到數(shù)據(jù)庫領(lǐng)域中,可以避免top-k查詢需要用戶提供效用函數(shù)的缺陷,提出skyline查詢的概念.Skyline查詢根據(jù)“支配”的概念對數(shù)據(jù)進行查詢.對于一個具有d維屬性的數(shù)據(jù)集D,其中的數(shù)據(jù)點p=(p[1],p[2],…,p[d])支配另外一點q=(q[1],q[2],…,q[d])需要滿足在任一維度i的屬性值上有p[i]不劣于q[i],且至少存在一個屬性值p[j]優(yōu)于q[j].對于skyline查詢,不會被任何點支配的數(shù)據(jù)點構(gòu)成了整個skyline集合,即skyline查詢的結(jié)果.隨后,高效的skyline求解算法被提出,如BNL(Block-Nested-Loops)算法[1]、BBS(Branch-and-Bound Skyline)算法[2]、D&C算法(Divide and Conquer)[1]等.其中,BBS是目前I/O最優(yōu)的方法.另外一些研究則是skyline的一些變體,可大致分為兩類:一類是為解決skyline返回集大小不可控的研究如約束的skyline(constrained skyline)[3]、子空間skyline(subspace skyline)[4，5]、k-skyband[6]、-skyline[7]及下節(jié)介紹的k代表點研究;另一類則是不同情景下的查詢,如連續(xù)skyline查詢(continuous skyline queries)[8]、概率skyline查詢(probabilistic skyline queries)[4]等(詳情可參考文獻[9,10]).Skyline查詢雖然不需要效用函數(shù)的指定,但存在輸出集大小不可控制的問題,通常隨維度的增加呈指數(shù)增長[9].下面通過多準則決策的一個具體實例介紹top-k與skyline查詢結(jié)果集.

例:如何選購汽車是一個典型的多準則決策例子.這里考慮每輛汽車具有兩維屬性:馬力(Horse Power,HP)與每加侖汽油可行駛英里數(shù)(Miles Per Gallon,MPG).任何一個購買者都希望自己選中的汽車動力強勁(馬力大)、且耗油量小(每加侖汽油行駛里程數(shù)最大).然而,這兩種屬性一定程度上相互掣肘,往往不存在馬力最大,而耗油量最小這樣的汽車.因此,從數(shù)據(jù)庫中挑選出具有代表性的汽車展示給用戶,是一個值得考慮的問題.

如圖1所示,假設(shè)有5輛汽車{p1,p2,p3,p4,p5}該例中的skyline集為{p1,p3,p4},而p2被p1、p3支配,p5被p3、p4支配,用戶不會選擇馬力小則耗油量大的p3與p5.因此,skyline查詢將{p1,p3,p4}作為結(jié)果集反饋給用戶,以供用戶更好地選擇.而如果用戶可以精確的給出了自己對這兩個屬性的偏好值,如對HP有著70%的傾向,其余30%的權(quán)重給予MPG屬性上,則p1～p5的得分為{109.1,89,146,149.1,107},若k=2,則應(yīng)該返回汽車{p4,p3}給用戶.然而正如前面所提到,skyline查詢結(jié)果不可控制、top-k查詢需要用戶精確的提供效用函數(shù),研究者更多地關(guān)注k代表點查詢.

圖1 汽車數(shù)據(jù)集例子Fig.1 Example of car database

2.2 k代表點查詢

提出k代表點查詢的目的是避免skyline與top-k查詢輸出結(jié)果集的數(shù)量不可控或需要提供效用函數(shù)的缺陷,用一個可控制數(shù)量(k個)的子集呈現(xiàn)給用戶.典型的k代表點查詢有k-遺憾查詢,top-k個skyline代表點查詢,基于距離的k個skyline代表點查詢以及k-覆蓋查詢等.

1)Top-k個skyline代表點查詢.Lin等人[23]將數(shù)據(jù)點p的支配數(shù)量|Dom(p)|作為重要性程度,選取一個大小為k且具有最大支配數(shù)量的子集S,即最大化其支配的非skyline數(shù)據(jù)點的數(shù)目,即:|Dom(S)|(=|∪q∈SDom(q)|).Lin等人[23]將該問題等價為最大集合覆蓋問題(Maximum Set Cover problem),證明了該問題是NP-難的,并設(shè)計了具有1-1/e近似率保證的貪婪算法.

2)基于距離的k個skyline代表點查詢.Tao等人[24]提出用歐式距離作為評估的指標,返回k個中心點集合S代表skyline集合,使得被支配點到離它最近的中心點距離最小,即最小化maxq∈D〗S{minp∈S‖q,p‖}.文獻[24]在2維情況下設(shè)計了精確算法,并證明了高維情況下是NP困難的(NP-hard),提出了具有1/2近似率的貪婪算法.

3)k-覆蓋查詢.Soholm等人[25]提出了k-覆蓋(k-coverage)查詢問題,通過支配區(qū)域的概念定義點的覆蓋范圍.通過選擇具有最大覆蓋范圍的k個點集合,近似地替代整個skyline空間.由于k-覆蓋問題是個NP-難問題,因此該查詢也是NP困難的.此外,Bai等人[30]考慮的在數(shù)據(jù)流上的k支配問題與k-覆蓋問題類似;Zheng等人[31]將靜態(tài)數(shù)據(jù)下的k-覆蓋查詢擴展到數(shù)據(jù)流與數(shù)據(jù)動態(tài)變化情況.

3 k-遺憾查詢

尺度不變性(Scale invariance)[26]指的是當數(shù)據(jù)集中點的屬性值按比例縮放后,對查詢結(jié)果不造成影響;而穩(wěn)定性(Stability)指在數(shù)據(jù)集中加入或刪除非skyline點不改變查詢結(jié)果.上述k代表點查詢中,基于距離的代表skyline查詢隨著屬性值的擴展,距離屬性受到影響,不具備尺度不變性;top-k代表skyline查詢因與支配點數(shù)量有關(guān),加入非skyline點導致支配關(guān)系的變化,因此不具有穩(wěn)定性.k-遺憾查詢因其自身具備尺度不變性與穩(wěn)定性成為近來備受關(guān)注的k代表點查詢研究.

3.1 k-遺憾查詢相關(guān)概念

首先介紹遺憾與遺憾率的概念.

遺憾與遺憾率[26]對于某一效用函數(shù)f,遺憾(regret)為數(shù)據(jù)集D與用戶選取的代表性子集S的效用值之差,即rD(S,f)=f(D)-f(S),而遺憾率(regret ratio)定義為遺憾與D的效用值的比值形式,即rrD(S,f)=rD(S,f)/f(D).根據(jù)定義可知,遺憾率的取值范圍是[0,1]:當遺憾率越接近0,表明用戶見到該結(jié)果會越高興;而遺憾率越接近1,則表明選中的集合不符合用戶的興趣,用戶越不高興.

由于用戶的效用函數(shù)未知,用符號F表示所有可能的效用函數(shù)集合,則最大遺憾率(maximum regret ratio)定義為:

其表示在效用空間F下,選中集合S后的遺憾率最大值.因此,遺憾查詢的目標是找一個滿足條件的集合S最小化遺憾率rrD(S,F).下面給出正式的遺憾查詢定義:

k-遺憾查詢[26]給定由n個d維數(shù)據(jù)點構(gòu)成的數(shù)據(jù)集D,效用函數(shù)空間F,與正整數(shù)k,尋找一個大小為k的子集S?D,使得rrD(S,F)盡可能地小.

目前大多數(shù)研究將效用函數(shù)限制在線性效用函數(shù)空間L下,即用線性效用函數(shù)刻畫用戶的偏好情況.

為解決k-遺憾最小化查詢問題,Nanongkai等人[26]提出了簡單有效的立方體算法(Cube).算法將數(shù)據(jù)空間劃分為若干個超立方體,然后分別從各超立方體中選取一個數(shù)據(jù)點加入結(jié)果集中.Cube算法可以保證在最壞情況下,最大遺憾率不會超過:

Cube算法首先在1～d-1維屬性上選擇值最大的點到結(jié)果集中,然后根據(jù)第d維的屬性值將數(shù)據(jù)點均勻地劃分在(k-d+1)個桶(bucket)中.因同一桶中的數(shù)據(jù)點在1～d-1維上的屬性值十分相近,而選取最好點的直觀做法就是選取桶中d維屬性最大的點.這樣就可以近似地選取每個桶中效用值最大的點.而算法開始時在1～d-1維上選取屬性值最大的點保證了解集在任意效用函數(shù)上的效用都足夠大.此外,Nanongkai等人[26]證明Cube算法的最大遺憾率存在一個下界:對于任一正整數(shù)k,有rrD(S,F)= Ω(1/k2),即Cube算法輸出的結(jié)果集始終存在不小于復雜度為1/k2的遺憾率.

圖2 Cube算法計算示例Fig.2 Example of cube

然而,Cube算法分配桶時根據(jù)空間距離進行劃分,一些桶中會出現(xiàn)不含有點的現(xiàn)象,導致算法最終并不能返回k個點(少于k)作為結(jié)果集;且盡管Cube對最大遺憾率有一個理論上界保證,但其實際運行效果遺憾率較大,因此Cube算法并不能滿足用戶對于結(jié)果集的質(zhì)量需求.

為解決上述問題,Nanongkai等人[26]提出了基于Ramer-Douglas-Peucker(RDP)算法框架的貪婪算法RDP-Greedy.RDP算法最初用于近似曲線與多邊形,隨后被借鑒于其它領(lǐng)域并取得了良好的效果.RDP算法的主要思想是逐步優(yōu)化最差的部分.基于此思想,針對遺憾查詢的算法RDP-Greedy首先選取每一維屬性值最大的點;緊接著迭代選取當前狀態(tài)下“最壞”點,即對導致產(chǎn)生當前最大遺憾率的點,加入該點可以降低最大遺憾率的值.更準確的說,每輪加入的點是使得rrD(S,F)=rrS∪p(S,F)成立的p點.而確定這樣的點,需要根據(jù)下面的線性規(guī)劃(Linear Programming)計算得到:

maxx

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

p·v=1

v[j]≥0 ?j≤d

x≥0

上式使得線性規(guī)劃目標值x取得最大的點q即為當前輪所求點,通過確定這樣的“最壞”點不斷地降低遺憾率,直至選滿k個點.

基于遺憾的k代表點查詢,可以應(yīng)用于許多領(lǐng)域,如推薦系統(tǒng)、信息推薦、搜索引擎等.但由于一些情景下無法直接應(yīng)用k-遺憾查詢,因此從不同角度出發(fā)的k-遺憾查詢相關(guān)研究被陸續(xù)提出.

3.2 更高效的算法

研究者為進一步提高查詢質(zhì)量與效率,從各方面出發(fā)做了不同嘗試.Peng等人[32]、Agarwal等人[33]、Cao等人[34]與Xie等人[35]從幾何性質(zhì)出發(fā)設(shè)計了高效算法;Agarwal等人[33]與Ausdeh等人[36]分別將查詢規(guī)約到命中集與集合覆蓋問題;Nanongkai等人[37]、Xie等人[38]與Zheng等人[39,40]利用交互手段提高解集質(zhì)量.此外,Dong等人[41]與Zheng等人[42]分別基于遺憾率函數(shù)的單調(diào)性特征與次模性質(zhì)加快查詢速度.

3.2.1 從幾何性質(zhì)出發(fā)

Peng等人[32]在skyline集上進一步提取出更小的候選集開心點(happy points),在此上進行k-遺憾查詢可以提高查詢效率.Peng等人[32]從數(shù)據(jù)點的幾何性質(zhì)出發(fā),提出了效率更高的GeoGreedy算法,且具有與RDP-Greedy具有一樣的質(zhì)量保證.

基于上述臨界比,GeoGreedy首先選取每一維上屬性值最大的點加入到S,然后不斷選擇與當前解集臨界比最小的p點加入到S.當最小臨界值為1或選足k個點時,算法返回解集S.

圖3 臨界比示例Fig.3 Critical ratio

Peng等人[32]根據(jù)效用空間為線性的前提,對候選集進行預處理,處理后的數(shù)據(jù)集是比skyline更小的子集,但可以獲得相同的結(jié)果集.Peng等人[32]將這種處理后的數(shù)據(jù)集稱為開心點集合,下面給出開心點的定義.

開心點[32]給定n個d維數(shù)據(jù)點組成的數(shù)據(jù)集D與點p、q∈D,在每一維坐標軸上增加一個虛擬點vpi=(0,…,1,…,0)(只在第i個分量為1,其余都為0).這些虛擬點的集合記為VP,VP∪{q}的凸包構(gòu)成的超平面記為H(q),若點p在H(q)的所有超平面內(nèi)或下方,并且至少在一個超平面的下方,則p被q“支配”.這里利用線性空間的特性,對skyline中支配的定義進行了放松,減小了處理后集合的規(guī)模.如圖4所示,在2維坐標軸上增加了兩個虛擬點(0,1)、(1,0),2維空間下的超平面對應(yīng)的是直線,因此H(p3)中含有直線p3-vp1與直線vp2-p3.從圖中可以看到,p2在p3的超平面下方,因此p2被p3“支配”,將p2從候選集中刪除.該例中如p1、p4這樣不被其它點支配的,會保留下來,構(gòu)成數(shù)據(jù)集的開心點集合.開心點少于skyline集合,但保留了在線性空間下不被支配的點,降低了查詢算法的計算量.

圖4 開心點示例Fig.4 Happy point

Agarwal等人[33]與Cao等人[34]幾乎同時提出借助-kernel(-核)的概念來解決遺憾查詢問題,且可以得到優(yōu)于Cube算法的理論上界.

圖5 -kernel示例Fig.5 -kernel

Agarwal等人[33]與Cao等人[34]證明,若集合S是數(shù)據(jù)集D的-kernel,則S在D上的遺憾率不超過.因此遺憾查詢就可轉(zhuǎn)化為求解-kernel問題,根據(jù)文獻[43]中的算法可以求解出數(shù)據(jù)集的-kernel,大小為可以通過二分搜索(binary search)的方式,變化的數(shù)值得到大小為k的結(jié)果集,此時根據(jù)-kernel與k的關(guān)系,可以推出結(jié)果集遺憾率上界為

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

Xie等人[35]借助Basis集合的定義提出了Sphere算法.該算法首先與Cube做法類似,將每個屬性上值最大的d個點加入到S;隨后計算出可以代表整個線性效用空間的子集L;根據(jù)L中的效用函數(shù),計算出D關(guān)于L中每個效用函數(shù)的Basis集合,不斷的將Basis集合中的點加入到S;若做完上步后|S|仍小于k則繼續(xù)通過Nanongkai等人[26]提出的RDP-Greedy算法繼續(xù)計算剩下要加入的點直至遺憾率為0或|S|=k,返回結(jié)果集S.同時,Xie等人[35]給出了與Agarwal等人[33]和Cao等人[34]借助-kernel一樣的遺憾率上界.

3.2.2 規(guī)約到經(jīng)典問題

Agarwal等人[33]將遺憾查詢轉(zhuǎn)化為命中集(hitting set)問題.

命中集問題[44]給定集合系統(tǒng)Σ = (D,R),R為D中子集的集合,若存在子集S?D,對于任意集合元素R∈R,都有S∩R不為空集,那么S就為該集合系統(tǒng)的一個命中集.

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

Ausdeh等人[36]將最大遺憾率最小化問題轉(zhuǎn)化為矩陣的最小-最大問題,提出了DMM算法.轉(zhuǎn)化思想如下:首先對連續(xù)效用空間進行離散化處理,利用采樣的方式近似代替原連續(xù)的效用空間,采樣的效用函數(shù)集合記為U.通過給定的數(shù)據(jù)集D與效用函數(shù)集合U,計算出每一點關(guān)于U中效用函數(shù)的遺憾率,構(gòu)建一個|D|×|U|的矩陣M(如圖8所示),矩陣中的元素Mi,j對應(yīng)著點pi在效用函數(shù)uj∈U上的遺憾率,因此求k個點的最大遺憾率最小值等價于在矩陣中找k行使得每一列的最小值最大者盡可能小.進一步地,矩陣最大最小問題通過設(shè)置閾值將問題進一步轉(zhuǎn)化為集合覆蓋問題(矩陣中元素大于則置0表示效用函數(shù)uj不在pi點對應(yīng)的集合中;否則置1,可視作uj在pi對應(yīng)集合中),滿足集合覆蓋的對應(yīng)行可保證最大遺憾率不超過.因此遺憾查詢問題就轉(zhuǎn)化為集合覆蓋問題的求解.與上述命中集類似,可通過二分搜索確定最佳的,并返回對應(yīng)的解集.由上可以看出,HittingSet和DMM具有相似性,其本質(zhì)原因是因為命中集問題(Hitting Set)和集合覆蓋問題(Set Cover)互為對偶問題.

圖8 矩陣最小最大問題示例Fig.8 Min-Max matrix problem

除此之外,Xie等人[47]設(shè)計的開心度算法,也可看作是從幾何角度構(gòu)建的集合覆蓋系統(tǒng),并通過貪婪算法[48]進行求解;Wang等人[49]將動態(tài)數(shù)據(jù)集下的遺憾查詢問題建模成動態(tài)集合覆蓋問題.由此可見,通過問題的轉(zhuǎn)化求解遺憾查詢是較為常見、有效的做法.

3.2.3 利用交互信息

Nanongkai等人[37]首次提出引入交互機制獲取用戶較為滿意的點集.在不借助交互手段的遺憾查詢中,往往很難通過只返回k個點的集合就可達到較小的遺憾率.而借助交互方式,可以有效地提高返回集的質(zhì)量.Xie等人[38]等人提出了UtilityApprox算法每輪向用戶展示s個數(shù)據(jù)點,讓用戶從中選取最感興趣的點,從中逐漸獲取用戶的偏好信息.直到輸出k個點可以使得最大遺憾率不大于時,停止交互.算法保證當遺憾率上界為時,需要進行O(sdlogs(d/))輪交互.

與Nanongkai等人[37]提出的算法相比,UH-Simplex算法可以保證用戶確定最滿意的點,需要較少的輪數(shù).然而UH-Simplex仍需數(shù)十輪交互才能達到遺憾率為0的結(jié)果,Zheng等人[39]提出交互過程中讓用戶給每輪展示的點進行排序,利用排序得到更多的信息,減小交互輪數(shù).

3.3 擴展到k-RMS

遺憾查詢的一個不足之處在于評判用戶滿意的標準太過嚴格,即每次對用戶的“最好”選擇具有唯一性(最大遺憾率最小的).但實際上,用戶的體驗會不斷變化.考慮一個旅館住宿的問題,用戶可能想嘗試新的旅館,而對推薦的“最好”旅館因去過反而感到不滿意.為解決這一問題,評價用戶滿意的標準就要更加靈活以適應(yīng)用戶不同需求.Chester等人[50]基于此提出了kRMS(k-Regret Minimizing Set)問題.kRMS查詢對遺憾查詢的概念進行了擴展,這里的用戶遺憾率指的是選中點集中最佳的點與整個數(shù)據(jù)集中第k優(yōu)的點的差距.本文用kmax(S,f)表示效用函數(shù)f下集合S中第k優(yōu)的效用值,則kRMS查詢下的遺憾率krr(S,f)定義為:

則在整個效用函數(shù)空間F下的最大遺憾率為:

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

下面給出kRMS查詢的定義.

kRMS查詢[50]給定數(shù)據(jù)集D,效用函數(shù)空間F,正整數(shù)k,與輸出集大小r,kRMS查詢的目標是找到一個集合S?D(|S|=r)使得mkrr(S,F)最小化.

特別的,當k=1時1RMS問題等同于Nanongkai等人[36]定義的最大遺憾率問題.Chester等人[50]證明了1RMS問題可規(guī)約到著名的集合覆蓋決定性(set cover decision)問題[51],由于集合覆蓋問題是NP困難的,被規(guī)約的1RMS問題也是NP困難的.進一步,他們證明了高維的kRMS問題也是NP困難的.Chester等人[50]針對2維情況,設(shè)計了一個精確算法;在高維數(shù)據(jù)查詢的情景下,沿用了Nanongkai等人[26]的算法思想,基于隨機分割與線性規(guī)劃提出了適用于kRMS的Greedy算法.Agarwal等人[33]與Cao等人[34]利用-核心集(kernel),從幾何性質(zhì)出發(fā)設(shè)計算法應(yīng)答kRMS查詢.

表1 遺憾查詢主流算法對比Table 1 Comparison among the mainstream algorithms

上述是對主要的遺憾查詢核心算法的總結(jié);除此之外,還有3個主要遺憾查詢的主要變種在該領(lǐng)域中也備受重視,分別為:平均遺憾率查詢、非線形效用函數(shù)下的遺憾查詢和動態(tài)數(shù)據(jù)集下的遺憾查詢.

3.4 平均遺憾率查詢

一般而言,查詢結(jié)果對于較多用戶來說都是很滿意的,只有極少數(shù)的用戶偏好過于極端,而為照顧這些極少數(shù)用戶,最大遺憾率查詢犧牲了絕大多數(shù)人的利益(這些用戶的遺憾率可以更小).Nanongkai等人[26]提出的遺憾查詢會導致只關(guān)注著最不開心的用戶,而忽視了其他用戶的體驗.Zeighami等人[52]指出在一些情景下,最大遺憾率不能很好地衡量用戶滿意程度,并提出了一種考慮用戶效用函數(shù)概率分布的遺憾查詢,即平均遺憾率查詢(average regret queries)的概念.

平均遺憾率 給定數(shù)據(jù)集D,效用函數(shù)F服從概率分布η,集合S?D的平均遺憾率定義為:

Zeighami等人[52]指出平均遺憾率函數(shù)是超模函數(shù)(supermodular function),利用超模函數(shù)特性與劣汰的思想,設(shè)計出Greedy-shrink算法.Greedy-shrink算法置初始解S為整個數(shù)據(jù)集D,每次從數(shù)據(jù)集S中去掉影響遺憾率最小的點q,即q=argminp∈Sarr(Sp),直至|S|=k時返回S.

Qiu等人[54]將問題轉(zhuǎn)化為等價的開心度(1-arr的形式)最大化問題,證明了開心度函數(shù)滿足次模(submodularity)性質(zhì),據(jù)此設(shè)計出加速算法,提高了求解效率.Zeighami等人[55]在2019年又提出了剪枝與減小候選集的策略加速平均開心度的計算過程.此外,Shetiya等人[56]引入數(shù)據(jù)挖掘領(lǐng)域的聚類方法設(shè)計了k-MEDOID算法,基于此提出了一個統(tǒng)一框架,通過該框架可分別響應(yīng)最大遺憾率查詢與平均遺憾率查詢.

3.5 非線性效用函數(shù)下的遺憾查詢

之前提到Nanongkai等人[26]對用戶效用函數(shù)做了線性假設(shè),然而線性效用函數(shù)有時卻不能準確地刻畫出用戶的偏好.在挑選汽車時,若用戶想購買具有較大馬力的汽車,面對馬力分別為260與280馬力的汽車A汽車B,由于汽車B具有更大的馬力,因此用戶會對B有著偏向性.但是,當用戶面臨選擇的是汽車C與汽車D的馬力值分別為460、480時,用戶可能并不會太偏向與汽車D,因為C的馬力已經(jīng)足夠高可以滿足用戶的期望了.可以看出,同樣相距20馬力,260與280,460與480,對用戶而言重要程度是不同的,此時線性函數(shù)不能刻畫出這一現(xiàn)象.這是現(xiàn)象是邊際效益遞減現(xiàn)象,即用戶的滿意程度會隨著商品單位屬性值的增加而降低,通?？杀硎緸橥购瘮?shù).Falukner等人[57]將Nanongkai等人[26]提出的遺憾率最小化查詢擴展到非線性效用空間.他們分析了更為一般的凸、凹與可置換性函數(shù)作為效用函數(shù),并論述了這些函數(shù)可以更好地刻畫邊際效益遞減,風險效益,可置換性偏好等現(xiàn)象.下面給出這些函數(shù)的定義.

凸函數(shù)(Convex) 函數(shù)f若滿足對定義域中任意兩點x1、x2與λ∈[0,1],都有f(λx1+(1-λ)x2)≤f(x1)+(1-λ)f(x2),則f為凸函數(shù).

凹函數(shù)(Concave) 若-f是凸函數(shù),則f是凹函數(shù).

這些函數(shù)更好地刻畫了普遍存在的效用函數(shù),使得k-遺憾查詢更有說服力.Falukner等人[57]對Cube算法進行改進,提出適用于非線性效用函數(shù)的MinWidth算法,并給出了這些函數(shù)下遺憾率的理論上界.

表2對非線性下的研究結(jié)果進行了總結(jié),其中參數(shù)t=|(k-d+1)1/(d-1)|為算法過程中劃分的桶數(shù).

從表2可以看出,當前非線性效用函數(shù)下的算法MinWidth和MinVAR得到的結(jié)果集,其遺憾率界通常比線性效用函數(shù)下遺憾率界最優(yōu)的算法Sphere要差,跟Cube算法的遺憾率界是一致的,其原因是這兩個算法本質(zhì)上就是Cube算法在非線性效用函數(shù)上的推廣.從時間復雜性的角度,跟線性效用函數(shù)下的時間復雜度異曲同工,線性時間復雜度(MinWidth)或者O(nlogn)時間復雜度(MinVar).

表2 非線性算法理論結(jié)果Table 2 Results on non-linear regret queries

3.6 動態(tài)數(shù)據(jù)集下的遺憾查詢

在一些現(xiàn)實生活場景中,數(shù)據(jù)集中數(shù)據(jù)并非是一成不變的:航班車次會隨著時間而新增與截止,商品存在上架與下架等,而數(shù)據(jù)集也會隨之變化.針對存在數(shù)據(jù)點插入或刪除情況下的非靜態(tài)數(shù)據(jù)集,簡單地重復運行已有的靜態(tài)算法以獲得每一次的查詢結(jié)果是一個十分耗時的過程,尤其是在數(shù)據(jù)點頻繁變化的應(yīng)用中,因此 Wang等人[49]提出了完全動態(tài)情況下的k-遺憾查詢,他們將動態(tài)的k-遺憾查詢問題轉(zhuǎn)換為動態(tài)集合覆蓋(dynamic set cover)問題,在此基礎(chǔ)上設(shè)計了FD-RMS(Fully-Dynamic algorithm for Regret Minimization Sets)算法,并在數(shù)據(jù)動態(tài)變化下維護一個集合覆蓋問題的穩(wěn)定解,可以有效地給出某一狀態(tài)下的結(jié)果集.

具體地,FD-RMS算法首先隨機采樣一系列效用函數(shù)并計算出它們各自的top-k數(shù)據(jù)點,類似于[36]中的方式構(gòu)造出集合系統(tǒng),進而利用貪婪算法求得集合覆蓋問題的初始解.由于數(shù)據(jù)點的插入和刪除引起效用函數(shù)top-k數(shù)據(jù)點的變化進一步引起集合系統(tǒng)的變化,算法引入結(jié)果集穩(wěn)定性的概念,并在維護過程中保證結(jié)果集的穩(wěn)定性,從而算法始終能得到一個最新的結(jié)果集.該算法可以保證同靜態(tài)算法Cube一樣的理論界,并且在線性時間內(nèi)可完成一次查詢.

算法小結(jié) 基于RDP框架的方法(RDP-Greedy,GreedyK)需要大量的線性規(guī)劃計算,所需查詢時間較長;基于幾何性質(zhì)的方法(Cube,Sphere),利用歐式距離近似替代效用信息,具有較快的運行速度,但對于較小的輸出集,結(jié)果質(zhì)量通常很差;轉(zhuǎn)化為集合覆蓋、命中集和核心集問題的方法(DMM,HittingSet,ε-kernel)具有理論保證,結(jié)果質(zhì)量接近于最優(yōu)解,運行效率介于RDP框架與幾何方法之間;交互方法(UtilityApprox,UH-Simplex,Sorting-Simplex)由于可以不斷和用戶交互,可以控制遺憾率的界,并且當交互輪數(shù)達到一定程度,可以讓用戶的遺憾率為0;由于非線性效用函數(shù)有其函數(shù)自身的特性,目前僅有基于Cube算法的MinWidth與MinVar具有遺憾率理論上界;平均遺憾查詢由于其超模性質(zhì),Greedy-Shrink得到的理論結(jié)果漸近最優(yōu);動態(tài)數(shù)據(jù)集查詢下的算法FD-RMS具備快速響應(yīng)查詢的能力,但遺憾率上界僅與Cube一致,尚未達到靜態(tài)查詢下的目前的最佳結(jié)果.

4 展 望

目前,遺憾查詢已逐漸發(fā)展成為多準則決策的重要支撐工具,以解決復雜的決策事務(wù).小到生活中挑選商品,大到對選舉者的確定,遺憾查詢都體現(xiàn)著其作用.在現(xiàn)有研究成果的基礎(chǔ)上,本文總結(jié)了遺憾查詢的一些研究問題與發(fā)展趨勢,認為未來遺憾查詢可能會重點關(guān)注數(shù)據(jù)流、與機器學習結(jié)合、更一般的約束與利用次模函數(shù)方法等方向,并且遺憾查詢作為多準則決策工具會運用到其它應(yīng)用領(lǐng)域.

4.1 數(shù)據(jù)流下遺憾查詢

數(shù)據(jù)流下的遺憾查詢存在著很大的研究空間.已有的相關(guān)查詢?nèi)鐃op-k、skyline查詢都有在數(shù)據(jù)流下的相關(guān)研究[59,60],盡管Wang等人[49]已經(jīng)做出了數(shù)據(jù)集動態(tài)變化下的相關(guān)研究,然而目前方法得到的遺憾率效果仍與靜態(tài)算法存在一些距離.此外,Wang等人[49]提出的FD-RMS算法的時間復雜度是線性的,當數(shù)據(jù)流的流速較快時,需要設(shè)計更低復雜度的高效算法以響應(yīng)查詢.因此進一步的研究工作可能會是提高數(shù)據(jù)流下的查詢算法質(zhì)量與效率.可行的研究思路是,從結(jié)果集維護而非重新運行靜態(tài)算法的角度進行處理以快速返回最新的結(jié)果集,也就是說設(shè)計的新算法無須在每次數(shù)據(jù)變化時重新計算結(jié)果集,而利用第一次計算得到的結(jié)果集增量更新.而在結(jié)果集維護過程中可以集成滑動窗口及單調(diào)隊列的技術(shù):滑動窗口可以過濾久遠的數(shù)據(jù),而單調(diào)隊列能將不可能被選入結(jié)果集的元組提前排除,從而避免了算法對過多無用數(shù)據(jù)的計算,以提升處理效率.就結(jié)果集質(zhì)量而言,可以結(jié)合靜態(tài)算法中遺憾率效果較好的算法,例如Sphere,將其動態(tài)化,保存之前結(jié)果集時的數(shù)據(jù)結(jié)構(gòu),并在數(shù)據(jù)流下動態(tài)維護這些數(shù)據(jù)結(jié)構(gòu),從而基于這些信息快速得到最新的結(jié)果集.另外,目前動態(tài)變化下的遺憾查詢研究還比較單一,如效用空間局限于線性函數(shù),非線性效用空間下的流式查詢工作還存在空白,而上述解決思路亦可應(yīng)用非線性效用函數(shù)下的算法(MinWidth,MinVar)進行處理.

4.2 結(jié)合機器學習

盡管目前最好的遺憾率查詢算法(如Sphere)可以返回遺憾率較小的結(jié)果,但對某一具體用戶而言,仍可能對返回結(jié)果感到不滿意.因為遺憾查詢針對的是同一效用空間下的用戶群體,給整體做出的查詢結(jié)果,因而每個用戶獲得的結(jié)果相同,且每次查詢都是相同的返回內(nèi)容.因此,針對特定用戶的遺憾查詢問題也是一個值得關(guān)注的研究方向.相關(guān)解決思路是:考慮結(jié)合機器學習中的主動學習(Active Learning)技術(shù)[61],將用戶可能的喜好看作是假設(shè)集,根據(jù)假設(shè)集去設(shè)置一系列的問題以及相應(yīng)的回答,通過交互的方式主動學習用戶的偏好.每輪交互中,采用一定的策略選擇問題來向用戶進行提問,用戶則根據(jù)自己的喜好做出相應(yīng)的回復,以此來篩選假設(shè)集,縮小結(jié)果集的候選范圍,從而逐步降低結(jié)果的遺憾率.其中,每一輪交互的結(jié)果都會影響著后續(xù)問題的選擇,所以,為了使得用戶能快速得到滿意的結(jié)果(遺憾率小),選擇問題的策略至關(guān)重要.

從另一個角度來看,之前的研究中,對特定用戶降低遺憾的方式是借助交互機制.交互方法雖然在一定程度上解決了遺憾查詢存在的問題,卻需要用戶花費時間與精力進行判斷給出反饋,這無疑增加了用戶負擔、降低了體驗效果.一個直覺上的想法是借助歷史記錄、緩存等手段,根據(jù)用戶的點擊與瀏覽信息,學習得到其效用函數(shù)信息,逐漸縮小特定用戶的效用函數(shù)范圍,在查詢時有針對性的返回結(jié)果以供用戶使用.Shetiya等人[56]引入數(shù)據(jù)挖掘中的算法解決遺憾率問題具有借鑒意義,而借助機器學習手段有效地降低用戶遺憾是未來研究的一個方向.

4.3 二進制約束與公平性約束下的遺憾查詢

二進制約束 用戶查詢時往往會對一些屬性值的范圍進行限制,如在購買電腦時限制價格在4000與7000元之間,內(nèi)存要求至少為8G等.這類約束被稱為二進制約束(binary constraint),即某商品在該屬性上要么滿足要么不滿足,查詢過程中要滿足用戶對這些屬性的需求.遺憾查詢需在滿足二進制約束的前提下,盡可能地最小化遺憾率.一個二進制約束可用符號c表示,若點p滿足該約束,則c(p)=1否則c(p)=0.對于一組二進制約束C={c1,c2,…,cr},點p滿足的約束集為C(p)={ci∈C:ci(p)=1}.因此,二進制約束下的遺憾查詢可定義如下:給定數(shù)據(jù)集D,與一組二進制約束集合C={c1,c2,..,cr},返回數(shù)量至多為k的子集S,使得滿足的約束集∪p∈SC(p)數(shù)量盡可能多,且集合S的遺憾率rrD(S,F)盡可能小.Dong等人[62]定義了二進制約束的支配關(guān)系,縮減了初始候選集,降低計算量,并利用線性規(guī)劃設(shè)計了貪婪算法.然而Dong等人[62]的研究技術(shù)還不成熟,所提算法沒有理論保證,不能保證輸出解的質(zhì)量,極端情況下算法所得結(jié)果可能會任意差.二進制約束下的遺憾查詢?nèi)孕枰哂欣碚摫ＷC的算法填補空白.

公平性約束 另外一種約束是當下比較熱門的話題:公平性(fairness)[63-67].公平性作為評估決策、算法是否合理的依據(jù),在不同情景下有著迥異的定義方式,而最常見且適用于查詢問題的是統(tǒng)計公平性[66,67].具體來說,數(shù)據(jù)集可根據(jù)一些屬性值劃分為不同的群體,統(tǒng)計公平性指,最終返回的結(jié)果集中含有各群體中數(shù)量應(yīng)該與其所在群體數(shù)量成正比.公平性最直觀的例子是挑選候選人,受到資源分配、政策等限制,從所有候選者中直接挑選出表現(xiàn)最優(yōu)的一部分人是不夠公平的.為達到公平性要求,應(yīng)根據(jù)性別、民族、年齡等因素,將候選人劃分到不同的群體,在各群體中按照所分配到名額進行擇優(yōu)選擇.因此查詢問題中的公平性約束可定義為對于不同群體Gi,限制選取數(shù)據(jù)點的數(shù)量ki.公平性約束下的遺憾查詢問題具體形式為:給定劃分為l個群體的數(shù)據(jù)集D(={G1,…,Gl}),及各群體的數(shù)量約束{k1,…,kl},目標是找到一個子集S,在滿足分組約束的前提下(即|S∩Gi|=ki)使得遺憾率rrD(S,F)盡可能地小.這類公平性約束是劃分擬陣(partition matroid)的特例,因此針對劃分擬陣的研究成果同樣可以適用于該類約束問題.根據(jù)文獻[36]的思想,可以將遺憾查詢問題建模為集合覆蓋問題,而劃分擬陣下的集合覆蓋問題有一定的研究基礎(chǔ),基于此,可以設(shè)計出解決公平性約束下遺憾查詢的方法.因此,遺憾查詢結(jié)合公平性也是有前景且可行的一個研究內(nèi)容.

4.4 引入次模函數(shù)

次模效應(yīng)指的是邊際增益遞減的一種現(xiàn)象,而次模函數(shù)f滿足對于定義域上的集合A與B都有f(A)+f(B)≥f(A∩B)+f(A∪B)[68].超模函數(shù)是與次模相逆的概念,若-f是次模函數(shù),則f滿足超模性.Zeighami等人[52]指出平均遺憾率函數(shù)是超模函數(shù),借助超模函數(shù)性質(zhì)可以保證輸出解的理論質(zhì)量.Zheng等人[69]指出最小開心函數(shù)不是次模函數(shù),但單個效用函數(shù)f下的開心度函數(shù)是次模的,這表明最小開心度函數(shù)仍具有次模的一部分性質(zhì),通過次模率(submodularity ratio)的概念可以構(gòu)建出次模與遺憾查詢的橋梁.覆蓋函數(shù)(coverage function)亦是次模函數(shù),因此文獻[36]提出的將查詢轉(zhuǎn)化為集合覆蓋思想可以視為次模的特例化研究,進一步論證了次模理論用于遺憾查詢的可行性.基于此,次模理論下的一些技術(shù)可以引入到遺憾查詢中,如最優(yōu)子集的選取[70],數(shù)據(jù)流下的研究[71,72],加速算法的策略[73,74]等.未來研究或可借助次模理論,對遺憾查詢的變體研究提供理論保證(如數(shù)據(jù)流下查詢,公平性約束下的研究等).

4.5 遺憾查詢的應(yīng)用

遺憾查詢可以集成到數(shù)據(jù)庫SQL查詢子句中.在SELECT聲明時可以集成可選的子句“REGRET-SET WITH …”,通過遺憾查詢進一步篩選結(jié)果.如下所示:

SELECT … FROM … WHERE …

REGRET-SET

WITH [sizek| error]

其中sizek可由用戶指定輸出集大小,并在查詢過程中最小化遺憾率;或由用戶指定遺憾率上界,查詢結(jié)果返回盡可能小的候選集使得遺憾率不超過.

遺憾查詢也可以作為工具用到其它問題領(lǐng)域中.與遺憾查詢聯(lián)系較為緊密的是多目標優(yōu)化問題.多目標優(yōu)化問題在處理過程中需滿足同時優(yōu)化多個目標函數(shù)(準則),這與遺憾查詢不謀而合:遺憾查詢將各維屬性值作為優(yōu)化準則,且最大遺憾率函數(shù)要求最壞情況下的效用值盡可能地好.Soma等人[75]與Feng等人[76]把遺憾查詢作為衡量求解多目標優(yōu)化問題算法的評價指標,類似于近似率的概念,對所提出的近似算法優(yōu)劣性進行判斷.Soma等人[74]率先提出多目標優(yōu)化問題可以借助遺憾的概念,用遺憾率衡量算法輸出解的質(zhì)量好壞,進而基于Cube算法的思想設(shè)計了多目標優(yōu)化問題下的算法,用以解決一般的多目標優(yōu)化問題,并從幾何角度進闡述算法流程與意義.Feng等人[76]為解決多目標優(yōu)化問題,也借助遺憾概念提出一種基于采樣的遺憾率最小化算法RRMS(Regret Ratio Minimization by Sampling),并對算法輸出解的最大遺憾率進行了理論保證.此外,計算機視覺領(lǐng)域的視頻概要(Video summarization)[77]問題是從大量幀中提取代表的若干幅圖片代表整個視頻,當一副圖片可以從多個角度(重要性、故事性)等描述時,視頻概要問題就是一個多準則決策問題.因此,可以將遺憾查詢技術(shù)引入到視頻概要中.另外,隨著研究的不斷深入,遺憾查詢將為其它領(lǐng)域的多準則決策、多目標優(yōu)化問題提供借鑒.

5 總 結(jié)

本文首先對top-k和skyline查詢以及代表點查詢技術(shù)做了簡單介紹,然后重點介紹了遺憾最小化查詢目前的研究進展情況.從遺憾查詢基本的概念出發(fā),介紹該領(lǐng)域的各種典型算法,并展開介紹其變種處理技術(shù).在最后部分,對遺憾查詢領(lǐng)域未來可能的研究點進行了展望.通過對遺憾查詢較為全面的介紹和總結(jié),為相關(guān)研究人員能夠快速進入該領(lǐng)域展開研究提供幫助.