基于時空關系和關聯規則挖掘的上下文信息缺失插補研究

王玉祥 喬秀全 李曉峰 孟洛明

(北京郵電大學網絡與交換技術國家重點實驗室 北京 100876)

1 引言

在上下文信息處理機制中，由于現實世界的復雜性、多變性以及人類自身認識的局限性和主觀性，使得人們獲得的上下文信息中含有大量的不確定、不準確、不完全、不一致的地方。上下文信息存在缺失的原因可能是傳感器之間時鐘同步錯誤，傳感器斷電，傳感器失效，通信傳輸錯誤，人為攻擊等，這在上下文信息處理機制中是不可避免的。傳感器數據的缺失，往往導致挖掘的信息知識準確性存在偏差，嚴重的會產生錯誤決策，導致系統癱瘓，造成重大的損失。因此，上下文信息的缺失插補方法是上下文信息處理機制的關鍵技術之一，數據的完備性是推理高層上下文信息從而形成智能決策的前提基礎。

當前，比較常用的數據缺失插補方法有線性回歸插補[1]，最近鄰插補[2]，熱板、冷板插補，期望最大EM(Expectation Maximum)[3]算法，最大可能性插補[4,5]，多重插補方法[6,7]，貝葉斯網絡(Bayesian Network)統計分析法[8]等統計學方面的插補方法，但是這些方法并沒有考慮到傳感器流數據的特點。傳感器數據最突出的特點：一是數據之間有很強的關聯性；二是傳感器數據之間具有明顯的時空特性。另外，最近較多的是采用數據挖掘的方法，特別是基于關聯規則的挖掘方法[9,10]，這些方法雖然考慮了數據之間的關聯特性，但是沒有涉及傳感器數據的時空特性。文獻[11,12]也只是研究了傳感器數據的時空特性去進行數據缺失插補，但是沒考慮數據之間的關聯特性。因此以往的研究方法都存在著不太全面的弊端，缺少全面綜合而又滿足實時應用的數據缺失插補方法。

為了更加準確地對傳感器數據缺失進行插補，本文針對傳感器數據這一類上下文信息，根據傳感器數據的關聯性和時空特性兩大特點，提出了基于時空關系和關聯規則挖掘的上下文信息缺失插補方法，全面綜合討論了數據插補方法，提高了傳感器數據缺失插補的準確性。

本文第2節首先介紹了關聯規則挖掘的基本概念和基本步驟。第3節提出了基于時空關系和關聯規則挖掘的上下文信息缺失插補方法，并詳細闡述基于時空關系和關聯規則挖掘的上下文信息缺失插補的詳細過程。第4節通過仿真實驗驗證了基于時空關系和關聯規則挖掘的上下文信息缺失插補方法的高效性和合理性。最后給出結論和未來的工作。

2 關聯規則挖掘

2.1 關聯規則挖掘的相關概念

定義1 數據項：在傳感器采集數據的過程中，傳感器X和Y采集到的數值可以根據用戶的不同要求，即顆粒度的要求不同離散成不同區間的數值，離散化后的數值稱之為傳感器的數據項。若干個數據項的集合就構成數據項集。數據項集所包含的數據項的個數稱為該數據項集的維數，長度為m的數據項集，定義為m維的數據項集。

定義2 支持度：在無線傳感網絡中，傳感器X和Y在某一段時間區間內采集的數據項中相同的個數和傳感器X和Y在這一段時間區間內采集的數據項的總的個數的比值稱之為關聯規則X→Y的支持度。數據項集合D的支持度通常記作supp(D)，關聯規則X→Y的支持度通常記作supp(X→Y)。

定義 3 信任度：在無線傳感網絡中，對于傳感器X和Y，在某一段時間區間內，傳感器X采集到的數據項而同時傳感器Y也能夠同時采集到相同數據項概率可能性的大小，稱之為關聯規則X→Y的信任度，由信任度的定義可知信任度可以用支持度來表示成為supp(X→Y)/supp(X)。

定義 4 最小支持度：在實際的應用系統中，根據用戶對系統的要求不同確定的關聯規則支持度需要滿足的最小的數值，它是滿足用戶最低需求的支持度的數值，稱之為最小支持度，通常記作minsupp。

定義 5 最小信任度：在實際的應用系統中，根據用戶對系統的要求不同確定的關聯規則信任度需要滿足的最小的數值，它是滿足用戶最低可靠性保證的數值，稱之為最小信任度，通常記作minconf。

定義 6 頻繁數據項集：對于用戶給定的最小支持度minsupp，傳感器X采集到的數據項D支持度如果大于該最小支持度minsupp，則稱數據項D為頻繁數據項集，同時稱傳感器X為頻繁節點集。

2.2 關聯規則挖掘概念

在上下文信息采集網絡中，對于傳感器X和Y，形如蘊含式X→Y稱之為關聯規則，其中傳感器X和Y都是獨立采集的。關聯規則是統計學中簡單而又實用的一種推理規則，也是數據挖掘研究熱點領域，特別適用于分析傳感器采集的大量數據項之間頻繁出現的模態關聯性，從而對傳感器采集的數據缺失進行插補。

支持度與信任分別大于用戶定義的最小閾值minsupp和minconf的規則通常稱為強關聯規則。關聯規則挖掘的目標就是從給定的傳感器節點所采集的所有數據項中找到所有的強關聯規則節點，分析出傳感器節點所采集的所有數據項的規律，從而挖掘出各節點之間關聯性、相關性，進一步可以對節點數據項進行推理、預測。

2.3 關聯規則挖掘的基本過程

由關聯規則挖掘的形式化定義可知，通常情況下，對于關聯規則挖掘問題可以劃分成兩個基本的過程：

(1)頻繁傳感器節點的查找 對于用戶設定的最小支持度 minsupp，從傳感器網絡系統中查找所有的頻繁傳感器節點集合，即滿足支持度大于等于minsupp的傳感器節點集合。實際上，這些頻繁傳感器節點集合或許具有一定的推出關系。不失一般性，我們通常只考慮那些不被其它傳感器節點集合所推出的頻繁最大傳感器節點集合。這些頻繁大傳感器節點集合是形成強關聯規則前提。

(2)強關聯規則的形成 對于用戶設定的最小信任度 minconf，在頻繁最大傳感器節點集合，根據一定的具體方法來生成信任度大于等于 minconf的關聯規則，從而形成蘊含式的強關聯規則，進一步可以推理出傳感器節點之間的關系，為傳感器數據項缺失的插補奠定基礎。

在關聯規則挖掘的兩個基本過程中，其中第(1)個基本過程是關聯規則挖掘算法設計的關鍵基礎，頻繁傳感器節點的查找效率的高低直接影響該挖掘算法有效性，這一步驟也是計算密集型過程，一般要通過并行分布式計算來處理該過程。而第(2)個基本過程僅僅是根據生成的頻繁傳感器節點的集合按照一定生成規則來創建相應蘊含式強關聯規則的過程，不是計算密集型過程。因此，目前關聯規則算法設計關鍵問題主要是圍繞怎樣來生成最大傳感器頻繁節點集合展開的。

3 基于時空關系和關聯規則挖掘的上下文信息缺失插補方法

為了更加準確進行上下文信息缺失數據插補，使數據缺失插補更加接近實際應用，本文引入時間新鮮度的概念。對傳感數據采樣序列回合號(round_number)進行加權，按照指數級np(p≥1)對采集到的傳感器數據進行時間序列化，時間新鮮度大的數據在插補的過程中占有更大的權重。因此，更加準確、真實反映傳感器數據的實際使用。本文還對支持度和信任度重新進行了定義，主要是考慮了時間新鮮度的概念，在本文中分別命名為加權支持度和加權信任度：

定義 7 加權支持度：在無線傳感網絡中，傳感器X和Y在某一段時間區間內采集的數據項中相同的帶有序列號加權權重個數和傳感器X和Y在這一段時間區間內采集的數據項的總的帶有序列號加權權重個數的比值稱之為關聯規則X→Y的加權支持度。數據項集合D的加權支持度通常記作 wei_supp(D)，關聯規則X→Y的加權支持度通常記作wei_supp(X→Y)。

定義 8 加權信任度：在無線傳感網絡中，對于傳感器X和Y，在某一段時間區間內，傳感器X采集到的帶有序列號加權權重的數據項而同時傳感器Y也能夠同時采集到相同帶有序列號加權權重的數據項概率可能性的大小，稱之為關聯規則X→Y的加權信任度，由加權信任度的定義可知加權信任度可以用加權支持度來表示成為 wei_supp(X→Y)/wei_supp(X)。同理，可以定義最小加權支持度和最小加權信任度，本文不再贅述。

對傳感器數據采用時空關系處理后，得到的傳感器數據再進行關聯規則挖掘，本文采用無冗余的閉頻數據項集關聯規則挖掘的方法，節省計算的時間和內存空間的占用，提高傳感器數據插補的效率和準確性，有利于實時性系統的應用。

定義9 閉數據項集：在無線傳感器網絡中，傳感器節點采集到的數據項集合設定為S={s1,s2,…,sm}是m維的傳感器數據項的序列號，U={u1,u2,… ,un}是n維數據項數值，則數據項可形式化為P=S.U., 設A，B為數據項序列號S的子集，A的個數為k的稱A為k數據項集，傳感器采集的數據流序列b為P的子集。則閉數據項集是滿足以下的函數f和g的傳感器數據序列：對于f(B)={i∈P|b∈B,i∈b}以及g(A)={b∈S|i∈A,i∈b}，函數f表示返回所有包含在傳感器采集數據序列B中的數據項集合，而函數g表示的返回的是包含給定數據項集A的數據序列集合。數據項A是閉數據項及當且僅當下式成立g(f(A))=f(g(A))=f?g(A)=A，H=f?g稱作閉運算或者稱作閉操作符。

定義10 閉頻數據項集：設P首先是閉數據項集，如果它的加權支持度大于或者等于用戶定義的最小加權支持度，則P為閉頻數據項集。

對采集到的傳感器數據進行序列號(回合號)加權，并引入了時間新鮮度。而對于傳感器數據之間的空間位置關系，主要是進行空間相似度計算，即是采用Pearson(皮爾森)相關系數的方法，找到空間上最相近的傳感器數據，然后再進行關聯規則的挖掘。

關聯規則挖掘算法是計算密集型的算法，為了減小計算的復雜度，提高上下文信息缺失插補的準確性，結合集合傳感器數據的特點，首先要對數據進行時空化處理。

本節根據關聯規則挖掘的兩個步驟，結合傳感數據的時空特性，提出基于時空關系和關聯規則挖掘的上下文信息缺失插補的基本過程可分為4步：

第1步 傳感數據空間化 對采集到的傳感數據首先計算其空間的相關度。本文采用Pearson相關系數法。Pearson相關系數法是計算兩個變量X和Y之間相關度常用的方法，其數值在[-1,1],用戶定義閾值，比如選擇 Pearson相關系數大于等于 0.5的那些傳感器作為關聯規則挖掘的傳感器S1,S2,…,。空間化后降低計算復雜度，利于實時性的應用，也大大提高了數據插補的準確性。

通常是采用相關相似度度量公式即Pearson相關系數度量各傳感器之間的相關度，設傳感器i和傳感器j共同采集的數據集合為Ii,j，則傳感器i和傳感器j的相似度sim(i,j)為其中Ri,c表示傳感器i對數據c的采集，和分別表示傳感器i和傳感器j對數據的平均值。注意，數據的平均值是指兩個傳感器有共同采集數值的平均值。求得和相關相似性系數的范圍是[-1,1]，相關系數越大，則表示這兩個傳感器的采集數據越接近，其采集的準確率就越高。

第2步 傳感數據時間序列化 對采集到的傳感數據按照回合進行加權處理。使采集到的數據和時間進行相關聯。每個傳感器數據前面加上相應的回合權重系數。在此基礎上計算最小加權支持度和最小加權信任度。對傳感器數據時間序列加權的方法可采用各種不同的方法。要根據具體的問題具體分析，主要是考慮數據對時間的敏感程度大小，小的可以采用線性增長的趨勢y=a?x，對時間敏感程度高的數據可以采用指數增長的方式，例如y=a?pn(p≥1)的方式，其中p為調整參數，其數值根據具體數據特點而定。

第 3步 查找頻繁數據項集 通過用戶給定的最小加權支持度wei_minsupp，找出所有頻繁數據項集合，也就是滿足加權支持度大于等于 wei_minsupp的數據項集。實際上，這些頻繁數據項集可能具有推出關系。不失一般性，我們只考慮那些不被其它頻繁數據項集所推出的頻繁大數據項的集合。而這些頻繁大數據項集是形成強關聯規則的前提基礎。

以溫度傳感器采集的溫度數據為例，如表 1。假設有4個傳感器S1,S2,S3,S4，假定p=3且第4回合數據出現缺失。

表1 4個溫度傳感器采集的溫度數據及其缺失情況

假設最小加權支持度 50%，最小加權信任度50%。由表 2可知，閉頻數據項集及其最小加權支持度分別為{S1.72,S3.74,S4.62}=2,{S1.72,S4.62}=3, {S2.62,S4.62}=2, {S4.62}=4。

第 4步 生成強關聯規則 通過用戶給定的最小加權信任度 wei_minconf，在每一個最大頻繁數據項集合中，生成加權信任度大于等于 wei_minconf的強關聯規則。

表2 閉頻數據項集及其最小加權支持度

產生關聯規則的具體操作過程如下：

(1)對于每一個頻繁數據項集P，產生所有的P的非空、真子集合。

(2)對于P的每一個非空、真子集Q，如果supp(P)/supp(Q)大于等于最小加權信任度，則輸出強關聯規則Q→(P-Q)。

對于上例來說，可以得出：規則1：{S1.72,S4.62}→S3.74,加權支持度為 1/2，加權信任度為 2/3。規則 2：S4.62→S2.62，加權支持度為 1/2，加權信任度為1/2。

因此，對于第4回合采集到的數據，S2缺失的數據66.7%可能是62，S3采集到的數據50%可能是74。

4 仿真實驗及結果分析

4.1 實驗環境

硬件配置如下：CPU: Inte1Pentium 2.8G；內存：DDR512M；

軟件環境如下：操作系統：windows XP；數據庫：MySQLserve:5.0；編程語言：R PROJECT。

4.2 仿真實驗及結果分析

本文實驗數據來自于美國三菱電子研究實驗室MERL(Mitsubishi Electric Research Labs)公開的一個大規模傳感器數據集，實驗數據可以從網站http://www.merl.com/wmd通過 FTP獲得：ftp://wmd@ftp.merl.com/,username:wmd passwd:w0rksh0pWMD，MERL主要是利用了200個傳感器來記錄實驗室兩層建筑物辦公人員一年內的不同時間不同位置的活動情況。為了簡化起見，本文實驗取了其中的部分實驗數據，包括100個不同位置不同時間段的溫度傳感器數據，使用溫度傳感器采集的 20個回合數據來進行實驗。本文利用 SQL SERVER數據庫存儲傳感器數據，并利用 R PROJECT軟件對傳感器數據進行統計分析處理，R PROJECT是一個有著統計分析功能及強大作圖功能的開源軟件系統。

實驗 1 缺失數據插補的準確性比較 為了比較各種插補方法的準確性，本文采用常用均方根誤差RMSE(Root Mean Square Error)進行比較，其公式如下：

其中iA是傳感器實際值，Ei是傳感器插補值，n為缺失的數量，N是采用數據集子集數量，最終結果可以取幾個子集的平均值，均方根誤差RMSE越小，表示插補方法越準確。

本文提出的STARM方法與傳統簡單線性回歸(SLR)，EM 算法，WARM(Window Association Rule Mining)方法，CARM(Closed Association Rule Mining)方法，FARM(Freshness Association Rule Mining)方法進行比較如圖1所示。

從圖 1可以看出，數據插補準確性，STARM要優于傳統的統計方法和其他的關聯規則挖掘方法。

實驗 2 缺失數據插補所用的時間比較 本文提出的對傳感器數據空間化減小了計算的復雜性，而同時采用回合權系數法引入的時間新鮮度又增加了計算的復雜度，最后的綜合結果需要通過仿真實驗進行實際性能評估。

本文采用平均插補時間 AIT(Average Imputation Time)即每個回合平均占用的數據插補的時間，其仿真結果如圖2所示。

從圖2可以看出，EM和SLR由于算法的簡單性所用的時間最少，而與其他算法比較中 STARM效率較高，所用時間較少，從而節省了系統時間開銷。

實驗3 缺失數據插補所占用內存空間比較

本文還采用了缺失數據插補過程中所占內存空間大小來衡量STARM算法的高效性。其仿真結果如圖3所示。

從圖3可以看出，EM和SLR由于算法的簡單性所占用的內存最小，而與其他算法比較中STARM 效率較高，占用內存較小，從而節省了系統空間開銷。

5 結束語

本文依據傳感器數據這一流數據的關聯性和時空特性，引入了時間新鮮度的概念，并依據傳統的關聯規則挖掘的基本過程，提出了基于時空關系和關聯規則挖掘的上下文信息缺失插補方法(STARM)，較傳統的缺失數據插補方法具有更高的準確性，并且減小了時空開銷。實驗證明此方法的在數據插補準確性優于傳統的統計方法和其他關聯規則挖掘方法，驗證了算法的合理性和高效性。

由于對傳感器數據進行時間序列化，如果采用指數加權，其數值會呈指數級遞增，數據有可能會溢出，如何進行控制數據的溢出，是本文未來進一步的研究工作。

圖1 SLR，EM，WARM，CARM，FARM，STARM之間RMSE值的比較

圖2 SLR，EM，WARM，CARM， FARM，STARM之間AIT值的比較

圖3 SLR，EM，WARM，CARM，FARM，STARM之間占用內存的比較

[1] Cool A L. A review of methods for dealing with missing data[C]. Paper presented at the Annual Meeting of the Southwest Educational Research Association, Dallas, TX,2000: 1-34.

[2] Shao Jun and Wang Han-sheng. Confidence intervals based on survey data with nearest neighbor imputation [J].Statistica Sinica, 2008, 18(1): 281-297.

[3] Gu Dong-bing. Distributed EM algorithm for Gaussian mixtures in sensor networks [J].IEEE Transactions on Neural Networks, 2008, 19(7): 1154-1166.

[4] Allison P D. Missing data [D]. Thousand Oaks, CA Sage,2002.

[5] Qin Yong-song and Zhang Shi-chao. Empirical likelihood confidence intervals for differences between two datasets with missing data [J].Pattern Recognition Letters, 2008, 29(6):803-812.

[6] 龐新生. 分層隨機抽樣條件下缺失數據的多重插補方法[J].統計與信息論壇, 2009, 24(5): 19-21.Pang Xin-sheng. Multiple imputation for missing data in stratified random sampling [J].Statistics&Information Forum, 2009 24(5): 19-21.

[7] 金勇進, 邵軍. 缺失數據的統計處理. 北京: 中國統計出版社,2009: 155-161.Jin Yong-jin and Shao Jun. Statistical Analysis with Missing Data [M]. Beijing: China Statistics Press, 2009: 155-161.

[8] Deshpande A, Guestrin C, Madden S, Hellerstein J, and Hong W. Model-driven data acquisition in sensor networks[C]. Proceedings of the 30th VLDB (Very Large Databases)Conference, Toronto, Canada, 2004: 588-599.

[9] Le Gruenwald, Hamed Chok, and Mazen Aboukhamis. Using data mining to estimate missing sensor data[C]. Proceedings of the Seventh IEEE International Conference on Data Mining Workshops, Norman, USA, 2007: 207-212.

[10] Nan Jiang. A data imputation model in sensor databases [C].High Performance Computing and Communications, Third International Conference, HPCC 2007, Houston, USA,September 26-28, 2007: 86-96.

[11] Li Y and Parker L E. Classification with missing data in a wireless sensor network[C]. IEEE Southeast Conference,Huntsville, Alabama, April 2008: 533-538.

[12] Li Y and Parker L E. A spatial-temporal imputation technique for classification with missing data in a wireless sensor network[C]. 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, Acropolis Convention Center Nice, France, Sept. 22-26, 2008: 3272-3279.