一種基于上界值剪枝的用戶敏感top-k dominating查詢方法

摘要：信息化社會帶來了數據量的快速增長，但也導致數據的完整性和價值密度越來越低，如何從海量不完整數據中快速找到有價值的信息用于用戶個性化推薦，已經成為研究的熱點。結合上界值剪枝算法，提出一種用戶敏感top-k dominating（TKD）查詢方法（USTD）。該方法首先結合用戶興趣度，重新定義了不完整數據集上對象的支配關系及其度量方法，計算對象的權重支配分數；然后以重新定義的支配關系，證明了依據上界值可剪枝的條件；最后將上界值剪枝條件融于USTD的查詢過程，以從數據集中快速找到前k個滿足用戶興趣的數據。實驗結果表明，USTD算法在查詢速度上有一定提升，在查詢結果的評分上具有顯著優勢。

關鍵詞：不完整數據；TKD查詢；用戶敏感；權重支配分數；上界值剪枝

中圖分類號：TP312文獻標志碼：A

文章編號：1001-3695（2023）01-032-0198-06

doi：10.19734/j.issn.1001-3695.2022.04.0232

User-sensitive top-k dominating query method based on upper bound pruning

Xu Chaoa，b，Wu Danqia，b，Chen Yonga，b，Lei Jintaoa，b

（a.School of Information Engineering，b.Institute of Audit Science amp; Technology，Nanjing Audit University，Nanjing 211815，China）

Abstract：With the rapid growth of data volume in the information society，the integrity and value density of data are getting lower and lower，but people’s personalized needs are becoming more and more obvious.How to quickly find valuable data from massive incomplete data for users’ personalized recommendation has became a hot spot of research.Combined with the upper bound pruning algorithm，this paper proposed a user-sensitive top-k dominating （TKD） query method （USTD）.Firstly，combined with user’s interests，the method redefined the dominance relationship and its measurement method of objects on incomplete datasets，and calculate the weight dominance grade of the object.Then，it proved the condition of pruning according to the upper bound value by using the redefined dominance relationship.Finally，it integrated the upper bound pruning condition into the query process of USTD to quickly find the first k data satisfying users’ interests from the dataset.The experimental results show that the USTD algorithm has a certain improvement in query speed and a significant advantage in the scoring of query results.

Key words：incomplete data；top-k dominating query；user sensitivity；weight dominance grade；upper bound value pruning

0引言

隨著社會的信息化發展，數據量快速增長，信息冗余問題出現，數據價值密度低，使得關鍵信息查找難度高、效率低。同時，數據不完整作為一種常見的數據質量問題，影響數據的可靠性和可用性。在很多情況下，海量數據中的缺失值無法被確定，并且用戶的個性化需求僅關注部分屬性維度，因此，從海量不完整數據中，高效地選擇最具有意義和影響力的數據結果，盡可能滿足用戶需求成為了研究的重點內容。

對于不完整數據集的處理和分析，通常需要先對其進行預處理，常用方法有簡單刪除存在缺失值的對象，如完整樣本分析［1］，或者采用各種技術填補缺失值，如均值填充法［2］、期望最大化填補法［3］、基于最近鄰區間的聚類填補［4］等。然而預處理的代價較大，并且數據的準確性不能保證，因此有必要探索直接對不完整數據集的高效查詢方法。top-k查詢指定一個評分函數來計算數據集中每個對象的分數，然后從數據集中返回k個得分最高的對象［5］。skyline查詢則返回數據集上不被其他對象支配的所有對象［6］。由于top-k查詢的評分函數難以定義，而skyline查詢的結果大小無法控制，所以Papadias［7］提出了top-k dominating查詢的概念，該查詢結合了top-k和skyline的優勢，在給定skyline準則的屬性集合上，對象o1的所有值均不大于對象o2的值，并且至少在一個屬性維度上，o1的值小于o2的值，則認為對象o1支配對象o2。依據這樣的支配關系，定義被對象o所支配的對象數量作為對象o的支配分數grade（o），最后top-k dominating查詢返回支配分數最高的k個對象。比如一個常見的公開電影數據集MovieLens整理了眾多用戶對多部電影的評分數據，如表1所示的電影評分數據集示例，每位用戶作為一個維度，每部電影作為一個對象，擁有多位用戶維度的評分數據，評分值為［1，2，3，4，5］五級，評分越高表示認可度越高。通過top-k dominating查詢，若某部電影支配的其他電影數量眾多，則說明該電影更受歡迎，因此可以從數據集中選擇出k部最受歡迎的電影。考慮到用戶的個性化需求，比如向18～24歲人群推薦電影，那么在查詢時，18～24歲用戶維度上的評分數據相比較其他用戶維度更重要，因此查詢算法中要關注不同屬性維度的重要性，而目前對于區分屬性重要性程度的TKD查詢研究較少。

本文則提出一個基于上界值剪枝的用戶敏感TKD查詢方法（USTD），結合用戶興趣度，設置一個權重向量，為數據對象的所有屬性維度賦權，引用MFD算子的概念，重新定義了數據對象的支配關系及其度量方法，計算數據對象的權重支配分數，使得屬性值是否缺失和屬性權重的大小對數據對象的得分更具有影響力。同時，由于判斷對象間的支配關系需要在整個數據集上將對象進行兩兩比較，這種最直接的方法十分低效，所以引用上界值剪枝的思想，先通過在單個維度上比較數據對象求出權重支配分數上界，再將上界值與候選集中的最小分數進行比較，判斷對象是否能被提前剪枝，從而減少計算分數的對象數量，高效地返回k個更具有影響力的數據對象結果。

1相關工作

Papadias［7］提出top-k dominating查詢的概念，從巨大的數據空間中返回更具有價值的有限的數據，許多研究人員也提出擴展的算法來優化這一查詢。韓希先等人［8］提出TDEP算法（top-k dominating with early pruning），利用較低的費用構建數據結構，并且通過早剪切方法獲得候選集，再從中計算對象的支配分數來返回查詢結果。Amagata等人［9］提出空間填補法來分布式處理TKD查詢，利用虛擬點聚焦需要優先搜索的數據空間，并且限制搜索的空間以剪枝不必要的計算，縮短查詢處理的時間。這些算法對于數據集中有缺失的屬性值沒有過多關注，無法有效地處理海量不完整的數據。

對于不完整數據，主要研究包括索引結構、skyline計算、相似性搜索以及top-k檢索等［10］。Gao等人［11］提出BG算法，利用桶結構，根據缺失情況將屬性集合分組，返回不被其所在組中其他對象支配的對象。Gulzar等人［12］提出一個OIS框架（optimized incomplete skyline），利用聚類、排序過濾等優化技術減少數據項之間支配測試的次數，從而簡化skyline處理。Miao等人［13］提出了一系列算法（ESB、UBB、BIG和IBIG），用于在集中式環境中處理不完整數據上的TKD查詢，其中基于上界值的top-k dominating算法（upper bound based algorithm，UBB），首先針對不完整數據，對支配的定義進行了完善；然后通過判斷對象在每一個屬性維度上的支配分數，選取所有維度中支配分數最小的作為該對象的得分上界值，進行有效剪枝獲得候選集；再對候選集中的對象進行兩兩支配關系的驗證，獲得對象的實際支配得分，返回k個分數最高的對象。該算法考慮到了有缺失值的屬性的支配情況，并且采用剪枝操作減少了對象的兩兩比較次數，提高了不完整數據查詢的效率。Ding等人［14］提出TKDI-MR算法和Wu等人［15］提出MGBIG、EHBIG、IEHBIG算法，基于BIG算法（bitmap index guided algorithm，BIG），通過構建位圖索引進一步優化剪枝策略，提升算法效率，同時在分布式環境下利用MapReduce架構，有效完成對大數據集的TKD查詢。文獻［16］提出一種加權TKD算法（weighted top-k dominating query，WTKD），使用B+樹構建桶結構以提高檢索的性能，同時應用加權因子描述對象在各個維度的數據缺失情況，以存在屬性值的維度數量占總維度數量的比例作為每個對象的權重，將權重與其支配分數相乘得到加權分數，依此篩選出k個分數最高的對象，強調了完整性更強的對象的支配力度。

但是這些算法未考慮屬性維度間的不同標度，沒有區分各個屬性維度的重要性程度。考慮到用戶僅對數據中的部分屬性維度感興趣，或者部分屬性維度對后續問題的探索更具有意義，因此查詢時需要對屬性維度間的標度作區分。Miao等人［13］提出一個缺失靈活支配算子（missing flexible dominance，MFD）的概念，為屬性維度賦權，引申支配的定義，但是未將其融合于查詢過程中。目前還未有考慮用戶個性化需求、區分屬性維度重要性的top-k dominating查詢算法。

2基于上界值剪枝的用戶敏感TKD查詢方法

針對不完整數據集，其中一些對象在某些維度上的屬性值缺失，對其進行TKD查詢。給定一個不完整數據集S，該數據集上的屬性維度集合為D，|D|=d。根據對象間的支配關系定義（定義1），計算S中每個對象o支配的對象數量作為o的支配分數（定義2），記作Grade（o），考慮到用戶個性化需求，區分各個屬性維度的重要性程度，設置長度為d的權重向量W=（w1，w2，…，wd），進一步計算每個對象o的權重支配分數（定義3），記作WeightGrade（o），最后USTD查詢返回k個權重支配分數最高的對象。表2給出本文中常用的符號及其說明。

2.1不完整數據集上對象間的支配定義

傳統的支配定義認為支配對象的屬性值越小越好，但實際上針對不同的應用場景，代表支配對象更好的意義不同，比如尋找既便宜又靠近海灘的旅館時，期待旅館在價格和距離兩個屬性維度上的值越小越好，而推薦高分電影時，期待電影在各個用戶維度上的評分值越大越好，因此定義對象間的支配關系需要適應不同場景。此外，傳統的支配定義未考慮數據缺失的維度上的支配條件。本文引申了對不完整數據集上對象間支配關系的定義，一般地，假設不完整數據集上的數據是隨機缺失的，并假定所有對象至少有一個維度的屬性值存在。

定義1支配關系。在一個屬性維度集合為D的不完整數據集S上，對于兩個存在部分缺失屬性值的對象o和o*，當同時滿足以下條件時，認為對象o支配o*，記作o→domo*：

條件1對于每個維度i，均有o［i］不比o*［i］差或者至少有一個對象在該維度的屬性值缺失；

條件2至少存在一個維度j，o［j］與o*［j］同時存在，并且o［j］比o*［j］好。

符號o［i］表示對象o在第i個維度上的屬性值。以表3的示例數據集為例，此數據集認為每個維度上的屬性值越小越好，因此o［i］不比o*［i］差表示為o［i］≤o*［i］。對于對象o1（1，-，2）和o2（3，1，2），因為o1［1］lt;o2［1］，o1［3］≤o2［3］，所以o1支配o2。對于對象o1（1，-，2）和o3（1，3，-），因為它們只有一個屬性維度即第1維的屬性值同時存在，并且o1［1］=o3［1］，所以o1和o3不相互支配。

2.2對象的支配分數定義

基于對象間的支配關系定義，將對象o與數據集上其他對象比較，判斷被對象o支配的對象集合，從而定義對象o的支配分數作為其評分函數，記作Grade。

定義2支配分數Grade。在一個屬性維度集合為D的不完整數據集S上，對于數據對象o，Grade（o）表示為對象o的支配分數，等于對象o支配的對象的數量，即Grade（o）=|{o*∈S-{o}|odomo*}|。

2.3基于屬性維度上權重向量的權重支配分數定義

對于不完整數據集上的兩個對象o和o*，其在各個維度上的屬性值有以下三種情況：

情況1在屬性維度i上，對象o和o*均有屬性值，即o［i］和o*［i］均存在；

情況2在屬性維度i上，僅有一個對象有屬性值，即o［i］和o*［i］僅有一個存在；

情況3在屬性維度i上，兩個對象均沒有屬性值，即o［i］和o*［i］均缺失。

通過區分這三種情況，并且考慮每個維度的重要程度不同，本文引用缺失靈活支配算子（MFD）的概念［13］：假設屬性維度集合D（|D|=d）存在權重向量W=（w1，w2，…，wd）和一個實參數λ（0lt;λlt;1），為對象o和o*的支配關系賦予一個權重，記作Ω（o，o*）=∑i∈I1wi+λ∑i∈I2wi，其中I1表示o［i］和o*［i］均存在的屬性維度集合，I2表示o［i］存在但o*［i］缺失的屬性維度集合。忽略o［i］和o*［i］均缺失的屬性維度。

基于MFD概念，本文對定義2的支配分數作出改進，重新定義對象的評分函數，稱作對象o的權重支配分數。

定義3權重支配分數WeightGrade。在一個屬性維度集合為D（|D|=d）的不完整數據集S上，屬性維度的權重向量為W=（w1，w2，…，wd），對于數據對象o，WeightGrade（o）表示為對象o的權重支配分數，等于對象o和被o支配的對象集合O之間Ω值的累積∑o*∈OΩ（o，o*），即

WeightGrade（o）=∑i∈Dset（o）Num1（i）×wi+∑j∈Dset（o）Num2（j）×λ×wj

其中：Dset（o）表示對象o的沒有缺失屬性值的維度集合；λ為參數（0lt;λlt;1），減弱有缺失值的維度的權重影響；Num1（i）表示在第i維上，被o支配的對象集合O中，該維度存在屬性值的對象的數量；Num2（j）表示在第j維上，被o支配的對象集合O中，該維度缺失屬性值的對象的數量，即

Num1（i）=|{o*∈O|o*［i］存在}|

Num2（j）=|{o*∈O|o*［j］缺失}|

2.4用戶敏感top-k dominating查詢（USTD）

定義4USTD查詢。在一個屬性維度集合為D（|D|=d）的不完整數據集S上，一個USTD查詢從S中選出權重支配分數WeightGrade最高的k個對象，放入結果集SR中，SRS，即|SR|=k，對o∈SR，o*∈{S-SR}，WeightGrade（o）≥WeightGrade（o*）。

以表3的示例數據集為例。對象o1支配{o2，o4}兩個對象，因此Grade（o1）=2，同理可得Grade（o2）=1，Grade（o4）=1，Grade（o3）=0。x，y，z三個維度的權重分別為w1，w2，w3，對象o1支配o2的關系權重為Ω（o1，o2）=w1+w3，對象o1支配o4的關系權重為Ω（o1，o4）=λ*w1+w3，因此對象o1的權重支配分數為

WeightGrade（o1）=w1+w3+λ*w1+w3=

∑i∈{1，3}（Num1（i）*wi+Num2（i）*λ*wi）

同理可得，WeightGrade（o2）=λ*w1+w2+w3，WeightGrade（o3）=0，WeightGrade（o4）=w2+λ*w3。當權重向量設置為W={3，1，2}，取λ=0.4時，WeightGrade（o1）=8.2，WeightGrade（o2）=4.2，WeightGrade（o3）=0，WeightGrade（o4）=1.8。所以當k=2時，USTD查詢返回的結果集為{o1，o2}。

2.5權重支配分數上界

傳統的TKD查詢需要將對象o與數據集S上的其他對象進行兩兩比較，以判斷對象間的支配關系，當數據量巨大時，計算對象的得分消耗太大的代價。為了提高不完整數據上TKD查詢的效率，Miao等人［15］提出了上界值算法（upper bound based algorithm，UBB），引入對象支配分數的上界值，依此確定對象的訪問順序，從而完成剪枝操作，縮小候選集的范圍。

本文考慮到區分屬性的重要性程度，因此引入權重支配分數上界，記作MaxWeightGrade，根據上界值判斷對象是否能被提前剪枝，從而減少計算權重支配分數的對象數量，以提高查詢效率。

引理1權重支配分數上界（MaxWeightGrade）。在一個屬性維度集合為D（|D|=d）的不完整數據集S上，給定一個對象o∈S，令Fi（o）表示在第i維上被對象o支配的對象集合，即

Fi（o）={o*∈S-o|o［i］≤o*［i］或o*［i］不存在}i∈Dset（o）

Si∈D-Dset（o）

其中：Dset（o）為對象o的屬性值存在的維度集合，在對象o的屬性值缺失的每一個維度上，認為o支配S中除o外的所有對象，不具有計算意義。基于Fi（o）得到的支配對象集合，對象o在每個維度上的權重支配分數為

WGi（o）=Num1（i）*wi+Num2（i）*λ*wii∈Dset（o）

0i∈D-Dset（o）

基于各維度的權重支配分數WGi（o），對象o的權重支配分數上界為MaxWeightGrade（o）=∑i∈DWGi（o）。

證明首先證明在每一個屬性維度上的|Fi（o）|是對象o實際支配的對象數量N（o）的上界，a）當iDset（o）時，顯然|Fi（o）|=|S|是N（o）的上界。b）當i∈Dset（o）時，Fi（o）包含所有在第i維上不比o［i］好的對象以及第i維上的屬性值缺失的對象，所以|Fi（o）|是N（o）的上界。其次，由于Fi（o）包含所有可能被o支配的對象，那么顯然|Fi（o）|≥|N（o）|，所以顯然各維度WGi（o）之和大于等于WeightGrade（o）。

以表4的樣本數據集示例，計算對象B3（9，4，-，-）的權重支配分數上界MaxWeightGrade（B3）。

F2（B3）=A1，A2，A3，A4，A5，B4，B5，C1，C3，C4，C5，D1，D2，D3，D4，D5

其中：{B4，B5，C1，C3，C4，C5}這6個對象在第2維上的屬性值存在；{A1，A2，A3，A4，A5，D1，D2，D3，D4，D5}這10個對象在第2維上的屬性值缺失，因此Num1（2）=6，Num2（2）=10。F1（B3）=，由于B3［3］和B3［4］缺失，所以F3（B3）=S，F4（B3）=S。由此可得WG1（B3）=0，WG2（B3）=6*w2+10*λ*w2，WG3（B3）=0，WG4（B3）=0。所以MaxWeightGrade（B3）=6*w2+10*λ*w2。

2.6基于上界值剪枝思想的USTD查詢

由權重支配分數上界的引理，本文給出依據MaxWeightGrade進行剪枝操作的方法，并論證基于上界值剪枝的可行性。

啟發式1基于上界值剪枝。 在一個屬性維度集合為D（|D|=d）的不完整數據集S上，令SC為USTD查詢的k個候選對象的集合，即|SC|=k，令τ是SC中所有對象中的最小權重支配分數。對于c∈SC，WeightGrade（c）≥τ，c*∈SC，WeightGrade（c*）=τ。對于S中的數據對象o∈S，若MaxWeightGrade（o）≤τ，則對象o可以被剪枝，提前終止計算其權重支配分數。

證明首先，c∈SC，WeightGrade（c）≥τ，當對象o∈S-SC時，若MaxWeightGrade（o）≤τ，由于WeightGrade（o）≤MaxWeightGrade（o）≤τ，所以c∈SC，WeightGrade（o）≤WeightGrade（c）。其次，|SC|=k，當對象o的MaxWeightGrade（o）≤τ時，對象o不比SC中的任意一個對象好，即有k個對象的分數高于o，故對象o可以被安全地剪枝。

基于上述定義和引理，將剪枝操作融入USTD查詢過程中，進一步給出基于上界值剪枝思想的USTD算法的偽代碼如算法1所示。

算法1基于上界值剪枝的用戶敏感TKD算法（USTD）

輸入：屬性維度集合為D（|D|=d）的不完整數據集S；參數k；將所有對象按其MaxWeightGrade由大到小排列的隊列Q。

輸出：USTD查詢在數據集S上的結果集合SR。

1初始化設置候選集SC←，結果集SR←，τ←-1

2for （any 對象o in Q） do

3o←dequeue（Q）

4if （MaxWeightGrade（o）≤τ） then

5break

6else

7WeightGrade（o）←CalculateGrade（o）

8if （WeightGrade（o）gt;τ "or τlt;0） then

9 將對象o加入候選集SC中

10if （|SC|gt;k） then

11從SC中刪去WeightGrade（o*）=τ的對象o*

12if （|SC|=k） then

13τ←min{WeightGrade（c）|c∈SC}

14return SR←SC

首先，對不完整數據集S上的所有對象，根據引理1，獲取權重支配分數上界MaxWeightGrade，將對象按照MaxWeightGrade由大到小排列，作為訪問的隊列Q。輸入S、Q和參數k，算法設置候選集SC和結果集SR，初始化為空集，并設置τ為SC中所有對象的最小分數，初始化為-1，當集合SC中少于k個對象時，τ保持為-1。然后，算法依次訪問隊列Q中的對象，將Q中的頂端對象o出隊，若MaxWeightGrade（o）gt;τ，則對象o可以被剪枝，滿足提前終止條件，結束for循環（算法第4、5行），此時，由于Q是按照MaxWeightGrade降序排列，所以Q中剩余的所有對象的分數都不大于τ。如果MaxWeightGrade（o）gt;τ，不滿足提前終止條件，則算法調用CaculateGrade函數開始計算對象o的實際權重支配分數WeightGrade（o），并維護候選集SC（算法第7～13行）。具體地，如果τ=1，說明此時SC中對象不足k個，則將對象o直接插入到候選集SC中；如果WeightGrade（o）gt;τ，說明SC中已有k個對象，則刪除SC中分數最小的對象，并將對象o插入到SC中，同時更新τ為當前SC中所有對象的最小分數。

為了說明對象o的實際權重支配分數WeightGrade（o）的計算，基于定義3，給出CalculateGrade函數的偽代碼，如算法2所示。

算法2CalculateGrade（o）

輸入：當前計算的對象o；屬性維度集合為D（|D|=d）的不完整數據集S；屬性維度權重向量W=（w1，w2，…，wd）；參數λ。

輸出：對象o的權重支配分數WeightGrade（o）。

1初始化設置向量Num1［］←［0］*d，Num2［］←［0］*d

2for （any 對象s in S and s≠o） do

3control←1

4for （any i in D） do

5if （s［i］缺失and o［i］缺失） then

6continue

7elif （s［i］缺失 or o［i］缺失） then

8continue

9elif （s［i］比o［i］好） then

10o不支配s，break

11else （s［i］比o［i］差） then

12control←true

13if （control為true） then

14o支配s

15for （any i in Dset（o）） then

16if （s［i］存在） then

17Num1［i］←Num1［i］+1

18else

19Num2［i］←Num2［i］+1

20WeightGrade（o）←∑i∈Dset（o）（Num1［i］*wi+Num2［i］*λ*wi）

21return WeightGrade（o）

首先，將需要計算分數的對象o和具有d維屬性的不完整數據集S輸入，設置一個參數λ（0lt;λlt;1）和一個長度為d的權重向量W=（w1，w2，…，wd）。算法設置兩個長度為d的向量Num1和Num2，分別記錄被對象o所支配的對象在Dset（o）的維度上，有屬性值的數量和缺失屬性值的數量，初始化向量值均為0。然后，算法依次訪問S中除o外的所有對象，根據兩兩支配關系統計被對象o支配的對象（算法第5～12行），若對象o*被支配，依次訪問對象o*的所有Dset（o）屬性維度i，若o*［i］存在，則Num1［i］加1，否則，Num2［i］加1（算法第13～19行）。當判斷完所有被對象o支配的對象集合后，根據權重支配分數定義3，計算對象o的權重支配分數WeightGrade（o）。

以表4的樣本數據集示例，演示采用USTD算法查詢前兩個結果的過程，在此樣本數據集上認為每個維度上的屬性值越小越好。屬性維度的權重向量設為W=（2，1，1，0.5），λ=0.4。按MaxWeightGrade降序排列對象的隊列Q如表5所示。

算法首先依次訪問Q中的前兩個對象A2和A3，加入候選集SC中，此時SC={A2，A3}，τ=32.2。然后訪問Q中的第三個對象B1，由于MaxWeightGrade（B1）=49.0gt;τ，所以進一步計算WeightGrade（B1）=40.2gt;τ，此時SC中已有兩個對象，所以將B1加入SC，把WeightGrade（A3）=32.2=τ的對象A3從SC中刪除，此時SC={A2，B1}，τ=40.2。繼續訪問Q中的對象C2，C3，D3，A1，D1，由于它們的上界值均大于τ，所以進一步計算它們的權重支配分數，由于WeightGrade均小于τ，所以不加入候選集SC中，候選集仍保持為SC={A2，B1}。繼續訪問Q中的對象B2，由于MaxWeightGrade（B2）=37.0lt;τ，滿足提前終止條件，所以最終返回的結果集合SR={A2，B1}。

2.7算法復雜度分析

首先，計算權重支配分數上界MaxWeightGrade，由引理1可知，對每一個對象，在所有維度上需要執行O（N）操作，因此，計算每個對象上界值的復雜度為O（Nd）。數據集S中有N個對象，計算S上所有對象的權重支配分數上界MaxWeightGrade獲取優先訪問隊列Q，其復雜度為O（N2d）。

其次，算法1執行USTD查詢過程。從隊列Q中依上次訪問對象o，若對象o滿足剪枝條件，則提前終止算法；若不滿足，則進一步計算對象的權重支配分數。最好情況下，計算k個對象的權重支配分數；最壞情況下，計算N個對象的權重支配分數。

算法2計算對象o的權重支配分數WeightGrade。最好情況下，算法復雜度為O（1）；最壞情況下，對象o在所有維度上沒有缺失的屬性值，即Dset（o）=D，需要比較的維度數量為|D|=d，并且對象o支配數據集S上其他所有對象，則對于其他的（N-1）個對象，需要在所有屬性維度上進行比較并統計缺失情況，因此算法2的復雜度為O（Nd）。總的來說，USTD算法消耗O（N2d）時間優先訪問隊列Q的機會，在最壞情況下依次訪問N個對象并計算其權重支配分數，復雜度為O（N2d）。因此，該算法最終時間復雜度為O（N2d）。

3實驗及結果分析

基于以上算法，本文設計實驗從多個方面評估USTD算法的性能和效果。實驗主要關注結果集大小k，不完整數據集的基數N，屬性維度數量d等多個因素對算法性能的影響，通過將USTD算法和UBB、BIG、WTKD算法進行比較，評估算法的查詢效率和算法返回的查詢結果的可靠性，表6列出了本文實驗進行比較的算法。

本實驗使用兩個數據集進行評估，分別是電影數據集MovieLens和全國主要城市的空氣質量數據。

MovieLens包含1 932部電影對象，每個對象具有60個維度，表示來自60個觀眾的評價，評分值從1到5，評分越高表示電影越值得推薦。電影數據集中僅有4 971個評分數據，缺失率為95.7%。對于電影評分數據，評分越高越值得推薦，所以在支配的定義中，屬性值應該是越大越好。對于電影數據集的用戶維度的權重，本文假設一個用戶需求情景：查詢18～24周歲年齡段的用戶最推薦的五部電影，因此用戶維度上的權重向量設置遵守以下規則，如表7所示：18～24歲的用戶對電影的評分對滿足用戶需求的查詢最具有參考價值，此類用戶維度的權重設為2；18歲以下和25～34周歲的用戶較為靠近目標用戶的年齡，此類用戶維度的權重設置為1；35～49歲的用戶的維度權重設置為0.8；50歲以上的用戶維度的權重設為0.5。

對于全國主要城市的空氣質量數據，主要采集全國389個城市在2022年2月和3月共59天中的空氣質量指數。每個城市對象有59個維度的屬性值，表示每日的空氣質量指數（AQI）。由于數據采集和統計過程受多種因素影響，所以部分城市的日監測數據缺失，實驗數據集的缺失率為5.6%。AQI越低表示空氣質量越好，所以在支配的定義中，該數據的屬性值應該是越小越好。對于空氣質量數據，本文假設用戶需求情景為：查詢2022年春節期間空氣質量最好的五個城市，因此日期維度上的權重向量設置遵守以下規則，如表8所示：春節七天2月11日至2月17日的空氣質量指數對用戶需求的查詢最具有參考價值，此段日期維度的權重設為2；2月其他日期較為靠近目標日期，此段日期維度的權重設置為1；3月的日期維度權重設置為0.8。

實驗主機是16 GB RAM，Intel Core i5-1135G7 2.40 GHz四核CPU的PC機。操作系統為Microsoft Windows 10。算法由Python 3.8，在PyCharm Community環境中運行。

3.1算法性能分析

3.1.1查詢結果的大小k對響應時間的影響分析

本實驗在不同的結果集大小k下，對算法性能進行分析。實驗采用包含1 932部電影和60個用戶維度評分數據的電影數據集以及389個城市和59個日期維度的空氣質量數據集，結果集大小k的取值為［5，10，15，20］。λ設為0.4，屬性維度權重依據表7、8，其他參數保持不變。實驗對比USTD算法和UBB、BIG、WTKD算法，隨著k的變化，算法的響應時間如圖1所示。從圖1可以直觀地看出，在電影數據集和空氣質量數據集上，USTD平均運行時間最少，USTD的執行效率更高。由于數據集的部分缺失，所以UBB中許多對象的最大支配分數幾乎等于|S|，而其實際支配分數很小，導致剪枝效果很弱；BIG采用位圖索引維護一個更小的剪枝上界，增強了剪枝效果，算法效率顯著提升；WTKD和USTD算法在UBB剪枝操作的基礎上以不同方式應用了加權因子，WTKD的加權得分有較大區分，USTD依據最大權重支配分數進行剪枝，MaxWeightGrade有較大區分，因此較快達到剪枝條件，剪枝效果良好，提高算法的查詢效率。

隨著查詢結果的大小k增加，算法查詢的時間會增長，但從圖1可以看到，隨著k增加，可能會出現算法運行時間減少的情況。由于對象的最大權重支配分數MaxWeightGrade與實際權重支配分數WeightGrade有一定差異，當依據MaxWeightGrade選擇對象進入候選集后，可能會有WeightGrade更大的對象替代候選集中的對象。當k增加時，候選集擴大，反而可能減少了從候選集中刪除對象的情況，一方面降低更新候選集的消耗；另一方面更快達到剪枝條件從而提前終止運行，因此算法消耗的時間可能減少。這取決于每個數據集中對象的MaxWeightGrade和WeightGrade，不同數據集的對象支配情況和具體情景下維度權重的設置情況是其影響因素。

3.1.2數據集基數和屬性維度對響應時間的影響分析

本實驗在不同的數據集基數N或者用戶維度d下，對算法性能進行分析。實驗采用電影數據集和空氣質量數據集，電影數量N的取值為［20，100，500，1 000］，城市數量N的取值為［20，50，100，389］，用戶和日期維度d取值為［15，30，45，60］，k=5，λ設為0.4，屬性維度權重依據表7、8，其他參數保持不變。實驗對比USTD和UBB、BIG、WTKD算法，隨著N或d的變化，算法的響應時間如圖2、3所示。

從圖2、3可以看出，USTD的執行效率更高。當數據集基數和用戶維度數量很小時，四種算法所花費的時間差異不明顯；但隨著數據量的增加，在數據集基數或者用戶維度數量較大的情況下，USTD算法所花費的時間明顯更低。同時，隨著不完整數據集的基數N或者用戶維度數量d的增加，算法消耗的時間增長，但是USTD算法消耗時間的增長速度與BIG、WTKD算法相比不呈劣勢，與UBB算法相比優勢明顯。

3.2算法效果評估

在電影數據集中，評分反映了用戶對電影的喜愛程度，平均評分即為對應年齡段用戶對該電影的總體感受，平均評分越高，說明該年齡段的用戶對該電影認可度越高。在空氣質量數據集中，AQI反映了城市每天的空氣質量情況，AQI的平均值即為對應時間段內該城市的總體空氣質量，平均值越低說明這段時間該城市的空氣質量越好。USTD查詢方法的目的是盡可能滿足用戶需求，精確地找到在重要屬性維度上表現更好的對象，該方法分別依據用戶評分和空氣質量指數進行查詢，則查詢返回對象的平均評分或平均AQI越高，說明方法越好。

本實驗分別使用電影數據集和空氣質量數據集，比較USTD算法和UBB、BIG、WTKD算法查詢返回的結果集合的平均值，評估算法的效果。由于UBB和BIG沒有應用加權因子，均依據對象的支配分數Grade進行查詢，所以兩種算法查詢返回的結果一致。其中USTD算法中對屬性維度的權重值設置如表7、8所示，λ設為0.4。通過實驗，兩個算法分別查詢返回5、20、50個結果，本文統計了不同的結果數量下，兩種算法推薦的結果在所有屬性維度上的平均值和在用戶敏感的屬性維度上的平均值情況，如表9所示。

通過表9可以發現，針對電影數據集，評分越高越好，USTD算法推薦的電影在所有用戶維度上的整體平均評分與UBB/BIG、WTKD推薦電影的評分相差不大，WTKD為對象賦予權重，查詢的對象完整度更高；USTD為屬性維度賦予權重，查詢的對象在特定維度上更具有意義。由于USTD的推薦電影更傾向于特定用戶，針對本實驗假設的用戶需求情景，重點分析用戶感興趣的18～24歲用戶維度上的分值情況。由表9可以看到，USTD推薦的電影在18～24歲用戶中獲得的評分平均值顯著高于UBB/BIG的結果，并且與WTKD相比也具有一定優勢。對于空氣質量數據集，AQI值越低越好，在所有日期維度和春節的日期維度上，USTD推薦的城市的平均空氣質量均好于UBB/BIG、WTKD算法推薦的城市，尤其是在用戶感興趣的春節日期維度上，USTD推薦的結果顯著好于其他算法的結果。

因此在海量不完整數據集上，USTD相較于UBB、BIG、WTKD可以查詢得到更加滿足用戶需求、更具有影響力和意義的對象結果，為用戶后續的分析和決策提供更有效的支持。

4結束語

本文針對海量的不完整數據集上用戶個性化推薦問題，提出了一個基于上界值剪枝的用戶敏感TKD查詢方法（USTD）。該方法為屬性維度賦權，充分考慮到屬性值是否缺失和屬性維度權重的大小對數據對象的得分的影響，重新定義了數據對象的支配關系及其度量方法，并結合上界值剪枝的思想，減少計算分數的對象數量，高效返回k個權重支配分數最高、更具有影響力的數據對象結果，滿足用戶興趣。USTD適用于海量不完整數據集上的推薦查詢，具有較高的查詢效率，當然該算法的性能和效果方面仍有提升的空間，需要未來進一步探索。

參考文獻：

［1］Cismondi F，Fialho A S，Vieira S M，et al.Missing data in medical databases：impute，delete or classify？［J］.Artificial Intelligence in Medicine，2013，58（1）：63-72.

［2］Garcia C，Leite D，Skrjanc I.Incremental missing-data imputation for evolving fuzzy granular prediction［J］.IEEE Trans on Fuzzy Systems，2019，28（10）：2348-2362.

［3］Simone R.An accelerated EM algorithm for mixture models with uncertainty for rating data［J］.Computational Statistics，2021，36（1）：691-714.

［4］常巧珍，曹雋喆，顧宏，等.基于最近鄰區間的不完整基因表達數據多目標聚類算法［J］.大連理工大學學報，2021，61（4）：416-423.（Chang Qiaozhen，Cao Junzhe，Gu Hong，et al.Multi-objective clustering algorithm based on the nearest neighbor interval for incomplete gene expression data［J］.Journal of Dalian University of Technology，2021，61（4）：416-423.）

［5］Ilyas I F，Beskales G，Soliman M A.A survey of top-k query proces-sing techniques in relational database systems［J］.ACM Computing Surveys，2008，40（4）：1-58.

［6］Soundararajan R，Kumar S R，Gayathri N，et al.Skyline query optimization for preferable product selection and recommendation system［J］.Wireless Personal Communications，2021，117（4）：3091-3108.

［7］Papadias D.Progressive skyline computation in database systems［J］.ACM Trans on Database Systems，2005，30（1）：41-82.

［8］韓希先，李建中，高宏.一種有效的海量數據top-k Dominating查詢算法［J］.計算機學報，2013，36（10）：2132-2145.（Han Xixian，Li Jianzhong，Gao Hong.An efficient top-k dominating algorithm on massive data［J］.Chinese Journal of Computers，2013，36（10）：2132-2145.）

［9］Amagata D，Hara T，Onizuka M.Space filling approach for distributed processing of top-k dominating queries［J］.IEEE Trans on Know-ledge and Data Engineering，2018，30（6）：1150-1163.

［10］Miao Xiaoye，Gao Yunjun，Guo Su，et al.Incomplete data management：a survey［J］.Frontiers of Computer Science，2017，12（1）：4-25.

［11］Gao Yunjun，Miao Xiaoye，Cui Huiyong，et al.Processing k-skyband，constrained skyline，and group-by skyline queries on incomplete data［J］.Expert Systems with Applications，2014，41（10）：4959-4974.

［12］Gulzar Y，Alwan A A，Turaev S.Optimizing skyline query processing in incomplete data［J］.IEEE Access，2019，7（1）：178121-178138.

［13］Miao Xiaoye，Gao Yunjun，Zheng Baihua，et al.Top-k dominating queries on incomplete data［J］.IEEE Trans on Knowledge and Data Engineering，2016，28（1）：252-266.

［14］Ding Xiangwu，Yan Chao，Zhao Yuan，et al.Efficient processing of top-k dominating queries on incomplete data using MapReduce［C］//Proc of the 4th International Conference on Cloud Computing and Security.Berlin：Springer，2018：478-489.

［15］Wu J M T，Wei Min，Wu Mu’en，et al.Top-k dominating queries on incomplete large dataset［J］.The Journal of Supercomputing，2022，78（3）：3976-3997.

［16］Fattah H M A，Hasan K M A，Tsuji T.Weighted top-k dominating queries on highly incomplete data［J］.Information Systems，2022，107：102008.

收稿日期：2022-04-28；修回日期：2022-07-04基金項目：國家自然科學基金資助項目（71972102）；教育部人文社會科學研究規劃基金資助項目（19YJAZH100）；江蘇省高等學校自然科學研究重大項目（20KJA520002）；江蘇省高校優秀科技創新團隊（2021）

作者簡介：徐超（1980-），男，湖北紅安人，教授，碩導，博士，主要研究方向為大數據審計、區塊鏈審計；吳丹琪（1997-），女，安徽黃山人，碩士，主要研究方向為大數據審計；陳勇（1986-），男（通信作者），湖南冷水江人，高級工程師，碩導，博士，主要研究方向為大數據審計、區塊鏈審計（chenyong@nau.edu.cn）；雷錦濤（1997-），男，湖南長沙人，碩士，主要研究方向為大數據審計、區塊鏈審計．