（計(jì)算機(jī)軟件與理論專業(yè)論文）基于序列編碼頻繁子樹挖掘算法研究.pdf

：啕_ 葉蟲害 基于序列編碼頻繁子樹挖掘算法研究 蘭州大學(xué)碩士學(xué)位論文 摘要 頻繁模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)基本問題，其研究范圍包括事務(wù)、序 列、樹和圖。其方法被廣泛應(yīng)用于許多其它數(shù)據(jù)挖掘任務(wù)中，如相關(guān)性分析。 周期分析，最大模式，閉合模式，查詢，分類，索引等等。 隨著網(wǎng)絡(luò)的快速發(fā)展，頻繁模式的挖掘已經(jīng)推廣到諸如圖和樹這類復(fù)雜模式 的挖掘上，并廣泛的應(yīng)用于生物信息學(xué)、w e b 挖掘、化合物結(jié)構(gòu)分析等領(lǐng)域。 本文對大量頻繁子樹挖掘算法，特別是基于模式增長的子樹挖掘方法進(jìn)行了深入 的研究與分析，主要分析了基于模式增長策略下各種挖掘算法的實(shí)現(xiàn)方法與技 巧，針對模式挖掘過程中侯選模式集的生成和支持度計(jì)算復(fù)雜的特點(diǎn)，以及重復(fù) 運(yùn)行挖掘算法而產(chǎn)生的時(shí)空消耗，提出一個(gè)簡單高效的挖掘算法。 本文提出了利用樹的序列編碼，按照模式增長方法來挖掘頻繁予樹的算法 算法弓l 入基于數(shù)組結(jié)構(gòu)的序列編碼來表示樹和森林：用最左路徑擴(kuò)展方法構(gòu)造完 整的模式增長機(jī)制；能夠系統(tǒng)的根據(jù)樹的拓?fù)浣Y(jié)構(gòu)，在頻繁子樹模式的各個(gè)增長 點(diǎn)上構(gòu)造相應(yīng)擴(kuò)展模式，把侯選模式生成巧妙地轉(zhuǎn)化成有效擴(kuò)展點(diǎn)的查找，這種 方式不但保證了侯選模式生成完全無冗余，而且使支持度計(jì)算變得更加的簡單可 行，在此基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了頻繁子樹挖掘改進(jìn)算法t m g 。本算法與基于a p r i o r i 的e m i n e r 算法的比較，t m g 算法具有更優(yōu)的性能。適用范圍更廣，進(jìn)行簡單 的變換后，可以對不同類型的樹進(jìn)行挖掘。 關(guān)鍵詞：樹挖掘，頻繁模式，p r u f e rs e q u e n c e s ，嵌入鏈表 藺- ，：寥 基于序列編碼頻繁子樹挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 a b s t r a c t f r e q u e n tp a t e mm i n i n gi sab a s i cp r o b l e mo f d a t am i n i n g ，i n c l u d i n gm i n i n g t r d i i g a c t i o n s ，s e q u e n c e s ，扭sa n dg r a p h s t h ea l g o r i t h mf o ri th a sb e e np r e v a l e n t l y u s e di nm a n yo t h e rd a t am i n i n gt a s k , s u c ha sa s s o c i a t i o na n a l y s i s , p e r i o d sa n a l y s i s , m a x i m a la n dc l o s e dp a t e m s ，q u e r y ，c l a s s i f i c a t i o na n di n d e x t e c l m o l o g yc t c w 汕t h er a p i dd e v e l o p m e n to fi n t e m e t f r e q u e n tp a t t e r nm i n i n gg e n e r a l i z e st o m o r ec o m p l e xp a t t e r n sl i k et r e em i n i n ga n dg r a p hm i n i n g m e t h o d sf o rm i n i n g 船q u e n tt r e e sa l ew d i e l yu s e di nb i o i n f o r m a t i c s , w e b m i n i n g c h e m i c a ld a t as t n k ：t i 髓 m 試i n g ，a n d s oo n i nt h i s p a p e r , t h ef r e q u e n tl a r g e - t r e ea l g o r i t h m f o rm i n i n g ， p a r t i c u l a r l yt h o s eb a s e do nt h eg r o w t hp a t t e r n so ft r e e - m i n i n gm e t h o dc o n d u c t e d i n - a e p t l lr e s e a r c ha n da n a l y s i s , b a s e do nt h ea n a l y s i so ft h em a i nm o d eo fg r o w t h s t r a t e g yu n d e rv a r i o u sm i n i n ga l g o r i t h mm e t h o dw i t ht h es k i l l s m i n i n ga g a i n s t c a n d i d a t e sp r o c e s sm o d e la n dt h eg e n e r a t i n gs u p p o r tc o m p u t a t i o n a lc o m p l e x i t y c h a r a c t e r i s t i c s ，r e p e a to p e r a t i o n sa n dm i n i n ga l g o r i t h ma n dt h et i m ec o n s u m p t i o n , w e p r o p o s eas i m p l ea n de f f i c i e n ta l g o r i t h mf o rm i n i n g t h i sp a p e rp r o p o s e st h eu s eo f t h et r e ec o d i n gs e q u e n c e ，i na c c o r d a n c ew i t ht h e m o d eo f g r o w t h 印p f o 卸ht om i n i n gf r e q u e n t - t r e ea l g o r i t h m a l g o r i t h m sb a s e do i lt h e i n t r o d u c t i o no fa na r r a yo fs e q u c n c oc o d i n gt oi n d i c a t et r e e sa n df o r e s t s ；m o s tl e f t w i t ht h ee x p a n s i o np a t hc o n s m u c t e di n t e g r i t yo ft h eg r o w t hm o d e ；a c c o r d i n gt ot h e t r e e t o p o l o g y , i n t h e t r e e - f r e q u 鋤tp a t t e r no fv a t i o mg r o w t hp o i n t s s 打l 1 c l l l r e c o r r e s p o n d i n ge x p a n s i o nm o d ep u tc a n d i d a t e sg e n e r a t i n gm a r v e l o u s l y e f f e c t i v e e x p a n s i o ni n t ot h es e a r c hp o i n t t h i sa p p r o a c hn o to n l ye n s u r e st h a tt h ec a n d i d a t e g e n e r a t i n gc o m p l e t e l yn o n - r e d u n d a n lb u ta l s os u p p o r tt h ec a l c u l a t i o nb e c o m e sm o r e s i m p l ea n df e a s i b l e , o nt h i sb a s i s ，d e s i g na n dr e a l i z a t i o no ft h ef r e q u e n tm i n i n g s u b - t r e ea l g o r i t h mt r e e m i n e r - gi m p r o v e d b a s e do nt h ea l g o r i t h ma n dt h et r e e m i n e r a p r i o r ia l g o r i t h m ，t r e e m i n e r - ga l g o r i t h mh a sf o u n db e t t e rp e r f o r m a n c e ab r o a d e r s c o p e ，as i m p l et r a n s f o r m a t i o n , w ec a l lf o rd i f f e r e n tt y p e so ft r e e st oc a r r yo u t e x c a v a t i o n s k e yw o r d s ：t r e em i n i n g ，f r e q u e n tp a t e r n s ，p r u f e rs e q u e n c e s ，e m b e d d i n gl i s t s - 原創(chuàng)性聲明 本人鄭重聲明：本人所呈交的學(xué)位論文，是在導(dǎo)師的指導(dǎo)下獨(dú)立 進(jìn)行研究所取得的成果。學(xué)位論文中凡引用他人已經(jīng)發(fā)表或未發(fā) 表的成果、數(shù)據(jù)、觀點(diǎn)等，均已明確注明出處。除文中已經(jīng)注明 引用的內(nèi)容外，不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過的科研 成果。對本文的研究成果做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以 明確方式標(biāo)明。 本聲明的法律責(zé)任由本人承擔(dān)。 論文作者簽名： 日期：壟立：蘭! ! 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人在導(dǎo)師指導(dǎo)下所完成的論文及相關(guān)的職務(wù)作品，知識產(chǎn)權(quán)歸 屬蘭州大學(xué)。本人完全了解蘭州大學(xué)有關(guān)保存、使用學(xué)位論文的規(guī)定， 同意學(xué)校保存或向國家有關(guān)部門或機(jī)構(gòu)送交論文的紙質(zhì)版和電子版， 允許論文被查閱和借閱；本人授權(quán)蘭州大學(xué)可以將本學(xué)位論文的全部 或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用任何復(fù)制手段保存和 匯編本學(xué)位論文。本人離校后發(fā)表、使用學(xué)位論文或與該論文直接相 關(guān)的學(xué)術(shù)論文或成果時(shí)，第一署名單位仍然為蘭州大學(xué)。 保密論文在解密后應(yīng)遵守此規(guī)定。 論文作者簽名：逸! 壘自導(dǎo)師簽名：畦! 魚蘭 日期：之竺王j - 膨 ：畸r 土亭基于序列編碼頻繁子樹挖掘算法研究蘭抖l 大學(xué)碩士學(xué)位論丈 1 1 研究背景 第一章緒論 頻繁模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)基本問題。1 9 9 4 年，為了尋找大量商務(wù) 事務(wù)庫中的項(xiàng)集之間的有趣聯(lián)系，a g r a w a i 開創(chuàng)性地提出了關(guān)聯(lián)規(guī)則挖掘問題， 并發(fā)表了著名的 p r i o r i 算法n 1 嘲，用頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則，發(fā)現(xiàn)顧客購買的不 同商品之間的聯(lián)系，分析顧客的購物習(xí)慣，幫助零售商制定營銷策略。1 9 9 5 年， 為描述同一顧客在多次購物所購物品之間可能存在的某種關(guān)聯(lián)關(guān)系，a g r a w a l 又 發(fā)表了序列模式挖掘算法捌。此后，頻繁項(xiàng)集與頻繁序列挖掘算法被廣泛應(yīng)用于 許多其它數(shù)據(jù)挖掘任務(wù)中，如相關(guān)性分析，周期分析，最大模式，閉合模式，查 詢，分類，索引等等。川”眥”本世紀(jì)初，研究者已發(fā)表數(shù)百篇論文，或提出新 的算法，或改進(jìn)己有的算法，來更有效的解決這個(gè)問題?？Эho 。 最近幾年，i n t e r n e te l 益普及，萬維網(wǎng)成為一個(gè)龐大的，分布廣泛的全球性 信息服務(wù)中心。h t m - 和x m l 文檔是其最重要的載體，也為數(shù)據(jù)挖掘提供了新的豐 富資源。w e b 挖掘是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)發(fā)展迅速，更具挑戰(zhàn)性的課題。其內(nèi)容 包括w e b 鏈接結(jié)構(gòu)，w e b 內(nèi)容及w e b 訪問模式挖掘等。由于h t m l 和x m l 文檔本身及頁 面之間的鏈接信息都可以用樹或圖結(jié)構(gòu)來建模，因此，頻繁模式的研究對象，也 自然的從最初的事務(wù)項(xiàng)集和序列，逐漸擴(kuò)展到樹和圖等結(jié)構(gòu)型數(shù)據(jù)o ”“小例“”。如 何發(fā)現(xiàn)挖掘頻繁子樹和頻繁子圖的高效算法，日益成為一個(gè)具有重要理論和實(shí)用 價(jià)值的研究課題。 經(jīng)過十幾年的研究，已經(jīng)奠定了較成熟的頻繁模式挖掘方法的理論基礎(chǔ)。根 據(jù)不同的挖掘策略，方法可分為兩大類：一類是寬度優(yōu)先，逐層挖掘的算法，一 類是深度優(yōu)先，模式增長的算法。通過限制挖掘出的模式彼此之間的關(guān)系，又可 分為完全頻繁模式挖掘，最大頻繁模式挖掘和頻繁閉合模式挖掘。麗根據(jù)挖掘?qū)?象的不同，方法可分為頻繁項(xiàng)集挖掘，頻繁序列挖掘，頻繁予樹挖掘和頻繁子圖 挖掘等。 本文圍繞頻繁子樹挖掘技術(shù)展開研究。重點(diǎn)研究利用模式增長方法在有序樹 構(gòu)成的森林中挖掘嵌入式頻繁子樹；在無序樹構(gòu)成的森林中挖掘直接頻繁子樹： 萄t ，：掌 基于序列編碼頻繁子樹挖掘算法研究 蘭州大學(xué)頤士學(xué)位論文 及相關(guān)的實(shí)現(xiàn)技術(shù)等系列關(guān)鍵問題。 1 2 本文研究的內(nèi)容和創(chuàng)新之處 根據(jù)前文對頻繁模式挖掘研究現(xiàn)狀的分析，對現(xiàn)有的大多數(shù)頻繁模式挖掘 算法進(jìn)行研究，針對算法中存在多次掃描數(shù)據(jù)庫產(chǎn)生和篩選候選模式集、時(shí)空效 率低，動(dòng)態(tài)維護(hù)復(fù)雜，不利于更新，特別是對于海量數(shù)據(jù)、長模式的挖掘和維護(hù) 效率低等問題。開展本文的研究工作，主要圍繞三個(gè)主題展開：一是待挖掘的半 結(jié)構(gòu)化數(shù)據(jù)在內(nèi)存中的管理與組織；二是基于序列的模式增長頻繁子樹挖掘算法 的設(shè)計(jì)與實(shí)現(xiàn)；三是高效內(nèi)存管理程序的設(shè)計(jì)。本文的研究主要成果和創(chuàng)新之處 包括以下幾個(gè)方面： l 、基于樹的編碼序列，在原來算法的基礎(chǔ)上改進(jìn)了頻繁子樹挖掘算法t m g 。 實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法與原算法相比性能更優(yōu)。適用泛圍更廣，可以對 不同類型的樹進(jìn)行挖掘。 2 、提出了一種新侯選子樹生成機(jī)制，這種侯選子樹的生成是建立在對樹進(jìn) 行序列編碼的基礎(chǔ)上，利用最左擴(kuò)展的方法，把侯選模式生成巧妙地轉(zhuǎn)化成有效 擴(kuò)展點(diǎn)的查找，實(shí)踐證明這種產(chǎn)生的侯選子樹的方法是簡單、有效的，并且所產(chǎn) 生的侯選集是完全的、無冗余的。 3 、在程序?qū)崿F(xiàn)中，對內(nèi)存空間的頻繁申請與釋放將會耗費(fèi)大量的時(shí)間，為 了節(jié)約這些開銷，本文提出的序列編碼和嵌入鏈表數(shù)據(jù)結(jié)構(gòu)，使內(nèi)存管理利用更 加的容易高效，從而實(shí)現(xiàn)了申請到的內(nèi)存空間的高效利用，這樣就可以避免每次 節(jié)點(diǎn)空間的申請與釋放都要通過操作系統(tǒng)與硬件通訊，使程序的效率有了很大的 提高。 實(shí)驗(yàn)結(jié)果表明本文提出的p r u f e r 序列( p r 誦c rs e q u e n c e s ) “”和嵌入子鏈表 ( e m b e d d i n gl i s t s ) 是兩種非常有效的數(shù)據(jù)結(jié)構(gòu)，使算法具有高性能緩存記憶 ( h i g h l y c a c h e c o n s c i o u s h c c ) 功能，h c c 起到了高效內(nèi)存管理利用的作用， t m o 算法是高效的、用途廣泛的頻繁子樹挖掘算法。 1 3 本文的組織結(jié)構(gòu) 第1 章：首先介紹了本文的研究工作的背景，接著闡述了本文的主要研究內(nèi) - 2 - 萄，? ：亨 基于序列編碼頻繁子樹挖掘算法研究蘭州文學(xué)碩士學(xué)位論文 容、研究成果和創(chuàng)新之處。 第2 章：頻繁子樹挖掘問題研究。首先簡單介紹了頻繁模式挖掘的相關(guān)研究 和工作進(jìn)展；其次，認(rèn)真分析了結(jié)構(gòu)化數(shù)據(jù)挖掘問題和基本過程；在此基礎(chǔ)上， 詳細(xì)研究了基于模式增長頻繁子樹挖掘問題，給出了相關(guān)術(shù)語的定義，認(rèn)真研究 了t r e e m i n e r 和t r e e c ，r o w t h 算法對子樹挖掘的策略和實(shí)現(xiàn)方式，深入探討了基 于模式增長的頻繁子樹挖掘算法。 第3 章：t m g 算法的設(shè)計(jì)與實(shí)現(xiàn)。對大量頻繁子樹挖掘算法進(jìn)行研究，詳 細(xì)分析了不同算法之間事務(wù)數(shù)據(jù)庫在內(nèi)存中的存儲形式，特別對多種利用模式增 長策略子樹挖掘算法進(jìn)行了比較，分析了模式增長過程中不同的方法及特點(diǎn)。在 比較分析的基礎(chǔ)上，吸取已有數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)，找到了兩種新的數(shù)據(jù)結(jié)構(gòu)p l 1 f c r s e q u e n c e s 和e m b e d d i n gl i s t s ，在兩種結(jié)構(gòu)的基礎(chǔ)上，提出了新的高效的頻繁子 樹挖掘算法1 m g 算法。然后給出算法描述、實(shí)現(xiàn)與性能分析。 第4 章：總結(jié)和下一步研究工作展望。主要對本論文的研究工作進(jìn)行總結(jié)， 并對下一步的工作進(jìn)行展望。 ；啕- ，蟲害 基于序列編碼頻繁子樹挖掘算法研究 蘭州大學(xué)硬士學(xué)位論文 第二章頻繁子樹挖掘問題研究 2 1 頻繁模式挖掘相關(guān)研究 本節(jié)介紹頻繁模式挖掘領(lǐng)域相關(guān)研究動(dòng)態(tài)。首先介紹傳統(tǒng)的頻繁項(xiàng)集和頻繁 序列模式挖掘的研究概況，接著介紹時(shí)間序列模式挖掘的常用方法，然后介紹已 有的頻繁最大模式和頻繁閉合模式的主要方法，最后介紹頻繁子圖的研究動(dòng)態(tài)。 2 1 1 頻繁項(xiàng)集挖掘 頻繁項(xiàng)集挖掘一直是數(shù)據(jù)挖掘領(lǐng)域的重點(diǎn)課題，所做的工作與取得的成果也 比較多。頻繁項(xiàng)集挖掘最初應(yīng)用于在事務(wù)庫中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的a p r i o r i 算法。由 r a g r a w a l 等人首先提出來。關(guān)聯(lián)規(guī)則反映了大量數(shù)據(jù)中項(xiàng)目集之間有趣的關(guān)聯(lián) 或相關(guān)聯(lián)系。識別或發(fā)現(xiàn)事務(wù)庫中所有的頻繁項(xiàng)集是關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法的核心和 關(guān)鍵。 a p r i o r i 算法是最有影響的挖掘頻繁項(xiàng)集的算法。其核心思想基于頻繁項(xiàng)集 的先驗(yàn)知識：即頻繁項(xiàng)集的所有非空子集必須也是頻繁的。算法使用一種逐層搜 索的迭代方法，將頻繁k 一項(xiàng)集用于探索頻繁( k + 1 ) 一項(xiàng)集。算法首先找出頻繁i 一 項(xiàng)集的集合，記做l l 。l 。用于尋找頻繁2 項(xiàng)集合l ：，然后l z 用于找l 。，如此下去， 直到不再產(chǎn)生頻繁k 項(xiàng)集。找每個(gè)l 需要掃描一遍數(shù)據(jù)庫。 p r i o r i 算法的一個(gè)巨大優(yōu)勢是其挖掘大型事務(wù)庫的能力。不需要將事務(wù)庫 讀入內(nèi)存就可以完成挖掘工作。然而該算法需要多次掃描數(shù)據(jù)庫，掃描次數(shù)等于 發(fā)現(xiàn)的最長的頻繁項(xiàng)集的項(xiàng)的個(gè)數(shù)。鑒于a p r i o r i 算法處理的數(shù)據(jù)庫的量非常大， 算法的效率顯得十分重要。許多研究人員對算法的連接和剪枝過程進(jìn)行各種優(yōu) 化，產(chǎn)生了很多變體。他們通常針對如下幾個(gè)目標(biāo)中的一個(gè)或多個(gè)進(jìn)行改進(jìn)優(yōu)化： 最小化掃描數(shù)據(jù)的次數(shù)；最小化候選集數(shù)量；最小化計(jì)算每個(gè)候選集頻率所需的 時(shí)間。 與a p r i o r i 算法所不同的是，f p - g r 6 w t h 算法和t r e e p r o j e c t i o n 算法采用深度 優(yōu)先的策略挖掘頻繁項(xiàng)集。f p - g r o w t h 算法思想是：先統(tǒng)計(jì)出頻繁l 項(xiàng)集( 集合中的 元素稱為頻繁項(xiàng)) ，將其壓縮到內(nèi)存中的一棵頻繁模式樹( f p - - 樹) ，同時(shí)保留項(xiàng) 藺- - j 天害 基于序列編碼頻繁子樹挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 間關(guān)聯(lián)信息；然后，通過關(guān)聯(lián)信息，將壓縮后的數(shù)據(jù)庫分成一組條件模式庫。每 一個(gè)條件模式庫與一個(gè)頻繁項(xiàng)關(guān)聯(lián)。之后使用稱為f p - g r o w t h 的方法從頻度最小 的頻繁項(xiàng)開始自底向上，在條件模式庫上進(jìn)行頻繁項(xiàng)集挖掘。研究表明f p - g r o w t h 算法大約比a p r i o r i 算法快一個(gè)數(shù)量級，同時(shí)也優(yōu)于t r e e p r o j e c t i o n 算法。 f p - g r 鉀t h 方法不足在于：當(dāng)存在許多長面復(fù)雜的模式時(shí)，f p - g r o w t h 算法需要遞 歸構(gòu)造的條件樹數(shù)量巨大，時(shí)空代價(jià)較高。 2 1 2 序列模式挖掘 序列模式挖掘同樣由r a g r a w a t 首先提出，之后引起了大家的重視。序列模 式與關(guān)聯(lián)規(guī)則之間的區(qū)別在于后者描述的是在一次購物中所購買物品之間的關(guān) 聯(lián)關(guān)系，即事務(wù)內(nèi)部的關(guān)聯(lián)模式。而前者則描述同一顧客在多次購物所購物品之 間可能存在的某種關(guān)聯(lián)關(guān)系，即事務(wù)之間的關(guān)聯(lián)模式。顯然，所有頻繁序列的集 合是所有頻繁項(xiàng)目集的超集。 a g r a w ai 在a p rio ri 算法的基礎(chǔ)上提出了三個(gè)序列模式挖掘算法 p r i o r i a i i p r i o r i s o m e 和d y n 硼i c s o m e 。這些算法也繼承了 p r i o r i 算法固有的 弱點(diǎn)，需要多遍掃描數(shù)據(jù)庫，需要代價(jià)較高的候選模式產(chǎn)生與測試操作等。文獻(xiàn) o “提出了s p a d e 算法，以深度優(yōu)先的策略挖掘模式。其將序列數(shù)據(jù)庫組織成新穎 的倒排格式，將支持度計(jì)算操作轉(zhuǎn)化為事務(wù)i d 和項(xiàng)i d 2 _ 間的求交運(yùn)算，算法僅需 要三次掃描數(shù)據(jù)庫，性能與類如r i o r i 算法相比有了很大提高。 2 1 3 時(shí)間序列模式挖掘 隨著數(shù)據(jù)挖掘研究領(lǐng)域的拓展，針對時(shí)間序列數(shù)據(jù)的數(shù)據(jù)挖掘研究e l 益受到 人們的關(guān)注。所謂時(shí)間序列類型數(shù)據(jù)就是按照時(shí)間先后順序排列各個(gè)觀測記錄的 數(shù)據(jù)集。h e i k k im a n n i l a 等將事物數(shù)據(jù)庫中關(guān)聯(lián)模式和序列模式的算法思想引入 到事件序列中，提出了從事件序列中發(fā)現(xiàn)頻繁情節(jié)的算法“”。 c l a u d i ob e t t i n i 等對時(shí)間序列中靜態(tài)結(jié)構(gòu)的發(fā)現(xiàn)問題進(jìn)行了研究，與 h e i k k im a n n i l a 不同的是，b e t t i n i 允許用戶指定感興趣的事件結(jié)構(gòu)，并在其算 法中增加了對多時(shí)間粒度關(guān)系的支持。為實(shí)現(xiàn)多粒度挖掘，b e t t i n i 定義了帶時(shí) 間粒度的靜態(tài)約束和帶時(shí)間粒度的事件結(jié)構(gòu)，在計(jì)時(shí)自動(dòng)機(jī)基礎(chǔ)上提出了一種稱 藺- r ) ：寥基于序列編碼頻繁子樹挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 為帶時(shí)間粒度的計(jì)時(shí)自動(dòng)機(jī)搜索算法，實(shí)現(xiàn)了多粒度復(fù)雜結(jié)構(gòu)的發(fā)現(xiàn)。 g a u t a md a s 等對從時(shí)間序列中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則進(jìn)行了研究倥叼，這里的規(guī)則是指 對時(shí)間序列中不同模式問關(guān)系的一種描述，文獻(xiàn)嘲的主要貢獻(xiàn)在于給出了個(gè)將 原始時(shí)間序列轉(zhuǎn)換成一個(gè)由各個(gè)模式標(biāo)示符組成的符號序列的一般性方案，該方 案由三部分組成，即分割，聚類和符號替換。然后采用序列模式發(fā)現(xiàn)算法實(shí)現(xiàn)了 符號序列中規(guī)則的發(fā)現(xiàn)。 文獻(xiàn)皿1 首次提出了在一種基于互關(guān)聯(lián)后繼樹模型的時(shí)序特征模式挖掘方 法。該方法在序列分段上，采用了一種新穎的、基于重要點(diǎn)的時(shí)問序列線段化算 法；在符號化過程中，采用基于相對斜率的局部符號化方法。既減少計(jì)算復(fù)雜度， 又避免了噪聲的影響。在挖掘算法實(shí)現(xiàn)上，根據(jù)序列特征模式的有序性和重復(fù)性， 提出了一種無須生成大量的候選模式集的互關(guān)聯(lián)后繼樹挖掘算法。 而針對更有分析價(jià)值的多序列關(guān)聯(lián)模式，文獻(xiàn)嘲進(jìn)一步提出一種新穎的關(guān)聯(lián) 模式挖掘方法。該方法利用a l l e n 區(qū)間邏輯關(guān)系來描述時(shí)聞序列模式的關(guān)聯(lián)關(guān)系， 避免了傳統(tǒng)方法在關(guān)聯(lián)關(guān)系描述上的非同步性；然后通過時(shí)間觀測窗口，構(gòu)造出 一種包含并行模式和串行模式特殊形式的模式序列。最后，在此基礎(chǔ)上構(gòu)造一種 廣義的互關(guān)聯(lián)后繼樹模型，實(shí)現(xiàn)多序列關(guān)聯(lián)模式的挖掘。 2 1 4 最大項(xiàng)集和閉合項(xiàng)集模式挖掘 由于完全頻繁項(xiàng)集數(shù)量眾多，因此，降低候選項(xiàng)目集的數(shù)量是減小開銷的最 好手段。由于最大頻繁項(xiàng)目集中己經(jīng)隱含了所有頻繁項(xiàng)目集，所以可把發(fā)現(xiàn)頻繁 項(xiàng)目集的問題轉(zhuǎn)化為發(fā)現(xiàn)最大頻繁項(xiàng)目集的問題。所謂最大頻繁模式m 。即，不 存在一個(gè)m 的超集m ，使得m 也是頻繁的。某些數(shù)據(jù)挖掘應(yīng)用僅需發(fā)現(xiàn)最大頻 繁項(xiàng)目集，而不必發(fā)現(xiàn)完全頻繁項(xiàng)目集，因而發(fā)現(xiàn)最大頻繁項(xiàng)目集對數(shù)據(jù)挖掘具 有一定意義。 目前已經(jīng)提出的可用于發(fā)現(xiàn)最大頻繁項(xiàng)目集的算法有m a x - h l i n e r 伽， p i n c e r s e a r c h m l ，d m f i 以及m a f i a 1 等。 m a p m i n e r 突破了傳統(tǒng)的自底向上的搜索策略，盡可能早地對項(xiàng)目集進(jìn)行修 剪。但其未利用自頂向下的信息進(jìn)行修剪，且未對最大頻繁項(xiàng)候選集( m f c s ) 進(jìn)行 適當(dāng)?shù)呐判?，產(chǎn)生了多余的最大頻繁候選項(xiàng)目集。 藺村，：害 基于序列編碼頻繁子樹挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 p i n c e r s e a r c h 采用了自底向上和自頂向下的雙向搜索策略，不過其第k 次的 m f c s 是由k - 1 次的m f c s 中的非頻繁項(xiàng)目集去掉一個(gè)元素來生成的，因此產(chǎn)生了過 多的無用候選項(xiàng)目集。 d m f i 有效地把自底向上和自頂向下的搜索策略進(jìn)行了合并，該算法為海量數(shù) 據(jù)庫中發(fā)現(xiàn)最大頻繁項(xiàng)目集和僅需要發(fā)現(xiàn)最大頻繁項(xiàng)目集的數(shù)據(jù)挖掘應(yīng)用提供 了一種有效而快速的算法。 m a f i a 使用位圖表示法，將原始數(shù)據(jù)庫重新組織成項(xiàng)一事務(wù)列表這樣一種倒排 結(jié)構(gòu)，通過對位圖求交來計(jì)算支持度，是一種很新穎的挖掘方法。不過，為節(jié)約 空間，要混合使不同長度的位圖，增加了算法的復(fù)雜性，并且，位圖表示法是節(jié) 約空間仍有待探討 最大頻繁模式丟失了支持度信息。在某些應(yīng)用中，挖掘頻繁閉合模式更有意 義嘲。簡單的說，所謂頻繁閉合模式c ，即，不存在一個(gè)p 的超集c ，使得c 與c 的支持度相同。頻繁閉合模式包含有完全頻繁模式的所有信息，但數(shù)量卻可 能比完全頻繁模式少幾個(gè)數(shù)量級。 以a p r i o r i 算法為基礎(chǔ)，p a s q u i e r m l 提出t a - c l o s e 算法，采用自底向上、寬 度優(yōu)先的搜索策略，通過構(gòu)造“生成子”集合，逐層枚舉所有的頻繁閉合模式。 通過引入剪裁技術(shù)減小搜索范圍。 p e i 以f p - g r o w t h 方法為基礎(chǔ)，提出c l o s e t 算法在f p - 樹上挖掘頻繁閉合項(xiàng) 集。然而由于采用動(dòng)態(tài)構(gòu)建條件f p - 樹，其數(shù)目同模式長度成正比，在稠密數(shù)據(jù) 上，動(dòng)態(tài)樹生成與維護(hù)開銷較大。 z a k i 等人提出t c h a r m 算法側(cè)，將事務(wù)庫中的項(xiàng)用事務(wù)列表這種倒排格式表 示，將支持度計(jì)算操作轉(zhuǎn)化為集合交運(yùn)算，并引入d i f s e t 技術(shù)減少存儲開銷和提 高求交運(yùn)算的效率。 所有這些方法，都必須將己經(jīng)發(fā)現(xiàn)的頻繁閉合項(xiàng)集緩存起來，以備對新發(fā)現(xiàn) 的頻繁項(xiàng)進(jìn)行閉包測試，但仍缺乏有效的組織方法。 2 1 5 頻繁子圖挖掘 完全頻繁子圖挖掘問題首先由i n o k u c h i 提出，同時(shí)給出了a g m 算法1 。a g m 算法使用基于a p r i o r i 的方法挖掘頻繁子圖模式。 ；鷺村：掌 基于序列編碼頻繁子樹挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 k u r a m p c h i 和k a r y p i s 貝f 提出了一個(gè)更有效的f s g 算法洶1 來解決同樣的問題。 其主要思路是：利用一種有效的稀疏圖表示方法來減小圖的存儲和計(jì)算開銷。利 用每次增長一條邊的方法增大子圖的尺寸，使其能夠有效地產(chǎn)生候選模式。 利用規(guī)范化編碼方法，將圖的鄰接鏈表或鄰接矩陣表示轉(zhuǎn)化為序列表示，并 且保障兩個(gè)同構(gòu)子圖的序列表示相同，從而避免了有關(guān)同構(gòu)予圖判定的復(fù)雜計(jì) 算。f s g 算法亦采取寬度優(yōu)先搜索策略。實(shí)驗(yàn)表明，f s g 算法效率較a g m 舅j ：法有較 大提高。 挖掘頻繁子圖的另一個(gè)著名的算法是g s p a n 算法。此算法堅(jiān)持了深度優(yōu)先， 模式增長方法優(yōu)于寬度優(yōu)先，候選模式產(chǎn)生與測試方法的基本觀點(diǎn)。其基本思想 是：首先，在圖與圖的表示之間建立起一種嚴(yán)格的字典式順序。其次，將每個(gè)圖 映射到最小d f s ( d e p t hf i r s ts e a r c h ) 編碼。此編碼方法能夠唯一地表示一個(gè)子 圖。然后，從頻繁一l 模式( 只有一條邊的頻繁子圖) 出發(fā)，采用深度優(yōu)先，模式增 長的策略，搜索所有可能模式的最d 、d f s 編碼。對于己發(fā)現(xiàn)的頻繁子圖，在其最 j j 、d f s 編碼的末尾附加一條新的邊，就可以探索可由其增長得到的頻繁模式，直 到其不可能再增長為尺寸更大的頻繁子圖。最后，利用模式增長的方法完成整個(gè) 搜索空間挖掘工作。最小化d f s 編碼方法避免了同構(gòu)子圖的復(fù)雜計(jì)算。深度優(yōu)先， 模式增長的方法避免了候選模式的生成和測試。因此g s p a n 成為目前最有效的圖 挖掘算法之一。實(shí)驗(yàn)表明，其效率是f s g 算法的1 5 3 0 0 倍，是判定頻繁子圖挖掘 效率的一個(gè)標(biāo)志性算法。 a d i 算法嘶1 改進(jìn)t g s p a n 算法，其將有效的兩層索引結(jié)構(gòu)引入g s p a n , 既擴(kuò)展了 其挖掘大型圖庫的能力，又提高了算法的計(jì)算性能。y a r 避- 步提出了挖掘頻繁 閉合子圖的算法c l o s e g - r a p h 0 ，并探討了將頻繁予圖應(yīng)用于索引和查詢的技術(shù)。 2 2 頻繁子樹挖掘問題綜述 數(shù)據(jù)挖掘關(guān)注從龐大數(shù)據(jù)集中尋找有用的模式和關(guān)系。然而當(dāng)今的大部分?jǐn)?shù) 據(jù)挖掘算法僅僅能夠處理具有固定結(jié)構(gòu)的數(shù)據(jù)。這類數(shù)據(jù)中數(shù)據(jù)模式往往己經(jīng)事 先定義，稱為結(jié)構(gòu)化數(shù)據(jù)。 在w e b 數(shù)據(jù)庫和生物信息學(xué)數(shù)據(jù)庫中，數(shù)據(jù)往往缺乏某種固定的結(jié)構(gòu)。常常 稱這種數(shù)據(jù)為半結(jié)構(gòu)化數(shù)據(jù)。在結(jié)構(gòu)化數(shù)據(jù)庫中，由于所有的數(shù)據(jù)項(xiàng)具有相同的 藺孵蟲害 基于序列編碼頻繁子樹挖掘算法研究 蘭州大學(xué)碩士學(xué)位論文 結(jié)構(gòu)，因此結(jié)構(gòu)信息在標(biāo)準(zhǔn)的數(shù)據(jù)挖掘中并不重要。對于半結(jié)構(gòu)化數(shù)據(jù)，數(shù)據(jù)項(xiàng) 的結(jié)構(gòu)在其語義中卻起著至關(guān)重要的作用。 頻繁子樹結(jié)構(gòu)往往能夠給出半結(jié)構(gòu)化數(shù)據(jù)庫的概要信息。這類信息可以用來 構(gòu)成查詢，也可以引導(dǎo)索引的生成，還可以作為對數(shù)據(jù)庫進(jìn)行分類或聚類的基礎(chǔ)。 不過，頻繁子樹挖掘并不像頻繁項(xiàng)集挖掘那樣直觀明了。因?yàn)橛性S多的因素會對 算法產(chǎn)生重大影響，比如： 樹的類型如何定義? 樹的孩子節(jié)點(diǎn)之間是否有序? 某棵樹是另一棵樹的“子樹”的標(biāo)準(zhǔn)是什么? 這類問題的答案與實(shí)際應(yīng)用背景有關(guān)。簡單的說，孩子節(jié)點(diǎn)之間存在前后關(guān) 系的樹稱為有序樹；子樹的父子節(jié)點(diǎn)保持父樹的祖先一后代關(guān)系時(shí)稱為嵌入式子 樹；子樹父子節(jié)點(diǎn)保持父樹的父子關(guān)系時(shí)稱為直接子樹。不同回答，不僅挖掘的 結(jié)構(gòu)大不一樣，而且搜索空間和刪枝策略也大不相同。 2 3 頻繁子樹挖掘算法介紹 頻繁子樹模式挖掘直到最近才引起大家的重視，相關(guān)的研究文獻(xiàn)也不太多。 文獻(xiàn)呻1 用麴p r i o r i 算法來解決這個(gè)問題。一個(gè)被稱為a p r i o r i 的性質(zhì)用來減少候 選頻繁模式的生成：每個(gè)頻繁模式的子模式也一定是頻繁的。不過，正如文獻(xiàn)嘲 在頻繁項(xiàng)集挖掘問題中指出的，當(dāng)存在大量復(fù)雜模式時(shí)，候選模式產(chǎn)生一測試策 略的性能會嚴(yán)重退化。 z a k i 和a s a i 幾乎同時(shí)提出了有效挖掘頻繁子樹的方法洶3 嘲，他們采用一種非 常有用的最右路徑擴(kuò)展機(jī)制來產(chǎn)生候選樹模式。在文獻(xiàn)中，z a k i 給出了兩種算 法，t r e e m i n e r 和p a t e r n m a t c h e r ，用來挖掘嵌入式頻繁子樹。 p a t e r n m a t c h e r 是類a p r i o r i 的寬度優(yōu)先挖掘算法。而t r e e m i n e r 貝l j 采用深度優(yōu) 先的挖掘策略。其利用一種樹的倒排表示方法，也即用s c o p e l i s t 結(jié)構(gòu)，來重新 組織數(shù)據(jù)庫，通過對s c o p e - l i s t 求交來進(jìn)行有效的支持度計(jì)算。t r e e m i n e r 的效 率比p a t e r r i m a t c h e r 高出大約4 - 2 0 倍，是迄今所發(fā)表的算法中最高效的挖掘嵌入 式頻繁子樹的方法之一。然而，盡管其非常有效，t r e e m i n e r 仍采用的是代價(jià)較 高的候選模式產(chǎn)生一測試策略。對s c o p e - l i s t 的求交運(yùn)算也是這個(gè)算法的一個(gè)瓶 頸。 篙- r 幺霧 基于序列編碼頻繁子樹挖掘算法研究 蘭州大學(xué)碩士學(xué)位論文 研究表明，利用靜態(tài)投影技術(shù)，在靜態(tài)i s + - 樹上挖掘頻繁模式，可以取得比 在動(dòng)態(tài)構(gòu)建的f p 樹上挖掘頻繁模式更好的效果。那么，用模式增長的方法和靜 態(tài)投影技術(shù)挖掘樹模式，是否更加有效? w a n g 首先嘗試用模式增長方法來解決這個(gè)問題，在p r e f i x s p a n 序列模式挖 掘算法基礎(chǔ)之上，提d j c h o p p e r 和x s p a n e r 兩種算法嘲。然而嚴(yán)格地來講，這兩種 算法是序列意義上的模式增長。即，先將樹看作是一個(gè)用先序表示的序列，然后 在序列上應(yīng)用模式增長方法。由于有許多不同拓?fù)浣Y(jié)構(gòu)的樹可能表示相同的序 列，所以算法依然需要使用字串匹配操作完成支持度計(jì)算，這極大的影響了算法 的效率，因此并不是真正的模式增長算法。 用模式增長方法挖掘樹模式，所面臨的主要困難在于： 怎樣表示樹和樹的集合，才有利于模式增長方法和投影技術(shù)的利用7 如何既無冗余，又完全地構(gòu)造頻繁模式生成空間7 使用怎樣的策略將頻繁k 一樹模式( 包含k 個(gè)節(jié)點(diǎn)) ，增長為頻繁( k + 1 ) 一樹模 式。 最后一點(diǎn)最困難也最重要。在頻繁項(xiàng)集挖掘中，由于每個(gè)事務(wù)中不存在重復(fù) 的項(xiàng)，因此，模式每增加一項(xiàng)，必然生成唯一的一個(gè)新模式。然而，樹的不同節(jié) 點(diǎn)可以有相同的標(biāo)識符。且樹的拓?fù)浣Y(jié)構(gòu)使得其可能有許多個(gè)“增長點(diǎn)”，相同 標(biāo)識符節(jié)點(diǎn)附加在不同的增長點(diǎn)上便會生成一個(gè)不同的模式。因此，用模式增長 方法挖掘樹模式，無論從算法復(fù)雜度，還是從算法本身的復(fù)雜性，都比挖掘頻繁 項(xiàng)集大得多。 2 3 1 相關(guān)問題定義 樹表示為三元組t ( r ，n ，b ，其中( 1 ) n 是帶標(biāo)識符節(jié)點(diǎn)集。標(biāo)志符取自集合l ， 不同節(jié)點(diǎn)可以有相同標(biāo)識符；( 2 ) r n 是唯一的根節(jié)點(diǎn)：( 3 ) b 是樹中分枝的集 合，且對每個(gè)分枝b = ( u i ，u ：) b ，都有u - ，u ：en 。稱u 為u ：的父親，u 2 為u 1 的孩子，若孩子之間有序，則稱之為有序樹。為簡潔起見，用t ( r ) 或t 表示以r 為根的樹。樹中節(jié)點(diǎn)個(gè)數(shù)稱為樹的大小，表示為。樹的集合稱為森林。數(shù)據(jù) 庫d 就是森林。當(dāng)r 不唯一時(shí)稱為自由子樹。 ；鶯- f 蟲害 基于序列編碼頻繁子樹挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 路徑p 是樹t ( r ) 的相連分技的集合，記為( u 。，u 。，u j ，且( u 。，r e + 1 ) eb 。節(jié) 點(diǎn)v 的層次定義為從r 到v 的路徑的長度，記為k 。稱從r 到v 的路徑上的任意節(jié)點(diǎn)u 為v 的祖先，v 為u 的后代。稱先序遍歷有序樹時(shí)節(jié)點(diǎn)對應(yīng)的遍歷次序?yàn)楣?jié)點(diǎn)序。 著t ( r ) 的最后節(jié)點(diǎn)為w ，稱從r 到w 的路徑為t ( r ) 的最右路徑。節(jié)點(diǎn)u 的轄域區(qū)問定 義為一段區(qū)間 l ，r ，其中，l 是u 本身在節(jié)點(diǎn)序中位置，r 是u 的最后一個(gè)后代的 位置。節(jié)點(diǎn)u 轄域內(nèi)的節(jié)點(diǎn)包含了u 的所有后代。最右路徑和轄域區(qū)間的概念在構(gòu) 造拓?fù)渫队暗倪^程中起著非常重要的作用。 有序樹給定1 棵樹，設(shè)u 是樹的非葉子節(jié)點(diǎn)( 內(nèi)部節(jié)點(diǎn)) ，且u 具有k 個(gè)孩子， 給這些孩子節(jié)點(diǎn)排序，形成u h u t ，排完序后形成的樹被稱為有序樹。 標(biāo)號樹給定1 棵樹t ( v o ) ，標(biāo)號集l ，頂點(diǎn)集n ，t ( v o ) 是標(biāo)號樹當(dāng)且僅當(dāng)存在 映射n 哼l , v vn ，墳壚l l ，記作t ( v 口) = ( l ( n ) ，b ) ) 有序標(biāo)號樹給定1 棵樹t ( v 0 ，v ，l ，e ) ，t 是有序標(biāo)號樹當(dāng)且僅當(dāng)t 是標(biāo)號樹 且t 是有序樹。給出如下形式化定義，t ( v 0 ，v ，l ，e ) 是有序標(biāo)號樹當(dāng)且僅當(dāng)滿 足以下條件： ( 1 ) v o 仨v ，是樹的根節(jié)點(diǎn)；( 2 ) v 是樹的節(jié)點(diǎn)集；( 3 ) l 是節(jié)點(diǎn)的標(biāo)號集， v u v ，l ( u ) 是節(jié)點(diǎn)u 的標(biāo)號；( 4 ) e 是樹的邊集。 給定樹t ( r ，n ，b ) ，樹s ( r 。，n 。，b i ) 稱為樹t 的嵌入子樹，表示為s t ，如果 ( 1 ) n scn ；( 2 ) 對任意分枝( u ，v ) bs ，在樹t 中一定存在路徑 ，即 u 是v 的祖先。稱t 包含s 。若u ，v 在t 中仍需保持父子關(guān)系，則稱s 為t 的直接子樹。 直接子樹是嵌入式子樹的一種特殊情況。稱大4 , k 的子樹為一棵k 一子樹。通常，s 是待挖掘的子樹模式，而t 是d 內(nèi)的一棵樹對s 中任意節(jié)點(diǎn)uen s ，t 中必有一 映射節(jié)點(diǎn)u en 與之對應(yīng)。稱t 中s 的所有映射節(jié)點(diǎn)為s 在t 中次呈現(xiàn)。 圖2 一l 所示，( a ) 代表一棵有序標(biāo)號樹，( b ) 是( a ) 的一棵直接予樹，( c ) 是 ( a ) 的一棵嵌入式子樹。根據(jù)以上定義可以得出，如果t 是t 的導(dǎo)出式子樹，n t 必然是t 的嵌入式子樹。反之則不成立。 ：菊，乞搴 基于序列編碼頓繁子樹挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 ( a )( c ) 圖2 1 定義2 1 ( 頻繁子樹) 給定數(shù)據(jù)庫d ，樹s t h 支持度指o f 包含s 的樹的個(gè)數(shù)。即， s u p ( s ) - - i t i t d ，s j ) 時(shí)：則將( y ，j ) 加入p ，。 3 ) ( i j ) 時(shí)：在此種情況沒有候選子樹產(chǎn)生。 所有由p 衍生的( k + 1 ) 一子樹都可以由對p 的元素列表中的每對元素上旖加求交 算子得到。 爨一 、 、禹一 暫- rj ，：搴 基于序列編碼頻繁子辯挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 該引理不僅保證僅僅在棵樹的最右路徑的各個(gè)節(jié)點(diǎn)上添加新節(jié)點(diǎn)，而且能 夠保證列舉空間的完整和無冗余。 圖2 - 3 中所示的是通過等價(jià)類擴(kuò)展候選進(jìn)行候選生成的過程。對照求 交算予所定義的各種情況：x f r ，的自交得到t 。和t 。，對t ，和t 2 求交得到t 5 ，t 。和l 求交對應(yīng)沒有候選子樹產(chǎn)生的情況，對t 。的自交得到t 。和t ，。等價(jià)類擴(kuò)展之后， t 3t r 和t 6t ，各自形成新的等價(jià)類。 妙凸 t 4 t 圖2 - 3 候選子樹計(jì)數(shù) t r e e m i n e r 使用一種新穎的稱為s c o p e - l i s t 的樹表示方法，高效的支持候選子 樹計(jì)數(shù)。 定義2 4 ( 樹的s c o p e l i s t 表示) 令x 表示一棵k 一子樹，令x k 表示x 的最后節(jié)點(diǎn)。 用鏈表l ( x ) 表示x 的s c o p e - l i s t ，其中的每個(gè)元素是一個(gè)三元組( t ，s ，m ) 。t 是 樹i d 號，表示x 呈現(xiàn)此樹中，s 是x 。的轄域，m 是x 的前( k 1 ) 個(gè)節(jié)點(diǎn)在此樹中的呈 現(xiàn)。 圖2 4 中顯示的是包含三棵樹的數(shù)據(jù)庫d 。圖2 5 左部為起始時(shí)由單獨(dú)項(xiàng)構(gòu)成的 單節(jié)點(diǎn)樹創(chuàng)建s c o p e l i s t ?；谝陨细拍?，給出t r e e m i n e r 算法的總體框架。 裔 &上暑 ；啕- r 幺薯 基于序列編碼頻繁子樹挖掘算法研究 蘭州大學(xué)碩士學(xué)位論文 1 1 2 ，【2 ，3 】n l ，【l n 3 ，【3 捌 1 1 2 ，體2 】n 3 ，d ，3 】 前綴串= m o ，【o ，3 】o f l ，i o ，【2 ，3 】o ，f 3 ，3 】 l ，【1 ，3 】 1 ，【o ，5 1 ，【5 ，5 】 l ， 3 , 3 1 2 ，【o ，7 】 l ，【2 ，2 2 ，【1 ，2 】 2 ，【4 ，7 】 l ，【4 ，4 2 ，【6 ，7 】 2 ，【7 ，7 】 2 ，【2 ，2 2 ，f 5 ，5 圖2 4 ，【5 ，5 1 0 , 0 ，【l ，1 】 0 , 0 ，【3 ，3 】 l , l ，【2 ，2 】 1 , 1 ，【3 ，3 】 2 , 0 ，【2 捌2 , 0 ，【7 ，7 1 2 , 0 ，【5 ，5 】 2 ，7 ，【7 ，7 2 , 4 ， 5 ，5 】 圖2 5 前綴串= l2 算法挖掘嵌入式子樹的t r e e m i n e r 算法 輸入：數(shù)據(jù)庫o ：最小支持度： 輸出：d 中所有頻繁子樹： i p o - - ( 所有的頻繁一l 予樹 用 p 。表示，其共享前綴串長度為x 2 e n u m e r a t e f r e q u e n t s u b t r e e s ( p 】o ) ： 函數(shù)e n u m e r a t e - f r e q u e n t s u b t r e e s ( p ) i f o r p 中的每個(gè)元素( x ，i ) d o 2 【p 1 = o ：p i 表示從元素( x ，i ) 衍生的等價(jià)類 3 f o r p 中的每個(gè)元素( y ，j ) e p d o 4 r ： ( x 。i ) 0 ( y ，j ) ； 5 。l ( r ) = l ( x ) nl ( y ) ： 6 i fr 中的任意元素r r 是頻繁的，則 p 。 = p 。 u ( r 7 e n d q 暑 串 綴 前6 萄- r 氣辜基于序列編碼頻繁子樹挖掘算法研究蘭州大學(xué)碩士學(xué)位論文 8 e n u m e r a t e f r e q u e n t s u b t r e e s ( i f ， ) 9 e n d 算法中，用r 表示對等價(jià)類中任意兩個(gè)元素?cái)U(kuò)展，用l ( r ) 表示它們各自的 s c o p e l i s t 。當(dāng)前層的頻繁子樹遞歸的構(gòu)成了等待進(jìn)一步擴(kuò)展的新的等價(jià)類。可 見，對s c o p e l i s t 的求交運(yùn)算在t r e e m i n e r q b 起著至關(guān)重要的作用。 s c o p e - l i s t 求交運(yùn)算 怎樣對等價(jià)類 p 中的兩棵予樹進(jìn)行s c o p e l i s t 求交運(yùn)算? 當(dāng)計(jì)算 ( x ，i ) o ( y ，j ) 時(shí)，只可能有兩種結(jié)果：y 成為x 的孩子節(jié)點(diǎn)，或者，y 成為x 的兄弟節(jié) 點(diǎn)。然后，將結(jié)果加入新生成的等價(jià)類 p 。 。前者稱這之為i n - s c o p e 測試，后者 稱之為。o u t s c o p e 測試。令( t y ，s y ，m ，) l ( y ) ，( b ，s 。，m 。) l ( x ) ，新生成的樹為t 。 對于i n s c o p