基于屬性優(yōu)先關(guān)系的多用戶Skyline查詢處理算法

邵路伊，王沁雪，郭 帥

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

0 引 言

Skyline查詢作為一種新的數(shù)據(jù)庫操作符在2001年被提出[1]，從此，它得到了研究者的廣泛關(guān)注。Skyline查詢?yōu)槎嗄繕?biāo)決策、數(shù)據(jù)挖掘等問題提供了解決途徑，有助于人們更好地做出決策。然而，隨著數(shù)據(jù)集的增大以及數(shù)據(jù)維度的增加，Skyline查詢返回的結(jié)果集仍舊很大，對(duì)用戶的參考意義不大。同時(shí)，在現(xiàn)實(shí)生活中，真實(shí)數(shù)據(jù)集的各個(gè)屬性的相對(duì)重要程度可能不同。例如一套房子的屬性有面積、價(jià)格、所在學(xué)區(qū)、交通便利性和綠化環(huán)境等，當(dāng)用戶選擇購買房子時(shí)，可能會(huì)最看重所在學(xué)區(qū)的排名，然后再對(duì)比價(jià)格和面積，而對(duì)綠化環(huán)境等其他因素沒有要求，因此房子所在學(xué)區(qū)這一屬性比其他屬性對(duì)于用戶的決策更有決定性作用，即它的優(yōu)先等級(jí)更高。因此，數(shù)據(jù)集屬性之間的優(yōu)先關(guān)系能更具體地體現(xiàn)用戶的偏好。

針對(duì)上述問題，研究者對(duì)偏好Skyline查詢展開研究，關(guān)注數(shù)據(jù)集屬性之間的相對(duì)重要性[2]。研究者們提出一些新的支配關(guān)系和算法[3-7]，根據(jù)屬性優(yōu)先關(guān)系改變數(shù)據(jù)點(diǎn)之間的支配關(guān)系，使Skyline結(jié)果集的規(guī)模發(fā)生變化，同時(shí)使查詢結(jié)果更符合用戶提出的偏好需求。目前已有的偏好Skyline查詢均是在單用戶場(chǎng)景下研究的，而在實(shí)際應(yīng)用中，往往需要考慮多用戶參與的情況。

表1 房子數(shù)據(jù)集信息示例

房子面積/m2價(jià)格/萬所在學(xué)區(qū)交通便利綠化環(huán)境H1180700887H22050474H380800968H4120600799H5130670786

例1一個(gè)家庭共同考慮購買一套房子，房子的數(shù)據(jù)信息如表1所示。其中，所在學(xué)區(qū)、交通便利和綠化環(huán)境這3個(gè)屬性以數(shù)值評(píng)分的形式展示，數(shù)值越大表示越好。家庭成員A、B、C分別根據(jù)自身的偏好提出了不同的查詢要求，并給出了自認(rèn)為最重要的屬性：

用戶A：查詢面積大、價(jià)格低，同時(shí)附近交通便利的房子，價(jià)格優(yōu)先考慮。

用戶B：查詢價(jià)格低且所在學(xué)區(qū)好的房子，所在學(xué)區(qū)優(yōu)先考慮。

用戶C：查詢面積大、所在學(xué)區(qū)好同時(shí)附近交通便利的房子，所在學(xué)區(qū)優(yōu)先考慮。

從例1可見，每個(gè)用戶都對(duì)數(shù)據(jù)集均提出不同的偏好查詢要求，且每個(gè)用戶對(duì)屬性之間的相對(duì)重要性的定義也不同，用戶A認(rèn)為價(jià)格屬性是最重要的，而用戶B和用戶C認(rèn)為所在學(xué)區(qū)是最重要的。此時(shí)，當(dāng)查詢主體的數(shù)量從單個(gè)向多個(gè)擴(kuò)展時(shí)，傳統(tǒng)偏好Skyline算法會(huì)存在以下局限性：

1)偏好Skyline查詢需要確定屬性之間的重要相關(guān)性，由于不同用戶對(duì)不同屬性的重視程度不同，缺乏將多用戶的偏好統(tǒng)一成一組屬性重要相關(guān)性的處理方法。

2)若分別對(duì)每個(gè)用戶采用傳統(tǒng)的偏好Skyline查詢處理，則無法對(duì)子結(jié)果集進(jìn)行有效的處理，特別是屬性之間沖突性較大的情況。

3)傳統(tǒng)算法缺乏多用戶環(huán)境下的交互性，無法最大程度地滿足各個(gè)用戶的需求。

經(jīng)過對(duì)現(xiàn)實(shí)生活中應(yīng)用場(chǎng)景的分析，以及對(duì)現(xiàn)有偏好Skyline查詢算法的分析，本文提出一種支持多用戶偏好查詢的MUPS算法，有效解決多用戶場(chǎng)景中屬性重要程度不同的偏好查詢，主要貢獻(xiàn)如下：

1)提出屬性偏好鏈的概念，并用屬性權(quán)重表示屬性的相對(duì)重要性，基于此提出一種新的σ-支配方式，來對(duì)結(jié)果集進(jìn)行剪枝。

2)提出一種基于屬性優(yōu)先關(guān)系的多用戶偏好Skyline查詢算法——MUPS算法，查詢過程中通過用戶群與返回候選集的交互，動(dòng)態(tài)修正屬性偏好鏈上各屬性的權(quán)重大小，使得最終結(jié)果更符合用戶群的真實(shí)偏好需求。

3)同時(shí)采用人造數(shù)據(jù)和真實(shí)數(shù)據(jù)對(duì)算法性能進(jìn)行評(píng)估，實(shí)驗(yàn)結(jié)果證明，MUPS算法能有效解決多用戶偏好Skyline查詢問題。

1 相關(guān)工作

研究者對(duì)傳統(tǒng)的Skyline查詢展開了大量的研究，傳統(tǒng)Skyline查詢的基本概念和定義為：

定義1支配。給定一個(gè)d維數(shù)據(jù)集S，D為d個(gè)維度的集合，即D={a1,a2,…,ad}，ai(1id)表示數(shù)據(jù)集的第i個(gè)維度。對(duì)于數(shù)據(jù)集S中的任意2個(gè)數(shù)據(jù)點(diǎn)p和q，p.ai和q.ai分別表示2點(diǎn)在任意維度ai上的屬性值，稱p支配q，記為pq，當(dāng)且僅當(dāng)：

1)?ai∈D，p(ai)q(ai)；

2)?aj∈D，p(aj)

對(duì)于p,q∈S，若p≮q且q≮p，則稱p和q不可比較。

定義2Skyline集合。對(duì)于數(shù)據(jù)集S，S上所有不被其他數(shù)據(jù)點(diǎn)支配的數(shù)據(jù)點(diǎn)所構(gòu)成的集合稱為Skyline結(jié)果集，記為Sky(S)，即：

定義3Skyline查詢。Skyline查詢指的是，從給定的數(shù)據(jù)集中選擇出所有不被任何其他數(shù)據(jù)點(diǎn)所支配的數(shù)據(jù)點(diǎn)的過程，其查詢結(jié)果為Skyline集合。

傳統(tǒng)Skyline查詢方法主要為集中式數(shù)據(jù)庫上的一般性算法，主要分為不使用索引的Skyline查詢算法[1,8-9]和基于索引的Skyline查詢算法[10-12]2個(gè)大類。此外，研究者還針對(duì)高維數(shù)據(jù)集對(duì)子空間Skyline查詢處理[13-17]進(jìn)行研究。

在現(xiàn)實(shí)應(yīng)用中，用戶的查詢要求更加復(fù)雜，每個(gè)用戶對(duì)不同維度的關(guān)心程度不同[18]，因此，研究者對(duì)偏好Skyline查詢進(jìn)行研究。現(xiàn)有的研究中，大多數(shù)都是對(duì)傳統(tǒng)的支配方式進(jìn)行改變，通過新定義的支配方式對(duì)數(shù)據(jù)集進(jìn)行Skyline查詢計(jì)算，具體的研究成果包括：

Abbaci等人[4]基于語義量詞“幾乎全部”定義了另一種新的支配關(guān)系，f-約束支配的條件是“絕大多數(shù)”的屬性值要更好，并在此基礎(chǔ)上詳細(xì)介紹了3種算法來實(shí)現(xiàn)對(duì)Skyline結(jié)果的進(jìn)一步縮小。第三種LISR算法在前2個(gè)算法的基礎(chǔ)上，不僅關(guān)注支配的維度數(shù)和支配的程度，還在一定程度上考慮了部分屬性的重要程度，使得結(jié)果更接近用戶的偏好。

Xia等人[5]提出了ε-Skyline的概念，利用可調(diào)整的參數(shù)ε，對(duì)傳統(tǒng)的支配關(guān)系進(jìn)行定量地放松或者收緊，通過新的ε支配關(guān)系對(duì)Skyline結(jié)果集的大小進(jìn)行有效地控制，并給出了支持該ε支配關(guān)系的2種算法。同時(shí)，在ε支配關(guān)系的定義中，作者加入了屬性權(quán)重的概念。在比較元組支配關(guān)系的過程中，不同權(quán)重的屬性其評(píng)判標(biāo)準(zhǔn)不同且與其權(quán)重相關(guān)，使返回的結(jié)果集更加符合用戶的偏好。但是，該算法需要提前定義屬性的權(quán)重值，缺乏實(shí)用性。

楊永滔等人[6]在p-Skyline關(guān)系的基礎(chǔ)上引入屬性相對(duì)重要性的概念，并在此基礎(chǔ)上提出了一種支持約束分析的CABDA算法。該算法通過對(duì)構(gòu)造優(yōu)先Skyline關(guān)系所必需滿足的約束集合的特征進(jìn)行分析，進(jìn)一步確定屬性之間的相對(duì)重要性，最終確定滿足約束條件的優(yōu)先Skyline關(guān)系。實(shí)驗(yàn)表明CABDA算法的效率遠(yuǎn)大于已有的算法，且計(jì)算得到的優(yōu)先Skyline關(guān)系確實(shí)能有效反應(yīng)用戶在數(shù)據(jù)對(duì)象屬性之間的偏好。

Zhao等人[7]針對(duì)QoS服務(wù)提出了一種模糊語言偏好模型，將由量詞表示的屬性偏好關(guān)系通過函數(shù)轉(zhuǎn)換成數(shù)值表示的權(quán)重值；并在此基礎(chǔ)上提出了hybrid-EA算法，同時(shí)引入加權(quán)的切比雪夫距離(WTD)，進(jìn)一步對(duì)Pareto支配關(guān)系產(chǎn)生的Skyline結(jié)果集中的元組進(jìn)行排序。

綜上可知，基于偏好的Skyline查詢結(jié)果更加符合用戶對(duì)每個(gè)屬性的偏好需求，然而，已有的相關(guān)研究工作均是針對(duì)單用戶展開的，在多用戶參與的應(yīng)用背景下缺少相關(guān)的研究。

2 交互式MUPS算法

2.1 查詢建模及相關(guān)定義

例1中的多用戶偏好Skyline查詢問題可以抽象為以下模型：對(duì)于某數(shù)據(jù)集，用戶群中的每個(gè)用戶分別基于自身的需求提出了一個(gè)偏好查詢，偏好包括屬性優(yōu)先關(guān)系，系統(tǒng)根據(jù)這些偏好查詢?cè)跀?shù)據(jù)集上進(jìn)行偏好Skyline查詢，最終返回Skyline結(jié)果集給用戶群。

下面對(duì)所提出的問題做嚴(yán)格化定義，并給出多用戶偏好Skyline查詢過程中涉及的相關(guān)概念的定義。

定義4屬性優(yōu)先關(guān)系。給定2個(gè)屬性d1和d2，d1,d2∈D，D為屬性集合，d1和d2之間的優(yōu)先關(guān)系可由?、?和≈這3個(gè)謂詞表示。d1?d2表示d1屬性的重要程度要遠(yuǎn)大于d2屬性；d1?d2表示d1屬性的重要程度要大于d2屬性；d1≈d2表示2個(gè)屬性的重要程度相等。

在例1中，若D={d1,d2,d3,d4,d5}分別表示面積、價(jià)格、所在學(xué)區(qū)、交通便利性和綠化環(huán)境這5個(gè)屬性，則對(duì)于用戶A來說，價(jià)格的重要程度要遠(yuǎn)大于其他任何屬性，因此d2?d1，d2?d3，d2?d4，d2?d5；而面積和交通便利性都是需要考慮但又不是最重要的屬性，因此d1≈d4，d1?d5，d4?d5。

定義5屬性偏好鏈。在屬性集合D′上，根據(jù)屬性之間的優(yōu)先關(guān)系形成的偏序的屬性偏好鏈，用φ={dk1φdk2φ…φdkn}表示，其中dki表示屬性，φ表示屬性之間的優(yōu)先關(guān)系。

在例1中，用戶A的屬性偏好鏈為ΦA(chǔ)={d2?d1≈d4?d3≈d5}。

定義7多用戶偏好Skyline查詢。用戶群中任一用戶uj∈U，針對(duì)數(shù)據(jù)集的屬性特點(diǎn)提出相應(yīng)的偏好查詢，表示為qj={C,dkt}，其中C={dk1,dk2,…,dkr}表示用戶需要考慮的屬性，dkt表示用戶優(yōu)先考慮即重要程度最大的屬性，dkt∈C。

基于上述給出的相關(guān)定義，下面給出可以有效求解多用戶偏好Skyline查詢問題的MUPS算法。

2.2 獲取初始屬性偏好鏈

在多用戶偏好Skyline查詢中，用戶群中每個(gè)用戶都會(huì)提出不同的偏好查詢。由定義7可知，用戶偏好對(duì)數(shù)據(jù)集屬性的重要程度提出定義，通過屬性之間的優(yōu)先關(guān)系可定性地推出單用戶的屬性偏好鏈。但是每個(gè)用戶的屬性偏好鏈存在差異性，甚至?xí)霈F(xiàn)部分沖突的情況。例如，現(xiàn)有用戶u1定義的部分偏好鏈為d1?d2，而用戶u2定義的為d2?d1，那么無法簡(jiǎn)單地合并處理d1和d2這2屬性的優(yōu)先關(guān)系。此時(shí)需要對(duì)用戶群的偏好進(jìn)行整體分析，引入屬性權(quán)重的概念，定量地判斷屬性間的優(yōu)先關(guān)系，具體的方法分為以下5個(gè)步驟：

1)初始化屬性權(quán)重。在用戶提出偏好查詢之前，默認(rèn)將D中所有屬性的權(quán)重值初始化為0，即W={w1,w2,…,wd}={0,0,…,0}。

2)對(duì)每個(gè)用戶的偏好屬性進(jìn)行分類。根據(jù)屬性優(yōu)先關(guān)系的定義，將所有屬性分成3類，分別為最重要、一般重要和不重要，記為c1、c2、c3。依次對(duì)每個(gè)用戶的偏好進(jìn)行分析，用戶定義的最優(yōu)先考慮的屬性dkt屬于c1，C={dk1,dk2,…,dkr}中除dkt外的其他需要考慮的屬性屬于c2，其余沒有提及的屬性屬于c3。

例如，對(duì)于例1的用戶A，有c1={d2}，c2={d1,d4}，c3={d3,d5}。

3)計(jì)算各屬性的權(quán)重值。在計(jì)算權(quán)重值的過程中，對(duì)于每個(gè)用戶而言，屬于c1和c2類的屬性其權(quán)重分別自加w(c1)和自加w(c2)，w(c1)和w(c2)分別表示c1和c2類的權(quán)重且w(c1)>w(c2)，由系統(tǒng)提前設(shè)定，本文取w(c1)=2，w(c2)=1，而c3類中的屬性權(quán)重保持不變，這在一定程度上定量地表示屬性重要程度的增加。對(duì)每個(gè)用戶按照公式(1)對(duì)上一步得到的分類后的屬性進(jìn)行計(jì)算，最后累積得到用戶群的屬性權(quán)重。

(1)

因此，對(duì)例1中用戶群的偏好進(jìn)行分析得到各屬性的權(quán)重值為W={2,3,4,2,0}。

例如，第3步得到的屬性權(quán)重值正規(guī)化后為W={0.36,0.28,0.18,0.18,0}。

5)生成屬性偏好鏈。根據(jù)歸一化后的屬性權(quán)重大小，對(duì)屬性權(quán)重值不為0的屬性降序排列，形成偏序的屬性偏好鏈。

最后可以得出，例1中用戶群的屬性偏好鏈為Φ={d3?d2?d1≈d4?d5}。

根據(jù)上述步驟給出獲取初始偏好鏈的具體算法，見算法1。

算法1createPriorityList(Q)

輸入：用戶群的偏好查詢集合Q={q1,q2,…,qn}

輸出：用戶群的屬性偏好鏈PriorityList

1.W←{0}; //初始化屬性權(quán)重集合W

2.for every user ujin U do

3.for every attribute diin qjdo

4.put diinto different class ckaccording to qj

//對(duì)屬性進(jìn)行分類

5.if di∈c1then

6.wi+=2;

7.else if di∈c2then

8.wi+=1; //按照屬性類別進(jìn)行累加

9.end for

10.end for

11.normalize the weight of the attributes //權(quán)值歸一化

12.sort the attributes in descending order according to their weights as PriorityList

//對(duì)屬性降序排列，并賦給PriorityList

13.return PriorityLis

算法1的輸入為用戶群的偏好查詢集合Q，qj表示用戶群中第j個(gè)用戶提出的偏好查詢要求，輸出為用戶群的屬性偏好鏈。該算法通過對(duì)各用戶偏好的分析，完成了對(duì)屬性偏好鏈及其權(quán)重的初步設(shè)定，為后續(xù)查詢的支配放松作基礎(chǔ)。

2.3 基于權(quán)重的支配放松策略

在多用戶參與的查詢中，每個(gè)用戶的偏好不同。當(dāng)屬性維度增加時(shí)，Skyline查詢結(jié)果集的大小會(huì)隨之出現(xiàn)指數(shù)增長(zhǎng)的情況。為了使查詢結(jié)果對(duì)用戶的決策有意義，需要對(duì)Skyline結(jié)果集進(jìn)行剪枝縮放。

現(xiàn)有的減少Skyline結(jié)果集的算法主要是通過放松數(shù)據(jù)點(diǎn)之間的支配方式來達(dá)到縮放的目的，但是已有的算法存在幾點(diǎn)不足：1)放松的閾值需要人為提前設(shè)定，這對(duì)用戶對(duì)數(shù)據(jù)集的認(rèn)識(shí)要求較高；2)放松的過程只有一次，用戶參與度不高。因此，在2.2節(jié)得到的屬性權(quán)重的基礎(chǔ)上，本節(jié)提出了新的放松粒度下的支配方式，并給出了一種循序漸進(jìn)的放松策略。

2.3.1 σ-支配

定義8σ-支配。給定一個(gè)d維數(shù)據(jù)集S，屬性權(quán)重集合為W={wi|i∈[1,d],0

(2)

值得注意的是，以上的定義假設(shè)數(shù)據(jù)集所有維度上的值越小越好。利用σ-支配，可以對(duì)Skyline結(jié)果集進(jìn)行進(jìn)一步的放松。由定義1可知，傳統(tǒng)的支配方式是相對(duì)嚴(yán)格的，對(duì)于滿足pq的2個(gè)數(shù)據(jù)點(diǎn)p和q，在任何屬性上都必須滿足p不比q差，這也意味著，q能比p好的幅度為0。而在σ-支配方式下，將對(duì)某些屬性進(jìn)行放松處理，在這些屬性上允許q比p好，但同時(shí)要求q比p好的差值不大于放松粒度σ，這也意味著σ-支配并沒有那么“嚴(yán)格”。例如，表1中的2個(gè)數(shù)據(jù)點(diǎn)H4和H5，兩者在傳統(tǒng)支配方式下無法比較，因此H4和H5均是傳統(tǒng)Skyline集合中的點(diǎn)。現(xiàn)在假設(shè)對(duì)其他屬性不進(jìn)行放松，僅對(duì)d1屬性采用σ-支配比較，且d1屬性上的放松粒度為0.1。此時(shí)，H4除d1屬性以外的屬性值均不比H5差，且在d2和d4屬性上優(yōu)于H5，雖然H4在d1屬性上比H5差，但滿足|H4.d1-H5.d1|<σ1×160=16，即差值在允許的放松范圍內(nèi)，因此H4σ1H5。利用新的支配方式，可以改變數(shù)據(jù)點(diǎn)之間的支配關(guān)系，使不可比較的數(shù)據(jù)點(diǎn)具有可比性，從而對(duì)被支配的數(shù)據(jù)點(diǎn)進(jìn)行剪枝，使得結(jié)果集規(guī)模減小。

由定義8可知，不同優(yōu)先級(jí)的屬性對(duì)應(yīng)的放松粒度σ不同，且放松粒度σ與其對(duì)應(yīng)屬性的權(quán)重值成反比。當(dāng)權(quán)重值越大時(shí)，該屬性的重要程度更大，在該屬性上允許被放松的程度越小，則放松粒度σ更小，反之也成立。同時(shí)，當(dāng)權(quán)重值增大逐漸趨向于1時(shí)，放松粒度σ緩慢減??；而當(dāng)權(quán)重值逐漸減少至0時(shí)，放松粒度σ快速增大，這對(duì)后續(xù)的權(quán)重更新處理有著重要的作用。

2.3.2 放松策略

利用σ-支配的定義，將對(duì)傳統(tǒng)的Skyline結(jié)果集進(jìn)行多輪迭代放松，具體的放松策略為：在每一輪的迭代放松過程中，從屬性偏好鏈中尾部的屬性開始依次往前放松，用戶可提前定義每一輪放松的維度數(shù)θ。假設(shè)當(dāng)前放松的屬性為第dd-θ+1～dd個(gè)屬性，那么在2個(gè)數(shù)據(jù)點(diǎn)p和q的比較過程中，對(duì)于第d1～di-θ個(gè)屬性將保持原本傳統(tǒng)的支配方式，而對(duì)于屬性dd-θ+1～dd將通過σ-支配方式來進(jìn)行比較。在下一次的放松過程中，當(dāng)前放松的屬性為dd-2θ+1～dd，意味著在dd-2θ+1～dd維屬性上采用σ-支配方式判斷數(shù)據(jù)點(diǎn)之間的支配關(guān)系。以此類推直到所有的屬性都經(jīng)過放松處理。

值得注意的是，在一輪放松的最后一次放松中，若d-xθ<θ，x為已經(jīng)放松的次數(shù)，則最后一次放松的維度為d-xθ，此時(shí)放松的屬性為d1～dd，即所有維度的屬性。

算法2prune(PriorityList，W，θ，Sky)

輸入：用戶群的屬性偏好鏈PriorityList，屬性權(quán)重集合W={w1,w2,…,wd}，每一輪放松的維度數(shù)θ，放松前的Skyline結(jié)果集Sky。

輸出：放松后的偏好Skyline查詢候選集P，部分被剪枝的結(jié)果集DeleteSet。

1.P←Sky，DeleteSet←?

//初始化集合Pskyline和DeleteSet

2.for every attribute diin D do

3.calculate the relax- granularity σi

//計(jì)算各屬性對(duì)應(yīng)的支配放松粒度

4.x←1;

5.for i=d to 0 do

6.for every tpand tq∈P do

7.if tpσtqin dd-xθ+1～dddimension then

8.remove tqfrom P and insert into DeleteSet;

//將被支配的點(diǎn)從P移除，加入DeleteSet

9.end if

10.end for

11.x++;

12.end for

13.output P and DeleteSet;

算法2給出了基于σ-支配的逐次放松的算法，算法的前2個(gè)輸入?yún)?shù)為2.3.1節(jié)對(duì)用戶群偏好的分析后得到的屬性偏好鏈PriorityList和相對(duì)應(yīng)的屬性權(quán)重集合W，第三個(gè)輸入?yún)?shù)為用戶輸入的維度數(shù)θ，表示每一輪放松過程一次放松的維度數(shù)。算法的輸出參數(shù)為放松結(jié)束后的偏好Skyline查詢候選集P以及放松過程中部分被刪除出去的結(jié)果集DeleteSet。首先，對(duì)偏好Skyline查詢候選集P以及部分被剪枝的結(jié)果集DeleteSet初始化，將其分別賦予Sky集合和置為空集；然后，根據(jù)當(dāng)前屬性偏好鏈中的屬性權(quán)重值來計(jì)算各屬性對(duì)應(yīng)的支配放松粒度σi，對(duì)應(yīng)算法2的2～3行；算法第4～12行為支配放松策略的具體實(shí)施步驟，從屬性偏好鏈中尾部的屬性開始依次往前放松，對(duì)P中的任意2點(diǎn)進(jìn)行比較，對(duì)支配結(jié)果分類處理：1)若tpσtq則將被支配的tp點(diǎn)從P移除，加入DeleteSet；2)若tp與tq這2點(diǎn)互相支配，將保留這2點(diǎn)在P中；3)若tp與tq無法比較，則將這2點(diǎn)保留在P中，等待下一次在其他維度的放松。通過多次放松，最終所有維度上都經(jīng)過放松處理，并將最終結(jié)果返回，對(duì)應(yīng)算法13行。

此外，算法使用對(duì)輸入數(shù)據(jù)Sky進(jìn)行預(yù)排序的方法，來減少數(shù)據(jù)點(diǎn)之間的比較次數(shù)。數(shù)據(jù)集按照屬性優(yōu)先序排列，即對(duì)數(shù)據(jù)點(diǎn)先在優(yōu)先級(jí)高的維度上降序排列，并依次在接下來的維度中降序排列。在數(shù)據(jù)點(diǎn)依次比較的過程中，保證了排在窗口后面的數(shù)據(jù)點(diǎn)在重要維度上的值不優(yōu)于排在它前面的值，對(duì)于未放松的維度，只要滿足被窗口末尾的數(shù)據(jù)點(diǎn)支配，則無需與窗口前面的數(shù)據(jù)點(diǎn)比較，即可終止本次對(duì)該點(diǎn)的比較，因此可減少數(shù)據(jù)點(diǎn)之間的比較的次數(shù)。

通過以上σ-支配放松處理，將有效地減少原始Skyline查詢結(jié)果集，同時(shí)每個(gè)屬性放松的粒度均與其優(yōu)先性相關(guān)，使得縮放的結(jié)果集更加合理，精準(zhǔn)地體現(xiàn)了用戶群的偏好。此外，算法采用了動(dòng)態(tài)輸出結(jié)果的方法，當(dāng)用戶得到其滿意的結(jié)果，則可以隨時(shí)終止算法的運(yùn)行，極大提高了用戶體驗(yàn)效果。

2.4 屬性權(quán)重動(dòng)態(tài)修正

在實(shí)際運(yùn)用中，數(shù)據(jù)集的屬性權(quán)重會(huì)動(dòng)態(tài)地發(fā)生變化，主要有以下3種原因：1)用戶在初次提出偏好查詢時(shí)，不具備對(duì)數(shù)據(jù)集的充足認(rèn)識(shí)，初始的權(quán)重值并不能真實(shí)反映用戶的偏好；2)受到時(shí)間、環(huán)境等因素的影響，用戶對(duì)不同屬性的偏好程度會(huì)因?yàn)閭€(gè)人因素發(fā)生變化；3)多用戶參與的情況下，用戶在查詢過程中會(huì)受到其他用戶的影響，綜合他人的決策意見，從而在一定程度上改變自己的偏好。以例1的多用戶購房為例，根據(jù)用戶偏好得到的初始屬性偏好鏈及其權(quán)重值并不能真實(shí)反映用戶群最終的偏好，需要經(jīng)過動(dòng)態(tài)地修正，才能達(dá)到最符合用戶群的需求，算法3給出了屬性權(quán)重的動(dòng)態(tài)修正算法。

算法3modifyWeights(PSkyline，DeleteSet，W，t)

輸入：偏好Skyline查詢候選集PSkyline，部分被剪枝的結(jié)果集DeleteSet，屬性權(quán)重集合W，迭代輪次t。

輸出：修正后的權(quán)重屬性權(quán)重集合W。

1.upAttr[x]，downAttr[y]←?;

//初始化需要修改的屬性列表

2.for every ukin U do

3.upAttrk，downAttrk←UserSelect (PSkyline,DeleteSet);

//用戶選擇需要增大和減少權(quán)重值的屬性

4.if count[di]≥n/2 when diin every upAttrkthen

5.insert diinto upAttr[x];

//獲取需要增加權(quán)重的屬性集合

6.if count[dj]≥n/2 when djin every downAttrkthen

7.insert djinto downAttr[y];

//獲取需要減小權(quán)重的屬性集合

8.calculate the Δ=min(1/[t×(t+1)]，min(wj)×y) for each wjin downAttr[y];

//計(jì)算每輪修改的權(quán)重值Δ，且考慮特殊情況

9.for every diin upAttr[x] do

10.wi+=Δ/x;

11.for every djin downAttr[y] do

12.wj-=Δ/y;

13.return W; //返回更新后的屬性權(quán)重集合

在算法3中，首先，算法對(duì)需要調(diào)整權(quán)重值大小的屬性列表進(jìn)行初始化，將其置為空。接著，用戶對(duì)本輪縮放得到的PSkyline和DeleteSet結(jié)果集進(jìn)行觀察和分析，進(jìn)行定性的反饋。由于PSkyline結(jié)果集是按照屬性優(yōu)先序排列的，因此用戶會(huì)有一個(gè)直觀的認(rèn)識(shí)。若PSkyline結(jié)果集中某屬性值密集且較優(yōu)，但對(duì)應(yīng)其他屬性上的值均很差，則說明該屬性的重要程度需要被減小，而其他屬性的優(yōu)先級(jí)可能需要增加。根據(jù)諸如此類的結(jié)果集信息，各用戶uk分別選出一個(gè)需要增大和減小權(quán)重值的屬性u(píng)pAttrk和downAttrk，對(duì)應(yīng)算法3的2～3行。然后，系統(tǒng)對(duì)用戶群的選擇結(jié)果進(jìn)行綜合分析，若滿足一半以上的用戶選擇同一個(gè)屬性，該屬性才能認(rèn)為是需要修改的，從而確定所有需要進(jìn)行調(diào)整權(quán)重值的屬性u(píng)pAttr[x]和downAttr[y]，分別表示權(quán)重值需要增加的屬性集合，其個(gè)數(shù)為x，以及需要減少的屬性集合，其個(gè)數(shù)為y，對(duì)應(yīng)算法3的4～7行。算法3中8～12行對(duì)上面步驟得到的需要調(diào)整的屬性作出修正，值得注意的是，每輪交互迭代過程中，屬性權(quán)重值增加的總值Δ+與減少的總值Δ-是相當(dāng)?shù)模浣^對(duì)值均為Δ，∑wi(di∈upAttr[x])=∑wj(dj∈downAttr[y])=Δ，保證了調(diào)整后所有屬性權(quán)重值之和仍為1。修改值Δ是有關(guān)迭代輪次t的函數(shù)f(t)=1/[t×(t+1)]，對(duì)于需要增大權(quán)重值的屬性di，其增加的權(quán)重值Δwi=Δ/x，而對(duì)于需要減少權(quán)重值的屬性dj，其減少的權(quán)重值為Δwj=Δ/y。需要注意的是，若存在Δwj

2.5 MUPS算法

前面分別給出了多用戶偏好Skyline查詢中用到的數(shù)據(jù)處理方法，基于上文的敘述，本節(jié)提出完整的基于屬性權(quán)重的多用戶偏好Skyline查詢算法——MUPS算法，并詳細(xì)分析該算法的處理流程。

算法4給出了多用戶偏好Skyline查詢算法——MUPS算法。算法的輸入為：用戶群給出的偏好查詢集合Q={q1,q2,…,qn}，其中qj={C,dkt}，C={dk1,dk2,…,dkr}表示用戶需要考慮的屬性，dkt表示用戶優(yōu)先考慮即重要程度最大的屬性，dkt∈C，以及用戶設(shè)定的每輪放松過程中一次放松處理的維度數(shù)θ。首先，對(duì)輸出的結(jié)果集PSkyline初始化，將其置為空；然后利用初始屬性偏好鏈生成算法1分析用戶群的偏好查詢，形成帶權(quán)重的屬性偏好鏈PriorityList，并得到各屬性的權(quán)重值W；接著對(duì)偏好屬性鏈上的維度用SFS算法[8]計(jì)算初始Skyline候選集，對(duì)應(yīng)算法4的第3行；在此基礎(chǔ)上，算法4第4～12行，通過σ-支配放松對(duì)上一步得到的初始Skyline候選集進(jìn)行多輪剪枝處理，每一輪的放松過程中，動(dòng)態(tài)輸出放松后結(jié)果P和部分被剪枝的結(jié)果DeleteSet，用戶對(duì)結(jié)果作出反饋意見，系統(tǒng)通過對(duì)用戶的意見進(jìn)行分析，動(dòng)態(tài)地更新屬性權(quán)重值，若因此屬性之間的優(yōu)先關(guān)系發(fā)生變化，則還要更新屬性偏好鏈，動(dòng)態(tài)調(diào)整后將進(jìn)入下一輪的放松處理直到滿足算法的終止條件，該算法的終止條件具體為：1)用戶手動(dòng)選擇終止交互過程；2)分析用戶的選擇后，沒有權(quán)重滿足需要修改的條件。此時(shí)最后一輪放松后的結(jié)果即為最優(yōu)偏好Skyline查詢結(jié)果PSkyline，將此作為算法的輸出參數(shù)輸出，對(duì)應(yīng)算法4的第11～12行。

算法4MUPS算法

輸入：用戶群的偏好查詢集合Q={q1,q2,…,qn}，每次放松的屬性維度數(shù)θ。

輸出：最優(yōu)偏好Skyline查詢結(jié)果集PSkyline。

1.PSkyline←?;

2.createPriorityList(Q)→PriorityList，W;

3.Sky←SFS (PriorityList);

//利用SFS算法計(jì)算初始的Skyline候選集

4.t←0;

5.while(true)

6.P，DeleteSet←prune(PriorityList，W，θ，Sky);

//動(dòng)態(tài)輸出放松結(jié)果P和部分被剪枝的結(jié)果DeleteSet

7.if Terminate(P) then

8.break; //若滿足終止條件，則退出循環(huán)

9.else

10.W←modifyWeights(PSkyline，DeleteSet);

//更新屬性權(quán)重

11.end if

12.t++;

13.PSkyline←P;

14.return PSkyline;

3 實(shí)驗(yàn)與分析

本章主要對(duì)MUPS算法進(jìn)行實(shí)驗(yàn)以及性能評(píng)估。算法的性能分為2個(gè)部分：

1)有效性。MUPS算法旨在基于屬性偏好關(guān)系減少原始Skyline結(jié)果集的規(guī)模大小，為用戶群決策提供有利價(jià)值，因此需要對(duì)剪枝后的結(jié)果集大小做檢驗(yàn)。

2)交互性能。MUPS算法通過交互來實(shí)現(xiàn)，交互過程中，系統(tǒng)需要在合理的時(shí)間間隔內(nèi)提供反饋信息，否則將影響用戶的交互體驗(yàn)，因此實(shí)驗(yàn)需要對(duì)算法過程中的系統(tǒng)自適應(yīng)間隔進(jìn)行驗(yàn)證。該算法對(duì)應(yīng)的系統(tǒng)自適應(yīng)間隔，指系統(tǒng)分析用戶選擇結(jié)果并動(dòng)態(tài)更新屬性權(quán)重后，在此基礎(chǔ)上再次剪枝返回結(jié)果的時(shí)間間隔。

此外，由于目前尚未有其他專門針對(duì)多用戶偏好Skyline查詢的算法可供比較，因此本實(shí)驗(yàn)中作為對(duì)比的Baseline算法為傳統(tǒng)單用戶下的LISR算法[4]的基本擴(kuò)展。具體為，對(duì)n個(gè)用戶分別通過執(zhí)行LISR算法完成每個(gè)用戶的偏好Skyline查詢，然后再取各子結(jié)果集的并集。

3.1 實(shí)驗(yàn)數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)分別采用模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行測(cè)試，如表2所示。本實(shí)驗(yàn)使用的模擬數(shù)據(jù)集參照文獻(xiàn)[1]的數(shù)據(jù)生成器產(chǎn)生，為相關(guān)數(shù)據(jù)集、獨(dú)立數(shù)據(jù)集以及反相關(guān)數(shù)據(jù)集3種，數(shù)據(jù)維度為6～10，且默認(rèn)屬性值越小越優(yōu)；采用的真實(shí)數(shù)據(jù)集為NBA球員技術(shù)統(tǒng)計(jì)數(shù)據(jù)集。由于實(shí)驗(yàn)需要多用戶同時(shí)參與，在學(xué)校范圍內(nèi)選取了30名志愿者，在實(shí)驗(yàn)過程中作為用戶提出不同的偏好需求。為避免隨機(jī)性對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生的影響，所有的結(jié)果均為10次試驗(yàn)運(yùn)行結(jié)果的平均值。

表2 實(shí)驗(yàn)數(shù)據(jù)集

數(shù)據(jù)集數(shù)據(jù)規(guī)模數(shù)據(jù)維度模擬數(shù)據(jù)集1×104～5×1046,7,8,9,10真實(shí)數(shù)據(jù)集172658

實(shí)驗(yàn)所用計(jì)算機(jī)的操作系統(tǒng)為Windows 10，CPU主頻為3.3 GHz，內(nèi)存為4 GB。所有算法均用C++語言實(shí)現(xiàn)，編譯器為Visual Studio 2010。

3.2 數(shù)據(jù)量對(duì)算法性能的影響

為分析數(shù)據(jù)量對(duì)MUPS算法性能的影響，本實(shí)驗(yàn)采用相關(guān)、獨(dú)立和反相關(guān)3種人造數(shù)據(jù)集進(jìn)行測(cè)試。數(shù)據(jù)點(diǎn)個(gè)數(shù)n從1×104到5×104變化，數(shù)據(jù)集維度均為6。實(shí)驗(yàn)隨機(jī)挑選10組測(cè)試用戶組合，設(shè)定每組測(cè)試中參與的用戶數(shù)為4，每個(gè)用戶關(guān)注的最大維度為4，所求結(jié)果集大小和系統(tǒng)自適應(yīng)間隔為10組實(shí)驗(yàn)結(jié)果的平均值。

(a) 相關(guān)數(shù)據(jù)集

(b) 獨(dú)立數(shù)據(jù)集

(c) 反相關(guān)數(shù)據(jù)集圖1 數(shù)據(jù)量對(duì)結(jié)果集大小的影響

圖1分別展示了不同類型數(shù)據(jù)集下MUPS算法與LISR-base算法的結(jié)果集大小對(duì)比，從實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)：未剪枝前的Skyline查詢結(jié)果集規(guī)模很大，且隨著數(shù)據(jù)集大小的增大而增加，在反相關(guān)數(shù)據(jù)集下尤為明顯，這是由于數(shù)據(jù)類型的特征導(dǎo)致的。MUPS算法與LISR-base算法對(duì)原始Skyline結(jié)果集均有一定的剪枝效果，結(jié)果集大小得到不同程度的控制。但對(duì)于同一個(gè)類型的數(shù)據(jù)集，MUPS算法的剪枝效果明顯要比LISR-base算法更好，得到的結(jié)果集更小，更有利于用戶決策。同時(shí)，MUPS算法對(duì)反相關(guān)數(shù)據(jù)集的剪枝效果比其他2類數(shù)據(jù)類型要好，這是因?yàn)榉聪嚓P(guān)數(shù)據(jù)集屬性之間的沖突較大，而MUPS算法能通過放松控制關(guān)系有效地緩解沖突，從而使得結(jié)果集規(guī)模減小。

圖2 數(shù)據(jù)量對(duì)系統(tǒng)自適應(yīng)間隔的影響

考慮到LISR-base沒有交互過程，因此對(duì)其不做交互性能的對(duì)比。圖2為MUPS算法在相關(guān)、獨(dú)立和反相關(guān)3種數(shù)據(jù)集下的系統(tǒng)自適應(yīng)間隔對(duì)比結(jié)果。該間隔時(shí)間主要包括MUPS算法中的系統(tǒng)對(duì)用戶反饋結(jié)果的分析時(shí)間和支配放松計(jì)算的運(yùn)行時(shí)間，由于支配放松需要數(shù)據(jù)點(diǎn)之間的比較，因此隨著數(shù)據(jù)量的增加，支配放松計(jì)算消耗的時(shí)間遞增。而實(shí)驗(yàn)中系統(tǒng)交互間隔均在5 s以內(nèi)，在用戶的容忍范圍之內(nèi)，可及時(shí)地對(duì)結(jié)果進(jìn)行溝通和反饋。

3.3 用戶數(shù)量對(duì)算法性能的影響

本實(shí)驗(yàn)主要考察用戶數(shù)量對(duì)MUPS算法性能的影響。從3.2節(jié)實(shí)驗(yàn)結(jié)果中可以發(fā)現(xiàn)，正相關(guān)數(shù)據(jù)集下的Skyline結(jié)果集包含的數(shù)據(jù)點(diǎn)數(shù)較少，因此算法性能均較好。因此，不再對(duì)比正相關(guān)數(shù)據(jù)集下的算法性能，實(shí)驗(yàn)利用獨(dú)立數(shù)據(jù)集和反相關(guān)數(shù)據(jù)集進(jìn)行測(cè)試，數(shù)據(jù)點(diǎn)個(gè)數(shù)均為1×104，數(shù)據(jù)集維度均為6。實(shí)驗(yàn)隨機(jī)從30名志愿者中選取不同數(shù)量的用戶組合，每組用戶的數(shù)量從2到6變化，每個(gè)用戶關(guān)注的維度最大為4，每組所求結(jié)果集大小為10次實(shí)驗(yàn)結(jié)果的平均值。

圖3 用戶數(shù)量對(duì)結(jié)果集大小的影響

圖3分別為獨(dú)立數(shù)據(jù)集和反相關(guān)數(shù)據(jù)集下結(jié)果集大小的測(cè)試結(jié)果，可以看出隨著用戶數(shù)量的增加，LISR-base算法得到的結(jié)果集規(guī)模隨之迅速增大，這是因?yàn)橛脩魯?shù)量增加，子偏好Skyline結(jié)果集的個(gè)數(shù)增加，并集操作后的結(jié)果集大小增加，在反相關(guān)數(shù)據(jù)集中結(jié)果集增大的幅度尤為明顯。而MUPS算法的返回結(jié)果集規(guī)模隨用戶數(shù)量的增加緩慢增大，有效地進(jìn)行了剪枝。

MUPS算法在獨(dú)立和反相關(guān)數(shù)據(jù)集下的系統(tǒng)自適應(yīng)間隔結(jié)果如圖4所示，當(dāng)用戶群中的用戶數(shù)量增加，系統(tǒng)自適應(yīng)間隔時(shí)間增長(zhǎng)的幅度緩慢，這是因?yàn)镸UPS中對(duì)用戶的選擇分析耗時(shí)以及權(quán)重更新的時(shí)間相比之下在常數(shù)級(jí)，因此變化影響并不大，而用戶的數(shù)量對(duì)支配比較時(shí)間并沒有直接影響。

3.4 真實(shí)數(shù)據(jù)下的算法性能

本實(shí)驗(yàn)采用NBA球員技術(shù)統(tǒng)計(jì)數(shù)據(jù)集對(duì)算法的有效性以及偏好性能進(jìn)行驗(yàn)證。該數(shù)據(jù)集共有17265條數(shù)據(jù)，全空間維數(shù)為8維。首先為了檢驗(yàn)用戶數(shù)量對(duì)算法性能的影響，隨機(jī)從30名志愿者中選取不同數(shù)量的用戶組合，每組用戶的數(shù)量分別從2到6變化，每個(gè)用戶關(guān)注的維度最大為4。

圖5 真實(shí)數(shù)據(jù)集下用戶數(shù)量對(duì)算法性能的影響

圖5展示了真實(shí)數(shù)據(jù)集下用戶數(shù)量對(duì)MUPS算法的系統(tǒng)自適應(yīng)間隔的影響，從圖5中可以發(fā)現(xiàn)其結(jié)果與人造標(biāo)準(zhǔn)數(shù)據(jù)下的結(jié)果一致，驗(yàn)證了MUPS算法的交互性，即可較高效地支持用戶進(jìn)行交互式查詢。

4 結(jié)束語

本文針對(duì)現(xiàn)實(shí)生活存在的多用戶場(chǎng)景下的偏好Skyline查詢問題，進(jìn)行深入分析和研究，闡述了傳統(tǒng)單用戶偏好Skyline查詢?cè)诮鉀Q該問題上的不足，在此基礎(chǔ)上提出了一種基于用戶權(quán)重的交互式多用戶Skyline查詢算法MUPS算法。MUPS算法，首先通過分析用戶群各用戶的偏好查詢要求，確定用戶群的初始屬性偏好鏈；然后，提出一種基于屬性權(quán)重的新的支配方式——σ-支配，通過新的支配方式對(duì)原始Skyline結(jié)果集進(jìn)行剪枝縮放，并通過用戶群與返回候選集的交互，對(duì)屬性偏好鏈中各屬性的權(quán)重大小進(jìn)行動(dòng)態(tài)修正，多輪迭代后最終返回更符合用戶群真實(shí)需求的結(jié)果。實(shí)驗(yàn)結(jié)果表明，MUPS算法能有效地解決多用戶場(chǎng)景下的偏好Skyline查詢問題，返回的結(jié)果集大小對(duì)用戶的決策有參考意義，同時(shí)該算法具有良好的交互性能。