一種面向多屬性不確定數據流的模體發現算法

王 菊 劉付顯

?

一種面向多屬性不確定數據流的模體發現算法

王 菊*劉付顯

(空軍工程大學防空反導學院 西安 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)