基于用戶分組的多用戶偏好查詢

王沁雪,江國華,秦小麟

(南京航空航天大學 計算機科學與技術學院,南京 210016) E-mail:nuaawqx@163.com

1 引 言

隨著基于位置的服務(LBS)、移動互聯網等技術的迅速發展,人們的生活越來越呈現出群體性、交互性和協作性的特點.越來越多的用戶更青睞于同具有共同偏好的其他用戶共享資源,在滿足自身需求的前提下,提升使用資源的性價比,例如用戶會選擇拼車或拼團旅行以降低行程花銷.與直接向每個用戶提供查詢結果相比,先對用戶分組,再對每個分組提供查詢結果具有如下兩方面的優點:一是對于查詢用戶,將用戶同與其相似或是滿足其偏好的用戶劃分為一組,由于提前考慮到了其他用戶會對該用戶滿意度產生影響,從而最終會使用戶體驗提升,同時分組會使查詢效率提高;二是對于被查詢對象,在同一時間為具有相似的屬性或偏好的多個用戶提供服務,可以提高服務的有效性及高效性.

例如,系統中有多位用戶發起拼車請求,若采用傳統的查詢方法需要將每位用戶的查詢都執行一次,且用戶最終可能與任何人成為拼車伙伴.提前分組則會對用戶最終的拼車同伴進行篩選,從而提高了用戶體驗,且以組為單位進行查詢也提高了查詢效率.因此,在類似查詢情境下,首先對用戶進行分組是十分必要且有意義的.整個查詢可分兩步實現,即首先對查詢用戶進行分組,再以每組為單位進行查詢.

如何將用戶進行分組是處理以上問題關鍵的一步,合理地分組可以在很大程度上提升用戶體驗以及查詢結果集質量,目前已有很多建立在用戶分組之上的研究,如組查詢、組推薦等[1-3,12].在這些研究中,對用戶分組的依據往往是某些用戶具有類似的查詢任務、相同的偏好或是相同的屬性,它們多是以提高最終的查詢結果質量為目的來進行分組.然而在一些實際問題中,應用上述分組方法存在一定缺陷.比如在拼車、拼團旅行中,用戶需要與同組成員進行協作與交流,而并不是簡單地利用對方得到一個查詢結果.用戶在被分組后將會一起行動,他們所在意的內容不僅僅是他們這項活動的目的以及通過結成分組能否從中受益,也會關注同組的伙伴是否令自己滿意.因此在建立分組的過程中,除了要考慮用戶對于查詢對象的偏好,也要考慮用戶與同組伙伴對于相互間的偏好.

考慮這樣一個場景:系統中多個用戶發起拼車請求,系統對用戶發起的查詢進行分析并將用戶分組,分組后為每組派發出租車.在分組的過程中需要考慮每組用戶的起點與終點是否接近,以及他們對出租車偏好是否相同,比如距離相近的幾位用戶都希望坐無煙的出租車,則將他們分為一組并為其分配無煙車.同時,為了使行程舒適,各個乘客也應該對彼此感到滿意.

很多已有的分組算法僅考慮將屬性相同的用戶分為一組[8,9],但顯然不能滿足該場景的需求.如A、B兩個用戶都是吸煙的男性,若在分組中只考慮用戶屬性是否相似,他們會因為屬性相似而被分為一組.但是,如果A、B兩人都希望與不吸煙的女性組成一組,他們都會違背對方對于同組用戶的偏好要求,從而導致用戶體驗較差.也有算法通過衡量用戶間查詢偏好的差異來對用戶進行劃分[6,7,10],將偏好相似度高的成員放在一個組內,但同樣無法滿足該場景的分組要求:A、B這兩位用戶對同乘用戶的偏好都是女性、不吸煙,兩人偏好一致因此被分到一組,然而他們本身的屬性卻違背了對方對于同組用戶的偏好要求.

圖1 多用戶分組查詢示意圖Fig.1 Diagram of multi-user group query

圖1給出了多用戶分組查詢流程的示意圖.上述問題可以概括為:對于某對象集合,系統中同時存在多個用戶的偏好查詢,在查詢過程中需要將用戶進行合理分組,每組用戶得到同樣的查詢結果.目前有關分組的解決方法并沒有考慮到組內成員之間的相互偏好.基于以上考慮,本文的工作主要針對多用戶如何在合理分組的基礎上進行偏好查詢,提出一種基于用戶分組的偏好查詢算法PQBG(Multi-users Preference Query Based on Grouping Algorithm),主要貢獻如下:

1)研究多用戶查詢系統中組查詢的問題,分析在查詢前對用戶進行分組的優勢,提出傳統對用戶進行分組的方法在應用于該問題上的不足,即未考慮組內用戶對相互間偏好的因素,并分析其對查詢結果的影響.

2)給出分組標準,并提出了一種基于用戶分組的偏好查詢算法PQBG,該算法將查詢分為分組和查詢兩個階段,并在分組過程中加入了對組內用戶之間偏好需求的考慮.

3)將PQBG查詢算法與未將用戶進行分組的算法BKNN,以及兩個分組查詢算法GAA、GAPS進行對比,采用擴充后的真實數據集對算法性能進行評估.實驗結果表明,PQBG算法能提升解決多用戶偏好查詢問題時的結果質量.

2 相關工作

對用戶進行群組劃分常用于組查詢及組推薦系統中,但在大多數情況下是在假設群組劃分已經給定的情況下進行下一步[1-3],涉及到具體如何分組的研究較少,而多用戶偏好查詢過程中如何對用戶進行合理分組是本文的研究重點.分析已有研究查詢或推薦系統等工作中的群組劃分依據,可分為如下四類:

1)地理位置.利用地理位置或軌跡信息將用戶進行分組,最簡單的方法是將某一區域按照經緯度以一定的步長柵格化,將落在同一柵格內的用戶劃為一組.張潮等人在[4]中將具有相同軌跡信息的用戶劃分為一組,利用單個用戶作為代表群組中具有相似運動軌跡的用戶以降低位置更新次數.文獻[5]也研究了從軌跡信息中發現旅行同伴的問題,并提出了智能交集和閉合候選的策略以減少內存成本.

2)社交關系.在對社交網絡的研究中主要是利用用戶之間的社交關系對用戶進行分組[11].Yang D N等人將社交關系定量地表示為社交距離,利用社交距離與熟人約束,以從社交網絡中找到一個給定成員數目以及指定活動時間的分組[14].文獻[15]同時考慮社交距離與空間距離,提出查詢k-CoFQ,最終得到的用戶分組中的成員彼此之間存在緊密的社會關系,并且被限制在地理空間中的一個小區域.

3)用戶屬性.一些研究根據用戶的社會化屬性、人口統計學特征以及用戶本身的各種屬性(如年齡、職業等)對用戶進行分組.如Gu L等人在[8]中充分利用了用戶的社會信息,提出一種考慮潛在用戶分組信息的相似度度量方法,以計算用戶潛在的分組.文獻[9]中在分組時利用了人口統計學特征(如兒童、殘疾人等),將用戶劃分為需要特殊對待的不同組.

4)用戶偏好.這種分組方法常用在推薦算法中,利用用戶的偏好對用戶進行分類,群組的偏好相似度越高,生成的群組推薦結果集越令人滿意[7,13].如Boratto等人在[6]中通過計算用戶偏好相似度構建用戶相似度網絡,利用社區劃分算法對用戶相似度網絡進行劃分.[10]通過建立用戶對對象的評分矩陣并計算用戶之間的歐氏距離,對相同項目具有相似評分的用戶會被劃為一組.

通過總結得出,以往研究中對用戶分組的目的大多為了提高查詢結果質量,或是提高查詢效率,但均沒有考慮到分組中用戶之間存在交互與協作的情況.除了沒有考慮到用戶對于同組伙伴的偏好之外,大部分研究在分組過程中對組內人數也沒有限制,只要符合要求便劃作一個組,這在很多組內人數存在上限的情境中無法適用.本文提出PQBG算法解決上述問題.

3 基于用戶分組的多用戶偏好查詢算法

3.1 問題描述

多位用戶提出偏好查詢,其中偏好包含了對查詢對象的偏好和對其他查詢用戶的偏好.查詢算法分為分組和查詢兩個階段.在分組階段,算法解決如何將N個查詢用戶分為M組的問題,每組人數最多為v,這些組之間沒有交集.分組結果需要滿足三點:一是組內用戶屬性相似;二是組內用戶對查詢對象的偏好相似,三是同組中每位用戶對其它用戶的偏好都能得到滿足.在查詢階段,查詢對象的屬性與查詢用戶偏好屬性相似度越高,其越有可能出現在查詢結果中,最后每組查詢用戶得到評分最高的k個查詢對象.

以用戶拼車為例,每位用戶對于查詢對象出租車和拼車伙伴都存在偏好,如對出租車的偏好為信用評分在9分以上,司機為不吸煙的男性,對拼車伙伴的偏好為信用評分在8分以上,不吸煙的女性.系統分析用戶查詢,通過用戶的屬性及其偏好分組.PQBG算法主要應用于擁有基于位置服務的應用,因此其地理位置,即空間屬性是一個重要的影響因素.對于該類應用,在進行分組時,首先應保證可能成為一組的用戶地理位置相距不遠,因為即使其他偏好條件都完全符合,司機要跨越整個城市去接幾名乘客是不現實的.其次,同組成員對出租車的偏好應在最大程度上接近,比如都希望乘坐不吸煙的男司機開的車.最后,組內成員對相互間的偏好不能發生沖突,如用戶在找到他所希望的信用評分在8分以上,不吸煙的女性同伴時,他本身的屬性也需要滿足同伴對他的偏好要求.在分組結束后,計算每輛出租車相對于該組的評分,并為每組返回評分最高的k輛出租車.

3.2 基本定義

定義1.(對象集合)對象集合O={o1,o2,…,om}.oi={ID,pos,X1,X2,…,Xl},(i=1,2,…,m)代表一個對象.其中ID為主鍵表示元素ID,pos表示對象的空間屬性,若對象屬性集中不包含空間屬性,則其pos為空;Xt(t=1,2,…,l)表示對象的其他屬性,數據類型為浮點數.

定義2.(查詢集合)查詢集合G={u1,u2,…,un},ui=,(i=1,2,…,n)代表一個用戶查詢.其中ui.Attr={ID,pos,time,Y1,Y2,…,Yh}表示用戶屬性集,其中ID為主鍵表示用戶ID;pos表示用戶的空間屬性,若用戶屬性集中不包含空間屬性,則其pos為空;time表示用戶的時間屬性,指用戶發起查詢后所等待的時間;Yt(t=1,2,…,h)表示用戶的其他屬性,數據類型為浮點數.ui.Obj={P1,P2,…,Pl}表示用戶對查詢對象屬性{X1,X2,…,Xl}的偏好,Pi(i=1,2,…,l)為數值區間或布爾值,Ui表示Xi取值的全集,Pi=Ui表示對這一項屬性無偏好.ui.Par={Q1,Q2,…,Qh}表示用戶對其它查詢用戶屬性{Y1,Y2,…,Yh}的偏好,Qi(i=1,2,…,h)為數值區間或布爾值,Qi=Ui表示對這一項屬性無偏好.

定義3.(用戶分組)分組group={u1,u2,…,us|ui∈G,(i=1,2,…,s)},(s≤n),表示一組用戶的集合.

定義4.(運算符⊙)ui.Pt⊙uj.Pt表示用戶ui和用戶uj對查詢對象屬性Xt偏好Pt的偏好重合度,取值為[0,1].

若Pt為范圍偏好(如評分為[8,10]),則

(1)

若Pt為布爾值(如性別為女,設定性別為男用1表示, 性別為女用0表示),則

(2)

定義5.(偏好相似度)相似度函數sim(ui,uj)表示用戶ui和uj關于查詢對象的偏好相似程度,計算公式為:

(3)

定義6.(組偏好集合)在一個分組group={u1,u2,…,us}中,組偏好集合D={M1,M2,…,Mh},其中Mi=u1.Qi∩u2.Qi∩…∩us.Qi,i=1,2,…,h,即組內所有成員對群組其它元素偏好集合的交集.

定義7.(組屬性集合)在一個分組group={u1,u2,…,us}中,組屬性集合A={N1,N2,…,Nh},其中Ni=u1.Yi∪u2.Yi∪…∪us.Yi,i=1,2,…,h,即組內所有成員屬性值的并集.

定義8.(對象評分函數)S(ui,oj)表示用戶ui對對象oj的評分.當二者空間屬性存在時評分包含兩個方面,一是ui與oj的空間屬性相近,二是oj屬性與用戶ui對查詢對象屬性偏好的相似度高,使用λ來對兩者進行平衡,在本文中默認為0.5;若ui與oj不存在空間屬性則λ的值為1.具體表示為:

(4)

其中contain(ui.Pt,oj.Xt)表示oj的第t個屬性是否與ui對其的偏好范圍存在交集,若存在則函數值為1,若不存在則函數值為0.d(ui,oj)表示ui與oj的距離,dmax表示ui與查詢集合中對象的最遠距離.

以拼車場景下的用戶查詢以及車輛信息為例.表1為出租車屬性表,o=(1,189.791856,31.243058,7,9.1,1,0)代表一輛出租車,ID=1表示出租車ID為1,pos=(189.791856,31.243058)表示該車所在位置的經緯度.后四個數值分別表示出租車(New,Credit,Sex,Smoke)四個屬性的值.

表1 出租車屬性表Table 1 Attribute table of taxi

表2為用戶屬性表,表3為用戶偏好表,u1=<(1,188.791856,31.943058,188.797638,32.028402,9.5,1,0),([6,10],[9,10],U,{0}),([8,10],U,{0})>代表了一個查詢.其中,u1.Attr=<(1,188.791856,31.943058,188.797638,32.028402,9.5,1,0)表示用戶屬性集,該用戶ID為1,起點經緯度坐標為(188.791856,31.943058),終點經緯度坐標為(188.797638,32.028402),該用戶的其它屬性為信用值9.5,不吸煙的男性.u1.Obj=([6,10],[9,10],U,{0})表示用戶對查詢對象的偏好,他希望出租車在六成新以上,司機的信用評分高于九分且不吸煙,性別偏好為U表示該用戶對司機的性別沒有特殊要求.u1.Par=([8,10],U,{0})表示用戶對其他用戶的偏好,他希望和信用值大于8,且不吸煙的人成為拼車伙伴.

表2 用戶屬性表Table 2 Attribute table of user

若有另一位用戶發起查詢,u2=<(2,188.784487,31.945761,188.784214,32.028519,254,8.3,1,1),([9,10],[8,10],{0},{0}),([7,10],{0},{0})>.利用公式(3)可得出兩位用戶的偏好相似度為sim(u1,u2)=0.6875.若將兩位用戶劃為一組,則該組的組偏好集合為D={[7,10],{0},{0}},該組的屬性集合為A={{9.5,8.3},{1},{0,1}}.

表3 用戶偏好表Table 3 Preference table of user

3.3 PQBG算法

本節給出基于用戶分組的多用戶偏好查詢算法PQBG.查詢集合G={u1,u2,…,un}發起對對象集合O={o1,o2,…,om}的查詢,在查詢過程中利用PQBG算法對查詢信息進行分析,將查詢集合中的用戶分組,其中每組成員人數最多為v,并為每組返回按評分函數排序的前k個查詢對象.

PQBG算法輸入為系統中的查詢集合G、查詢對象集合O、每組人數上限v與結果個數k,輸出為最符合組偏好的top-k對象集合result.首先選取系統中最早發起查詢的用戶作為分組的起點用戶,計算該用戶與其它用戶的歐氏距離,并選取前K名用戶作為預選結果集.之后計算這K名用戶與起點用戶對查詢對象的偏好相似度,生成按偏好相似度降序排列的隊列L.接著為每組設定組偏好集合及組屬性集合,利用這兩個集合對隊列中的用戶進行篩選,從隊頭用戶起依次篩選,滿足條件的用戶可加入該分組;重復上一步,若每組達到人數上限v則停止;若遍歷K個用戶組內人數仍無法達到v,則認為沒有足夠多的用戶滿足小組要求,組內所有人數即為該組最后的總人數.最后利用該組的查詢偏好集合得到該組的查詢結果集合.PQBG算法執行一次結束后,重新計算系統中的查詢集合,利用該算法生成新的分組并為該組返回查詢結果.

算法1.PQBG算法

輸入:查詢集合G={u1,u2,…,un},查詢對象集合O={o1,o2,…,on},每組人數上限v,輸出結果個數k

輸出:最符合組查詢偏好的top-k對象集合result

1.while(G≠?)

2. startuser←earliestStart(G);

//將等待時間最久的用戶選作起點用戶

3. group.add(startuser);

4. G.delete(startuser);

5. get the KNNresults of G and keep them in preResult;

// 利用K近鄰查詢算法處理生成預選結果集

6. preList←DesSimilarity(startuser,preResult);

//依次計算起點用戶與預選組員的偏好相似度,將結果按降序排列

7. group←UserSelect(startuser,preList,v);//利用組偏好集合與組屬性集合篩選用戶生成分組

8. result←TopkPreQeury(group,O,k)//返回該組查詢結果集合

9.returnresult;

PQBG算法中主要的四個模塊分別為預選結果集生成(第1-5行),預選隊列生成(第6行),組員選擇(第7行)以及查詢結果生成(第8行).在3.3.1至3.3.4中詳細分析了這四個模塊.

例如在拼車場景中,PQBG算法首先選取起點用戶,計算他與系統中其他用戶的歐氏距離并取前K個用戶.之后分別計算這K個用戶與起點用戶對出租車的偏好相似度,用戶按偏好相似度降序排列.接著以起點用戶為中心建立分組,設定組偏好集合并將其初始化為起點用戶對其它用戶的偏好,設定組屬性集合并將其初始化為起點用戶的屬性.從隊首用戶起依次判斷每位用戶的屬性和偏好是否與小組已有成員相沖突,無沖突則加入該組并更新組偏好集合與組屬性集合.遍歷隊列,直至組中已有v名成員或遍歷完隊列中所有用戶.最后計算出租車相對于該組的評分,得到最優的k個查詢結果.

3.3.1 預選結果集生成

為提高組員選擇效率,節約系統開銷,設置組員預選步驟.利用K近鄰查找方法思想,計算用戶之間的歐氏距離,距離越近則二者越相似,越有可能被歸為一組.帶特征權參數的兩個n維向量的歐氏距離計算公式為:

(5)

在此前對各屬性值進行歸一化處理,m為查詢個數,將原始數據都歸化為[0,1]區間的數,運用公式:

i=1,2,…,m,l=1,2,…,n

(6)

為了提高查找效率,采用kd-tree作為索引.計算結束后選取距離最近的前K名用戶作為預選組員.

如在拼車場景下,查詢用戶都具有空間屬性,且該類屬性對于計算歐式距離起到了決定性作用.直觀上認為出發點與目的地都越接近的用戶越有可能成為同組伙伴;該組發起者是等待時間最長的用戶,同時也希望系統中等待時間久的用戶優先加入分組.因此考慮五個屬性參數:起始點經度、起始點緯度、終點經度、終點緯度、查詢等待時間.同時,在考慮兩個用戶是否相近時,其起始點與終點距離遠近的重要性遠大于其等待時間的長短,因此在該場景下公式(5)的默認權重為(0.24,0.24,0.24,0.24,0.04).若應用于查詢用戶不存在空間屬性的場景,預選結果集生成算法同樣適用,此時計算歐式距離只考慮時間屬性這一維屬性,其權重為1.

3.3.2 預選隊列生成

預選隊列通過計算預選結果集中成員與起點用戶對查詢對象的偏好相似度得到,偏好相似度定義及計算公式已在定義5中給出.生成預選隊列是為最終的組員確定做準備,該步驟對最終的組員確定順序進行排序,查詢對象偏好越相似的用戶越被優先考慮是否能成為同組成員.分別計算預選結果集中用戶與起點用戶對查詢對象的偏好相似度(第1-3行),在組內成員對相互間偏好不沖突的前提下,他們對查詢對象的偏好越相似越優,因此生成的隊列是由按用戶偏好相似度大小降序排列(第4-5行).

算法2.預選隊列生成算法DesSimilarity

輸入:起點用戶startuser,預選結果集preResult

輸出:按偏好相似度降序排列的隊列preList

1.foreach tupleuin preResultdo

2.u.sim=sim(startusers,u);//計算偏好相似度

3.endfor

4. preList←descendingOrder(preResult);

//將預選結果集按偏好相似度降序排列

5.returnpreList;

3.3.3 組員選擇

算法3.組員選擇算法UserSelect

輸入:起點用戶startuser,按偏好相似度降序排列的預選組員隊列preList,每組人數上限v

輸出:生成成員數最多為v的分組group

1. GroupPreSet.add(startuser.Par);

2. GroupAtrrSet.add(startuser.Atrr);

3. GroupNum=1;

4.foreach tupleuin preListdo

5.if(GroupNum

6. ConfGroupPreSet=U.complement(GroupPreSet);

//計算組沖突偏好集合

7. u.ConfPar=U.complement(u.Par);

//計算用戶的沖突偏好

8.if(conflict(u.Atrr,ConfGroupPreSet)=0)

&&(conflict(GroupAtrrSet,u.ConfPar)=0)

//判斷用戶與組成員之間是否沖突

9. Group.add(u);

10.G.delete(u);

11. GroupNum++;

12. GroupPreSet.add(u.Par);

13. GroupAtrrSet.add(u.Atrr);

14.endif

15.endif

16.endfor

17.returngroup;

組偏好集合與組屬性集合意在維護新用戶與組內已有用戶無沖突,這里沖突是指每名用戶的屬性是否滿足組內其它組員對用戶的偏好.初始化組偏好集合為起點用戶對其它用戶的偏好,組屬性集合為起點用戶的屬性(第1-3行),從預選組員隊列頭起依次判斷隊列中的用戶與這兩個集合的沖突情況(第4-5行).為了提高算法效率和減少比較次數,計算用戶偏好在其值域范圍的補集,為用戶的沖突偏好;計算組偏好集合在其值域范圍的補集,為組沖突偏好集合.此時,只要存在某一屬性維度的值與對其相應的沖突值域交集不為空,則表示存在沖突,該用戶不能加入分組.若組屬性集合與該用戶的沖突偏好不存在交集,且該用戶的屬性與組沖突偏好集合不存在交集,則將用戶加入該組的結果集,并將其從原始查詢集合中去除,目的是保證每個小組之間不存在交集(第7-11行).加入后更新該組的組偏好集合,為新用戶對其它用戶的偏好集合與原來組偏好的集合交集;更新該組的組屬性集合,為新用戶屬性與原來組屬性的集合并集,并返回生成的組(第12-17行).

3.3.4 查詢結果生成

在生成用戶分組的基礎上,給出最終的查詢結果生成算法.本文定義的研究對象與空間關鍵字查詢類似且查詢重點為分組算法,因此在查詢時借助空間關鍵字查詢中的BKNN算法[17,18],將整組視為一個查詢點,利用該組的查詢偏好集合及屬性集合得到該組的查詢結果集合.首先將整組成員的平均位置信息設為查詢點的位置信息(第1-4行),并將該組的組偏好集合設為查詢點的偏好信息(第5行),最后利用BKNN算法得出前k個查詢結果(第6-7行),這k個對象不僅滿足該組的查詢偏好且距離平均查詢點最近.

算法4.查詢結果生成算法TopkPreQeury

輸入:用戶分組group={u1,u2,…,us},查詢對象集合O={o1,o2,…,on},輸出結果個數k

輸出:最符合組查詢偏好的top-k對象集合result

1.forall tuples uiin groupdo

2. pos=AddPosition(ui.pos);

3.endfor

4. q.pos=Average(pos);//計算組成員平均位置

5. q.per=GroupPerSet;

6. result←BKNN(q,O,k);

7.returnresult;

4 實驗及分析

4.1 實驗環境

本章實驗驗證PQBG算法的有效性及查詢性能,與BKNN、GAA、GAPS三個算法進行對比.其中BKNN算法[18]不對用戶進行分組,針對單個用戶,直接利用對查詢對象的評分得出評分最高的k個查詢結果,假設得到相同top-1結果的用戶最終為同組成員,每組人數最多為v;GAA與GAPS算法是作為對比的Baseline算法,這兩個算法都對發起查詢的用戶進行分組,其中GAA算法僅選取與起點用戶歐氏距離最近的v-1名用戶作為同組成員;GAPS算法在預選隊列生成后,直接選取前v-1名用戶作為同組成員,而不考慮組內成員相互間的偏好情況.四個算法的比較如表4所示.實驗環境為:Inter(R)Core(TM)i3-2120 CPU@ 3.30GHz,4BG內存,Windows 7操作系統.所有算法均是采用C++語言實現,編譯器為Visual Studio 2013.

表4 PQBG算法與BKNN和Baseline算法的比較Table 4 Compare with PQBG,BKNN and Baseline

算法的有效性通過定義SATI值對用戶滿意度進行評估.在查詢結束后,設每組最終人數為s(s≤v),則組內每位的用戶ui的SATI值通過四個因素進行度量:與同組成員間平均屬性相似度、與同組成員間平均屬性及偏好相容度、組飽和度、查詢結果評分.分別用Ai、Fi、Ni、Si表示,它們的值域都為[0,1].定義如下:

Ai表示用戶ui與同組成員間的平均相似度,是該用戶與組內其余成員歐氏距離的平均值,計算公式為:

(7)

Fi表示與同組成員間平均屬性及偏好相容度,計算公式如公式(8).其中contain(ui.Qt,uj.Yt)表示用戶uj的第t個屬性是否與ui對其的偏好范圍存在交集,若存在則函數值為1,若不存在函數值為0.

(8)

Ni為組飽和度,為組內最終人數與組人數上限的比值.Si為用戶查詢結果評分,其計算方法如公式(4)所示.

由以上四個參數得到用戶SATI值計算公式:

SATI=α.Ai+β.Fi+γ.Ni+εSi

(9)

H名查詢用戶的平均SATI值ASATI為:

(10)

α、β、γ、ε表示這四個度量因素在最終的用戶滿意度評分中所占的權重,默認值都設定為0.25.SATI值域為[0,1],其值越大,表示該用戶對查詢及分組結果的滿意度越高.ASATI值越高,表示用戶的平均滿意度越高.

實驗數據采用NYC′s Taxi and Limousine Commission網站公布的TLC Trip Record Data數據集.該數據集收集了紐約市2009到2016年的出租車行車信息,每條包含出租車出租等級、執照號、起點經緯度、終點經緯度等19項信息,從中提取2016年11月中的10571輛出租車信息作為實驗的數據.由于該數據集中并不包含出租車的其他屬性信息,如司機性別、吸煙與否等,實驗通過隨機采樣生成的方法對原數據集進行了擴充,隨機生成了出租車的其它屬性信息.同時,在此基礎上模擬生成了用戶數據集,該數據集內每行信息包含了用戶起點與終點的經緯度,并補充了用戶的其它屬性信息以及偏好信息.

圖2 查詢對象規模對算法性能的影響Fig.2 Performances with query object size

實驗的主要目的是,將考慮組內成員存在偏好的分組查詢算法PQBG與不考慮對組內成員存在偏好的分組查詢算法GAA、GAPS,以及不對用戶分組的普通查詢算法BKNN進行比較,從而證明對用戶進行分組,以及在分組的過程中加入對組內成員偏好考慮的重要性.第一組實驗對分組查詢算法(PQBG、GAA、GAPS)與不對用戶進行分組的查詢算法BKNN的查詢性能進行對比;后三組實驗對三個分組查詢算法(PQBG、GAA、GAPS)的查詢性能進行對比.實驗結果均是算法執行1000次的平均性能.

4.2 結果分析

4.2.1 查詢對象規模對算法性能的影響

為了分析查詢對象規模對算法性能的影響,實驗在查詢對象個數從2K到10K下進行實驗.系統中查詢用戶個數為3K,分組查詢算法中組規模大小為4,K值取30,計算系統中所有用戶查詢完畢后的查詢時間與用戶平均滿意度ASATI.

圖2顯示了查詢對象規模對算法的執行時間與ASATI值的影響.在查詢規模較小時,分組代價相對較高,因此BKNN的查詢執行時間相對較低.隨著查詢對象規模的增大,查詢耗時逐漸高于分組耗時,因此BKNN的查詢時間增長速度高于三個分組查詢算法,最終所需查詢時間高于分組查詢算法.即隨著查詢對象規模的增長,以整組為單位進行查詢,代價將低于每個用戶單獨進行查詢.而在ASATI值方面,由于BKNN算法未曾考慮用戶屬性及偏好,其Ai、Fi值遠小于三個分組查詢算法,因此ASATI值始終最小,且由于組飽和度下降,總體呈下降趨勢.而三個分組查詢算法隨著查詢對象規模增大,Si有所提升,ASATI呈緩慢上升趨勢.

4.2.2 K值對分組查詢算法性能的影響

從上節實驗中發現,分組查詢性能總體上要優于普通查詢,因此后三節針僅對三個分組查詢算法(PQBG、GAA、GAPS)進行性能比較,查詢對象為整個數據集.由于在實際情況中,系統中的查詢用戶規模以及查詢對象規模在不斷變化,因此三個實驗考察在某一時刻算法生成一個新的分組并得出該組查詢結果的性能.

圖3 K值對算法性能的影響Fig.3 Performances with different K

圖3顯示了在查詢用戶數為3K,組規模為4時,K的取值對分組查詢算法的執行時間與ASATI值的影響.隨著K值的增大,算法的執行時間都隨之增大,其中GAPS算法由于存在計算用戶的偏好相似度與生成預選隊列的過程,執行時間要大于GAA算法.而PQBG算法在GAPS算法的基于組內偏好對組員進行篩選處理,因此執行時間最長.就ASATI值而言,GAA算法始終最低,因為GAA算法的Si值明顯低于其它算法.值得注意的是,在K很小時其余兩者的ASATI值接近甚至GAPS算法的ASATI值更高,這是由于當K值很小時,雖然采用GAPS算法建立的分組同組用戶間屬性及偏好相容度Fi較低,但采用PQBG算法的組飽和度Ni也很低造成的.隨著K值的增大,采用PQBG算法的組飽和度增大,而采用GAA算法和GAPS算法建立的分組中同組用戶間屬性及偏好相容程度基本沒有增長,因此PQBG算法的ASATI值將高于另兩個算法.

4.2.3 組規模對分組查詢算法性能的影響

為了分析查詢組規模不同對分組查詢算法性能的影響,分析K取值為30且查詢用戶數為3K,組規模增大時,算法的執行時間與ASATI值,實驗結果如圖4所示.

圖4 組規模對算法性能的影響Fig.4 Performances with different group size

組規模的大小對于算法執行時間幾乎沒有影響,這是由于算法中組員選擇的步驟對于整個算法的時間復雜度的影響可以忽略不計.GAPS與PQBG算法的執行時間會有略微提升,而GAA算法與組規模大小無關,因此執行時間基本保持不變.三個算法的ASATI值都會下降,這是由于隨著組內成員的增多,同組用戶屬性相似度以及查詢結果評分都會下降導致的.同時,對于GAA和GAPS算法,雖然組成員數可以一直達到飽和,但隨著組內成員數的增多,同組用戶間屬性及偏好相容度下降加快.而PQBG算法隨著組規模的增大,ASATI值的下降幅度由最初的較小突然變大,這是由于當組規模達到一定程度后,由于無法找到足夠的組員,組飽和度的下降將導致的.

4.2.4 查詢用戶規模對分組查詢算法性能的影響

圖5 查詢用戶規模對算法性能的影響Fig.5 Performances with user size

5 結束語

文本從實際應用需求出發,研究基于用戶分組的多用戶偏好查詢算法.在查詢前對基于用戶偏好對用戶進行分組可提高用戶滿意度,如何對用戶進行合理分組是解決該問題的關鍵,現有的分組查詢算法在解決多用戶偏好查詢時,未考慮用戶對組內成員之間的偏好對分組結果影響.基于此,本文提出一種考慮組內成員相互間偏好的分組查詢算法PQBG.實驗結果表明,PQBG算法能提升多用戶偏好查詢的查詢性能.