王 菊，刘付显，靳春杰，李祯东



一种面向不确定数据流的模体发现算法

王 菊1，刘付显1，靳春杰2，李祯东3

(1. 空军工程大学防空反导学院 西安 710051；2. 93527部队 河北 张家口 075000；3. 93787部队 北京丰台区 100076)

借鉴生物信息学中序列模式发现思想，提出了基于MEME(multiple expectation-maximization for motif elicitation)的不确定数据流模体发现算法。该算法根据不确定数据流的特点，设计了不确定滑动窗口的简化计算方法，改进了SAX(symbolic aggregate approximation)的符号化策略，用防空反导情报传感器网络中的一组不确定数据流验证了其可行性，通过植入不同数目模体的方法测试了其准确性，并在元组存在概率为1的条件下与已有算法进行比较，验证其有效性。

MEME算法; 模体发现; SAX; 不确定数据流; 不确定滑动窗口

随着信息化时代的到来，通信、传感器和计算机等技术发展迅猛，使得各类测量数据急剧膨胀，催生出一个发展广阔且军事意义重大的应用研究领域——数据流分析。作为一个连续到达的数据序列，与传统时间序列相比，数据流具有无界性、高速性等显著特点[1]。携带有不完整、不精确信息的数据流被称为不确定数据流，它在无线传感器网络、互联网、战场态势等领域有极大的应用需求[2-3]。目前，有关不确定数据流的研究主要包括聚类、查询和分类等方面，而关于不确定数据流内隐含的关系、规则及模式等知识挖掘方面则很少提及[4-6]。

本文借鉴生物信息学中序列模式发现思想，研究不确定数据流中功能或行为相似的流段(模体)，用于分析或预测产生数据流的实体行为。为了发现不确定数据流在不同时刻滑动窗口下的模体，实现对不确定数据流的预测、规则挖掘、分类和异常检测，设计了基于MEME的不确定数据流模体发现算法，在传统时间序列模体发现的基础上，增加了处理不确定性和动态性的功能。

1 MEME算法

在生物信息学中，模体发现的近似算法主要分为两类：一类是基于启发式或贪心技术的算法，主要有WEEDER、VINE、Pattern Branching算法等；另一类是基于统计技术的算法，主要有EM、MEME、吉布斯采样以及HMM算法等。

MEME算法[7-9]是目前最流行的符号序列集合模体发现算法，它可将模体从由背景成分和模体成分组成的混合符号序列中辨识出来。对于由符号序列组成的符号序列集合而言，用表示一个长度为的碱基片段，即。MEME算法就是从符号序列集合中识别出重复出现的。

(1)

步可以表示为：

步可以表示为：

(3)

步和步重复执行多次直至收敛。此外，通过描述位点如何分布，MEME又将概率模型细分为OOPS、ZOOPS和TCM这3类。OOPS模型表示每条序列中有且只有一个模体出现，这是模体发现问题最基本的假设；ZOOPS模型表示每条序列中含有一个或零个模体；TCM模型允许一条序列中有零或多个模体出现。

2 基于MEME的不确定数据流模体发现算法

基于MEME的不确定数据流模体发现算法的核心是如何将具有时序性、海量性、无界性、实时性、高速性和连续性等特点的数据序列合理地转换为符号序列集合。它的难点是如何对有效时间内的不确定数据流进行合理划分以及对具有不确定性的数据序列进行符号化。因此，在对不确定滑动窗口技术和SAX符号化策略进行改进和扩展的基础上，本文综合利用这两种思想的优点，提出了一种适用于不确定数据流的符号化方法。利用MEME算法对符号化的不确定数据流进行模体发现，进而解决不确定数据流模体发现问题。

根据可能世界模型[10]，利用一组不确定数据流，假设各元组可以在离散域中取多个规范化值[4]，则该数据流可以被描述为：

2.1 不确定滑动窗口定义及简化计算

考虑到不确定数据流具有无限性，要处理从数据出现到当前时刻的所有数据是不可能的。基于此，文献[11]提出了不确定滑动窗口的概念，其核心思想是根据一定的置信概率使滑动窗口中存在的元组数目为，但该方法在应用中需要进行大量的复杂概率计算。因此，本文提出了不确定滑动窗口的简化计算方法，该方法可以大幅度减少更新滑动窗口时的计算量，提高处理速度。

2.1.1 不确定滑动窗口的定义

为了便于观察，不确定滑动窗口的符号说明及定义如表1所示。

表1 符号说明

当新元组到来时，更新滑动窗口的计算流程如下。

Loop

End while

End if

End loop

2.1.2 不确定滑动窗口的简化计算方法

(7)

(9)

2.2 改进的SAX符号化策略

SAX[13-14]是一种针对一元时间序列符号化的方法，可以用于聚类、分类、索引和异常检测等。为了将该方法拓展到不确定数据流，确保每个滑动窗口中存在元组的数目差别不大，本文将SAX的符号化策略改进为以下3个步骤。

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

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

上述步骤中，步骤1)的目的是为了确保每个滑动窗口中存在元组的数目近似为。步骤2)是将原本的维时间序列降为维，即用一组向量表示原来的时间序列。其中，第个元素的计算公式为：

如图1所示，采用PAA过程后，一个128维的时间序列(浅线条)可以用的8维时间序列(粗线条)进行表示。

图1 PAA过程示例

步骤3)的目的是为了选取合适的字符集进行符号化，其关键是分界点的选取，文献[14]中给出了常用的分界点值及所需字符集的数目，如表2所示。

表2 常用的分界点值及所需字符集的数目

对于图1中所示的时间序列，当用3个字符进行表示时，该序列的符号化情况如图2所示，符号化结果为baabccbc。

2.3 算法设计

综合2.1节的方法和2.2节的改进策略，本节设计了基于MEME算法的不确定数据流模体发现算法，该算法可以对任意一组不确定数据流进行模体发现，流程图如图3所示。

具体算法描述如下。

2) 判断不确定数据流是否到来，是转步骤3)，否则算法结束；

4) 不确定滑动窗口的更新及数据缓存：

LOOP

转步骤5；

Else

continue；

End if

Else

continue；

End if

End if

End loop

综上所述，由于采用了并行计算和不确定滑动窗口简化计算方法，文中算法计算时间较短，运算效率高。

3 实验与分析

3.1 实例验证

防空反导情报传感器网络是军事中产生不确定数据流的典型应用，本文对该网络中产生的一组距离不确定数据流进行模体发现。

表3 部分规范化不确定数据流示例

3) 继续采集诸如表3中的数据，根据存在概率判断是否满足不等式，直到，得到(具体如图4所示，黑点表示元组存在，白点表示元组不存在)，返回初始状态。

a.中规范化后的距离值

b.中规范化后的距离值

表4 符号化结果

表4 符号化结果

编号上述三条综合指标序列所对应的字符串 seq1CCCCAGTGCCGGCGGCCCCCCCGGAGGCCCGGGGGGCCGGCGACAAACGG seq2TTCCCCCTGCGAAGCCGGACCTAGGCGGCCGGGTCGCGCTACTCGCGTCG seq3CGCCCGGCCGGGAGGGCGGCGCGCGGCGCCGCACCCGGCCCGGCCGCCCC

5) 根据MEME算法，采用DNA序列分析工具，对表4中的符号序列集合进行模体发现，其结果如图6所示。

由图5可知，在表3所示规范化后的距离值中，共发现了两种模体，分别由两种粗细的线条进行表示。进而根据所发现模体的排序及位置(如图5中方框内所示)，可以反推出原数据中模体的位置及形状，如图6所示。

a.中规范化后的距离值及模体位置与形状

b.中规范化后的距离值及模体位置与形状

从图6可发现，所发现模体在形状上具有一定的相似性，满足“模体”在时间序列中的定义，也验证了文中算法的可行性。

3.2 实验分析

通过3.1节的案例分析，文中算法的可行性得到验证。为进一步分析文中算法的有效性，本节设计了两个实验来进行验证。

实验1：若对不确定数据流进行模体植入，当植入模体的数目依次为时，本文算法所发现模体的准确率如图7所示。

从图7可知，在不同的模体植入情况下，文中算法的模体发现准确率在0.8～0.9之间，稳定性强，验证了该算法的有效性。

实验2：考虑到目前还没有关于不确定数据流模体发现的相关算法，文中设定不确定数据流中元组的存在概率都为1，设置滑动窗口长度为。此时假设滑动窗口不更新，将不确定数据流转换为确定的时间序列。在相同的3个白噪声数据集上依次植入随机数目的模体，得到3组实验数据集，将文中算法与文献[15-16]提出的MK和MOEN算法进行比较，其模体发现准确率结果如表5所示。

表5 算法准确率比较

从表5可知，文中算法的模体发现准确率高于MK和MOEN算法，进一步验证了该算法的有效性。

4 结束语

本文在传统时间序列模体发现的基础上加入了不确定性和动态性，建立起了序列数据挖掘和不确定数据流挖掘之间的桥梁，并采用生物信息学算法完成了对不确定数据流的模体发现。

1) 提出了基于MEME的不确定数据流模体发现算法，根据防空反导传感器网络对距离的实时测量数据进行模体发现，验证了其可行性；

2) 通过多次模体植入实验和算法性能对比实验，验证了本文算法的有效性。仿真分析表明，在同等仿真条件下，本文算法优于MK和MOEN算法；

3) 该文部分内容属于探索性的研究，相关理论和研究可以对不确定数据流的模体发现提供理论和应用支撑；

4) 本文所建立的不确定数据流是基于离散属性值，对具有连续属性的不确定数据流进行模体发现是本文下一步的研究内容。

[1] 梁春泉. 不确定数据流分类算法研究[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] 邹力鹍, 张其善. 基于多最小支持度的加权关联规则挖掘算法[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] 张懿璞, 霍红卫, 于强, 等. 用于转录因子结合位点识别的定位投影求精算法[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] 李明, 张维明. 不确定数据流多维建模方法[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]. 系统工程与电子技术, 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-)，女，博士生，主要从事数据挖掘方面的研究.