《树模式挖掘及其在树流分类中的应用研究》由会员分享，可在线阅读，更多相关《树模式挖掘及其在树流分类中的应用研究（52页珍藏版）》请在金锄头文库上搜索。
1、A t h e s i s ( d i s s e r t a t i o n ) s u b m i t t e dt o Z h e n g z h o uU n i v e r s i t y f o rt h ed e g r e eo fM a s t e r T r e eP a t t e r nM i n i n ga n di t sA p p l i c a t i o nR e s e a r c ho nT r e e S t r e a mC l a s s i f i c a t i o n B yM i n j i eJ i a S u p e r v i s o
2、 r ：P r o f L i m i n gW a n g C o m p u t e rS o f t w a r ea n dT h e o r y S c h o o lo fI n f r o m a t i o nE n g i n e e r i n g M a y 2 0 1 2 原创性声明 删燃 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均己在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者： 缓
3、艟 日期：州) 年，月罗1 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州 大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、 缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学 位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑 州大学。保密论文在解密后应遵守此规定。 学位论文作者：亥刍每乞 日期：弦，年厂月纠日 摘要 摘要 在近些年，树挖掘和模式分类已
4、经成为数据挖掘中相当活跃的研究领域。 同时，由于数据多以连续流形式出现，需要考虑数据分布随时间而改变，例如 感知器网络、w e b 日志、生物学中的各种酶分子结构等。发现有识别能力的模 式是树挖掘中一个重要的环节。同时，设计实时快速的分类算法是非常有必要 的，分类模型要适应数据分布的动态变化。目前对结构化数据的分类方法大多 是基于频繁子结构挖掘，然后通过排序剪枝等处理将频繁子结构与类关联得到 结构规则进而分类。现在成熟的树流分类算法主要有：使用代价敏感分类模型 的分类算法X R u l e s ，它发现大量满足用户最小支持度和置信度阈值的规则，然 后从中选取高质量的规则：以及先挖掘频繁闭树，随
5、后采用b o o s t i n g 分类方法 的A d a T r e e M i n e r 算法等。 本文首先阐述了树挖掘理论的相关知识，分析了闭和最大频繁树模式挖掘 的优点，详细介绍了类相关模式挖掘中的思想和原理。与X R u l e s 相比， A d a T r e e M i n e r 算法提高分类的算法时间，并考虑到概念漂移，但是其分类正确 率相对较低。本文提出的树流分类算法T S C ，基于类相关模式，将S P - t r e e 数据 结构引入到树模式的发现过程中。在该过程中，使用分支界限法提高搜索效率， 无需挖掘完全模式，另一方面对参考度不断更新从而避免后剪枝操作，得到
6、的 树模式可直接用于分类。其次，对统计中的卡方度量进行优化，提高发现k b e s t 树模式的时间和空间效率；将得到的k b e s t 树模式用于树流分类，方法简单高 效。此外，将一对多分类思想运用到树流分类上，解决多类分类问题中的效率 问题。 在合成数据集和真实数据集上的实验表明，本文提出的基于k b e s t 树模式 的树流分类算法在分类正确率和运行效率方面较已往的算法具有一定的优势。 关键字：数据挖掘；树流：分类；k b e s t 树模式；相关度量 A b s t r a c t I nr e c e n ty e a r s ，t h et r e em i n i n ga
7、n dp a t t e r nc l a s s i f i c a t i o nh a sb e c o m eaq u i t e a c t i v ea r e ao fr e s e a r c hi nd a t am i n i n g A tt h es a m et i m e ，b e c a u s em o s to ft h ed a t a e m e r g e sw i t ht h ef o r m o fac o n t i n u o u ss t r e a m ，w en e e dt oc o n s i d e rt h ed a t a d
8、i s t r i b u t i o nc h a n g e so v e rt i m e ，s u c ha ss e n s o rn e t w o r k s 。w e bl o g s av a r i e t yo f e n z y m em o l e c u l es t r u c t u r e i nb i o l o g y F i n d i n gt h ed i s c r i m i n a t i v ep a t t e mi Sa l l i m p o r t a n tp a r to ft r e em i n i n g M e a n w
9、 h i l e i ti sn e c e s s a r yt od e s i g nar e a l t i m ea n d f a S tc l a s s i f i c a t i o na l g o r i t h m C l a s s i f i c a t i o nm o d e ls h o u l db ea d a p t e dt ot h ed y n a m i c c h a n g e so fd a t ad i s t r i b u t i o n A tp r e s e n t ，t h ec l a s s i f i c a t i o
10、 nm e t h o d st os t r u c t u r e dd a m i Sb a s e do nt h ef r e q u e n ts u b s t r u c t u r em i n i n g a n dt h e ng e ta s s o c i a t e ds t r u c t u r er u l e s a f t e ras o r to rp r u n i n gp r o c e s s i n go ff r e q u e n ts u b - s t r u c t u r ew i t hac l a s sa n dt h e n
11、u s e f o rp r e d i c tt a s k N O Wt h em a t u r ec l a s s i f i c a t i o nm e t h o d so f t r e es t r e a mm a i n l yi n c l u d e ： c l a s s i f i c a t i o na l g o r i t h mX R u l e so fc o s t s e n s i t i v ec l a s s i f i c a t i o nm o d e l f i r s t l y , i t f o u n d sal a r
12、g eq u a n t i t yp a t t e r n sw h i c hm e e tt h eu s e r - d e f i n e dm i n i m u ms u p p o r ta n d t h e ns e l e c th i g h q u a l i t yr u l e sw i t hu s e r - d e f i n e dc o n f i d e n c et h r e s h o l d A n o t h e ri s A d a T 陀e M i n e ra l g o r i t h mu s i n gb o o s t i n
13、 gc l a s s i f i c a t i o nm e t h o da f t e rm i n i n gc l o s e d f r e q u e n tt r e e sa n dS Oo n I nt h i sP a p e r ，w ei n t r o d u c et h et h e o r yo fk n o w l e d g eo ft r e em i n i n ga n da n a l y z e t h ea d v a n t a g e so fc l o s e da n dm a x i m a If r e q u e n tp a
14、t t e r n T h e n w ed e t a i lt h ei d e a sa n d p r i n c i p l e s i nt h ec l a s sc o r r e l a t e d p a t t e r nm i n i n g C o m p a r e d t oX R u l e s A d a T r e e M i n e ra l g o r i t h mi m p r o v e st h et i m ee f f i c i e n c yi nc l a s s i f i c a t i o n a n dt a k e s i n
15、 t oa c c o u n tt h ed r i f tc o n c e p t B u ti t sp r e d i c ta c c u r a c yi Sl o w e r I nm i sp a p e r , w e p r o p o s eaD e es n e a mc l a s s i f i c a t i o na l g o r i t h mT S Cb a s e do nc l a s sc o r r e l a t e dp a t t e r n T S Cg i v e t h eS P - t r e ed a t as t r u c t
16、 u r eu s 酣t ot h et r c ep a t t e r nd i s c o v e r yp r o c e s s D u r i n gt h i sp r o c e s s T S C U S e Sb r a n c ha n db o u n dt e c h n o l o g yt oi m p r o v et h es e a r c he f f i c i e n c yw i t h o u tm i n i n gt h ec o m p l e t e f r e q u e n tp a t t e r n s ，o nt h eo t h e rh a n d , u p d a t e st h et h r e s h o l dt oa v o i dt h ep o s t - p r u n es t e p ，a n d a l l o w sc l a s s i l y i n gd i r e c t l yu s i n gt h et
