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

?

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

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

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

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

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

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

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

1 MEME算法

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

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

(1)

步可以表示為：

步可以表示為：

(3)

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

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

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

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

2.1 不確定滑動窗口定義及簡化計(jì)算

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

2.1.1 不確定滑動窗口的定義

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

表1 符號說明

當(dāng)新元組到來時(shí)，更新滑動窗口的計(jì)算流程如下。

Loop

End while

End if

End loop

2.1.2 不確定滑動窗口的簡化計(jì)算方法

(7)

(9)

2.2 改進(jìn)的SAX符號化策略

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

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

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

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

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

圖1 PAA過程示例

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

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

對于圖1中所示的時(shí)間序列，當(dāng)用3個(gè)字符進(jìn)行表示時(shí)，該序列的符號化情況如圖2所示，符號化結(jié)果為baabccbc。

2.3 算法設(shè)計(jì)

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

具體算法描述如下。

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

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

LOOP

轉(zhuǎn)步驟5；

Else

continue；

End if

Else

continue；

End if

End if

End loop

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)例驗(yàn)證

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

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

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

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

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

表4 符號化結(jié)果

表4 符號化結(jié)果

編號上述三條綜合指標(biāo)序列所對應(yīng)的字符串 seq1CCCCAGTGCCGGCGGCCCCCCCGGAGGCCCGGGGGGCCGGCGACAAACGG seq2TTCCCCCTGCGAAGCCGGACCTAGGCGGCCGGGTCGCGCTACTCGCGTCG seq3CGCCCGGCCGGGAGGGCGGCGCGCGGCGCCGCACCCGGCCCGGCCGCCCC

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

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

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

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

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

3.2 實(shí)驗(yàn)分析

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

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

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

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

表5 算法準(zhǔn)確率比較

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

4 結(jié)束語

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

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

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

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

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

[1] 梁春泉. 不確定數(shù)據(jù)流分類算法研究[D]. 西安: 西北農(nóng)林科技大學(xué), 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ìn), 等. 水文時(shí)間序列模體挖掘[J]. 水利學(xué)報(bào), 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] 鄒力鹍, 張其善. 基于多最小支持度的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法[J]. 北京航空航天大學(xué)學(xué)報(bào), 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), 于強(qiáng), 等. 用于轉(zhuǎn)錄因子結(jié)合位點(diǎn)識別的定位投影求精算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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]. 國防科技大學(xué)學(xué)報(bào), 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] 曲文龍, 張克君, 楊炳儒, 等. 基于奇異事件特征聚類的時(shí)間序列符號化方法[J]. 系統(tǒng)工程與電子技術(shù), 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

國家自然科學(xué)基金(61272011)

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