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

王 菊 劉付顯

?

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

王 菊*劉付顯

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

該文針對(duì)多屬性不確定數(shù)據(jù)流的頻繁模式發(fā)現(xiàn)問題，借鑒生物信息學(xué)中的模體發(fā)現(xiàn)思想，提出了一種基于MEME(Multiple Expectation-maximization for Motif Elicitation)的多屬性不確定數(shù)據(jù)流模體發(fā)現(xiàn)算法。該算法根據(jù)不確定數(shù)據(jù)流的特點(diǎn)，設(shè)計(jì)了基于混合型模型的不確定滑動(dòng)窗口更新計(jì)算方法，改進(jìn)了SAX(Symbolic Aggregate approXimation)的符號(hào)化策略，提出了不同滑動(dòng)窗口下多屬性模體的相似性分析方法。在實(shí)驗(yàn)當(dāng)中，用防空反導(dǎo)情報(bào)傳感器網(wǎng)絡(luò)中的一組不確定數(shù)據(jù)流驗(yàn)證了其功能，通過植入不同數(shù)目的模體測(cè)試了其發(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ī)則挖掘問題，其實(shí)質(zhì)是發(fā)現(xiàn)動(dòng)態(tài)多屬性數(shù)據(jù)中重復(fù)出現(xiàn)的相似模式。作為關(guān)聯(lián)規(guī)則挖掘中的關(guān)鍵問題，多屬性不確定數(shù)據(jù)流中頻繁模式的發(fā)現(xiàn)準(zhǔn)確率會(huì)受到其動(dòng)態(tài)性、不確定性以及屬性之間關(guān)聯(lián)性的影響，已成為數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)研究熱點(diǎn)和難點(diǎn)。

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

模體發(fā)現(xiàn)屬于數(shù)據(jù)挖掘中的序列模式發(fā)現(xiàn)[8]，來(lái)源于生物信息學(xué)當(dāng)中，也稱為轉(zhuǎn)錄因子結(jié)合位點(diǎn)識(shí)別，用于尋找在序列當(dāng)中具有功能和排列相似的短核苷酸片段[9]，主要算法有隨機(jī)投影(Random Projection), EM(Expectation Maximization), MEME和Voting等[10]。借鑒生物信息學(xué)中模體發(fā)現(xiàn)的思想，Lin等人[11]在2002年首次提出了時(shí)間序列模體發(fā)現(xiàn)的概念，其他專家學(xué)者又相繼提出了一種線性時(shí)間下的隨機(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)時(shí)間序列模體發(fā)現(xiàn)的基礎(chǔ)上，增加了處理不確定性、動(dòng)態(tài)性和多屬性模體相似性分析等功能。該算法設(shè)計(jì)了基于混合型模型的不確定滑動(dòng)窗口更新計(jì)算方法，改進(jìn)了SAX的符號(hào)化策略，提出了不同滑動(dòng)窗口下多屬性模體的相似性分析方法，能夠較準(zhǔn)確地發(fā)現(xiàn)多屬性不確定數(shù)據(jù)流中的頻繁模式。

2 MEME算法

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

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

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

(3)

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

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

3.1 算法設(shè)計(jì)思路

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

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

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

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

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

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

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

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

3.3基于混合型模型的不確定滑動(dòng)窗口

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

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

定義3[21]不確定滑動(dòng)窗口 由于滑動(dòng)窗口的實(shí)際長(zhǎng)度具有不確定性，因此該窗口被定義為不確定滑動(dòng)窗口，其滿足

當(dāng)新元組到來(lái)時(shí)，更新滑動(dòng)窗口的計(jì)算流程如表1所示。

表1不確定滑動(dòng)窗口更新過程

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

3.3.2基于混合型模型的不確定滑動(dòng)窗口更新計(jì)算

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

(9)

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

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

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

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

圖2 不同滑動(dòng)窗口下多屬性模體示意圖

3.5 不同滑動(dòng)窗口下多屬性模體的相似性分析

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

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

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

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

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

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

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

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

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

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

時(shí)間飛機(jī)速度發(fā)動(dòng)機(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 實(shí)驗(yàn)與分析

4.1 案例分析

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

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

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

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

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

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

(6)根據(jù)MEME算法，采用MEME程序包，對(duì)表4中的符號(hào)序列集合進(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)模體在形狀上具有一定的相似性，滿足“模體”在時(shí)間序列中的定義，證明文中所提出的算法具有發(fā)現(xiàn)多屬性不確定數(shù)據(jù)流中頻繁模式的功能。

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

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

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

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

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

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

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

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

實(shí)驗(yàn)2 考慮到目前還沒有關(guān)于多屬性不確定數(shù)據(jù)流模體發(fā)現(xiàn)的相關(guān)算法，因此文中需要設(shè)定不確定數(shù)據(jù)流中所有屬性的出現(xiàn)概率和元組存在概率都為1。進(jìn)而通過設(shè)置滑動(dòng)窗口長(zhǎng)度，屬性個(gè)數(shù)，滑動(dòng)窗口不更新，將文中算法與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é)束語(yǔ)

本文在傳統(tǒng)時(shí)間序列模體發(fā)現(xiàn)的基礎(chǔ)上引入了不確定性和動(dòng)態(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ò)對(duì)飛機(jī)速度和發(fā)動(dòng)機(jī)溫度的實(shí)時(shí)測(cè)量數(shù)據(jù)進(jìn)行了模體發(fā)現(xiàn)，驗(yàn)證了其功能；(2)通過多次模體植入實(shí)驗(yàn)和算法性能對(duì)比實(shí)驗(yàn)，在同等仿真條件下，相比于MK和MOEN算法，驗(yàn)證了其優(yōu)越性。文中部分內(nèi)容屬于探索性的研究，不確定性理論、智能搜索算法與不確定數(shù)據(jù)流模體發(fā)現(xiàn)的結(jié)合將是本文下一步的研究?jī)?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), 等. 水文時(shí)間序列模體挖掘[J]. 水利學(xué)報(bào), 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é)合位點(diǎn)識(shí)別問題的算法研究[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]. [博士論文], 中國(guó)科學(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é)合位點(diǎn)識(shí)別的定位投影求精算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 曲文龍, 張克君, 楊炳儒, 等. 基于奇異事件特征聚類的時(shí)間序列符號(hào)化方法[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年生，博士生，研究方向?yàn)閿?shù)據(jù)挖掘.

劉付顯： 男，1962年生，教授，研究方向?yàn)樽鲬?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

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

The National Natural Science Foundation of China (61272011)