基于投影數(shù)據(jù)挖掘算法研究與實(shí)現(xiàn)

1、灰曲理N號(hào)彷畢業(yè)論文（設(shè)計(jì)）題目基于投影數(shù)據(jù)挖掘算法研究與實(shí)現(xiàn)學(xué)生姓名郭凱學(xué)號(hào)041842020院（系）學(xué)系專(zhuān)業(yè)班級(jí)信息與計(jì)算科學(xué)043班指導(dǎo)教師痛流完成地點(diǎn)數(shù)學(xué)系數(shù)據(jù)挖掘?qū)嶒?yàn)室2008年6月9日基于投影數(shù)據(jù)挖掘算法研究與實(shí)現(xiàn)作者：郭凱（陜西理工學(xué)院數(shù)學(xué)系信息與計(jì)算科學(xué)專(zhuān)業(yè)043班陜西723001）指導(dǎo)教師：周濤摘要：序列模式的發(fā)現(xiàn)是數(shù)據(jù)挖掘領(lǐng)域一個(gè)活躍的研究分支，即在序列數(shù)據(jù)庫(kù)中找出所有的頻繁子序列.本文先介紹序列模式挖掘中的一些基本概念，然后詳細(xì)描述FreeSpan和PrefixSpan2個(gè)基于投影、分治的模式增長(zhǎng)的重要算法?；谕队胺椒葱蛄袛?shù)據(jù)庫(kù)先被投影為很多小投影數(shù)據(jù)庫(kù)，然后在小投影

2、數(shù)據(jù)庫(kù)中進(jìn)行遞歸挖掘的典型算法.其中FreeSpan算法是將數(shù)據(jù)庫(kù)分成若干個(gè)子空間，再每個(gè)子空間里進(jìn)行遞歸的的投影，對(duì)于每一個(gè)項(xiàng)及其與前一項(xiàng)組合成的序列模式進(jìn)行投影挖掘，最終得出頻繁子序列。PrefixSpan算法則是先找出長(zhǎng)度為1的序列模式，以此序列模式為前綴的投影，并在投影數(shù)據(jù)庫(kù)里面繼續(xù)遞歸的進(jìn)行投影，最終得出頻繁子序列。本文并以實(shí)例解析，更為詳細(xì)清楚的描述了兩種算法的過(guò)程。關(guān)鍵詞:數(shù)據(jù)挖掘；FreeSpan算法；PrefixSpan算法;AccordingtocastshadowadatatoscoopoutcalculatewayresearchAuthor:GuoKai(Grade0

3、4,Class03,Informationandcalculationscience,DepartmentofMathematics,ShaanxiUniversityofTechnology,Hanzhong723000,Shaanxi)tutor:ZhouTaoAbstractSequencemodedataminingisthediscoveryofanactiveareaofresearchbranch,thatis,allsequencesinthedatabasetoidentifythefrequencyofsequence.Inthispaper,firstintroduced

4、inthesequencepatternminingsomeofthebasicconcepts,andthendescribedindetailFreeSpanandPrefixSpan2basedprojection,thepartitionoftheimportantgrowthpatternalgorithm.Basedontheprojectionmethodthatsequencedatabasewasfirstprojectionforthemanysmallprojectiondatabase,andthenasmallprojectiondatabaseMiningtypic

5、alrecursivealgorithm.WhichFreeSpanalgorithmisdividedintoseveralsub-databasespace,theneachoftherecursivespacefortheprojector,andforeachandeveryitemwithacombinationof10%oftheformermodelprojectionexcavationsequence,thefinalsequenceofdrawnfrequent.ThePrefixSpancalculatewaythenfindoutthelengthasonesequen

6、cemodefirst,takethissequencemodeascastshadowofex-Zhui,andcontinuetopasstoreturnintheprojectionthedatabaseofcarryoncastshadow,endgetmultifarioussub-sequence.Analysisandexamplesinthispaper,amoredetaileddescriptionofthetwoclearlyalgorithmprocess.KeywordsThedatascoopout;FreeSpanarithmetic;PrefixSpanarit

7、hmetic;目錄一引言5二序列模式挖掘相關(guān)知識(shí)52.1 基本術(shù)語(yǔ)52.2 基本定義5三序列模式簡(jiǎn)介62.1 問(wèn)題描述錯(cuò)誤！未定義書(shū)簽。2.2 系統(tǒng)規(guī)定錯(cuò)誤！未定義書(shū)簽。四模式增長(zhǎng)方法61 freespan算法61.4 freespan算法的思想61.4 freespan算法執(zhí)行過(guò)程的描述錯(cuò)誤！未定義書(shū)簽。1.4 freespan算法的分析71 prefixspan算法71.5 prefixspan算法的提出71.5 prefixspan算法的思想及描述71.5 prefixspan算法的分析81.5 prefixspan算法的主要改進(jìn)81.5 prefixspan算法和Aporiori算法的

8、比較8五實(shí)例解析9I利用freespan算法解析錯(cuò)誤！未定義書(shū)簽。n利用PrefixSpan算法解析錯(cuò)誤！未定義書(shū)簽。六對(duì)prefixspan算法的VC®序的實(shí)現(xiàn)12(1) prefixspan算法的流程圖12(1) 算法的執(zhí)行結(jié)果13(1) 算法結(jié)果分析14七結(jié)論與展望15八致謝15九參考文獻(xiàn)16十附錄17序列模式挖掘是數(shù)據(jù)挖掘研究的一個(gè)重要課題，而且具有非常廣泛的應(yīng)用，被應(yīng)用在包括顧客購(gòu)買(mǎi)行為的分析、網(wǎng)絡(luò)訪(fǎng)問(wèn)模式分析、科學(xué)實(shí)驗(yàn)的分析、疾病治療的早期診斷、自然災(zāi)害的預(yù)測(cè)、DNA序列模式的分析等1.目前對(duì)序列模式挖掘問(wèn)題的研究主要集中在算法設(shè)計(jì)和實(shí)際應(yīng)用，在理論方面研究還很罕見(jiàn).序列

9、模式挖掘是對(duì)關(guān)聯(lián)規(guī)則挖掘的進(jìn)一步推廣，它挖掘出序列數(shù)據(jù)庫(kù)中項(xiàng)集間的時(shí)序關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究的一個(gè)重要內(nèi)容.早先的很多關(guān)聯(lián)規(guī)則挖掘研究都有助于挖掘序列模式或者與時(shí)間相關(guān)的頻繁模式.SRIKANTAGRAWAL序列規(guī)定了時(shí)間限制、滑動(dòng)時(shí)間窗口和用戶(hù)規(guī)定的分類(lèi)，并總結(jié)了序列模式的定義，提出一種基于Apriori的改進(jìn)算法GSP(generalizedsequentialpatterns)算法.以上這些都是基于Apriori的水平格式的序列模式挖掘或者與時(shí)間相關(guān)的頻繁模式挖掘.后來(lái)，ZAKI提出了一種基于垂直格式存儲(chǔ)的序列模式挖掘方法SPAD算法，該算法由基于垂直格式的頻繁項(xiàng)挖掘演化而來(lái).近幾年，H

10、AN人又提出一種基于投影的模式增長(zhǎng)算法Freespan(FrequentPattern-pojectedSequentialPatternMining)算法，該算法改進(jìn)后為Pre巾xSpan(Prefix-ProjectedSequentialPatternsMining)算法網(wǎng)，性能進(jìn)一步提高.MANNILA等人4提出的挖掘頻繁序列片段問(wèn)題，GAROFALAKI等人提出的基于規(guī)則表達(dá)式約束的序列模式挖掘，還有關(guān)于序列模式挖研究的一些擴(kuò)展，如序列模式閉項(xiàng)挖掘、并行挖掘、分布式挖掘、多維度序列模式挖掘和近似序列模式挖掘等，所有這些對(duì)后來(lái)研究序列模式挖掘都有一定的影響.本文重點(diǎn)對(duì)典型的序列模式挖掘

11、算法FreeSpan和PrefixSpan兩種典型算法進(jìn)行詳細(xì)的描述、分析和比較二、序列模式挖掘的相關(guān)知識(shí)基本術(shù)語(yǔ)設(shè)I=i1,i2,in是一個(gè)項(xiàng)目集合，項(xiàng)目集或者項(xiàng)集(items)就是各種項(xiàng)目組成的集合，即I的所有子集.一個(gè)序列就是若干項(xiàng)集的有序列表，一個(gè)序列S可表示為s1,s2,sn>,其中sj為項(xiàng)集，也稱(chēng)作S勺元素.元素由不同的項(xiàng)組成，可表示為(x1,x2,xn).當(dāng)元素只包含一項(xiàng)時(shí)，一般省去括號(hào)，如(x2)一般表示為x2.元素之間是有順序的，但元素內(nèi)的項(xiàng)是無(wú)序的，一般定義為詞典序.序列包含項(xiàng)的個(gè)數(shù)稱(chēng)為序列的長(zhǎng)度，長(zhǎng)度為L(zhǎng)的序列記為L(zhǎng)-序列.序列數(shù)據(jù)庫(kù)就是元組(tuples)sid,

12、s>的集合，其中s是序列，sid是該序列的序列號(hào)，元組的個(gè)數(shù)稱(chēng)為序列數(shù)據(jù)庫(kù)的大小，記作|SDB|.基本定義定義1序列模式：給定一個(gè)由不同序列組成的集合，其中，每個(gè)序列由不同的元素按順序有序排列，每個(gè)元素由不同項(xiàng)目組成，同時(shí)給定一個(gè)用戶(hù)指定的最小支持度閾值，序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中的出現(xiàn)頻率不低于用戶(hù)指定的最小支持度閾值定義2子序列和超序列：對(duì)于序列A=a1,a2,an>和B=b1,b2,bm>,當(dāng)且僅當(dāng)1Wj1<j2V,<jm<m且a1?j1,a2?j2,an?jn時(shí)，稱(chēng)序列B為序列A的超序列，序列A為序列B的子序列，又稱(chēng)序

13、列B包含序列A,記作A?B.例如在表1中a(abc)(cf)bd>這個(gè)序列，其中(abc)>,a(abc)(cf)>者B是a(abc)(cf)bd>的子序列，a(abc)(cf)bd>是(abc)>,a(abc)(cf)>的超序列.定義3支持?jǐn)?shù)：序列數(shù)據(jù)庫(kù)比元組sid,S>的集合，sid為序列標(biāo)識(shí)號(hào).如果序列T是S勺子序列(即T?S),稱(chēng)元組sid,S>包含序列T,則序列T在序列數(shù)據(jù)庫(kù)D43的支持?jǐn)?shù)是數(shù)據(jù)庫(kù)中包含T的元組數(shù)，即supportD(T)=|sid,S>|sid,S>CDAT?S|,記作support(T).定義4頻繁

14、序列模式：給定一個(gè)最小支持度閾值minsup,如果序列s的支持度不小于minsup,則稱(chēng)序列s為頻繁序列模式，所有的頻繁序列模式集合記作FS.例如在表1中(ac)>這個(gè)序列分別在10和40序列出現(xiàn)2次，所以其支持?jǐn)?shù)為2.假設(shè)用戶(hù)規(guī)定minsup為2,可知(ac)序列是頻繁序列模式.定義5前綴(Pre巾x):設(shè)每個(gè)元素中的所有項(xiàng)目按照字典序排列.給定序列“=<ele2,""en>,3=<el'e2',em'>(m<n),如果ei'=ei(i<m-1),em'?em,并且(em-em')中

15、的項(xiàng)目均在em'中項(xiàng)目的后面，則稱(chēng)3是a的前綴；定義6后綴(Suffix):序列a關(guān)于子序列3=<e1e2,em-1em'>的投影為J=<e1en>,其中enf=(eme2,en>(n>m),則序列a關(guān)于子序列3的后綴為<enVem+1,定義7投影：給定序列a和3,如果3是a的子序列，則a關(guān)于3的投影a'必須滿(mǎn)足:a'的前綴，a'是a的滿(mǎn)足上述條件的最大子序列.定定義8投影數(shù)據(jù)庫(kù)：設(shè)值為序列數(shù)據(jù)庫(kù)什的一個(gè)序列模式，則3的投影數(shù)據(jù)庫(kù)為S中所有以口為前綴的序列相對(duì)于a的后綴，記為S|o(.例：在表1中9>一投影

16、數(shù)據(jù)庫(kù)由3個(gè)后綴序列組成：<(abc)(cf)bd>,<bc(ce)>,<(_c)bg(cf)f>,<(ab)>投影數(shù)據(jù)庫(kù)<(_c)(cf)bd>.定義9投影數(shù)據(jù)庫(kù)中的支持?jǐn)?shù)：設(shè)”為序列數(shù)據(jù)庫(kù)S中的一個(gè)序列模式，序列3以a為前綴，則3在a的投影數(shù)據(jù)庫(kù)S|a中的支持?jǐn)?shù)為S|a中滿(mǎn)足條件3?a.丫的序列丫的個(gè)數(shù).表1序列數(shù)據(jù)庫(kù)Sid序列10a(abc)(cf)bd20eabc(ce)30cghd40(ac)bg(cf)f三、序列模式簡(jiǎn)介問(wèn)題描述：給定序列數(shù)據(jù)庫(kù)和最小支持度閾值，序列模式挖掘就是要找出序列數(shù)據(jù)庫(kù)中所有的序列模式.系統(tǒng)規(guī)定：由

17、于同一個(gè)元素中的項(xiàng)目之間排列沒(méi)有順序，為了表達(dá)的唯一性，我們將同一個(gè)元素內(nèi)部的不同項(xiàng)目按照字典順序排列四、模式增長(zhǎng)方法這類(lèi)算法是一種基于投影的、分治的模式增長(zhǎng)的方法，即序列數(shù)據(jù)庫(kù)先被投影為很多小投影數(shù)據(jù)庫(kù)，然后在小投影數(shù)據(jù)庫(kù)中進(jìn)行遞歸挖掘.1FreeSpan算法FreeSpan算法思想FreeSpan,即頻繁模式投影的序列模式挖掘，其基本思想為：利用頻繁項(xiàng)遞歸地將序列數(shù)據(jù)庫(kù)投影到更小的投影數(shù)據(jù)庫(kù)集中，在每個(gè)投影數(shù)據(jù)庫(kù)中生成子序列片段.這一過(guò)程對(duì)數(shù)據(jù)和待檢驗(yàn)陜西理工學(xué)院畢業(yè)設(shè)計(jì)的頻繁模式集進(jìn)行了分割，并且將每一次檢驗(yàn)限制在與其相符合的更小的投影數(shù)據(jù)庫(kù)中.FreeSpan算法執(zhí)行過(guò)程的描述：(1)

18、首先給定序列數(shù)據(jù)庫(kù)S及最小支持度閾值8.2)掃描序列數(shù)據(jù)庫(kù)S,找到S中的頻繁項(xiàng)集，并以降序排列生成f_list列表。執(zhí)行下面步驟：a.根據(jù)生成的f_list列表把數(shù)據(jù)庫(kù)分成幾個(gè)不相交的子集。1)只包含第一個(gè)項(xiàng)。2)包含第二個(gè)項(xiàng)，但不包含以后的項(xiàng)。3)包含第N®,但不包含NH后的項(xiàng)。4)只包含最后一項(xiàng)。b.第一遍掃描數(shù)據(jù)庫(kù)S,找出每個(gè)項(xiàng)及其與前一項(xiàng)組成的項(xiàng)在序列數(shù)據(jù)庫(kù)中的頻度，刪除小于最小支持度的項(xiàng)。d.對(duì)生成的大于最小支持度的項(xiàng)遞歸的挖掘出更長(zhǎng)頻度的序列。直至最后的投影數(shù)據(jù)庫(kù)都是最大的頻繁子集。4.1.3FreeSpan算法分析：它將頻繁序列和頻繁模式的挖掘統(tǒng)一起來(lái)，把挖掘工作限制在

19、投影數(shù)據(jù)庫(kù)中，還能限制序列分片的增長(zhǎng).它能有效地發(fā)現(xiàn)完整的序列模式，同時(shí)大大減少產(chǎn)生候選序列所需的開(kāi)銷(xiāo)，比基于Apriori的GSPT法快很多.不足之處，它可能會(huì)產(chǎn)生許多投影數(shù)據(jù)庫(kù)，如果一個(gè)模式在數(shù)據(jù)庫(kù)中的每個(gè)序列中出現(xiàn)，該模式的投影數(shù)據(jù)庫(kù)將不會(huì)縮減；另外，一個(gè)長(zhǎng)度為k的序列可能在任何位置增長(zhǎng)，那么長(zhǎng)度為k+1的候選序列必須對(duì)每個(gè)可能的組合情況進(jìn)行考察，這樣所需的開(kāi)銷(xiāo)是比較大的.又FreeSpan中頻繁項(xiàng)矩陣F占用存儲(chǔ)空間的定量分析如下：設(shè)序列數(shù)據(jù)庫(kù)中有m頻繁項(xiàng)，頻繁項(xiàng)矩陣共需要|M|=m+32X(m-1)x(m-2)個(gè)計(jì)數(shù)單元。例如，m=1000,|M|=1.5x106=3Mb(假設(shè)每個(gè)計(jì)數(shù)

20、單元占用2b的空間)，目前一般的計(jì)算機(jī)就很容易滿(mǎn)足這個(gè)要求4。4.2PrefixSpan算法PrefixSpan算法的提出在許多應(yīng)用中，如DN剛析和股市序列分析等，數(shù)據(jù)庫(kù)常包含大量的序列模式，而且許多模式很長(zhǎng)，此時(shí)有必要重新審視序列模式挖掘問(wèn)題，以探索一些更加有效、易于擴(kuò)展的方法.通過(guò)觀察發(fā)現(xiàn)，基于Apriori算法的瓶頸在于每一步的候選集生成和測(cè)試，能否找到一種方法，既能吸取Apriori的靈魂又能避免或者充分減少昂貴的候選集生成和測(cè)試.順著這個(gè)思路，PeiJian,HanJiawei及WangJianyong等人基于分治和模式擴(kuò)展的原理提出了模式擴(kuò)展方法，代表性的算法有FreeSpan和P

21、re巾xSpan，其中PrefixSpan改進(jìn)法采用了偽投影技術(shù)，性能比FreeSpan好.下面描述并分析PrefixSpan算法.PrefixSpan算法思想及描述該算法就是通過(guò)前綴投影來(lái)挖掘序列模式，進(jìn)行投影時(shí)，并不考慮所有出現(xiàn)的頻繁子序列，而是找出前綴序列，把相應(yīng)的后綴投影成為一系列的投影數(shù)據(jù)庫(kù).對(duì)于每一個(gè)投影數(shù)據(jù)庫(kù)，只須找出局部頻繁模式，且不產(chǎn)生候選碼，它的主要步驟如下：掃描數(shù)據(jù)庫(kù)一次，找出頻繁L2序列，假設(shè)為k個(gè)；劃分研究空間：把完整的序列模式劃分為k個(gè)研究空間，分別以頻繁L2序列為前綴；構(gòu)造相應(yīng)的數(shù)據(jù)庫(kù)，也就是對(duì)應(yīng)前綴的后綴集合；在這些后綴集合中遞歸地發(fā)現(xiàn)頻繁模式的子集算法形式化描

22、述如下：輸入：序列數(shù)據(jù)庫(kù)S和最小支持度minsup.輸出：所有的序列模式.方法：調(diào)用子程序PrefixSpan(<>,0,S)其中子程序PrefixSpan(a,L,S|a)描述如下：(1)掃描S|a,找到滿(mǎn)足下述要求的長(zhǎng)度為1的序列模式b:b可以添加到a的最后一個(gè)元素中并為序列模式；<b>可以作為a的最后一個(gè)元素并為序列模式.(2)對(duì)每個(gè)生成白序列模式b，將b添加到a形成序列模式a',并輸出a'；(3)對(duì)每個(gè)a',構(gòu)造a'的投影數(shù)據(jù)庫(kù)S|a'，并調(diào)用子程序PrefixSpan(a',L+1,S|a').子程序參數(shù)

23、說(shuō)明：a為一個(gè)序列模式；L為序列模式a的長(zhǎng)度；S|a為a的投影數(shù)據(jù)庫(kù)(當(dāng)a為空時(shí)，S|a就是S).PrefixSpan算法分析：(1)PrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間(2)相對(duì)于原始的序列數(shù)據(jù)庫(kù)而言，投影數(shù)據(jù)庫(kù)的規(guī)模不斷減小(3)PrefixSpan算法的主要開(kāi)銷(xiāo)在于投影數(shù)據(jù)庫(kù)的構(gòu)造.PrefixSpan算法的主要改進(jìn)：(1)逐層投影：使用隔層投影代替逐層投影，從而可以有效減小投影數(shù)據(jù)庫(kù)的個(gè)數(shù)(2)偽投影：當(dāng)序列數(shù)據(jù)庫(kù)可以直接放入內(nèi)存時(shí)，可以使用偽投影操作代替實(shí)際的投影數(shù)據(jù)庫(kù)，從而可以有效減少構(gòu)造投影數(shù)據(jù)庫(kù)的開(kāi)銷(xiāo).其主要思想就是用指針指向?qū)?yīng)序列，用偏移量

24、表示后綴起始位置，這樣就可用指針和偏移量代替真實(shí)投影，從而在投影數(shù)據(jù)庫(kù)中不重復(fù)出現(xiàn)后綴，節(jié)省不少的空間.例如：序列數(shù)據(jù)庫(kù)只有序列a(abc)(ac)d(cf)>,關(guān)于ab的投影數(shù)據(jù)庫(kù)為(-c)(ac)d(cf)>,這時(shí)可以用(e,4)代替S|<ab>,指針指向?qū)?yīng)的序列，而4表示后綴從第4位置開(kāi)始，即從字符c開(kāi)始.可見(jiàn)利用虛擬投影節(jié)省了空間，進(jìn)一步提高了該類(lèi)算法的性能.PrefixSpan算法與Apriori算法的比較經(jīng)過(guò)測(cè)試比較，PrefixSpan算法性能比基于Apriori的算法(GSP和SPADE)明顯要好，原因在于：1)模式擴(kuò)展方式不生成候選序列。Prefix

25、Span是一個(gè)基于模式擴(kuò)展的方法，就象FP-growth一樣。用傳統(tǒng)的候選集生成-測(cè)試方法來(lái)處理一個(gè)比較小的數(shù)據(jù)庫(kù)(例如只有10k的序列)，需要相當(dāng)多的時(shí)間來(lái)生成和測(cè)試大量的候選序列模式。2)基于投影的分治是數(shù)據(jù)縮減(reduction)的有效方法。序列模式”的投影數(shù)據(jù)庫(kù)包含且僅包含用來(lái)挖掘那些由a擴(kuò)展得到的模式的必需信息，投影數(shù)據(jù)庫(kù)的大小隨著挖掘過(guò)程向更長(zhǎng)第8頁(yè)共27頁(yè)的序列模式進(jìn)行而迅速縮減。3)PrefixSpan需要的內(nèi)存空間相對(duì)穩(wěn)定。原因在于它采用分治的方法,不生成候選集。而GSP和SPADE，當(dāng)支持度閾值(supportthreshold)降低時(shí)，由于需要容納大量候選序列，需要相當(dāng)

26、數(shù)量的內(nèi)存?；谀Ｊ綌U(kuò)展的方法，可以應(yīng)用到多層次、多維數(shù)的序列模式中，也可以挖掘其他結(jié)構(gòu)化的模式。五、實(shí)例解析:例給定如下表所示的序列數(shù)據(jù)庫(kù)，分別用FreeSpan和PrefixSpan算法進(jìn)行計(jì)算，設(shè)最小支持度為2,并給出詳細(xì)過(guò)程.TABLE2Sequence_idSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>I、禾1J用FreeSpan算法解析：1.(1)找到頻繁項(xiàng)集：頻繁項(xiàng)按支持度降序排列形成頻繁項(xiàng)列表f_List=<a:4,b:4

27、,c:4,d:3,f:3,e:2>(注意：由于g:1<2,所以剪去。)根據(jù)f_List,序列模式集被分為不相交的六個(gè)子集：只包含項(xiàng)<a>.含項(xiàng)<b>,但不包括<b>以后的項(xiàng)。如<ab>正確，但<bc>錯(cuò)誤。含項(xiàng)<c>,但不包括<c>以后的項(xiàng)。)含項(xiàng)<d>,但不包括<d>以后的項(xiàng))含項(xiàng)<f>,但不包括<f>以后的項(xiàng)包含項(xiàng)<e>.分而自治策略。如序列模式<a>的投影數(shù)據(jù)庫(kù)是含有<a>的序列集的子序列，非頻繁項(xiàng)及a后的項(xiàng)也

28、被刪除。在數(shù)據(jù)庫(kù)中含<a>的項(xiàng)<aaa><aa><a><a>，但只有<aa>:2被保留，其余全部刪除。又如序列模式<c>的投影數(shù)據(jù)庫(kù)是含有<c>的序列子集的子序列。其中包括與<c>以前的項(xiàng)所一起組成的子序列。挖掘以<C>影的數(shù)據(jù)<a(abc)(ac)c>,<ac(bc)a>,<(ab)cb>,<acbc>.再次掃貓數(shù)據(jù)庫(kù)，挖掘出長(zhǎng)度為2的序列，如<ac>:4,<(bc)>2,<bc>:3,&l

29、t;cc>:3,<ca>:2,<cb>:3,接下來(lái)我們?cè)俅螔哓堃?lt;ac>為前綴的投影數(shù)據(jù)庫(kù)，包括<a(abc)(ac)c>,<ac(bc)a>,<acbc>,并以此生成長(zhǎng)度為3的序列模式，即有<acb>:3,<acc>:3,<(ab)c>:2,<aca>:2.對(duì)于<acb>挖掘數(shù)據(jù)庫(kù)如下<ac(bc)a>,<(ab)cb>,<acbc>,此時(shí)我們發(fā)現(xiàn)找不到長(zhǎng)度為4的序列模式。則此時(shí)<acb>就到此結(jié)束，<

30、acb>即為一個(gè)頻繁序列子集。相似的，對(duì)于其他的序列模式我們也如此的進(jìn)行遞歸的投影。最終得到的頻繁序列子集如下表。n、利用PrefixSpan算法解析：.查找長(zhǎng)度為1的序列模式<a>:4,<b>:4,<c>:4,<d>:3,<e>:3,<f>:3.分割搜索空間序列模式集可按6個(gè)前綴被劃分為六個(gè)子集：1)包含前綴<a>的子集；2)包含前綴<b>的子集；3)包含前綴<c>的子集；4)包含前綴<d>的子集；5)包含前綴<e>的子集；6)包含前綴<f>的

31、子集。.尋找序列模式的子集。構(gòu)建并遞歸挖掘投影數(shù)據(jù)庫(kù)。(1)尋找具有前綴<a>的序列模式。<a>一投影數(shù)據(jù)庫(kù)，由4個(gè)后綴序列組成：<(abc)(ac)d(cf)>,<(_d)c(bc)(ae)>,<(_b)(df)cb>,<(_f)cbc>。(3)掃描<a>投影數(shù)據(jù)庫(kù)一遍，找到含有前綴<a>的長(zhǎng)度為2的序列模式，包括：<aa>:<ab>:4,<(ab)>:2,<ac>:4,<ad>:2,<af>:2。(4)遞歸，所有具有前綴&l

32、t;a>的序列劃分為6個(gè)子集：1)包含前綴<aa>的子集；,；6)包含前綴<af>的子集<aa>一投影數(shù)據(jù)庫(kù)：<(_bc)(ac)d(cf)>。不產(chǎn)生任何頻繁子序列，結(jié)束。<(ab)>一投影數(shù)據(jù)庫(kù)：<(_c)(ac)d(cf)>,<(df)cb>,包含前綴<(ab)>的序列模式有：<c>,<d>,<f>,<dc>。即<(ab)c>,<(ab)d>,<(ab)f>,<(ab)dc><ab>

33、一投影數(shù)據(jù)庫(kù)：<(_c)(ac)d(cf)>,<(_c)a>,<c>。序列模式：<(_c)>,<(_c)a>,<a>,<c>,即<a(bc)>,<a(bc)a>,<aba>,<abc>。,直到<af>都投完。然后繼續(xù)以沒(méi)有結(jié)束的3-序列模式繼續(xù)投影，如<(ab)d>一投影數(shù)據(jù)庫(kù)：<(cf)>,<(_f)cb>包含前綴<(ab)d>的序列模式有：<c>,找到含有前綴<(ab)d>的序

34、列模式，包括：第10頁(yè)共27頁(yè)<(ab)dc>。最終序列模式如下圖所示:前綴投影（后綴）數(shù)據(jù)庫(kù)序列模式<a><(abc)(ac)d(cf)>,<(_d)c(bc)(ae)>,<(_b)(df)cb>,<(_f)cbc><a>,<aa>,<ab>,<a(bc)>,<a(bc)a>,<aba>,<abc>,<(ab)>,<(ab)c>,<(ab)d>,<(ab)f>,<(ab)dc>,

35、<ac>,<aca>,<acb>,<acc>,<ad>,<adc>,<af><b><(_c)(ac)d(cf)>,<(_c)(ae)>,<(df)cb>,<c><b>,<ba>,<bc>,<(bc)>,<(bc)a>,<bd>,<bdc>,<bf><c><(ac)d(cf)>,<(bc)(ae)>,<b>,&l

36、t;bc><c>,<ca>,<cb>,<cc><d><(cf)>,<c(bc)(ae)>,<(_f)cb><d>,<db><dc>,<dcb><e><(_f)(ab)(df)cb>,<(af)cbc><e>,<ea>,<eab>,<eac>,<eacb>,<eb>,<ebc>,<ec>,<ecb>,<

37、;ef>,<efb>,<efc>,<efcb><f><(ab)(df)cb>,<cbc><f>,<fb>,<fbc>,<fc>,<fcb>六：Mprefixspan算法的Vd序的實(shí)現(xiàn)prefixspan算法的流程圖分割搜索空間序列模式集可按6個(gè)前綴被劃分為六個(gè)子集1）包含前綴a的子集；，；6）包含前綴f的子集算法執(zhí)行結(jié)果prefixspan算法的本算法只是針對(duì)給定的特定的數(shù)據(jù)庫(kù)序列數(shù)據(jù)進(jìn)行挖掘，結(jié)合對(duì)理解的基礎(chǔ)上，對(duì)prefixspan實(shí)現(xiàn)了簡(jiǎn)單的編程，在V

38、C勺編程環(huán)境下，利用控制臺(tái)程序來(lái)實(shí)現(xiàn)對(duì)算法的運(yùn)行。算法的運(yùn)行結(jié)果基本和上述算法的結(jié)果吻合。實(shí)驗(yàn)結(jié)果會(huì)在Debug文件下生成一個(gè)output.txt文檔。Hicrosoftilindo忖零XPl版本5.L.26闕】<C>版權(quán)所有198S-2001NicrosoFtCorp.一.I:C：XDocumiits«ndSettingsfkdninistrator>cdC;XJDociirwnts<ndSettingsXftdRijnlstrat口DociinntsXgkPi*efixspanDehugrC-XltocurnntsandSnttingsMHdRiniiit

39、ratdrMlyDocuMntskXPTvfixBjMfiXllebug>prefi翼匕pan_testa.txt-f0>.2DeciiiwntsandSettIngsNAldpilnistratorMlyDocumentsgJ«Pre£ix&p4nxDebuig>結(jié)果保存在output.txt文件中de|be|cbb|cb|c|dfbc|df|efb|c|eFb|dfb|df|eFbeFbecc|dfc|dfefcef結(jié)果分析通過(guò)對(duì)算法的結(jié)果來(lái)看，比較更加容易的理解算法的基本性能，但是對(duì)于其他數(shù)據(jù)來(lái)說(shuō)仍然比較吃力。七、結(jié)論與展望序列模式挖掘是當(dāng)前

40、數(shù)據(jù)挖掘領(lǐng)域中一個(gè)較新而且非?；钴S的研究分支，有著廣泛的應(yīng)用價(jià)值。文章在介紹了序列模式挖掘的相關(guān)概念后，對(duì)一類(lèi)序列模式挖掘的2個(gè)經(jīng)典的算法進(jìn)行了描述和分析，不難發(fā)現(xiàn)，基于模式擴(kuò)展的方法是個(gè)前途很好的發(fā)展方向。模式擴(kuò)展方法還有很多工作要做，如閉合集挖掘、在特定領(lǐng)域的針對(duì)性研究等等。通過(guò)文章我們了解到FreeSpan和PrefixSpan屬于模式增長(zhǎng)方法，它們采用分而治之的方法，大大提高了算法的效率。但在實(shí)際應(yīng)用中，在挖掘過(guò)程的不同階段，數(shù)據(jù)集白特點(diǎn)，數(shù)據(jù)規(guī)模等因素可能不同，如果根據(jù)各階段的特點(diǎn)，選擇與之相應(yīng)的算法，則序列模式挖掘能達(dá)到更好的效果。面對(duì)一個(gè)具體的實(shí)例，例如股票序列分析中，如何根據(jù)不

41、同階段的數(shù)據(jù)集的特點(diǎn)選擇合適的算法，這些數(shù)據(jù)挖掘算法的結(jié)論信息又如何鏈接、傳輸、共享和兼容等，這些問(wèn)題都是我們今后工作的研究?jī)?nèi)容。八、致謝九、參考文獻(xiàn)呂鋒，張煒偉。4種序列模式挖掘算法的特性研究，武漢理工大學(xué)學(xué)報(bào)。2006年2月第28卷第2期。HANJia-wei,PEIJian.Freespan:frequentpattern-projectedsequentialpatternminingC/Procofthe2000InternalionalConferenceonKnowledgeDiscoveryandDataMining(KDD).NewYork:ACMPress,2000:355

42、2-359.PEIJian,HANJia-wei,PINTOH,etal.PrefixSpan:miningsequentialpatternsefficientlybyprefix-projectedpatterngrowthC/Proc2001IntConfDataEngin(ICDE01).LosAlamitos:IEEEComputerSocietyPress,2001:2152224.MANNILAH,TOIVONENH,VERKAMOAI.DiscoveryoffrequentepisodesineventsequencesJ.DataMin&KnowlDiscovery,

43、1996,1(3):2582289.5張大海，胡孔法，陳凌。序列模式算法綜述。揚(yáng)州大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007年2月第10卷第1期。6夏明，王曉川，孫永強(qiáng)，金士堯。序列模式挖掘算法研究。11算機(jī)技術(shù)與發(fā)展。2006年第16卷第4期。十、附錄算法實(shí)現(xiàn)的主要程序如下：一：prefixspan.cpp#pragmawarning(disable:4786)#include<iostream>#include<fstream>#include<string>#include<vector>#include<list>#include<

44、;set>#include<map>#include<math.h>#includealgorithm#include"prefixspan.h"usingnamespacestd;#defineSAME_SET"_"#defineMAX_FR_SIZE(unsignedint)32768/輸出幫助信息voidshow_help()(std:cout<<"n"<<"Prefixspantestscriptn"<<"nn"<&

45、lt;"Usage:'tprefixspan_testINPUT_NAMEsMIN_SUPPOUTPUT_NAMEorn<<"'tprefixspan_testINPUT_NAME-fMIN_FROUTPUT_NAMEnn"<<"Defaultoutputnameis'output.txt'nn")/讀取輸入數(shù)據(jù)文件到內(nèi)存intread_input(INFILE&f,sequence_database&db)(sequencecurrent_row;itemcurrent_

46、item;itemsetcurrent_set;std:stringbuff;std:getline(f,buff);while(!f.eof()(current_item.erase();current_set.clear();current_row.clear();for(unsignedinti=0;i<buff.size();+i)(if('|'=buffi)/thismeansthatwe'reattheendofanitemcurrent_set.push_back(current_item);current_item.erase();)elseif(

47、''=buffi|'t'=buffi)/正處在項(xiàng)集第1項(xiàng)(if(0<current_item.size()/跳過(guò)多個(gè)空格(current_set.push_back(current_item);current_item.erase();current_set.sort();/排序項(xiàng)目當(dāng)前"設(shè)置"current_row.push_back(current_set);current_set.clear();)else(current_item+=buffi;/處在項(xiàng)目的中間，必須擴(kuò)大)current_set.push_back(curren

48、t_item);current_set.sort();current_row.push_back(current_set);db.push_back(current_row);std:getline(f,buff);/讀取一行)return0;)/輸出一個(gè)序列std:ostream&print_sequence(std:ostream&f,constsequence&s)for(sequence:const_iteratorit=s.begin();it!=s.end();+it)(itemset:const_iteratoris_it=it->begin();f

49、<<(*is_it);for(+is_it;is_it!=it->end();+is_it)f<<"|"<<(*is_it);)f<<"")returnf;)/輸出一個(gè)數(shù)據(jù)庫(kù)std:ostream&print_database(std:ostream&f,constsequence_database&db)for(sequence_database:const_iteratorit=db.begin();it!=db.end();+it)print_sequence(f,(*i

50、t);f<<std:endl;)returnf;)/輸出序列列表std:ostream&print_list(std:ostream&f,constsequence_listl)(intk=0;for(sequence_list:const_iteratorit=l.begin();it!=l.end();+it)(if(k%2=0)print_sequence(f,(*it);f<<"n"+k;)returnf;)/c計(jì)算最小支持度unsignedintcalc_min_supp(constsequence_database&

51、;db,floatmin_freq)(return(unsignedint)ceil(float)db.size()*min_freq);)/計(jì)算支持計(jì)數(shù)voidcount_frequencies(constsequence_database&db,frequency_counter&fc)(for(sequence_database:const_iteratorrow_it=db.begin();row_it!=db.end();+row_it)(set_of_itemsitems_in_the_row;for(sequence:const_iteratorseq_it=ro

52、w_it->begin();seq_it!=row_it->end();+seq_it)(for(itemset:const_iteratorset_it=seq_it->begin();set_it!=seq_it->end();+set_it)/puttingtheitemsinaset=>eachwilloccuronceitems_in_the_row.insert(*set_it);)/在每個(gè)項(xiàng)目該行時(shí)增加支持度f(wàn)or(set_of_items:iteratoritems_it=items_in_the_row.begin();items_it!=ite

53、ms_in_the_row.end();+items_it)+fc(*items_it);)/序列擴(kuò)展voidextend_prefix_sequence(constsequence&old_prefix,constitem&alfa,sequence&new_prefix)new_prefix=old_prefix;itemsettmp_set;tmp_set.push_back(alfa);new_prefix.push_back(tmp_set);/項(xiàng)集擴(kuò)展voidextend_prefix_itemset(constsequence&old_prefix

54、,constitem&beta,sequence&new_prefix)new_prefix=old_prefix;itemset&tmp_set=new_prefix.back();tmp_set.push_back(beta);/剪切序列前綴voidcut_sequence(sequence&s,sequence:iterator&seq_it,itemset:iterator&item_pos)seq_it->erase(seq_it->begin(),+item_pos);if(seq_it->empty()+seq_i

55、t;elseseq_it->push_front(SAME_SET);s.erase(s.begin(),seq_it);/構(gòu)造序列數(shù)據(jù)庫(kù)voidproject_database_sequence(constsequence_database&db,constitem&alfa,sequence_database&projected_db)projected_db.clear();for(sequence_database:const_iteratorrow_it=db.begin();row_it!=db.end();+row_it)sequencecurren

56、t_row=(*row_it);booldone=false;for(sequence:iteratorseq_it=current_row.begin();!done&&seq_it!=current_row.end();+seq_it)itemset:iteratoralfa_pos=find(seq_it->begin(),seq_it->end(),alfa);陜西理工學(xué)院畢業(yè)設(shè)計(jì)itemset:iteratorindicator_pos=find(seq_it->begin(),seq_it->end(),SAME_SET);/wehaveav

57、alidsuffix,ifthenewitemalfaisin/anitemsetthatdoesn'tcontainthejokerch.if(seq_it->end()!=alfa_pos&&seq_it->end()=indicator_pos)done=true;cut_sequence(current_row,seq_it,alfa_pos);projected_db.push_back(current_row);/檢查序列的最后一個(gè)項(xiàng)集是否在給定的項(xiàng)集中boolis_full_prefix_included(itemset&current

58、_set,constitemset&prefix_end,constitem&beta,itemset:iterator&beta_pos)boolprefix_found=true;itemset:iteratoritem_pos=current_set.begin();for(itemset:const_iteratorit=prefix_end.begin();prefix_found&&it!=prefix_end.end();+it)/it'senoughtocheckfromthelastfoundposition,/sincethe

59、listsareordereditem_pos=find(item_pos,current_set.end(),(*it);prefix_found=(current_set.end()!=item_pos);if(prefix_found)beta_pos=find(current_set.begin(),current_set.end(),beta);prefix_found=(current_set.end()!=beta_pos);returnprefix_found;/根據(jù)項(xiàng)集擴(kuò)展來(lái)構(gòu)造數(shù)據(jù)庫(kù)voidproject_database_itemset(constsequence_dat

60、abase&db,constsequence&prefix,constitem&beta,sequence_database&projected_db)projected_db.clear();itemsetlast_set;if(!prefix.empty()last_set=prefix.back();for(sequence_database:const_iteratorrow_it=db.begin();row_it!=db.end();+row_it)(sequencecurrent_row=(*row_it);booldone=false;for(sequence:iteratorseq_it=current_row.begin();!done&&seq_it!=current_row.end();+seq_it)(itemset:iteratorindicator_pos=find(seq_it->begin(),seq_it->end(),SAME_SET);if(seq_it->end()!=indicator_pos)itemset:iteratorbeta_pos=find(seq_it->begin(),seq_it->end(),bet