基于時(shí)空關(guān)系和關(guān)聯(lián)規(guī)則挖掘的上下文信息缺失插補(bǔ)研究

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

(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 北京 100876)

1 引言

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

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

為了更加準(zhǔn)確地對(duì)傳感器數(shù)據(jù)缺失進(jìn)行插補(bǔ)，本文針對(duì)傳感器數(shù)據(jù)這一類上下文信息，根據(jù)傳感器數(shù)據(jù)的關(guān)聯(lián)性和時(shí)空特性兩大特點(diǎn)，提出了基于時(shí)空關(guān)系和關(guān)聯(lián)規(guī)則挖掘的上下文信息缺失插補(bǔ)方法，全面綜合討論了數(shù)據(jù)插補(bǔ)方法，提高了傳感器數(shù)據(jù)缺失插補(bǔ)的準(zhǔn)確性。

本文第2節(jié)首先介紹了關(guān)聯(lián)規(guī)則挖掘的基本概念和基本步驟。第3節(jié)提出了基于時(shí)空關(guān)系和關(guān)聯(lián)規(guī)則挖掘的上下文信息缺失插補(bǔ)方法，并詳細(xì)闡述基于時(shí)空關(guān)系和關(guān)聯(lián)規(guī)則挖掘的上下文信息缺失插補(bǔ)的詳細(xì)過程。第4節(jié)通過仿真實(shí)驗(yàn)驗(yàn)證了基于時(shí)空關(guān)系和關(guān)聯(lián)規(guī)則挖掘的上下文信息缺失插補(bǔ)方法的高效性和合理性。最后給出結(jié)論和未來的工作。

2 關(guān)聯(lián)規(guī)則挖掘

2.1 關(guān)聯(lián)規(guī)則挖掘的相關(guān)概念

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

定義2 支持度：在無線傳感網(wǎng)絡(luò)中，傳感器X和Y在某一段時(shí)間區(qū)間內(nèi)采集的數(shù)據(jù)項(xiàng)中相同的個(gè)數(shù)和傳感器X和Y在這一段時(shí)間區(qū)間內(nèi)采集的數(shù)據(jù)項(xiàng)的總的個(gè)數(shù)的比值稱之為關(guān)聯(lián)規(guī)則X→Y的支持度。數(shù)據(jù)項(xiàng)集合D的支持度通常記作supp(D)，關(guān)聯(lián)規(guī)則X→Y的支持度通常記作supp(X→Y)。

定義 3 信任度：在無線傳感網(wǎng)絡(luò)中，對(duì)于傳感器X和Y，在某一段時(shí)間區(qū)間內(nèi)，傳感器X采集到的數(shù)據(jù)項(xiàng)而同時(shí)傳感器Y也能夠同時(shí)采集到相同數(shù)據(jù)項(xiàng)概率可能性的大小，稱之為關(guān)聯(lián)規(guī)則X→Y的信任度，由信任度的定義可知信任度可以用支持度來表示成為supp(X→Y)/supp(X)。

定義 4 最小支持度：在實(shí)際的應(yīng)用系統(tǒng)中，根據(jù)用戶對(duì)系統(tǒng)的要求不同確定的關(guān)聯(lián)規(guī)則支持度需要滿足的最小的數(shù)值，它是滿足用戶最低需求的支持度的數(shù)值，稱之為最小支持度，通常記作minsupp。

定義 5 最小信任度：在實(shí)際的應(yīng)用系統(tǒng)中，根據(jù)用戶對(duì)系統(tǒng)的要求不同確定的關(guān)聯(lián)規(guī)則信任度需要滿足的最小的數(shù)值，它是滿足用戶最低可靠性保證的數(shù)值，稱之為最小信任度，通常記作minconf。

定義 6 頻繁數(shù)據(jù)項(xiàng)集：對(duì)于用戶給定的最小支持度minsupp，傳感器X采集到的數(shù)據(jù)項(xiàng)D支持度如果大于該最小支持度minsupp，則稱數(shù)據(jù)項(xiàng)D為頻繁數(shù)據(jù)項(xiàng)集，同時(shí)稱傳感器X為頻繁節(jié)點(diǎn)集。

2.2 關(guān)聯(lián)規(guī)則挖掘概念

在上下文信息采集網(wǎng)絡(luò)中，對(duì)于傳感器X和Y，形如蘊(yùn)含式X→Y稱之為關(guān)聯(lián)規(guī)則，其中傳感器X和Y都是獨(dú)立采集的。關(guān)聯(lián)規(guī)則是統(tǒng)計(jì)學(xué)中簡單而又實(shí)用的一種推理規(guī)則，也是數(shù)據(jù)挖掘研究熱點(diǎn)領(lǐng)域，特別適用于分析傳感器采集的大量數(shù)據(jù)項(xiàng)之間頻繁出現(xiàn)的模態(tài)關(guān)聯(lián)性，從而對(duì)傳感器采集的數(shù)據(jù)缺失進(jìn)行插補(bǔ)。

支持度與信任分別大于用戶定義的最小閾值minsupp和minconf的規(guī)則通常稱為強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘的目標(biāo)就是從給定的傳感器節(jié)點(diǎn)所采集的所有數(shù)據(jù)項(xiàng)中找到所有的強(qiáng)關(guān)聯(lián)規(guī)則節(jié)點(diǎn)，分析出傳感器節(jié)點(diǎn)所采集的所有數(shù)據(jù)項(xiàng)的規(guī)律，從而挖掘出各節(jié)點(diǎn)之間關(guān)聯(lián)性、相關(guān)性，進(jìn)一步可以對(duì)節(jié)點(diǎn)數(shù)據(jù)項(xiàng)進(jìn)行推理、預(yù)測。

2.3 關(guān)聯(lián)規(guī)則挖掘的基本過程

由關(guān)聯(lián)規(guī)則挖掘的形式化定義可知，通常情況下，對(duì)于關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個(gè)基本的過程：

(1)頻繁傳感器節(jié)點(diǎn)的查找 對(duì)于用戶設(shè)定的最小支持度 minsupp，從傳感器網(wǎng)絡(luò)系統(tǒng)中查找所有的頻繁傳感器節(jié)點(diǎn)集合，即滿足支持度大于等于minsupp的傳感器節(jié)點(diǎn)集合。實(shí)際上，這些頻繁傳感器節(jié)點(diǎn)集合或許具有一定的推出關(guān)系。不失一般性，我們通常只考慮那些不被其它傳感器節(jié)點(diǎn)集合所推出的頻繁最大傳感器節(jié)點(diǎn)集合。這些頻繁大傳感器節(jié)點(diǎn)集合是形成強(qiáng)關(guān)聯(lián)規(guī)則前提。

(2)強(qiáng)關(guān)聯(lián)規(guī)則的形成 對(duì)于用戶設(shè)定的最小信任度 minconf，在頻繁最大傳感器節(jié)點(diǎn)集合，根據(jù)一定的具體方法來生成信任度大于等于 minconf的關(guān)聯(lián)規(guī)則，從而形成蘊(yùn)含式的強(qiáng)關(guān)聯(lián)規(guī)則，進(jìn)一步可以推理出傳感器節(jié)點(diǎn)之間的關(guān)系，為傳感器數(shù)據(jù)項(xiàng)缺失的插補(bǔ)奠定基礎(chǔ)。

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

3 基于時(shí)空關(guān)系和關(guān)聯(lián)規(guī)則挖掘的上下文信息缺失插補(bǔ)方法

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

定義 7 加權(quán)支持度：在無線傳感網(wǎng)絡(luò)中，傳感器X和Y在某一段時(shí)間區(qū)間內(nèi)采集的數(shù)據(jù)項(xiàng)中相同的帶有序列號(hào)加權(quán)權(quán)重個(gè)數(shù)和傳感器X和Y在這一段時(shí)間區(qū)間內(nèi)采集的數(shù)據(jù)項(xiàng)的總的帶有序列號(hào)加權(quán)權(quán)重個(gè)數(shù)的比值稱之為關(guān)聯(lián)規(guī)則X→Y的加權(quán)支持度。數(shù)據(jù)項(xiàng)集合D的加權(quán)支持度通常記作 wei_supp(D)，關(guān)聯(lián)規(guī)則X→Y的加權(quán)支持度通常記作wei_supp(X→Y)。

定義 8 加權(quán)信任度：在無線傳感網(wǎng)絡(luò)中，對(duì)于傳感器X和Y，在某一段時(shí)間區(qū)間內(nèi)，傳感器X采集到的帶有序列號(hào)加權(quán)權(quán)重的數(shù)據(jù)項(xiàng)而同時(shí)傳感器Y也能夠同時(shí)采集到相同帶有序列號(hào)加權(quán)權(quán)重的數(shù)據(jù)項(xiàng)概率可能性的大小，稱之為關(guān)聯(lián)規(guī)則X→Y的加權(quán)信任度，由加權(quán)信任度的定義可知加權(quán)信任度可以用加權(quán)支持度來表示成為 wei_supp(X→Y)/wei_supp(X)。同理，可以定義最小加權(quán)支持度和最小加權(quán)信任度，本文不再贅述。

對(duì)傳感器數(shù)據(jù)采用時(shí)空關(guān)系處理后，得到的傳感器數(shù)據(jù)再進(jìn)行關(guān)聯(lián)規(guī)則挖掘，本文采用無冗余的閉頻數(shù)據(jù)項(xiàng)集關(guān)聯(lián)規(guī)則挖掘的方法，節(jié)省計(jì)算的時(shí)間和內(nèi)存空間的占用，提高傳感器數(shù)據(jù)插補(bǔ)的效率和準(zhǔn)確性，有利于實(shí)時(shí)性系統(tǒng)的應(yīng)用。

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

定義10 閉頻數(shù)據(jù)項(xiàng)集：設(shè)P首先是閉數(shù)據(jù)項(xiàng)集，如果它的加權(quán)支持度大于或者等于用戶定義的最小加權(quán)支持度，則P為閉頻數(shù)據(jù)項(xiàng)集。

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

關(guān)聯(lián)規(guī)則挖掘算法是計(jì)算密集型的算法，為了減小計(jì)算的復(fù)雜度，提高上下文信息缺失插補(bǔ)的準(zhǔn)確性，結(jié)合集合傳感器數(shù)據(jù)的特點(diǎn)，首先要對(duì)數(shù)據(jù)進(jìn)行時(shí)空化處理。

本節(jié)根據(jù)關(guān)聯(lián)規(guī)則挖掘的兩個(gè)步驟，結(jié)合傳感數(shù)據(jù)的時(shí)空特性，提出基于時(shí)空關(guān)系和關(guān)聯(lián)規(guī)則挖掘的上下文信息缺失插補(bǔ)的基本過程可分為4步：

第1步 傳感數(shù)據(jù)空間化 對(duì)采集到的傳感數(shù)據(jù)首先計(jì)算其空間的相關(guān)度。本文采用Pearson相關(guān)系數(shù)法。Pearson相關(guān)系數(shù)法是計(jì)算兩個(gè)變量X和Y之間相關(guān)度常用的方法，其數(shù)值在[-1,1],用戶定義閾值，比如選擇 Pearson相關(guān)系數(shù)大于等于 0.5的那些傳感器作為關(guān)聯(lián)規(guī)則挖掘的傳感器S1,S2,…,?？臻g化后降低計(jì)算復(fù)雜度，利于實(shí)時(shí)性的應(yīng)用，也大大提高了數(shù)據(jù)插補(bǔ)的準(zhǔn)確性。

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

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

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

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

表1 4個(gè)溫度傳感器采集的溫度數(shù)據(jù)及其缺失情況

假設(shè)最小加權(quán)支持度 50%，最小加權(quán)信任度50%。由表 2可知，閉頻數(shù)據(jù)項(xiàng)集及其最小加權(quán)支持度分別為{S1.72,S3.74,S4.62}=2,{S1.72,S4.62}=3, {S2.62,S4.62}=2, {S4.62}=4。

第 4步 生成強(qiáng)關(guān)聯(lián)規(guī)則 通過用戶給定的最小加權(quán)信任度 wei_minconf，在每一個(gè)最大頻繁數(shù)據(jù)項(xiàng)集合中，生成加權(quán)信任度大于等于 wei_minconf的強(qiáng)關(guān)聯(lián)規(guī)則。

表2 閉頻數(shù)據(jù)項(xiàng)集及其最小加權(quán)支持度

產(chǎn)生關(guān)聯(lián)規(guī)則的具體操作過程如下：

(1)對(duì)于每一個(gè)頻繁數(shù)據(jù)項(xiàng)集P，產(chǎn)生所有的P的非空、真子集合。

(2)對(duì)于P的每一個(gè)非空、真子集Q，如果supp(P)/supp(Q)大于等于最小加權(quán)信任度，則輸出強(qiáng)關(guān)聯(lián)規(guī)則Q→(P-Q)。

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

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

4 仿真實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

硬件配置如下：CPU: Inte1Pentium 2.8G；內(nèi)存：DDR512M；

軟件環(huán)境如下：操作系統(tǒng)：windows XP；數(shù)據(jù)庫：MySQLserve:5.0；編程語言：R PROJECT。

4.2 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

其中iA是傳感器實(shí)際值，Ei是傳感器插補(bǔ)值，n為缺失的數(shù)量，N是采用數(shù)據(jù)集子集數(shù)量，最終結(jié)果可以取幾個(gè)子集的平均值，均方根誤差RMSE越小，表示插補(bǔ)方法越準(zhǔn)確。

本文提出的STARM方法與傳統(tǒng)簡單線性回歸(SLR)，EM 算法，WARM(Window Association Rule Mining)方法，CARM(Closed Association Rule Mining)方法，F(xiàn)ARM(Freshness Association Rule Mining)方法進(jìn)行比較如圖1所示。

從圖 1可以看出，數(shù)據(jù)插補(bǔ)準(zhǔn)確性，STARM要優(yōu)于傳統(tǒng)的統(tǒng)計(jì)方法和其他的關(guān)聯(lián)規(guī)則挖掘方法。

實(shí)驗(yàn) 2 缺失數(shù)據(jù)插補(bǔ)所用的時(shí)間比較 本文提出的對(duì)傳感器數(shù)據(jù)空間化減小了計(jì)算的復(fù)雜性，而同時(shí)采用回合權(quán)系數(shù)法引入的時(shí)間新鮮度又增加了計(jì)算的復(fù)雜度，最后的綜合結(jié)果需要通過仿真實(shí)驗(yàn)進(jìn)行實(shí)際性能評(píng)估。

本文采用平均插補(bǔ)時(shí)間 AIT(Average Imputation Time)即每個(gè)回合平均占用的數(shù)據(jù)插補(bǔ)的時(shí)間，其仿真結(jié)果如圖2所示。

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

實(shí)驗(yàn)3 缺失數(shù)據(jù)插補(bǔ)所占用內(nèi)存空間比較

本文還采用了缺失數(shù)據(jù)插補(bǔ)過程中所占內(nèi)存空間大小來衡量STARM算法的高效性。其仿真結(jié)果如圖3所示。

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

5 結(jié)束語

本文依據(jù)傳感器數(shù)據(jù)這一流數(shù)據(jù)的關(guān)聯(lián)性和時(shí)空特性，引入了時(shí)間新鮮度的概念，并依據(jù)傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘的基本過程，提出了基于時(shí)空關(guān)系和關(guān)聯(lián)規(guī)則挖掘的上下文信息缺失插補(bǔ)方法(STARM)，較傳統(tǒng)的缺失數(shù)據(jù)插補(bǔ)方法具有更高的準(zhǔn)確性，并且減小了時(shí)空開銷。實(shí)驗(yàn)證明此方法的在數(shù)據(jù)插補(bǔ)準(zhǔn)確性優(yōu)于傳統(tǒng)的統(tǒng)計(jì)方法和其他關(guān)聯(lián)規(guī)則挖掘方法，驗(yàn)證了算法的合理性和高效性。

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

圖1 SLR，EM，WARM，CARM，F(xiàn)ARM，STARM之間RMSE值的比較

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

圖3 SLR，EM，WARM，CARM，F(xiàn)ARM，STARM之間占用內(nèi)存的比較

[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ī)抽樣條件下缺失數(shù)據(jù)的多重插補(bǔ)方法[J].統(tǒng)計(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] 金勇進(jìn), 邵軍. 缺失數(shù)據(jù)的統(tǒng)計(jì)處理. 北京: 中國統(tǒng)計(jì)出版社,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.