葉　李

(中國西南電子技術研究所，四川 成都 610036)

?

傳感器網(wǎng)絡時間序列數(shù)據(jù)的事件分類研究

葉李

(中國西南電子技術研究所，四川 成都 610036)

摘要：目前智能環(huán)境中傳感器網(wǎng)絡所采集的海量數(shù)據(jù)面臨著進行有效事件的模式分類及異常檢測的難題。為了有效對智能環(huán)境中傳感器網(wǎng)絡采集的時間序列數(shù)據(jù)所表征的事件進行分類，提出了基于協(xié)方差特征空間映射數(shù)據(jù)的聚類分析方法。通過對采集得到的時間序列數(shù)據(jù)按時隙進行劃分，映射到協(xié)方差特征空間，然后對映射后的數(shù)據(jù)進行了動態(tài)密度聚類，從而實現(xiàn)對事件的分類；并根據(jù)聚類結果建立分類模板，作為對日常事件進行分類劃分的檢測方法，同時利用所得的分類模板，實現(xiàn)對異常事件的檢測。實驗結果表明，基于協(xié)方差特征空間映射數(shù)據(jù)的聚類分析方法能有效對傳感器網(wǎng)絡采集的時間序列數(shù)據(jù)所表征的事件進行分類，并能有效提升異常事件的檢測及篩選效果。

關鍵詞：事件分類；時間序列分析；密度聚類；智能環(huán)境

0引言

隨著自組織無線傳感器網(wǎng)絡(wireless ad-hoc sensor network, WASN)技術的發(fā)展，智能環(huán)境技術得到了高速發(fā)展[1-4]。在智能環(huán)境的技術應用中，各個傳感器節(jié)點將定期采集周圍環(huán)境中的事件和數(shù)據(jù)，包括溫度、濕度、噪聲等，并發(fā)送到中心節(jié)點進行分析處理。目前，對WASN所采集的海量數(shù)據(jù)進行分析處理已經(jīng)成為重要的研究課題。

傳感器網(wǎng)絡所采集的數(shù)據(jù)是一系列按照時間順序排列的信號，在實際的傳感器部署環(huán)境中，發(fā)生的各種事件影響了多種類型的傳感器信號的數(shù)值。不同事件促發(fā)的信號類別、時間間隔、發(fā)生頻率均有不同。目前，已有的相關研究工作集中在如何從傳感器網(wǎng)絡采集的時間序列信號中發(fā)現(xiàn)部署環(huán)境下發(fā)生的事件是事件序列時間探測所關注的問題，如何從事件探測中篩選出異常事件仍然是一個極具挑戰(zhàn)性的工作，困難的原因之一是在新布置的智能環(huán)境中，沒有已知的異常模式進行識別的匹配。

在過去的工作中，通過對時序數(shù)據(jù)在協(xié)方差特征空間的映射，利用基于馬氏距離的T2檢驗進行異常事件的檢測，實驗結果表明，此方法能有效檢測出WASN采集數(shù)據(jù)中存在的異常事件，得出日常事件模板[5]。但此方法仍然存在一些問題，如篩選參數(shù)的選擇對異常事件的篩選影響較大，容易篩選掉可能是正常的事件。為了解決上述問題，同時實現(xiàn)對事件的分類，本文提出了基于協(xié)方差特征空間映射數(shù)據(jù)的聚類分析方法，通過對時間序列數(shù)據(jù)按時隙進行劃分，映射到協(xié)方差特征空間，在此基礎上進行基于聚類的分析處理，進而對事件進行分類劃分。

實驗結果表明，本文提出的方法能夠有效對傳感器網(wǎng)絡的時間序列數(shù)據(jù)進行事件分類的分析處理，相對以前的工作，能更準確地對異常事件進行篩選。

1相關理論

1.1協(xié)方差特征空間

數(shù)據(jù)的協(xié)方差特征空間的應用已較為廣泛[6-7]，但針對智能環(huán)境中傳感器網(wǎng)絡所采集的數(shù)據(jù)處理有所不同。實際上，傳感器網(wǎng)絡的采集數(shù)據(jù)是一種時間序列數(shù)據(jù)。假設有q個傳感器，則某一時刻采集得到的觀測值x包含了q個數(shù)值，即x={f1,f2,…,fq}。在l(1≤l≤∞)時間段Tl內(nèi)，包含了n個時刻的觀測值的數(shù)據(jù)形成一個矩陣，該矩陣的協(xié)方差矩陣記為

(1)

由于cov(X,Y)=cov(Y,X)，可知協(xié)方差矩陣Ml為一對稱陣，可只針對矩陣的上三角數(shù)值進行分析。通過對Ml的計算，將時間段Tl內(nèi)的傳感器觀測值映射到了協(xié)方差特征空間，每對傳感器之間的關系構成了協(xié)方差特征空間的坐標。

在協(xié)方差特征空間中，按時間序列采集的各個時刻的原始數(shù)據(jù)是按時間段Tl為單位進行的匯總，與原始數(shù)據(jù)包含的q×l個維度相比，協(xié)方差特征空間包含的數(shù)據(jù)維度為[q×(q+1)]/2。當時間段Tl包含了l>(q+1)/2 個時刻觀測值的情況下，到協(xié)方差特征空間的映射方法在一定程度上壓縮了數(shù)據(jù)處理量。

將傳感器網(wǎng)絡在每個時刻采集的數(shù)據(jù)進行時間段分片后映射至協(xié)方差特征空間進行分析處理有2個優(yōu)勢：①就實際情況來說，各個自然事件的跨度通常由數(shù)分鐘至一個小時不等，而按秒或分鐘所采集的單時刻數(shù)據(jù)并不能從整體上反映出事件的自然屬性；②根據(jù)文獻[6]的研究分析表明，將單一數(shù)據(jù)分組匯總后映射至協(xié)方差特征空間的異常檢測技術相對單一數(shù)據(jù)檢測方式而言，能獲得更高的檢測準確率和運行效率。

1.2聚類分析

聚類分析就是在無先驗知識的情況下，將數(shù)據(jù)集劃分成簇，保證相同簇中的數(shù)據(jù)之間具有較高的相似度，不同簇的數(shù)據(jù)之間相似度較低，簇內(nèi)數(shù)據(jù)的相似度越高而簇間差別度越大，表明聚類的質量越高。聚類算法大體上包括了層次法(hierarchical)、劃分法(partitioning)、基于密度的方法(density-based)、基于網(wǎng)格的方法(grid-based)以及基于模型的方法(model-based)。

層次法聚類包括凝聚和分解2種方式，凝聚是從單個數(shù)據(jù)開始，不斷合并2個或多個最合適的簇，分解法是將所有的數(shù)據(jù)點看作一個大簇，然后按照準則不斷進行合適的分裂直到滿足預設條件，代表算法有Birch，Cure和Chameleon等；劃分法聚類只是創(chuàng)建數(shù)據(jù)集的一個單層的劃分，其代表算法包括K-means和K-medoids算法等；基于密度的方法是基于數(shù)據(jù)密度來度量類間相似度，通過判斷區(qū)域中的點密度是否大于設定的閾值講數(shù)據(jù)點聚類；基于網(wǎng)格的方法是將數(shù)據(jù)空間劃分成有限數(shù)目的數(shù)據(jù)單元，通過數(shù)據(jù)網(wǎng)格結構進行聚類處理，其代表算法有Sting，Clique，WaveCluster等；基于模型的聚類算法運行在根據(jù)目標數(shù)據(jù)集的分布特征假設的函數(shù)模型之上，典型的聚類模型包括統(tǒng)計的模型和神經(jīng)網(wǎng)絡的模型。

由于同類事件通過傳感器所采集的數(shù)據(jù)具有類似屬性值的特點，選用基于密度的方法對采集數(shù)據(jù)進行聚類分析處理?；诿芏鹊木垲惙椒ㄗR別類的一個主要依據(jù)是每個類中的點的密度明顯高于類外點的密度。

基于密度的聚類算法通過檢查數(shù)據(jù)集中每個對象的ε-領域，即鄰域半徑來尋找聚類。其輸入?yún)?shù)為ε-領域和MinPts(指在任何簇中的點的最小數(shù)目)。它通過反復尋找核心對象的直接密度可達對象，合并密度可達簇，當沒有新的對象可以添加到任何簇時，完成聚類。基于密度的聚類算法涉及的基本概念包括以下5方面。

1)密度。定義為在某給定的距離內(nèi)，包含的對象的最小數(shù)目；

2)核心對象。根據(jù)對象的ε-領域包含對象的數(shù)目確定，如果包含大于或等于MinPts個對象，則稱其為核心對象；

3)直接密度可達。o是從p直接密度可達是指給定對象集合D和核心對象p，對象o在對象p的ε-領域內(nèi)；

4)密度可達。對象on是從對象o密度可達是指存在一個對象鏈o1，o2，…，on，oi+1是從oi關于ε-領域直接密度可達的；

5)密度相連。對象p和q是密度相連是指對象集合D中存在一個對象o，使得對象p和q是從o密度可達的。

經(jīng)典的基于密度的聚類算法，如具有噪聲的基于密度的聚類(density-basedspatialclusteringofapplicationswithnoise,DBSCAN)方法等，通過檢查數(shù)據(jù)集中每個對象的ε-領域來尋找類簇。算法中的ε-領域及密度閾值MinPts為全局參數(shù)，因此，對密度不均勻的數(shù)據(jù)分類效果較差。在處理密度不均勻的數(shù)據(jù)集上，共享最近鄰密度聚類(sharingnearestneighbor，SNN)[8]的聚類效果相對具有優(yōu)勢，相對DBSCAN而言，SNN改進了密度的定義方法，引入新的全局參數(shù)k，將對象所有k近鄰中與其共享的鄰居個數(shù)總和定義為密度。通過密度定義的改變動態(tài)反映簇的密度變化，從而識別密度不均勻的簇[9-11]。

2事件分類分析

傳感器網(wǎng)絡時間序列數(shù)據(jù)的事件分類分析處理主要包含3個過程：首先，對傳感器網(wǎng)絡原始采集數(shù)據(jù)在協(xié)方差特征空間進行映射處理；然后，針對映射后的數(shù)據(jù)進行動態(tài)密度聚類，對按照時間片劃分的數(shù)據(jù)聚類處理形成事件分類簇；最后，針對日常數(shù)據(jù)，根據(jù)事件分類簇進行事件分類判別。

2.1數(shù)據(jù)映射處理

由于傳感器網(wǎng)絡所采集的數(shù)據(jù)是某一時刻的瞬時數(shù)值，并不能準確反映環(huán)境中實際的事件變化。因此，將傳感器網(wǎng)絡采集的一系列原始數(shù)據(jù)集D按時間片劃分成包含n個時刻采集數(shù)據(jù)的Tl的形式。

按照時間順序將包含n個時刻采集數(shù)據(jù)的時間片數(shù)據(jù)Tl映射到協(xié)方差特征空間，取Tl數(shù)據(jù)生成的協(xié)方差矩陣的上三角數(shù)值，并拓展成列向量。

將所有拓展成列向量的時間片數(shù)據(jù)按時間匯聚形成數(shù)據(jù)矩陣，從而形成特征空間數(shù)據(jù)集M。數(shù)據(jù)集M中每個時間片的數(shù)據(jù)即視為需要聚類處理的一個對象。

2.2動態(tài)密度聚類

使用動態(tài)密度聚類算法，為了自動區(qū)分密度不同的簇，需對數(shù)據(jù)集M中的所有對象計算其密度值。選擇密度值最大的對象開始建立一個新簇，循環(huán)聚集從該對象直接密度可達的對象，直到該簇無新增對象；對剩余對象迭代此過程，直到完成全部對象的處理，形成聚類結果簇列表S。S中的每項都為一個類簇C，包含內(nèi)容為數(shù)據(jù)集M中的一個或多個數(shù)據(jù)項。

動態(tài)密度聚類分析的實現(xiàn)步驟描述如下。

輸入：數(shù)據(jù)集M、近鄰個數(shù)參數(shù)k、ε-領域及密度閾值MinPts。

輸出：聚類簇列表S。

1)計算數(shù)據(jù)集M中所有數(shù)據(jù)項對象的距離矩陣，根據(jù)距離矩陣及近鄰個數(shù)k、ε-領域參數(shù)計算每個對象o的密度值；

2)根據(jù)各個對象的密度值對所有對象排序；

3)選取未歸入類簇的密度最大的對象ol，建立新簇Cl；

4)遍歷距離矩陣，尋找所有從對象oi出發(fā)的關于ε-領域及密度閾值MinPts密度可達的對象oj，如果oj未加入其他簇中，則加入對象oj所對應的簇Ci；

5)重復步驟4)，直到?jīng)]有新的對象加入對象oi所對應的簇Ci；

6)重復步驟3)，直到所有對象都已處理完畢；

7)輸出聚類完成的簇列表S={C1,C2,…,Cm} 。

通過動態(tài)密度聚類方法，將協(xié)方差特征空間的數(shù)據(jù)進行了分類，分類的數(shù)據(jù)保存在聚類簇列表S中。后續(xù)數(shù)據(jù)可通過比對列表S中的類簇C中的模板數(shù)據(jù)進行分類處理。

2.3日常數(shù)據(jù)處理

獲得聚類分析結果后，剔除包含對象數(shù)目比例較少的聚類簇，將其包含的數(shù)據(jù)對象劃分為噪聲點或異常事件。而剩余的聚類簇列表S′，體現(xiàn)了傳感器網(wǎng)絡所監(jiān)測到的事件分類。聚類簇列表S′包含各簇Ci所對應的核心對象集{o1,o2,…，om}，可作為日常數(shù)據(jù)分類處理的判據(jù)。

分類判別的實現(xiàn)步驟描述如下。

1)系統(tǒng)獲得傳感器網(wǎng)絡采集了對應時間片的數(shù)據(jù)后，將其映射到協(xié)方差特征空間，形成待分類數(shù)據(jù)p；

2)將數(shù)據(jù)p與聚類簇列表S′包含各簇Ci所對應的核心對象集{o1,o2,…,om}進行距離計算，并獲得對應距離最小的類簇標識；

3)如果數(shù)據(jù)p與各簇Ci所對應的核心對象集{o1,o2,…，om}的距離均大于ε-領域，則將該時間片事件標識為異常事件報警；否則，將該事件分類為對應距離最小的類簇所標識的事件。

3實驗分析

實驗環(huán)境中，傳感器網(wǎng)絡采集的數(shù)據(jù)主要包括6種類型，分別為聲強、光強、動作、溫度、濕度以及二氧化碳濃度。6種不同類型的傳感器安裝在實驗室的一個測試房間內(nèi)，系統(tǒng)每分鐘采集并記錄一次傳感器數(shù)據(jù)。測試房間在日常的使用中包括了閑置、會議、清潔等模式。

實驗將傳感器網(wǎng)絡初始2個月的采集數(shù)據(jù)作為訓練集，按15min的間隔劃分時間片。通過對記錄半年多的實驗數(shù)據(jù)進行事件分類分析，聚類分析選擇近鄰個數(shù)參數(shù)k=8、ε-領域=0.15、密度閾值MinPts=5。

對實驗數(shù)據(jù)進行聚類分析處理后可以獲取該房間7×24小時的事件網(wǎng)格分類模板，如圖1所示。從圖1可以看出，工作日早上6—7點，為空調(diào)系統(tǒng)運行事件；晚上22—23點，為清掃事件；在工作日中存在4種不同強度的工作或會議事件；其余時刻均為空閑事件。除去篩選后的異常數(shù)據(jù)外，實驗通過數(shù)據(jù)的聚類分析處理將事件分成了7類，為日常行為模式的模型建立奠定了數(shù)據(jù)基礎，這是前期工作所不能得到的。

未進行事件分類的實驗結果如圖2所示，可以看出，通過聚類分析處理后的事件分類模板提供了更加明確的關于監(jiān)控房間的事件分類模式。

圖2　事件分類模板Fig.2　Event classification template

基于T2異常檢測后獲得的分類模板如圖3所示，與圖2中的基于聚類分析方法進行的異常事件檢測結果相比，可以看出，基于聚類的異常事件篩選形成的時間模板更加精細準確。與實際日常事件記錄比對可以確定，基于聚類的檢測方法提高了對異常事件的檢測準確率。

圖3　基于T2異常檢測處理的分類模板Fig.3　Event classification template after originalanomaly detection

4結論

本文在前期基于異常事件檢測的傳感器網(wǎng)絡數(shù)據(jù)分析工作的基礎上，提出了基于協(xié)方差特征空間映射數(shù)據(jù)的聚類分析方法。對傳感器網(wǎng)絡在每個時刻采集的數(shù)據(jù)按設定時間段進行分片，將分片數(shù)據(jù)映射至協(xié)方差特征空間，對映射后數(shù)據(jù)進行基于密度的聚類分析處理，獲得了日常數(shù)據(jù)分類模板。

實驗結果表明，利用聚類分析的方法獲得了關于傳感器網(wǎng)絡時間序列數(shù)據(jù)的事件分類，能更準確地對異常事件進行篩選，有效完善了7×24 h的事件分類模板，對于智能環(huán)境的事件分析處理具有實際參考價值。

參考文獻：

[1]GHAYVAT H, MUKHOPADHYAY S C, GUI X.Intelligent Environmental Sensing[M].Berlin：Springer International Publishing, 2015:1-31.

[2]HAGRAS H, ALGHAZZAWI D, ALDABBAGH G. Employing Type-2 Fuzzy Logic Systems in the Efforts to Realize Ambient Intelligent Environments(Application Notes)[J].IEEE Computational Intelligence Magazine, 2015, 10(1):44-51.

[3]田會峰, 袁明新. 基于無線傳感網(wǎng)的智能環(huán)境監(jiān)控系統(tǒng)設計[J].測控技術, 2014, 33(9):36-39.

TIAN Huifeng,YUAN Mingxin. Design of Intelligent Environment Monitoring System Based on Wireless Sensor Network[J].Measurement & Control Technology,2014, 33(9):36-39.

[4]劉練, 周鳳星. 基于APP的智能家居環(huán)境監(jiān)測系統(tǒng)的設計與實現(xiàn)[J]. 計算機測量與控制, 2014, 22(7):2018-2023.

LIU Lian, ZHOU Fengxing. Design and Implementation of Environment Monitoring System at Smart Home Based on APP[J].Computer Measurement & Control,2014,22(7):2018-2023.

[5]YE Li, QIN Zhiguang, WANG Juan,et al.Anomaly Event Detection in Temporal Sensor Network Data of Intelligent Environments[C]//IEEE.2nd International Conference on Computer Engineering and Technology(ICCET).New York:IEEE，2010, 7:414-420.

[6]JIN S Y, YEUNG D S, WANG X Z.Network intrusion detection in covariance feature space[J].Pattern Recognition，2007，40 (8) ：2185-2197.

[7]王邦軍, 李凡長, 張莉,等. 基于改進協(xié)方差特征的李-KNN分類算法[J]. 模式識別與人工智能, 2014(2):173-178.

WANG Bangjun, LI Fanzhang, ZHANG Li, et al. Improved Covariance Feature Based Lie-KNN Classification Algorithm[J].Pattern Recognition and Artificial Intelligence, 2014(2):173-178.

[8]ERTOZ L, MICHAEL S, KUMAR V. Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data[C]∥Proceedings of the third SIAM International Conference on Data Mining (SIAM 2003). San Francisco, CA: SIAM，2003: 47-58

[9]李霞, 蔣盛益, 張倩生, 等. 適用于大規(guī)模文本處理的動態(tài)密度聚類算法[J]. 北京大學學報：自然科學版, 2013, 49(1):133-139.

LI Xia, JIANG Shengyi, ZHANG Qiansheng,et al. A Dynamic Density-Based Clustering Algorithm Appropriate to Large-Scale Text Processing[J].Acta Scientiarum Naturalium Universitatis Pekinensis：Natural Science Edition, 2013, 49(1):133-139.

[10] 萬靜, 張義, 何云斌，等.基于KD-樹和K-means動態(tài)聚類方法研究[J].計算機應用研究,2015, 32(12):3590-3595.

WAN Jing, ZHANG Yi,HE Yunbin,et al.Dynamic clustering algorithm based on KD-tree and K-means method[J].Application Research of Computers,2015, 32(12):3590-3595.

[11] MENARDI G. A Review on Modal Clustering[J]. International Statistical Review, 2015(6):1-12.

Research of time series data events classification in sensor networks

YE Li

(Southwest China Institute of Electronic Technology, Chengdu 610036, P.R.China)

Abstract:The big data collected by sensor networks in intelligent environments are faced with the problem of pattern classification and anomaly detection of time series data events. For the efficient event classification of time series data collected by sensor networks, the clustering analysis in covariance feature space was proposed. By partitioning the time series data which were collected by sensor networks, then mapping to the covariance feature space and using density-based clustering algorithms, the classification template was built to classify the usual event. The classification template was used in anomaly detection. The experiments results show that the proposed methods can effectively classify the time series data events, and enhance the performance of anomaly detection.

Keywords：event classification; times series analysis; density-based clustering; intelligent environments

DOI：10.3979/j.issn.1673-825X.2016.03.023

收稿日期：2016-03-18

修訂日期：2016-05-05通訊作者：葉李forefell@sohu.com

基金項目：國家自然科學基金(61379159)；重慶市科委自然科學基金(cstc2014jcyjA1350)

Foundation Items：The National Natural Science Foundation of China(61379159)；The Natural Science Foundation Project of CQ CSTC (cstc2014jcyjA1350)

中圖分類號：TP3

文獻標志碼：A

文章編號：1673-825X(2016)03-0421-05

作者簡介：

葉李(1977-)，男，四川達州人，工程師，博士，主要研究方向為偵察對抗總體設計。E-mail: forefell@sohu.com。

(編輯：王敏琦)