無(wú)線傳感網(wǎng)絡(luò)中不確定數(shù)據(jù)空值的有效處理

金宗安，楊路明，謝　東

(1.六安職業(yè)技術(shù)學(xué)院 信息與電子工程學(xué)院，安徽 六安 237158;2.中南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長(zhǎng)沙 410083)

?

無(wú)線傳感網(wǎng)絡(luò)中不確定數(shù)據(jù)空值的有效處理

金宗安1,2，楊路明2，謝東2

(1.六安職業(yè)技術(shù)學(xué)院 信息與電子工程學(xué)院，安徽 六安 237158;2.中南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長(zhǎng)沙 410083)

為了有效的解決無(wú)線傳感網(wǎng)絡(luò)中的空值問(wèn)題，把數(shù)據(jù)庫(kù)中的元組分為不相容元組和相互獨(dú)立元組，給出了兩種元組在并操作時(shí)的概率計(jì)算方法；提出了基于最近鄰的加權(quán)表決算法PKNN，把存在空值的節(jié)點(diǎn)周?chē)鷎個(gè)值經(jīng)加權(quán)計(jì)算得到空值的填充值.實(shí)驗(yàn)表明，PKNN算法具有較好的準(zhǔn)確性和平均絕對(duì)誤差率，且隨著k值的增大，平均絕對(duì)誤差率不斷減小，從而降低了數(shù)據(jù)的不確定性.

不確定數(shù)據(jù)；空值；最近鄰居

在無(wú)線傳感網(wǎng)絡(luò)中，空值的出現(xiàn)有許多種情況：①由于無(wú)線數(shù)據(jù)的傳輸受到周?chē)鷾囟?、濕度等各方面的影響，?huì)出現(xiàn)大量數(shù)據(jù)的丟失現(xiàn)象(未知值).②由于無(wú)線傳感網(wǎng)絡(luò)的數(shù)據(jù)傳輸能力限制，網(wǎng)絡(luò)中的通信線路會(huì)因?yàn)槟撤N原因而出現(xiàn)斷接時(shí)，傳感器中的數(shù)據(jù)不能及時(shí)傳輸而丟失，從而使用用戶得到一些空缺的值[1].③無(wú)線傳輸節(jié)點(diǎn)的能量是有限的，當(dāng)節(jié)點(diǎn)的能量比較低時(shí)，此時(shí)節(jié)點(diǎn)處理不穩(wěn)定的條件下，有可能不能把有效的數(shù)據(jù)傳輸出去(空值或錯(cuò)誤的值).

基于信息粒度空值處理也得到了較好的研究，在MC(Mean Completer)算法[2]中，把所有的元組的平均值作為空值的補(bǔ)充值，這種方法沒(méi)有考慮其它屬性的權(quán)值，沒(méi)有較好的理論依據(jù)，因此不能作為無(wú)線傳感網(wǎng)絡(luò)中空值的處理方法.

CMC(conditional Mean Completer)算法[3]考慮了其它取了出現(xiàn)頻率最高的值作為空值的補(bǔ)充值，但沒(méi)有考慮不同屬性之間的相互影響，這對(duì)于無(wú)線傳感網(wǎng)絡(luò)中數(shù)據(jù)之間相互關(guān)聯(lián)不相符，因此也不能作為無(wú)線傳感網(wǎng)絡(luò)中空值的處理方法.

CC算法(Combinatorial Completer)算法[4]從屬性約簡(jiǎn)屬性中選擇一個(gè)最佳的值作為空值的補(bǔ)充，這種方法能得到較好的約簡(jiǎn)效果，但當(dāng)數(shù)據(jù)中存在較多的空值或數(shù)據(jù)量很大時(shí)，計(jì)算的時(shí)間代價(jià)就會(huì)很大.

為了有效的解決無(wú)線傳感網(wǎng)絡(luò)中存在相互關(guān)聯(lián)的數(shù)據(jù)計(jì)算并操作的概率，本文把不確定數(shù)據(jù)分為不相容元組和相互獨(dú)立元組，并給出了不同的計(jì)算方法.針對(duì)存在的空值問(wèn)題，本文提出了基于最近鄰居的加權(quán)表決計(jì)算方法PKNN，把存在空值的節(jié)點(diǎn)周?chē)鷎個(gè)值經(jīng)加權(quán)計(jì)算得到空值的填充值，算法具有較好的準(zhǔn)確性和平均絕對(duì)誤差率，隨著k值的增大，平均絕對(duì)誤差率不斷減小，從且降低了數(shù)據(jù)的不確定性.

1　問(wèn)題定義

當(dāng)在不確定關(guān)系中出現(xiàn)空值時(shí)，這些空值的處理是比較復(fù)雜的，而如果不對(duì)這些空值進(jìn)行處理，則對(duì)不確定數(shù)據(jù)進(jìn)行查詢等操作時(shí)，會(huì)產(chǎn)生更多不可確定性的結(jié)果.如表1所示，對(duì)于表1中不確定關(guān)系R，假設(shè)屬性A為確定性屬性，屬性B和屬性C為不確定性屬性，取值有不可確定性，ps為確定屬性A在不確定屬性(B，C)某一取值時(shí)的概率，當(dāng)B，C取值中出現(xiàn)*時(shí)代表空值.

由表1中可以看出，當(dāng)A屬性取值為a1時(shí)，(B，C)屬性取值為(b1,*)的概率為0.65，也就是說(shuō)B屬性取值為b1，而C屬性此時(shí)取值不確定.

在傳統(tǒng)的不確定關(guān)系空值處理方法中，目前主要有兩種主要的方法，一種是直接把這包含不確定信息進(jìn)行清除，但隨著不確定數(shù)據(jù)中空值出現(xiàn)的日益廣泛，對(duì)于這些數(shù)據(jù)的清除會(huì)直接影響整個(gè)不確定數(shù)據(jù)庫(kù)中數(shù)據(jù)的完整性.對(duì)于表1中，若把含不確定數(shù)據(jù)時(shí)行清除，則表中的確定性屬性取值為a2的元組將不再出現(xiàn)，表中的數(shù)據(jù)如表2所示.當(dāng)不確定數(shù)據(jù)中空值出現(xiàn)規(guī)模較大時(shí)，這種方法是無(wú)效的.

表1　不確定關(guān)系R

表2　清除空值后的不確定關(guān)系

另外一種方法就是當(dāng)幾個(gè)互不相依賴(lài)的不確定屬性出現(xiàn)在同一個(gè)不確定關(guān)系中，可以通過(guò)把這幾個(gè)互不依賴(lài)的不確定關(guān)系進(jìn)行分解[5].例如，表1中的關(guān)系，B,C兩個(gè)互不依賴(lài)屬性，即一個(gè)屬性的取值會(huì)不會(huì)依賴(lài)于另一個(gè)屬性的取值，可以把這種含有空值的不確定關(guān)系分解成多個(gè)沒(méi)有空值的不確定關(guān)系，但每一種關(guān)系中都包含概率屬性.把表1中的不確定關(guān)系模式分解為表3、表4、表5中的3個(gè)關(guān)系{A,ps, {A,B,ps}, {A,C,ps}, {A,B,C,ps}.在分解后的不確定關(guān)系中，不再含有空值，而原不確定關(guān)系中的值都保留在了分解后的不確定關(guān)系中.

表3　分解后的不確定關(guān)系(1)

表4　分解后的不確定關(guān)系(2)

表5　分解后的不確定關(guān)系(3)

從表面上看，這樣處理方式是可行的，但仔細(xì)分析可以看出，分解后的三個(gè)不確定關(guān)系并不等價(jià)于原不確定關(guān)系，例如，元組在原不確定關(guān)系中的概率是0.33，而在分解后的關(guān)系中，卻無(wú)從得知.因此，在不確定關(guān)系中，不能使用分解的方法來(lái)消除空值.

而在原不確定關(guān)系中，進(jìn)行代數(shù)運(yùn)算時(shí)，采用傳統(tǒng)的計(jì)算方法，計(jì)算的結(jié)果不符合實(shí)際的要求.例如，對(duì)于表1中不確定關(guān)系R分別在B屬性和C屬性上進(jìn)行投影運(yùn)算，按照傳統(tǒng)的計(jì)算方法，計(jì)算的公式為

從表中可以看出，B屬性取值為b1的元組有三個(gè),,，則b1出現(xiàn)的概率ps為

min{1,0.65+0.64+0.61}=1 .

經(jīng)計(jì)算，整個(gè)表的投影運(yùn)算計(jì)算結(jié)果如表6、表7所示：

表6　Π{B}(R)計(jì)算結(jié)果

表7　Π{Ⅰ}(R)計(jì)算結(jié)果

從上兩個(gè)表中可以看出，屬性B取值為b1是一定出現(xiàn)的，從表7可以看出，屬性C取值為c2是一定出現(xiàn)的，它們的概率都為1.而從原不確定關(guān)系中可以看出，不確定關(guān)系為空的概率為

(1-0.65-0.33)*(1-0.45-0.47)*(1-0.61)=0.000 624.

雖然這個(gè)概率很小，但代表屬性B取值為b1并不一定出現(xiàn)，所以原概率計(jì)算出現(xiàn)了錯(cuò)誤.

2　空缺概率的分配

定義1不相容元組(Disjoint Tuple)：在不確定關(guān)系R中，若兩個(gè)元組x,y的確定性屬性取值相同，并且它們的取值的概率之和小于等于1，即ps(x)+ps(y)≤1，則把這兩個(gè)具有相同確定屬性取值的元組稱(chēng)為不相容的元組.對(duì)于這兩個(gè)不確定元組x,y，根據(jù)不相容事件的概率計(jì)算方法，它們的并操作可表示為

p(x∨y)=p(x)+p(y)，

其中，p(x)代表元組x的概率.

例如，在表1中不確定關(guān)系R中，元組〈a1,b1,*,0.65〉和〈a1,b2,c1,0.33〉在確定性屬性A取值是相同的，都為a1，則這兩個(gè)元組是不相容的元組.它們并操作的概率為0.65+0.33=0.98.

定義2相互獨(dú)立元組(Independent Tuple)：在不確定關(guān)系R中，若兩個(gè)元組x,y的確定性屬性取值不相同，則把這兩個(gè)元組x,y稱(chēng)之為相互獨(dú)立元組.根據(jù)相互獨(dú)立事件的概率計(jì)算方法，它們的并操作可表示為

p(x∨y)=1-(1-p(x))(1-p(y)).

例如，在表1中不確定關(guān)系R中，元組〈a1,b1,*,0.65〉和〈a3,b1,c2,0.61〉在確定性屬性A取值是不相同的，則這兩個(gè)元組是相互獨(dú)立元組.它們并操作的概率為1-(1-0.65)*(1-0.61)=0.136 5.

定義3最近鄰居(Nearest Neighbor)[6]：在n維空間里，對(duì)于查詢q，在一個(gè)設(shè)定的查詢對(duì)象集合S中，找到與查詢樣例q的屬性相對(duì)接近的子集NNS(q)，這個(gè)子集滿足如下公式成立：

NNS(q)={r∈S|?p∈S,dist(q,r)≤dist(p,p)}.

也就是說(shuō)，在S的子集r中的數(shù)據(jù)點(diǎn)距離查詢點(diǎn)q的之間距離要小于或等于同樣S子集的p中的點(diǎn)和q的距離，此時(shí)r中的點(diǎn)即是q的最近鄰居.

如果r中元素的個(gè)數(shù)為l時(shí)，就是單個(gè)的最近鄰居查詢，如果r中元素的個(gè)數(shù)大于1時(shí)，比方說(shuō)為k，此時(shí)q的k個(gè)最近鄰居，dist表示兩對(duì)象間的最小距離，dist(q,r)表示q，r兩點(diǎn)的距離.

定義4相異度(Dissimilarity)，由歐幾里德距離定義，其中兩個(gè)點(diǎn)X(x1,x2,...,xn)和Y(y1,y2,...,yn)的歐幾里德距離如公式(1)所示：

(1)

其中n是維數(shù)，xi和yi分別是x和y的第i個(gè)屬性.對(duì)于兩個(gè)標(biāo)稱(chēng)屬性描述的對(duì)象，如果它們的屬性值不匹配，則說(shuō)明它們的相異度為1，如果匹配則說(shuō)明它們的相異為0.

在多數(shù)表決方法中，每個(gè)近鄰對(duì)分類(lèi)的影響都一樣，這使得算法對(duì)k的選擇很敏感.降低k的影響的一種途徑就是根據(jù)每個(gè)最近鄰xi的距離不同對(duì)其作用加權(quán)：wi=1/D(x′,xi).結(jié)果使得遠(yuǎn)離x的訓(xùn)練樣例對(duì)分類(lèi)的影響要比那些靠近x的訓(xùn)練樣例弱一些.使用距離加權(quán)表決方案，類(lèi)標(biāo)號(hào)可以由公式(2)確定,距離加權(quán)表決：

(2)

上述公式中，v是類(lèi)標(biāo)號(hào)，yi是一個(gè)最近鄰的類(lèi)標(biāo)號(hào)，I(.)是指示函數(shù)，如果其參數(shù)為真，則返回1，否則，則返回0.

3　算法設(shè)計(jì)

使用基于最近領(lǐng)居分類(lèi)方法存儲(chǔ)無(wú)線傳感網(wǎng)絡(luò)中不確定數(shù)據(jù)，當(dāng)有新的不確定數(shù)據(jù)出現(xiàn)時(shí)，要構(gòu)建新的構(gòu)造模型，對(duì)數(shù)據(jù)進(jìn)行分類(lèi).k最近鄰居分類(lèi)的每一個(gè)數(shù)據(jù)對(duì)象一般有N個(gè)數(shù)據(jù)屬性，可以把N個(gè)數(shù)據(jù)屬性構(gòu)成N維空間模式進(jìn)行存儲(chǔ)，每一個(gè)N維空間代表一個(gè)數(shù)據(jù)對(duì)象.使用k最近鄰居分類(lèi)算法搜索存儲(chǔ)的數(shù)據(jù)，計(jì)算最近的k個(gè)數(shù)據(jù)對(duì)象作為k最近鄰居.

算法1 搜索傳感節(jié)點(diǎn)k個(gè)近鄰的算法：PKNN(A[n],k) .

輸入：A[n]為N個(gè)傳感節(jié)點(diǎn)樣本在空間中的坐標(biāo)，k為節(jié)點(diǎn)x最近鄰數(shù)，含有空值的不確定數(shù)據(jù)

輸出：填補(bǔ)空值后的不確定數(shù)據(jù)

取A[1]～A[k]作為x的初始近鄰，計(jì)算與測(cè)試樣本x間的歐式距離d(x,A[i]),i=1,2,.....,k；按d(x，A[i])升序排序，計(jì)算最遠(yuǎn)傳感節(jié)點(diǎn)與x間的距離D=max{d(x,a[j]) | j=1,2,.....,k};

for(i=k+1;i<=n;i++)

{

計(jì)算a[i]與x間的距離d(x,A[i]);

if(d(x,A[i]))

then 用A[i]代替最遠(yuǎn)節(jié)點(diǎn)

按照d(x,A[i])升序排序，計(jì)算最遠(yuǎn)節(jié)點(diǎn)與x間的距離D=max{d(x,A[j]) |j=1,...,i};

End

}

計(jì)算樣本集合A[i],(i=1,2,...,k)的概率并記錄它們所屬的類(lèi)標(biāo)號(hào)，依此計(jì)算并填充樣本x的空值.

本算法通過(guò)采集出現(xiàn)空值x的N個(gè)周?chē)臻g坐標(biāo)值，先計(jì)算與已知樣本x前k個(gè)測(cè)試樣本距離，這k個(gè)點(diǎn)的最遠(yuǎn)歐式距離設(shè)為D；然后依次計(jì)算剩余測(cè)試樣本數(shù)據(jù)集合中所有數(shù)據(jù)與樣本x間的歐式距離dist，當(dāng)dist小于D時(shí)，則把此測(cè)試樣本存儲(chǔ)到k-最近鄰中，直到所有的測(cè)試樣本都計(jì)算完，并按類(lèi)標(biāo)號(hào)的頻率依次排序，把頻率最大的類(lèi)標(biāo)號(hào)作為空值計(jì)算的依據(jù).

如果選擇合適的k值要結(jié)合實(shí)際運(yùn)用的情況，當(dāng)k值較大時(shí)，距離某一個(gè)點(diǎn)的較遠(yuǎn)點(diǎn)中的數(shù)據(jù)也會(huì)出現(xiàn)在最近鄰居列表中，這樣有可能出現(xiàn)錯(cuò)誤的分類(lèi)測(cè)試樣例.如果選用的k值較小時(shí)，距離某一個(gè)點(diǎn)的較近的一些數(shù)據(jù)會(huì)排出在最近鄰居列表中.因此，選持合適的k值是也是實(shí)際應(yīng)用要考慮的一個(gè)重要問(wèn)題.

4　實(shí)驗(yàn)分析

無(wú)線傳感網(wǎng)絡(luò)不確定數(shù)據(jù)空值處理的實(shí)驗(yàn)環(huán)境為Windows 7系統(tǒng)，Intel(R) Core(TM) i5-4200M CPU,主頻2.50 Ghz，內(nèi)存3 GB，SQL Server2008數(shù)據(jù)庫(kù).不確定數(shù)據(jù)空值處理采用C++編程實(shí)現(xiàn)，實(shí)驗(yàn)采用了Intel Berkeley Research Lab實(shí)驗(yàn)室提供尺寸s=143 MB的數(shù)據(jù)，這些數(shù)據(jù)由54個(gè)傳感器每31秒收集一次，每個(gè)數(shù)據(jù)有4個(gè)屬性(temperature、humidity、light、voltage).

采用rand()函數(shù)對(duì)實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行處理，產(chǎn)生隨機(jī)的空值.對(duì)于數(shù)據(jù)樣本數(shù)為n的m維數(shù)據(jù)集R，隨機(jī)產(chǎn)生x個(gè)空值，其過(guò)程如下：

Fori=1 tox

H=int(n*rand())+1

L=int(m*rand())+1

R(H,L)=NULL

Next

針對(duì)Intel Berkeley Research Lab數(shù)據(jù)集的四個(gè)屬性分別使用CC、MC、CMC和PKNN算法進(jìn)行驗(yàn)證，如圖1所示.從圖1中可以看出，CC算法雖然使用約簡(jiǎn)屬性中最好的一個(gè)作為補(bǔ)充，但效果確最差，因?yàn)檫@種算法并不適用于無(wú)線傳感網(wǎng)絡(luò)中的數(shù)據(jù)；MC算法使用平均值填充，沒(méi)有考慮決策屬性，而CMC雖然考慮了決策屬性，但并沒(méi)有考慮無(wú)線傳感網(wǎng)絡(luò)中數(shù)據(jù)的不確定性，因此它們的確準(zhǔn)率并不是最好；PKNN算法綜合考慮無(wú)線傳感網(wǎng)絡(luò)中數(shù)據(jù)和節(jié)點(diǎn)之間關(guān)聯(lián)的特點(diǎn)，采用基于距離的加權(quán)表決，根據(jù)數(shù)據(jù)的不確定性的大小和距離的遠(yuǎn)近計(jì)算空值的填充值，因此其準(zhǔn)確率明顯高于其它算法.

圖1　填充準(zhǔn)確率對(duì)比

由于空值的計(jì)算采用的是基于近鄰居的加權(quán)距離表決，因此，近鄰數(shù)對(duì)各算法的平均絕對(duì)誤差有不同影響，如圖2所示.從圖2中可以看出， 當(dāng)k值較小時(shí)，算法的總體平均絕對(duì)誤差率較大，隨著k值的增大，算法的平均絕對(duì)誤差在減小，

圖2　k值對(duì)平均絕對(duì)誤差率的影響

5　結(jié)語(yǔ)

本文針對(duì)無(wú)線傳感網(wǎng)絡(luò)中不確定數(shù)據(jù)空值進(jìn)行了有效的處理，針對(duì)不相容元組和相互獨(dú)立元組給出了不同的并操作計(jì)算方法，提出了基于最鄰居的加權(quán)表決計(jì)算方法PKNN，算法具有較好的準(zhǔn)確性和平均絕對(duì)誤差率.但無(wú)線傳感網(wǎng)絡(luò)中不確定數(shù)據(jù)很問(wèn)題都還沒(méi)有效解決[7]，以后主要研究方向?yàn)棰俨淮_定關(guān)系數(shù)據(jù)庫(kù)中自連接查詢的處理：當(dāng)一個(gè)關(guān)系的名稱(chēng)在一個(gè)查詢中出現(xiàn)兩次的時(shí)候，如何判斷它是一個(gè)線性的還是NP難的查詢；②查詢優(yōu)化：不確定關(guān)系數(shù)據(jù)庫(kù)的查詢優(yōu)化和確定性的數(shù)據(jù)庫(kù)的查詢優(yōu)化有些類(lèi)似，但也不同的地方，如何更好的對(duì)不確定關(guān)系數(shù)據(jù)庫(kù)進(jìn)行優(yōu)化仍然是一個(gè)問(wèn)題.

[1]Ye M, Lee W C, Lee D L, et al. Distributed processing of probabilistic top-k queries in wireless sensor networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2013,25(1):76-91.

[2]姜延吉，黃鳳崗．存在型空值插補(bǔ)的特征約簡(jiǎn)方法研究[J]．哈爾濱工程大學(xué)學(xué)報(bào)，2010，31(6):743-748．

[3]李聰，梁昌勇，楊善林．基于粗糙集的不完備信息系統(tǒng)空值估算方法[J]．計(jì)算機(jī)集成制造系統(tǒng)，2009，15(3):604-608．

[4]張霞，儲(chǔ)尚軍，許鳴珠．基于粗糙集的不完備信息系統(tǒng)空值補(bǔ)齊算法[J]．小型微型計(jì)算機(jī)系統(tǒng)，2011，32(4):752-756．

[5]Olteanu D, Huang J, Koch C. Approximate confidence computation in probabilistic databases[C]Los Angeles:Proceeding of the 29th ICDE Comference,IEEE press, 2010.

[6]Cheema M A, Lin X M, Wang W, et al. Probabilistic reverse nearest neighbor queries on uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering，2010, 22(4):550-564.

[7]Dalvi N, Suciu D. Efficient query evaluation on probabilistic databases[J]. International Journal on VLDB, 2006,16(4):523-544.

責(zé)任編輯：趙秋宇

Efficient Processing of Null Value on Probabilistic Data in Wireless Sensor Network

JIN Zong-an1,2，YANG Lu-ming2，XIE Dong2

(1.SchoolofInformationandElectronicEngineering,Liu’AnVocationTechnologyCollege,Liu’an, 237158China;2SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China)

In order to effectively solve the problem of empty value in wireless sensor networks, the paper presents a method for calculating operation probability of different tuples in the database. In which the tuples are divided into dependent tuples and independent tuples. In this paper, we propose a weighted algorithm PKNN, which is based on the nearest neighbor, to calculate the filling value of the null values by the weighted values of the k nodes around null values. Experimental results show that the proposed PKNN algorithm has a better accuracy and lower average absolute error rate. With increase of k, the average absolute error rate decreases. Thus, it can effectively reduce the uncertainty of the data.

probabilistic database; null value; nearest neighbor

2016-01-22

安徽省優(yōu)秀青年人才基金重點(diǎn)項(xiàng)目(2013SQRL143ZD)

金宗安(1983—)，男，河南信陽(yáng)人，講師，碩士，研究方向：不確定數(shù)據(jù)處理．

1671-9824(2016)05-0055-06

TP311

A