WSNS中基于Fusion－Bayes的離群點檢測

徐蘇婭，胡彩平，王立松

(南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇南京 210016)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)由部署在監(jiān)測區(qū)域內(nèi)大量的廉價微型傳感器節(jié)點組成，通過無線通信的方式形成一個多跳的自組織網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作的感知、采集和處理網(wǎng)絡(luò)覆蓋的地理區(qū)域中感知對象的信息，并發(fā)給用戶［1］。無線通信等技術(shù)的快速發(fā)展，推動了低功耗多功能傳感器的快速發(fā)展，從而使這種網(wǎng)絡(luò)系統(tǒng)的應(yīng)用越來越廣泛，包括環(huán)境監(jiān)測、交通管理、醫(yī)療衛(wèi)生、工農(nóng)業(yè)等。然而由于無線傳感器網(wǎng)絡(luò)自身存在的一些缺陷以及采集數(shù)據(jù)量越來越大等因素的影響，采集的數(shù)據(jù)樣本中不可避免地存在一些錯誤或異常數(shù)據(jù)，即所謂的離群點。在現(xiàn)實社會中，相對于那些經(jīng)常發(fā)生和出現(xiàn)的事物，人們往往對那些不常出現(xiàn)的特別事件或物體更感興趣［2］。例如對于森林檢測而言，溫度異常的數(shù)據(jù)或許預(yù)示火災(zāi)的發(fā)生，因此對離群點的檢測是有必要的。

到目前為止，對離群點還沒有一個正式的定義。Hawkins是這樣定義離群點的:“如果在一個數(shù)據(jù)樣本與其他樣本之間存在足以引起懷疑的差異，則稱其為離群點［3］。”離群點有多種別名:孤立點、異常點、新穎點、偏離點、噪音等。在許多研究中，為減少不一致數(shù)據(jù)也即離群數(shù)據(jù)對分析結(jié)果的影響，離群點常被忽略或者作為噪聲被處理，然而一個人的噪聲可能是另一個人的信號，不加分析的舍棄離群數(shù)據(jù)，可能導(dǎo)致重要信息的丟失。例如在欺詐檢測中，離群數(shù)據(jù)可能意味著欺詐行為的發(fā)生;在環(huán)境監(jiān)測中，離群數(shù)據(jù)可能預(yù)示著災(zāi)害天氣的到來。

根據(jù)離群點的定義，當一個數(shù)據(jù)樣本的屬性值有異常時，它會被識別為離群點。相對于多屬性的數(shù)據(jù)樣本來說，單個屬性的數(shù)據(jù)樣本更容易被識別。然而，每個傳感器節(jié)點都配備多個不同的傳感器，這樣數(shù)據(jù)樣本就存在多個屬性，這些屬性可能就存在特定的相關(guān)性。因此，把多個數(shù)值屬性融合之后再進行離群點檢測，其正確性會更高，也更具有實際意義。

1 相關(guān)工作

1.1 數(shù)據(jù)融合知識

數(shù)據(jù)融合最早起源于軍事領(lǐng)域，是一個愈來愈受到人們重視的研究方向。它的誕生可以歸結(jié)于在一個系統(tǒng)中使用了多個不同的傳感器，因此也稱為多傳感器數(shù)據(jù)融合。目前對數(shù)據(jù)融合還沒有得到一致的定義，它是針對使用多個或多類傳感器系統(tǒng)的處理方法，利用計算機和嵌入式技術(shù)對按時間序列獲得的數(shù)據(jù)信息在一定規(guī)則下做出決策和估計。

數(shù)據(jù)融合的關(guān)鍵技術(shù)主要是數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)相關(guān)、數(shù)據(jù)庫和融合計算等，其中融合計算是多傳感器數(shù)據(jù)融合系統(tǒng)的核心技術(shù)［4］。文中用到了數(shù)據(jù)轉(zhuǎn)換技術(shù)，由于多傳感器輸出的數(shù)據(jù)形式、環(huán)境描述不一樣，數(shù)據(jù)融合中心處理這些不同來源的信息時，首先需要把這些數(shù)據(jù)轉(zhuǎn)換成相同的形式和描述，然后再進行相關(guān)處理。數(shù)據(jù)轉(zhuǎn)換時，不僅要轉(zhuǎn)換不同層次的信息，而且需要轉(zhuǎn)換對環(huán)境或目標描述的不同與相似之處。即使同一層次的信息，也存在不同的描述。再者，數(shù)據(jù)融合存在時間性與空間性，因此要用到坐標變換。坐標變換的非線性帶來的誤差直接影響數(shù)據(jù)的質(zhì)量和時空校準，影響融合處理的質(zhì)量［5－6］。

1.2 貝葉斯分類

貝葉斯的主要思想是這樣的:對于給出的待分類項，求解在此項出現(xiàn)的條件下各個類別出現(xiàn)的概率，哪個最大就認為此待分項就屬于哪個類別。貝葉斯分類是一類分類算法的總稱，這類算法是以貝葉斯定理為基礎(chǔ)的，故統(tǒng)稱為貝葉斯分類。貝葉斯定理也稱為貝葉斯推理，是18世紀英國學(xué)者貝葉斯根據(jù)條件概率提出的。假設(shè)表示事件B已經(jīng)發(fā)生的前提下，事件A發(fā)生的概率，叫作事件B發(fā)生下事件A的條件概率。貝葉斯定理基本公式為p(B)/P(A)。

貝葉斯分類的正式定義如下:假設(shè)有一個未知數(shù)據(jù)樣本x{a1，a2，…，am}，屬性個數(shù)為m，其中每個a為x的一個特征屬性，假設(shè)數(shù)據(jù)類別為n，集合C={y1，y2，…，yn}，已知數(shù)據(jù)樣本，分別計算，如果概率最大，即，那么該數(shù)據(jù)樣本屬于第 k 類，即 x∈yk［7－8］。

本文利用貝葉斯分類原理，推廣到多傳感器網(wǎng)絡(luò)中，將數(shù)據(jù)分為正常數(shù)據(jù)和異常數(shù)據(jù)兩個類別，通過對部分數(shù)據(jù)訓(xùn)練得到分類模型，然后利用該模型對未知數(shù)據(jù)進行檢測，屬于異常數(shù)據(jù)類別的數(shù)據(jù)樣本就可以認為是離群點。

2 基于數(shù)據(jù)融合的貝葉斯檢測方法

2.1 數(shù)據(jù)預(yù)處理

首先將多傳感器收集的多屬性數(shù)據(jù)進行數(shù)據(jù)轉(zhuǎn)換，使數(shù)值屬性都變成純量數(shù)據(jù)，這樣就可以將多維數(shù)據(jù)進行比較。目前常用的數(shù)據(jù)轉(zhuǎn)換主要有min－max標準化、log函數(shù)轉(zhuǎn)換、atan函數(shù)轉(zhuǎn)換、z－score標準化等。

min－max標準化(Min－max normalization)，也叫離差標準化，是對原始數(shù)據(jù)的線性變化，使結(jié)果落到［0，1］區(qū)間，轉(zhuǎn)換函數(shù)為 x*=(x－min)/(max－min)，其中max為樣本數(shù)據(jù)的最大值，min為樣本數(shù)據(jù)的最小值。這種方法有一個缺陷就是當有新數(shù)據(jù)加入時，可能導(dǎo)致max和min的變化，因此需要重新定義。log轉(zhuǎn)換函數(shù)為x*=log10(x)/log10(max)，其中max為樣本數(shù)據(jù)最大值，并且所有的數(shù)據(jù)均≥1。atan函數(shù)轉(zhuǎn)換利用反正切函數(shù)也可以實現(xiàn)數(shù)據(jù)轉(zhuǎn)換，使用這個方法進行數(shù)據(jù)轉(zhuǎn)換時要求數(shù)據(jù)≥0，＜0的數(shù)據(jù)將被映射到［－1，0］區(qū)間上，具體轉(zhuǎn)換方法為 x*=a tan(x)*2/π，其中函數(shù)a tan(x)是求x的反正切函數(shù)。z－score標準化(zero－mean normalization)，也叫標準差標準化，經(jīng)過處理的數(shù)據(jù)符合標準正態(tài)分布，即均值為0，標準差為1，其轉(zhuǎn)化函數(shù)為x*=(x－u)/σ，其中u為所有樣本數(shù)據(jù)的均值，σ為所有樣本數(shù)據(jù)的標準差。

本文選用的是min－max標準化轉(zhuǎn)換函數(shù)，這是比較常用的轉(zhuǎn)換函數(shù)，也是最容易實現(xiàn)的函數(shù)。通過標準化轉(zhuǎn)換，所有的數(shù)據(jù)屬性都變成無量綱數(shù)據(jù)，彼此間可以進行融合計算。

2.2 貝葉斯方法檢測

假設(shè)在無線傳感器網(wǎng)絡(luò)中，每個數(shù)據(jù)樣本用一個n維特征向量表示，這n維特征向量分別用A1，A2，…，An表示。假定數(shù)據(jù)樣本共有m個類，給定一個未知類別的數(shù)據(jù)樣本X，在已知該數(shù)據(jù)樣本的條件下，分類器將預(yù)測其屬于最高后驗概率的類。也就是說，樸素貝葉斯分類將未知樣本分配給Ci(1≤i≤m)類當且僅當，對任意的 j=1，2，…，m，j≠i。這樣最大的類Ci就被稱為最大后驗假定，可以根據(jù)貝葉斯定理p(Ci)/p(X)求出。

由于對于所有類為常數(shù)，只要p(X Ci)P(Ci)最大即可。如果類Ci的先驗概率未知，則通常假定這些類是等概率的，即p(C1)=p(C2)=…=p(Cm)，因此問題就轉(zhuǎn)換為對的最大化。否則，就需要最大化，這里類的先驗概率可以用公式p(Ci)=si/S計算，其中si是類Ci中的訓(xùn)練樣本數(shù)，而S是訓(xùn)練樣本總數(shù)。

多屬性數(shù)據(jù)集的計算開銷可能較大，為降低計算開銷，可以做類條件獨立的樸素假定。給定樣本的類標號，假定屬性相互條件獨立，即在屬性間不存在依賴關(guān)系。這樣

。對未知樣本分類，也就是對每個類別Ci，計算的大小。如果，那么數(shù)據(jù)樣本X就被指派到類別 Ci，即數(shù)據(jù)樣本 X被指派到最大的類。

利用數(shù)據(jù)融合和貝葉斯分類結(jié)合的方法進行離群點檢測，首先將傳感器收集的數(shù)據(jù)轉(zhuǎn)換成同一樣式，然后對不同屬性進行融合分類，檢測出離群點，分別對所有單個屬性、部分屬性、所有屬性融合檢測，分別得出其檢測的正確性，并進行比較，實驗得出多屬性的融合檢測結(jié)果比單一或低維屬性的融合檢測效果更好。

2.3 Fusion－Bayesian算法步驟

數(shù)據(jù)預(yù)處理階段:(1)加載數(shù)據(jù)樣本S，選取溫度、濕度、亮度和電壓4個屬性。(2)利用min－max標準化方法對數(shù)據(jù)樣本S進行標準化處理，使其都變成純量綱數(shù)值。(3)在得到的標準化數(shù)據(jù)樣本中隨機插入離群數(shù)據(jù)樣本So。(4)將含有離群點的數(shù)據(jù)樣本分成兩部分，一部分是用于訓(xùn)練建模的訓(xùn)練樣本Strain;另一部分是用于測試數(shù)據(jù)的測試樣本Stest。訓(xùn)練數(shù)據(jù)樣本階段:(1)將樣本所屬類別分為Cnormal和 Coutlier兩類，分別求出兩類的概率 Pnormal和Poutlier。(2)對指定的類別和數(shù)據(jù)樣本的不同屬性融合，分別求出均值mu和方差xigma。

測試數(shù)據(jù)樣本階段:(1)給定測試樣本X，分別計算數(shù)據(jù)屬性xi屬于類Ci的概率(2)對于0≤i≤n，其中n為測試樣本總數(shù)，數(shù)據(jù)樣本X被指派到最大的類中。(3)最后，計算分類的正確率。

2.4 算法復(fù)雜度分析

利用數(shù)據(jù)融合和貝葉斯分類結(jié)合的方法進行離群點檢測，首先將傳感器收集的數(shù)據(jù)轉(zhuǎn)換成同一樣式，然后對不同屬性進行融合分類。假設(shè)m為數(shù)據(jù)樣本個數(shù)，n為數(shù)據(jù)樣本的維度;k為離群點個數(shù);t為將數(shù)據(jù)樣本分成的種類數(shù)。在預(yù)處理階段數(shù)據(jù)標準化的復(fù)雜度為O(mn)，隨機插入離群數(shù)據(jù)樣本的復(fù)雜度為O(k)，訓(xùn)練數(shù)據(jù)樣本階段的復(fù)雜度為O(tm)，測試數(shù)據(jù)樣本階段的復(fù)雜度為O(mnt)。由此可見，F(xiàn)usion－Bayes算法的復(fù)雜度較低，效率較高。

3 實驗結(jié)果

實驗采用的數(shù)據(jù)樣本是由伯克利實驗室配置的無線傳感器網(wǎng)絡(luò)收集而來［5］。實驗中選取如圖1所示的鄰近7個傳感器節(jié)點的數(shù)據(jù)進行檢測，實驗在Matlab2007上進行的。每個數(shù)據(jù)樣本有8個屬性，即日期、時間、時間戳、標記號、溫度、濕度、亮度和電壓，實驗中選取后4個屬性進行融合檢測。實驗中選取圓圈內(nèi)標注的簇節(jié)點的數(shù)據(jù)進行實驗，Node35是中心節(jié)點，其余節(jié)點是鄰居節(jié)點。這些數(shù)據(jù)樣本是傳感器節(jié)點在2004年3月5日內(nèi)收集的，在每個傳感器節(jié)點收集的數(shù)據(jù)中加入由Matlab隨機生成的200個離群點，這些隨機生成的離群點和傳感器數(shù)據(jù)樣本轉(zhuǎn)換后的格式一致。

圖1 伯克利實驗布置的傳感器分布圖

實驗中共對7個傳感器節(jié)點在一天內(nèi)收集的樣本數(shù)據(jù)進行檢測，傳感器節(jié)點平均31 s進行一次數(shù)據(jù)記錄，每個傳感器收集的數(shù)據(jù)樣本融合由Matlab隨機生成的離群點，總個數(shù)約為2 000個，利用基于數(shù)據(jù)融合的離群點進行檢測，每個數(shù)據(jù)樣本有4個屬性，即溫度、濕度、亮度和電壓，根據(jù)不同屬性進行融合可得到15組不同的組合，分別對這些組合進行離群點檢測實驗，每個傳感器節(jié)點在不同屬性融合的前提下，檢測正確率如圖2所示，其中橫坐標對應(yīng)所選取的7個傳感器位置，縱坐標是檢測的正確率。

圖2可以看出對溫度、濕度、亮度和電壓4個屬性進行融合后檢測的正確率最高，僅對單一屬性檢測的結(jié)果最差，選取若干個屬性進行融合后再進行離群點檢測的正確性居于上述情況之間。但并非是對所有單維屬性或低維屬性的檢測結(jié)果都不好，這正是后期需要研究的工作。因為本實驗主要是從檢測的正確率來考慮，實際應(yīng)用中還應(yīng)該考慮時間空間復(fù)雜度等其他客觀因素的影響，如果能找到一種數(shù)據(jù)融合模型，在給定的特定條件下，能決定選取幾個屬性、哪幾個屬性的融合可以使檢測結(jié)果最好，那么這將為多屬性數(shù)據(jù)樣本的離群點檢測工作帶來較大的便利，也避免了對所有屬性融合和大的計算開銷。

4 結(jié)束語

提出了基于Fusion－Bayes的貝葉斯檢測方法，該方法首先利用數(shù)據(jù)融合方法對數(shù)據(jù)樣本的多維屬性進行數(shù)據(jù)轉(zhuǎn)換，然后融合不同屬性進行離群點檢測，相比于單維屬性的檢測，多維屬性融合的檢測結(jié)果正確性更高。該方法仍存在需要改進的地方，例如在什么情況下可以根據(jù)單維或低維屬性進行離群點檢測，若可以用低維屬性進行檢測，那么如何選取屬性等問題。本文采用的離群點檢測方法是貝葉斯方法，雖然貝葉斯方法的檢測正確率較高，但是貝葉斯方法設(shè)定了過多假設(shè)，這些問題在以后的工作中會繼續(xù)研究，以期找到更好的檢測方法。

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

［2］TAN P N，STEINBACH M，KUMAR V.Introduction to data mining［M］.Beijing:Posts＆ Telecom Press，2006.

［3］HAN J，KAMBER M.Data mining:concepts and techniques［M］.San Francisco:Morgan Kaufmann Publishers，2001.

［4］龔元明，蕭德云，王俊杰.多傳感器數(shù)據(jù)融合技術(shù):上［J］.冶金自動化，2002(4):4－7.

［5］那彥，田軍，楊萬海，等.數(shù)據(jù)融合技術(shù)與多傳感器探測［J］.電子科技，2002(3):39 －41.

［6］蔡科，左憲章，康健，等.無線傳感器網(wǎng)絡(luò)測試系統(tǒng)數(shù)據(jù)融合研究［J］.計算機仿真，2010(7):1－4.

［7］毛曉明，盧光躍，趙國.一種提高無線傳感器網(wǎng)絡(luò)節(jié)點定位精度的算法［J］.西安郵電學(xué)院學(xué)報，2012，17(1):42－46.

［8］石紅麗，王潔，唐艷，等.基于無線傳感器網(wǎng)絡(luò)的K均值算法研究［J］.電子設(shè)計工程，2011，19(6):113－115.