基于聚集約束的不確定性數(shù)據(jù)Top—k查詢

占仟豪++劉斌

摘要：在對不確定性數(shù)據(jù)進(jìn)行Top-k查詢時(shí)，一般會附加一些我們已經(jīng)知道的聚集約束條件，該文主要闡述了在該條件下的不確定性數(shù)據(jù)的Top-k查詢問題。針對可能世界實(shí)例空間指數(shù)型增長的特點(diǎn)，該文借鑒了文獻(xiàn)中對可能世界實(shí)例采樣的優(yōu)化思想，通過定義U-Topk和U-kRanks兩種查詢類型，提出了具體的查詢新算法。實(shí)驗(yàn)結(jié)果表明，這種新的算法的查詢效率很高，而且可以處理大量的具有不明確性的數(shù)據(jù)集。

關(guān)鍵詞：不確定性數(shù)據(jù)；Top-k查詢；聚集約束；數(shù)據(jù)查詢

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）20-0014-03

1 引言

現(xiàn)階段，隨著技術(shù)的發(fā)展，在數(shù)據(jù)的采集方面和對數(shù)據(jù)的處理方面，人們的水平不斷加強(qiáng)。但是目前在一些領(lǐng)域，比如經(jīng)濟(jì)、軍事和物流等一些相關(guān)領(lǐng)域，會出現(xiàn)很多不確定性數(shù)據(jù)，這些不確定性數(shù)據(jù)對這些領(lǐng)域的發(fā)展有著關(guān)鍵性的作用[1]。近年來，針對不確定性數(shù)據(jù)Top-k查詢的研究也越來越多。運(yùn)用采樣的近似方法，極大地減少了可能世界實(shí)例的數(shù)模，從而實(shí)現(xiàn)查詢的優(yōu)化。然而對不確定性數(shù)據(jù)的Top-k查詢主要針對的都是存在級的不確定性數(shù)據(jù)，沒有專門針對基于聚集約束條件的Top-k查詢的研究。本文研究的是如何基于聚集約束條件更加高效的處理屬性級不確定數(shù)據(jù)的Top-k查詢問題。

2 對不確定性數(shù)據(jù)Top-k查詢的一些基本說明

2.1 可能世界模型

這個(gè)模型中，每個(gè)元組的組合都可以成為一個(gè)可能世界的具體例子，它的概率值可以通過該元組的概率來得出結(jié)果。在表1中，我們可以看到有3個(gè)元組，概率表示該元組的概率，但是元組之間它們的關(guān)系之間有兩種，依賴或者是獨(dú)立的。一我們設(shè)定元組是獨(dú)立的關(guān)系的時(shí)候，可以得出23=8個(gè)可能世界實(shí)例。這些實(shí)例的概率是由實(shí)例內(nèi)元組的概率相乘然后再與實(shí)例外元組的不發(fā)生的概率相乘而得到。就像，可能世界實(shí)例{1，2}的發(fā)生概率為。二當(dāng)設(shè)定元組是依賴關(guān)系的時(shí)候，元組1和元組3不能同時(shí)發(fā)生，那就會有6個(gè)實(shí)例。在這種情況下，可能世界實(shí)例{1，2}的發(fā)生概率為。

但是，在很多情況下，不確定性又可以分為兩種，一是存在級，二是屬性級。前者主要是說明元組是否存在，而后者沒有論述整個(gè)元組的不確定性，它是對某個(gè)特定對象來說明這個(gè)對象的不確定性，它主要是以概率密度函數(shù)或者是統(tǒng)計(jì)參數(shù)去說明的。

本文主要闡述的是對元組存在相互獨(dú)立的關(guān)系時(shí)的屬性級的不確定性數(shù)據(jù)方面的問題。

2.2 具體的應(yīng)用實(shí)例

比如，一個(gè)企業(yè)計(jì)劃向市場退出一個(gè)新的產(chǎn)品，這個(gè)企業(yè)邀請這方面的專業(yè)人士對某市的三個(gè)地區(qū)進(jìn)行市場調(diào)查，A、B、C，為了是確定這個(gè)產(chǎn)品在三個(gè)地區(qū)的大概要推出的數(shù)量，并把結(jié)果記錄下來。表2是預(yù)測的結(jié)果：

在上述表中，我們就可以用可能世界模型來進(jìn)行分析。A、B、C，三個(gè)組存在著相互獨(dú)立的關(guān)系，每個(gè)組都有3個(gè)可能存在的數(shù)值，然后得出總結(jié)果：可能世界實(shí)例。然后結(jié)合公司以前的銷售經(jīng)驗(yàn)，可以得出該市下個(gè)月的總的銷量在[6000，6400]之間，但是在實(shí)際情況下，會考慮一些情況。第一種情況：如果我們預(yù)測范圍正確的話，那A、B、C，三個(gè)地區(qū)哪個(gè)是最多的？可以達(dá)到多少？第二種情況：還是在我們對總銷量預(yù)測范圍正確的前提下，那這個(gè)總銷量的具體數(shù)值應(yīng)該是多少？第一種，第二種這兩種情況的查詢，都屬于對不確定性數(shù)據(jù)的Top-k查詢，但是它們的排序標(biāo)準(zhǔn)不同，一是按銷量，二是按概率?；卮鹕鲜龅膬蓚€(gè)查詢，方法一：先列舉所有可能世界實(shí)例，然后對整個(gè)可能世界實(shí)例空間直接進(jìn)行查詢。方法二：如果先考慮一些制約條件的話，那就會有一個(gè)結(jié)果，針對27個(gè)可能世界實(shí)例中，只有下面3個(gè)是滿足條件的例子：w1=<2000，2000，2100>，w2=<2000，2000，2400>，w3=<2100，2000，2100>，且概率P（w1）=0.006，P（w2）=0.004，P（w3）=0.018。對這三個(gè)實(shí)例進(jìn)行查詢，可以得出結(jié)論為：第一種情況下為C區(qū)，銷量為2400，第二種情況下最有可能銷量為6200件（因?yàn)镻（w3）最大）。

根據(jù)上面所列舉的例子，我們看到很容易得出一些結(jié)論，但是上述數(shù)據(jù)的規(guī)模是很小的，但是在一些實(shí)際情況下，數(shù)據(jù)都是很龐大的，如果存在一個(gè)不確定數(shù)據(jù)集有10000個(gè)元組，然后每個(gè)組中有3個(gè)可能的值，那么實(shí)例為。針對這種很大的數(shù)據(jù)集，第一種方法是行不通的，方法二通過簡化查詢的可能世界實(shí)例空間，雖然是一種非精確的方法，但是可以滿足查詢的要求。為了最大的提高查詢效率，如何最快最準(zhǔn)的找出滿足約束條件的可能世界實(shí)例是問題的關(guān)鍵。

3 對問題形式的一些說明和所建立的模型

3.1 可能世界模型說明

3.2 對聚集條件的描述說明

現(xiàn)在是對4個(gè)SQL語言的操作：SUM，MAX，MIN和AVG。其中形式描述如下：，在這個(gè)描述中R是與該條件有關(guān)的但不確定的數(shù)據(jù)集，T是該類型，a和b各是聚集條件的上限和下限。

3.3 查詢語義的定義

這兩個(gè)查詢U-kRank和 U-Topk，它們是大不相同的，其中U-Topk的結(jié)果是以向量k的形式所表現(xiàn)的，而這個(gè)k會在可能世界的最前列。在可能世界對元組的排序中，是根據(jù)分值不同的大小來排列的，這說明每個(gè)元組都是不相同的。而在U-kRank中，某一個(gè)元組可以重復(fù)出現(xiàn)，這是U-kRank所允許的。

4 問題解決方法

本文借鑒文獻(xiàn)2中使用的馬爾科夫鏈蒙特卡洛（MCMC）采樣方法，先利用已知的聚集約束條件對整個(gè)可能世界實(shí)例空間進(jìn)行采樣，得到一個(gè)規(guī)模較小的滿足條件的可能世界實(shí)例數(shù)據(jù)集，然后在對采樣后的數(shù)據(jù)集進(jìn)行Top-k查詢。

4.1 獲取滿足約束的數(shù)據(jù)集

實(shí)際上，從一個(gè)已知的合格點(diǎn)X出發(fā)，通過改變X中某一個(gè)或幾個(gè)元組的屬性值，得到一個(gè)新的可能世界實(shí)例仍然極有可能滿足所有約束條件。運(yùn)用馬爾科夫鏈蒙特卡洛（MCMC）方法，經(jīng)過有限步的采樣，就可以得到滿足所有約束條件的可能世界實(shí)例數(shù)據(jù)集。

在可能世界空間中，滿足約束的可能世界實(shí)例都會相鄰而存在，形成一塊塊的合格區(qū)域。即某一個(gè)點(diǎn)滿足約束，改變該點(diǎn)某幾個(gè)元組的值通常也會滿足約束條件。例如，可能世界實(shí)例X滿足所有的約束條件，不妨稱X為一個(gè)合格點(diǎn)，如果可能世界實(shí)例Y與X非常的相似，那么Y也極有可能是一個(gè)合格點(diǎn)。MCMC方法便是利用了這一特性來對可能世界空間進(jìn)行采樣，因此該方法可以分為兩個(gè)階段：

第一階段：尋找一個(gè)滿足約束的初始合格點(diǎn)

1）隨機(jī)生成一個(gè)可能世界實(shí)例，逐一將各個(gè)約束條件去判斷該點(diǎn)是否滿足，如果都滿足，則該點(diǎn)就是初始合格點(diǎn)；如果該點(diǎn)所有元組值的和小于該約束的下限，則對該點(diǎn)的元組需要調(diào)大投票，如果所有元組值的和大于該約束的上限，則對元組需要調(diào)小投票。

2）根據(jù)元組的得票，調(diào)整各候選值的隨機(jī)選中概率。即如果某個(gè)元組的需要調(diào)大得票高，則增大該元組候選值中比初始值大的候選值的概率；需要調(diào)小的得票高，則增大比初始值小的候選值的概率。

3）對調(diào)整概率后的各個(gè)元組，重新隨機(jī)選擇候選值得到一個(gè)新的點(diǎn)，如果該點(diǎn)滿足所有約束，則返回該點(diǎn)為初始合格點(diǎn)；如果不滿足轉(zhuǎn)4。

4）按1中的規(guī)則進(jìn)行投票，對得票最高的元組進(jìn)行候選值調(diào)整，得到新的點(diǎn)。判斷該點(diǎn)是否滿足所有約束條件，滿足即返回該點(diǎn)為初始合格點(diǎn)。如果不滿足轉(zhuǎn)5。

5）重復(fù)步驟4一定次數(shù)，如果仍得不到合格點(diǎn)，則返回錯(cuò)誤信息。

第二階段：從初始合格點(diǎn)出發(fā)進(jìn)行采樣

1）從初始點(diǎn)出發(fā)，隨機(jī)選取s（稱為步長）個(gè)元組，改變選中的元組的值，隨機(jī)選擇與原來值大小相鄰的值中的一個(gè)，得到一個(gè)新的狀態(tài)點(diǎn)。

2）判斷新的點(diǎn)是否滿足所有約束條件，滿足則采集該點(diǎn)為馬爾科夫鏈的下一個(gè)狀態(tài)點(diǎn)；不滿足則依據(jù)Metropolis-Hastings采樣規(guī)則以一定的概率接受該點(diǎn)為下一個(gè)狀態(tài)點(diǎn)。

3）重復(fù)步驟1和2，直到采集到足夠的合格樣本點(diǎn)。

4.2 查詢一些采集的數(shù)據(jù)集

這些采集的數(shù)據(jù)集都要進(jìn)行兩種查詢，分別是U-Topk和U-kRanks，從下面可以看出各自的算法，

U-Topk算法

5 它的實(shí)驗(yàn)應(yīng)用

MATLAB的運(yùn)用可以對上面提到的算法進(jìn)行去實(shí)現(xiàn)，Windows XP系統(tǒng)是它的運(yùn)行系統(tǒng)，Intel Core 2 CPU（6400 2.13GHz），它的內(nèi)存是1GB.

5.1 它的實(shí)驗(yàn)中的數(shù)據(jù)

它的實(shí)驗(yàn)中的數(shù)據(jù)集采用的是一種模擬數(shù)據(jù)，這種模擬數(shù)據(jù)是由計(jì)算機(jī)生成的，這些數(shù)據(jù)集中的每個(gè)元組都包括4個(gè)在[0，100]之間生成的一些候選值，而這些值具有隨機(jī)性。假設(shè)元組的個(gè)數(shù)為N，這個(gè)N可以設(shè)為1K、10K、20K，組成三個(gè)大小不一樣的數(shù)據(jù)集。然后還有4個(gè)聚集約束條件，可以寫成一種矩陣的形式來表示：。這4個(gè)條件約束的元組都是不同的，第一個(gè)是第0到0.4N個(gè)元組，第二個(gè)是第0.2N到0.6N個(gè)元組，第三個(gè)是第0.4N到0.8N元組，第四個(gè)是第0.6N到第N個(gè)。

5.2它的實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)進(jìn)行的過程中，先針對不同大小的三個(gè)數(shù)據(jù)集，分別進(jìn)行U-Topk和U-kRanks查詢，實(shí)驗(yàn)中參數(shù)k=3，采樣鏈mclength=1000，得到實(shí)驗(yàn)結(jié)果如下表所示：

從表3和表4我們可以發(fā)現(xiàn)，兩種查詢消耗的時(shí)間都在幾秒到幾十秒之間，相對于直接對整個(gè)可能世界空間查詢效率有很大的提高。況且當(dāng)N=10K時(shí)，可能世界實(shí)例總數(shù)將達(dá)到個(gè)，利用窮舉的方法根本不可能得到查詢結(jié)果。

6 結(jié)論

綜上所述，本文主要是討論了對在聚集約束條件下對一些不確定性的數(shù)據(jù)Top-k的查詢方面的問題，然后分析了一些目前的查詢方法，借鑒文獻(xiàn)2中的采樣思想，提出了針對不確定性數(shù)據(jù)的U-Topk和U-kRanks查詢的新的計(jì)算方法。而且通過實(shí)驗(yàn)可以看出，這兩個(gè)新的算法可以對一些大規(guī)模的不確定的數(shù)據(jù)進(jìn)行處理，并且查詢效率相對于傳統(tǒng)方法有很大的提高。

參考文獻(xiàn)：

[1] 周傲英，金澈清，王國仁，李建中. 不確定性數(shù)據(jù)管理技術(shù)研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào)，2009，31（1） .

[2] Mohan Yang， Haixun Wang， Haiquan Chen， Jeff Ku. Querying Uncertain Data with Aggregate Constraints [C]. SIGMOD. Athens，Greece： 2011.

[3] Todd J.Green， Val Tannen. Models for incomplete and probabilistic information [C]. IEEE Date Engineering Bulletin. 2006.

[4] Nilesh Dalvi， Dan Sucin. Efficient Query Evaluation on Probabilistic Databases[J]. VLDBJ，2007，16（4） .