（计算机软件与理论专业论文）面向分类预测的增量关联规则应用研究.pdf

四川师范大学硕士学位论文 面向分类预测的增量关联规则应用研究 计算机软件与理论专业 研究生：廖旺宇指导教师：刘芳 数据库技术以及计算机硬件技术的飞速发展使得搜集更多有用的数据成为 可能。然而，大量的数据在一定程度上为描述特征、制定决策带来便利的同时， 也将数据的处理者带入了“数据丰富，但知识贫乏”的窘境当中。为了打破这 一窘境，高效处理数据、发掘潜在有用信息，数据挖掘技术在2 0 世纪8 0 年代 应运而生，并得到了飞速发展。 在数据挖掘的众多分支中，关联规则挖掘和分类的应用研究又是两个具有 高活跃度的重要领域。由于它们都有挖掘相关性强的项目集的显著共性，将关 联规则挖掘用于解决数据挖掘中的分类应用的研究工作也就逐步展开并深入 了。研究发现，由于关联规则挖掘方法可以同时考虑多个属性之间的高置信度 关联，将它用于分类应用往往可以获得比当前最为常用的决策树方法更高的准 确率。 本文在对国内外将关联规则用于分类应用的研究现状进行简要分析的基础 上，首先介绍了数据挖掘的产生、基本概念、过程以及功能等。其中，又着重 对关联规则挖掘进行了概述，包括其定义、经典算法，以及增量关联规则的更 新等。随后，在第三章论证了提出面向分类预测的增量关联规则更新应用研究 的必要性。在此基础上，提出了最小支持度阈值( m i n s u p ) 和最小置信度阈值 ( m i n c o n f ) 发生改变时高效更新分类预测关联规则的一个改进算法，然后以此 改进算法为基础，进一步提出了当目标数据集中数据增加或者减少时高效更新 分类预测关联规则的两个新算法。论文对三个算法的算法基础、算法描述，以 及算法有效性实验和结果分析分别进行了阐述。 面向分类预测的增量关联规则应用研究 在第四章中，以u c i 数据集中的g e r m a nc r e d i td a t a 真实银行信贷审核分 类数据集作为实例进行了面向分类预测的增量关联规则挖掘系统的设计与实 现，进一步检验了所提出的算法的有效性。 本文所做的工作对于客户管理和商业应用中的面向分类预测的数据挖掘技 术，如进行客户关系管理、商品销售分析、推进商业和金融业等行业智能化等 方面都具有一定的指导和借鉴意义。 关键词：数据挖掘，关联规则，分类预测，增量更新，频繁谓词集 四川师范大学硕士学位论文 t h ea p p l i e dr e s e a r c ho fi n c r e m e n t a lu p d a t i n ga l g o r i t h m s f o rm i n i n gc l a s s i f i c a t i o na s s o c i a t i o nr u l e s m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y p o s t g r a d u a t e ：l i a ow a n g y u t u t o r ：l i uf a n g f o l l o w i n gt h er a p i dd e v e l o p m e n to fd a t a b a s ea n dc o m p u t e rh a r d w a r e ，i ti s p o s s i b l et oc o l l e c tp l e n t yo fd a t a t oac e r t a i ne x t e n t ，t h el a r g ea m o u n to f d a t al e t p e o p l ee a s yt od e s c r i b et h ec h a r a c t e r i s t i c sa n dm a k e d e c i s i o n b u ta tt h es a m et i m e ， i t g u i d ep e o p l et ot h ea w k w a r dp o s i t i o n ，w h i c hw a sn a m e d “d a t ai sr i c h ，b u t k n o w l e d g ei sp o o r i no r d e rt os o l v et h i sp r o b l e m ，t h ed a t am i n i n ge m e r g e di n 19 8 0 sa n db e c a m ea ni m p o r t a n tt e c h n o l o g yo fi n f o r m a t i o nt e c h n o l o g y i nt h em u l t i p l eb r a n c ho fd a t am i n i n g ，b o t hm i n i n ga s s o c i a t i o nr u l e sa n d c l a s s i f i c a t i o na p p l i e dr e s e a r c ha ret h em o s ta c t i v ea r e a s b e c a u s et h e yh a v et h e s i g n i f i c a n ts i m i l a r i t i e si nm i n i n gs t r o n gr e l a t e dp r o j e c t ，t h et e c h n o l o g yo fm i n i n g a s s o c i a t i o nr u l e sw a su s e di nt h ea p p l i c a t i o no fc l a s s i f i c a t i o n a n df o u n di nt h e s t u d yt h a tb e c a u s eo fa s s o c i a t i o nr u l e sm i n i n gc a nr e g a r dt h eh i g hd e g r e er e l a t i o no f s e v e r a la t t r i b u t e s ，i tt e n dt og e th i g h e ra c c u r a c yr a t e b a s e do nt h eb r i e fa n a l y s i so ft h ed a t am i n i n gr e s e a r c ha th o m ea n da b r o a d ，t h i s p a p e ri n t r o d u c e dt h eg e n e r a t i o n ，c o n c e p t s ，p r o c e s s e s ，f u n c t i o na n ds oo n a m o n g t h e m ，i tf o c u s e do na l lo v e r v i e wo fm i n i n ga s s o c i a t i o nr u l e s ，i n c l u d i n gi t sd e f i n i t i o n ， t h ec l a s s i ca l g o r i t h m s ，a n di n c r e m e n t a lu p d a t i n go fa s s o c i a t i o nr u l e s s u b s e q u e n t l y , i nc h a p t e rt h r e e i td e m o n s t r a t e dt h en e e do fi n c r e m e n t a l u p d a t i n gc l a s s i f i c a t i o na s s o c i a t i o nr u l e s a n db a s e do ni t ，t h ep a p e rr a i s e dan e w i m p r o v e da l g o r i t h mt os o l v et h ep r o b l e m so fu p d a t i n gc l a s s i f i c a t i o nr u l e sw h e nt h e i i i 亘堕坚望堑塑塑竺塑茎壁塑型生里堡窒 肌l l l m u ms u p p o r t t h r e s h o l d ( m i n s u p ) c h a n g e d t h e nf u r t h e rr a i s e dt w on e w a i g o r i t h m st oo b t a i nt h eu p d a t i n gc l a s s i f i c a t i o nr u l e sw h e nt h ed a t a b a s e c h a n g e d ， i n c l u d i n ga d d i n gs o m en e wd a t aa n dd e l e t i n gt h eo l dd a t a a n di nc h a p t e rf o u r , t h ep a p e ru s et h ed a t as e t ，w h i c hh a m e d g e 肌a i lc r e d i t d a t a ，f r o mu c ia sa l li n s t a n c ef o r t h ei n c r e m e n t a lu p d a t i n gc l a s s i f i c a t i o na s s o c i a t i o n r u j e ss y s t 锄d e s i g na n di m p l e m e n t a t i o n ，f u r t h e re x a m i n e t h e s ea 1 9 0 珊1 i i l si i l c h a p t e rt h r e e t h ep a p e ri sf o ra p p l i c a t i o n o r i e n t e dc l a s s i f i c a t i o na n dp r e d i c t i o nd a t al l l i n i n g 妣h n o l o g y , s u c ha sc u s t o m e rr e l a t i o n s h i pm a n a g e m e n t , p r o d u c ts a l e s a 1 1 a l y s i s t 0 p r o n l o t es u c ni n d u s t r i e sa sb u s i n e s sa n df n a n c i a li n t e l l i g e n c e ，e t c i th a sac e n a i l l d e g r e eo fg u i d a n c ea n dr e f e r e n c es i g n i f i c a n c e k e yw 。r d s ：d a t am i n i n a s s 。c i a t i 。n r u l e s ，c l a s s i f i c a t i o n ，i n c r e m e n t a lu p 枷n g ， f r e q u e n ti t e m s e t s i v 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师型羞劐整丝指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何 其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印刷 版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库供检 索；2 ) 为教学、科研和学术交流目的，学校可以将公开的学位论文或解密后的 学位论文作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中国学位论文全 文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 硝翩躲却劣 签字日期：歹。i 口年j 月 日 签字日期：印o 年厂月7 日 四川师范大学硕t 学位论文 第一章绪论 1 1研究背景和意义 伴随着数据库技术以及计算机硬件，尤其是存储介质的飞速发展，各行各 业可以收集并保存更多的数据，这使得各种各样的数据爆炸式的快速增长。然 而由于缺乏有效的处理手段，人们却难以从这些大量的数据中获取所需的更多 有趣、潜在有用的知识。于是数据挖掘技术应运而生，并快速发展，已经成为 信息技术领域的一大热点。 分类预测是数据挖掘技术的重要功能之一。如何利用数据挖掘技术高效地 对已知的数据进行学习、分析，以获得对未来发展趋势的准确、有效的分类和 预测信，g 自然受到了广泛的关注和研究，并且其研究成果也迅速地投入到实际 的应用中。 本论文以增量关联规则高效更新的相关技术为研究背景，探讨、研究了在 诸如客户管理中的优质客户、流失客户分析，商业管理中广告定向投放、产品 布局、捆绑销售及促销等只关注分类预测结果中某些特定类别的应用中增量关 联规则高效更新的关键技术。论文对在此类应用中，针对数据集不变而最小支 持度阈值( m i n s u p ) 和最小置信度阈值( m i n c o n f ) 发生改变，以及最小支持度 阈值( m i n s u p ) 和最小置信度阈值( m i n c o n f ) 不变时所挖掘的数据集中数据增 加或数据减少的三种情况进行了重点分析、研究，在原有高效更新算法的基础 上提出了更契合应用实际的新的优化算法。在论文最后提出了一个基于增量关 联规则高效更新的银行信贷风险分类预测的应用系统设计方案，并进行了实验 及检测评价。 论文所做的工作对于客户管理、商业应用中的面向分类预测的数据挖掘技 术，如进行客户关系管理、商品销售分析、推进商业和金融业等行业智能化等 方面都具有一定的指导和借鉴意义。 1 2 国内外研究现状 随着数据库技术以及计算机硬件技术的稳步、快速发展，使得各行各业均 采集了大量的数据。然而，由于缺乏有效的分析和处理技术，使得决策者们在 面对这些丰富的数据时仍然无法获得充足的信息。为了改善这种状况，数据仓 面向分类预测的增量关联规则应用研究 库与数据挖掘技术的研究在2 0 世纪8 0 年代后期开始兴起。 1 2 1关联规则挖掘研究的现状 在事务数据库中进行关联规则的挖掘是由r a g r a e a l 等人首先提出【2 】，现在 已经成为数据挖掘领域的研究重点之一。早期的一些经典关联规则挖掘算法， 如a p r i o r i 算法等，所处理的数据集都是相对固定的静态数据集【3 】。当数据集中 的数据发生增加、删减，或者调整最小支持度阈值时，已有的挖掘结果就无法 再进行利用，算法只能完全重新执行整个关联规则挖掘过程，严重降低了运行 效率。为了避免这种情况的发生，增量关联规则的应用研究成为了关联规则挖 掘研究中的热点。 综合文献 4 - 2 3 】，当前增量关联规则的研究主要涉及以下三个方面： 1 所挖掘数据集不变，而最小支持度阈值( m i n s u p ) 和最小置信度阈值 ( m i n c o n f ) 发生变化的情况。 2 最小支持度阈值( m i n s u p ) 和最小置信度阈值( m i n c o n f ) 不变，所挖 掘数据集中数据增加的情况。 3 最小支持度阈值( m i n s u p ) 和最小置信度阈值( m i n c o n f ) 不变，所挖 掘数据集中部分数据被删减的情况。 针对1 和2 ，当前研究成果较多，文章【4 7 】已经提出了一些比较成熟完备 的算法，如f u p 算法、i u a 算法、p i u a 算法等。针对3 ，当前主要的处理方 式为对删减后剩余的数据集重新执行原挖掘算法，高效更新算法很少。 1 2 2 数据挖掘中分类预测应用的研究现状 从数据挖掘中的分类和预测应用研究而言，当前主要有 1 】【2 4 】：用决策树归 纳分类、贝叶斯分类、基于规则的分类、神经网络分类、支持向量机、关联分 类等。对于以上各种方法的比较仍然是一个研究课题，目前还没有发现某种方 法对所有数据集进行处理的效果都优于其他方法1 1 】o 下面依次简要介绍各种分 类和预测的主要技术和方法的情况： 1 用决策树归纳分类 决策树归纳分类所获得分类规则容易理解、速度快、不需要背景知识【2 5 1 ， 2 四川师范大学硕上学位论文 在分类预测中得到了广泛应用。著名的算法主要有以信息增益作为测试属性选 择度量的i d 3 算法【2 6 1 ，以及为改进1 1 3 3 算法的属性选择倾向于包含属性值多的 属性而使用信息增益率作为属性选择度量的c 4 5 算法等。但这些算法在每个结 点都只测试单个属性，造成决策树中子树重复和某些属性在决策树的某一路径 上被多次测试的情况【27 | 。为改善这些问题，构造多变量决策树的研究成为决策 树研究的新热点。 2 贝叶斯分类 贝叶斯网络以概率网络的形式描述了一组离散变量的联合分布【2 引。贝叶斯 定理和贝叶斯假设是贝叶斯学习的两大支柱【2 9 1 。朴素贝叶斯分类基于后验概率 的贝叶斯定型1 1 。它针对每个项目通常只会有相对较少的特征数，并且对项目 的训练和分类也仅仅是针对特征概率的数学运算，因而它在接受大数据量的训 练和查询时具备高速度【3 0 l 。但贝叶斯定理假设一个属性对于给定类的影响独立 于其他属性，然而此假设在实际情况中却经常不成立【3 1 1 ，即它不能处理基于特 征组合所产生的变化结果。因此，对贝叶斯方法的提高【3 2 1 、降低贝叶斯分类的 独立性假设的研究是当前贝叶斯分类研究的热点。 3 神经网络分类 神经网络具有很强的函数拟合能力、自学能力和分类能力，在分类预测中 的应用也比较广泛。但是由于每个神经元行为的数学描述都是一个多变量的非 线性函数方程，组成网络后的庞大多变量非线性方程组更难以进行数学分析 1 3 3 1 ，也难以理解。用于分类的常见神经网络模型包括：b p 神经网络、r b f 神 经网络、自组织特征映射神经网络、学习矢量化神经网络。目前，神经网络分 类算法研究多集中在以b p 为代表的神经网络上【3 。 4 支持向量机 基于统计学习理论的支持向量机( s v m ，s u p p o r tv e c t o rm a c h i n e ) 是一种重 要的分类算法。作为有监督的机器学习方法，它采用经验风险最小化和结构风 险最小化准则，比较好地解决了小样本、非线性、高维数和局部极小点等问题， 具有较好的泛化能力【3 4 】【3 5 】。在分类应用方面，它已经比较成功地被应用于文本 分类、人脸识别、图像分析掣3 4 1 领域。但它所具有的高时间复杂度【3 6 1 又成为了 它进一步发展的主要障碍。 面向分类预测的增量关联规则应用研究 5 关联分类 关联分类中，关联规则的产生和分析旨在用于分类。由于其可以考察多属 性之间的高置信度关联，使得其准确率比诸如c 4 5 等传统的分类方法更高。关 联分类可以用于诸如产品布局、分类设计和交叉销售等许多决策过程。【l 】当前， 用于关联分类的方法主要有三种【l 】：c b a ( c l a s s i f i c a t i o n - b a s e d a s s o c i a t i o n ，基 于分类的关联) 、c m a r ( c l a s s i f i c a t i o nb a s e do nm u l t i p l er u l e s ，基于多关联规 则的分类) 和c p a r ( c l a s s i f i c a t i o nb a s e do np r e d i c t i v ea s s o c i a t i o nr u l e s j ) 。 1 3本文主要研究内容和所做工作 通过大量的查阅和研究国内外有关关联规则挖掘和增量式关联规则更新的 文献资料，并结合分类预测应用的实际，本文提出了更有针对性的增量关联规 则更新改进算法。并根据此算法建立了一个银行信贷风险分类系统作为实例。 具体而言，本文的研究内容和所做的工作主要包括： 1 结合实际，针对客户管理、商业分析等应用进行分析，论述只关注分类 预测结果当中某些特定类别的应用的需求、有效性和优点。 2 分析并总结论述了关联规则挖掘、增量关联规则挖掘与更新相关技术的 现状。 3 基于面向分类预测的应用，对增量关联规则的挖掘与更新技术做了重点 论述。针对所挖掘数据集不发生改变，但最小支持度阈值( m i n s u p ) 和最小置 信度阈值( m i n c o n f ) 发生改变的情况，在原有高效更新的算法基础上提出了更 契合本应用实际的优化算法，并进行有效性实验。 4 以第3 点中所述优化算法为基础，进一步提出处理最小支持度阈值 ( m i n s u p ) 和最小置信度阈值( m i n c o n f ) 不变时，所挖掘数据集中的数据发生 增加或减少时高效更新面向分类预测的增量关联规则的新算法，并进行有效性 实验。 5 结合u c i 数据集中某德国商业银行信贷风险分类数据的实际应用背景， 提出了一个分类预测应用系统的设计方案。采用v i s u a ls t u d i o2 0 0 5 中c 和 m i c r o s o f ts q ls e r v e r2 0 0 0 进行开发、实验及检测评价。 4 四川师范大学硕上学位论文 1 4 研究方法和论文框架结构 本文采用的研究方法主要是理论研究与实证研究相结合。在阅读大量增量 式关联规则更新、分类预测的文献资料的基础上，采用实际数据，对提出的改 进算法和扩展算法进行验证以及实例评价。 本论文的框架结构如下： 第一章：绪论。主要介绍研究背景和意义、国内外研究现状，以及本文的 主要研究内容和所做的工作。 第二章：介绍数据挖掘、关联规则挖掘与更新的相关概念和应用背景。 第三章：面向分类预测的增量关联规则更新的算法基础及算法有效性实验。 第四章：介绍了结合某银行信贷风险分类数据的实际应用背景的分类预测 应用系统的设计、模型建立、有效性实验、检测及评价等。 第五章：总结与展望。 其中，第三章和第四章是论文的核心部分，也是论文研究成果的集中体现。 面向分类预测的增量关联规则应用研究 第二章关联规则挖掘及更新概述 2 1数据挖掘概述 2 1 1数据挖掘技术的产生和概念 众所周知，数据库技术在2 0 世纪获得了飞速发展和广泛应用。从2 0 世纪 6 0 年代开始，信息技术历经了由简单的文件处理向数据库系统演进，进而发展 对到层次、网络数据库，关系型数据库、数据建模工具和索引、存取方法，扩 充关系的、对象关系的等高级数据模型和高级应用，数据仓库等的研究【1 】【3 8 1 。 同时，伴随着计算机硬件技术，尤其是存储介质的快速发展，数据库中采集的 数据急剧膨胀。但是由于缺乏对数据进行有效分析和处理的能力，使得人们不 得不面临“数据丰富，但信息贫乏 的尴尬情形。为了应对这一挑战，数据挖 掘和知识发现应运而生，并成为了信息处理的骨干技术之一。 通常所说的数据挖掘，是数据挖掘的广义定义，它与数据库中的知识发现 ( 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 ) 含义相同。k d d 一词首次出现在 1 9 8 9 年8 月举行的第1 1 届国际人工智能叙述会议上【3 9 】。它指的是从存放在数 据库、数据仓库或其他信息库中的大量数据中发现有趣且潜在有用的知识或模 式的过程。本文中所涉及的“数据挖掘”一词，除特别指出的以外，均指广义 观点的数据挖掘。 数据挖掘是一个多学科交叉的研究领域，它把人们对数据的引用提升到了 从中发掘知识并用于支持决策的新高度，融合了数据库技术、人工智能、机器 学习、统计学、模式识别等f 1 】【删一系列学科和技术的研究成果，展现出蓬勃的 生机。 2 1 2 数据挖掘的过程 数据挖掘是一个需要经过不断反复的，包含众多处理阶段的复杂处理过程。 对于数据挖掘过程模型，众多的数据挖掘软件供应商和数据挖掘资讯公司都提 出了各自的数据挖掘过程模型。在这些模型中，由u s a m am f a y y a d 等人提出 的模型f 4 1 1 ，得到了广泛的认可。 下面就以f a y y a d 等人提出的过程模型为基础，对数据挖掘过程作概要性介 绍。f a y y a d 过程模型【3 8 】【4 1 】【4 2 】【4 3 1 是一个高级处理过程，它包含多个处理阶段， 6 四川师范大学硕士学位论文 每个阶段之间都相互影响，反复调整，形成了一种螺旋式上升的过程，如图2 1 所示。 k 一数据准备_ 4 磁据掺掘一果表达一 在广义观点的数据挖掘的众多阶段之中，狭义观点的数据挖掘仅仅是其中 一个主要的、核心的阶段。整个广义观点的数据挖掘的主要阶段【l 】【3 8 】【4 l 儿4 2 】【4 3 】 有： 1 数据选取 根据挖掘目标，从原始数据集中分析、确定、选取与挖掘任务相关的数据 集，并将来自不同数据源的数据集成起来。 2 数据清洗 原始数据通常并不完美，其中不可避免地包含着噪声和离群点、数据遗漏、 数据不一致或重复、数据有偏差、或者数据不代表描述所设想的现象或总体情 况【删。在数据挖掘中将这些数据称为“脏 数据。在数据清洗阶段需要利用各 种数据预处理手段对“脏”数据进行处理，使之成为能用于数据挖掘的“干净” 数据。 3 数据转化 数据转化的目的是将目标数据转换为适合于进行数据挖掘的数据存储形 面向分类预测的增量关联规则应用研究 式，其方法包括改变数据的组织方式、变换数据的存储类型、或者使用数学 逻辑算子对数据进行转换等一系列措施。 4 数据挖掘 该阶段的数据挖掘是狭义观点的数据挖掘，主要是指通过选取合适的智能 方法【4 5 1 ，如：分类、聚类、关联规则、神经网络等，对目标数据集中的数据进行 分析、处理，以获取潜在有用知识的过程。 5 模式评估 该阶段根据一定的评价、度量标准，判断获取结果的价值，识别获取的结 果中真正有意义的知识。若未能获取有用的知识，则需要重复执行以上挖掘过 程，直至获取有用的知识。 6 知识表示 该阶段利用各种可视化和知识表达技术，向用户反馈所获取到的真正有意 义的、潜在有用的知识。 2 1 3 数据挖掘功能 数据挖掘功能用于指定数据挖掘任务要找的模式类型【l 】【4 1 1 。根据挖掘的目 的，数据挖掘任务一般又被分为描述型数据挖掘和预测型数据挖掘两类。描述 型挖掘任务【l 】描述数据库中数据的一般性质，它一般可以通过数据特征化、数 据区分及比较等技术来得以实现晰】。预测型挖掘任务通过对已知数据的分析来 对目标数据进行推断、预测。 具体而言，数据挖掘功能以及它们可以发现的模式类型包括【l 】：概念类描 述、频繁模式、关联和相关、分类和预测、聚类分析、离群点分析、演变分析 等。下面对常用的数据挖掘功能进行简要介绍： 1 概念类描述 概念类描述是种描述性数据挖掘，它被用于在大量的细节数据中提取更 加简洁、抽象的一般性描述，并使得用户可以简便、灵活地在不同的抽象层次、 粒度考察数据。 2 频繁模式、关联和相关 通过发掘频繁出现的模式进一步获取到事务之间有趣的内在联系，更详细 8 四川师范大学硕上学位论文 的介绍参见2 2 节。 3 分类和预测 分类和预测是两种数据分析方式。 分类是指通过对已知类标号的训练集进行学习、训练后，提取出能够尽可 能准确地进行分类的模型用于对未知类标号的项分类的两步数据分析过程。 预测是指构造和使用模型对无标号类进行评估，或者对给定的样本进行数 值预测的数据分析方法。 当前用于分类和预测的最主要的技术是决策树。它以每个内部节点( 非树 叶节点) 表示对某一个属性的测试，以每个分枝代表对测试的结果输出，直到 最终在叶节点上获取分类和预测的类标号作为结果。 此外，正如上文提及的，由于可以同时考虑多个属性之间的关联，从而可 以获得更好的分类、预测效果的关联规则也是被用于分类、预测的众多的数据 挖掘技术之一。 4 聚类分析 聚类1j 【3 8 1 就是将抽象的对象的集合分成相似的对象类或簇的过程。它根据 对象的属性值来评估其相似度，并要求所划分的每个对象类或簇的内部具有非 常高的相似度，同时，在不同的对象类或簇之间的相似度又尽可能的低。 与分类和预测不同的是聚类分析是一种无监督学习方式，它所要分析的数 据集的每个对象的类标号都是未知的。当前，主要的聚类技术包括【l l ：划分方 法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法、高维数 据的方法( 如：基于频繁模式的方法) 和基于约束的聚类。此外，离群点检测 也可以使用聚类技术。 5 离群点分析 离群点【1 】是指那些与数据的一般模型或行为表现不一致的数据对象。虽然 在一些数据挖掘过程中它们会作为噪声被排除掉，但是有时对这些离群点进行 分析，也可能会发现一些有用的信息。比如，现在离群点分析就经常被用于银 行业的欺诈检测分析，以及医疗业的各种医疗处置不寻常反应分析等。 通常用于离群点分析的主要方法有【l 】：基于统计分布的离群点检测、基于 距离的离群点检测、基于密度的局部离群点检测、基于偏差的离群点检测等。 9 面向分类预测的增量关联规则应用研究 6 演变分析【1 】【4 7 】 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋 势，并对其建模。尽管这可能包括时间相关数据的特征化、区分、关联和相关 分析、分类、预测或聚类，这些分析的不同特点包括时间序列数据分析、序列 或周期模式匹配和基于相似性的数据分析。 2 2关联规则挖掘与更新概述 2 2 1关联规则挖掘概述 关联规则挖掘起源于对大型事务数据库中频繁模式的挖掘。在挖掘这些频 繁模式的过程中导致了发现其中频繁项集之间有趣的联系。这些联系可以用关 联规则模式化地表示出来。 关联规则的形式化描述如下【1 】：设卜 1 1 ，1 2 ，i m 是项的集合。设任务 相关的数据d 是数据库事务的集合，其中每个事务t 是项的集合，使得t i 。 每一个事务有一个标识符，称作t i d 。设a 是一个项集，事务t 包含a 当且仅 当a t 。关联规则是形如a j b 的蕴含式，其中a c i ，b c i ，并且a n b = 囝。 规则a j b 在事务数据集d 中成立，具有支持度s ，其中s 是d 中事务包含a u b 的百分比，它是概率p ( a u b ) 。规则a j b 在事务集d 中具有置信度c ， 其中c 是d 中包含a 的事务同时也包含b 的百分比，这是条件概率p ( b i a ) 。 即： s u p p o r t ( a j b ) = p ( a u b ) c o n f i d e n c e ( a b ) = p ( b i a ) 同时满足用户指定的最小支持度阈值( m i n s u p ) 和最小置信度阈值 ( m i n c o n f ) 的规则称作强规则，即所要挖掘的关联规则。 关联规则挖掘的主要步骤有两步： 1 筛选出所有满足用户指定的最小支持度阈值( m i n s u p ) 的项目集，称为 频繁项目集。 2 验证所有的频繁项目集及其子集是否满足最小置信度阂值( m i n c o n f ) 。 若满足最小置信度阈值( m i n c o n f ) 则为所需的关联规则，否则不是。 由于在己知频繁项目集的情况下求取并验证其置信度相对容易，而且已经 l o 四川师范大学硕士学位论文 有比较成熟、高效的算法。因此，关联规则挖掘算法的研究主要集中于如何高 效获得频繁项目集。 2 2 2 关联规则挖掘的经典算法概述 a p r i o r i 算法【2 】是关联规则挖掘中最经典的算法之一，是由r a g r a w a l 和 r s r i k a n t 于1 9 9 4 年提出的。该算法是通过逐层搜索的迭代方法扫描目标数据 库，每一次扫描数据库都产生一个层次的频繁项集的集合、将其加入频繁项集 的集合f ，并以此次产生的频繁项集的集合作为产生下一层次的频繁项集的集 合的基础，直到所有的频繁项集都已经生成并包含于频繁项集的集合f 中。 具体而言，在第一次扫描数据库时，统计每个项的个数，并收集满足最小 支持度的项，生成频繁1 项集，记作l 1 。随后，在第i 次( i - 2 ，3 ，) 扫描 数据库时，通过将上次产生的频繁项集l i 1 与自身连接产生候选项集的集合c i ， 统计c i 中的每个i 项集的绝对计数，并检验其是否满足由用户所指定的最小支 持度阈值( m i n s u p ) 换算而来的绝对支持度计数阈值。若满足则将其加入频繁 i 项集的集合，记作l i ，然后再迭代使用l i 产生k + l ，直到无法再产生新的频 繁项集。 这种方法虽然简单易行，但每次产生l i 都要扫描一次数据库，将产生大量 的i o 负载和庞大的候选集。 为了减少生成频繁项集所造成的严重的i o 负担，j i a w e ih a n 等提出了 f p t r e e 算法【4 8 1 。不同于a p r i o r i 算法的广度优先搜索，f p t r e e 算法是一种深度 优先搜索算法。该算法采用分治策略，直接将产生频繁集的数据库压缩到一颗 频繁模式树，然后通过该树产生关联规则，而不使用候选集。但它虽然只扫描 数据库两次，却需要占用大量的内存f 3 8 j f 4 9 1 。 2 2 3 增量关联规则更新概述 通常，传统的关联规则经典算法对所处理的目标数据库都隐含着假设其不 发生改变的条件。但与这一假设相冲突的是实际应用中的数据库大多数都会实 时、不断地发生各种各样的变化。当这些数据库中的数据增加或者减少的时候， 甚至在数据库不发生改变，而仅仅改变用户指定的最小支持度阈值( m i n s u p ) 面向分类预测的增量关联规则应用研究 和最小置信度阈值( m i n c o n f ) 的时候，a p r i o r i 等传统经典算法便完全无法对 已有的挖掘结果进行再利用。此时，如果仍然要运用它们来获得变化后的关联 规则，唯一的办法就是完全重新执行整个关联规则挖掘过程。这种办法无疑会 严重地降低计算机获取关联规则的效率。为了应对这一挑战，增量关联规则更 新算法开始出现。而如何高效地进行增量关联规则更新也成为了关联规则挖掘 研究领域的新兴热点之一。 所谓增量关联规则更新，就是指当原目标数据库发生变化，或者最小支持 度阈值( m i n s u p ) 和最小置信度阈值( m i n c o n f ) 发生变化的时候，在充分利用 此前已有的挖掘结果的基础上，仅对涉及变化部分的数据集进行扫描、分析， 从而高效率地将关联规则更新的方法。 综合文献 4 - - 2 3 ，此前所述的数据库无改变而最小支持度阈值( m i n s u p ) 改变，以及最小支持度阈值( m i n s u p ) 不变而数据库中数据发生增、减等三种 情况正是现在增量关联规则更新研究中的热点。其中，又以对最小支持度阈值 ( m i n s u p ) 发生改变的情况的研究最多，而负增量式关联规则研究相对较少。 使用增量式更新的方法对关联规则进行更新，可以充分利用原有的挖掘结 果，避免了在更新关联规则时因为需要重复获取已知却无法再利用的挖掘结果 而造成的对目标数据库中大量的没有变化的数据项进行的反复扫描，从而大大 提高了系统的工作效率，打破了原有关联规则挖掘只能应用在静态数据库的瓶 颈，使得高效率地对动态数据库的关联规则进行更新成为现实。 在本文中将依次讨论最小支持度阈值( m i n s u p ) 改变、数据集中数据增加 和数据集中数据减少三种情况下分类预测增量关联规则的高效更新。 由于当所挖掘的目标数据集中的数据增加或者减少时，目标数据集的大小 将呈现出正增长或者负增长，因此，在本文中所挖掘的数据集中的数据增加时 的分类预测增量关联规则挖掘算法和数据减少时的分类预测增量关联规则挖掘 算法也分别被称为正增量分类预测关联规则挖掘算法和负增量分类预测关联规 则挖掘算法。 1 2 四川师范大学硕士学位论文 第三章面向分类预测的增量关联规则更新算法 3 1 算法的必要性 由于关联规则挖掘与数据挖掘的分类应用所具有的挖掘相关性强的项目集 的集合【5 0 】的共性，关联规则挖掘的方法被尝试用于分类应用。经验证【l 】，由于 可以考虑多个属性之间的高置信度关联，将关联规则挖掘方法用于分类应用可 以取得较好的效果。 但是，在传统的关联规则挖掘过程中，需要对所有频繁项目集的非空子集 进行计算，从而最大程度地获取更多的规则。然而事实上，在某些分类预测的 实际应用中，用户往往只关注分类预测结果当中的某些特定的类别。如：客户 管理中的优质客户、流失客户，商业管理中的广告定向投放、捆绑销售及促销 等。因而，在这类应用中，传统的挖掘方式获得的规则中将包含众多用户不关 注的规则。这样既不方便用户浏览挖掘结果，又浪费了计算机的资源、降低了 效率。 因此，有必要根据上文提出的应用实际，提出契合其特点的高效的面向分 类预测的增量关联规则更新算法。 3 2i l l in s u p 和m in c o n f 改变时的分类预测增量关联规则更新算法 3 2 1算法基础 新的改进算法沿用了文章【6 中算法的基本思想，即在扫描数据集一次后， 记录所有非空项目集及其支持度计数，在生成频繁项目集时反复利用，避免多 次、重复扫描数据集。 同时，针对本文研究的只关注分类预测结果中某特定的类别的应用，由于 所需的关联规则的结果相对固定，原算法在记录支持度计数非零的项目集的过 程中将产生大量与所需结果无关的无效记录。因此，本文在其基础上提出了新 的改进算法。该新算法在只增加扫描数据库一次的前提下，避免了众多无效记 录的产生，从而降低了算法运行的空间需求，并使得挖掘结果聚焦度提高，又 根据此类应用的实际情况，将其扩展为挖掘多维关联规则。在挖掘多维关联规 则的过程中，事务项变为属性值对，而项目集则称为谓词集。 面向分类预测的增量关联规则应用研究 3 2 2 算法描述 算法分为两个阶段：第一阶段，高效统计出每一非空谓词集的支持度计数； 第二阶段，可交互式地产生或更新具有用户指定的最小支持度的频繁谓词集【2 】。 对于每一个谓词集都有一个c o u n t 域来存储其支持度计数，算法描述如下： 算法1 统计各谓词集的支持度计数 输入：数据库d b ，谓词集i 为d b 中所有属性值对。 输出：所有支持度计数非零的谓词集所产生的候选集c ，及c 中每一谓词 集所对应的支持度计数。 算法描述： 1 ) 初始化c = o 2 ) 令d = ( d e c = x ) ) 3 ) f o ra l lr e c o r d st d bd o 3 1 )f o ra l li t e m s e t sc c _ td o 3 2 )求包含属性d e c = x 的谓词集计数： i f c ) o d ) o 若c 的d e c 属性为x 3 3 ) i fc ct h e n 若c 存在于c 中 3 4 )c c o u n t + + c 的计数增加1 3 5 )e l s e 3 6 ) c = c u c 将c 加入至0c 中 3 7 1c c o u n t = 1 设置其计数为l 3 8 )f o ra l li t e m s e t sc cd o 3 9 )求与包含属性d e c = x 的项的不包含属性d e c - - - x 的子集的 计数： c - - - - c d 1 4 四川师范大学硕上学位论文 3 1 0 )i fc ct h e n 若c 存在于c 中 3 1 1 ) c c o u n t + + c 的计数增加1 3 1 2 )e l s e 3 1 3 ) c = c u c 将c 加入到c 中 3 1 4 )c c o u n t = 1 设置其计数为1 由算法l ，显然有： 定理1 由算法1 所产生的候选谓词集的集合c 包含且仅包含数据库d b 中 与分类结果为d e c = x 相关的支持度计数非零的谓词集。 下面来讨论目标数据库d b 没有发生改变而最小支持度阈值( m i n s u p ) 发 生改变的情况： 设变化后的最小支持度阈值为m i n s u p ，原有最小支持度阈值为m i n s u p ，则 最小支持度阈值可能的变化方式可以描述为以下两种情况： 1 m i n s u p m i n s u p 针对上述的情况1 ，由于新设置的最小支持度m i n s u p 减小，原有的候选谓 词集的集合c 中的一些非频繁谓词集的支持度计数可能变得大于等于最小支持 度计数，从而成为频繁谓词集合中的项。而原有的频繁谓词集f 中的谓词集的 计数则显然都大于等于新的最小支持度。因此【6 】，只需要判断候选谓词集的集 合c = c f 中的所有非