間隙約束序列模式挖掘的對(duì)比研究

◆苗雪連

間隙約束序列模式挖掘的對(duì)比研究

◆苗雪連

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

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

間隙約束序列挖掘；算法

0 前言

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

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

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

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

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

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

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

1.1 無(wú)特殊條件

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

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

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

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

1.2 一次性條件

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

首次在帶通配符的序列模式挖掘中引入一次性條件的是He等人，在MPP算法的基礎(chǔ)上，通過(guò)對(duì)MPP算法改進(jìn)，提出了兩種啟發(fā)式掃描策略:One-way scan和Two-way scan，即單向掃描和雙向掃描算法。但是因?yàn)闆](méi)有對(duì)通配符的范圍進(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)，并且有效的縮短了挖掘時(shí)間。Wu等人在提出One-off Ming算法時(shí)，在計(jì)算序列模式的支持度時(shí)提出了兩種計(jì)算支持度的方法，Calsup算法和i-Calsup算法。因?yàn)镃alsup算法在計(jì)算支持度的時(shí)候可能會(huì)丟失一部分的出現(xiàn)，導(dǎo)致頻繁模式項(xiàng)集不準(zhǔn)確，因此對(duì)Calsup進(jìn)行了改進(jìn)，形成了第二種計(jì)算支持度的算法i-Calsup。i-Calsup為了找到更多的出現(xiàn)，在計(jì)算支持度時(shí)采用了前向搜索和后向搜索。在前向搜索階段，通過(guò)可能匹配的所有位置以及滿(mǎn)足間隙約束條件的所有前一個(gè)字符，找到當(dāng)前的字符可能匹配的所有位置，并將它們保存在二維數(shù)組中，直到搜索到模式的最后一個(gè)字符的可能匹配的位置。在向后搜索過(guò)程中，采用最左優(yōu)先策略，與前向搜索階段搜索順序相反，從最后一個(gè)字符開(kāi)始，對(duì)二維數(shù)組中的每個(gè)模式的可能匹配位置進(jìn)行選擇。

1.3 無(wú)重疊條件

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

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

2 發(fā)展趨勢(shì)

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

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

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

[2]吳信東，謝飛，黃詠明，胡學(xué)鋼，高雋.帶通配符和One-Off 條件的序列模式挖掘.軟件學(xué)報(bào)，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)和鍵盤(pán)進(jìn)行相應(yīng)的操作，通過(guò)鼠標(biāo)點(diǎn)觸鍵盤(pán)來(lái)實(shí)現(xiàn)對(duì)事件的監(jiān)聽(tīng)和加載代碼。在系統(tǒng)操作實(shí)現(xiàn)中，鼠標(biāo)所具有的功能是實(shí)現(xiàn)對(duì)鏡頭的有效縮放處理，在操作鼠標(biāo)的時(shí)候就能控制鏡頭的移動(dòng)。系統(tǒng)中網(wǎng)頁(yè)的名稱(chēng)主要包括mousemove、mousedown、mouseup等。事件在發(fā)生的時(shí)候需要判斷鼠標(biāo)的具體操作，從而加強(qiáng)對(duì)鏡頭的操作控制。

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

4 3D可視交互平臺(tái)設(shè)計(jì)性能分析

4.1 跨瀏覽器的測(cè)試

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn):

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

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