【正文】 (H) 5 (C) (D,G) (H) 客戶序列描述數(shù)據(jù)庫表四頻繁項集映射(C)1(D)2(G)3(DG)4(H)5頻繁項集分別是(C)、(D)、(G)、(D,G)和(H)轉(zhuǎn)換階段：表五客戶標(biāo)識原始客戶序列轉(zhuǎn)換后客戶序列映射后序列1(C)(H){(C)}{(H)}{1}{5}2(A,B)(C)(D,F,G{(C)}{(D)(G),(D,G)}{1}{2,3,4}3(C,E,G){(C),(G)}{1,3}4(C)(D,G)(H)(H{(C)}{(D),(G),(D,G)}{(H{1}{2,3,4}{5}5{(H)}{5}序列階段：表六客戶號客戶序列1{1 5}{2}{3}{4}2{1}{3}{4}{3 5}3{1}{2}{3}{4}4{1}{3}{5}5{4}{5}本例子我們設(shè)定的Minupport=2，其求解過程如下表。(2) delete all sequences c ∈Ck such that some//對候選者進行修剪(修剪的理論是頻繁模式集的子集合也是頻繁的) AprioriAll算法的程序本程序采用了vc開發(fā)工具和Access數(shù)據(jù)庫。Minsupport=，序列數(shù)據(jù)庫如下：其經(jīng)程序運行，結(jié)果如下：2．4．4 AprioriAll算法程序運行結(jié)果分析在本程序中，我以AprioriAll算法的基本原理作為依據(jù)進行編程實現(xiàn)其功能?？梢赃M行初步的應(yīng)用目的。(文獻[1]的作者毛國君于2002 年針對關(guān)聯(lián)規(guī)則挖掘問題提出了項目序列集的概念,并指出使用項目序列集可以簡化挖掘的過程)。候選序列的長度增加1,就需要掃描1次數(shù)據(jù)庫；3) 不易發(fā)現(xiàn)長序列模式,因為隨著需要挖掘的序列模式長度的增加,侯選序列的數(shù)量會成指數(shù)級增長；4）在發(fā)現(xiàn)序列模式的過程中,每次掃描數(shù)據(jù)庫都要在數(shù)據(jù)轉(zhuǎn)換中產(chǎn)生很大的開銷。在第一遍掃描結(jié)束后,該算法知道哪些項是頻繁的,即產(chǎn)生了頻繁1項集,而每個頻繁1項集即形成了頻繁1序列。在產(chǎn)生每一條候選(k+1)序列的同時對其計數(shù),當(dāng)所有的候選(k+1)序列均已產(chǎn)生后,算法根據(jù)每條候選(k+1)序列的計數(shù)確定哪些候選(k+1) 序列形成頻繁(k+1)序列,并作為下一步的種子集合。 GSP 算法的基本思路1 長度為1的序列模式L1，作為初始的種子集。3 重復(fù)第二步,直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止。 C2 222。 C3 222。 C4 222。 …… 產(chǎn)生候選序列模式的步驟1 連接階段：如果去掉序列模式s1的第一個項目與去掉序列模式s2的最后一個項目所得到的序列相同,則可以將s1與s2進行連接，即將s2的最后個項目添加到s1中。例子：下表演示了如何從長度為3的序列模式產(chǎn)生長度為4的候選序列模式。其余的序列均不滿足連接條件。Sequential patternsWith length 3Candidate 4SequencesAfter JoinAfter Pruning(1,2) 3(1,2) (3,4)(1,2) (3,4)(1,2) 4(1,2) 3 51 (3,4)(1,3) 52 (3,4)2 3 5 后選集計數(shù)對于事務(wù)數(shù)據(jù)庫中的每個數(shù)據(jù)序列,需對其每一項進行哈希,從而確定應(yīng)該考察哈希樹哪些葉子節(jié)點中的候選k序列。對每個包含在該數(shù)據(jù)序列中的候選序列,需分成兩個階段:1)向前階段:在d中尋找從s的首項開始的連續(xù)子序列xixj(ij)直至time (xj)time(xi)maxgap,此時轉(zhuǎn)入向后階段,否則,如在d中不能找到s的某個元素,則s不是d的子序列。當(dāng)新找到的xj1仍不滿足time(xj)time(xi)≤maxgap時,從時間值為time(xj1)maxgap后重新搜索xj2 ,同時保持xj3位置不變,直至某位置元素xji滿足條件或x1不能保持位置不變,此時,返回向前階段。B. 當(dāng)x1不能保持位置不變時,向前階段應(yīng)從原x1 位置后重新搜索x1及后續(xù)元素。現(xiàn)假設(shè)最大事務(wù)時間間隔maxgap=30,最小事務(wù)時間間隔mingap=5,滑動時間窗口ws=0,考察候選數(shù)據(jù)序列s =(1,2)(3)(4)是否包含在該數(shù)據(jù)序列中。由于最小事務(wù)時間間隔mingap = 5,故應(yīng)在事務(wù)時間15之后尋找s的下一個元素(3)。由于451030,故轉(zhuǎn)入向后階段,重新尋找元素(1,2)的第一次出現(xiàn)位置。此時轉(zhuǎn)入向前階段,繼續(xù)尋找(3)的下一個元素(4)在事務(wù)時間70之后的第一次出現(xiàn)位置。在考察某個數(shù)據(jù)序列d是否包含某個候選k序列s的兩個階段中,需要在數(shù)據(jù)序列d中不斷尋找候選序列s中的單個元素。此時,若欲尋找某項x在事務(wù)時間t后的第一次出現(xiàn)位置對應(yīng)的事務(wù)時間,只需對x的事務(wù)時間鏈表遍歷直至找出某個大于t的事務(wù)時間。若time(xn)time(x1)≤ws,則已經(jīng)在該數(shù)據(jù)序列d中找到si,可以繼續(xù)在d中尋找s的下一個元素。 GSP 算法程序?qū)崿F(xiàn) GSP 算法的程序本程序采用了vc開發(fā)工具和Access數(shù)據(jù)庫。Minsupport=，序列數(shù)據(jù)庫如下： GSP 算法程序運行結(jié)果3．5．4 GSP算法程序運行結(jié)果分析在本程序中，我以GSP算法的基本原理作為依據(jù)進行編程實現(xiàn)其功能。可以進行初步的應(yīng)用目的。GSP 算法的時間復(fù)雜度與序列中的元素個數(shù)成線性比例關(guān)系,執(zhí)行時間隨數(shù)據(jù)序列中字段的增加而增加,但是增加不明顯。2) 需要對序列數(shù)據(jù)庫進行循環(huán)掃描。4．對于Apriori 的算法小結(jié)從以上兩個算法及AprioriSome 等算法,可以發(fā)現(xiàn)基于Apriori 的候選集生成 測試類方法通常的思路如下:(1) 確定初始種子集(通常的作法是掃描序列數(shù)據(jù)庫,把得到的長度為1 的序列模式L1 作為初始的種子集) 。然后掃描序列數(shù)據(jù)庫,刪除不是序列模式的候選序列模式。(3) 重復(fù)步驟(2) ,當(dāng)找不到新的序列模式,或者沒有候選集產(chǎn)生的時候算法中止。文章在介紹了序列模式挖掘的基于Apriori的兩種基本算法ApriorAll和GSP算法相關(guān)概念后,對兩類序列模式挖掘的幾個經(jīng)典的算法進行了描述和分析,不難發(fā)現(xiàn),基于模式擴展的方法是個前途很好的發(fā)展方向。致謝在我畢業(yè)論文的整個設(shè)計的過程中，我得到系上的大力支持和老師的全力指導(dǎo)，特別是我的指導(dǎo)老師周濤。計算機技術(shù)與發(fā)展學(xué)報，.[7] 都志輝,陳渝,[M]1 北京:清華大學(xué)出版社,2002.[8] Globus Toolkit Globus [EB/OL]. [9] Tuecke S,Czajkowski C,Foster I, Service Speci2fication – Draft 11/4/ Working Group,Global Grid Forum[EB/OL].[10] Joseph J,Fellensein C1 網(wǎng)格計算[M]1 戰(zhàn)曉蘇,張少華,譯1北京:清華大學(xué)出版社,2005.[11] :OGSIpliance on Framework[EB/ OL].附件一：// : implementation of the CAprioriView class//include include include include include include include include include include//include ifdef _DEBUGdefine new DEBUG_NEWundef THIS_FILEstatic char THIS_FILE[] = __FILE__。 nAllFreqItem=0。 inputElm=。 //{{AFX_DATA_MAP(CAprioriView) DDX_Control(pDX, IDC_List_FreqItem, m_List_FreqItem)。 cs){ // TODO: Modify the Window class or styles here by modifying // the CREATESTRUCT cs return CRecordView::PreCreateWindow(cs)。GetDocument()m_aprioriSet。 GetParentFrame()RecalcLayout()。}// CAprioriView printingBOOL CAprioriView::OnPreparePrinting(CPrintInfo* pInfo){ // default preparation return DoPreparePrinting(pInfo)。}void CAprioriView::Dump(CDumpContextamp。}CAprioriDoc* CAprioriView::GetDocument() // nondebug version is inline{ ASSERT(m_pDocumentIsKindOf(RUNTIME_CLASS(CAprioriDoc)))。}endif //_DEBUG// CAprioriView database supportCRecordset* CAprioriView::OnGetRecordset(){ return m_pSet。//獲取數(shù)據(jù)庫中的字段數(shù)目 int nDbCount。 CString strIntToString=。//clock_t表示long型，來定義時間 double timeused。 int nListFreqItemCount=0。 // ClearItem()。//在0列的左邊插入數(shù)據(jù)段的Item項 (1,Count,LVCFMT_LEFT,100)。 return。 //確定的要插入列表中的數(shù)據(jù)項 for(int k=1。k++) { AprioriGen(k,1)。mmCandLargeItemCount[k]。 } m_pSetMoveFirst()。 while(!m_pSetIsEOF()) { TransGenCand(k,nDbCount)。jjnTransCandCount。jj1CandLargeItemCount[k]。 //候選項的頻數(shù) break。 m_pSetMoveNext()。 } stop=clock()。 timeused=(double)tick/CLK_TCK。 (%s%f,strIntToString,timeused)。} void CAprioriView::ClearItem(){ //清除列表顯示的內(nèi)容 ()。 UpdateWindow()。kknMaxSize。 //將ItemCount列清0 for(int kk1=0。kk1++) for(int kk2=0。kk2++) LargeItem[kk1][kk2]=。 CString strTemp,strLeftTemp1,strLeftTemp2。 int nCandFreqItemCount=0。 strTemp2=。 strRightTemp2=。 strLeftTemp1=。 nstrTemp1=0。 nAllFreqItem=nAllFreqItem + LargeItemCount[nCandFreqItem1]。i1LargeItemCount[nCandFreqItem1]。 strTemp1=LargeItem[nCandFreqItem 1][i1]。,39。 strRightTemp1=( ()nstrTemp11)。 for(int j1=i1+1。) { //strTemp2=strCandFreqItem[j1]。 nstrTemp2= (39。)。 strLeftTemp2=(nstrTemp2) 。amp。,39。//組成了新的候選項目集 if(Prune(nCandFreqItem,strTemp)) { CandLargeItem[nCandFreqItem][nCandFreqItemCount++]=strTemp。 } else { j1++。 } } CandLargeItemCount[nCandFreqItem]=nCandFreqItemCount。void CAprioriView::SubItemGen(int strSubItemCount,CString strSubItem)//由實參給形參賦值{//對每個事務(wù)分解成單個項目 CString strTemp1。 CString strReverse。 int nstrRightTemp1。 strT