無線傳感網絡中不確定數據空值的有效處理

金宗安，楊路明，謝　東

(1.六安職業技術學院 信息與電子工程學院，安徽 六安 237158;2.中南大學 信息科學與工程學院, 湖南 長沙 410083)

?

無線傳感網絡中不確定數據空值的有效處理

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

(1.六安職業技術學院 信息與電子工程學院，安徽 六安 237158;2.中南大學 信息科學與工程學院, 湖南 長沙 410083)

為了有效的解決無線傳感網絡中的空值問題，把數據庫中的元組分為不相容元組和相互獨立元組，給出了兩種元組在并操作時的概率計算方法；提出了基于最近鄰的加權表決算法PKNN，把存在空值的節點周圍k個值經加權計算得到空值的填充值.實驗表明，PKNN算法具有較好的準確性和平均絕對誤差率，且隨著k值的增大，平均絕對誤差率不斷減小，從而降低了數據的不確定性.

不確定數據；空值；最近鄰居

在無線傳感網絡中，空值的出現有許多種情況：①由于無線數據的傳輸受到周圍溫度、濕度等各方面的影響，會出現大量數據的丟失現象(未知值).②由于無線傳感網絡的數據傳輸能力限制，網絡中的通信線路會因為某種原因而出現斷接時，傳感器中的數據不能及時傳輸而丟失，從而使用用戶得到一些空缺的值[1].③無線傳輸節點的能量是有限的，當節點的能量比較低時，此時節點處理不穩定的條件下，有可能不能把有效的數據傳輸出去(空值或錯誤的值).

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

CMC(conditional Mean Completer)算法[3]考慮了其它取了出現頻率最高的值作為空值的補充值，但沒有考慮不同屬性之間的相互影響，這對于無線傳感網絡中數據之間相互關聯不相符，因此也不能作為無線傳感網絡中空值的處理方法.

CC算法(Combinatorial Completer)算法[4]從屬性約簡屬性中選擇一個最佳的值作為空值的補充，這種方法能得到較好的約簡效果，但當數據中存在較多的空值或數據量很大時，計算的時間代價就會很大.

為了有效的解決無線傳感網絡中存在相互關聯的數據計算并操作的概率，本文把不確定數據分為不相容元組和相互獨立元組，并給出了不同的計算方法.針對存在的空值問題，本文提出了基于最近鄰居的加權表決計算方法PKNN，把存在空值的節點周圍k個值經加權計算得到空值的填充值，算法具有較好的準確性和平均絕對誤差率，隨著k值的增大，平均絕對誤差率不斷減小，從且降低了數據的不確定性.

1　問題定義

當在不確定關系中出現空值時，這些空值的處理是比較復雜的，而如果不對這些空值進行處理，則對不確定數據進行查詢等操作時，會產生更多不可確定性的結果.如表1所示，對于表1中不確定關系R，假設屬性A為確定性屬性，屬性B和屬性C為不確定性屬性，取值有不可確定性，ps為確定屬性A在不確定屬性(B，C)某一取值時的概率，當B，C取值中出現*時代表空值.

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

在傳統的不確定關系空值處理方法中，目前主要有兩種主要的方法，一種是直接把這包含不確定信息進行清除，但隨著不確定數據中空值出現的日益廣泛，對于這些數據的清除會直接影響整個不確定數據庫中數據的完整性.對于表1中，若把含不確定數據時行清除，則表中的確定性屬性取值為a2的元組將不再出現，表中的數據如表2所示.當不確定數據中空值出現規模較大時，這種方法是無效的.

表1　不確定關系R

表2　清除空值后的不確定關系

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

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

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

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

從表面上看，這樣處理方式是可行的，但仔細分析可以看出，分解后的三個不確定關系并不等價于原不確定關系，例如，元組在原不確定關系中的概率是0.33，而在分解后的關系中，卻無從得知.因此，在不確定關系中，不能使用分解的方法來消除空值.

而在原不確定關系中，進行代數運算時，采用傳統的計算方法，計算的結果不符合實際的要求.例如，對于表1中不確定關系R分別在B屬性和C屬性上進行投影運算，按照傳統的計算方法，計算的公式為

從表中可以看出，B屬性取值為b1的元組有三個,,，則b1出現的概率ps為

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

經計算，整個表的投影運算計算結果如表6、表7所示：

表6　Π{B}(R)計算結果

表7　Π{Ⅰ}(R)計算結果

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

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

雖然這個概率很小，但代表屬性B取值為b1并不一定出現，所以原概率計算出現了錯誤.

2　空缺概率的分配

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

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

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

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

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

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

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

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

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

也就是說，在S的子集r中的數據點距離查詢點q的之間距離要小于或等于同樣S子集的p中的點和q的距離，此時r中的點即是q的最近鄰居.

如果r中元素的個數為l時，就是單個的最近鄰居查詢，如果r中元素的個數大于1時，比方說為k，此時q的k個最近鄰居，dist表示兩對象間的最小距離，dist(q,r)表示q，r兩點的距離.

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

(1)

其中n是維數，xi和yi分別是x和y的第i個屬性.對于兩個標稱屬性描述的對象，如果它們的屬性值不匹配，則說明它們的相異度為1，如果匹配則說明它們的相異為0.

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

(2)

上述公式中，v是類標號，yi是一個最近鄰的類標號，I(.)是指示函數，如果其參數為真，則返回1，否則，則返回0.

3　算法設計

使用基于最近領居分類方法存儲無線傳感網絡中不確定數據，當有新的不確定數據出現時，要構建新的構造模型，對數據進行分類.k最近鄰居分類的每一個數據對象一般有N個數據屬性，可以把N個數據屬性構成N維空間模式進行存儲，每一個N維空間代表一個數據對象.使用k最近鄰居分類算法搜索存儲的數據，計算最近的k個數據對象作為k最近鄰居.

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

輸入：A[n]為N個傳感節點樣本在空間中的坐標，k為節點x最近鄰數，含有空值的不確定數據

輸出：填補空值后的不確定數據

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

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

{

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

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

then 用A[i]代替最遠節點

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

End

}

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

本算法通過采集出現空值x的N個周圍空間坐標值，先計算與已知樣本x前k個測試樣本距離，這k個點的最遠歐式距離設為D；然后依次計算剩余測試樣本數據集合中所有數據與樣本x間的歐式距離dist，當dist小于D時，則把此測試樣本存儲到k-最近鄰中，直到所有的測試樣本都計算完，并按類標號的頻率依次排序，把頻率最大的類標號作為空值計算的依據.

如果選擇合適的k值要結合實際運用的情況，當k值較大時，距離某一個點的較遠點中的數據也會出現在最近鄰居列表中，這樣有可能出現錯誤的分類測試樣例.如果選用的k值較小時，距離某一個點的較近的一些數據會排出在最近鄰居列表中.因此，選持合適的k值是也是實際應用要考慮的一個重要問題.

4　實驗分析

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

采用rand()函數對實驗數據集進行處理，產生隨機的空值.對于數據樣本數為n的m維數據集R，隨機產生x個空值，其過程如下：

Fori=1 tox

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

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

R(H,L)=NULL

Next

針對Intel Berkeley Research Lab數據集的四個屬性分別使用CC、MC、CMC和PKNN算法進行驗證，如圖1所示.從圖1中可以看出，CC算法雖然使用約簡屬性中最好的一個作為補充，但效果確最差，因為這種算法并不適用于無線傳感網絡中的數據；MC算法使用平均值填充，沒有考慮決策屬性，而CMC雖然考慮了決策屬性，但并沒有考慮無線傳感網絡中數據的不確定性，因此它們的確準率并不是最好；PKNN算法綜合考慮無線傳感網絡中數據和節點之間關聯的特點，采用基于距離的加權表決，根據數據的不確定性的大小和距離的遠近計算空值的填充值，因此其準確率明顯高于其它算法.

圖1　填充準確率對比

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

圖2　k值對平均絕對誤差率的影響

5　結語

本文針對無線傳感網絡中不確定數據空值進行了有效的處理，針對不相容元組和相互獨立元組給出了不同的并操作計算方法，提出了基于最鄰居的加權表決計算方法PKNN，算法具有較好的準確性和平均絕對誤差率.但無線傳感網絡中不確定數據很問題都還沒有效解決[7]，以后主要研究方向為①不確定關系數據庫中自連接查詢的處理：當一個關系的名稱在一個查詢中出現兩次的時候，如何判斷它是一個線性的還是NP難的查詢；②查詢優化：不確定關系數據庫的查詢優化和確定性的數據庫的查詢優化有些類似，但也不同的地方，如何更好的對不確定關系數據庫進行優化仍然是一個問題.

[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]姜延吉，黃鳳崗．存在型空值插補的特征約簡方法研究[J]．哈爾濱工程大學學報，2010，31(6):743-748．

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

[4]張霞，儲尚軍，許鳴珠．基于粗糙集的不完備信息系統空值補齊算法[J]．小型微型計算機系統，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.

責任編輯：趙秋宇

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

安徽省優秀青年人才基金重點項目(2013SQRL143ZD)

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

1671-9824(2016)05-0055-06

TP311

A