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

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

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

3、性的模式、模體等;這些種類的模式將有助于開發(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ù)。序列模式挖掘的過程即在序列數(shù)據(jù)庫中提取頻繁子序列。這項工作也更加吸引數(shù)據(jù)挖掘研究的研究人員的注意，并有許多關(guān)于挖

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

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

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

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

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

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

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

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

12、nX(Y))，包含Y序列但不包含X的序列(n(X)Y)。如果我們知道n，nX，nY和nXY。在這些方程中計算評估值得其他項目可以很容易被表示為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是一個規(guī)則的

13、自信度，并且imv=Sup(X, Y)/ Sup(X)。一個序列規(guī)則可通過將序列分成兩部分來創(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)測量值是r的置信度Conf(r)。也就是說，Conf(r)=Sup(p

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

15、項集擴展的節(jié)點集的大小不改變，根節(jié)點的大小是基于擴展項集的定義，那么序列規(guī)則不是從這個項目集擴展的節(jié)點集形成的。子樹的節(jié)點是根節(jié)點的序列擴展節(jié)點，子樹序列的序列規(guī)則是調(diào)用程序GENERATE_SR_FROM_SUBTREE而形成的，因為上面的根序列記為pre會形成從根的序列擴展節(jié)點擴展的所有序列的前綴。因此，對于每個子樹中，子樹序列的序列規(guī)則根據(jù)前綴pre而形成?，F(xiàn)有的根節(jié)點的所有擴展節(jié)點由此成為下一級子樹的前綴，這個過程被每個根節(jié)點的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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