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

◆苗雪連

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

◆苗雪連

（河北工業大學計算機科學與軟件學院 天津 300401）

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

間隙約束序列挖掘；算法

0 前言

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

1 具有間隙約束的序列挖掘的分類及研究現狀

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

（1）一次性條件。一次性條件的間隙約束序列模式挖掘對具有間隙約束的序列模式挖掘的出現提出了要求，即模式在序列中的任意兩次出現都不共享序列中同一位置的字符。

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

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

下面對這三種形式的相關研究進行了簡要的介紹。

1.1 無特殊條件

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

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

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

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

1.2 一次性條件

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

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

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

1.3 無重疊條件

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

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

2 發展趨勢

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

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

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

[2]吳信東，謝飛，黃詠明，胡學鋼，高雋.帶通配符和One-Off 條件的序列模式挖掘.軟件學報，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文件中的頂點相關參數

3 3D可視化中人機交互的實現

基于WebGL的交互主要是借助鼠標和鍵盤進行相應的操作，通過鼠標點觸鍵盤來實現對事件的監聽和加載代碼。在系統操作實現中，鼠標所具有的功能是實現對鏡頭的有效縮放處理，在操作鼠標的時候就能控制鏡頭的移動。系統中網頁的名稱主要包括mousemove、mousedown、mouseup等。事件在發生的時候需要判斷鼠標的具體操作，從而加強對鏡頭的操作控制。

網頁中的鍵盤事件主要有keydown和keyup兩種，在系統平臺中鍵盤操作能夠對模型的具體移動進行操控，具體按鍵是W鍵和S鍵，觸發函數參數是HTML5標準中的全局變量event，其通過對按鍵的ACSII碼判斷能夠執行相應的指令。

4 3D可視交互平臺設計性能分析

4.1 跨瀏覽器的測試

在測試中將基于網絡安全數據構建的三維可視模型直接運行在三大主流瀏覽器中。結果顯示，可視模型能夠實現無插件穩定運行。

4.2 基于WebGL技術模型載入時間測試

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

5 結束語

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

參考文獻:

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

[2]汪浩，田豐，張文俊.基于WebGL的交互平臺設計與實現[J].電子測量技術，2015.