包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)

王美靜,鄭吉平,2

1(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211106)

2(南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,南京 210093)

0 引 言

隨著互聯(lián)網(wǎng)的發(fā)展,數(shù)據(jù)資源的重要性日益凸顯,如何進(jìn)行多準(zhǔn)則決策,即從海量的數(shù)據(jù)中找出小部分具有代表性且滿足用戶(hù)需求的數(shù)據(jù)來(lái)代表整個(gè)數(shù)據(jù)集,是數(shù)據(jù)庫(kù)系統(tǒng)的一個(gè)重要功能.這樣的問(wèn)題出現(xiàn)在許多現(xiàn)實(shí)應(yīng)用中,如個(gè)性化推薦、市場(chǎng)交易、職場(chǎng)招聘等.在多準(zhǔn)則決策問(wèn)題中,有兩種常用的方法,即skyline查詢(xún)和top-k查詢(xún),但這兩種查詢(xún)分別具有結(jié)果集大小不可控和要求用戶(hù)指定精確的效用函數(shù)(亦稱(chēng)評(píng)分函數(shù)、用戶(hù)偏好函數(shù)等)的缺點(diǎn).為了克服這些缺點(diǎn),Nanongkai等人[1]首次提出k-遺憾查詢(xún),即遺憾最小化查詢(xún).通過(guò)定義“遺憾率”,將遺憾率最小的結(jié)果集作為代表整個(gè)數(shù)據(jù)集的集合返回給用戶(hù).近年來(lái),遺憾最小化查詢(xún)因其具有結(jié)果集大小可控、不要求用戶(hù)提供具體的效用函數(shù)、尺度不變性和穩(wěn)定性等優(yōu)點(diǎn),得到廣泛研究[1-12].

為了進(jìn)一步降低遺憾率,提高查詢(xún)效率,Nanongkai等人[2]首次引入交互機(jī)制,提出交互式遺憾最小化查詢(xún).通過(guò)不斷地向用戶(hù)展示一些數(shù)據(jù)(元組),讓其從中選擇自己最滿意的一個(gè)元組,然后基于用戶(hù)的反饋,不斷縮小效用空間,持續(xù)上述交互過(guò)程,直至:找到數(shù)據(jù)集中用戶(hù)最滿意的元組,或者結(jié)果集的遺憾率達(dá)到用戶(hù)能接受的范圍.目前,已有學(xué)者在交互式遺憾最小化方面做了一些研究[3-5].

然而,無(wú)論是傳統(tǒng)的遺憾最小化,還是交互式遺憾最小化,都是在數(shù)據(jù)集中的數(shù)據(jù)僅具有數(shù)值型屬性的前提下進(jìn)行.比如在一個(gè)汽車(chē)數(shù)據(jù)集中,每輛汽車(chē)擁有3個(gè)屬性:百公里油耗、百公里加速時(shí)間和價(jià)格,這些屬性均為數(shù)值形式,本身就具有“越大越好”或者“越小越好”的客觀順序,且可以直接通過(guò)效用函數(shù)(用戶(hù)對(duì)每維屬性的權(quán)重)來(lái)計(jì)算效用值,從而根據(jù)效用值的大小衡量一輛汽車(chē)的好壞.但是,在實(shí)際應(yīng)用中,數(shù)據(jù)集中的數(shù)據(jù)可能還會(huì)具有非數(shù)值型的屬性,如在上述的汽車(chē)數(shù)據(jù)集中,汽車(chē)可能還會(huì)有品牌(紅旗、比亞迪、寶馬等)、顏色(白色、黑色、藍(lán)色等)等非數(shù)值形式的屬性.在不知道用戶(hù)任何偏好的情況下,這些屬性不存在客觀的順序,無(wú)法直接計(jì)算每輛汽車(chē)的效用值并衡量其好壞,而現(xiàn)有的方法無(wú)法解決這類(lèi)問(wèn)題.

從另一方面看,即使某些數(shù)據(jù)集中數(shù)據(jù)的屬性都是數(shù)值型的,如果用戶(hù)對(duì)某屬性的要求不是單調(diào)的“越大越好”或者“越小越好”,而是希望在某一個(gè)區(qū)間內(nèi),那么也可以將其看作是非數(shù)值型屬性的情況.比如在電影數(shù)據(jù)集中,電影具有時(shí)長(zhǎng)這一屬性,比起時(shí)長(zhǎng)為1小時(shí)和3小時(shí)的電影,用戶(hù)更喜歡時(shí)長(zhǎng)為1～2小時(shí)的.在面對(duì)這種問(wèn)題時(shí),遺憾最小化查詢(xún)領(lǐng)域未有涉及.

基于上述問(wèn)題,本文提出包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún),并給出基于最大期望候選集縮減的問(wèn)題選擇算法(Maximum Expected Candidate Reduction based Question Selection,MECR_QS),可以有效解決包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)問(wèn)題.本文主要貢獻(xiàn)如下:

1)針對(duì)存在非數(shù)值型屬性的數(shù)據(jù),提出一種遺憾率的定義;并進(jìn)而提出相應(yīng)的交互式遺憾最小化查詢(xún)問(wèn)題的定義.

2)借助偏好矩陣學(xué)習(xí)記錄用戶(hù)的偏好,提出一種用于解決包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)問(wèn)題的算法MECR_QS.

3)采用合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集對(duì)算法MECR_QS進(jìn)行對(duì)比實(shí)驗(yàn),驗(yàn)證其有效性,實(shí)驗(yàn)結(jié)果表明,算法MECR_QS能有效處理包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)問(wèn)題.

本文結(jié)構(gòu)如下:第1節(jié)簡(jiǎn)要介紹遺憾最小化查詢(xún)以及交互式遺憾最小化查詢(xún)的相關(guān)工作;第2節(jié)詳細(xì)介紹包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)問(wèn)題所涉及到的相關(guān)概念以及問(wèn)題定義;第3節(jié)提出用于預(yù)處理的skyline刪減算法和用于解決交互式遺憾最小化的算法MECR_QS;第4節(jié)通過(guò)與幾個(gè)算法的變體以及現(xiàn)有算法對(duì)比,對(duì)算法MECR_QS進(jìn)行實(shí)驗(yàn)評(píng)估驗(yàn)證;第5節(jié)對(duì)本文工作進(jìn)行總結(jié).

1 相關(guān)工作

自Nanongkai等人[1]首次提出遺憾最小化查詢(xún)后,多種高效遺憾最小化查詢(xún)算法陸續(xù)被提出[6,7].Nanongkai等人[1]通過(guò)劃分?jǐn)?shù)據(jù)空間提出立方體(Cube)算法,并給出其最大遺憾率的界,針對(duì)Cube算法的結(jié)果集可能會(huì)少于k個(gè)且實(shí)際效果較差的問(wèn)題,以逐步優(yōu)化最差的思想提出基于拉默-道格拉斯-普克框架的貪婪算法(Ramer-Douglas-Peucker-Greedy algorithm,RDP-Greedy算法).Peng等人[8]通過(guò)先在skyline集上篩選開(kāi)心點(diǎn)(happy points),再?gòu)闹羞M(jìn)行遺憾最小化查詢(xún),以提高查詢(xún)效率.Xie等人[9]通過(guò)先找到能代表線性效用空間的效用函數(shù)集合,再根據(jù)該集合計(jì)算基礎(chǔ)集(basis),最后從中選擇元組作為查詢(xún)結(jié)果,給出更優(yōu)的理論上界.Agarwal等人[10]將遺憾查詢(xún)規(guī)約到命中集(hitting set)問(wèn)題,Ausdeh等人[11]將最小化最大遺憾率問(wèn)題歸約到矩陣的最小-最大問(wèn)題,并進(jìn)一步歸約到集合覆蓋問(wèn)題.Wang等人[12]考慮k-遺憾查詢(xún)的動(dòng)態(tài)情況,將其轉(zhuǎn)化為動(dòng)態(tài)集合覆蓋問(wèn)題,以進(jìn)行遺憾最小化查詢(xún).

Nanongkai等人[2]通過(guò)引入交互機(jī)制(讓用戶(hù)從展示的元組中選擇自己最滿意的一個(gè))減小結(jié)果集的遺憾率,將其擴(kuò)展為交互式遺憾最小化,彌補(bǔ)傳統(tǒng)的遺憾最小化查詢(xún)?cè)诓樵?xún)效率方面的不足.他們證明了交互可以有效降低遺憾率,并減小了結(jié)果集大小.但在他們的交互過(guò)程中,存在不屬于數(shù)據(jù)庫(kù)中的(虛假的,人為構(gòu)造的)元組,可能導(dǎo)致用戶(hù)失望.Xie等人[3]對(duì)此從幾何的角度設(shè)計(jì)了新的交互式遺憾最小化算法,在保證使用真實(shí)的(數(shù)據(jù)集中存在的)元組進(jìn)行交互的同時(shí),降低交互輪次.Zheng等人[4]和Chen等人[5]通過(guò)讓用戶(hù)對(duì)展示的元組進(jìn)行排序的方法,充分利用排序信息,進(jìn)一步減少交互次數(shù).

此外,還有一些其它的方法[11-15]同樣通過(guò)交互來(lái)學(xué)習(xí)用戶(hù)的偏好.Mindolin等人[13]通過(guò)讓用戶(hù)將展示的元組分為“喜歡”和“不喜歡”兩組,來(lái)探索用戶(hù)對(duì)不同屬性之間的偏好權(quán)重關(guān)系.Lee等人[14]將用戶(hù)偏好建模為嚴(yán)格的部分屬性排序來(lái)進(jìn)行個(gè)性化skyline查詢(xún).Jamieson等人[15]希望通過(guò)交互給數(shù)據(jù)集中所有元組排序,Qian等人[16]希望通過(guò)交互學(xué)習(xí)用戶(hù)的所有隱式偏好,這都會(huì)導(dǎo)致他們向用戶(hù)提問(wèn)更多的問(wèn)題,而其中有些問(wèn)題可能是不必要的,因?yàn)樗麄儾皇抢脤W(xué)習(xí)到的偏好找用戶(hù)最喜歡的元組.Wang等人[17]的交互方法同文獻(xiàn)[15]和文獻(xiàn)[16]一樣,每個(gè)問(wèn)題都是讓用戶(hù)從展示的兩個(gè)元組中選擇一個(gè)更喜歡的,以此來(lái)學(xué)習(xí)用戶(hù)的偏好,以較少的用戶(hù)精力找到用戶(hù)top-k之一的元組.

然而,以上方法都是針對(duì)只有數(shù)值型屬性的情況,當(dāng)遇到包含非數(shù)值型屬性的數(shù)據(jù)集時(shí),它們無(wú)法有效地解決查詢(xún)問(wèn)題.關(guān)于非數(shù)值型屬性,僅有少數(shù)非遺憾查詢(xún)領(lǐng)域有所涉及.He等人[18]未借助交互,而是基于表格掃描的方法篩選數(shù)據(jù)集中的元組.Jiang等人[19]的交互方法同文獻(xiàn)[13]一樣,通過(guò)讓用戶(hù)將展示的元組分為“喜歡”和“不喜歡”兩組來(lái)學(xué)習(xí)用戶(hù)的偏好,而本文同文獻(xiàn)[20]中的做法一樣,直接給出兩個(gè)屬性值,讓用戶(hù)選擇其中更喜歡的一個(gè),從而減少用戶(hù)精力.但Lee等人[20]注重通過(guò)交互盡可能找到用戶(hù)所有的偏好,以進(jìn)行skyline查詢(xún),這依然會(huì)耗費(fèi)不少用戶(hù)精力.Le等人[21]借助偏好矩陣來(lái)學(xué)習(xí)用戶(hù)偏好,但他們的目的不是從數(shù)據(jù)集中尋找用戶(hù)滿意的元組.Qin等人[22]在交互時(shí)不僅需要用戶(hù)決定所展示的所有元組的去留,還需要將其進(jìn)行排序,以消耗大量用戶(hù)精力來(lái)?yè)Q取用戶(hù)偏好信息.

與上述研究不同,本文提出包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún),給出了相關(guān)定義并提出算法MECR_QS,在盡可能減少用戶(hù)精力的同時(shí)從數(shù)據(jù)集中找出用戶(hù)滿意的元組,以彌補(bǔ)現(xiàn)有研究的不足.

2 問(wèn)題分析及定義

在正式介紹本文研究的問(wèn)題之前,本節(jié)首先介紹支配、skyline、遺憾率、期望候選集縮減等相關(guān)概念,相關(guān)符號(hào)及描述如表1所示.

表1 相關(guān)符號(hào)及描述Table 1 Symbols and descriptions

定義1.(支配)給定兩個(gè)元組p,q∈V,當(dāng)且僅當(dāng)?Di∈D:piq且?Dj∈D:p?jq時(shí),稱(chēng)元組p支配元組q,即元組p在所有維度都不差于元組q,且在某一維度(如j)優(yōu)于元組q.

對(duì)于數(shù)值型屬性,可以直接通過(guò)數(shù)值的大小來(lái)判斷屬性值的優(yōu)劣程度;而對(duì)于非數(shù)值型屬性,由于屬性值之間不存在客觀的順序,需要根據(jù)用戶(hù)的偏好決定其優(yōu)劣,所以在判斷兩個(gè)元組間的支配關(guān)系時(shí),需要關(guān)注用戶(hù)對(duì)非數(shù)值型屬性的偏好.

如表2所示,題材和上映年份是電影的兩個(gè)非數(shù)值型屬性,評(píng)分(滿分是10)和票房是兩個(gè)數(shù)值型屬性.顯然,評(píng)分高,票房高的電影更優(yōu).根據(jù)定義1,可以看出v4支配v3,因?yàn)樵陬}材和上映年份這兩個(gè)屬性上二者相等,即v4不差于v3,而在評(píng)分和票房?jī)蓚€(gè)屬性上v4優(yōu)于v3.由于事先并不知道用戶(hù)對(duì)于“恐怖”“懸疑”“科幻”以及“2013”“2015”之間的偏好關(guān)系,無(wú)法判斷哪個(gè)屬性值更優(yōu),所以無(wú)法判斷其它電影之間的支配關(guān)系.如v1和v3之間,盡管它們?cè)谠u(píng)分和票房?jī)蓚€(gè)屬性上有明顯的支配關(guān)系(v3更優(yōu)),但它們?cè)陬}材屬性上的不同,使得這一關(guān)系并不一定成立,當(dāng)用戶(hù)更喜歡“恐怖”而非“懸疑”時(shí),v3就無(wú)法支配v1.

表2 電影屬性信息Table 2 Movie attribute information

此外,支配本身還具有以下性質(zhì):

1)傳遞性[23],即若元組p支配元組q,q又支配元組o,那么p也支配o.如表2中,若已知“懸疑>恐怖”,那么可知v4支配v3,v3支配v1,由傳遞性可得v4也支配v1.這一點(diǎn)也可以由支配的定義直接得出,v4的評(píng)分和票房數(shù)值都比v1高,上映年份相同而v4的“懸疑”優(yōu)于v3的“恐怖”,所以v4支配v1.

2)累加性[24],定義f(s)=∑Ai∈ANs(Ai),表示元組s的數(shù)值型屬性值之和,其中s(Ai)表示元組s的第i維屬性值.若元組p支配元組q,則f(p)≥f(q),即p的數(shù)值型屬性值之和一定大于等于q的數(shù)值型屬性值之和,這里假設(shè)數(shù)值型屬性值越大越優(yōu);反之,若f(p)

定義2.(Skyline)當(dāng)且僅當(dāng)元組p在屬性集A上不被任何元組支配時(shí),稱(chēng)p是A上的一個(gè)skyline元組.給定數(shù)據(jù)集V,其skyline是所有skyline元組的集合.

如表2所示,在沒(méi)有任何先驗(yàn)知識(shí)的情況下,只能得到v4支配v3,其skyline為{v1,v2,v4,v5}.若已知“科幻?懸疑?恐怖”,那么除了v4支配v3,還可以得到v3支配v1,v5支配v2,此時(shí),skyline就變?yōu)閧v4,v5}.若已知“科幻?懸疑”“2015?2013”,則可知v2支配v1,v4支配v3,v5支配v4,此時(shí)skyline為{v2,v5}.

將元組p的遺憾率定義為:

(1)

將集合S的遺憾率(regret ratio,rr)定義為:

(2)

其中,Ai是元組p∈S對(duì)應(yīng)的屬性.顯然,0≤rrp≤1,0≤rrS≤1.

假設(shè)用戶(hù)在表2的5部電影中最喜歡v4,那么根據(jù)定義3,v1,v2,v3和v5的遺憾率分別為0.75,1,0.5和0.5,因?yàn)関1和v4的非數(shù)值型屬性中只有“2013”是相同的,而v1的數(shù)值型屬性值均沒(méi)有v4的大,所以rv1=4-1=3,rrv1=1-1/4=0.75,其余同理.而根據(jù)定義3,集合{v1,v3}的遺憾率為0.5,因?yàn)?d-rv1)/d=0.25,(d-rv3)/d=0.5.

定義4.(期望候選集縮減,Expected Candidate Reduction,ECR)用(x,y)表示交互過(guò)程中可能向用戶(hù)提出的問(wèn)題qi∈Q,其中x,y∈Di,即x和y是屬于同一維度(第i維)的兩個(gè)屬性值,用戶(hù)對(duì)于問(wèn)題qi的回答只會(huì)有3種情況:x?y,x～y,xy.令表示當(dāng)用戶(hù)對(duì)于問(wèn)題qi的回答是x?y時(shí),候選集根據(jù)用戶(hù)回答更新后的大小,和則分別對(duì)應(yīng)用戶(hù)回答是x～y和xy的情況.定義期望候選集縮減為:

(3)

用于在交互過(guò)程中選擇向用戶(hù)提出問(wèn)題的策略.

注意,如果沒(méi)有先驗(yàn)信息(即不知道用戶(hù)的任何偏好或者無(wú)法從用戶(hù)的歷史操作記錄中或許到任何有效信息),則默認(rèn)Pr(x?y|qi)=Pr(x～y|qi)=Pr(xy|qi)=1/3[20].而如果已知一些信息,比如在用戶(hù)的歷史觀影記錄中,具有“懸疑”屬性的電影數(shù)量是具有“恐怖”屬性電影的兩倍,則當(dāng)問(wèn)題是“(懸疑,恐怖)”時(shí),用戶(hù)回答是“懸疑?恐怖”的概率為2/(1+2)=2/3,是“懸疑恐怖”的概率為1/(1+2)=1/3.

定義5.(偏好矩陣)給定數(shù)據(jù)集V,非數(shù)值型屬性的維度m,用戶(hù)關(guān)于非數(shù)值型屬性的偏好信息用m個(gè)偏好矩陣PM1,PM2,…,PMm表示,每個(gè)矩陣PMi的大小由第i維屬性值的個(gè)數(shù)決定,即PMi是一個(gè)|Di|×|Di|矩陣,其中Di∈DC.用PMi(a,b)表示矩陣PMi中第a行第b列的元素,共有4種可能的值:0,-1,1,-10.由于屬性有固定的順序,所以可將PMi(a,b)看作是第i維屬性中用戶(hù)對(duì)第a個(gè)屬性值x和第b個(gè)屬性值y的偏好.PMi(a,b)=0表示用戶(hù)對(duì)屬性值x和y的喜歡程度相同,即x～y;PMi(a,b)=-1表示用戶(hù)相比屬性值x,更喜歡y,即xy;PMi(a,b)=1表示用戶(hù)相比屬性值y,更喜歡x,即x?y;PMi(a,b)=-10表示目前暫時(shí)未知用戶(hù)對(duì)屬性值x和y的偏好.

比如表2中“題材”屬性所對(duì)應(yīng)的偏好矩陣PM1如表3所示,假設(shè)已知用戶(hù)相比“恐怖”,更喜歡“懸疑”,即“懸疑?恐怖”,那么PM1(2,1)=1,且PM1(1,2)=-1.在初始化偏好矩陣時(shí),對(duì)角線元素就全為0,因?yàn)槊總€(gè)屬性值和自己相比,用戶(hù)對(duì)其的喜愛(ài)程度一定相同,如表3矩陣PM1中:PM1(1,1)=0,PM1(2,2)=0,PM1(3,3)=0.而暫時(shí)未知用戶(hù)關(guān)于“恐怖”“科幻”間以及“懸疑”“科幻”間的偏好關(guān)系,所以PM1(1,3)=-10,PM1(3,1)=-10,PM1(2,3)=-10,PM1(3,2)=-10.

表3 偏好矩陣示例Table 3 Example of a preference matrix

若在表3的基礎(chǔ)上,通過(guò)一次交互得知用戶(hù)相比“恐怖”,更喜歡“科幻”,即“恐怖?科幻”,那么可更新偏好矩陣PM1(1,3)=1和PM1(3,1)=-1.而根據(jù)“懸疑?恐怖”和定義1中支配的傳遞性可知“懸疑?科幻”(“懸疑?恐怖?科幻”),所以可繼續(xù)更新偏好矩陣PM1(2,3)=1和PM1(3,2)=-1.最終更新后的偏好矩陣PM1如表4所示.

表4 更新后的偏好矩陣示例Table 4 Example of an updated preference matrix

問(wèn)題定義.(交互式遺憾最小化查詢(xún))給定數(shù)據(jù)集V,屬性維度為d,非數(shù)值型屬性的維度為m(數(shù)值型屬性的維度為d-m),目標(biāo)是通過(guò)交互,以盡可能少的代價(jià)(盡可能少的交互輪次)找到一個(gè)小的子集S,該子集的遺憾率最小,即:

(4)

簡(jiǎn)單來(lái)說(shuō),如果依次向用戶(hù)提問(wèn),構(gòu)成的問(wèn)題集合為Q1,Q2,…,Qh,其中Q1?Q2?…?Qh,h為最終的交互次數(shù),得到縮減的數(shù)據(jù)集合V1,V2,…,Vh,其中V1?V2?…?Vh,并最終知道用戶(hù)所有的偏好信息,可達(dá)到準(zhǔn)確推薦的目的(遺憾率為0),成功推薦出用戶(hù)最滿意的元組,或者達(dá)到用戶(hù)滿意的遺憾率.本文的目標(biāo)是通過(guò)提問(wèn)盡可能少的問(wèn)題,達(dá)到用戶(hù)的要求,進(jìn)而提出算法MECR_QS.

3 算 法

基于上述概念,本章提出一個(gè)面向包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)算法:最大期望候選集縮減的問(wèn)題選擇算法MECR_QS.該算法根據(jù)每一對(duì)“不確定兩兩之間偏好關(guān)系”的非數(shù)值型屬性分別生成一個(gè)問(wèn)題,每輪交互都會(huì)選擇一個(gè)可以使得期望候選集縮減最大的問(wèn)題去向用戶(hù)提問(wèn),然后根據(jù)用戶(hù)的回答更新用戶(hù)偏好信息,并對(duì)候選集進(jìn)行相應(yīng)的刪減,直至達(dá)到交互的停止條件.

為了提高遺憾最小化查詢(xún)的效率,首先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理,即對(duì)于非數(shù)值型屬性一樣的數(shù)據(jù),根據(jù)其數(shù)值型屬性進(jìn)行skyline刪減,相關(guān)引理及算法如下:

引理1.(skyline刪減)給定兩個(gè)元組p,q,若元組p支配q,則元組q可以被刪除,即元組p,q滿足以下兩個(gè)條件:1)元組p,q所有非數(shù)值型屬性的屬性值均完全相同,即?Ai∈AC:p(Ai)=q(Ai);2)關(guān)于數(shù)值型屬性,元組p完全支配元組q,即?Aj∈AN:p(Aj)jq(Aj),并且?Ak∈AN:p(Ak)?kq(Ak).其中j表示在第j個(gè)屬性上(元組p)不差于(元組q),?k表示在第k個(gè)屬性上(元組p)完全優(yōu)于(元組q).

在skyline刪減之前,首先按照數(shù)據(jù)的非數(shù)值型屬性將數(shù)據(jù)分類(lèi),即非數(shù)值型屬性完全相同的數(shù)據(jù)為一類(lèi),便于后續(xù)通過(guò)交互信息篩選時(shí)可以不直接對(duì)數(shù)據(jù)進(jìn)行操作,而是對(duì)類(lèi)進(jìn)行篩選.然后再根據(jù)引理1對(duì)數(shù)據(jù)集進(jìn)行初步skyline篩選,由于數(shù)據(jù)集已分類(lèi),所以可直接在類(lèi)中根據(jù)數(shù)值型屬性進(jìn)行skyline篩選,具體如算法1所示.

算法1.skyline刪減

輸入：按非數(shù)值型屬性分類(lèi)的數(shù)據(jù)集V1,V2,…,Vl

輸出：skyline刪減后的數(shù)據(jù)集V1′,V2′,…,Vl′

1.foreachVi,i∈1,…,l

2. 初始化skyline列表L為空;

3. 計(jì)算所有p∈Vi的∑Ai∈ANAi,并排序;//如果數(shù)值型屬性值越小越好,則按降序排列,否則按升序排列

4.foreachp∈Vi

5.ifp被任意一個(gè)q∈L支配

6. continue;

7.else//L中沒(méi)有可以支配p的

8.L←L∪{p};

9.endfor

10.Vi′←L;

11.endfor

skyline刪減算法將已按非數(shù)值型屬性分類(lèi)的數(shù)據(jù)集V1,V2,…,Vl作為算法的輸入,其中l(wèi)表示類(lèi)的個(gè)數(shù),最大為非數(shù)值型屬性的域|DC|,即所有非數(shù)值型屬性值個(gè)數(shù)的累乘|D1|×…×|Dm|,其中m為非數(shù)值型屬性的維度.然后分別對(duì)每個(gè)Vi按照引理1進(jìn)行skyline篩選,注意這里已將數(shù)據(jù)的數(shù)值型屬性值規(guī)范化到[0,1],并已統(tǒng)一所有維度的值都是“越小越好”或“越大越好”(不統(tǒng)一的可以用1減去原本的值進(jìn)行轉(zhuǎn)化).篩選時(shí),首先將列表L(表示當(dāng)前的skyline結(jié)果)初始化為空,即算法1的第2行.若已統(tǒng)一當(dāng)前數(shù)據(jù)集的數(shù)值型屬性值越小越優(yōu),則計(jì)算Vi中所有元組的數(shù)值型屬性值之和∑Ai∈ANAi,并按降序?qū)⑵鋵?duì)應(yīng)的元組排列;反之,若值越大越優(yōu),則計(jì)算屬性值之和后按升序排列,從而利用支配的第2條性質(zhì)減少檢查元組間支配關(guān)系的次數(shù).算法1的第4～9行遍歷一次Vi的所有元組,通過(guò)判斷其是否與當(dāng)前列表L中的元組形成支配關(guān)系,以篩選出Vi的初步skyline結(jié)果.最后將Vi更新為最終的L.

與已有方法[20]不同,算法1對(duì)每個(gè)類(lèi)內(nèi)部作處理,可以省去不同類(lèi)之間數(shù)據(jù)的比較.原因是不同類(lèi)之間數(shù)據(jù)的非數(shù)值型屬性必然是不相同的,根據(jù)引理1可知無(wú)法判斷他們之間的支配關(guān)系,所以無(wú)需比較,由此提高了預(yù)處理效率.

預(yù)處理結(jié)束后,在非數(shù)值型屬性的每一維中,針對(duì)每一對(duì)“不確定兩兩之間偏好關(guān)系”的屬性值生成一個(gè)對(duì)應(yīng)的問(wèn)題,一個(gè)問(wèn)題中包含同一屬性的兩個(gè)屬性值,即詢(xún)問(wèn)用戶(hù)對(duì)于某一維兩個(gè)屬性值之間的偏好關(guān)系.這些問(wèn)題構(gòu)成的集合Q就是在交互過(guò)程中可能會(huì)向用戶(hù)提問(wèn)的所有問(wèn)題集合,而在每輪交互中,選擇集合Q中的哪一個(gè)問(wèn)題去提問(wèn)則是根據(jù)定義4中的期望候選集縮減ECR來(lái)決定.為了能在較少的交互輪次中使用戶(hù)的遺憾最小化(找到用戶(hù)最滿意的元組),本文提出的算法在每一輪交互中都選擇使得當(dāng)前期望候選集縮減最大的問(wèn)題,即argmaxq∈QECR(q).然后根據(jù)用戶(hù)的回答,不斷更新存儲(chǔ)用戶(hù)偏好信息的偏好矩陣和候選集,直至候選集中只剩下一個(gè)元組(遺憾率為0),或者沒(méi)有能使得期望候選集繼續(xù)縮減的問(wèn)題存在.具體細(xì)節(jié)如算法2所示.

算法2.MECR_QS

輸入：預(yù)處理過(guò)的數(shù)據(jù)集V1′,V2′,…,Vl′,問(wèn)題集合Q,偏好矩陣PM1,PM2,…,PMm

輸出：候選集C

1.C←V1′∪V2′∪…∪Vl′;

2.初始化PM1,PM2,…,PMm;

3.while|C|>1 &?qi∈Q使得ECR(qi)>0do

7. 根據(jù)用戶(hù)回答更新PMi和C;

8.endwhile

算法2將經(jīng)算法1預(yù)處理后的數(shù)據(jù)集V1′,V2′,…,Vl′作為輸入,即已按照非數(shù)值型屬性分類(lèi),且在類(lèi)中根據(jù)數(shù)值型屬性完成skyline刪減的數(shù)據(jù)集,一同作為輸入的還有問(wèn)題集合Q以及偏好矩陣PM1,PM2,…,PMm.首先將整個(gè)輸入的數(shù)據(jù)集作為候選集,并根據(jù)是否存在先驗(yàn)信息來(lái)初始化偏好矩陣(算法2的第1～2行):當(dāng)無(wú)任何先驗(yàn)信息時(shí),將所有偏好矩陣中除對(duì)角線以外的所有元素(即PMi(a,b),a≠b,i=1,…,m)均初始化為-10(不同于1,0,-1即可),對(duì)角線上的元素(即PMi(a,b),a=b,i=1,…,m)初始化為0;而當(dāng)有先驗(yàn)信息時(shí),先初始化所有偏好矩陣的對(duì)角線元素為0,再根據(jù)先驗(yàn)信息將對(duì)應(yīng)位置的元素設(shè)為1或-1,每個(gè)信息至少可設(shè)置2個(gè)元素,即PMi(a,b)和PMi(b,a),其余元素均初始化為-10.

4 實(shí) 驗(yàn)

在本節(jié)中,使用C++語(yǔ)言實(shí)現(xiàn)上述算法,所有實(shí)驗(yàn)均在Windows10操作系統(tǒng),Intel Core i7-8750處理器,主頻2.20GHz,內(nèi)存8GB的實(shí)驗(yàn)環(huán)境下進(jìn)行.本文通過(guò)使用合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集來(lái)驗(yàn)證算法的有效性:合成數(shù)據(jù)集的大小n為10k,非數(shù)值型屬性由既定詞典隨機(jī)生成,數(shù)值型屬性的值為區(qū)間[0,100]的隨機(jī)值.真實(shí)數(shù)據(jù)集采用Yelp(美國(guó)著名商戶(hù)點(diǎn)評(píng)網(wǎng)站)數(shù)據(jù)集中關(guān)于用戶(hù)的部分?jǐn)?shù)據(jù),并隨機(jī)選取其中10k條進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)中涉及的參數(shù)包括所有屬性(包含數(shù)值型和非數(shù)值型)的維度d,非數(shù)值型屬性的維度m,每一維非數(shù)值型屬性域的大小|Di|.表5為評(píng)估的主要參數(shù)及其變化范圍.

表5 實(shí)驗(yàn)參數(shù)Table 5 Experiment parameters

4.1 對(duì)比算法

為了驗(yàn)證算法MECR_QS的性能及其有效性,本文通過(guò)多組實(shí)驗(yàn)進(jìn)行測(cè)試,并通過(guò)改變交互過(guò)程中問(wèn)題的選擇策略,提出算法2的兩個(gè)變體,以及改造已有的針對(duì)數(shù)值型數(shù)據(jù)交互式遺憾最小化查詢(xún)方法作為對(duì)比算法.5種對(duì)比算法各自的特點(diǎn)如下:

3)效用超平面隨機(jī)算法(Utility Hyperplanes-Random,UH-Random[3])在每輪交互中,向用戶(hù)展示的兩個(gè)元組是隨機(jī)選擇的.

4)效用超平面單純形算法(Utility Hyperplanes-Simplex,UH-Simplex[3])在每輪交互中,向用戶(hù)展示的兩個(gè)元組借助單純形法(Simplex)[25]進(jìn)行選擇.其中,由于算法UH-Random和算法UH-Simplex針對(duì)僅具有數(shù)值型屬性的數(shù)據(jù)集進(jìn)行查詢(xún),所以實(shí)驗(yàn)中先通過(guò)交互的方式確定用戶(hù)對(duì)數(shù)據(jù)集中所有非數(shù)值型屬性的偏好,按照其喜好程度,將所有非數(shù)值型屬性值轉(zhuǎn)換為數(shù)值型,再作為算法UH-Random和算法UH-Simplex的輸入進(jìn)行查詢(xún).

4.2 實(shí)驗(yàn)結(jié)果

為了分析與驗(yàn)證數(shù)據(jù)集中數(shù)值型屬性和非數(shù)值型屬性的維度以及屬性域大小對(duì)算法性能的影響,實(shí)驗(yàn)使用交互輪次評(píng)估上述5種算法解決交互式遺憾最小化查詢(xún)問(wèn)題的性能.注意算法UH-Random和算法UH-Simplex的交互輪次包括轉(zhuǎn)換非數(shù)值型屬性前學(xué)習(xí)偏好的輪次,以及轉(zhuǎn)換后進(jìn)行遺憾最小化查詢(xún)的輪次.

4.2.1 合成數(shù)據(jù)集

圖1給出非數(shù)值型屬性域的大小|Di|對(duì)交互輪次的影響,圖1(a)、圖1(b)和圖1(c)是3種非數(shù)值型屬性維度m不同的情況,m分別為3、4、5,而3種情況下的總屬性維度d均為5,即數(shù)值型屬性維度分別為2、1、0.可以看到隨著非數(shù)值型屬性域大小|Di|的增大,5種算法的交互輪次都在增多,這是因?yàn)閨Di|表示數(shù)據(jù)(元組)在每一維屬性上可能取到的值,|Di|的增大意味著屬性可取的值增多,那么用戶(hù)可能的偏好就會(huì)大大增多,且其增長(zhǎng)速度遠(yuǎn)大于|Di|的增長(zhǎng)速度,所以需要更多信息以確定用戶(hù)的偏好.算法MP_QS和算法MECR_QS的交互輪次接近,且明顯優(yōu)于其它算法,因?yàn)槎呔菑目s小候選集的角度出發(fā):算法MECR_QS有效利用了期望候選集縮減,每次都選擇能使得預(yù)期候選集最小的問(wèn)題提問(wèn),可以達(dá)到迅速縮減候選集的目的;而算法MP_QS每次選擇相應(yīng)屬性值占比最高的問(wèn)題進(jìn)行提問(wèn),一輪交互結(jié)束后有可能刪減大量元組,快速縮小候選集.

圖1 非數(shù)值型屬性域的大小|Di|對(duì)交互輪次的影響Fig.1 Effect of the size of domains for attributes |Di| to iterations

圖2給出屬性維度d對(duì)交互輪次的影響,圖2(a)、圖2(b)和圖2(c)是3種數(shù)值型屬性維度d-m不同的情況,分別為2、1、0,而非數(shù)值型屬性域的大小不變(|Di|=4),即通過(guò)改變非數(shù)值型屬性的維度m而達(dá)到改變d的目的.可以看出隨著屬性維度d的增大(非數(shù)值型屬性維度m的增大),5種算法的交互輪次均增多,同非數(shù)值型屬性域大小|Di|增大時(shí)的本質(zhì)原因一樣,屬性維度d的增大使得用戶(hù)可能的偏好增多,需要更多的交互信息來(lái)確定用戶(hù)的真實(shí)偏好,從而篩選候選集.而算法MP_QS和算法MECR_QS的交互輪次比較接近,且優(yōu)于其它算法,這依然得益于從縮小候選集角度出發(fā)的思想.此外,還可以通過(guò)橫向?qū)Ρ葓D2(a)、圖2(b)和圖2(c),觀察僅改變數(shù)值型屬性的維度d-m和非數(shù)值型屬性的維度m,而不改變總屬性維度d的情況下對(duì)交互輪次的影響.以d=5為例,當(dāng)非數(shù)值型屬性的維度m從3增大至5時(shí),5種算法的交互輪次在緩慢增加,這是因?yàn)橄噍^于數(shù)值型屬性,非數(shù)值型屬性不存在客觀的順序.對(duì)于數(shù)值型屬性,只需得知用戶(hù)對(duì)其的偏好是“越大越好”還是“越小越好”,即可分辨元組的好壞,而對(duì)于非數(shù)值型屬性,需要向用戶(hù)提問(wèn)更多的問(wèn)題,一一確定其對(duì)不同屬性值的偏好,從而進(jìn)行遺憾最小化查詢(xún).

圖2 屬性維度d對(duì)交互輪次的影響Fig.2 Effect of the dimensionality d to iterations

4.2.2 真實(shí)數(shù)據(jù)集

本文從真實(shí)數(shù)據(jù)集Yelp中隨機(jī)選擇10k條數(shù)據(jù),并篩選出有效數(shù)據(jù)9696條進(jìn)行實(shí)驗(yàn).

類(lèi)似于圖2,圖3給出屬性維度d對(duì)交互輪次的影響,同樣地,通過(guò)改變非數(shù)值型屬性的維度m而達(dá)到改變d的目的.與在合成數(shù)據(jù)集上的結(jié)果相同,可以看出隨著d的增大,交互輪次逐漸增多,而算法MP_QS和算法MECR_QS所需交互輪次較少,明顯優(yōu)于其它算法.

圖3 屬性維度d對(duì)交互輪次的影響Fig.3 Effect of the dimensionality d to iterations

此外,本文還對(duì)交互輪次對(duì)候選集大小的影響進(jìn)行觀察,如圖4所示.當(dāng)交互輪次為0時(shí),即還未開(kāi)始進(jìn)行交互,候選集大小為3491個(gè),這是對(duì)9696條數(shù)據(jù)進(jìn)行skyline刪減的結(jié)果.可以看到當(dāng)進(jìn)行5輪交互后,算法MP_QS、算法MECR_QS以及算法R_QS迅速縮減了候選集,而算法UH-Random和算法UH-Simplex需要大約15輪才能縮減到同樣大小,這是因?yàn)樗惴║H-Random和算法UH-Simplex是針對(duì)僅具有數(shù)值型屬性數(shù)據(jù)的遺憾最小化查詢(xún)方法,無(wú)法直接對(duì)包含非數(shù)值型屬性的數(shù)據(jù)進(jìn)行查詢(xún),所以需要先確定用戶(hù)對(duì)非數(shù)值型屬性的偏好,將其轉(zhuǎn)化為數(shù)值型后,才能進(jìn)行查詢(xún).

圖4 交互輪次對(duì)候選集大小的影響Fig.4 Effect of the iterations to candidate set size

5 結(jié) 語(yǔ)

本文針對(duì)包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)問(wèn)題進(jìn)行了深入的研究.通過(guò)對(duì)既有數(shù)值型屬性、又有非數(shù)值型屬性的數(shù)據(jù)以及集合的遺憾率進(jìn)行定義,提出了更為一般化的交互式遺憾最小化查詢(xún)問(wèn)題.為了解決該問(wèn)題,提出了用于預(yù)處理的skyline刪減算法,并利用偏好矩陣提出了算法MECR_QS;最后,在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了驗(yàn)證,實(shí)驗(yàn)結(jié)果表明本文提出的算法能有效解決針對(duì)包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)問(wèn)題,且比現(xiàn)有算法(UH-Random和UH-Simplex)更有效.

未來(lái)的研究工作將考慮面臨用戶(hù)的反饋不符合其真實(shí)偏好(即用戶(hù)在交互過(guò)程中誤操作導(dǎo)致回答有誤)時(shí),如何將問(wèn)題轉(zhuǎn)化為多目標(biāo)優(yōu)化,進(jìn)一步轉(zhuǎn)化為單目標(biāo)優(yōu)化,以有效解決包含非數(shù)值型屬性的交互式遺憾最小化查詢(xún)問(wèn)題.以及如何結(jié)合機(jī)器學(xué)習(xí),更高效準(zhǔn)確的學(xué)習(xí)用戶(hù)偏好進(jìn)行遺憾最小化查詢(xún),在減少用戶(hù)精力的同時(shí)降低遺憾率.