包含非數值型屬性的交互式遺憾最小化查詢

王美靜,鄭吉平,2

1(南京航空航天大學 計算機科學與技術學院,南京 211106)

2(南京大學 計算機軟件新技術國家重點實驗室,南京 210093)

0 引 言

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

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

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

從另一方面看,即使某些數據集中數據的屬性都是數值型的,如果用戶對某屬性的要求不是單調的“越大越好”或者“越小越好”,而是希望在某一個區間內,那么也可以將其看作是非數值型屬性的情況.比如在電影數據集中,電影具有時長這一屬性,比起時長為1小時和3小時的電影,用戶更喜歡時長為1～2小時的.在面對這種問題時,遺憾最小化查詢領域未有涉及.

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

1)針對存在非數值型屬性的數據,提出一種遺憾率的定義;并進而提出相應的交互式遺憾最小化查詢問題的定義.

2)借助偏好矩陣學習記錄用戶的偏好,提出一種用于解決包含非數值型屬性的交互式遺憾最小化查詢問題的算法MECR_QS.

3)采用合成數據集和真實數據集對算法MECR_QS進行對比實驗,驗證其有效性,實驗結果表明,算法MECR_QS能有效處理包含非數值型屬性的交互式遺憾最小化查詢問題.

本文結構如下:第1節簡要介紹遺憾最小化查詢以及交互式遺憾最小化查詢的相關工作;第2節詳細介紹包含非數值型屬性的交互式遺憾最小化查詢問題所涉及到的相關概念以及問題定義;第3節提出用于預處理的skyline刪減算法和用于解決交互式遺憾最小化的算法MECR_QS;第4節通過與幾個算法的變體以及現有算法對比,對算法MECR_QS進行實驗評估驗證;第5節對本文工作進行總結.

1 相關工作

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

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

此外,還有一些其它的方法[11-15]同樣通過交互來學習用戶的偏好.Mindolin等人[13]通過讓用戶將展示的元組分為“喜歡”和“不喜歡”兩組,來探索用戶對不同屬性之間的偏好權重關系.Lee等人[14]將用戶偏好建模為嚴格的部分屬性排序來進行個性化skyline查詢.Jamieson等人[15]希望通過交互給數據集中所有元組排序,Qian等人[16]希望通過交互學習用戶的所有隱式偏好,這都會導致他們向用戶提問更多的問題,而其中有些問題可能是不必要的,因為他們不是利用學習到的偏好找用戶最喜歡的元組.Wang等人[17]的交互方法同文獻[15]和文獻[16]一樣,每個問題都是讓用戶從展示的兩個元組中選擇一個更喜歡的,以此來學習用戶的偏好,以較少的用戶精力找到用戶top-k之一的元組.

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

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

2 問題分析及定義

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

表1 相關符號及描述Table 1 Symbols and descriptions

定義1.(支配)給定兩個元組p,q∈V,當且僅當?Di∈D:piq且?Dj∈D:p?jq時,稱元組p支配元組q,即元組p在所有維度都不差于元組q,且在某一維度(如j)優于元組q.

對于數值型屬性,可以直接通過數值的大小來判斷屬性值的優劣程度;而對于非數值型屬性,由于屬性值之間不存在客觀的順序,需要根據用戶的偏好決定其優劣,所以在判斷兩個元組間的支配關系時,需要關注用戶對非數值型屬性的偏好.

如表2所示,題材和上映年份是電影的兩個非數值型屬性,評分(滿分是10)和票房是兩個數值型屬性.顯然,評分高,票房高的電影更優.根據定義1,可以看出v4支配v3,因為在題材和上映年份這兩個屬性上二者相等,即v4不差于v3,而在評分和票房兩個屬性上v4優于v3.由于事先并不知道用戶對于“恐怖”“懸疑”“科幻”以及“2013”“2015”之間的偏好關系,無法判斷哪個屬性值更優,所以無法判斷其它電影之間的支配關系.如v1和v3之間,盡管它們在評分和票房兩個屬性上有明顯的支配關系(v3更優),但它們在題材屬性上的不同,使得這一關系并不一定成立,當用戶更喜歡“恐怖”而非“懸疑”時,v3就無法支配v1.

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

此外,支配本身還具有以下性質:

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

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

定義2.(Skyline)當且僅當元組p在屬性集A上不被任何元組支配時,稱p是A上的一個skyline元組.給定數據集V,其skyline是所有skyline元組的集合.

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

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

(1)

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

(2)

其中,Ai是元組p∈S對應的屬性.顯然,0≤rrp≤1,0≤rrS≤1.

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

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

(3)

用于在交互過程中選擇向用戶提出問題的策略.

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

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

比如表2中“題材”屬性所對應的偏好矩陣PM1如表3所示,假設已知用戶相比“恐怖”,更喜歡“懸疑”,即“懸疑?恐怖”,那么PM1(2,1)=1,且PM1(1,2)=-1.在初始化偏好矩陣時,對角線元素就全為0,因為每個屬性值和自己相比,用戶對其的喜愛程度一定相同,如表3矩陣PM1中:PM1(1,1)=0,PM1(2,2)=0,PM1(3,3)=0.而暫時未知用戶關于“恐怖”“科幻”間以及“懸疑”“科幻”間的偏好關系,所以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的基礎上,通過一次交互得知用戶相比“恐怖”,更喜歡“科幻”,即“恐怖?科幻”,那么可更新偏好矩陣PM1(1,3)=1和PM1(3,1)=-1.而根據“懸疑?恐怖”和定義1中支配的傳遞性可知“懸疑?科幻”(“懸疑?恐怖?科幻”),所以可繼續更新偏好矩陣PM1(2,3)=1和PM1(3,2)=-1.最終更新后的偏好矩陣PM1如表4所示.

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

問題定義.(交互式遺憾最小化查詢)給定數據集V,屬性維度為d,非數值型屬性的維度為m(數值型屬性的維度為d-m),目標是通過交互,以盡可能少的代價(盡可能少的交互輪次)找到一個小的子集S,該子集的遺憾率最小,即:

(4)

簡單來說,如果依次向用戶提問,構成的問題集合為Q1,Q2,…,Qh,其中Q1?Q2?…?Qh,h為最終的交互次數,得到縮減的數據集合V1,V2,…,Vh,其中V1?V2?…?Vh,并最終知道用戶所有的偏好信息,可達到準確推薦的目的(遺憾率為0),成功推薦出用戶最滿意的元組,或者達到用戶滿意的遺憾率.本文的目標是通過提問盡可能少的問題,達到用戶的要求,進而提出算法MECR_QS.

3 算 法

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

為了提高遺憾最小化查詢的效率,首先對數據集進行預處理,即對于非數值型屬性一樣的數據,根據其數值型屬性進行skyline刪減,相關引理及算法如下:

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

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

算法1.skyline刪減

輸入：按非數值型屬性分類的數據集V1,V2,…,Vl

輸出：skyline刪減后的數據集V1′,V2′,…,Vl′

1.foreachVi,i∈1,…,l

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

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

4.foreachp∈Vi

5.ifp被任意一個q∈L支配

6. continue;

7.else//L中沒有可以支配p的

8.L←L∪{p};

9.endfor

10.Vi′←L;

11.endfor

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

與已有方法[20]不同,算法1對每個類內部作處理,可以省去不同類之間數據的比較.原因是不同類之間數據的非數值型屬性必然是不相同的,根據引理1可知無法判斷他們之間的支配關系,所以無需比較,由此提高了預處理效率.

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

算法2.MECR_QS

輸入：預處理過的數據集V1′,V2′,…,Vl′,問題集合Q,偏好矩陣PM1,PM2,…,PMm

輸出：候選集C

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

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

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

7. 根據用戶回答更新PMi和C;

8.endwhile

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

4 實 驗

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

表5 實驗參數Table 5 Experiment parameters

4.1 對比算法

為了驗證算法MECR_QS的性能及其有效性,本文通過多組實驗進行測試,并通過改變交互過程中問題的選擇策略,提出算法2的兩個變體,以及改造已有的針對數值型數據交互式遺憾最小化查詢方法作為對比算法.5種對比算法各自的特點如下:

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

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

4.2 實驗結果

為了分析與驗證數據集中數值型屬性和非數值型屬性的維度以及屬性域大小對算法性能的影響,實驗使用交互輪次評估上述5種算法解決交互式遺憾最小化查詢問題的性能.注意算法UH-Random和算法UH-Simplex的交互輪次包括轉換非數值型屬性前學習偏好的輪次,以及轉換后進行遺憾最小化查詢的輪次.

4.2.1 合成數據集

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

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

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

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

4.2.2 真實數據集

本文從真實數據集Yelp中隨機選擇10k條數據,并篩選出有效數據9696條進行實驗.

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

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

此外,本文還對交互輪次對候選集大小的影響進行觀察,如圖4所示.當交互輪次為0時,即還未開始進行交互,候選集大小為3491個,這是對9696條數據進行skyline刪減的結果.可以看到當進行5輪交互后,算法MP_QS、算法MECR_QS以及算法R_QS迅速縮減了候選集,而算法UH-Random和算法UH-Simplex需要大約15輪才能縮減到同樣大小,這是因為算法UH-Random和算法UH-Simplex是針對僅具有數值型屬性數據的遺憾最小化查詢方法,無法直接對包含非數值型屬性的數據進行查詢,所以需要先確定用戶對非數值型屬性的偏好,將其轉化為數值型后,才能進行查詢.

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

5 結 語

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

未來的研究工作將考慮面臨用戶的反饋不符合其真實偏好(即用戶在交互過程中誤操作導致回答有誤)時,如何將問題轉化為多目標優化,進一步轉化為單目標優化,以有效解決包含非數值型屬性的交互式遺憾最小化查詢問題.以及如何結合機器學習,更高效準確的學習用戶偏好進行遺憾最小化查詢,在減少用戶精力的同時降低遺憾率.