基于前綴樹(shù)結(jié)構(gòu)的序列模式挖掘算法研究(英文版).pdf

1、隨著計(jì)算機(jī)和因特網(wǎng)技術(shù)的迅猛發(fā)展，從各種各樣應(yīng)用中收集到的數(shù)據(jù)量越來(lái)越龐大，若不采用有效工具挖掘需要信息，這些海量數(shù)據(jù)信息將超出人類的理解范疇。長(zhǎng)此以往將演變?yōu)閿?shù)據(jù)量大而有效信息卻貧乏的形勢(shì)。因此，從海量數(shù)據(jù)中挖掘出有價(jià)值的信息和所需要的知識(shí)已經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域中的重要任務(wù)之一。數(shù)據(jù)的多樣性和豐富性已經(jīng)形成不同的數(shù)據(jù)種類，其中包括事務(wù)數(shù)據(jù)、序列數(shù)據(jù)、流數(shù)據(jù)、時(shí)間序列數(shù)據(jù)等。
　　 序列數(shù)據(jù)是數(shù)據(jù)的一種重要類型，其被廣泛運(yùn)用在

2、科學(xué)與工程學(xué)、商業(yè)、客戶行為分析、股票趨勢(shì)預(yù)測(cè)、DNA序列分析、web使用行為分析及其他的一些實(shí)際應(yīng)用中。它由具有有序元素或事件的序列組成，并且列出或沒(méi)有列出特定時(shí)間概念。盡管對(duì)于其他種類的數(shù)據(jù)已經(jīng)存在大量通用的數(shù)據(jù)挖掘方法，但對(duì)于序列數(shù)據(jù)，這些方法不能被應(yīng)用。因?yàn)樵谒蓄愋偷臄?shù)據(jù)中，序列數(shù)據(jù)有其自身獨(dú)特的序列特征，并且可以應(yīng)用于許多有趣的應(yīng)用程序中，這使得發(fā)現(xiàn)了許多新的有趣種類的知識(shí)，包括序列模式、相似生物序列模式、部分有序模式、周期

3、性的模式、模體等;這些種類的模式將有助于開(kāi)發(fā)新的分類、聚類和異常值分析方法，這需要新的不同種類應(yīng)用程序的發(fā)展。
　　 序列模式挖掘是數(shù)據(jù)挖掘研究的重要任務(wù)之一，并且被普遍使用到序列數(shù)據(jù)挖掘應(yīng)用程序中。它在挖掘關(guān)聯(lián)，相關(guān)分析和許多其他有趣的數(shù)據(jù)之間的關(guān)系起著根本性的作用。此外，它提供數(shù)據(jù)分類，聚類，和其他的數(shù)據(jù)挖掘任務(wù)。序列模式挖掘的過(guò)程即在序列數(shù)據(jù)庫(kù)中提取頻繁子序列。這項(xiàng)工作也更加吸引數(shù)據(jù)挖掘研究的研究人員的注意，并有許多關(guān)于挖

4、掘序列模式的研究作品被審查。然而，面臨的主要挑戰(zhàn)仍然以大的搜索空間和無(wú)效處理稠密數(shù)據(jù)集的方式存在。例如，當(dāng)挖掘包含組合數(shù)的頻繁序列的長(zhǎng)頻繁序列，長(zhǎng)模式挖掘過(guò)程中會(huì)產(chǎn)生大量頻繁子序列，或當(dāng)使用非常低的支持度閾值來(lái)挖掘序列模式時(shí)，這在時(shí)間和空間成本上都是十分昂貴的。因此，序列模式挖掘算法的性能通常會(huì)出乎意料地被降低。要解決上述挑戰(zhàn)，挖掘序列規(guī)則，閉序列模式，以及順序生成模式的問(wèn)題已經(jīng)被提出。
　　 前綴樹(shù)是一個(gè)有序的樹(shù)數(shù)據(jù)結(jié)構(gòu)，用于

5、存儲(chǔ)序列的快速查找，其中父節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)都有一個(gè)與該節(jié)點(diǎn)相關(guān)的序列的共同的前綴，而根節(jié)點(diǎn)與空序列有關(guān)聯(lián)。其最簡(jiǎn)單的形式中通?？梢允褂玫年P(guān)鍵字的列表或字典。構(gòu)建前綴樹(shù)的過(guò)程是，建立序列之間父節(jié)點(diǎn)與孩子節(jié)點(diǎn)間直接關(guān)系，共同幫助開(kāi)采過(guò)程中采取更快、更直觀的方法，其中前綴樹(shù)從根節(jié)點(diǎn)具有空序列的0層開(kāi)始。每個(gè)子節(jié)點(diǎn)在1層存儲(chǔ)一個(gè)序列模式，每個(gè)節(jié)點(diǎn)在k層都是一個(gè)單一的項(xiàng)目集;每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)k模式序列。遞歸地，繼一個(gè)k模式序列后還有下一級(jí)(k+

6、1)以單個(gè)項(xiàng)目延深。有兩種方法可以擴(kuò)展一個(gè)k-模式序列，即序列擴(kuò)展項(xiàng)集延伸。在序列擴(kuò)展中，表示為◇s，(I)是在最終以字典順序排序的項(xiàng)目集中大于其中所有其他項(xiàng)目的項(xiàng)目，其中單一的項(xiàng)目被添加到k-模式序列最后的項(xiàng)目集作為一個(gè)新的項(xiàng)集，增加序列的大小。一個(gè)序列α是α所有序列擴(kuò)展序列的一個(gè)前綴，α是α中擴(kuò)展序列節(jié)點(diǎn)的所有子節(jié)點(diǎn)的前綴。在項(xiàng)集擴(kuò)展表示◇s，擴(kuò)展的項(xiàng)集序列的大小沒(méi)有改變。α是α中擴(kuò)展項(xiàng)集節(jié)點(diǎn)的所有子節(jié)點(diǎn)的一個(gè)不完全前綴。項(xiàng)目集擴(kuò)展

7、表示為◇i，擴(kuò)展的項(xiàng)目集序列的大小不會(huì)改變，α是一個(gè)在α中擴(kuò)展項(xiàng)目集節(jié)點(diǎn)的所有子節(jié)點(diǎn)的不完整前綴。
　　 關(guān)于前綴樹(shù)的節(jié)點(diǎn)序列常以字典字母順序出現(xiàn)，所以他們采用深度優(yōu)先搜索方式?；谇熬Y樹(shù)，我們遵守的規(guī)則基于深度優(yōu)先搜索如下:
　　 i.如果序列β'=β◇θ，那么β＜β'，所以我們需要首先搜索前綴，然后搜索序列。例如，給出序列〈(AB)〉，我們首先搜索〈A〉，然后搜索〈AB)〉。如果序列β=α◇sθ和β'=α◇iθ，然后

8、β＜β'，所以我們需要首先搜索序列擴(kuò)展，然后搜索項(xiàng)集擴(kuò)展。例如，給出序列〈(A)(B)〉and〈(AB)〉，首先搜索〈(A)(B)〉，然后搜索〈(AB)〉。
　　 ii.如果β=α◇θ并且β'=α◇θ'，θ＜θ'意味著β＜β'，然后兩個(gè)序列β和β'有相同的前綴，所以基于后綴的字母順序搜索他們。例如，給出一個(gè)序列〈(A)(A)〉和〈(A)(B)〉，我們首先搜索〈(A)(A)〉然后搜索〈(A)(B)〉。
　　 在本文中，我們

9、提出了新的算法以如下兩個(gè)主要目標(biāo)來(lái)解決這些問(wèn)題。
　　 二級(jí)信息如基于相應(yīng)前綴樹(shù)結(jié)構(gòu)的序列模式，閉序列模式，序列生成模式的開(kāi)發(fā)。
　　 在前綴樹(shù)結(jié)構(gòu)中，基于二級(jí)信息生成多種序列規(guī)則。
　　 在這篇論文中，我們做出的四項(xiàng)主要貢獻(xiàn)可以簡(jiǎn)要描述如下:
　　 第一，我們也提出一個(gè)有效的算法，采用從存儲(chǔ)了整個(gè)序列模式的前綴樹(shù)獲得的以上趣味性措施來(lái)生成所有相關(guān)順序的規(guī)則，序列模式的每個(gè)子節(jié)點(diǎn)存儲(chǔ)序列模式及其相應(yīng)的支持

10、值。通過(guò)遍歷前綴樹(shù)，該算法可以很容易地識(shí)別一個(gè)規(guī)則的組成部分，并且可以計(jì)算出測(cè)量值的規(guī)則。本文中我們提到了像Lift，Conviction，Piatetsky-Shapiro，Cosine，Jaccard等幾個(gè)興趣度，這些規(guī)則的提出是為了挖掘關(guān)聯(lián)規(guī)則和分類規(guī)則，但他們并沒(méi)有被應(yīng)用到序列數(shù)據(jù)庫(kù)挖掘序列規(guī)則，除了傳統(tǒng)措施的規(guī)則如支持度和置信度。
　　 在數(shù)據(jù)挖掘研究中挖掘序列規(guī)則是一個(gè)重要問(wèn)題。已經(jīng)提出了通過(guò)應(yīng)用規(guī)則的興趣度度量決策

11、相關(guān)的知識(shí)和去除虛假模式。興趣度規(guī)則在挖掘數(shù)據(jù)研究中是重要的規(guī)則挖掘指標(biāo)。它們可以用來(lái)減少搜索空間的大小，從而提高了挖掘效率，或根據(jù)它們的興趣度值的安排的排列模式。此外，在從發(fā)現(xiàn)規(guī)則集中選擇有用或有趣的規(guī)則的過(guò)程中，他們起著至關(guān)重要的作用。
　　 經(jīng)常用來(lái)計(jì)算規(guī)則X(→)Y的測(cè)量值的術(shù)語(yǔ)，是序列數(shù)據(jù)庫(kù)中的序列的總數(shù)(n)，包含X的序列數(shù)(nX)，包含Y的序列數(shù)(nY)，同時(shí)包含X和Y的序列數(shù)(nXY)，包含X但不包含Y的序列數(shù)(

12、nX(Y))，包含Y序列但不包含X的序列(n(X)Y)。如果我們知道n，nX，nY和nXY。在這些方程中計(jì)算評(píng)估值得其他項(xiàng)目可以很容易被表示為nX(Y)=nX-nXY，n(X)Y=nY-nXY，n(X)=n-nX和n(Y)=n-nY。
　　 形成了一種序列規(guī)則X(→)Y(q，imv)，其中X和Y是序列模式，X(∩) Y=(φ)，q是規(guī)則(q=Sup(X, Y))的支撐，imv是規(guī)則的興趣度值。在傳統(tǒng)的序列規(guī)則，imv是一個(gè)規(guī)則的

13、自信度，并且imv=Sup(X, Y)/ Sup(X)。一個(gè)序列規(guī)則可通過(guò)將序列分成兩部分來(lái)創(chuàng)建:前綴(pre)和后綴(post)的順序模式。如果pre與post串聯(lián)，表示為pre++post，那么結(jié)果是初始的序列模式。序列規(guī)則r由此可以形成pre(→)post(Sup，imv)。r的支持Sup(r)因此為Sup(pre++post)。r值的趣味性措施imv，r的傳統(tǒng)測(cè)量值是r的置信度Conf(r)。也就是說(shuō)，Conf(r)=Sup(p

14、re++post)/Sup(pre)。
　　 以前綴樹(shù)興趣度度量挖掘序列規(guī)則的算法可被詳細(xì)描述如下:它首先調(diào)用PRISM算法生成前綴樹(shù)結(jié)構(gòu)中所有的序列模式，這些模式和存儲(chǔ)。對(duì)于每個(gè)節(jié)點(diǎn) SP在1級(jí)的前綴樹(shù)，它調(diào)用 GENERATE_SR_FROM_TREE_ROOT程序生成序列規(guī)則，從每個(gè)子樹(shù)與SP作為根節(jié)點(diǎn)。當(dāng)過(guò)程GENERATE_SR_FROM_TREE_ROOT中被處理時(shí)，有兩種類型的節(jié)點(diǎn):序列擴(kuò)展節(jié)點(diǎn)和項(xiàng)集擴(kuò)展節(jié)點(diǎn)。由于

15、項(xiàng)集擴(kuò)展的節(jié)點(diǎn)集的大小不改變，根節(jié)點(diǎn)的大小是基于擴(kuò)展項(xiàng)集的定義，那么序列規(guī)則不是從這個(gè)項(xiàng)目集擴(kuò)展的節(jié)點(diǎn)集形成的。子樹(shù)的節(jié)點(diǎn)是根節(jié)點(diǎn)的序列擴(kuò)展節(jié)點(diǎn)，子樹(shù)序列的序列規(guī)則是調(diào)用程序GENERATE_SR_FROM_SUBTREE而形成的，因?yàn)樯厦娴母蛄杏洖閜re會(huì)形成從根的序列擴(kuò)展節(jié)點(diǎn)擴(kuò)展的所有序列的前綴。因此，對(duì)于每個(gè)子樹(shù)中，子樹(shù)序列的序列規(guī)則根據(jù)前綴pre而形成?，F(xiàn)有的根節(jié)點(diǎn)的所有擴(kuò)展節(jié)點(diǎn)由此成為下一級(jí)子樹(shù)的前綴，這個(gè)過(guò)程被每個(gè)根節(jié)點(diǎn)的

16、擴(kuò)展節(jié)點(diǎn)遞歸地調(diào)用。此遞歸過(guò)程反復(fù)進(jìn)行，直至達(dá)到最后一級(jí)的前綴樹(shù)。此外，在程序GENERATE_SR_FROM_SUBTREE中，輸入是序列pre預(yù)和子樹(shù)，因而pre是子樹(shù)所有序列的一個(gè)共有前綴。子樹(shù)中的每個(gè)序列SP，規(guī)則“pre(→)post”形成，由此post是SP的一個(gè)關(guān)于pre前綴的前綴。
　　 一個(gè)規(guī)則的大多數(shù)有趣的方法依賴于Post的支持，為了獲得Post的支持，程序FIND_SUP_POST(RNode，Post)

17、被調(diào)用，RNode是Post的前綴樹(shù)中的第一個(gè)根節(jié)點(diǎn)并且為非空。FIND_SUP_POST程序(RNode，Post)產(chǎn)生Post的支持通過(guò)遍歷以RNode為根節(jié)點(diǎn)的前綴樹(shù)的所有分支，Rnode為Post的前綴。
　　 實(shí)驗(yàn)結(jié)果表明，使用這種基于前綴樹(shù)并結(jié)合趣味性標(biāo)準(zhǔn)的序列規(guī)則挖掘算法，比使用其他現(xiàn)有的改進(jìn)算法更快，特別是用最小支持度去挖掘大型序列數(shù)據(jù)庫(kù)時(shí)，從序列數(shù)據(jù)庫(kù)中產(chǎn)生序列模型的數(shù)量是非常巨大。并且該算法比那些只通過(guò)前綴樹(shù)

18、立即去確定一個(gè)序列是左邊還是右邊規(guī)則的算法，并且他們的支持度值從序列模式集中計(jì)算興趣度值的規(guī)則。
　　 第二，本文中，序列生成器模式的特征是結(jié)合前綴樹(shù)的擴(kuò)展序列提出了兩種高效的算法，命名為MSGPs和MSGP_PreTre，這兩種算法在產(chǎn)生序列模式的同時(shí)挖掘出所有的序列生成器模式。使用前綴樹(shù)，通過(guò)附加到最后位置的一個(gè)父節(jié)點(diǎn)作為項(xiàng)集合的擴(kuò)展或通過(guò)序列擴(kuò)展，作為子節(jié)點(diǎn)集的新序列可以很容易的創(chuàng)建。該方法使用了主模塊編碼方法來(lái)表示候選序

19、列，并且通過(guò)在主模塊使用聯(lián)合操作來(lái)判斷每個(gè)候選序列的頻率。在MSGPs算法中，為了能快速檢查，它使用了一個(gè)帶有哈希秘鑰的哈希表來(lái)存儲(chǔ)序列生成模式作為模式的支持度。
　　 MSGPs算法中輸入?yún)?shù)是一個(gè)序列數(shù)據(jù)庫(kù)(SD)和最小支持度，輸出是一組序列生成器模式(SGPs)。為了能快速檢索，使用哈希表存儲(chǔ)模式。首先，該算法遍歷序列數(shù)據(jù)庫(kù)一次，找到所有頻率為1的模式并存儲(chǔ)到dbpat。每個(gè)出現(xiàn)頻率為1模式序列作為一個(gè)序列生成器模式增加到

20、SGPs，對(duì)于每個(gè)在數(shù)據(jù)集dbpat中的模式，EXTEND_TREE通過(guò)在前綴樹(shù)中使用深度優(yōu)先搜素去擴(kuò)充對(duì)應(yīng)的前綴樹(shù)。算法然后返回SGPs中所有的序列生成器模式。擴(kuò)充樹(shù)種每個(gè)根節(jié)點(diǎn)有兩個(gè)擴(kuò)充類型，項(xiàng)目集擴(kuò)展和序列擴(kuò)展，EXTEND_ITEMSET和EXTEND_SEQ UENCE各自擴(kuò)充了樹(shù)?；谛再|(zhì)4.3，算法然后調(diào)用EXTEND_TREE通過(guò)擴(kuò)充根節(jié)點(diǎn)集繼續(xù)擴(kuò)充樹(shù)，這樣可以減少搜索空間，算法僅擴(kuò)充序列生成器中的節(jié)點(diǎn)。EXTEND_I

21、TEMSET通過(guò)在數(shù)據(jù)集dbpat中附加沒(méi)一項(xiàng)來(lái)增加新節(jié)點(diǎn)集，其中每一項(xiàng)必須大于最后一個(gè)項(xiàng)目在最近項(xiàng)目集的擴(kuò)展節(jié)點(diǎn)和到最后的項(xiàng)目集的擴(kuò)展節(jié)點(diǎn)。使用基于棱柱分解的塊編碼來(lái)創(chuàng)建一個(gè)新的模式和計(jì)算其支持度。如果新模式Pnew是序列模式并且Pnew的支持度和擴(kuò)充節(jié)點(diǎn)相等，則Pnew不是生成模式。否則，調(diào)用CHECK GENERATOR檢查Pnew是否是生成器，然后將Pnew添加到擴(kuò)充節(jié)點(diǎn)的項(xiàng)擴(kuò)充集里。
　　 EXTEND_SEQUENC

22、E通過(guò)增加dbpat中每一項(xiàng)到擴(kuò)充節(jié)點(diǎn)的最后位置來(lái)創(chuàng)建新模式Pnew。每一個(gè)添加的項(xiàng)目新節(jié)點(diǎn)Pnew最近的項(xiàng)集。如果Pnew的支持度與擴(kuò)展節(jié)點(diǎn)相同，則Pnew是一個(gè)非生成模式。否則，調(diào)用CHECK GENERATOR去確認(rèn)Pnew是否是一個(gè)生成器模式，然后增加Pnew到擴(kuò)充節(jié)點(diǎn)的擴(kuò)充序列。在CHECK_GENERATOR中，如果Pnew是P的子序列，P是非生成模式，則P可以被Pnew取代，如果Pnew是P的超序列，并且Pnew是一個(gè)非生

23、成模式，如果Pnew不存在SGPs中，則它可以被插入到生成模式集合中。在生成序列生成器模式的算法中，MSGP_PreTree算法是另一個(gè)改進(jìn)了MSGPs算法的有效算法。改進(jìn)算法的思想是通過(guò)修改前綴樹(shù)，前綴樹(shù)的每個(gè)節(jié)點(diǎn)將被添加字段，確實(shí)存儲(chǔ)在這個(gè)節(jié)點(diǎn)上的序列是否是一個(gè)序列生成器。整個(gè)序列的信息存儲(chǔ)在前綴樹(shù)，所以MSGP_PreTree算法不需要使用哈希表來(lái)存儲(chǔ)序列生成器模式。基于頻率的超序列和前綴樹(shù)的非生成樹(shù)的刪減應(yīng)用在MSGP_PreT

24、ree算法來(lái)減少搜索空間。
　　 為了生成所有的序列生成模式，MSGP_PreTree算法在MSGPs算法的基礎(chǔ)上進(jìn)行了改進(jìn)。改進(jìn)算法的想法是通過(guò)修改前綴樹(shù)執(zhí)行的，例如前綴樹(shù)中的每個(gè)頂點(diǎn)將會(huì)添加字段來(lái)檢查儲(chǔ)存在這個(gè)點(diǎn)中的這個(gè)序列是否是一個(gè)序列生成模式。這個(gè)序列的所有信息都被儲(chǔ)存在前綴樹(shù)中，所以MSGP_PreTree算法不需要跟哈希表來(lái)儲(chǔ)存序列生成模式，這樣會(huì)大大減少內(nèi)存的使用。超層序在前綴樹(shù)中基于頻繁的剪支和基于非生成器的剪支

25、被應(yīng)用在MSGP_PreTree算法中來(lái)減少所有空間。擴(kuò)展前綴樹(shù)和在MSGP_PreTree算法中決策序列模式的過(guò)程，與MSGP算法是相似的。
　　 MSGP_PreTree算法也初始化pretree樹(shù)，把根節(jié)點(diǎn)設(shè)為空，遍歷SD一次找出所有頻率為1的模式并且將其存儲(chǔ)在SPs中。每個(gè)SPs中的頻率模式作為一個(gè)根節(jié)點(diǎn)被插入到pretree。對(duì)于每一個(gè)頻率為1的模式序列是一個(gè)序列生成模式，所以在pretree中所有序列為1的模式序列被

26、設(shè)置作為一個(gè)生成器。對(duì)于Pretree的每個(gè)節(jié)點(diǎn)，算法通過(guò)調(diào)用EXTEND_TREE去擴(kuò)展相應(yīng)的前綴樹(shù)。算法返回的pretree包含所有的SGPs。在EXTEND_TREE,每根節(jié)點(diǎn)有兩個(gè)擴(kuò)展類型，項(xiàng)目集擴(kuò)展和序列擴(kuò)展，對(duì)應(yīng)的擴(kuò)展過(guò)程分別是EXTEND_ITEMSET和EXTEND_SEQUENCE。對(duì)于根節(jié)點(diǎn)的每個(gè)擴(kuò)充節(jié)點(diǎn)集，算法調(diào)用EXTEND_TREE繼續(xù)擴(kuò)展樹(shù)。對(duì)于擴(kuò)充節(jié)點(diǎn)中的項(xiàng)目集中的每個(gè)節(jié)點(diǎn)，刪減搜索空間保證算法僅遍歷生成模

27、式的節(jié)點(diǎn)。EXTEND_ITEMSET通過(guò)在SPs中增加項(xiàng)來(lái)創(chuàng)建新節(jié)點(diǎn)，其中增加的項(xiàng)必須大于擴(kuò)從節(jié)點(diǎn)最后一個(gè)項(xiàng)集的最后一項(xiàng)。算法使用基于棱鏡分解的塊編碼來(lái)創(chuàng)建一個(gè)新的模式并計(jì)算支持度。如果Pnew的支持度等于擴(kuò)充節(jié)點(diǎn)，則Pnew是非擴(kuò)充集，否則調(diào)用CHECK_GENERATOR確認(rèn)Pnew是否是生成器，然后Pnew作為擴(kuò)充節(jié)點(diǎn)的孩子節(jié)點(diǎn)的擴(kuò)充項(xiàng)增加到pretree。EXTEND_SEQUENCE通過(guò)在dbpat增加每一項(xiàng)到擴(kuò)充節(jié)點(diǎn)的最后

28、位置來(lái)創(chuàng)建新模式Pnew。每一個(gè)添加的項(xiàng)目新節(jié)點(diǎn)Pnew最近的項(xiàng)集。如果Pnew的支持度與擴(kuò)展節(jié)點(diǎn)相同，則Pnew是一個(gè)非生成模式。否則，調(diào)用CHECK_GENERATOR去確認(rèn)Pnew是否是一個(gè)生成器模式，然后增加Pnew到擴(kuò)充節(jié)點(diǎn)的擴(kuò)充序列。在CHECK_GENERATOR中，遍歷pretree確認(rèn)是否存在Pnew的子序列或者超序列是生成器。對(duì)于在pretree中有和Pnew一樣支持度的模體，如果Pnew是P的子序列，P是非生成模式

29、集，Pnew是生成模式集;如果Pnew是P的超序列，則Pnew是非生成器模式。
　　 對(duì)于合成的和真實(shí)的數(shù)據(jù)庫(kù)，所有的實(shí)驗(yàn)結(jié)果表明序列生成器模式的數(shù)量總是小于序列模式的數(shù)量，并且在所有情況中這種算法就運(yùn)行時(shí)間來(lái)說(shuō)是勝過(guò)其他算法的。
　　 第三，我們提出了一種高效的算法，在生成序列模式的過(guò)程中，直接來(lái)發(fā)現(xiàn)閉合序列模式和他們的序列生成器模式，稱為CloGen算法(Closedsequential pattern-sequen

30、tial Generator pattern)，該算法是基于結(jié)合前綴樹(shù)結(jié)構(gòu)的父子節(jié)點(diǎn)關(guān)系和閉合序列模式以及序列生成器模式的定義。CSGM(閉合序列和序列生成器挖掘)算法是2010年Zang等人首先提出的，算法同時(shí)挖掘頻繁閉合序列和序列生成器模式。使用CSGM算法，通過(guò)遍歷序列數(shù)據(jù)庫(kù)一次就能產(chǎn)生序列生成器和閉合序列生成器模式，減少了時(shí)間復(fù)雜度。但是，集合構(gòu)建對(duì)象數(shù)據(jù)庫(kù)的時(shí)間復(fù)雜度很高。論文提出了一個(gè)高效的算法能直接發(fā)現(xiàn)閉合序列和序列生成器

31、模式，在生成序列模式的過(guò)程中調(diào)用CloGen算法，該算法是基于結(jié)合前綴樹(shù)中的父子節(jié)點(diǎn)關(guān)系和閉合序列模式及序列生成器模式。
　　 在我們的方法中，前綴樹(shù)上的每個(gè)節(jié)點(diǎn)存儲(chǔ)了一個(gè)序列模式和它相對(duì)應(yīng)的支持度值。此外，它會(huì)被添加一個(gè)字段(IsmSGP)來(lái)決策該節(jié)點(diǎn)是否是最小的序列生成模式，并且另一個(gè)字段(IsCSP)用來(lái)決策該節(jié)點(diǎn)是否是一個(gè)閉合序列模式。根據(jù)添加到節(jié)點(diǎn)上的這些字段，算法很容易判斷每個(gè)節(jié)點(diǎn)上的序列是最小生成器序列還是閉合序列

32、模式，所以算法的時(shí)間復(fù)雜度明顯減少了。算法同時(shí)也在素因子分解的主模塊編碼方法上使用了聯(lián)合操作來(lái)代表候選序列并且判定每個(gè)候選序列的頻率。
　　 算法描述如下:首先，初始化前綴樹(shù)pretree，根節(jié)點(diǎn)是空節(jié)點(diǎn)設(shè)置為空，孩子節(jié)點(diǎn)序列模式為1設(shè)置IsmSGP和IsCSP為true。每個(gè)前綴樹(shù)的孩子節(jié)點(diǎn)作為根節(jié)點(diǎn)，使用EXTENND_TREE算法創(chuàng)建孩子節(jié)點(diǎn)并且擴(kuò)充前綴樹(shù)。在函數(shù)中，每個(gè)根節(jié)點(diǎn)P的孩子節(jié)點(diǎn)是由項(xiàng)擴(kuò)充或序列擴(kuò)充創(chuàng)建的。為找出

33、候選序列和決定每個(gè)序列的頻率，使用主模塊編碼方法和合并主模塊。因?yàn)槊恳粋€(gè)新創(chuàng)建的子節(jié)點(diǎn)Pnew被分配｛IsmSGP,IsCSP｝=｛true，true｝，如果Sup(Pnew)=Sup(P)，Pnew.IsmSGP和P.IsCSP將被設(shè)置為false。調(diào)用UPDATE_PRETREE(Pnew，pretree)更新閉序列模式和前綴樹(shù)的序列生成器模式。最后，算法返回對(duì)應(yīng)的前綴樹(shù)。
　　 實(shí)驗(yàn)結(jié)果表明挖掘閉序列模式的運(yùn)行時(shí)間和它們使

34、用CloGen算法的最小序列生成器模型提高了一個(gè)數(shù)量級(jí)。CloGen算法可以同時(shí)生成所有的序列模式，序列生成器模式，和閉合序列模式。此外，對(duì)于挖掘非冗余序列規(guī)則以及挖掘所有序列規(guī)則，我們方法中構(gòu)建的前綴樹(shù)將會(huì)在未來(lái)成為最有效前綴樹(shù)方法之一。
　　 第四，本論文提出了一個(gè)高效的MNSR-Pretree算法來(lái)挖掘非冗余序列規(guī)則。這個(gè)算法分為兩個(gè)階段。第一階段，它從一個(gè)給定的序列數(shù)據(jù)庫(kù)中構(gòu)建了一個(gè)前綴樹(shù)，存儲(chǔ)所有的序列模式。在第二階段

35、，它從這個(gè)前綴樹(shù)中挖掘非冗余序列規(guī)則。在前綴樹(shù)的構(gòu)建過(guò)程中，前綴樹(shù)中的每個(gè)節(jié)點(diǎn)都有有一個(gè)字段(IsmSGP)來(lái)表示該節(jié)點(diǎn)是否是最小的序列生成模式，另外一字段(IsCSP)來(lái)表示該節(jié)點(diǎn)是否是一個(gè)閉序列模式。通過(guò)遍歷這個(gè)前綴樹(shù)，非冗余序列規(guī)則可以很容易從最小序列生成器模式X到閉序列Y中挖掘到，因?yàn)閄是Y的前綴樹(shù)，這樣可以很大程度地減少挖掘所需的時(shí)間。基于IsmSGP和IsCSP值，當(dāng)父節(jié)點(diǎn)的IsmSGP值對(duì)于子節(jié)點(diǎn)IsCSP為真是正確的時(shí)，

36、算法才挖掘該規(guī)則。因此父節(jié)點(diǎn)的序列被認(rèn)為是先驗(yàn)規(guī)則，從閉序列模體中移除前綴部分，挖掘規(guī)則就會(huì)產(chǎn)生。MNSR-Pretree算法的輸入是前綴樹(shù)pretree和minConf。對(duì)于前綴樹(shù)深入為1的每個(gè)節(jié)點(diǎn)SP，算法調(diào)用GENERATE_NSR_FROM_ROOT(SP)從每個(gè)以SP作為根節(jié)點(diǎn)的子圖中產(chǎn)生非冗余序列規(guī)則。最終返回非冗余序列規(guī)則集NSR。有兩種不同類型的節(jié)點(diǎn):序列擴(kuò)種節(jié)點(diǎn)和項(xiàng)擴(kuò)充節(jié)點(diǎn)。根據(jù)項(xiàng)擴(kuò)充定義，項(xiàng)擴(kuò)充類型的孩子節(jié)點(diǎn)集的大小

37、不會(huì)改變根節(jié)點(diǎn)的規(guī)模。所以GENERATE_NSR_FROM_ROOT(SP)不會(huì)在項(xiàng)擴(kuò)充節(jié)點(diǎn)集中產(chǎn)生規(guī)則。在序列根節(jié)點(diǎn)的擴(kuò)充集中會(huì)產(chǎn)生規(guī)則。當(dāng)子集SP的根節(jié)點(diǎn)是最小序列生成器模式(IsSGP為true)。
　　 生成樹(shù)的非冗余序列準(zhǔn)則通過(guò)函數(shù)GENERATE_NSR(SP, Subtree)。生成函數(shù)GENERATE_NSR(SP, Subtree)的輸入包括子樹(shù)SP的根節(jié)點(diǎn)和子樹(shù)，其中子樹(shù)為最小序列生成器模式。子樹(shù)SP的根序

38、列，和所有字?jǐn)?shù)中的序列有相同的前綴。因此，Pre從根的序列擴(kuò)充節(jié)點(diǎn)構(gòu)成了所有擴(kuò)充序列的前綴。非冗余序列準(zhǔn)則從前綴樹(shù)的序列中產(chǎn)生。對(duì)于子樹(shù)種每個(gè)節(jié)點(diǎn)n，都是序列模式(n的IsCSP為true)。如果Conf≥minConf,則序列準(zhǔn)則SR:“Pre(→)Post”成立，其中post是節(jié)點(diǎn)n的后綴序列。所有本階段的根的擴(kuò)充節(jié)點(diǎn)將在下個(gè)節(jié)點(diǎn)變成字?jǐn)?shù)的前綴，每個(gè)根的擴(kuò)充節(jié)點(diǎn)遞歸調(diào)用這個(gè)函數(shù)。這個(gè)過(guò)程重復(fù)執(zhí)行直到前綴樹(shù)的最后一層到達(dá)。
　　

39、 合成數(shù)據(jù)和真實(shí)的數(shù)據(jù)庫(kù)的實(shí)驗(yàn)結(jié)果表明，序列生成器模式的數(shù)量遠(yuǎn)小于序列模式，而且本文提出的算法在運(yùn)行時(shí)間方面優(yōu)于其他算法。同時(shí)，結(jié)果也表明對(duì)于挖掘非冗余序列規(guī)則本文提出的算法在時(shí)間復(fù)雜度上是優(yōu)于現(xiàn)有算法的。
　　 綜上所述，在本文中我們已經(jīng)提出了有效的算法并且完成了最開(kāi)始提出的目標(biāo)——提高挖掘次級(jí)信息算法，如基于前綴樹(shù)結(jié)構(gòu)的序列模式、閉序列模式和序列生成器模式的有效性。主要的貢獻(xiàn)是前綴樹(shù)的使用，為了從次級(jí)信息中生成有效的各種序