一種可交叉的帶時(shí)間約束的互異最小情節(jié)計(jì)數(shù)方法

李 威 吳志剛 李健俊 陸海龍

1(浙江中煙工業(yè)有限責(zé)任公司 杭州 310001)2(杭州世平信息科技有限公司 杭州 310012) (lwei@zjtobacco.com)

考慮事件的發(fā)生順序，面向序列數(shù)據(jù)的挖掘算法主要分為頻繁序列挖掘和頻繁情節(jié)挖掘2類，但其面向的數(shù)據(jù)類型仍存在差異.頻繁序列挖掘是在一組序列的集合上進(jìn)行挖掘，找出眾多序列中頻繁出現(xiàn)的子序列，如獲取多個(gè)用戶的網(wǎng)絡(luò)行為信息，從中挖掘他們?yōu)g覽網(wǎng)頁的共同操作行為.該領(lǐng)域的經(jīng)典算法包括GSP算法、Prefix Span算法、SPADE算法、SPAM算法等[1-3].

頻繁情節(jié)挖掘算法其數(shù)據(jù)類型為一長(zhǎng)串帶有發(fā)生時(shí)間的有序信號(hào)事件序列，其工作目標(biāo)是從中找出事件序列中頻繁出現(xiàn)的子序列，從而揭示相鄰信號(hào)事件的關(guān)聯(lián)關(guān)系和發(fā)生規(guī)律.如何發(fā)現(xiàn)頻繁情節(jié)已成為數(shù)據(jù)挖掘領(lǐng)域的熱點(diǎn)問題之一，學(xué)者們先后研究了許多算法[4-6]，如WINEPI，MINEPI，EpiBF，NONEPI，MANEPI等.這些基于最小發(fā)生、窗口發(fā)生的算法，或因?yàn)榍楣?jié)發(fā)生之間可能會(huì)產(chǎn)生重疊，導(dǎo)致情節(jié)發(fā)生的“過計(jì)數(shù)”問題，或?qū)⑶楣?jié)設(shè)置為發(fā)生時(shí)間完全獨(dú)立的無交疊設(shè)定，存在情節(jié)漏記.此外，上述算法都是基于靜態(tài)數(shù)據(jù)的，在進(jìn)行情節(jié)挖掘時(shí)，基于事件的統(tǒng)計(jì)特性使用廣度優(yōu)先的搜索策略，生成候選情節(jié)，然后進(jìn)行情節(jié)發(fā)生計(jì)數(shù)，滿足最小支持度閾值的情節(jié)即為頻繁情節(jié).

這類方法以事件出現(xiàn)頻率為基準(zhǔn)，按照支持度閾值，首先將事件劃分為頻繁項(xiàng)與非頻繁項(xiàng)，進(jìn)而根據(jù)情節(jié)的向下閉合特性生成候選情節(jié).但是動(dòng)態(tài)數(shù)據(jù)流環(huán)境下，事件的出現(xiàn)頻度時(shí)刻發(fā)生變化，原本頻繁的事件可能會(huì)變得不頻繁，而不頻繁的事件可能在某些時(shí)刻轉(zhuǎn)變?yōu)轭l繁事件.因此，以上所描述的方法無法直接應(yīng)用到數(shù)據(jù)變化的動(dòng)態(tài)頻繁情節(jié)挖掘中.

據(jù)了解，現(xiàn)有的能夠應(yīng)對(duì)動(dòng)態(tài)數(shù)據(jù)頻繁挖掘的算法極少，與一組序列數(shù)據(jù)相比，長(zhǎng)串?dāng)?shù)據(jù)不易分割的特點(diǎn)更加劇了動(dòng)態(tài)頻繁情節(jié)挖掘的難度.為了解決長(zhǎng)串序列數(shù)據(jù)不易進(jìn)行分割的問題，現(xiàn)有的情節(jié)定義方法通常采用窗口計(jì)數(shù)、最小發(fā)生計(jì)數(shù)、無交疊發(fā)生計(jì)數(shù)等方式.

1 相關(guān)工作

1) MESELO算法.

MESELO算法是由Ao等人[7]提出的，該算法處理的序列是一個(gè)完整信號(hào)序列，給出了一種基于最后一次出現(xiàn)的最小情節(jié)發(fā)生定義，將信號(hào)序列按照固定長(zhǎng)度進(jìn)行窗口切割劃分，且每個(gè)窗口起始時(shí)刻相差為1，這使得對(duì)于長(zhǎng)度為L(zhǎng)的序列數(shù)據(jù)，需要建立(L-|w|+1)個(gè)窗口，其中|w|表示窗口大小.然而在現(xiàn)實(shí)的場(chǎng)景中：其一，該算法很難保證數(shù)據(jù)間隔的穩(wěn)定性；其二，算法需要對(duì)每個(gè)時(shí)間間隔內(nèi)的挖掘結(jié)果進(jìn)行存儲(chǔ)，冗余數(shù)據(jù)多，占用大量?jī)?nèi)存.而且，在各時(shí)刻點(diǎn)統(tǒng)計(jì)情節(jié)出現(xiàn)頻率時(shí)，需要對(duì)各時(shí)段內(nèi)挖掘到的情節(jié)進(jìn)行統(tǒng)計(jì)并去除重復(fù)計(jì)數(shù)的情節(jié).

2) ONCE算法.

有限狀態(tài)自動(dòng)機(jī)[8]通過狀態(tài)轉(zhuǎn)移，實(shí)現(xiàn)對(duì)特定情節(jié)的計(jì)數(shù)工作.其工作原理是按照情節(jié)順序建立狀態(tài)機(jī).在捕獲到當(dāng)前等待事件后進(jìn)行狀態(tài)轉(zhuǎn)移，轉(zhuǎn)為等待情節(jié)的下一事件.當(dāng)情節(jié)的最后一個(gè)事件到達(dá)時(shí)，狀態(tài)機(jī)跳轉(zhuǎn)到結(jié)束態(tài)，意味著一個(gè)完整情節(jié)的發(fā)生.但有限狀態(tài)機(jī)所捕獲的情節(jié)發(fā)生沒有時(shí)間跨度的約束，存在一次情節(jié)發(fā)生開始事件與結(jié)束事件時(shí)間跨度較長(zhǎng)的情況，這類情節(jié)發(fā)生不再具備較強(qiáng)的現(xiàn)實(shí)意義，而且對(duì)于交叉發(fā)生的情節(jié)不具備識(shí)別能力.

ONCE算法主要是利用狀態(tài)轉(zhuǎn)移的思想，是一種對(duì)帶時(shí)間約束的無交叉最小發(fā)生情節(jié)進(jìn)行計(jì)數(shù)的計(jì)數(shù)算法：它構(gòu)建了一種名為OccMap的數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)可以用來存儲(chǔ)事件信號(hào)的時(shí)間戳.當(dāng)最后一行為激活態(tài)，且有對(duì)應(yīng)信號(hào)事件到達(dá)時(shí)，表明存在一次完整的情節(jié)發(fā)生，之后通過自底向上對(duì)OccMap表進(jìn)行信號(hào)事件選取，得到最小情節(jié)發(fā)生，然后檢驗(yàn)情節(jié)發(fā)生的時(shí)間跨度是否滿足約束.如果滿足時(shí)間跨度約束，則表明捕獲到一次符合條件約束的情節(jié)發(fā)生，可以進(jìn)行情節(jié)計(jì)數(shù)+1的操作.該算法和OccMap結(jié)構(gòu)詳細(xì)見Li等人[9]以及李健等人[10]的研究.

ONCE算法按照無交疊的情節(jié)最小發(fā)生進(jìn)行掃描計(jì)數(shù)，不適用于交叉互異的最小情節(jié)發(fā)生.某些交叉發(fā)生的互異情節(jié)不能被挖掘捕獲.

現(xiàn)有情節(jié)定義方法通常為保證情節(jié)發(fā)生計(jì)數(shù)的方便性，以犧牲準(zhǔn)確性為代價(jià)，采用窗口計(jì)數(shù)、最小發(fā)生計(jì)數(shù)、無交疊發(fā)生計(jì)數(shù)等方式.這些計(jì)數(shù)方式或事件被重復(fù)使用，存在重復(fù)計(jì)數(shù)問題，或由于情節(jié)的無交叉性某些情節(jié)被漏記.在此，我們定義一種更為通用的情節(jié)計(jì)數(shù)方式——可交叉的帶時(shí)間約束的互異最小發(fā)生，基于這種情節(jié)定義方式實(shí)現(xiàn)高效的情節(jié)計(jì)數(shù).我們復(fù)用了ONCE算法采用的OccMap結(jié)構(gòu)，通過設(shè)計(jì)該結(jié)構(gòu)的初始化過程，實(shí)現(xiàn)帶時(shí)間約束的可交叉最小發(fā)生情節(jié)進(jìn)行計(jì)數(shù)，在我們提出的情節(jié)定義下完成情節(jié)發(fā)生的準(zhǔn)確計(jì)數(shù).

2 實(shí)現(xiàn)方案

參考李健等人[10]的計(jì)數(shù)方案提出的OccMap數(shù)據(jù)結(jié)構(gòu)，本文對(duì)OccMap結(jié)構(gòu)的情節(jié)判定和初始化步驟進(jìn)行了改進(jìn)，實(shí)現(xiàn)單遍掃描序列數(shù)據(jù)，完成對(duì)可交叉的帶時(shí)間約束的互異最小情節(jié)計(jì)數(shù)的工作，該算法命名為ONCE-TDM.具體操作過程如下：

1) OccMap表建立.

如圖1所示，以序列情節(jié)α4=〈A,B,B〉為例(α的上標(biāo)“4”，表示時(shí)間跨度最大為4)，按順序建立存儲(chǔ)事件時(shí)間戳的對(duì)應(yīng)行，目標(biāo)情節(jié)和各行共同構(gòu)成1張OccMap表，記作OM(αδ)=[l1,l2,…,lk].將第1行事件A設(shè)置為激活狀態(tài)，表示OccMap表正等待事件A的到達(dá)，其他行設(shè)置未激活狀態(tài).之后隨著序列S中每個(gè)事件的產(chǎn)生和到達(dá)，OccMap不斷保存和更新.

圖1 α4=〈A,B,B〉在序列S中的計(jì)數(shù)過程

2) OccMap表更新.

隨著長(zhǎng)序列S中事件的到達(dá)，需要比較OccMap中處于激活狀態(tài)的各行事件與到達(dá)事件是否相同，若相同，則將該事件時(shí)間戳加入已激活的事件對(duì)應(yīng)行中，將OccMap表中第1個(gè)無數(shù)據(jù)的行設(shè)置為激活狀態(tài)，表示等待該行類型的信號(hào)事件到達(dá).

3) OccMap最后數(shù)據(jù)到達(dá).

最后一行到達(dá)表示找到一個(gè)完整的情節(jié)發(fā)生，因?yàn)榘凑瘴覀兊募せ钜?guī)則，OccMap表中的數(shù)據(jù)必定滿足l1[1]<l2[1]<…<lk[1]，下面將判斷形成的情節(jié)發(fā)生是否滿足約束條件.

4) 情節(jié)約束條件判定.

一種多層小型化5G毫米波功率分配器設(shè)計(jì)…………………………………………… 姬曉春，姬五勝，王林年，張志悅，童滎贇，涅佛達(dá)夫.E.I（6）

考慮到本文所要尋找的是情節(jié)的最小發(fā)生，所以當(dāng)最后一行激活且有事件匹配時(shí)，先在OccMap中自底向上選中每行能構(gòu)成情節(jié)最小發(fā)生的事件時(shí)間戳.

最后一行的選中事件即為剛到達(dá)的唯一的時(shí)間戳所表示的事件，之后向上確定每行選中事件時(shí)尋找發(fā)生時(shí)間早于下一行選中事件時(shí)間戳，且最靠近下一事件發(fā)生時(shí)刻的時(shí)間，即小于下一事件時(shí)間戳的本行時(shí)間戳的最大值，從而保證選中事件構(gòu)成的發(fā)生為最小情節(jié)發(fā)生.得到情節(jié)最小發(fā)生的時(shí)間跨度[ts,te]，若te-ts≤δ，則存在1次情節(jié)發(fā)生，滿足最小時(shí)間跨度約束；相反，則情節(jié)發(fā)生不能滿足時(shí)間約束.

如圖1(5)所示，α4=〈A,B,B〉的一次最小發(fā)生ts=1,te=5，滿足時(shí)間約束δ(δ=4).

5) OccMap表初始化.

在完成1組選中事件的條件約束判定之后，需要對(duì)OccMap進(jìn)行初始化操作，以便對(duì)后續(xù)序列進(jìn)行情節(jié)計(jì)數(shù).

本文所定義的情節(jié)發(fā)生其事件必須滿足互異性，但發(fā)生時(shí)間的時(shí)間跨度可以有重疊.在此，我們對(duì)OccMap初始化步驟進(jìn)行重新設(shè)計(jì)，使得它能勝任帶時(shí)間約束可交叉的互異最小情節(jié)的計(jì)數(shù)工作.

由于滿足和不滿足時(shí)間跨度約束的情節(jié)發(fā)生在OccMap初始化時(shí)操作情況是不同的，在此對(duì)2種情況進(jìn)行分類討論.

1) 滿足約束條件發(fā)生的OccMap初始化.

按照之前描述的步驟，在情節(jié)最后事件到達(dá)后，按要求自底向上按層查找，可得到最小發(fā)生的時(shí)間跨度[ts,te].考慮到最大化的捕獲序列S中滿足要求的情節(jié)發(fā)生，我們?cè)黾?次自上而下確定情節(jié)發(fā)生時(shí)間戳的步驟，如圖2所示:

不同的學(xué)生有著不同的學(xué)習(xí)層次，不同的學(xué)生學(xué)習(xí)能力也不盡相同，因此，在進(jìn)行分層異步教學(xué)時(shí)，要進(jìn)行合理的分層，保證學(xué)生學(xué)習(xí)能力與知識(shí)的匹配，學(xué)習(xí)上不產(chǎn)生很大的壓力，導(dǎo)致學(xué)習(xí)興趣的喪失。在分層異步教學(xué)中實(shí)現(xiàn)對(duì)學(xué)生進(jìn)行合理的分配，需對(duì)每一個(gè)學(xué)生進(jìn)行充分了解，根據(jù)學(xué)生的理解水平和學(xué)習(xí)能力進(jìn)行合理分組，再對(duì)每一個(gè)組的教學(xué)方式和授課方法進(jìn)行調(diào)整，使每一個(gè)學(xué)生都能夠從不一樣的程度進(jìn)行學(xué)習(xí)，以學(xué)生為主體地位，對(duì)每一個(gè)組進(jìn)行不一樣的指導(dǎo)，充分調(diào)動(dòng)學(xué)生學(xué)習(xí)的積極性，漸漸使理解能力差的學(xué)生也能夠熟練地掌握知識(shí)。

圖2 α6=〈A,B,A,C〉在序列S中的計(jì)數(shù)過程

圖3 α4=〈A,B,A〉在序列S中的計(jì)數(shù)過程

以圖2(5)中的序列數(shù)據(jù)而言，如果以O(shè)cc1(α6,S)=〈1,2,4,5〉作為本次情節(jié)的發(fā)生，則為了保證互異性，事件(A,4)不能被2次使用.

而如果增加1次自上而下確定情節(jié)發(fā)生時(shí)間戳的步驟，則在保證最小發(fā)生時(shí)間跨度不變的同時(shí)，可以選擇較為靠前的事件時(shí)間戳(A,3).此時(shí)，由于情節(jié)發(fā)生可交叉的設(shè)定，(A,4)將可以用于下一次情節(jié)發(fā)生Occ2(α6,S)=〈4,6,7,8〉，這使得情節(jié)發(fā)生計(jì)數(shù)更加準(zhǔn)確.

在確定情節(jié)發(fā)生的時(shí)間戳之后，將OccMap表中選中事件及各行選中事件之前的數(shù)據(jù)刪除，同時(shí)，由于選中事件已經(jīng)被使用，刪除與選中事件相同的時(shí)間戳，如圖2(5+)中第1行數(shù)據(jù)(A,3).

最后，對(duì)表中剩余數(shù)據(jù)進(jìn)行檢查操作，確保每行數(shù)據(jù)符合OccMap表的要求，即l1[1]<l2[1]<…，并將表中第1個(gè)空行及之前行設(shè)置為激活態(tài).如圖2(5++)，剩余數(shù)據(jù)(A,4)的第1行數(shù)據(jù)為激活態(tài)，第2行為首個(gè)空行，也設(shè)置為激活態(tài)，代表等待第2行數(shù)據(jù)的到達(dá).

2) 不滿足約束條件發(fā)生的OccMap初始化.

根據(jù)之前的討論，OccMap在各層有數(shù)據(jù)的情況下才能激活下一層事件，所以當(dāng)情節(jié)最后1個(gè)事件到達(dá)，必可以構(gòu)成至少1個(gè)按順序的序列情節(jié).我們從最后一行開始，自底向上逐層查找，找到目標(biāo)情節(jié)的最小發(fā)生及情節(jié)時(shí)間跨度[t1,tk]，因此如果該組序列情節(jié)不滿足約束條件，存在的問題當(dāng)且僅當(dāng)是選定的情節(jié)發(fā)生超出其時(shí)間跨度約束.

如圖3(6)所示，已知選中的這組情節(jié)的發(fā)生已經(jīng)是最小發(fā)生，時(shí)間跨度達(dá)到最小值，若該組時(shí)間戳數(shù)據(jù)不能滿足要求，則說明當(dāng)前狀態(tài)下無法找到滿足時(shí)間約束的情節(jié)，該組數(shù)據(jù)作廢.作廢情況下，選中事件并沒有被使用，與后續(xù)事件構(gòu)成情節(jié)發(fā)生時(shí)，不存在事件被重復(fù)利用的情況，如圖3(6+)中事件(A,6).所以表中與選中事件相同的事件不必進(jìn)行刪除操作.

又知，當(dāng)前選中情節(jié)發(fā)生已經(jīng)為最小發(fā)生，且超過時(shí)間跨度約束.則此時(shí)自下而上選中的各行較為靠后的數(shù)據(jù)(如圖3(6+)中事件B選中時(shí)間戳為5的數(shù)據(jù))，若能與后續(xù)到達(dá)的事件再次構(gòu)成情節(jié)發(fā)生，其時(shí)間跨度只可能大于本次發(fā)生，所以不必再自上而下找發(fā)生較靠前的等價(jià)發(fā)生，可直接判定選中數(shù)據(jù)及各行選中數(shù)據(jù)之前的數(shù)據(jù)失效，對(duì)其進(jìn)行刪除操作.

接下來與按照滿足約束條件發(fā)生OccMap初始化的流程一致，對(duì)剩余數(shù)據(jù)進(jìn)行整理，保證剩余事件能滿足情節(jié)中事件的順序約束(l1[1]<l2[1]<…).并將有數(shù)據(jù)的行和第1個(gè)無數(shù)據(jù)的行設(shè)置為激活狀態(tài)，表示OccMap正等待這些數(shù)據(jù)的到達(dá).

至此，利用OccMap數(shù)據(jù)結(jié)構(gòu)，按照以上5個(gè)步驟，實(shí)現(xiàn)對(duì)長(zhǎng)串序列數(shù)據(jù)S中帶時(shí)間約束的特定情節(jié)αδ的計(jì)數(shù)工作.

3 結(jié) 論

本文綜合考慮情節(jié)發(fā)生的時(shí)間跨度問題、信號(hào)事件的互異性、情節(jié)的可交叉性，提出一種更具普適性的情節(jié)定義方式.文中提出的情節(jié)定義滿足情節(jié)反單調(diào)性，參照ONCE算法提出的情節(jié)計(jì)數(shù)方案，利用算法構(gòu)建的OccMap數(shù)據(jù)，通過修改OccMap的情節(jié)判定和初始化過程，實(shí)現(xiàn)對(duì)序列數(shù)據(jù)1遍掃描，完成對(duì)有交叉帶時(shí)間約束的最小情節(jié)發(fā)生精確計(jì)數(shù)的工作.