一種面向不確定數(shù)據(jù)流的模體發(fā)現(xiàn)算法

王 菊，劉付顯，靳春杰，李禎東

?

一種面向不確定數(shù)據(jù)流的模體發(fā)現(xiàn)算法

王 菊1，劉付顯1，靳春杰2，李禎東3

(1. 空軍工程大學防空反導學院 西安 710051；2. 93527部隊 河北 張家口 075000；3. 93787部隊 北京豐臺區(qū) 100076)

借鑒生物信息學中序列模式發(fā)現(xiàn)思想，提出了基于MEME(multiple expectation-maximization for motif elicitation)的不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法。該算法根據(jù)不確定數(shù)據(jù)流的特點，設計了不確定滑動窗口的簡化計算方法，改進了SAX(symbolic aggregate approximation)的符號化策略，用防空反導情報傳感器網(wǎng)絡中的一組不確定數(shù)據(jù)流驗證了其可行性，通過植入不同數(shù)目模體的方法測試了其準確性，并在元組存在概率為1的條件下與已有算法進行比較，驗證其有效性。

MEME算法; 模體發(fā)現(xiàn); SAX; 不確定數(shù)據(jù)流; 不確定滑動窗口

隨著信息化時代的到來，通信、傳感器和計算機等技術發(fā)展迅猛，使得各類測量數(shù)據(jù)急劇膨脹，催生出一個發(fā)展廣闊且軍事意義重大的應用研究領域——數(shù)據(jù)流分析。作為一個連續(xù)到達的數(shù)據(jù)序列，與傳統(tǒng)時間序列相比，數(shù)據(jù)流具有無界性、高速性等顯著特點[1]。攜帶有不完整、不精確信息的數(shù)據(jù)流被稱為不確定數(shù)據(jù)流，它在無線傳感器網(wǎng)絡、互聯(lián)網(wǎng)、戰(zhàn)場態(tài)勢等領域有極大的應用需求[2-3]。目前，有關不確定數(shù)據(jù)流的研究主要包括聚類、查詢和分類等方面，而關于不確定數(shù)據(jù)流內隱含的關系、規(guī)則及模式等知識挖掘方面則很少提及[4-6]。

本文借鑒生物信息學中序列模式發(fā)現(xiàn)思想，研究不確定數(shù)據(jù)流中功能或行為相似的流段(模體)，用于分析或預測產(chǎn)生數(shù)據(jù)流的實體行為。為了發(fā)現(xiàn)不確定數(shù)據(jù)流在不同時刻滑動窗口下的模體，實現(xiàn)對不確定數(shù)據(jù)流的預測、規(guī)則挖掘、分類和異常檢測，設計了基于MEME的不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法，在傳統(tǒng)時間序列模體發(fā)現(xiàn)的基礎上，增加了處理不確定性和動態(tài)性的功能。

1 MEME算法

在生物信息學中，模體發(fā)現(xiàn)的近似算法主要分為兩類：一類是基于啟發(fā)式或貪心技術的算法，主要有WEEDER、VINE、Pattern Branching算法等；另一類是基于統(tǒng)計技術的算法，主要有EM、MEME、吉布斯采樣以及HMM算法等。

MEME算法[7-9]是目前最流行的符號序列集合模體發(fā)現(xiàn)算法，它可將模體從由背景成分和模體成分組成的混合符號序列中辨識出來。對于由符號序列組成的符號序列集合而言，用表示一個長度為的堿基片段，即。MEME算法就是從符號序列集合中識別出重復出現(xiàn)的。

(1)

步可以表示為：

步可以表示為：

(3)

步和步重復執(zhí)行多次直至收斂。此外，通過描述位點如何分布，MEME又將概率模型細分為OOPS、ZOOPS和TCM這3類。OOPS模型表示每條序列中有且只有一個模體出現(xiàn)，這是模體發(fā)現(xiàn)問題最基本的假設；ZOOPS模型表示每條序列中含有一個或零個模體；TCM模型允許一條序列中有零或多個模體出現(xiàn)。

2 基于MEME的不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法

基于MEME的不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法的核心是如何將具有時序性、海量性、無界性、實時性、高速性和連續(xù)性等特點的數(shù)據(jù)序列合理地轉換為符號序列集合。它的難點是如何對有效時間內的不確定數(shù)據(jù)流進行合理劃分以及對具有不確定性的數(shù)據(jù)序列進行符號化。因此，在對不確定滑動窗口技術和SAX符號化策略進行改進和擴展的基礎上，本文綜合利用這兩種思想的優(yōu)點，提出了一種適用于不確定數(shù)據(jù)流的符號化方法。利用MEME算法對符號化的不確定數(shù)據(jù)流進行模體發(fā)現(xiàn)，進而解決不確定數(shù)據(jù)流模體發(fā)現(xiàn)問題。

根據(jù)可能世界模型[10]，利用一組不確定數(shù)據(jù)流，假設各元組可以在離散域中取多個規(guī)范化值[4]，則該數(shù)據(jù)流可以被描述為：

2.1 不確定滑動窗口定義及簡化計算

考慮到不確定數(shù)據(jù)流具有無限性，要處理從數(shù)據(jù)出現(xiàn)到當前時刻的所有數(shù)據(jù)是不可能的?；诖?，文獻[11]提出了不確定滑動窗口的概念，其核心思想是根據(jù)一定的置信概率使滑動窗口中存在的元組數(shù)目為，但該方法在應用中需要進行大量的復雜概率計算。因此，本文提出了不確定滑動窗口的簡化計算方法，該方法可以大幅度減少更新滑動窗口時的計算量，提高處理速度。

2.1.1 不確定滑動窗口的定義

為了便于觀察，不確定滑動窗口的符號說明及定義如表1所示。

表1 符號說明

當新元組到來時，更新滑動窗口的計算流程如下。

Loop

End while

End if

End loop

2.1.2 不確定滑動窗口的簡化計算方法

(7)

(9)

2.2 改進的SAX符號化策略

SAX[13-14]是一種針對一元時間序列符號化的方法，可以用于聚類、分類、索引和異常檢測等。為了將該方法拓展到不確定數(shù)據(jù)流，確保每個滑動窗口中存在元組的數(shù)目差別不大，本文將SAX的符號化策略改進為以下3個步驟。

2) PAA過程，即用一小段序列的平均值代表該序列；

3)符號化，即用不同的符號表示每小段的平均值。

上述步驟中，步驟1)的目的是為了確保每個滑動窗口中存在元組的數(shù)目近似為。步驟2)是將原本的維時間序列降為維，即用一組向量表示原來的時間序列。其中，第個元素的計算公式為：

如圖1所示，采用PAA過程后，一個128維的時間序列(淺線條)可以用的8維時間序列(粗線條)進行表示。

圖1 PAA過程示例

步驟3)的目的是為了選取合適的字符集進行符號化，其關鍵是分界點的選取，文獻[14]中給出了常用的分界點值及所需字符集的數(shù)目，如表2所示。

表2 常用的分界點值及所需字符集的數(shù)目

對于圖1中所示的時間序列，當用3個字符進行表示時，該序列的符號化情況如圖2所示，符號化結果為baabccbc。

2.3 算法設計

綜合2.1節(jié)的方法和2.2節(jié)的改進策略，本節(jié)設計了基于MEME算法的不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法，該算法可以對任意一組不確定數(shù)據(jù)流進行模體發(fā)現(xiàn)，流程圖如圖3所示。

具體算法描述如下。

2) 判斷不確定數(shù)據(jù)流是否到來，是轉步驟3)，否則算法結束；

4) 不確定滑動窗口的更新及數(shù)據(jù)緩存：

LOOP

轉步驟5；

Else

continue；

End if

Else

continue；

End if

End if

End loop

綜上所述，由于采用了并行計算和不確定滑動窗口簡化計算方法，文中算法計算時間較短，運算效率高。

3 實驗與分析

3.1 實例驗證

防空反導情報傳感器網(wǎng)絡是軍事中產(chǎn)生不確定數(shù)據(jù)流的典型應用，本文對該網(wǎng)絡中產(chǎn)生的一組距離不確定數(shù)據(jù)流進行模體發(fā)現(xiàn)。

表3 部分規(guī)范化不確定數(shù)據(jù)流示例

3) 繼續(xù)采集諸如表3中的數(shù)據(jù)，根據(jù)存在概率判斷是否滿足不等式，直到，得到(具體如圖4所示，黑點表示元組存在，白點表示元組不存在)，返回初始狀態(tài)。

a.中規(guī)范化后的距離值

b.中規(guī)范化后的距離值

表4 符號化結果

表4 符號化結果

編號上述三條綜合指標序列所對應的字符串 seq1CCCCAGTGCCGGCGGCCCCCCCGGAGGCCCGGGGGGCCGGCGACAAACGG seq2TTCCCCCTGCGAAGCCGGACCTAGGCGGCCGGGTCGCGCTACTCGCGTCG seq3CGCCCGGCCGGGAGGGCGGCGCGCGGCGCCGCACCCGGCCCGGCCGCCCC

5) 根據(jù)MEME算法，采用DNA序列分析工具，對表4中的符號序列集合進行模體發(fā)現(xiàn)，其結果如圖6所示。

由圖5可知，在表3所示規(guī)范化后的距離值中，共發(fā)現(xiàn)了兩種模體，分別由兩種粗細的線條進行表示。進而根據(jù)所發(fā)現(xiàn)模體的排序及位置(如圖5中方框內所示)，可以反推出原數(shù)據(jù)中模體的位置及形狀，如圖6所示。

a.中規(guī)范化后的距離值及模體位置與形狀

b.中規(guī)范化后的距離值及模體位置與形狀

從圖6可發(fā)現(xiàn)，所發(fā)現(xiàn)模體在形狀上具有一定的相似性，滿足“模體”在時間序列中的定義，也驗證了文中算法的可行性。

3.2 實驗分析

通過3.1節(jié)的案例分析，文中算法的可行性得到驗證。為進一步分析文中算法的有效性，本節(jié)設計了兩個實驗來進行驗證。

實驗1：若對不確定數(shù)據(jù)流進行模體植入，當植入模體的數(shù)目依次為時，本文算法所發(fā)現(xiàn)模體的準確率如圖7所示。

從圖7可知，在不同的模體植入情況下，文中算法的模體發(fā)現(xiàn)準確率在0.8～0.9之間，穩(wěn)定性強，驗證了該算法的有效性。

實驗2：考慮到目前還沒有關于不確定數(shù)據(jù)流模體發(fā)現(xiàn)的相關算法，文中設定不確定數(shù)據(jù)流中元組的存在概率都為1，設置滑動窗口長度為。此時假設滑動窗口不更新，將不確定數(shù)據(jù)流轉換為確定的時間序列。在相同的3個白噪聲數(shù)據(jù)集上依次植入隨機數(shù)目的模體，得到3組實驗數(shù)據(jù)集，將文中算法與文獻[15-16]提出的MK和MOEN算法進行比較，其模體發(fā)現(xiàn)準確率結果如表5所示。

表5 算法準確率比較

從表5可知，文中算法的模體發(fā)現(xiàn)準確率高于MK和MOEN算法，進一步驗證了該算法的有效性。

4 結束語

本文在傳統(tǒng)時間序列模體發(fā)現(xiàn)的基礎上加入了不確定性和動態(tài)性，建立起了序列數(shù)據(jù)挖掘和不確定數(shù)據(jù)流挖掘之間的橋梁，并采用生物信息學算法完成了對不確定數(shù)據(jù)流的模體發(fā)現(xiàn)。

1) 提出了基于MEME的不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法，根據(jù)防空反導傳感器網(wǎng)絡對距離的實時測量數(shù)據(jù)進行模體發(fā)現(xiàn)，驗證了其可行性；

2) 通過多次模體植入實驗和算法性能對比實驗，驗證了本文算法的有效性。仿真分析表明，在同等仿真條件下，本文算法優(yōu)于MK和MOEN算法；

3) 該文部分內容屬于探索性的研究，相關理論和研究可以對不確定數(shù)據(jù)流的模體發(fā)現(xiàn)提供理論和應用支撐；

4) 本文所建立的不確定數(shù)據(jù)流是基于離散屬性值，對具有連續(xù)屬性的不確定數(shù)據(jù)流進行模體發(fā)現(xiàn)是本文下一步的研究內容。

[1] 梁春泉. 不確定數(shù)據(jù)流分類算法研究[D]. 西安: 西北農林科技大學, 2014.

LIANG Chun-quan. Classification algorithm based on uncertain data stream[D]. Xi'an: Northwest Agriculture and Forestry University, 2014.

[2] THANH T L T, PENG L P, DIAO Y L, et al. CLARO: Modeling and processing uncertain data streams[J]. VLDB Journal, 2012, 21: 651-676.

[3] JIN C Q, JEFFREY X Y, ZHOU A Y, et al. Efficient clustering of uncertain data streams[J]. Knowl Inf Syst, 2014, 40: 509-539.

[4] 朱躍龍, 彭力, 李士進, 等. 水文時間序列模體挖掘[J]. 水利學報, 2012, 43(12): 1422-1430.

ZHU Yue-long, PENG Li, LI Shi-jin, et al. Research on hydrological time series mining[J]. Hydraulic Engineering, 2012, 43(12): 1422-1430.

[5] PUNEET A, GAUTAM S, SARMIMALA S, et al. Efficiently discovering frequent motifs in large-scale sensor data[EB/OL]. [2015-06-30]. https://www.researchgate.net/ publication/270454309_Efficiently_Discovering_Frequent_Motifs_in_Large-scale_Sensor_Data.

[6] 鄒力鹍, 張其善. 基于多最小支持度的加權關聯(lián)規(guī)則挖掘算法[J]. 北京航空航天大學學報, 2007, 33(5): 590-593.

ZOU Li-pu, ZHANG Qi-shan. Algorithm of weighted association rules mining with multiple minimum supports [J]. Beijing University of Aeronautics and Astronautics Technology, 2007, 33(5): 590-593.

[7] 張懿璞, 霍紅衛(wèi), 于強, 等. 用于轉錄因子結合位點識別的定位投影求精算法[J]. 計算機學報, 2013, 36(12): 2545-2559.

ZHANG Yi-pu, HUO Hong-wei, YU Qiang, et al. A novel fixed- position projection refinement algorithm for TFBS Identification[J]. Journal of Computers, 2013, 36 (12): 2545-2559.

[8] TIMOTHY L B. Dreme: Motif discovery in transcription factor ChIP-seq data[J]. Original Paper, 2011, 17(12): 1653-1659.

[9] DANIEL Q, XIE X H. Extreme: an online EM algorithm for motif discovery[J]. Original Paper, 2014, 30(12): 1667-1673.

[10] 李明, 張維明. 不確定數(shù)據(jù)流多維建模方法[J]. 國防科技大學學報, 2014, 36(5): 174-179.

LI Ming, ZHANG Wei-ming. Multi-dimensional modeling method of uncertain data stream[J]. Journal of the National Defense University, 2014, 36 (5): 174-179.

[11] MICHELE D. Modeling and querying data series and data streams with uncertainty[D]. The Autonomous Province of Trento: Universita` degli Studi di Trento, 2014,

[12] HONG Y. On computing the distribution function for the sum of independent and non-identical random indicators[EB/OL]. [2015-10-10]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.8708.

[13] 曲文龍, 張克君, 楊炳儒, 等. 基于奇異事件特征聚類的時間序列符號化方法[J]. 系統(tǒng)工程與電子技術, 2006, 28(8): 1131-1134.

QU Wen-long, ZHANG Ke-jun, YANG Bing-ru, et al. Time series symbolization based on singular event feature clustering[J]. Systems Engineering and Electronics, 2006, 28 (8): 1131-1134.

[14] LIN J, KENOGH E J, WEI D L, et al. Experiencing SAX: a novel symbolic representation of time series[J]. Data Min Knowl Disc, 2007, 15: 107-144.

[15] MUEEN A, KEOGH E J, ZHU Q, et al. Exact discovery of time series motif[C]//Society for Industrial and Applied Mathematics Conf. on Data Mining. [S.l.]: Springer, 2009.

[16] ABDULLAH M, NIKAN C. Enumeration of time series motifs of all lengths[J]. Knowl Inf Syst, 2015, 45: 105-132.

編 輯 葉 芳

New Motif Discovery Algorithm for Uncertain Data Stream

WANG Ju1, LIU Fu-xian1, JIN Chun-jie2, and LI Zhen-dong3

(1. Air and Missile Defense College, Air Force Engineering University Xi’an 710051; 2. 93527 Military Unit Zhangjiakou Heibei 075000; 3. 93787 Military Unit Fengtai Beijing 100076)

A new MEME-based motif discovery algorithm for uncertain data stream is proposed by using the idea of sequential pattern discovery in bioinformatics. According to features of uncertain data stream, the new algorithm designs a simplified calculation method for uncertain sliding window and modifies the SAX symbolic strategy. The feasibility of the proposed algorithm is verified by one uncertain test data stream from air and missile defense sensors. And its accuracy is measured through planting different number motifs. Furthermore, the proposed algorithm is validated by comparing with existing algorithms in the condition that the existence probability of tuples is set to 1.

MEME algorithm; motif discovery; SAX; uncertain data stream; uncertain sliding window;

TP391

A

10.3969/j.issn.1001-0548.2017.01.013

2015-12-23；

2016-06-01

國家自然科學基金(61272011)

王菊(1991-)，女，博士生，主要從事數(shù)據(jù)挖掘方面的研究.