◆苗雪連

間隙約束序列模式挖掘的對比研究

◆苗雪連

（河北工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院 天津 300401）

本文首先描述了間隙約束序列挖掘的分類及研究現(xiàn)狀，最后給出了間隙約束的序列模式挖掘在實(shí)際生活中的發(fā)展趨勢。在未來的研究領(lǐng)域中，具有間隙約束的序列模式挖掘仍是一個重要的研究方向。

間隙約束序列挖掘；算法

0 前言

近年來，隨著人們對數(shù)據(jù)挖掘的不斷深入研究以及信息的不斷發(fā)展，序列模式挖掘也得到很大提升，應(yīng)用范圍不僅僅局限于傳統(tǒng)的商業(yè)交易數(shù)據(jù)庫，在醫(yī)學(xué)、社會與科學(xué)等方面均有擴(kuò)展。商業(yè)行為分析如客戶購買行為模式的分析，醫(yī)學(xué)領(lǐng)域如DNA分析，社科類的如自然災(zāi)害預(yù)測，等等。隨著對序列模式挖掘不斷深入的研究，序列模式挖掘劃分越來越細(xì)，具有間隙約束的序列模式挖掘就是其中之一。

1 具有間隙約束的序列挖掘的分類及研究現(xiàn)狀

具有間隙約束的序列模式挖掘問題是：給定序列S、支持度閾值和間隙約束，從序列S中挖掘出所有出現(xiàn)次數(shù)不小于給定支持度閾值的頻繁序列模式，并且模式中任意兩個相鄰元素在序列中出現(xiàn)的位置滿足間隙約束。為了滿足用戶的需求，在已有傳統(tǒng)的的間隙約束序列挖掘研究中，對挖掘的出現(xiàn)加入一種或多種約束條件。目前已有的約束條件有無特殊條件的間隙約束[1]、一次性條件的間隙約束[2]和無重疊條件的間隙約束[3]等三種形式。

（1）一次性條件。一次性條件的間隙約束序列模式挖掘?qū)哂虚g隙約束的序列模式挖掘的出現(xiàn)提出了要求，即模式在序列中的任意兩次出現(xiàn)都不共享序列中同一位置的字符。

（2）無重疊條件。無重疊條件的模式匹配是模式在序列中的任意兩個出現(xiàn)，出現(xiàn)的相同的位置上不能使用相同的字符，相同的字符只能使用在不同的位置上。

（3）無特殊條件。無特殊條件的模式匹配則對出現(xiàn)和位置都沒有要求。

下面對這三種形式的相關(guān)研究進(jìn)行了簡要的介紹。

1.1 無特殊條件

Zhang等人對單序列中帶有通配符的模式挖掘問題進(jìn)行了研究，提出了MPP算法，同時在生物DNA序列上實(shí)驗(yàn)了該序列模式挖掘問題。雖然MPP算法采用Apriori-like性質(zhì)對候選模式進(jìn)行了裁剪，有效的解決了具有間隙約束的頻繁模式不能使用Apriori性質(zhì)挖掘的問題，減少了冗余候選模式的產(chǎn)生。但是由于MPP算法考慮模式的所有位置的出現(xiàn)，包括重復(fù)的出現(xiàn)，因此MPP算法產(chǎn)生的候選模式依然很多，這就導(dǎo)致了在處理大規(guī)模數(shù)據(jù)時，MPP算法運(yùn)行效率較低。另外，MPP算法挖掘的頻繁模式項(xiàng)集包含一些表面上看起來是頻繁的模式。理論上，我們認(rèn)為如果一個模式出現(xiàn)的次數(shù)更多的話，頻繁的可能性應(yīng)該更大，但是MPP算法計算得到的挖掘結(jié)果與理論上矛盾了。

針對MPP算法存在的問題，Min等人對MPP算法進(jìn)行了改進(jìn)，提出了AMin算法。首先，重新定義了具有間隙約束的頻繁模式，使得AMin算法可以采用Apriori性質(zhì)進(jìn)行剪枝。方法就是在序列的末尾加上了虛擬字符，這使得一些模式的偏移序列個數(shù)增多了。AMin算法核心思想是:如果挖掘到的一個模式是頻繁的，那么規(guī)定其子模式也是頻繁的。

Zhu and Wu等人提出了MCPaS算法，該算法探索了從多序列中挖掘頻繁模式。該算法雖然做了一些改進(jìn)，但由于其同MPP算法一樣，模式允許重復(fù)出現(xiàn)，所以挖掘效率也不高。

武等人[1]基于網(wǎng)樹建立了不完全網(wǎng)樹結(jié)構(gòu)，提出了MAPD算法。MAPD首先對序列進(jìn)行全面掃描，根據(jù)給定的序列和候選模式構(gòu)建網(wǎng)樹，然后通過計算網(wǎng)樹中的候選模式在序列中的出現(xiàn)數(shù)，與給定的閾值進(jìn)行比較，判斷該模式是否是頻繁模式，該算法高效的解決了在單序列上周期間隙約束的序列模式挖掘問題。

1.2 一次性條件

SAIL算法是Chen等人在2006年提出的，它是為研究具有長度約束和一次性條件的模式匹配問題的算法。SAIL算法旨在盡可能多的找到滿足要求的出現(xiàn)。為了提高解的完備性，SAIL算法分為正向階段和反向階段兩個設(shè)計階段。根據(jù)模式P、序列S和間隙約束，SAIL算法通過建立一個二維表來解決模式匹配問題。若在模式挖掘過程中有多個位置出現(xiàn)時，SAIL算法選擇位置最小的出現(xiàn)作為最優(yōu)出現(xiàn)。

首次在帶通配符的序列模式挖掘中引入一次性條件的是He等人，在MPP算法的基礎(chǔ)上，通過對MPP算法改進(jìn)，提出了兩種啟發(fā)式掃描策略:One-way scan和Two-way scan，即單向掃描和雙向掃描算法。但是因?yàn)闆]有對通配符的范圍進(jìn)行具體的限制，所以不能夠挖掘更加靈活的帶有通配符的模式。

Wu等人[2]在One-off下的序列模式挖掘的條件下，提出了One-off Ming算法。該算法在生物DNA序列上進(jìn)行了相關(guān)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，與其他的序列模式挖掘算法相比，One-off Ming算法能找到更多的出現(xiàn)，并且有效的縮短了挖掘時間。Wu等人在提出One-off Ming算法時，在計算序列模式的支持度時提出了兩種計算支持度的方法，Calsup算法和i-Calsup算法。因?yàn)镃alsup算法在計算支持度的時候可能會丟失一部分的出現(xiàn)，導(dǎo)致頻繁模式項(xiàng)集不準(zhǔn)確，因此對Calsup進(jìn)行了改進(jìn)，形成了第二種計算支持度的算法i-Calsup。i-Calsup為了找到更多的出現(xiàn)，在計算支持度時采用了前向搜索和后向搜索。在前向搜索階段，通過可能匹配的所有位置以及滿足間隙約束條件的所有前一個字符，找到當(dāng)前的字符可能匹配的所有位置，并將它們保存在二維數(shù)組中，直到搜索到模式的最后一個字符的可能匹配的位置。在向后搜索過程中，采用最左優(yōu)先策略，與前向搜索階段搜索順序相反，從最后一個字符開始，對二維數(shù)組中的每個模式的可能匹配位置進(jìn)行選擇。

1.3 無重疊條件

首次在具有間隙約束的序列模式挖掘研究中引入Non-Overlap的是Ding等人，所提出的算法主要挖掘無交叉出現(xiàn)的閉合序列模式。與He等人不同的是，Ding等人在基于INSgrow算法的基礎(chǔ)上提出了模式挖掘算法，另外該算法挖掘的序列為多序列，Ding等人的算法有效的提高了挖掘效率。INSgrow算法是一種貪婪算法，該算法的主要思想是模式增長。首先建立大小為1的零號支持集；之后在每次的迭代過程中，都遵循最左原則進(jìn)行模式增長，Chen和Wu等人已證明了最左原則尋找的模式是局部最優(yōu)，但是可能會導(dǎo)致全局解的不完備。

因?yàn)镮NSgrow算法存在丟失解的現(xiàn)象，武等人在文獻(xiàn)[3]首先論證了無重疊約束的模式匹配是一個P問題，之后基于網(wǎng)樹結(jié)構(gòu)，提出了NETLAP-BEST算法，找到了無重疊序列模式挖掘的完備解，實(shí)驗(yàn)結(jié)果驗(yàn)證了 NETLAP-Best 算法的正確性和有效性。NETLAP-BEST算法在求解時，首先根據(jù)模式匹配問題建立網(wǎng)樹，在網(wǎng)樹上迭代地尋找最右樹根-葉子路徑，之后剪去這條路徑和無用的網(wǎng)樹節(jié)點(diǎn)。

2 發(fā)展趨勢

經(jīng)過多年的發(fā)展與研究，具有間隙約束的序列模式挖掘已取得了較大的發(fā)展，無特殊條件的間隙約束序列模式挖掘已經(jīng)能夠快速高效的找到所有的出現(xiàn)，無重疊條件的間隙約束序列模式匹配問題已被證明為一種P問題，且能找到完備解。但仍存在一些問題，目前一次性條件的序列模式挖掘仍然是一個NP問題，如何優(yōu)化算法，使得提高解的完備性的同時也能提高挖掘速度仍是一個難題。另外，在實(shí)際應(yīng)用的研究過程中，如何合理的設(shè)定具有間隙約束的序列模式挖掘算法的閾值仍沒有較好的評判方法。

具有間隙約束的序列模式挖掘在實(shí)際生活中已經(jīng)有了許多的應(yīng)用。在未來的研究領(lǐng)域中，具有間隙約束的序列模式挖掘仍是一個重要的研究方向。

[1]Wu Youxi，Wang Lingling，et al.Mining Sequential Patterns with Periodic Wildcard Gaps.Applied Intelligence，2014.

[2]吳信東，謝飛，黃詠明，胡學(xué)鋼，高雋.帶通配符和One-Off 條件的序列模式挖掘.軟件學(xué)報，2013.

[3]Youxi Wu，Cong Shen，He Jiang，Xindong Wu.Strict pattern matching under non-overlapping condition.Science China Information Sciences，2017.

圖1 加載OBJ文件的程序流程

圖2 OBJ文件中的頂點(diǎn)相關(guān)參數(shù)

3 3D可視化中人機(jī)交互的實(shí)現(xiàn)

基于WebGL的交互主要是借助鼠標(biāo)和鍵盤進(jìn)行相應(yīng)的操作，通過鼠標(biāo)點(diǎn)觸鍵盤來實(shí)現(xiàn)對事件的監(jiān)聽和加載代碼。在系統(tǒng)操作實(shí)現(xiàn)中，鼠標(biāo)所具有的功能是實(shí)現(xiàn)對鏡頭的有效縮放處理，在操作鼠標(biāo)的時候就能控制鏡頭的移動。系統(tǒng)中網(wǎng)頁的名稱主要包括mousemove、mousedown、mouseup等。事件在發(fā)生的時候需要判斷鼠標(biāo)的具體操作，從而加強(qiáng)對鏡頭的操作控制。

網(wǎng)頁中的鍵盤事件主要有keydown和keyup兩種，在系統(tǒng)平臺中鍵盤操作能夠?qū)δＰ偷木唧w移動進(jìn)行操控，具體按鍵是W鍵和S鍵，觸發(fā)函數(shù)參數(shù)是HTML5標(biāo)準(zhǔn)中的全局變量event，其通過對按鍵的ACSII碼判斷能夠執(zhí)行相應(yīng)的指令。

4 3D可視交互平臺設(shè)計性能分析

4.1 跨瀏覽器的測試

在測試中將基于網(wǎng)絡(luò)安全數(shù)據(jù)構(gòu)建的三維可視模型直接運(yùn)行在三大主流瀏覽器中。結(jié)果顯示，可視模型能夠?qū)崿F(xiàn)無插件穩(wěn)定運(yùn)行。

4.2 基于WebGL技術(shù)模型載入時間測試

為了驗(yàn)證本文可視化方法的有效性，在Intel i7（3.5 GHz）處理器，8 GB內(nèi)存，MacOS 10.12.3（64 bit）平臺上對可視系統(tǒng)進(jìn)行了實(shí)驗(yàn)。文章測試操作以網(wǎng)絡(luò)安全數(shù)據(jù)三維可視模型為例，通過不同瀏覽器的載入來對模型的響應(yīng)時間進(jìn)行實(shí)驗(yàn)測試。選擇的三維可視模型主要由13236個三角面單元構(gòu)成，頂點(diǎn)的數(shù)量達(dá)到了6104個。在上述平臺中分別使用Chrome瀏覽器、Opera瀏覽器、Firefox瀏覽器進(jìn)行測試，最終的響應(yīng)時間分別是1.12ms、1.58ms和1.09ms。經(jīng)過分析比較之后發(fā)現(xiàn)可視模型載入時間短，且最終瀏覽器表現(xiàn)的性能結(jié)果良好。

5 結(jié)束語

基于WebGL技術(shù)構(gòu)建高效能的三維可視平臺是未來Web3D技術(shù)的熱點(diǎn)發(fā)展方向，文章對基于WebGL的3D可視交互平臺的設(shè)計和實(shí)現(xiàn)進(jìn)行了分析測試，構(gòu)建出性能良好、操作方便的3D可視交互平臺，利用WebGL技術(shù)實(shí)現(xiàn)了更加豐富友好的用戶體驗(yàn)。相信在未來WebGL憑借其在交互體驗(yàn)和實(shí)現(xiàn)效率上的優(yōu)越性將在可視分析、虛擬現(xiàn)實(shí)等技術(shù)上得到更廣泛的認(rèn)可。

參考文獻(xiàn):

[1]丁晨溦，程星，袁慧，王巖，鄧維維.Student Devision高校信息交互平臺的設(shè)計與實(shí)現(xiàn)[J].軟件工程師，2015.

[2]汪浩，田豐，張文俊.基于WebGL的交互平臺設(shè)計與實(shí)現(xiàn)[J].電子測量技術(shù)，2015.