【正文】 prioriAll算法程序的結(jié)果本程序以I1，I2，I3，I4，I5，I6，I7，I8，I9，I10作為項(xiàng)目集。表七 L1：1序列支持度1422344454L2：表八2序列支持度1 221 341 431 532 322 423 433 524 52L3：表九3序列支持度1 2 321 2 421 3 431 3 522 3 42L4：表十4序列支持度1 2 3 42最大頻繁子序列：表十序列支持度〈1 2 3 4〉2〈1 3 5〉2〈4 5〉22．4 AprioriAll算法程序?qū)崿F(xiàn)2．4．1 AprioriAll算法的描述AprioriAll算法輸入：大項(xiàng)集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫(kù)輸出：所有最長(zhǎng)序列(1) L1={large1 sequence}；//大項(xiàng)集階段得到的結(jié)果(2) For（k=2；Lk1≠0；k++）do begin(3) Ck=Candidate – generate（Lk1）//Ck是從Lk1中產(chǎn)生的新的候選者(4) For each customer – sequence c in the database do//對(duì)數(shù)據(jù)庫(kù)中的每一個(gè)顧客序列c(5) Increment the count of all candidates in Ck that are contained in c；//對(duì)包含于c中Ck內(nèi)的所有候選者計(jì)數(shù)(6) Lk=Candidates in Ck with minimumsuport；//Lk為Ck中滿足最小支持度的候選者(7) End(8) Answer=Maximal Sequences in ∪kLk其中候選集生成算法Ck=Candidate – generate（Lk1）如下：輸入：所有的大（k – 1）序列的集合輸出：候選 Ck(1) Insert into Ck//首先進(jìn)行 Lk1與Lk1的連接運(yùn)算select ,…,from LK1 p,Lk1 q//p和q是Lk1 中兩個(gè)不同的序列串where =,…,=。第1 次掃描時(shí),長(zhǎng)度為1 的頻繁序列模式作為初始的大1 —序列。否則,該項(xiàng)變成s1最后一個(gè)元素的最后一項(xiàng)。產(chǎn)生候選k序列的規(guī)則為將序列s1與序列s2的末項(xiàng)相連。設(shè)有種子集合Lk1,候選序列集合Ck 通過(guò)將 1 種子集合Lk 1與Lk1相連接得到。 定義4：（序列關(guān)聯(lián)規(guī)則）對(duì)于給定的項(xiàng)集I={i1,i2,…Im}以及序列S，T，形如S222。定義3（頻繁序列模式）：給定正整數(shù)V為支持度閾值，如果數(shù)據(jù)庫(kù)中最少有V個(gè)元組包含序列s,即support(s)=V，則稱序列S為序列數(shù)據(jù)庫(kù)D中的一個(gè)(頻繁)序列模式。稱T為S的子序列，S為T的超序列?！北硎尽氨话凇?，序列T是序列S的子序列可記為T208。即序列S包含序列T。定義2(子序列)：序列T＝ti1, ti2,…,tim是另一個(gè)序列S=s1,s2，…,sn的子序列，滿足下面條件:對(duì)于每一個(gè)j,1=j=m1,有ijij+1i且對(duì)于每一個(gè)j，1=j=m存在1=k=n，使得tij205。 序列包含的所有項(xiàng)的個(gè)數(shù)稱為序列的長(zhǎng)度。序列是不同項(xiàng)集的有序排列。序列包含的項(xiàng)的個(gè)數(shù)稱為序列的長(zhǎng)度,長(zhǎng)度為k 的序列記為k 序列。每個(gè)元素由不同項(xiàng)組成。這個(gè)理論是經(jīng)典的數(shù)據(jù)挖掘理論,也是下面將討論的算法的理論依據(jù)。Agrawal等人建立了用于事務(wù)數(shù)據(jù)庫(kù)挖掘的項(xiàng)目集格空間理論,這個(gè)理論的核心思想是:頻繁項(xiàng)目集的子集是頻繁項(xiàng)目集。設(shè)I1?I,項(xiàng)目集I1在D上的支持度(support) 是包含I1的事務(wù)在D中所占的百分比,即support(I1)=||{t∈D|I1?t}||/||D||對(duì)項(xiàng)目集I 和事務(wù)數(shù)據(jù)庫(kù)D,I中所有滿足用戶指定的最小支持(Minsupport)的項(xiàng)目集,即大于或等于Minsupport的I的非空子集,稱為頻繁項(xiàng)目集或者大項(xiàng)目集。關(guān)鍵字：數(shù)據(jù)挖掘 Armorial算法 GSP算法Two Data Mining AlgorithmsAuthor：Liu Jianqing（Grade04,Class04, Information and calculation science，Department of Mathematics，Shaanxi University of Technology，Hanzhong 723000，Shaanxi）Tutor: Zhou TaoAbstract: Sequential pattern mining from the sequence found in the database as a sequence of frequent pattern, it is a kind of important data mining issues, has a very wide application, be used in customer buying behavior, including the analysis of network access mode of analysis, the scientific experiments Analysis, the early diagnosis of disease, natural disasters forecast, DNA sequences deciphered, and so on. The efficiency. In this paper, I was in the sequence pattern mining one of two algorithms to study, namely: Armorial and GSP algorithm. First on the sequence patterns of some basic concepts and principles. And demonstrate through concrete examples of the implementation of the algorithm, then reached into the grasp of understanding. Used vc again based on the programming language and Access database to achieve the end result of running the analysis and synthesis. Keyword: Data mining algorithm Aprioriall algorithm GSP Algorithm目錄１．序列模式挖掘的基本概念 1 2．AprioriAll算法學(xué)習(xí) 2 2．1基本思想 2 2．2 AprioriAll算法的基本思路 2 2．3 應(yīng)用舉例 2 2．4 AprioriAll算法程序?qū)崿F(xiàn) 5 2．4．1 AprioriAll算法的描述 5 2．4．2 AprioriAll算法的程序 6 2．4．3 AprioriAll算法程序的結(jié)果 6 2．4．4 AprioriAll算法程序運(yùn)行結(jié)果分析 7 2．5 AprioriAll算法的本質(zhì) 7 2．6 AprioriAll 算法存在的問(wèn)題 7 3．GSP 算法的學(xué)習(xí) 8 3．1 GSP 算法的基本思想 8 3．2 GSP 算法的基本思路 8 3．3 產(chǎn)生候選序列模式的步驟 8 3．4 后選集計(jì)數(shù) 9 3．5 GSP 算法程序?qū)崿F(xiàn) 10 3．5 ．1 GSP 算法的程序 10 3．5 ．2 GSP 算法程序結(jié)果 10 3．5．4 GSP算法程序運(yùn)行結(jié)果分析 12 3．6 GSP 算法分析 12 3．7 GSP 法存在的問(wèn)題 12 4．對(duì)于Apriori 的算法小結(jié) 12 5．研究發(fā)展展望 12 致謝 13 參考文獻(xiàn) 14 附件一： 15 附件二 32 １．序列模式挖掘的基本概念項(xiàng)目集或稱項(xiàng)集(Itemset)是各種項(xiàng)目組成的集合。并通過(guò)具體的實(shí)例演示算法的執(zhí)行過(guò)程，進(jìn)而達(dá)到掌握理解的成度。本文我就是在對(duì)序列模式挖掘的其中兩種算法進(jìn)行研究，即：Armorial和GSP算法。AprioriAll和GSP算法的研究及實(shí)現(xiàn) [摘要]：序列模式挖掘即從序列數(shù)據(jù)庫(kù)中發(fā)現(xiàn)頻繁子序列以作為模式,它是一類重要的數(shù)據(jù)挖掘問(wèn)題,有著非常廣泛的應(yīng)用前景,被應(yīng)用在包括顧客購(gòu)買行為的分析、網(wǎng)絡(luò)訪問(wèn)模式分析、科學(xué)實(shí)驗(yàn)的分析、疾病治療的早期診斷、自然災(zāi)害的預(yù)測(cè)、DNA 序列的破譯等方面。的效率上。首先講述了序列模式的一些概念及基本原理。再次基礎(chǔ)上采用vc編程語(yǔ)言和Access數(shù)據(jù)庫(kù)進(jìn)行實(shí)現(xiàn)，最后對(duì)程序運(yùn)行結(jié)果進(jìn)行分析和總結(jié)。設(shè)I={i1,i2,…,im}是一個(gè)項(xiàng)目集合,事務(wù)數(shù)據(jù)庫(kù)D={t1,t2,…tn}是由一系列具有惟一標(biāo)識(shí)TID 的事務(wù)組成,每個(gè)事務(wù)ti(i=1,2,…,n)都對(duì)應(yīng)I上的一個(gè)子集。在頻繁項(xiàng)目集中挑選出所有不被其它元素包含的頻繁項(xiàng)目集稱為最大頻繁項(xiàng)目集(Maximum Frequent Itemsets)或最大大項(xiàng)目集(Maximum Large Itemsets)。 非頻繁項(xiàng)目集的超集是非頻繁項(xiàng)目集。設(shè)I={i1,i2,…,im}是項(xiàng)集,ik(1≤k≤m)是一個(gè)項(xiàng),序列S記S=s1,s2…sn,其中sj(1≤j≤n)為項(xiàng)集(也是S的元素)。序列的元素可表示為(i1,i2,…ik)。設(shè)ɑ=a1,a2,…an,β=b1,b2,…bm,如果存在整數(shù)1≤j1j2…jnm,使得a1?bj1,a2?bj2,…an?bjn,a1?bj1則稱序列α為序列β的子序列,又稱序列β包含序列α,記為α?β，序列α在序列數(shù)據(jù)庫(kù)S中的支持?jǐn)?shù)為序列數(shù)據(jù)庫(kù)S中包含序列α的序列個(gè)數(shù), 記為Support(α)，給定支持度閾值ζ,如果序列α在序列數(shù)據(jù)庫(kù)中的支持?jǐn)?shù)不低于ζ,則稱序列α為序列模式,長(zhǎng)度為k 的序列模式記為k模式。 定義1(序列)I={i1,i2,…,im}是項(xiàng)集,ik(1=k=m)是一個(gè)項(xiàng),序列S記為S＝s1,s2,…,sn其中sj(1=j=n)為項(xiàng)集(也稱序列S的元素),即sj?I,每個(gè)元素由不同項(xiàng)組成,序列的元素可表示為(i1,i2,…,ik),若一個(gè)序列只有一個(gè)項(xiàng)，則括號(hào)可以省略。長(zhǎng)度為l 的序列記為l 序列。sk。用符號(hào)“208。S。若一個(gè)序列S不包含在任何其它的序列之中，則稱序列S是最大的。 序列模式挖掘的任務(wù)就是找出數(shù)據(jù)庫(kù)中所有的序列模式，即那些在序列集合中出現(xiàn)頻率超過(guò)最小支持度（用戶指定最小支持度閥值）的子序列。T的表達(dá)式稱為序列關(guān)聯(lián)規(guī)則。設(shè)ss2分別為種子集合Lk 1中序列，ss2能夠相連接得到一個(gè)候選k序列的充要條件為s1拿去首項(xiàng)所得的子序列等于s2拿去末項(xiàng)所得的子序列。若s2的末項(xiàng)為s2的最后一個(gè)元素,則該項(xiàng)變成s1的最后一個(gè)元素。2．AprioriAll算法學(xué)習(xí) 2．1基本思想在每一次掃描(pass) 數(shù)據(jù)庫(kù)時(shí),利用上一次掃描時(shí)產(chǎn)生的大序列生成候選序列,并在掃描的同時(shí)計(jì)算它們的支持度( support) ,滿足支持度的候選序列作為下次掃描的大序列。2．2 AprioriAll算法的基本思路1) 排序階段 利用客戶標(biāo)識(shí)customer 2id作為主關(guān)鍵字以及事務(wù)發(fā)生的時(shí)間transaction 2 time作為次關(guān)鍵字對(duì)數(shù)據(jù)庫(kù)D排序,該步驟將原始的事務(wù)數(shù)據(jù)庫(kù)轉(zhuǎn)換成客戶序列的數(shù)據(jù)庫(kù).2) 發(fā)現(xiàn)頻繁項(xiàng)集階段 利用關(guān)聯(lián)規(guī)則挖掘算法找出所有的頻繁項(xiàng)目集.3) 轉(zhuǎn)換階段 在已經(jīng)轉(zhuǎn)換的客戶序列中,每一個(gè)事務(wù)被包含于該事物中的所大項(xiàng)目集來(lái)替換,如果一個(gè)序列不包含任何大項(xiàng)目集,則在已經(jīng)轉(zhuǎn)換的序列中不應(yīng)該保留這項(xiàng)事務(wù).4) 序列階段 利用核心算法找出所有的序列模式. 2．3 應(yīng)用舉例表一交易發(fā)生的時(shí)間客戶標(biāo)識(shí)購(gòu)買項(xiàng)June 10’042A，BJune 12’045HJune 15’042CJune 20’042D，F(xiàn)，GJune 25’044CJune 25’044C，E，GJune 25’041CJune 30’041HJune 30’044D，GJuly 25’044H重新排序階段表二客戶標(biāo)識(shí)交易時(shí)間購(gòu)買項(xiàng)1June 25’04C1June 30’04H2June 10’04A,B2June 15’04C2June 20’04D,F,G3June 25’04C,E,G4June 25’04C4June 30’04D,G4July 25’04H5June 12’04H由客戶標(biāo)識(shí)及交易發(fā)生的時(shí)間為關(guān)鍵字所排序的數(shù)據(jù)庫(kù)表三客戶號(hào)客戶序列1 (C) (H) 2 (A,B) (C) (D,F,G) 3 (C,E,G) 4 (C) (D,G)