王 菊 劉付顯

?

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

王 菊*劉付顯

(空軍工程大學(xué)防空反導(dǎo)學(xué)院 西安 710051)

該文針對多屬性不確定數(shù)據(jù)流的頻繁模式發(fā)現(xiàn)問題，借鑒生物信息學(xué)中的模體發(fā)現(xiàn)思想，提出了一種基于MEME(Multiple Expectation-maximization for Motif Elicitation)的多屬性不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法。該算法根據(jù)不確定數(shù)據(jù)流的特點，設(shè)計了基于混合型模型的不確定滑動窗口更新計算方法，改進(jìn)了SAX(Symbolic Aggregate approXimation)的符號化策略，提出了不同滑動窗口下多屬性模體的相似性分析方法。在實驗當(dāng)中，用防空反導(dǎo)情報傳感器網(wǎng)絡(luò)中的一組不確定數(shù)據(jù)流驗證了其功能，通過植入不同數(shù)目的模體測試了其發(fā)現(xiàn)準(zhǔn)確率，并在元組有效概率設(shè)置為1的條件下與已有算法進(jìn)行了比較，結(jié)果表明：該算法可以較準(zhǔn)確地發(fā)現(xiàn)多屬性不確定數(shù)據(jù)流中的頻繁模式。

數(shù)據(jù)挖掘；模體發(fā)現(xiàn)；不確定數(shù)據(jù)流；MEME(Multiple Expectation-maximization for Motif Elicitation)算法

1 引言

多屬性不確定數(shù)據(jù)流的頻繁模式發(fā)現(xiàn)問題可以歸結(jié)為數(shù)據(jù)挖掘領(lǐng)域中的關(guān)聯(lián)規(guī)則挖掘問題，其實質(zhì)是發(fā)現(xiàn)動態(tài)多屬性數(shù)據(jù)中重復(fù)出現(xiàn)的相似模式。作為關(guān)聯(lián)規(guī)則挖掘中的關(guān)鍵問題，多屬性不確定數(shù)據(jù)流中頻繁模式的發(fā)現(xiàn)準(zhǔn)確率會受到其動態(tài)性、不確定性以及屬性之間關(guān)聯(lián)性的影響，已成為數(shù)據(jù)挖掘領(lǐng)域中的一個研究熱點和難點。

針對不確定數(shù)據(jù)流的頻繁模式挖掘，Leung等人[4]提出了SUF-growth(mine Frequent itemsets from Streams on Uncertain data)算法，基于該算法的框架，出現(xiàn)了較多的改進(jìn)算法，如基于滑動窗口的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)算法和基于界標(biāo)窗口的XTUF- streaming(eXtended TUF-streaming)算法[7]等，但這些算法只適應(yīng)于單屬性的不確定數(shù)據(jù)流。在實際數(shù)據(jù)流的產(chǎn)生過程中，不僅數(shù)據(jù)是動態(tài)的，且可能會有多個屬性同時到達(dá)，而關(guān)于如何挖掘這類多屬性不確定數(shù)據(jù)流的研究還相對較少。

模體發(fā)現(xiàn)屬于數(shù)據(jù)挖掘中的序列模式發(fā)現(xiàn)[8]，來源于生物信息學(xué)當(dāng)中，也稱為轉(zhuǎn)錄因子結(jié)合位點識別，用于尋找在序列當(dāng)中具有功能和排列相似的短核苷酸片段[9]，主要算法有隨機(jī)投影(Random Projection), EM(Expectation Maximization), MEME和Voting等[10]。借鑒生物信息學(xué)中模體發(fā)現(xiàn)的思想，Lin等人[11]在2002年首次提出了時間序列模體發(fā)現(xiàn)的概念，其他專家學(xué)者又相繼提出了一種線性時間下的隨機(jī)投影方法[12]、致密球[13]、MK算法[14]和MOEN算法[15]等。

本文把該思路做了進(jìn)一步的拓展，將模體發(fā)現(xiàn)的概念應(yīng)用于多屬性不確定數(shù)據(jù)流的頻繁模式發(fā)現(xiàn)中，提出了一種基于MEME的多屬性不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法，在傳統(tǒng)時間序列模體發(fā)現(xiàn)的基礎(chǔ)上，增加了處理不確定性、動態(tài)性和多屬性模體相似性分析等功能。該算法設(shè)計了基于混合型模型的不確定滑動窗口更新計算方法，改進(jìn)了SAX的符號化策略，提出了不同滑動窗口下多屬性模體的相似性分析方法，能夠較準(zhǔn)確地發(fā)現(xiàn)多屬性不確定數(shù)據(jù)流中的頻繁模式。

2 MEME算法

文獻(xiàn)[16]和文獻(xiàn)[18]中詳細(xì)介紹了MEME算法，其核心是定義了一個二元隨機(jī)變量，通過計算每一個(表示一個長度為的堿基片段)的似然值來尋找模體。其中，表示每一個對應(yīng)的背景成分或模體成分，即當(dāng)字符表示為一個結(jié)合位點時，，否則。該算法將整個序列集合的似然值表示為

E步的具體表達(dá)式為

M步的具體表達(dá)式為

(3)

E步和M步重復(fù)執(zhí)行，直至收斂。

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

3.1 算法設(shè)計思路

基于MEME的多屬性不確定數(shù)據(jù)流模體發(fā)現(xiàn)的核心有兩點：一是如何將具有時序性、海量性、無界性、實時性、高速性和連續(xù)性等特點的數(shù)據(jù)序列合理地轉(zhuǎn)換為符號序列集合；二是如何從不同屬性的模體中發(fā)現(xiàn)潛在的規(guī)律。

基于此，本文采用混合型模型對不確定數(shù)據(jù)流進(jìn)行表示，利用滑動窗口對有效時間內(nèi)的不確定數(shù)據(jù)流進(jìn)行劃分，對滿足一定條件的數(shù)據(jù)進(jìn)行符號化，執(zhí)行MEME算法進(jìn)行模體發(fā)現(xiàn)，最后再對不同滑動窗口下多屬性模體的相似性進(jìn)行分析，其思路如圖1所示。

圖1 算法設(shè)計思路

3.2多屬性不確定數(shù)據(jù)流表示

采用混合型模型可以對多屬性不確定數(shù)據(jù)流進(jìn)行表示，本文又進(jìn)一步地定義了元組有效概率，可以簡化用混合型模型所表示的多屬性不確定數(shù)據(jù)流，達(dá)到數(shù)據(jù)校驗和快速計算的目的。

3.2.1混合型模型 文獻(xiàn)[19]中所提出的混合型模型(mixed-type model)綜合考慮了存在級不確定性和屬性級不確定性，不僅能處理離散型屬性，還可以處理連續(xù)型屬性，是一種較為通用的不確定數(shù)據(jù)流模型，其定義如下。

定義1[19]混合型模型 給定一個元組，將其個連續(xù)不確定屬性用表示，個離散不確定屬性用表示，其余確定屬性用表示，混合模型的分布用表示。其中，是元組的存在概率(Tuple Existence Probability, TEP),是所有不確定屬性的聯(lián)合概率密度函數(shù)，定義為。因此，可以用一個定義在(代表該元組不存在的情形)上的隨機(jī)向量表示，即

3.2.2元組有效概率 基于混合型模型，本文定義了元組的有效概率，該概率不僅能夠綜合屬性出現(xiàn)概率和元組存在概率的影響，起到數(shù)據(jù)校驗的效果，還能簡化多屬性不確定數(shù)據(jù)流的表示形式，提高計算效率。

3.3基于混合型模型的不確定滑動窗口

多屬性不確定數(shù)據(jù)流具有無限性，因此要處理從數(shù)據(jù)出現(xiàn)直至當(dāng)前時刻的所有數(shù)據(jù)是不可能的。針對這個問題，本文設(shè)計了一種基于混合型模型的不確定滑動窗口更新計算方法，保證滑動窗口中有效元組的數(shù)目依置信概率為個。通常情況下，有效元組數(shù)目由所處理不確定數(shù)據(jù)流的稀疏程度以及計算機(jī)的處理能力決定，置信概率由所處理不確定數(shù)據(jù)流的用途和用戶的偏好決定。

3.3.1不確定滑動窗口的定義及更新 在一個不確定數(shù)據(jù)流中，表示滑動窗口的大小，表示該窗口中有效元組的數(shù)目，不確定滑動窗口的定義和更新過程如下。

定義3[21]不確定滑動窗口 由于滑動窗口的實際長度具有不確定性，因此該窗口被定義為不確定滑動窗口，其滿足

當(dāng)新元組到來時，更新滑動窗口的計算流程如表1所示。

表1不確定滑動窗口更新過程

輸入： 輸出： 被賦予空集 Loop If (中的新元組到達(dá)) then ←∪ While do ← (是窗口中最早的元素) End while End if End loop

3.3.2基于混合型模型的不確定滑動窗口更新計算

根據(jù)定義2和定義3，本文結(jié)合滑動窗口的更新過程和于混合型模型，對約束條件進(jìn)行了變形和簡化。

(9)

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

SAX[23,24]是一種針對一元時間序列符號化的方法，可以用于聚類、分類、索引和異常檢測等。為了將該方法應(yīng)用于不確定數(shù)據(jù)流，確保每個滑動窗口中存在的元組數(shù)目差別不大，使每一種屬性(包括連續(xù)屬性和離散屬性)都能用SAX進(jìn)行符號化，本文將SAX的符號化策略改進(jìn)為以下4個步驟：

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

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

圖2 不同滑動窗口下多屬性模體示意圖

3.5 不同滑動窗口下多屬性模體的相似性分析

為了發(fā)現(xiàn)具有相似性的多屬性模體，本文提出了一種不同滑動窗口下多屬性模體(如圖2所示)的相似性分析方法，該方法可以為具有多屬性的不確定數(shù)據(jù)流預(yù)測、分類、異常檢測和規(guī)則挖掘等提供依據(jù)，其具體處理流程如下。

步驟1 列出窗口中不同屬性間所有模體的組合，如圖2中的窗口1，其所有模體的組合為和；

步驟2 采用Hamming距離對所有的模體組合進(jìn)行相似性匹配，記錄滿足閾值條件的模體組合(閾值根據(jù)實際需要進(jìn)行設(shè)定，本文中設(shè)定為2)，圖2中得到的模體組合為；

步驟3 計算每一個滿足閾值條件模體組合所對應(yīng)的若干個多屬性模體間的相對時間向量。將第1個模體的起始點設(shè)置為0，向量中的值表示模體起始點相對于0點的時間，圖2中模體組合所對應(yīng)的兩個多屬性模體的相對時間向量都為；

步驟4 計算每一個滿足閾值條件模體組合所對應(yīng)的若干個多屬性模體中任意兩個相對時間向量之間的歐氏距離。當(dāng)該距離小于給定(根據(jù)實際的精度要求進(jìn)行設(shè)定，本文中設(shè)定為0.01)時，其相應(yīng)的多屬性模體具有相似性，輸出并記錄該多屬性模體。

3.6 算法設(shè)計

根據(jù)以上的分析，文中提出了一種基于MEME的多屬性不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法，該算法可以對任意一組多屬性不確定數(shù)據(jù)流進(jìn)行模體發(fā)現(xiàn)，其總體描述如表2所示。表中，步驟4和步驟5至步驟8可以同時運(yùn)算，步驟3-步驟8的具體實現(xiàn)方法已在前文中進(jìn)行過介紹。

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

輸入：//為最多可同時處理的滑動窗口數(shù)目，為屬性個數(shù)。 輸出：具有相似性的多屬性模體。 步驟1 初始化參數(shù)，設(shè)置變量； 步驟2 判斷不確定數(shù)據(jù)流是否到來，是轉(zhuǎn)步驟3，否則算法結(jié)束； 步驟3 對建模、規(guī)范化及有效概率計算，得到 步驟4 Loop If (中的新元組到達(dá)) then ←∪； If then ； 被賦予空集； ； If then ； 另存為，轉(zhuǎn)步驟5； Else Continue; End if Else Continue; End if End if 步驟5 對序列集進(jìn)行符號化，得到　個的字符矩陣； 步驟6 對字符矩陣同一行中的字符串執(zhí)行MEME算法，存儲并輸出所發(fā)現(xiàn)的模體 步驟7 釋放所占用的存儲空間； 步驟8 對不同滑動窗口下所發(fā)現(xiàn)的多屬性模體進(jìn)行相似性分析，存儲具有相似性的多屬性模體。 End loop

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

時間飛機(jī)速度發(fā)動機(jī)溫度距離存在概率有效概率 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 案例分析

防空反導(dǎo)情報傳感器網(wǎng)絡(luò)是產(chǎn)生不確定數(shù)據(jù)流的典型應(yīng)用，本文根據(jù)該網(wǎng)絡(luò)對飛機(jī)速度和發(fā)動機(jī)溫度的實時測量數(shù)據(jù)進(jìn)行模體發(fā)現(xiàn)。其實驗平臺是裝有64位Windows7操作系統(tǒng)的個人電腦，具有Core i5-4590的雙核處理器和4GB內(nèi)存，可運(yùn)行Matlab和MEME程序包。

(1)針對本文中所處理的不確定數(shù)據(jù)流，可設(shè)置窗口中有效元組數(shù)目，置信概率,,,。

(2)判斷不確定數(shù)據(jù)流是否實時到來，若數(shù)據(jù)流中斷，則算法終止，否則轉(zhuǎn)下一步繼續(xù)執(zhí)行計算。

(4)繼續(xù)采集諸如表3中的數(shù)據(jù)，根據(jù)元組的有效概率來判斷是否滿足，當(dāng)，得到后，設(shè)置，不斷重復(fù)步驟3。

表4的符號化結(jié)果

速度屬性seq1TGCATTGCTCACGCCCGCGACGCGCAGGCCGCGTCGGAACACGCCCTGCG seq2CGAGGGCGACTAGGGGGAACGCCGACGGGGGGCGCCGCGGTCCGAGGGGC seq3GGCTGGTACCACGGGCTGGCGGCGGTACCGTTGGGGCCCGTGGAGAAGGG 溫度屬性seq1GGGTGGCCTGAGGTTCGGGCCCCCCCGGCAGACCCGCGGCAGCCACGACC seq2GACGCATTCGCGCCTCCGGCGCCTGGACAAGACCCGGCTGCAGGCGCTAC seq3CCGATCGGCCCGGCCGCCGGACGGGCCGCGCTCGATCCTTCACCGGACAA

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

由圖3可知，在表4的兩種屬性中，共發(fā)現(xiàn)了4種模體。進(jìn)而根據(jù)所發(fā)現(xiàn)模體的排序及位置(如圖3中方框內(nèi)所示)，可以反推出原數(shù)據(jù)中模體的位置及形狀，如圖4所示。

從圖4可發(fā)現(xiàn)，所發(fā)現(xiàn)模體在形狀上具有一定的相似性，滿足“模體”在時間序列中的定義，證明文中所提出的算法具有發(fā)現(xiàn)多屬性不確定數(shù)據(jù)流中頻繁模式的功能。

(8)根據(jù)圖3和圖4，可得到如圖5所示的示意圖。

圖3 模體發(fā)現(xiàn)結(jié)果

圖4 模體在原數(shù)據(jù)中的位置及形狀

圖5 不同滑動窗口下所發(fā)現(xiàn)模體的示意圖

4.2 實驗分析

通過4.1節(jié)的案例，驗證了文中算法的功能。為進(jìn)一步分析該算法的性能，本節(jié)設(shè)計了兩個實驗，分別用于測試其模體發(fā)現(xiàn)準(zhǔn)確率和將其與已有算法進(jìn)行比較。

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

從圖6可知，在植入不同數(shù)目模體的情況下，本文算法的模體發(fā)現(xiàn)準(zhǔn)確率在0.8~0.9之間，穩(wěn)定性強(qiáng)。

實驗2 考慮到目前還沒有關(guān)于多屬性不確定數(shù)據(jù)流模體發(fā)現(xiàn)的相關(guān)算法，因此文中需要設(shè)定不確定數(shù)據(jù)流中所有屬性的出現(xiàn)概率和元組存在概率都為1。進(jìn)而通過設(shè)置滑動窗口長度，屬性個數(shù)，滑動窗口不更新，將文中算法與Mueen 提出的MK[14]和MOEN[15]算法在隨機(jī)植入模體的3組白噪聲數(shù)據(jù)集上進(jìn)行比較，其模體發(fā)現(xiàn)準(zhǔn)確率結(jié)果如圖7所示。

從圖7可知，文中算法的模體發(fā)現(xiàn)準(zhǔn)確率高于MK和MOEN算法。

5 結(jié)束語

本文在傳統(tǒng)時間序列模體發(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ò)對飛機(jī)速度和發(fā)動機(jī)溫度的實時測量數(shù)據(jù)進(jìn)行了模體發(fā)現(xiàn)，驗證了其功能；(2)通過多次模體植入實驗和算法性能對比實驗，在同等仿真條件下，相比于MK和MOEN算法，驗證了其優(yōu)越性。文中部分內(nèi)容屬于探索性的研究，不確定性理論、智能搜索算法與不確定數(shù)據(jù)流模體發(fā)現(xiàn)的結(jié)合將是本文下一步的研究內(nèi)容。

圖6 本文算法所發(fā)現(xiàn)模體的準(zhǔn)確率 圖7 算法準(zhǔn)確率比較

[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] 湯克明. 不確定數(shù)據(jù)流中頻繁數(shù)據(jù)挖掘[D]. [博士論文], 南京航空航天大學(xué), 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ìn), 等. 水文時間序列模體挖掘[J]. 水利學(xué)報, 2012, 43(12): 1422-1430.

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

[9] 張懿璞. 轉(zhuǎn)錄因子結(jié)合位點識別問題的算法研究[D]. [博士論文], 西安電子科技大學(xué), 2014.

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

[10] 楊矯云. 大規(guī)模生物序列分析的高性能算法和模型[D]. [博士論文], 中國科學(xué)技術(shù)大學(xué), 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] 張懿璞, 霍紅衛(wèi), 于強(qiáng), 等. 用于轉(zhuǎn)錄因子結(jié)合位點識別的定位投影求精算法[J]. 計算機(jī)學(xué)報, 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]. 系統(tǒng)工程與電子技術(shù), 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年生，博士生，研究方向為數(shù)據(jù)挖掘.

劉付顯： 男，1962年生，教授，研究方向為作戰(zhàn)建模與仿真、數(shù)據(jù)挖掘.

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

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

The National Natural Science Foundation of China (61272011)