莊志惠,　岑　健,　劉　娟，　趙　曉，　王藝璇

(1.廣東技術(shù)師范學(xué)院自動化學(xué)院,廣州 510665； 2.國網(wǎng)南陽供電公司,河南 南陽 473000)

0　引　言

傳統(tǒng)的技術(shù)對于不確定性數(shù)據(jù)的處理效率低下，這使得研究人員都致力于設(shè)計新的數(shù)據(jù)管理技術(shù)應(yīng)用到不確定性數(shù)據(jù),根據(jù)數(shù)據(jù)特點(diǎn)的區(qū)別[1-4]，針對一些結(jié)構(gòu)特性的不確定數(shù)據(jù)給出了相應(yīng)的處理模型;依據(jù)數(shù)據(jù)特點(diǎn)的區(qū)別，針對一些結(jié)構(gòu)特性的不確定數(shù)據(jù)給出了相應(yīng)的處理模型;針對時間快速流動的數(shù)據(jù)，設(shè)計了滑動窗口模型；針對不同語義與應(yīng)用背景的多種查詢方法設(shè)計了如：Top-k與Skyline等查詢方法[5-9]。近2年來隨著研究的不斷深入，不確定數(shù)據(jù)方面的研究水平有了顯著改進(jìn)，而與此同時隨著各種模型與查詢方法的設(shè)計與改進(jìn)，其處理的效果也有很大的提升[10-12]。然而如數(shù)據(jù)測量有誤，影響到整個傳輸過程等；相關(guān)人員沒有準(zhǔn)確的處理數(shù)據(jù)等方面的問題依然需要進(jìn)一步發(fā)展，在相關(guān)學(xué)術(shù)界的研究中發(fā)現(xiàn)在不確定數(shù)據(jù)元組的數(shù)目很大時，現(xiàn)有的發(fā)展模型基本上不可能得到有效的查詢結(jié)果[13,5,7]，本文基于這一方向的考慮，進(jìn)一步改進(jìn)不確定數(shù)據(jù)Top-k查詢的有效結(jié)果，采用控制集合方法完成了不確定數(shù)據(jù)查詢算法的改進(jìn)及優(yōu)化驗證，這一研究對于大元組不確定的數(shù)據(jù)管理具有顯著的理論和實踐價值。

1　控制集合方法實現(xiàn)算法的改進(jìn)設(shè)計

U-Topk、Uk-Ranks、PT-k以及Pk-Topk是當(dāng)前不確定數(shù)據(jù)的4種Top-k查詢算法，這4種算法的共同點(diǎn)是要將數(shù)據(jù)元組中最大分值的k個找出，不同的是它們在語義上和處理方式是有區(qū)別的，各有各的特點(diǎn)。與最初的處理方法相比，這幾種方法的處理效果確實有很大的提升，但是仍有一些地方還需要改進(jìn)，這里主要針對PT-Tok查詢算法進(jìn)行改進(jìn)。

1.1　改進(jìn)算法的數(shù)據(jù)查詢

普通關(guān)系的數(shù)據(jù)查詢是對數(shù)據(jù)進(jìn)行精確或完全相同的查詢處理，而DRA關(guān)系的查詢則有所不同，它的相關(guān)查詢是基于數(shù)據(jù)庫存在不確定性，所查詢的對象是不確定性數(shù)據(jù)。精確查詢與設(shè)計的DRA查詢是設(shè)計的DRA模型兩種的查詢操作，精確查詢所指的是在設(shè)計的DRA關(guān)系R=(U,B,V,M)中，設(shè)定y為此關(guān)系中所要查詢的目標(biāo)，查詢結(jié)果可分為兩種，即典型結(jié)果集合M與邊界結(jié)果集合N：M(y)=Gd([y]),N(y)=Bv([y])；而另一種查詢操作則指的是在設(shè)計的DRA關(guān)系R=(U,B,V,M)中，設(shè)定y依然是此關(guān)系中所要查詢的目標(biāo)，查詢結(jié)果一樣可分為兩種，即典型結(jié)果集合M與邊界結(jié)果集合N：M(y)={Gv([y]):[y]?Cy}，N(y)={Nv([y]):[y]?Nn(y)}。

1.2　PT-Tok查詢中算法實現(xiàn)過程

表1　相互獨(dú)立的不確定數(shù)據(jù)元組

這里以上表中的數(shù)據(jù)進(jìn)行算法設(shè)計的實現(xiàn)過程分析。根據(jù)大小對幾率值進(jìn)行排序，從而得出PT-k的結(jié)果。

(1)

(2)

(3)

根據(jù)上述算法改進(jìn)設(shè)計,表1中的數(shù)據(jù)便可獲得表2的結(jié)果。

表2　PT-k查詢處理結(jié)果

2　實驗設(shè)計驗證

以下是采用上述模型城市的負(fù)荷數(shù)據(jù)天氣進(jìn)行實驗應(yīng)用。

2.1　城市負(fù)荷預(yù)測應(yīng)用結(jié)果

這里針對20天的城市的負(fù)荷數(shù)據(jù)天氣特征值進(jìn)行低21天的數(shù)據(jù)預(yù)測，圖1所示算法數(shù)據(jù)應(yīng)用預(yù)測結(jié)果，圖2則相應(yīng)給出了實際情況的預(yù)報誤差，實際例證結(jié)果表明,算法訓(xùn)練速度快、時間短、收斂效果好。為了進(jìn)一步詳細(xì)說明算法設(shè)計的有效價值及應(yīng)用效果，下面通過java進(jìn)行虛擬實驗對比及詳細(xì)分析。

圖1　預(yù)測結(jié)果

圖2　預(yù)報誤差

2.2　jav數(shù)據(jù)的算法實驗對比

2.2.1實驗數(shù)據(jù)

對java中的random函數(shù)進(jìn)行調(diào)用而隨機(jī)生成的實驗數(shù)據(jù)，其分值范圍為0～2 000，概率值范圍為0～1。由于在可能世界實例中，分值一樣的情況無法對排序進(jìn)行明確，因此在當(dāng)前的研究中，兩個獨(dú)立的元組有著一樣的分值的情況并不在考慮之列。故這里所研究的情況并未將分值相等考慮其中，實驗中所采用的數(shù)據(jù)表一共有100張，其中有10份數(shù)據(jù)是元組個數(shù)，分別為：100，200，300，400，500，600，700，800，900，1 000；而這10份數(shù)據(jù)實驗結(jié)果的平均值即為該實驗結(jié)果。

2.2.2實驗對比結(jié)果

圖3所示為查詢在數(shù)據(jù)量與k值不同的情況下，所獲得的控制集合中元組的數(shù)目，由圖4可知，隨著數(shù)據(jù)量的增大控制集合的數(shù)目也有不太明顯的變化(稍增)，因為即便原始數(shù)據(jù)有所增大因為上文中已經(jīng)對控制集合以外的元組成為查詢結(jié)果的可能性為0進(jìn)行了論證，因此當(dāng)控制集合較小時，該方法的的優(yōu)勢更為明顯。

圖3　控制集合的數(shù)據(jù)量

圖4、5所表示的是采用DRA方法，當(dāng)k保持不變時，查詢的結(jié)果也會保持不變，數(shù)據(jù)更新對查詢結(jié)果無影響的概率則是1—194 860/200 000=2.57%。由圖可以看到，控制集合中的元組隨著k值的增大而變大，查詢結(jié)果受影響的概率降低。

圖4k不同時更新數(shù)據(jù)需要重查的概率

圖5數(shù)據(jù)量不同時更新數(shù)據(jù)需要重查的概率

圖6所示為采用現(xiàn)有方法與改進(jìn)后的方法處理PT-k查詢時所需處理的平均元組數(shù)。由圖6可知，這兩種方法的差距隨著數(shù)據(jù)量的變大而變大，造成這種現(xiàn)象的主要原因是使用現(xiàn)有的方法需對所有元組成為PT-k結(jié)果的可能性進(jìn)行計算，接著再將成為PT-k查詢結(jié)果不小于閾值P的概率值取出，再根據(jù)由大到小的順序?qū)@些概率值進(jìn)行排序,而相應(yīng)的元組也就是最后的查詢結(jié)果，而改進(jìn)后的方法在閾值P>0.25時控制集合中比閾值p小的元組概率值是無需考慮的，這是由于PT-k查詢所要查找的是在全部可能世界實例中排在前k位的概率總和不小于閾值P的元組，而任一元組排在全部可能世界實例中前k位的概率總和不可能大于這一元組的存在性概率值，因此，存在性概率值比閾值P小的元組成為PT-k的查詢結(jié)果是不存在的，前面已經(jīng)對僅在查詢閾值比0.25大的情況進(jìn)行了論證，PT-k查詢只能用于基于控制集合的方法，故如果閾值超過0.25，控制集合中可能成為PT-k的查詢結(jié)果僅僅是存在性概率值比0.25大的元組。實驗室中分別將0.3、0.5、0.7作為3個閾值，因為所取閾值不一樣，所需計算的元組也會有所變化，但比現(xiàn)有方法所處理的元組數(shù)要少的多，因此，圖中所顯示的這3種情況差不多。

圖6　數(shù)據(jù)量不同時對PT-k查詢的影響

3　結(jié)　語

對于不確定數(shù)據(jù)，相關(guān)研究人員已經(jīng)提出了許多數(shù)據(jù)模型。而這些數(shù)據(jù)模型的共同點(diǎn)就是其核心思想都是基于可能世界模型而產(chǎn)生的。所謂的可能世界實例指的是可能世界模型由一個或一個以上的不確定數(shù)據(jù)源演化為多個確定的數(shù)據(jù)庫實例，其中全部實例的幾率總和為1。雖然可以先對每個實例的查詢結(jié)果進(jìn)行分別計算，再將中間結(jié)果合并從而得到最終查詢結(jié)果，但可能世界實例比不確定性數(shù)據(jù)庫的規(guī)模要大的多，因此，該方法并不適用。本文對此作了具體說明，將100份數(shù)據(jù)結(jié)果的平均值作為實驗結(jié)果，同時，對現(xiàn)有方法進(jìn)行了全面的對比，這樣可更加客觀的對該方法的改進(jìn)進(jìn)行評價。

參考文獻(xiàn)(References)：

[1]陳愛東,劉國華,肖瑞,等. 均勻分布下不確定數(shù)據(jù)的關(guān)聯(lián)規(guī)則變粒度查詢[J]. 計算機(jī)工程與科學(xué),2013(10):79-88.

[2]陳愛東,劉國華,費(fèi)凡,等. 滿足均勻分布的不確定數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法[J]. 計算機(jī)研究與發(fā)展,2013(S1):186-195.

[3]黃娜,王洪濤,范辭冬,等. 基于不確定度和敏感度分析的LCA數(shù)據(jù)質(zhì)量評估與控制方法[J]. 環(huán)境科學(xué)學(xué)報,2012(6):1529-1536.

[4]王意潔,李小勇,祁亞斐,等. 不確定數(shù)據(jù)查詢技術(shù)研究[J]. 計算機(jī)研究與發(fā)展,2012(7):1460-1466.

[5]祁亞斐,王意潔,李小勇. 基于高斯模型的不確定數(shù)據(jù)流Skyline查詢方法[J]. 計算機(jī)研究與發(fā)展,2012(7):1467-1473.

[6]周遜,李建中,石勝飛. 不確定數(shù)據(jù)上兩種查詢的分布式聚集算法[J]. 計算機(jī)研究與發(fā)展,2010(5):762-771.

[7]王悅,唐常杰,楊寧,等. 在不確定數(shù)據(jù)集上挖掘優(yōu)化的概率干預(yù)策略[J]. 軟件學(xué)報,2011(2):285-297.

[8]汪金苗,張龍波,鄧齊志,等. 不確定數(shù)據(jù)頻繁項集挖掘方法綜述[J]. 計算機(jī)工程與應(yīng)用,2011(20):121-125.

[9]白梅,信俊昌,東韓,等. 不確定數(shù)據(jù)流上的概率反輪廓查詢處理[J]. 計算機(jī)研究與發(fā)展,2011(10):1842-1849.

[10]孫永佼,袁野,王國仁. P2P環(huán)境下面向不確定數(shù)據(jù)的Top-k查詢[J]. 計算機(jī)學(xué)報,2011(11):2155-2164.

[11]王爽,王國仁. 面向不確定感知數(shù)據(jù)的頻繁項查詢算法[J]. 計算機(jī)學(xué)報,2013(3):571-581.

[12]蔣濤,高云君,張彬,等. 不確定數(shù)據(jù)查詢處理[J]. 電子學(xué)報,2013(5):966-976.

[13]盧鑫,陳華輝,董一鴻,等. MapReduce框架下的不確定數(shù)據(jù)Top-k查詢計算[J]. 模式識別與人工智能,2013(7):695-704.