（計算機應用技術專業(yè)論文）序列模糊概念格模型及其分布處理研究.pdf

袁運浩：序列模糊概念格模型及其分布處理研究 摘要 隨著社會經濟與科學技術的發(fā)展，信息技術得到了廣泛的應用，許多領域積 累了大量的數(shù)據，迫切需要一種新技術與工具來幫助人們快速地從海量的數(shù)據中 找出重要的有價值的信息，數(shù)據挖掘技術就是基于這種背景應運而生。而作為數(shù) 據挖掘的一個重要研究內容一序列模式挖掘，已經得到了許多研究，提出了許多 有關序列模式挖掘的算法，如a p r i o r i a l l 算法、s p a d e 算法以及p r i f i x s p a n 算法等 等，而且序列模式挖掘在許多領域得到了廣泛的應用，如顧客購買行為分析、w e b 訪問模式分析以及d n a 序列分析等等。 但是，目前已經提出的許多序列模式挖掘算法僅僅是挖掘出滿足用戶指定的 最小支持度m i n s u p 的序列模式，并沒有考慮序列模式的重要性，即雖算法挖掘出 的所有的序列模式都滿足用戶指定最小支持度m i n s u p ，但用戶可能更關注比較重 要的序列模式，它們雖然不能滿足用戶指定最小支持度，但是這些序列對用戶來 說比較有價值；相反地，有些序列模式可能對用戶來說重要程度并不是很大，并 不需要挖掘，這就需要算法能夠自適應地調整以挖掘出符合用戶需求的序列模式， 但已提出的挖掘算法沒有考慮這種特征，無法挖掘出這樣的序列模式。 由于形式概念分析中的概念格模型只需訪問一次數(shù)據庫就可構建成功，并且它 的知識與層次表達能力強，將序列引入概念格中，只需存儲最大公共子序列，減 少了冗余序列的產生。為此，本文對序列模式挖掘與模糊概念格的結合進行了系 統(tǒng)的研究，主要研究成果如下： ( 1 ) 針對目前概念格構造算法在較大規(guī)模稀疏的數(shù)據集或分布式的數(shù)據集上， 生成概念時仍然需要耗費大量的時間，本文提出了一種基于i e t r e e ( i n t e n s i o na n d e x t e n s i o nt r e e ) 與特征空間劃分的概念生成算法i e t r e e c s ( c o n c e p ts e tb a s e do n i n t e n s i o na n de x t e n s i o nt r e e ) 。i e t r e e c s 算法首先將形式背景轉為i e t r e e ，減少了 數(shù)據集的存儲量；然后該算法在i e t r e e 的基礎上進行了特征空間的描述與劃分， 最后給出了完整的i e t r e e c s 算法。實驗結果表明該算法在較大規(guī)模稀疏的數(shù)據集 或分布式的數(shù)據集上性能優(yōu)越，有明顯地提高。同時，i e t r e e c s 算法也為序列模 2 揚州大學碩士學位論文 糊概念格的構建提供了算法支持。 ( 2 ) 為了組織與挖掘有價值的滿足多需求的序列模式，本文提出了一種序列 模糊概念格模型，并給出了序列模糊概念格的構造算法s e q f u z c l ( s e q u e n c ef u z z y c o n c e p tl a t t i c e ) 。在傳統(tǒng)的模糊形式背景的基礎上，本文將其在序列上進行了擴展， 定義了序列模糊形式背景；利用擴展的序列模糊形式背景，定義了概念的g a l o i s 閉包連接、序列模糊概念及其格結構，最后給出了序列模糊概念格的構建算法 s e q f u z c l 。通過實驗表明，序列模糊概念格模型不僅可以方便有效的組織自適應 序列模式，在時間與空間上都具有良好的性能，而且還可以在序列模糊概念格上 挖掘傳統(tǒng)意義下的序列模式，同時，為進一步挖掘自適應序列模式提供了理論支 持。 ( 3 ) 由于在實際應用中，許多大型數(shù)據庫是以分布式的形式存在的，為了能 夠有效與方便地處理分布環(huán)境下的序列，本文在序列模糊概念格的基礎上提出了 分布序列模糊概念格模型及其構建算法d s e q f u z c l ( d i s t r i b u t e ds e q u e n c ef u z z y c o n c e p tl a t t i c e ) 。在分布序列模糊概念格模型上，不僅可以有效挖掘分布序列模式， 而且還可以挖掘滿足用戶多需求的特殊分布序列模式，如分布加權序列模式等。 通過實驗證明，本文提出的分布序列模糊概念格構建算法d s e q f u z c l 具有良好的 時間與空間性能。 ( 4 ) 在序列模糊概念格的基礎上，利用序列權重與序列的重要度閾值，本文 定義了序列自適應系數(shù)及其自適應序列模式s a s p ( s e l f - a d a p t i v es e q u e n c ep a t t e r n ) ， 給出了基于序列模糊格的自適應序列模式的發(fā)現(xiàn)算法s a s e q p ( s e l f - a d a p t i v e s e q u e n c ep a t t e r n ) 。它可以自適應地調整用戶指定的最小支持度m i n s u p ，以挖掘出 滿足用戶需求的特別有價值的序列模式。 關鍵詞：形式概念分析；概念格；模糊形式背景；模糊概念格；數(shù)據挖掘； 序列模式挖掘；分布序列模式 袁運浩：序列模糊概念格模型及其分布處理研究 3 a b s t r a c t w i t ht h ed e v e l o p m e n to fs o c i o - e c o n o m i ca n ds c i e n c et e c h n o l o g y , i n f o r m a t i o n t e c h n o l o g ya c q u i r e se x t e n s i v ea p p l i c a t i o n s m a n yf i e l d sh a v ea c c u m u l a t e da b u n d a n t d a t a ；t h e r e f o r e ，p e o p l en e e dan e wt e c h n o l o g ya n dt o o lt oh e l pt h e md i s c o v e rt h e i m p o r t a n ta n dv a l u a b l ei n f o r m a t i o n i nt h i sc a s e ，d a t am i n i n gt e c h n i q u ei sp r e s e n t e dt o s o l v et h ea b o u t - m e n t i o n e dp r o b l e m a sa ni m p o r t a n tr e s e a r c ho fd a t am i n i n g ，s e q u e n c e p a t t e r nm i n i n gh a sg a i n e dl o t so fr e s e a r c h e s a tp r e s e n t ，m a n ys c h o l a r sa th o m ea n d a b r o a dh a v ep r e s e n t e dv a r i o u sa l g o r i t h m st od e t e c ts e q u e n c ep a t t e r n s f o re x a m p l e ， a p r i o r i a ua l g o r i t h m ，s p a d ea l g o r i t h ma n dp r i f i x s p a na l g o r i t h m ，a n ds oo n a n d s e q u e n c ep a t t e r nm i n i n gh a sb e e nw i d e l ya p p l i e di nt h ea c t i o na n a l y s i so fc u s t o m e r b u y i n g ，a n a l y s i so fn e t w o r kv i s i t i n g ，a n a l y s i so fd n as e q u e n c ep a t t e r n s ，a n do t h e r f i e l d s h o w e v e r ，c u r r e n ta l g o r i t h m sf o rm i n i n gs e q u e n c ep a a e m sa l eo n l ya b l et od i s c o v e r t h ef r e q u e n ts e q u e n c e ss a t i s f y i n gt h em i n i m u ms u p p o r tt h r e s h o l dm i n s u p n e v e r t h e l e s s ， t h e s em e t h o d sd o n tc o n s i d e rt h ei m p o r t a n c eo fs e q u e n c e sa n di t e m s ，i e ，m o s to ft h e f r e q u e n ts e q u e n c e sw h i c ha b o v e - m e n t i o n e da l g o r i t h m sd e t e c tm a yb eu n i m p o r t a n tf o r u s e r s a t t e n t i o n t h o u g hs o m es e q u e n c e sd o n ts a t i s f yt h em i n i m u ms u p p o r tt h r e s h o l d m i n s u p ，t h e ya l ev e r yv a l u a b l ef o ru s e r s c o n t r a r i l y , s o m es e q u e n c ep a t t e r n sa r en o ts o i m p o r t a n tf o ru s e r s d e m a n dt h a tt h e yd o n tn e e dt ob ed e t e c t e d t h e r e f o r e ，i ti sv e r y e s s e n t i a lf o ra l g o r i t h m sm i n i n gs e q u e n c ep a t t e r n st oa d j u s ts e l f - a d a p t i v e l yt od e t e c t s e q u e n c ep a t t e m so fs a t i s f y i n gu s e r s r e q u i r e h o w e v e r , c u r r e n te x i s t i n gm i n i n g a l g o r i t h m sd o n tt a k ea c c o u n to ft h ef e a t u r en o tt om i n et h ef r e q u e n ts e q u e n c e sm e e t i n g u s e r s n e e d s b e c a u s et h ec o n c e p tl a t t i c ei nf o r m a lc o n c e p ta n a l y s i so n l ys c a n so n c ei nd a t a b a s e t os u c c e s s f u l l yc o n s t r u c tl a t t i c es t r u c t u r e a n di tm a ys t r o n g l yd e s c r i b ek n o w l e d g ea n d h i e r a r c h i c a lr e l a t i o nb e t w e e nc o n c e p t i o n s i to n l yn e e d st os t o r et h em a x i m a lc o m m o n 4 揚州大學碩士學位論文 s u b s e q u e n c ei nc o n c e p tl a t t i c e a sar e s u l t ，c o n c e p tl a t t i c em a yr e d u c et h eg e n e r a t i o no f r e d u n d a n ts e q u e n c e st os a v em u c hs p a c e t h e r e f o r e ，t h i sp a p e rc o n d u c t sas y s t e m a t i c s t u d yf o rt h ec o m b i n a t i o no fs e q u e n c ep a t t e r nm i n i n ga n df u z z yc o n c e p tl a t t i c e t h e m a i nr e s e a r c hr e s u l t sa r ea sf o l l o w s ： ( 1 ) f o rc u r r e n ta l g o r i t h m sf o rb u i l d i n gc o n c e p tl a t t i c es t i l lc o n s u m em u c ht i m et o g e n e r a t ec o n c e p t si nt h el a r g e s c a l es p a r s ed a t as e t so rd i s t r i b u t e dd a t as e t s ，t h i sp a p e r p r e s e n t san e wa l g o r i t h mc a l l e di e t r e e c s ( c o n c e p ts e t sb a s e do ni n t e n s i o na n d e x t e n s i o nt r e e ) b a s e do nt h e i e t r e e ( i n t e n s i o na n d e x t e n s i o nt r e e ) a n dt h e c h a r a c t e r i s t i cs p a c ep a r t i t i o n t h ei e t r e e c sa l g o r i t h mf i r s t l yd e f i n e sa ni e t r e e ，t h e ni t c o n v e r t sf o r m a lc o n t e x ti n t oi e t r e et or e d u c et h es t o r a g eo fd a t as e t s ，i e ，t h ei e t r e e c a nr e d u c et h es t o r a g eo ft h ef o r m a lc o n t e x t a n dt h e nt h ei e t r e e c sa l g o r i t h mg i v e sa d e f i n i t i o na b o u tt h ec h a r a c t e r i s t i cs p a c ea n dd e s c r i b e sh o wt op a r t i t i o nac h a r a c t e r i s t i c s p a c eo nt h eb a s i so ft h ei e t r e e a tl a s t ，t h ep a p e rp r e s e n t st h ei n t e g r a t e di e t r e e c s a l g o r i t h mt h a tg e n e r a t e sa l lc o n c e p t sf r o mab i n a r yr e l a t i o n t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tt h ei e t r e e c sa l g o r i t h mp e r f o r m sm o r ee f f i c i e n tt h a nt h en e x t c l o s u r ea n d s s p c ga l g o r i t h m sf r o mt h el a r g e - s c a l es p a r s ed a t as e t so rd i s t r i b u t e dd a t as e t s s i m u l t a n e o u s l y , i e t r e e c sa l g o r i t h mp r o v i d e sa l g o r i t h m i cs u p p o r tf o rc o n s t r u c t i n g s e q u e n c ef u z z yc o n c e p tl a t t i c e ( 2 ) f o rt h es a k eo fo r g a n i z i n ga n dm i n i n gv a l u a b l es e q u e n c ep a t t e r n ss a t i s f y i n g u s e r sv a r i o u sr e q u i r e s ，t h i sp a p e rp r e s e n t san e ws e q u e n c ef u z z yc o n c e p tl a t t i c em o d e l b a s e do nt r a d i t i o n a lf u z z yf o r m a lc o n t e x t ，w ee x t e n di tt oe x p r e s ss e q u e n c e si nb r i e f , a n dg i v eo u tad e f i n i t i o no fs e q u e n c ef u z z yf o r m a lc o n t e x t m a k i n gu s eo ft h es e q u e n c e f u z z yf o r m a lc o n t e x t ，g a l o i sc o n n e c t i o n , s e q u e n c ef u z z yc o n c e p t i o na n ds e q u e n c ef u z z y c o n c e p tl a t t i c ea r ed e f i n e di nt h ep a p e r a tl a s t ，t h i sa r t i c l ep r e s e n t st h ei n c r e m e n t a l c o n s t r u c t i o na l g o r i t h ms e q f u z c l ( s e q u e n c ef u z z yc o n c e p tl a t t i c e ) o ft h es e q u e n c e f u z z yc o n c e p tl a t t i c e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h ms e q f u z c lc a n e f f e c t i v e l ye x p r e s ss e l f - a d a p t i v es e q u e n c ep a t t e m si nt h el a t t i c e ，a n dh a se x c e l l e n t p e r f o r m a n c eo nt h et i m e - s p a t i a lc o m p l e x i t y s i m u l t a n e o u s l y , t h em o d e lp r o v i d e s t h e o r e t i cs u p p o r tf o rm i n i n gs e l f - a d a p t i v es e q u e n c ep a t t e r n s 袁運浩：序列模糊概念格模型及其分布處理研究 5 ( 3 ) a c t u a u y , al a r g en u m b e ro fl a r g ed a t a b a s ea r es t o r e di nt h ed i s t r i b u t e ds y s t e m t h u s ，s e q u e n c e sa l s oe x i s t i nt h ed i s t r i b u t e dc o n d i t i o n i no r d e rt oh a n d l ed i s t r i b u t e d s e q u e n c ee f f i c i e n t l ya n dc o n v e n i e n t l y , t h i ep a p e rp u t sf o r w a r dad i s t r i b u t e ds e q u e n c e f u z z yc o n c e p tl a t t i c em o d e lo nt h eb a s i so fs e q u e n c ef u z z yc o n c e p tl a t t i c ea n dp r e s e n t sa b u i l d i n ga l g o r i t h md s e q f u z c l ( d i s t r i b u t e ds e q u e n c ef u z z yc o n c e p tl a t t i c e ) i n d i s t r i b u t e ds e q u e n c ef u z z yc o n c e p tl a t t i c e ，a l g o r i t h md s e q f u z c lc a l ln o to n l yd i s c o v e r d i s t r i b u t e ds e q u e n t i a lp a t t e r n s ，b u ta l s om i n i n gs p e c i f i cd i s t r i b u t e ds e q u e n t i a lp a t t e m s s a t i s f y i n gu s e r sv a r i o u sd e m a n d s ，f o ri n s t a n c e ，w e i g h t e ds e q u e n c ep a t t e r n s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a ta l g o r i t h md s e q f u z c lh a se x c e l l e n tp e r f o r m a n c eo n t h e t i m e - s p a t i a lc o m p l e x i t y ( 4 ) o nt h eb a s i so fs e q u e n c ef u z z yc o n c e p tl a t t i c e ，t h i sp a p e rd e f i n es e l f - a d a p t i v e c o e f f i c i e n ta n ds e l f - a d a p t i v es e q u e n c ep a t t e r n ss a s p ( s e l f - a d a p t i v es e q u e n c ep a t t e m ) ， a n dt h e nw ep r e s e n tan e wa l g o r i t h ms a s e q p ( s e l f - a d a p t i v es e q u e n c ep a t t e r n ) f o r m i n i n gs e l f - a d a p t i v es e q u e n c ep a a e m sb a s e do ns e q u e n c ef u z z yc o n c e p t l a t t i c e a l g o r i t h ms a s e q pm a yd y n a m i c a l l ya d j u s tt h em i n i m u ms u p p o r tt h r e s h o l dm i n s u pb y s e l f - a d a p t i v ec o e f f i c i e n tt od i s c o v e rv e r yv a l u a l es e q u e n t i a lp a t t e m sf o ru s e r s k e y w o r d s ：f o r m a lc o n c e p ta n a l y s i s ；c o n c e p tl a t t i c e ；f u z z yf o r m a lc o n t e x t ；f u z z y c o n c e p tl a t t i c e ；d a t am i n i n g ；s e q u e n c ep a t t e mm i n i n g ；d i s t r i b u t e ds e q u e n c ep a t t e m 袁運浩：序列模糊概念格模型及其分布處理研究 1 0 3 揚州大學學位論文原創(chuàng)性聲明和版權使用授權書 學位論文原創(chuàng)性聲明 本人聲明：所呈交的學位論文是在導師指導下獨立進行研究工作所取得的研 究成果。除文中已經標明引用的內容外，本論文不包含其他個人或集體已經發(fā)表 的研究成果。對本文的研究做出貢獻的個人和集體，均已在文中以明確方式標明。 本聲明的法律結果由本人承擔。 撇簽名薏主訖 簽字日期：年月z 日 學位論文版權使用授權書 本人完全了解學校有關保留、使用學位論文的規(guī)定，即：學校有權保留并向 國家有關部門或機構送交學位論文的復印件和電子文檔，允許論文被查閱和借閱。 本人授權揚州大學可以將學位論文的全部或部分內容編入有關數(shù)據庫進行檢索， 可以采用影印、縮印或掃描等復制手段保存、匯編學位論文。同時授權中國科學 技術信息研究所將本學位論文收錄到 ：中國學位論文全文數(shù)據庫，并通過網絡向 社會公眾提供信息服務。 。葉 糊一躲需藝汔名：專多 簽字日期：、筘穸年莎月力日 簽字日期： 。j 年6 月砂日 | 、 ( 本頁為學位論文采頁。如論文為密件可不授權，但論文原創(chuàng)必須聲明。) 袁運浩：序列模糊概念格模型及其分布處理研究 7 第一章緒論 1 1 論文研究背景與選題依據 隨著社會經濟與科學技術的發(fā)展，信息技術得到了廣泛的應用，數(shù)據庫作為 信息技術的重要組成部分，在各個領域也得到了大量的使用。近年來，數(shù)據庫的 規(guī)模與數(shù)量獲得了急速增長，在這個過程中，許多領域積累了大量的數(shù)據，迫切 需要一種新技術與工具來幫助人們快速地從海量的數(shù)據中找出重要的有價值的信 息，數(shù)據挖掘技術就是基于這種背景應運而生。 數(shù)據挖掘【l j 作為數(shù)據庫中知識發(fā)現(xiàn)k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 中最核心的部分，是根據決策需要，采用具體的算法，從數(shù)據庫中抽取隱含的、 以前未知的、具有潛在應用價值的信息的過程。目前，數(shù)據挖掘的研究主要集中 在分類、聚類、規(guī)則發(fā)現(xiàn)、異常和趨勢發(fā)現(xiàn)等方面，其中序列模式挖掘 2 1 已是數(shù)據 挖掘研究的熱點內容之一。 序列模式挖掘( s e q u e n t i a lp a t t e mm i n i n g ) 問題是由r s r i k a n t 與r a g r a w a l 在 文獻【2 】中最先提出的：給定一個序列集，其中每一個序列由項集構成，然后給定由 用戶確定的最小支持度閾值m i n s u p ，序列模式挖掘就是去發(fā)現(xiàn)所有滿足最小支持 度m i n s u p 的頻繁子序列，即從序列數(shù)據庫中發(fā)現(xiàn)頻繁子序列以作為模式，它是挖 掘基于時間或者其它順序的出現(xiàn)頻率較高的模式。 在數(shù)據庫的知識發(fā)現(xiàn)中，序列模式經常隱藏著有價值的信息，如對超市而言， 根據顧客的購物清單，可以推斷出購物者的某些購買習慣，進而指導超市的銷售 策略；在天氣預報領域中，分析某地區(qū)多年來的歷史氣象資料，可以發(fā)現(xiàn)一些氣 候變化規(guī)律，進而對天氣進行預測；又如在證券市場上，交易價格隨時間的變化 存在著某些規(guī)律，發(fā)現(xiàn)這些規(guī)律可以指導證券交易者等。因此序列模式挖掘是非 常有用并且重要的，它具有廣闊的應用領域，如顧客購買行為分析、w e b 訪問模 式發(fā)現(xiàn)、科學實驗分析、疾病治療的早期診斷、自然災害的預測以及d n a 序列模 式分析等。 8 揚州大學碩士學位論文 近些年來，序列模式挖掘已經得到了許多學者的關注與研究。目前，已經提 出了許多序列模式的挖掘算法，就算法采用的挖掘策略大體可將序列模式挖掘算 法分為兩類。一類是基于候選碼生成測試的挖掘算法：1 9 9 5 年r s r i k a n t 與 r a g r a w a l 在文獻 2 】中最早提出序列模式挖掘問題，并給出了一個序列模式挖掘的 經典算法a p f i o d a l l 。這個算法主要分為三步：算法首先找出所有的頻繁項集，然 后轉換交易數(shù)據庫，將交易數(shù)據庫中所有的事物代之以對應的頻繁項集，最后在 轉換后的數(shù)據庫中挖掘所有的序列模式。隨后，r s r i k a n t 與r a g r a w a l 又提出了一 個更有效的挖掘算法g s p t 3 1 。m z a k 在1 9 9 8 至2 0 0 2 年期間發(fā)表了許多關于序列模 式研究的論文【4 】【5 嗣，并提出了s p a d e 算法【4 】。s p a d e 算法引入格結構來存儲序 列模式，并在其中存儲序列的i d 表，使用相應的格搜索技術與基于時間的連接操 作，通過三次掃描數(shù)據庫挖掘所有的序列模式，降低了i o 的數(shù)據量。另外還有使 用哈希樹組織候選序列的p s p t 7 】算法。 這類基于候選碼生成測試的挖掘算法雖然能夠發(fā)現(xiàn)所有的序列模式，但算法 需要多次掃描數(shù)據庫，并會產生大量的候選序列，時空復雜度很大。為此以j h a n 與j p e i 等人為代表的學者提出了另一類無須生成候選序列的基于模式增長的發(fā)現(xiàn) 算法。如f r e e s p a n 算法【8 】【9 】、p r i f i x s p a n 算法【1 0 1 ，這類算法的基本思想是在數(shù)據庫 上采用了投影技術，將數(shù)據庫投影成更小的一組數(shù)據庫，直接在前綴對應的投影 數(shù)據庫上挖掘序列模式。 上述兩類算法著重挖掘所有的序列模式，這就必然引起挖掘結果呈現(xiàn)指數(shù)級 增長，針對這種情況，文獻 1 1 1 2 1 研究了只挖掘最大序列與閉序列模式的問題。 此外，算法i s e i l 3 1 與i s m t l 4 1 研究了序列模式的增量更新以及文獻 1 5 對分布式序列 模式發(fā)現(xiàn)算法進行了研究。 然而上述有關序列模式挖掘算法大多數(shù)都需要多次掃描數(shù)據庫，并且挖掘出 的序列模式之間沒有明顯的層次性，難于查找用戶真正感興趣的模式。雖然文獻 1 3 】 1 4 研究了增量更新的問題，但依然需要訪問原有數(shù)據庫，增加了i o 開銷。 形式概念分析【1 6 】( f o r m a lc o n c e p ta n a l y s i s ) 是研究知識表示的領域，它的核 心數(shù)據結構一概念格( c o n c e p tl a t t i c e ) ，是對概念以及概念之間關系的描述，它在 一定程度上是對客觀世界的一種高度簡化的描述形式。這種簡化的最大優(yōu)點是其 袁運浩：序列模糊概念格模型及其分布處理研究 9 具有良好的數(shù)學性質。w i l l e 教授在文獻 1 6 中基于這種簡化，系統(tǒng)地研究了概念 的有序性質、格代數(shù)性質以及概念格與形式背景的同構性質，開創(chuàng)了形式概念分 析領域。 由于形式概念分析中的概念格具有鮮明的層次性、簡潔的更新操作與良好的 數(shù)學性質，使用戶能夠很方便的組織概念，并且只需訪問一次數(shù)據庫就可構建成 功，因此非常適合于序列模式的組織與挖掘，并可以在其上迅速地查找到用戶需 求的序列模式。目前，在國內外的些研究【1 7 】【1 8 1 1 9 j d p ，己將概念格引入到了序列 模式挖掘中。文獻【1 7 】【1 8 研究了概念格與序列模式的結合，利用最大公共子串作 為序列概念的內涵，但此方法不能生成自適應或用戶真正需求的序列模式，更不 能應用于分布序列模式的表示與挖掘；文獻 1 9 提出了另外一種基于概念格的序列 模式挖掘算法，這個算法首先利用( c 協(xié)，死d ) 對每個交易進行標識，然后構造概 念格，在得到的概念格中生成頻繁1 序列，然后再利用a p r i o r i a u 算法迭代生成頻 繁盡序列( p 1 ) ，但實質上該算法生成的概念格并不能表示序列模式。除此之外， 文獻【2 0 】也做了類似的研究。文獻【2 1 】基于分布式概念格研究了分布式序列模式的 發(fā)現(xiàn)，但其構建的概念格不能夠真正表示序列，在格上僅能輸出頻繁1 序列，其 他頻繁序列的獲得需要借助a p r i o r i a l l 、p r i f i x s p a n 等算法，因此，從嚴格意義上 考慮，其仍然沒有有效解決分布序列模式的挖掘。文獻 2 2 2 3 】提出了一種多維概 念格，它是對概念格的延伸與泛化，在此結構上提出了增量式多維序列模式挖掘 算法，但其本質上還是在對單機上的單一關系序列進行簡單操作，并不能處理分 布環(huán)境下的復雜序列模式。 實際上，序列概念格具有良好的數(shù)學性質與鮮明的層次性，可以利用它表示 或挖掘出一些滿足用戶指定的最小支持度的序列模式。但遺憾的是，目前大部分 已提出的序列概念格【17 】瞄1 僅能表示或挖掘傳統(tǒng)意義上的序列模式( 即僅滿足用戶 指定的最小支持度的序列模式) 。在現(xiàn)實中，一方面，用戶對序列挖掘的要求往往 不是一個變量參數(shù)就可以完全描述刻畫出的，即用戶的多種需求( 多參數(shù)) 同時 存在；另一方面，由于i n t e m e t 的發(fā)展，利用網絡連接的分布式系統(tǒng)也已經得到了 廣泛的應用，許多數(shù)據已是分布的存儲在不同地方的計算機上，在這些實際情況 下，大部分已提出的序列概念格【1 7 】【2 2 1 已不能夠給予很好的表示或組織具有不同重 1 0 揚州大學碩士學位論文 要程度的自適應的或分布環(huán)境下的序列模式，而序列概念格已經具備了最基本的 描述功能和嚴密的數(shù)學性質，這就是說，應當可以對之進行合理地擴展以更好地 適合描述現(xiàn)實世界的序列形式，以使其具有更好的表達能力，從而實現(xiàn)與真實世 界的接近。 自然科學中的許多學科的發(fā)展也都經歷了這樣的過程，即對現(xiàn)實世界高度抽 象和簡化，以形成數(shù)學性質良好的模型，然后再對這個模型進行擴展，以逼近和 模擬真實世界。同樣，序列概念格模型也可以進行合理地擴展，使其形成新的擴 展模型，這樣就與現(xiàn)實世界更加接近了。因此序列概念格的擴展模型、構建及分 布處理研究必然會有廣闊的前景。 總之，當前對形式概念分析、序列模式挖掘以及序列概念格的研究非?；钴S， 但序列模式挖掘過程中自身呈現(xiàn)的問題需要更好的模型去解決，而與概念格結合 不僅可以解決此類問題，而且還會方便的更新、擴展序列模式。雖然已經有部分 研究將概念格應用到了序列模式挖掘中，但其構建的模型表達能力較弱或根本無 法在概念格上表示分布環(huán)境下的序列模式，因此，對構建一套帶有良好數(shù)學性質 的序列概念格擴展模型以滿足不同的應用，以及研究基于擴展模型的具有良好效 率的序列模式挖掘算法還是十分必要且具有重要實際意義的。為此，本文針對序 列概念格的不足之處，提出了序列概念格的擴展模型、構建算法、分布處理以及 應用等研究，從而為復雜序列模式挖掘問題提供了一條新的解決途徑和新的研究 方向。 1 2 論文主要內容與創(chuàng)新 本文根據當前的實際需要并結合國內外在序列模式挖掘與形式概念分析方面 的研究情況，對序列模式挖掘與模糊概念格的結合進行了系統(tǒng)的研究。本文首先 闡述了形式概念分析中的有關理論、概念格的基本概念以及構建算法，接著給出 了傳統(tǒng)序列模式的相關概念、挖掘算法及其應用，然后研究了在大規(guī)模稀疏數(shù)據 集或分布式數(shù)據集上的概念格構造算法，在此基礎上，提出了序列模糊概念格及 其分布序列模糊概念格模型，以及它們相應的構建算法，最后提出了自適應序列 模式的挖掘問題，并給出了相應的發(fā)現(xiàn)算法，為序列模式的挖掘提供了新的途徑 袁運浩：序列模糊概念格模型及其分布處理研究 l l 與技術。 總的來說，本文的主要研究內容與成果如下： ( 1 ) 針對目前概念格構造算法在較大規(guī)模稀疏的數(shù)據集或分布式的數(shù)據集上， 生成概念時仍然需要耗費大量的時間，本文提出了一種基于i e t r e e 與特征空間劃 分的概念生成算法i e t r e e c s 。i e t r e e c s 算法首先將形式背景轉為i e t r e e ，減少了 數(shù)據集的存儲量；然后該算法在i e t r e e 的基礎上進行了特征空間的描述與劃分， 最后給出了完整的i e t r e e c s 算法。實驗結果表明該算法在大規(guī)模稀疏的數(shù)據集或 分布式的數(shù)據集上性能優(yōu)越，有明顯地提高。同時，i e t r e e c s 算法也為序列模糊 概念格的構建提供了算法支持。 ( 2 ) 為了組織與挖掘有價值的滿足多需求的序列模式，本文提出了一種序列 模糊概念格模型，在傳統(tǒng)的模糊形式背景的基礎上，本文將其在序列上進行了擴 展，定義了序列模糊形式背景；利用擴展的序列模糊形式背景，定義了概念的g a l o i s 閉包連接、序列模糊概念及其格結構，最后給出了序列模糊概念格的構建算法。 通過實驗表明，序列模糊概念格模型不僅可以方便有效的組織自適應序列模式， 在時間與空間上都具有良好的性能，而且還可以在序列模糊概念格上挖掘傳統(tǒng)意 義下的序列模式，同時，為進一步挖掘自適應序列模式提供了理論支持。 ( 3 ) 由于在實際應用中，許多大型數(shù)據庫是以分布式的形式存在的，為了能 夠有效與方便地處理分布環(huán)境下的序列，本文在序列模糊概念格的基礎上提出了 分布序列模糊概念格模型。在分布序列模糊概念格模型上，不僅可以有效挖掘分 布序列模式，而且還可以挖掘滿足用戶多需求的特殊分布序列模式，如分布加權 序列模式等。通過實驗證明，本文提出的分布序列模糊概念格模型具有良好的時 間與空間性能。 ( 4 ) 在序列模糊概念格的基礎上，利用序列權重與序列的重要度閾值，本文 定義了序列自適應系數(shù)及其自適應序列模式s a s p ，給出了基于序列模糊格的自適 應序列模式的發(fā)現(xiàn)算法s a s e q p 。它可以自適應地調整用戶指定的最小支持度 m i n s u p ，以挖掘出滿足用戶需求的有特別價值的序列模式。 1 2 揚少i 1 大學碩士學位論文 1 3 論文內容組織 本文各章節(jié)的詳細設置情況如下： 第一章主要闡述了論文的研究背景與選題依據，并給出了論文的主要研究內 容與成果。 第二章系統(tǒng)概述了形式概念分析與序列模式挖掘的基本定義與有關概念，介 紹了概念格的批處理與漸進式構建算法，例如g o d i n 算法、b o r d a t 算法等；闡述 了序列模式挖掘中的兩類挖掘算法，即基于候選碼測試與基于模式增長的發(fā)現(xiàn)算 法，例如a p r i o r i a l l 算法、g s p 算法以及p r e f i x s p a n 算法等。同時，列舉了概念格 與序列模式挖掘中的一些成熟應用。 第三章研究了形式概念分析中形式背景對應的i e t r e e 模型，定義i e t r e e 結 構與其生成算法，并給出了在其上特征空間的基本概念、劃分以及有關定理，最 后，在大規(guī)模稀疏的或分布式的數(shù)據集上提出了一種基于i e t r e e 與特征空間劃分 的概念生成算法i e t r e e c s 。 第四章研究并定義了一種序列模糊概念格模型，并給出該模型的漸進式構造 算法一s e q f u z c l 算法。該模型能夠有效地組織序列模式，通過設置不同的參數(shù)、 閾值來滿足用戶不同的需求，也為進一步挖掘自適應序列模式提供了理論支持。 第五章在分布式環(huán)境下，研究了分布序列模糊概念格模型，并提出了分布序 列模糊概念格構建算法d s e q f u z c l ，為分布序列模式的挖掘提供了良好的理論基 礎。 第六章在序列模糊概念格的基礎上，利用序列權重與序列的重要度閾值，定 義了序列自適應系數(shù)及其自適應序列模式，給出了基于序列模糊格的自適應序列模 式的發(fā)現(xiàn)算法s a s e q p 。 第七章評價和總結了論文的工作與研究成果，并提出了一些有待于進一步研 究的問題。 袁運浩：序列模糊概念格模型及其分布處理研究 1 3 第二章概念格理論與序列模式挖掘 2 1 概念格模型 形式概念分析f c a ( f o r m a lc o n