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

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

0　引　言

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

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

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

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

普通關(guān)系的數(shù)據(jù)查詢是對(duì)數(shù)據(jù)進(jìn)行精確或完全相同的查詢處理，而DRA關(guān)系的查詢則有所不同，它的相關(guān)查詢是基于數(shù)據(jù)庫(kù)存在不確定性，所查詢的對(duì)象是不確定性數(shù)據(jù)。精確查詢與設(shè)計(jì)的DRA查詢是設(shè)計(jì)的DRA模型兩種的查詢操作，精確查詢所指的是在設(shè)計(jì)的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è)計(jì)的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查詢中算法實(shí)現(xiàn)過(guò)程

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

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

(1)

(2)

(3)

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

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

2　實(shí)驗(yàn)設(shè)計(jì)驗(yàn)證

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

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

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

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

圖2　預(yù)報(bào)誤差

2.2　jav數(shù)據(jù)的算法實(shí)驗(yàn)對(duì)比

2.2.1實(shí)驗(yàn)數(shù)據(jù)

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

2.2.2實(shí)驗(yàn)對(duì)比結(jié)果

圖3所示為查詢?cè)跀?shù)據(jù)量與k值不同的情況下，所獲得的控制集合中元組的數(shù)目，由圖4可知，隨著數(shù)據(jù)量的增大控制集合的數(shù)目也有不太明顯的變化(稍增)，因?yàn)榧幢阍紨?shù)據(jù)有所增大因?yàn)樯衔闹幸呀?jīng)對(duì)控制集合以外的元組成為查詢結(jié)果的可能性為0進(jìn)行了論證，因此當(dāng)控制集合較小時(shí)，該方法的的優(yōu)勢(shì)更為明顯。

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

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

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

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

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

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

3　結(jié)　語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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