王 菊 刘付显



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

王 菊*刘付显

(空军工程大学防空反导学院 西安 710051)

该文针对多属性不确定数据流的频繁模式发现问题，借鉴生物信息学中的模体发现思想，提出了一种基于MEME(Multiple Expectation-maximization for Motif Elicitation)的多属性不确定数据流模体发现算法。该算法根据不确定数据流的特点，设计了基于混合型模型的不确定滑动窗口更新计算方法，改进了SAX(Symbolic Aggregate approXimation)的符号化策略，提出了不同滑动窗口下多属性模体的相似性分析方法。在实验当中，用防空反导情报传感器网络中的一组不确定数据流验证了其功能，通过植入不同数目的模体测试了其发现准确率，并在元组有效概率设置为1的条件下与已有算法进行了比较，结果表明：该算法可以较准确地发现多属性不确定数据流中的频繁模式。

数据挖掘；模体发现；不确定数据流；MEME(Multiple Expectation-maximization for Motif Elicitation)算法

1 引言

多属性不确定数据流的频繁模式发现问题可以归结为数据挖掘领域中的关联规则挖掘问题，其实质是发现动态多属性数据中重复出现的相似模式。作为关联规则挖掘中的关键问题，多属性不确定数据流中频繁模式的发现准确率会受到其动态性、不确定性以及属性之间关联性的影响，已成为数据挖掘领域中的一个研究热点和难点。

针对不确定数据流的频繁模式挖掘，Leung等人[4]提出了SUF-growth(mine Frequent itemsets from Streams on Uncertain data)算法，基于该算法的框架，出现了较多的改进算法，如基于滑动窗口的MFCIFUDS算法[5]、基于Hyper-structure的UHS- stream(Uncertain Hyper-Structure stream mining)算法[6]、基于衰减窗口的TUF-streaming(use the Time-fading model in an Uncertain data environment to mine Frequent patterns from streaming data)算法和基于界标窗口的XTUF- streaming(eXtended TUF-streaming)算法[7]等，但这些算法只适应于单属性的不确定数据流。在实际数据流的产生过程中，不仅数据是动态的，且可能会有多个属性同时到达，而关于如何挖掘这类多属性不确定数据流的研究还相对较少。

模体发现属于数据挖掘中的序列模式发现[8]，来源于生物信息学当中，也称为转录因子结合位点识别，用于寻找在序列当中具有功能和排列相似的短核苷酸片段[9]，主要算法有随机投影(Random Projection), EM(Expectation Maximization), MEME和Voting等[10]。借鉴生物信息学中模体发现的思想，Lin等人[11]在2002年首次提出了时间序列模体发现的概念，其他专家学者又相继提出了一种线性时间下的随机投影方法[12]、致密球[13]、MK算法[14]和MOEN算法[15]等。

本文把该思路做了进一步的拓展，将模体发现的概念应用于多属性不确定数据流的频繁模式发现中，提出了一种基于MEME的多属性不确定数据流模体发现算法，在传统时间序列模体发现的基础上，增加了处理不确定性、动态性和多属性模体相似性分析等功能。该算法设计了基于混合型模型的不确定滑动窗口更新计算方法，改进了SAX的符号化策略，提出了不同滑动窗口下多属性模体的相似性分析方法，能够较准确地发现多属性不确定数据流中的频繁模式。

2 MEME算法

文献[16]和文献[18]中详细介绍了MEME算法，其核心是定义了一个二元随机变量，通过计算每一个(表示一个长度为的碱基片段)的似然值来寻找模体。其中，表示每一个对应的背景成分或模体成分，即当字符表示为一个结合位点时，，否则。该算法将整个序列集合的似然值表示为

E步的具体表达式为

M步的具体表达式为

(3)

E步和M步重复执行，直至收敛。

3 基于MEME的多属性不确定数据流模体发现算法

3.1 算法设计思路

基于MEME的多属性不确定数据流模体发现的核心有两点：一是如何将具有时序性、海量性、无界性、实时性、高速性和连续性等特点的数据序列合理地转换为符号序列集合；二是如何从不同属性的模体中发现潜在的规律。

基于此，本文采用混合型模型对不确定数据流进行表示，利用滑动窗口对有效时间内的不确定数据流进行划分，对满足一定条件的数据进行符号化，执行MEME算法进行模体发现，最后再对不同滑动窗口下多属性模体的相似性进行分析，其思路如图1所示。

图1 算法设计思路

3.2多属性不确定数据流表示

采用混合型模型可以对多属性不确定数据流进行表示，本文又进一步地定义了元组有效概率，可以简化用混合型模型所表示的多属性不确定数据流，达到数据校验和快速计算的目的。

3.2.1混合型模型 文献[19]中所提出的混合型模型(mixed-type model)综合考虑了存在级不确定性和属性级不确定性，不仅能处理离散型属性，还可以处理连续型属性，是一种较为通用的不确定数据流模型，其定义如下。

定义1[19]混合型模型 给定一个元组，将其个连续不确定属性用表示，个离散不确定属性用表示，其余确定属性用表示，混合模型的分布用表示。其中，是元组的存在概率(Tuple Existence Probability, TEP),是所有不确定属性的联合概率密度函数，定义为。因此，可以用一个定义在(代表该元组不存在的情形)上的随机向量表示，即

3.2.2元组有效概率 基于混合型模型，本文定义了元组的有效概率，该概率不仅能够综合属性出现概率和元组存在概率的影响，起到数据校验的效果，还能简化多属性不确定数据流的表示形式，提高计算效率。

3.3基于混合型模型的不确定滑动窗口

多属性不确定数据流具有无限性，因此要处理从数据出现直至当前时刻的所有数据是不可能的。针对这个问题，本文设计了一种基于混合型模型的不确定滑动窗口更新计算方法，保证滑动窗口中有效元组的数目依置信概率为个。通常情况下，有效元组数目由所处理不确定数据流的稀疏程度以及计算机的处理能力决定，置信概率由所处理不确定数据流的用途和用户的偏好决定。

3.3.1不确定滑动窗口的定义及更新 在一个不确定数据流中，表示滑动窗口的大小，表示该窗口中有效元组的数目，不确定滑动窗口的定义和更新过程如下。

定义3[21]不确定滑动窗口 由于滑动窗口的实际长度具有不确定性，因此该窗口被定义为不确定滑动窗口，其满足

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

表1不确定滑动窗口更新过程

输入： 输出： 被赋予空集 Loop If (中的新元组到达) then ←∪ While do ← (是窗口中最早的元素) End while End if End loop

3.3.2基于混合型模型的不确定滑动窗口更新计算

根据定义2和定义3，本文结合滑动窗口的更新过程和于混合型模型，对约束条件进行了变形和简化。

(9)

3.4改进的SAX符号化策略

SAX[23,24]是一种针对一元时间序列符号化的方法，可以用于聚类、分类、索引和异常检测等。为了将该方法应用于不确定数据流，确保每个滑动窗口中存在的元组数目差别不大，使每一种属性(包括连续属性和离散属性)都能用SAX进行符号化，本文将SAX的符号化策略改进为以下4个步骤：

步骤3 PAA(Piecewise Aggregate Approxi- mation)过程，即用一小段序列的平均值代表该序列；

步骤4 符号化，即用不同的符号表示每小段的平均值。

图2 不同滑动窗口下多属性模体示意图

3.5 不同滑动窗口下多属性模体的相似性分析

为了发现具有相似性的多属性模体，本文提出了一种不同滑动窗口下多属性模体(如图2所示)的相似性分析方法，该方法可以为具有多属性的不确定数据流预测、分类、异常检测和规则挖掘等提供依据，其具体处理流程如下。

步骤1 列出窗口中不同属性间所有模体的组合，如图2中的窗口1，其所有模体的组合为和；

步骤2 采用Hamming距离对所有的模体组合进行相似性匹配，记录满足阈值条件的模体组合(阈值根据实际需要进行设定，本文中设定为2)，图2中得到的模体组合为；

步骤3 计算每一个满足阈值条件模体组合所对应的若干个多属性模体间的相对时间向量。将第1个模体的起始点设置为0，向量中的值表示模体起始点相对于0点的时间，图2中模体组合所对应的两个多属性模体的相对时间向量都为；

步骤4 计算每一个满足阈值条件模体组合所对应的若干个多属性模体中任意两个相对时间向量之间的欧氏距离。当该距离小于给定(根据实际的精度要求进行设定，本文中设定为0.01)时，其相应的多属性模体具有相似性，输出并记录该多属性模体。

3.6 算法设计

根据以上的分析，文中提出了一种基于MEME的多属性不确定数据流模体发现算法，该算法可以对任意一组多属性不确定数据流进行模体发现，其总体描述如表2所示。表中，步骤4和步骤5至步骤8可以同时运算，步骤3-步骤8的具体实现方法已在前文中进行过介绍。

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

输入：//为最多可同时处理的滑动窗口数目，为属性个数。 输出：具有相似性的多属性模体。 步骤1 初始化参数，设置变量； 步骤2 判断不确定数据流是否到来，是转步骤3，否则算法结束； 步骤3 对建模、规范化及有效概率计算，得到 步骤4 Loop If (中的新元组到达) then ←∪； If then ； 被赋予空集； ； If then ； 另存为，转步骤5； Else Continue; End if Else Continue; End if End if 步骤5 对序列集进行符号化，得到　个的字符矩阵； 步骤6 对字符矩阵同一行中的字符串执行MEME算法，存储并输出所发现的模体 步骤7 释放所占用的存储空间； 步骤8 对不同滑动窗口下所发现的多属性模体进行相似性分析，存储具有相似性的多属性模体。 End loop

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

时间飞机速度发动机温度距离存在概率有效概率 t1(0.84,0.8)([-0.3,1.2],)0.90.362 t2(2.43,0.7)([-1.2,0.3],)0.80.282 t3(-0.35,0.8)([-2.2,0.9],)0.90.577 t4(1.38,0.9)([-2.1,0.3],)0.60.324 t5(-0.86,0.8)([0.7,1.8],)0.70.115 t6(0.21,0.9)([-0.4,0.6],)0.90.309 t7(-21,0)([0.8,1.9],)0.90 t8(0.34,0.8)([0.1,1.4],)0.80.243 t9(-0.49,0.8)([-0.2,0.9],)00

4 实验与分析

4.1 案例分析

防空反导情报传感器网络是产生不确定数据流的典型应用，本文根据该网络对飞机速度和发动机温度的实时测量数据进行模体发现。其实验平台是装有64位Windows7操作系统的个人电脑，具有Core i5-4590的双核处理器和4GB内存，可运行Matlab和MEME程序包。

(1)针对本文中所处理的不确定数据流，可设置窗口中有效元组数目，置信概率,,,。

(2)判断不确定数据流是否实时到来，若数据流中断，则算法终止，否则转下一步继续执行计算。

(4)继续采集诸如表3中的数据，根据元组的有效概率来判断是否满足，当，得到后，设置，不断重复步骤3。

表4的符号化结果

速度属性seq1TGCATTGCTCACGCCCGCGACGCGCAGGCCGCGTCGGAACACGCCCTGCG seq2CGAGGGCGACTAGGGGGAACGCCGACGGGGGGCGCCGCGGTCCGAGGGGC seq3GGCTGGTACCACGGGCTGGCGGCGGTACCGTTGGGGCCCGTGGAGAAGGG 温度属性seq1GGGTGGCCTGAGGTTCGGGCCCCCCCGGCAGACCCGCGGCAGCCACGACC seq2GACGCATTCGCGCCTCCGGCGCCTGGACAAGACCCGGCTGCAGGCGCTAC seq3CCGATCGGCCCGGCCGCCGGACGGGCCGCGCTCGATCCTTCACCGGACAA

(6)根据MEME算法，采用MEME程序包，对表4中的符号序列集合进行模体发现，其结果如图3所示。

由图3可知，在表4的两种属性中，共发现了4种模体。进而根据所发现模体的排序及位置(如图3中方框内所示)，可以反推出原数据中模体的位置及形状，如图4所示。

从图4可发现，所发现模体在形状上具有一定的相似性，满足“模体”在时间序列中的定义，证明文中所提出的算法具有发现多属性不确定数据流中频繁模式的功能。

(8)根据图3和图4，可得到如图5所示的示意图。

图3 模体发现结果

图4 模体在原数据中的位置及形状

图5 不同滑动窗口下所发现模体的示意图

4.2 实验分析

通过4.1节的案例，验证了文中算法的功能。为进一步分析该算法的性能，本节设计了两个实验，分别用于测试其模体发现准确率和将其与已有算法进行比较。

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

从图6可知，在植入不同数目模体的情况下，本文算法的模体发现准确率在0.8~0.9之间，稳定性强。

实验2 考虑到目前还没有关于多属性不确定数据流模体发现的相关算法，因此文中需要设定不确定数据流中所有属性的出现概率和元组存在概率都为1。进而通过设置滑动窗口长度，属性个数，滑动窗口不更新，将文中算法与Mueen 提出的MK[14]和MOEN[15]算法在随机植入模体的3组白噪声数据集上进行比较，其模体发现准确率结果如图7所示。

从图7可知，文中算法的模体发现准确率高于MK和MOEN算法。

5 结束语

本文在传统时间序列模体发现的基础上引入了不确定性和动态性，建立了序列数据挖掘和不确定数据流挖掘之间的桥梁，并采用生物信息学算法完成了不确定数据流的模体发现。主要工作有：(1)提出了基于MEME的多属性不确定数据流模体发现算法，根据防空反导传感器网络对飞机速度和发动机温度的实时测量数据进行了模体发现，验证了其功能；(2)通过多次模体植入实验和算法性能对比实验，在同等仿真条件下，相比于MK和MOEN算法，验证了其优越性。文中部分内容属于探索性的研究，不确定性理论、智能搜索算法与不确定数据流模体发现的结合将是本文下一步的研究内容。

图6 本文算法所发现模体的准确率 图7 算法准确率比较

[1] LEUNG C K S, JIANG F, and HAYDUK Y. A landmark-model based system for mining frequent patterns from uncertain data streams[C]. 2011 International Database Engineering and Applications Symposium, Lisbon, Portugal, 2011:249-250. doi: 10.1145/2076623.2076659.

[2] CHUI C K and KAO B. A decremental approach for mining frequent itemsets from uncertain data[C]. 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Osaka, Japan, 2008:64-75. doi: 10.1007/978-3-540-68125.

[3] LEUNG C K S, HAO B, and BRAJCZUK D A. Mining uncertain data for frequent itemsets that satisfy aggregate constraints[C]. 25th Annual ACM Symposium on Applied Computing, Sierre, Switzerland, 2010:1034-1038. doi: 10.1145/1774088.1774305.

[4] LEUNG C K S and HAO B. Mining of frequent items from streams of uncertain data[C]. 25th IEEE International Conference on Data Engineering, Piscataway, NJ, USA, 2009: 1663-1670. doi: 10.1109/ICDE.2009.157.

[5] 汤克明. 不确定数据流中频繁数据挖掘[D]. [博士论文], 南京航空航天大学, 2012.

TANG Keming. Study on frequent data mining from uncertain data streams[D]. [Ph.D. dissertation], Nanjing University of Aeronautics and Astronautics, 2012.

[6] HEWANADUNGODAGE C, YUNI X, and LEE J J. Hyper-structure mining of frequent patterns in uncertain data streams[J]., 2013, 37:219-244. doi: 10.1007/s10115-012-0581-y.

[7] LEUNG C K S, CUZZOCREA A, FAN J,. Discovering frequent patterns from uncertain data streams with time-fading and landmark models[J].--, 2013: 174-196. doi: 10.1007/978-3-642-37574-3_8.

[8] 朱跃龙, 彭力, 李士进, 等. 水文时间序列模体挖掘[J]. 水利学报, 2012, 43(12): 1422-1430.

ZHU Yuelong, PENGLi, LI Shijin,.Research on hydrological time series mining [J]., 2012, 43(12): 1422-1430.

[9] 张懿璞. 转录因子结合位点识别问题的算法研究[D]. [博士论文], 西安电子科技大学, 2014.

ZHANG Yipu. Algorithm research on the problem of transcription factor binging sites identification[D]. [Ph.D. dissertation], XidianUniversity,2014.

[10] 杨矫云. 大规模生物序列分析的高性能算法和模型[D]. [博士论文], 中国科学技术大学, 2014.

YANG Jiaoyun. High performance algorithms and models for large-scale biological sequence analysis[D]. [Ph.D. dissertation], University of Science and Technology of China,2014.

[11] LIN J, KEOGH E, PATEL P,. Finding motifs in time series[C]. Proceedings of the 2nd Workshop on Temporal Data Mining at KDD, District of Colombia, USA, 2002: 53-68.

[12] CHIU B, KEOGH E, and LONARDI S. Probabilistic discovery of time series motifs[C]. 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, District of Colombia, USA, 2003: 493-498. doi: 10.1145/956750.956808.

[13] FERREIRA P G, AZEVEDO P J, SILVA C G,. Mining approximate motifs in time series[C]. 9th international conference on Discovery Science, Berlin, Germany, 2006: 89-101 .

[14] MUEEN A, KEOGH E, ZHU Q,. Exact discovery of time series motif[C]. 9th SIAM International Conference on Data Mining 2009, Nevada, USA, 2009: 469-480.

[15] ABDULLAH M and NIKAN C. Enumeration of time series motifs of all lengths[J]., 2015,45:105-132. doi: 10.1007/s10115-014-0793-4.

[16] 张懿璞, 霍红卫, 于强, 等. 用于转录因子结合位点识别的定位投影求精算法[J]. 计算机学报, 2013, 36(12): 2545-2559. doi: 10.3724/SP.J.1016.2013.02545.

ZHANG Yipu, HUO Hongwei, YU Q,. A novel fixed-position projection refinement algorithm for TFBS Identification[J]., 2013, 36(12): 2545-2559. doi: 10.3724/SP.J.1016.2013.02545.

[17] TIMOTHY L B. DREME: motif discovery in transcription factor ChIP-seq data[J]., 2011, 17(12): 1653-1659. doi:10.1093/bioinformatics/btr261.

[18] DANIEL Q and XIE Xiaohui. EXTREME: an online EM algorithm for motif discovery[J]., 2014, 30(12): 1667-1673. doi:10.1093/bioinformatics/btu093.

[19] THANH T L T, PENG Liping, DIAO Yanlei,. CLARO: modeling and processing uncertain data streams[J]., 2012, 21: 651–676. doi: 10.1007/s00778-011-0261-7.

[20] ARCHAMBEAU C and VERLEYSEN M. Manifold constrained finite Gaussian mixtures [C]. 8th International Work Conference on Artificial Neural Networks, Berlin, Germany, 2005: 820–828.

[21] MICHELE D. Modeling and querying data series and data streams with uncertainty[D]. [Ph.D. dissertation], University of Trento, 2014.

[22] HONG Y. On computing the distribution function for the sum of independent and non-identical random indicators [R]. Technical Report, Department of Statistics, Virginia Tech, 2011.

[23] 曲文龙, 张克君, 杨炳儒, 等. 基于奇异事件特征聚类的时间序列符号化方法[J]. 系统工程与电子技术, 2006, 28(8): 1131–1134.

QU Wenlong, ZHANG Kejun, YANG Bingru,. Time series symbolization based on singular event feature clustering[J]., 2006, 28(8): 1131–1134.

[24] JESSICA L, EAMONN K, LI W,. Experiencing SAX: a novel symbolic representation of time series[J]., 2007, 15: 107–144. doi:10.1007/s10618-007-0064-z.

王 菊： 女，1991年生，博士生，研究方向为数据挖掘.

刘付显： 男，1962年生，教授，研究方向为作战建模与仿真、数据挖掘.

Motif Discovery Algorithm for Multiple Attributes Uncertain Data Stream

WANG Ju LIU Fuxian

(,,’710051,)

Algorithm of motif discovery for multiple attributes uncertain data stream is proposed on the basis of MEME (Multiple Expectation-maximization for Motif Elicitation), which consults the thought of sequential pattern discovery in bioinformatics to solve the problem of frequent pattern discovery for multiple attributes uncertain data stream. A new method for update calculation of uncertain sliding window is designed based on mixed type model, SAX (Symbolic Aggregate approXimation) symbolic strategy is improved, and similarity analysis method for multiple attributes motifs under different sliding windows is put forward. The proposed algorithm is verified to be correct functionally by a set of uncertain data stream in the wireless sensor network of air and missile defense. Its accuracy is measured through planting different number of motifs. Furthermore, comparison with previous algorithm with tuples’ valid probability set to 1 shows that the proposed algorithm can discover frequent pattern for multiple attributes uncertain data stream precisely.

Data mining; Motif discovery; Uncertain data stream; Multiple Expectation-maximization for Motif Elicitation (MEME) algorithm

TP391

A

1009-5896(2017)01-0159-08

10.11999/JEIT160247

2016-03-17；改回日期：2016-08-16；

2016-09-30

王菊 yonglingjuke@126.com

国家自然科学基金(61272011)

The National Natural Science Foundation of China (61272011)