畢業(yè)設(shè)計(jì)（論文）-基于投影數(shù)據(jù)挖掘算法研究與實(shí)現(xiàn).docVIP

陜西理工學(xué)院畢業(yè)設(shè)計(jì) 畢業(yè)論文設(shè)計(jì)題 目 基于投影數(shù)據(jù)挖掘算法研究與實(shí)現(xiàn) 學(xué)生姓名 學(xué)號(hào) 041842020 所在院(系) 數(shù)學(xué)系 專業(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é)專業(yè) 陜西 723001）指導(dǎo)教師：摘要：序列模式的發(fā)現(xiàn)是數(shù)據(jù)挖掘領(lǐng)域一個(gè)活躍的研究分支,即在序列數(shù)據(jù)庫中找出所有的頻繁子序列.本文先介紹序列模式挖掘中的一些基本概念,然后詳細(xì)描述freespan和prefixspan2個(gè)基于投影、分治的模式增長(zhǎng)的重要算法。基于投影方法即序列數(shù)據(jù)庫先被投影為很多小投影數(shù)據(jù)庫, 然后在小投影數(shù)據(jù)庫中進(jìn)行遞歸挖掘的典型算法.其中freespan算法是將數(shù)據(jù)庫分成若干個(gè)子空間，再每個(gè)子空間里進(jìn)行遞歸的的投影，對(duì)于每一個(gè)項(xiàng)及其與前一項(xiàng)組合成的序列模式進(jìn)行投影挖掘，最終得出頻繁子序列。prefixspan算法則是先找出長(zhǎng)度為1的序列模式，以此序列模式為前綴的投影，并在投影數(shù)據(jù)庫里面繼續(xù)遞歸的進(jìn)行投影，最終得出頻繁子序列。本文并以實(shí)例解析，更為詳細(xì)清楚的描述了兩種算法的過程。關(guān)鍵詞:數(shù)據(jù)挖掘； freespan算法；prefixspan算法；according to cast shadow a data toscoop out calculate way researchauthor：guokai（grade04,class03, information and calculation science，department of mathematics，shaanxi university of technology，hanzhong 723000，shaanxi）tutor: zhoutaoabstract sequence mode data mining is the discovery of an active area of research branch, that is, all sequences in the database to identify the frequency of sequence. in this paper, first introduced in the sequence pattern mining some of the basic concepts, and then described in detail freespan and prefixspan2 based projection, the partition of the important growth pattern algorithm. based on the projection method that sequence database was first projection for the many small projection database, and then a small projection database mining typical recursive algorithm. which freespan algorithm is divided into several sub-database space, then each of the recursive space for the projector, and for each and every item with a combination of 10% of the former model projection excavation sequence, the final sequence of drawn frequent. the prefixspan calculate way then find out the length as one sequence mode first, take this sequence mode as cast shadow of ex- zhui, and continue to pass to return in the projection the database of carry on cast shadow, end get multifarious sub- sequence. analysis and examples in this paper, a more detailed description of the two clearly algorithm process.keywords the data scoop out;freespan arithmetic; prefixspan arithmetic;目 錄一 引言5二 序列模式挖掘相關(guān)知識(shí)52.1 基本術(shù)語52.2 基本定義5三 序列模式簡(jiǎn)介63.1 問題描述63.2 系統(tǒng)規(guī)定6四 模式增長(zhǎng)方法64.1 freespan算法6 4.1.1 freespan算法的思想6 4.1.2 freespan算法執(zhí)行過程的描述7 4.1.3 freespan算法的分析74.2 prefixspan算法7 4.2.1 prefixspan算法的提出7 4.2.2 prefixspan算法的思想及描述7 4.2.3 prefixspan算法的分析8 4.2.4 prefixspan算法的主要改進(jìn)8 4.2.5 prefixspan算法和aporiori算法的比較8五 實(shí)例解析9i 利用freespan算法解析9 利用prefixspan算法解析10六 對(duì)prefixspan算法的vc程序的實(shí)現(xiàn)126.1 prefixspan算法的流程圖126.2 算法的執(zhí)行結(jié)果136.3 算法結(jié)果分析14七 結(jié)論與展望15八 致謝15九 參考文獻(xiàn)16十 附錄17一：引言：序列模式挖掘是數(shù)據(jù)挖掘研究的一個(gè)重要課題, 而且具有非常廣泛的應(yīng)用，被應(yīng)用在包括顧客購買行為的分析、網(wǎng)絡(luò)訪問模式分析、科學(xué)實(shí)驗(yàn)的分析、疾病治療的早期診斷、自然災(zāi)害的預(yù)測(cè)、dna 序列模式的分析等1.目前對(duì)序列模式挖掘問題的研究主要集中在算法設(shè)計(jì)和實(shí)際應(yīng)用，在理論方面研究還很罕見.序列模式挖掘是對(duì)關(guān)聯(lián)規(guī)則挖掘的進(jìn)一步推廣, 它挖掘出序列數(shù)據(jù)庫中項(xiàng)集間的時(shí)序關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究的一個(gè)重要內(nèi)容. 早先的很多關(guān)聯(lián)規(guī)則挖掘研究都有助于挖掘序列模式或者與時(shí)間相關(guān)的頻繁模式. srikant和agrawal對(duì)序列規(guī)定了時(shí)間限制、滑動(dòng)時(shí)間窗口和用戶規(guī)定的分類, 并總結(jié)了序列模式的定義, 提出一種基于apriori 的改進(jìn)算法gsp(generalized sequential patterns)算法. 以上這些都是基于apriori的水平格式的序列模式挖掘或者與時(shí)間相關(guān)的頻繁模式挖掘. 后來, zaki提出了一種基于垂直格式存儲(chǔ)的序列模式挖掘方法spade算法, 該算法由基于垂直格式的頻繁項(xiàng)挖掘演化而來. 近幾年, han等人又提出一種基于投影的模式增長(zhǎng)算法freespan（frequent pattern-pojected sequential pattern mining）算法2 , 該算法改進(jìn)后為prefixspan(prefix-projected sequential patterns mining)算法3 , 性能進(jìn)一步提高. mannila等人4提出的挖掘頻繁序列片段問題,garofalakis等人提出的基于規(guī)則表達(dá)式約束的序列模式挖掘, 還有關(guān)于序列模式挖研究的一些擴(kuò)展, 如序列模式閉項(xiàng)挖掘、并行挖掘、分布式挖掘、多維度序列模式挖掘和近似序列模式挖掘等, 所有這些對(duì)后來研究序列模式挖掘都有一定的影響. 本文重點(diǎn)對(duì)典型的序列模式挖掘算法freespan和prefixspan兩種典型算法進(jìn)行詳細(xì)的描述、分析和比較.二、序列模式挖掘的相關(guān)知識(shí)2.1 基本術(shù)語設(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)集, 也稱作s的元素. 元素由不同的項(xiàng)組成, 可表示為(x1, x2, , xn). 當(dāng)元素只包含一項(xiàng)時(shí), 一般省去括號(hào), 如(x2)一般表示為x2. 元素之間是有順序的, 但元素內(nèi)的項(xiàng)是無序的, 一般定義為詞典序. 序列包含項(xiàng)的個(gè)數(shù)稱為序列的長(zhǎng)度, 長(zhǎng)度為l的序列記為l- 序列. 序列數(shù)據(jù)庫就是元組(tuples)sid, s 的集合, 其中s是序列, sid 是該序列的序列號(hào), 元組的個(gè)數(shù)稱為序列數(shù)據(jù)庫的大小, 記作|sdb|.2.2 基本定義5定義1 序列模式：給定一個(gè)由不同序列組成的集合，其中，每個(gè)序列由不同的元素按順序有序排列，每個(gè)元素由不同項(xiàng)目組成，同時(shí)給定一個(gè)用戶指定的最小支持度閾值，序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中的出現(xiàn)頻率不低于用戶指定的最小支持度閾值.定義2子序列和超序列：對(duì)于序列a=a1, a2, , an和b=b1, b2, , bm , 當(dāng)且僅當(dāng)1j1 j2 jm m 且a1j1 , a2j2 , , anjn時(shí), 稱序列b為序列a的超序列, 序列a為序列b的子序列, 又稱序列b包含序列a, 記作ab. 例如在表1中a(abc)(cf) bd這個(gè)序列, 其中(abc),a(abc) (cf)都是a(abc)(cf)bd的子序列, a(abc)(cf)bd是(abc),a(abc)(cf)的超序列.定義3 支持?jǐn)?shù)：序列數(shù)據(jù)庫d是元組sid, s的集合, sid為序列標(biāo)識(shí)號(hào). 如果序列t是s的子序列(即ts) , 稱元組sid, s包含序列t , 則序列t 在序列數(shù)據(jù)庫d中的支持?jǐn)?shù)是數(shù)據(jù)庫中包含t的元組數(shù), 即support d(t) = |sid, s|sid, sdts | , 記作support(t).定義4頻繁序列模式：給定一個(gè)最小支持度閾值minsup , 如果序列s的支持度不小于minsup , 則稱序列s為頻繁序列模式, 所有的頻繁序列模式集合記作fs. 例如在表1中(ac)這個(gè)序列分別在10和40序列出現(xiàn)2次, 所以其支持?jǐn)?shù)為2. 假設(shè)用戶規(guī)定min sup 為2, 可知(ac)序列是頻繁序列模式.定義5 前綴( prefix) :設(shè)每個(gè)元素中的所有項(xiàng)目按照字典序排列.給定序列 = ,=( m n) ,如果ei= ei ( i m - 1) , em em ,并且(em- em) 中的項(xiàng)目均在em中項(xiàng)目的后面, 則稱是的前綴;定義6 后綴(suffix) : 序列關(guān)于子序列= 的投影為= ( n m) ,則序列關(guān)于子序列的后綴為 , 其中em= ( em - em) ;定義7 投影：給定序列和，如果是的子序列，則關(guān)于的投影必須滿足：是的前綴，是的滿足上述條件的最大子序列.定定義8投影數(shù)據(jù)庫：設(shè)a為序列數(shù)據(jù)庫s中的一個(gè)序列模式，則a的投影數(shù)據(jù)庫為s中所有以a為前綴的序列相對(duì)于a的后綴，記為s|a.例：在表1中投影數(shù)據(jù)庫由3個(gè)后綴序列組成：，,， 投影數(shù)據(jù)庫.定義9 投影數(shù)據(jù)庫中的支持?jǐn)?shù):設(shè)為序列數(shù)據(jù)庫s 中的一個(gè)序列模式,序列以為前綴,則在的投影數(shù)據(jù)庫s|中的支持?jǐn)?shù)為s|中滿足條件.的序列的個(gè)數(shù). 表1 序列數(shù)據(jù)庫sid序列10a（abc）(cf)bd20eabc(ce)30cghd40(ac)bg(cf)f 三、序列模式簡(jiǎn)介3.1 問題描述：給定序列數(shù)據(jù)庫和最小支持度閾值，序列模式挖掘就是要找出序列數(shù)據(jù)庫中所有的序列模式.3.2 系統(tǒng)規(guī)定：由于同一個(gè)元素中的項(xiàng)目之間排列沒有順序，為了表達(dá)的唯一性，我們將同一個(gè)元素內(nèi)部的不同項(xiàng)目按照字典順序排列.四、模式增長(zhǎng)方法這類算法是一種基于投影的、分治的模式增長(zhǎng)的方法, 即序列數(shù)據(jù)庫先被投影為很多小投影數(shù)據(jù)庫, 然后在小投影數(shù)據(jù)庫中進(jìn)行遞歸挖掘.4.1 freespan 算法 4.1.1 freespan算法思想freespan ,即頻繁模式投影的序列模式挖掘,其基本思想為:利用頻繁項(xiàng)遞歸地將序列數(shù)據(jù)庫投影到更小的投影數(shù)據(jù)庫集中,在每個(gè)投影數(shù)據(jù)庫中生成子序列片段.這一過程對(duì)數(shù)據(jù)和待檢驗(yàn)的頻繁模式集進(jìn)行了分割,并且將每一次檢驗(yàn)限制在與其相符合的更小的投影數(shù)據(jù)庫中.4.1.2 freespan 算法執(zhí)行過程的描述:(1) 首先給定序列數(shù)據(jù)庫s 及最小支持度閾值.(2) 掃描序列數(shù)據(jù)庫s，找到s中的頻繁項(xiàng)集，并以降序排列生成f_list列表。 執(zhí)行下面步驟：a. 根據(jù)生成的f_list列表把數(shù)據(jù)庫分成幾個(gè)不相交的子集。1） 只包含第一個(gè)項(xiàng)。2） 包含第二個(gè)項(xiàng)，但不包含以后的項(xiàng)。3） 包含第n項(xiàng)，但不包含n以后的項(xiàng)。4） 只包含最后一項(xiàng)。b.第一遍掃描數(shù)據(jù)庫s，找出每個(gè)項(xiàng)及其與前一項(xiàng)組成的項(xiàng)在序列數(shù)據(jù)庫中的頻度，刪除小于最小支持度的項(xiàng)。d.對(duì)生成的大于最小支持度的項(xiàng)遞歸的挖掘出更長(zhǎng)頻度的序列。直至最后的投影數(shù)據(jù)庫都是最大的頻繁子集。4.1.3 freespan 算法分析:它將頻繁序列和頻繁模式的挖掘統(tǒng)一起來,把挖掘工作限制在投影數(shù)據(jù)庫中,還能限制序列分片的增長(zhǎng).它能有效地發(fā)現(xiàn)完整的序列模式,同時(shí)大大減少產(chǎn)生候選序列所需的開銷,比基于apriori 的gsp算法快很多.不足之處,它可能會(huì)產(chǎn)生許多投影數(shù)據(jù)庫,如果一個(gè)模式在數(shù)據(jù)庫中的每個(gè)序列中出現(xiàn),該模式的投影數(shù)據(jù)庫將不會(huì)縮減;另外,一個(gè)長(zhǎng)度為k 的序列可能在任何位置增長(zhǎng),那么長(zhǎng)度為k + 1的候選序列必須對(duì)每個(gè)可能的組合情況進(jìn)行考察,這樣所需的開銷是比較大的. 對(duì)freespan 中頻繁項(xiàng)矩陣f占用存儲(chǔ)空間的定量分析如下:設(shè)序列數(shù)據(jù)庫中有m個(gè)頻繁項(xiàng),頻繁項(xiàng)矩陣共需要|m|= m +32(m-1)(m-2) 個(gè)計(jì)數(shù)單元。例如, m=1000 ,|m|=1.5106=3mb(假設(shè)每個(gè)計(jì)數(shù)單元占用2b 的空間) ,目前一般的計(jì)算機(jī)就很容易滿足這個(gè)要求4。4.2prefixspan 算法4.2.1 prefixspan算法的提出在許多應(yīng)用中,如dna分析和股市序列分析等,數(shù)據(jù)庫常包含大量的序列模式,而且許多模式很長(zhǎng),此時(shí)有必要重新審視序列模式挖掘問題,以探索一些更加有效、易于擴(kuò)展的方法.通過觀察發(fā)現(xiàn),基于apriori算法的瓶頸在于每一步的候選集生成和測(cè)試,能否找到一種方法,既能吸取apriori的靈魂又能避免或者充分減少昂貴的候選集生成和測(cè)試.順著這個(gè)思路, peijian ,han jiawei 及wang jianyong 等人基于分治和模式擴(kuò)展的原理提出了模式擴(kuò)展方法,代表性的算法有freespan 和prefixspan ,其中prefixspan改進(jìn)法采用了偽投影技術(shù),性能比freespan 好.下面描述并分析prefixspan 算法.4.2.2 prefixspan 算法思想及描述該算法就是通過前綴投影來挖掘序列模式, 進(jìn)行投影時(shí), 并不考慮所有出現(xiàn)的頻繁子序列, 而是找出前綴序列, 把相應(yīng)的后綴投影成為一系列的投影數(shù)據(jù)庫. 對(duì)于每一個(gè)投影數(shù)據(jù)庫, 只須找出局部頻繁模式, 且不產(chǎn)生候選碼, 它的主要步驟如下: 掃描數(shù)據(jù)庫一次, 找出頻繁l2序列, 假設(shè)為k個(gè); 劃分研究空間: 把完整的序列模式劃分為k個(gè)研究空間, 分別以頻繁l2序列為前綴; 構(gòu)造相應(yīng)的數(shù)據(jù)庫,也就是對(duì)應(yīng)前綴的后綴集合; 在這些后綴集合中遞歸地發(fā)現(xiàn)頻繁模式的子集.算法形式化描述如下:輸入: 序列數(shù)據(jù)庫s 和最小支持度min sup.輸出: 所有的序列模式.方法:調(diào)用子程序prefixspan( , 0 , s )其中子程序prefixspan( , l , s|) 描述如下:(1) 掃描s|,找到滿足下述要求的長(zhǎng)度為1 的序列模式b :1) b 可以添加到的最后一個(gè)元素中并為序列模式;2) 可以作為的最后一個(gè)元素并為序列模式.(2) 對(duì)每個(gè)生成的序列模式b ,將b 添加到形成序列模式,并輸出;(3) 對(duì)每個(gè),構(gòu)造的投影數(shù)據(jù)庫s|,并調(diào)用子程序prefixspan (,l + 1,s|) .子程序參數(shù)說明:為一個(gè)序列模式; l 為序列模式的長(zhǎng)度; s|為的投影數(shù)據(jù)庫(當(dāng)為空時(shí), s|就是s) .4.2.3 prefixspan算法分析：(1)prefixspan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間.(2)相對(duì)于原始的序列數(shù)據(jù)庫而言，投影數(shù)據(jù)庫的規(guī)模不斷減小.(3)prefixspan算法的主要開銷在于投影數(shù)據(jù)庫的構(gòu)造.4.2.4 prefixspan算法的主要改進(jìn)：(1)逐層投影：使用隔層投影代替逐層投影，從而可以有效減小投影數(shù)據(jù)庫的個(gè)數(shù).(2)偽投影：當(dāng)序列數(shù)據(jù)庫可以直接放入內(nèi)存時(shí)，可以使用偽投影操作代替實(shí)際的投影數(shù)據(jù)庫，從而可以有效減少構(gòu)造投影數(shù)據(jù)庫的開銷. 其主要思想就是用指針指向?qū)?yīng)序列, 用偏移量表示后綴起始位置, 這樣就可用指針和偏移量代替真實(shí)投影, 從而在投影數(shù)據(jù)庫中不重復(fù)出現(xiàn)后綴, 節(jié)省不少的空間. 例如: 序列數(shù)據(jù)庫只有序列a(abc)(ac)d (cf) , 關(guān)于ab的投影數(shù)據(jù)庫為(- c)(ac) d (cf) , 這時(shí)可以用(e ,4) 代替s |ab, 指針指向?qū)?yīng)的序列, 而4表示后綴從第4 位置開始, 即從字符c 開始. 可見利用虛擬投影節(jié)省了空間, 進(jìn)一步提高了該類算法的性能6.4.2.5 prefixspan 算法與apriori算法的比較經(jīng)過測(cè)試比較,prefixspan 算法性能比基于apriori的算法(gsp 和spade) 明顯要好,原因在于:1) 模式擴(kuò)展方式不生成候選序列。prefixspan 是一個(gè)基于模式擴(kuò)展的方法,就象fp - growth 一樣。用傳統(tǒng)的候選集生成- 測(cè)試方法來處理一個(gè)比較小的數(shù)據(jù)庫(例如只有10k 的序列) ,需要相當(dāng)多的時(shí)間來生成和測(cè)試大量的候選序列模式。2) 基于投影的分治是數(shù)據(jù)縮減( reduction) 的有效方法。序列模式的投影數(shù)據(jù)庫包含且僅包含用來挖掘那些由擴(kuò)展得到的模式的必需信息, 投影數(shù)據(jù)庫的大小隨著挖掘過程向更長(zhǎng)的序列模式進(jìn)行而迅速縮減。3) prefixspan 需要的內(nèi)存空間相對(duì)穩(wěn)定。原因在于它采用分治的方法,不生成候選集。而gsp 和spade ,當(dāng)支持度閾值(support threshold) 降低時(shí),由于需要容納大量候選序列,需要相當(dāng)數(shù)量的內(nèi)存?；谀Ｊ綌U(kuò)展的方法,可以應(yīng)用到多層次、多維數(shù)的序列模式中,也可以挖掘其他結(jié)構(gòu)化的模式。五、實(shí)例解析：例 給定如下表所示的序列數(shù)據(jù)庫，分別用freespan和prefixspan算法進(jìn)行計(jì)算，設(shè)最小支持度為2，并給出詳細(xì)過程.table 2sequence_idsequence10203040、利用freespan算法解析：1. (1)找到頻繁項(xiàng)集：頻繁項(xiàng)按支持度降序排列形成頻繁項(xiàng)列表f_list= (注意：由于g：12,所以剪去。) (2)根據(jù)f_list，序列模式集被分為不相交的六個(gè)子集： 1)只包含項(xiàng). 2)含項(xiàng),但不包括以后的項(xiàng)。如正確，但錯(cuò)誤。 3)含項(xiàng),但不包括以后的項(xiàng)。 4）含項(xiàng),但不包括以后的項(xiàng) 5）含項(xiàng),但不包括以后的項(xiàng) 6)包含項(xiàng). (3)分而自治策略。如序列模式 的投影數(shù)據(jù)庫是含有的序列集的子序列，非頻繁項(xiàng)及a后的項(xiàng)也被刪除。在數(shù)據(jù)庫中含的項(xiàng)，但只有:2被保留，其余全部刪除。又如序列模式的投影數(shù)據(jù)庫是含有的序列子集的子序列。其中包括與以前的項(xiàng)所一起組成的子序列。挖掘以投影的數(shù)據(jù),. 再次掃貓數(shù)據(jù)庫，挖掘出長(zhǎng)度為2的序列，如:4,2,:3,:3,:2,:3,接下來我們?cè)俅螔哓堃詾榍熬Y的投影數(shù)據(jù)庫，包括,并以此生成長(zhǎng)度為3的序列模式，即有:3,:3,:2,:2.對(duì)于挖掘數(shù)據(jù)庫如下,此時(shí)我們發(fā)現(xiàn)找不到長(zhǎng)度為4的序列模式。則此時(shí)就到此結(jié)束，即為一個(gè)頻繁序列子集。相似的，對(duì)于其他的序列模式我們也如此的進(jìn)行遞歸的投影。最終得到的頻繁序列子集如下表。 、利用prefixspan算法解析：1.查找長(zhǎng)度為1的序列模式 :4,:4,:4,:3,:3,:32.分割搜索空間序列模式集可按6個(gè)前綴被劃分為六個(gè)子集：1）包含前綴的子集；2）包含前綴的子集；3）包含前綴的子集；4）包含前綴的子集；5）包含前綴的子集；6）包含前綴的子集。3.尋找序列模式的子集。構(gòu)建并遞歸挖掘投影數(shù)據(jù)庫。 (1) 尋找具有前綴的序列模式。 (2) 投影數(shù)據(jù)庫，由4個(gè)后綴序列組成：，。 (3) 掃描投影數(shù)據(jù)庫一遍，找到含有前綴的長(zhǎng)度為2的序列模式，包括：2，：4，：2，：4，：2，：2。(4) 遞歸，所有具有前綴的序列劃分為6個(gè)子集：1）包含前綴的子集；6）包含前綴的子集(5) 投影數(shù)據(jù)庫：。不產(chǎn)生任何頻繁子序列，結(jié)束。投影數(shù)據(jù)庫：，包含前綴的序列模式有：,。即,投影數(shù)據(jù)庫：，。序列模式：， 即，。直到都投完。然后繼續(xù)以沒有結(jié)束的3-序列模式繼續(xù)投影，如投影數(shù)據(jù)庫：，包含前綴的序列模式有：，找到含有前綴的序列模式，包括：。最終序列模式如下圖所示： 前綴投影（后綴）數(shù)據(jù)庫序列模式, ,六：對(duì)prefixspan算法的vc程序的實(shí)現(xiàn) 6.1 prefixspan算法的流程圖類似投影的方法對(duì)其他進(jìn)行投影投影數(shù)據(jù)庫，由4個(gè)后綴序列組成：，。尋找具有前綴的序列模式尋找具有前綴的序列模式第一次掃描數(shù)據(jù)庫s，查找長(zhǎng)度為1的序列模式:4,:4,:4,:3,:3,:3開始給定序列數(shù)據(jù)庫s 及最小持度閾值分割搜索空間序列模式集可按6個(gè)前綴被劃分為六個(gè)子集1）包含前綴的子集；6)包含前綴的子集尋找序列模式的子集。構(gòu)建并遞歸挖掘投影數(shù)據(jù)庫尋找序列模式的子集。構(gòu)建并遞歸挖掘投影數(shù)據(jù)庫(5) 投影數(shù)據(jù)庫：。不產(chǎn)生任何頻繁子序列，結(jié)束。投影數(shù)據(jù)庫：，包含前綴的序列模式有：,。即,投影數(shù)據(jù)庫：，。序列模式：， 即，。直到都投完。掃描投影數(shù)據(jù)庫一遍，找到含有前綴的長(zhǎng)度為2的序列模式，包括：2，：4，：2，：4，：2，：2。 遞歸，所有具有前綴的序列劃分為6個(gè)子集1）包含前綴的子集；6）包含前綴的子集結(jié)束所有的序列模式6.2 算法執(zhí)行結(jié)果本算法只是針對(duì)給定的特定的數(shù)據(jù)庫序列數(shù)據(jù)進(jìn)行挖掘，結(jié)合對(duì)prefixspan算法的理解的基礎(chǔ)上，對(duì)prefixspan實(shí)現(xiàn)了簡(jiǎn)單的編程，在vc的編程環(huán)境下，利用控制臺(tái)程序來實(shí)現(xiàn)對(duì)算法的運(yùn)行。算法的運(yùn)行結(jié)果基本和上述算法的結(jié)果吻合。實(shí)驗(yàn)結(jié)果會(huì)在debug文件下生成一個(gè)output.txt文檔。結(jié)果保存在output.txt文件中6.3 結(jié)果分析通過對(duì)算法的結(jié)果來看，比較更加容易的理解算法的基本性能，但是對(duì)于其他數(shù)據(jù)來說仍然比較吃力。七、結(jié)論與展望序列模式挖掘是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域中一個(gè)較新而且非常活躍的研究分支,有著廣泛的應(yīng)用價(jià)值。文章在介紹了序列模式挖掘的相關(guān)概念后,對(duì)一類序列模式挖掘的2個(gè)經(jīng)典的算法進(jìn)行了描述和分析,不難發(fā)現(xiàn),基于模式擴(kuò)展的方法是個(gè)前途很好的發(fā)展方向。模式擴(kuò)展方法還有很多工作要做,如閉合集挖掘、在特定領(lǐng)域的針對(duì)性研究等等。通過文章我們了解到freespan 和prefixspan 屬于模式增長(zhǎng)方法,它們采用分而治之的方法,大大提高了算法的效率。但在實(shí)際應(yīng)用中,在挖掘過程的不同階段,數(shù)據(jù)集的特點(diǎn),數(shù)據(jù)規(guī)模等因素可能不同,如果根據(jù)各階段的特點(diǎn),選擇與之相應(yīng)的算法,則序列模式挖掘能達(dá)到更好的效果。面對(duì)一個(gè)具體的實(shí)例,例如股票序列分析中,如何根據(jù)不同階段的數(shù)據(jù)集的特點(diǎn)選擇合適的算法,這些數(shù)據(jù)挖掘算法的結(jié)論信息又如何鏈接、傳輸、共享和兼容等,這些問題都是我們今后工作的研究?jī)?nèi)容。八、致謝 九、參考文獻(xiàn) 1呂鋒，張煒偉。4 種序列模式挖掘算法的特性研究，武漢理工大學(xué)學(xué)報(bào)。2006年2月第28卷第2期。2 han j ia-wei, pe i j ian. freespan: frequent pattern -p ro jected sequential pattern mining c /proc of the 2000internat ional conference on know ledge d iscovery and datam ining (kdd). new york: acm press, 2000: 3552-359.3 pe i j ian, han jia-wei, pintoh, etal. prefixspan: mining sequential patterns efficiently by prefix-projectedpattern growth c /proc 2001 int conf data engin ( icde01). los a lam ito s: ieee computer society press,2001: 2152224.4 mannilah, to ivon en h, v erkamo a i. d iscovery of frequent ep isodes in event sequences j . datam in & know ld iscovery, 1996, 1 (3) : 2582289.5 張大海，胡孔法，陳凌。序列模式算法綜述。揚(yáng)州大學(xué)學(xué)報(bào)（自然科學(xué)版），2007年2月第10卷第1期。6 夏明，王曉川，孫永強(qiáng)，金士堯。 序列模式挖掘算法研究。計(jì)算機(jī)技術(shù)與發(fā)展。2006年第16卷第4期。十、附錄算法實(shí)現(xiàn)的主要程序如下：一：prefixspan.cpp#pragma warning(disable: 4786)#include #include #include #include #include #include #include #include #include #include prefixspan.husing namespace std;#define same_set_#define max_fr_size(unsigned int)32768/輸出幫助信息void show_help()std:cout -n prefix span test scriptn -nn usage: tprefixspan_test input_name -smin_supp output_name or n tprefixspan_test input_name -fmin_fr output_namenn default output name is output.txtnn; /讀取輸入數(shù)據(jù)文件到內(nèi)存int read_input(infile &f, sequence_database &db)sequence current_row;item current_item;itemset current_set;std:string buff;std:getline( f, buff);while ( !f.eof()current_item.erase();current_set.clear();current_row.clear();for ( unsigned int i = 0; i buff.size(); +i)if ( | = buffi)/ this means that were at the end of an itemcurrent_set.push_back( current_item);current_item.erase();else if ( = buffi | t = buffi)/ 正處在項(xiàng)集第1項(xiàng)if ( 0 begin();f end(); +is_it)f | (*is_it);f ;return f; / 輸出一個(gè)數(shù)據(jù)庫std:ostream &print_database( std:ostream &f, const sequence_database &db)for ( sequence_database:const_iterator it = db.begin(); it != db.end(); +it)print_sequence( f, (*it);f std:endl;return f; /輸出序列列表std:ostream &print_list( std:ostream &f, const sequence_list l)int k=0;for ( sequence_list:const_iterator it = l.begin(); it != l.end(); +it)if (k%2=0)print_sequence( f, (*it);f begin(); seq_it != row_it-end(); +seq_it)for ( itemset:const_iterator set_it = seq_it-begin(); set_it != seq_it-end(); +set_it) / putting the items in a set = each will occur onceitems_in_the_row.insert( (*set_it); / 在每個(gè)項(xiàng)目該行時(shí)增加支持度for ( set_of_items:iterator items_it = items_in_the_row.begin(); items_it != items_in_the_row.end(); +items_it)+fc(*items_it);/序列擴(kuò)展void extend_prefix_sequence( const sequence &old_prefix, const item& alfa, sequence &new_prefix)new_prefix = old_prefix;itemset tmp_set;tmp_set.push_back( alfa);new_prefix.push_back( tmp_set);/項(xiàng)集擴(kuò)展void extend_prefix_itemset( const sequence &old_prefix, const item &beta, sequence &new_prefix)new_prefix = old_prefix;itemset &tmp_set = new_prefix.back();tmp_set.push_back( beta);/剪切序列前綴void cut_sequence( sequence &s, sequence:iterator &seq_it, itemset:iterator &item_pos)seq_it-erase( seq_it-begin(), +item_pos);if ( seq_it-empty()+seq_it;elseseq_it-push_front( same_set);s.erase( s.begin(), seq_it);/ 構(gòu)造序列數(shù)據(jù)庫void project_database_sequence( const sequence_database &db, const item& alfa, sequence_database &projected_db)projected_db.clear();for ( sequence_database:const_iterator row_it = db.begin(); row_it != db.end(); +row_it)sequence current_row = (*row_it);boo