（计算机应用技术专业论文）关联规则挖掘技术在税收执法管理中的应用研究.pdf

关联规则挖掘技术在税收执法管理中的应用研究 摘要 应用数据挖掘技术，加强税收数据进行分析，为税务系统强化科学管理提 供有价值的决策信息，已经成为当前税务系统的一个研究热点。本文针对当前 税收执法管理工作中存在的不足，结合税收行业数据特点，提出了一种基于h a s h 和项集空间划分的关联规则挖掘算法一s a v m 算法，并将关联规则挖掘技术和 s a v m 算法应用到税收执法数据分析中，找出了税收执法过错行为和税收执法 者特征之间的关联关系，为税务系统加强税收执法管理提供了非常有价值的参 考信息。 本文的主要工作和创新点如下： 一、阐述了数据挖掘技术在税务系统的应用现状，全厦介绍了税收执法管 理的内容、方法和存在的不足，分析了应用数据挖掘技术开展税收执法数据分 析的重要意义。 二、阐述了数据挖掘的基本理论、主要技术、知识分类、常用挖掘工具和 研究趋势，深入研究了关联规则挖掘技术，重点介绍了几种经典关联规则挖掘 算法，分析了各种挖掘算法的优、缺点，指出了关联规则挖掘技术的研究热点 和发展趋势。 三、提出一种基于h a s h 和项集空间划分的关联规则挖掘算法一s a v m 算 法。将事务数据库转换成比特向量表示形式，通过向量的与运算来计算项集的 支持度，在挖掘过程中只需扫描一遍数据库；运用h a s h 技术，在第一次扫描数 据库的过程中，直接生成频繁2 项集，提高算法的执行效率；采用基于共同前缀 的划分方法，将已生成的频繁项集划分到不同的子空间，在每个独立的子空间 内生成候选项集，减少连接次数。实验结果表明，s a v m 算法提高了关联规则 挖掘的效率。 四、将关联规则挖掘技术应用到税收执法数据分析中，详细阐述了数据选 择、预处理、挖掘频繁项集和生成关联规则等处理过程，对生成的规则进行了 分析，得出了对税务系统加强税收执法管理具有重要参考意义的结论。同时， 也为将关联规则挖掘技术应用到税收管理的其他领域提供了一个可供借鉴的方 法。 关键词：数据挖掘关联规则s a v m 算法税收执法管理 1 1 1 t h e a p p l i c a t i o nr e s e a r c h t e c h n o l o g yi nm a n a g e m e n t o fa s s o c i a t i o nr u l e sm i n i n g o ft a x a t i o nl a we n f o r c e m e n t a b s t r a c t i n s i s t i n gi nm a n a g i n gt a x a t i o nb yl a w ，b u i l d i n guj u s t i c ea n dj u s t n e s s e n v i r o n m e n to f t a x a t i o nl a we x e c u t i o n ，i sav e r yi m p o r t a n t p a r t o f b u i l d i n gh a r m o n i o u ss o c i a l i s ms o c i e t y ，a n dt h es t a r ta n ds t a n dp o i n to f c u r r e n tt a x a t i o ns y s t e m d e v e l o p i n gt a x a t i o nw o r k h o wu s i n gt o d a y s i n f o r m a t i o nt e c h n o l o g y ，e s p e c i a l l yt h ed a t am i n i n gt e c h n o l o g y ，t oa n a l y z e t h et a x a t i o nl a we x e c u t i o nd a t at h a tw eg o t ，a n dp r o v i d eu s e f u ld e c i s i o n i n f o r m a t i o nf o rt a x a t i o ns y s t e mt oe n h a n c em a n a g e m e n to ft a x a t i o nl a w e x e c u t i o nh a sb e e nah o tr e s e a r c hp o i n to ft a x a t i o ns y s t e m b a s e do nt h e d e e pr e s e a r c ho fa s s o c i a t i o nr u l e sm i n i n gt e c h n o l o g y ，t h i sd i s s e r t a t i o n p o i n t e do u tt h ea d v a n t a g e s a n d d i s a d v a n t a g e s o fs e v e r a lc l a s s i c a s s o c i a t i o nr u l e sa l g o r i t h m s ，a n dd e v e l o p e daa l g o r i t h mt h a tb a s e do n h a s ha n di t e ms e t ss p a c ed i v i s i o n 一一s a v ma l g o r i t h m s i ta l s oa p p l y a s s o c i a t i o nr u l e st e c h n o l o g ya n ds a v ma l g o r i t h m st o a n a l y z i n gt h e t a x a t i o nl a we x e c u t i o nd a t a ，f o u n dt h er e l a t i o n s h i pb e t w e e nf a u l ta c t i o n s o ft a x a t i o nl a we x e c u t i o na n dt h eo n ew h om a k et h e m ，p r o v i d es o m ev e r y v a l u a b l er e f e r e n c ei n f o r m a t i o nf o rt h et a x a t i o ns y s t e mt oe n h a n c et a xl a w e x e c u t i o n t h em a i nj o ba n di n n o v a t i o np o i n t so ft h i sd i s s e r t a t i o na r e ： 1 d e s c r i b e dt h ec u r r e n ts i t u a t i o no fd a t am i n i n gt e c h n o l o g ya p p l i e d i nt a x a t i o n s y s t e m ，g i v e n af u l lv e r s i o no ft a x a t i o nl a we x e c u t i o n m a n a g e m e n t sc o n t e n t ，m e t h o d s a n dw e a k p o i n t s ，a n a l y z i n g h o w i m p o r t a n tt oa p p l yd a t am i n i n gt oa n a l y z i n gt a x a t i o nl a we x e c u t i o n 2 i n t r o d u c e dt h eb a s i ct h e o r y ，m a i nt e c h n o l o g y ，k n o w l e d g e c l a s s i f i c a t i o n ，c o m m o n u s e dt o o l sa n dt h er e s e a r c h t r e n d d e e p l y r e s e a r c h e da s s o c i a t i o nr u l e st e c h n o l o g y ，a n di n t r o d u c e ds o m ec l a s s i c a l a s s o c i a t i o nr u l e s a l g o r i t h m sb y s t r e s s a n a l y z e dt h ea d v a n t a g e s a n d d i s a d v a n t a g e so fa l la l g o r i t h m s ，a n dp o i n t e do u tt h er e s e a r c hh o tp o i n t a n dd e v e l o pt r e n do fa s s o c i a t i o nr u l e sm i n i n gt e c h n o l o g y 3 d e v e l o p e daa l g o r i t h mt h a tb a s e d o nh a s ha n di t e ms e t s s p a c e d i v is i o n 一一s a v ma l g o r i t h m s i tc o n v e r t e dt r a n s a c t i o nd a t a b a s ei n t ob i t e v e c t o r ，b yt h ev e c t o r so r p e r a t i o nt og e ti t e ms e t ss u p p o r td e g r e e ，a n dj u s t i v o n et i m es c a ni nd a t a b a s e w i t h i nh a s ht e c h n o l o g y ，i tb u i l df r e q u e n t2 i t e ms e t s b y o n et i m es c a nd a t a b a s e ，t o i m p r o v e t h e e f f i c i e n c y o f a l g o r i t h m b yu s i n gt h ec o m m o np r e f i x ，i td i v i d e df r e q u e n ti t e ms e t si n t o d i f f e r e n ts u bs p a c e s c a n d i d a t ei t e ms e t sw e r eb u i l ti ne v e r yi n d e p e n d e n t s u bs p a c et od e c r e a s et h ec o n n e c t i o nt i m e s t h ee x p e r i m e n t sr e s u l tt e l l s u ss a v ma l g o r i t h m si m p r o v e dt h ee f f i c i e n c yo fa s s o c i a t i o nr u l e sm i n i n g 4 a p p l yd a t am i n i n gt e c h n o l o g y t ot a x a t i o nl a we x e c u t i o nd a t a a n a l y z i n g ，e x p l a i n e dt h ed a t ac h o o s e ，p r e p r o c e s s ，m i n i n gf r e q u e n ti t e m s e t sa n dd e v e l o pa s s o c i a t i o nr u l e si nd e t a i l b ya n a l y z i n gt h ed e v e l o p e d r u l e s ，i tf o u n dt h ev a l u a b l er e f e r e n c ei n f o r m a t i o nf o rt a x a t i o ns y s t e m e n h a n c et a xl a we x e c u t i o n a tt h es a m et i m e ，i t s u p p l i e d au s e f u l r e f e r e n c em e t h o df o ra p p l y i n ga s s o c i a t i o nr u l e sm i n i n gt e c h n o l o g yt o o t h e rf i e ld s k e y w o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e s ；s a v ma l g o r i t h m ；t a x a t i o nl a w e n f o r c e m e n t v 图2 图4 图4 图5 插图清单 g e o m i n er 的体系结构9 s a v m 算法和a p r i o r i 算法运行时间对比3 3 s a v m 算法和f p g r o w t h 算法运行时间对比3 3 税收执法管理信息系统架构图3 5 1 x 表格清单 表4 1 事务数据库d 28 表4 2 项的比特向量表示形式2 8 表5 1 税收执法过错行为3 6 表5 2 税收执法人员年龄分段3 6 表5 3 税收执法人员学历分段3 6 表5 4 税收执法人员能级3 6 表5 5 税收执法人员所属单位3 6 表5 6 税收执法人员所属部门3 6 表5 7 税收执法过错行为3 7 表5 82 0 0 5 年度税收执法过错行为数据3 7 表5 92 0 0 6 年度税收执法过错行为数据3 7 表5 1 02 0 0 5 年度数据生成的频繁项集3 8 表5 112 0 0 6 年度数据生成的频繁项集3 8 表5 1 22 0 0 5 年度数据生成的关联规则3 8 表5 132 0 0 6 年度数据生成的关联规则3 8 x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得金肥王些太堂或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签字 知魄：蝴铀脚日 学位论文版权使用授权书 本学位论文作者完全了解合肥工业大学 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权合肥工业大学 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名，支始彩 导师签名： 签字日期：2 0 0 7 年1 2 月0 3 日签字日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： i i 电话：研c ，；矿孑 邮编7 铺矽 | 致谢 当提交这篇学位论文时，我仍觉得意犹未尽。这是一次难忘的求学经历， 几年来，我在认真做好单位工作的同时，抓住一切可以利用的时间，学习理论 知识，提升技术水平。今天，在诸位良师益友的帮助指导下，我终于顺利地完 成了学位论文。 衷心地感谢我的导师胡学钢教授。胡教授是我不悔的选择! 您渊博的科学 知识、敏锐的洞察能力、严谨的治学态度、诲人不倦的工作作风都让我敬佩不 已。您对我的关心和鼓励让我终身难忘。所有这一切，我将终身受益。在此， 我谨以最诚挚的心情向我的导师胡学钢教授表示最衷心的感谢。 在此，我还要特别感谢我深爱的妻子和儿子，我取得的每一点成绩都离不 开你们的支持，是你们给我创造了一个安心学习的环境，谢谢你们。我把这篇 论文作为最好的礼物送给你们。 衷心感谢评阅、评审、出席论文答辩会的各位专家给予的悉心指导! 作者： 域乞 2 0 0 7 年1 2 月0 3 日 第一章绪论 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，已 经从单台机器发展到网络环境。近年来，由于数据采集技术的更新，企业和政 府利用计算机管理事务的能力增强，产生了大规模的数据。数以百万计的数据 库系统在运行，而且每天都在增加。随着数据库中存储的数据量急剧增大，大 量的数据背后隐藏着许多重要的信息，人们希望能够提供更高层次的数据分析 功能，自动和智能地将待处理的数据转化为有用的信息和知识，以便更好地利 用这些数据。但目前数据库系统只能对指定的数据进行简单的数字处理，而不 能对这些数据所包含的内在信息进行提取，导致了“数据爆炸但知识贫乏”的现 象。 面对这一挑战，数据挖掘和知识发现技术应运而生，并显示出强大的生命 力。数据挖掘和知识发现使数据处理技术进入了一个更高级的阶段。它不仅能 对过去的数据进行查询，而且能够找出过去数据之间的潜在联系，进行更高层 次的分析，以便更好地做出理想的决策，预测未来的发展趋势等。通过数据挖 掘，有价值的知识、规则或高层次的信息就能从数据库的相关数据集合中抽取 出来，从而使大型数据库作为一个丰富、可靠的资源为知识的提取服务。特别 是近几年，数据挖掘和知识发现得到了蓬勃发展，并越来越显示出其强大的生 命力和广阔的发展前景。 i i 课题背景 税收是国家财政收入的主要来源，是国家进行宏观经济调控、实施收入再 分配的重要手段。随着社会主义市场经济的快速发展和对外开放的扩大，税收 在国民经济中的作用和地位日益增强。多年的税收实践表明，坚持依法治税是 做好税收工作的一项重要原则，是税收的灵魂和基础，对于营造公平、公正、 公开的税收环境，促进社会主义市场经济快速、稳定、健康发展具有重要意义。 如何做到依法治税，关键是要规范税收执法行为，强化对税务干部税收执法权、 行政管理权实施过程的监控与管理。 随着数据挖掘理论的不断发展和应用技术的逐渐成熟，数据挖掘技术引起 了各行业越来越多的重视。如何将数据挖掘技术应用到税务系统，加强税收数 据的分析利用已经成为摆在广大税务工作者面前的一个重要课题。特别是应用 关联规则挖掘技术，对税收执法行为数据进行深度分析，揭示各种税收执法过 错行为与执法者之间的内在联系，找出执法过错行为的规律，辅助税务机关有 针对性地采取管理措施，进一步加强税收执法管理，对于促进依法治税，构建 和谐的税收征纳关系具有十分重要的意义。 1 2 税收执法管理 税收执法是税务工作者依据法定权限、程序执行各项税收法律、法规和政 策，组织税收收入的过程。税收执法管理是指税务机关加强税收执法监督，规 范税收执法行为，不断提高依法治税、依法征管水平的过程。 为全面加强税收执法管理，从2 0 0 5 年起，国家税务总局开始在全国税务系 统全面推行税收执法责任制，制定了税收执法责任制评议考核办法( 试行) 、 全国国税系统税收执法责任制岗位职责和工作规程范本( 试行) 、全国 地税系统税收执法责任制岗位职责和工作规程范本( 试行) 、税收执法过 错责任追究办法等相关文件，进一步细化管理流程，落实管理责任，强化对 税收执法权的监督制约。 在试点基础上，国家税务总局整合开发了一套适用全国的、能够实现对执 法行为自动监控和考核的“税收执法管理信息系统”。这套系统以税收执法责 任制岗位职责和工作规程为依据，包括执法考核子系统和执法监察子系统。执 法考核子系统能够实时、自动提取征管信息系统中存储的执法活动记录，通过 预先设定的5 6 个考核指标和1 0 6 项过错行为，对执法数据进行分析比对，自动生 成考核结果。该系统全面推广应用，取得了显著的效果，主要表现在三个方面： 1 、系统能够自动完成税收执法行为数据监控、抽取、分析、考核工作，完成了 人工考核情况下无法完成的工作量，大大提高了执法责任制评议考核的广度；2 、 该系统对工作流程进行考核，能分析判断出现过错的具体岗位，提高了执法责 任制评议考核的准确性；3 、该系统通过执法行为进行比较分析，将有可能出现 过错的行为及时向相关执法人员进行预警提示，减少了因为执法人员的疏忽而 产生的执法过错，提高了执法监督的时效性。 从功能设计上看，该系统通过对税务人员日常执法行为的监控，提取有价 值的税收执法信息，根据有关法律、法规和制度规定，判断有无执法过错行为， 并对过错责任人实施批评教育、经济惩戒和行政责任追究，以此来警醒、督促 税收执法人员规范执法行为，提高执法水平。 但是这种管理方式也存在明显的不足，它是一种“亡羊补牢”式的被动管 理，效率相对较低。能否找到一种变“被动管理”为“主动管理”的方法了? 答案是肯定。即应用数据挖掘技术，对历史和现有的税收执法行为数据进行分 析，揭示执法过错行为和执法者之间的内在联系，分析执法过错行为产生的原 因，找出过错行为发生规律，帮助税务机关“对症下药”，有针对性地采取管 理措施，加强执法管理，尽可能地预防和减少执法过错行为的发生。 1 3 数据挖掘技术在税务系统的应用 1 3 1 国外税务系统数据挖掘应用现状 2 在欧美等发达国家，数据挖掘技术已经被广泛引入到税收管理领域，并取 得了较好的应用效果。上世纪9 0 年代末，美国就将数据挖掘技术引入到税收征 管系统中，对纳税人纳税数据进行分析，评估税收申报的真实性，减少了偷漏 税现象的发生。澳大利亚己在全国税务机关内部全面运用计算机系统管理纳税 申报，有效地利用数据仓库和数据挖掘技术对税源进行控制，有针对性的开展 税务审计和税收预测【lj 。 1 3 2 国内税务系统数据挖掘应用现状 在国内，数据仓库和数据挖掘技术在税务领域的应用才刚刚起步【2 j ，成功 的应用案例现对较少。2 0 0 1 年1 月，国家税务总局制定了数据仓库框架整体设 计，对数据仓库系统建设的系统定位、业务需求、数据格式、实施平台和建 设步骤等技术问题进行了明确。作为总局开展数据仓库应用的试点单位，广东 省国税、北京市国税采用o r a c l e 、e s s b a s e 、b i 等技术工具，初步建成了税收 分析与辅助决策系统，开创了应用数据仓库和数据挖掘技术开展税收数据分析 利用的先河。其后，浙江、广东、辽宁、南京、武汉等省、市地税局也先后进 行了数据仓库建设项目。从技术角度看，所有这些应用都主要着眼于数据仓库 的建立和o l a p 分析，只有少数系统提供了数据挖掘工具：从应用领域看，所 有这些应用系统都侧重于税收收入分析、纳税评估两个方面，对税务干部的税 收执法行为分析较少；从应用效果看，大部分应用由于事先对用户需求的了解 不够全面、深入，视图中缺乏所应包含的维度，从不同的视图得到的结果可能 并不相同，容易产生错误引导，因此用户需要做大量的工作才能得出正确的结 果，而且仍有可能遗漏数据之间重要的模式和联系，因此很难发现数据中隐含 的深层次的信息。可以说，目前还没有比较成功的采用o l a m 技术进行税务数 据分析的应用。 1 4 本文研究内容及结构 本论文全面介绍了数据挖掘的基础知识、研究动态以及在国内外税务领域 的应用情况，说明了数据挖掘既具有多层次的研究价值，又具有很高的应用价 值。详细阐述了关联规则挖掘的概念、技术和知识分类，对关联规则挖掘的经 典算法进行了深入研究，指出了各种算法的优缺点，提出了一种基于h a s h 和项 集空间划分的关联规则挖掘算法一s a v m 算法。对税务部门税收执法管理现状 进行了分析，将关联规则挖掘技术应用到税收执法数据分析中，找出执法过错 行为与执法者特征属性之间的内在联系，为税务机关加强税收执法管理提供了 有价值的决策信息。论文具体结构如下： 第一章，介绍了课题的研究背景和意义，数据挖掘技术在税务领域的应用 现状，论文的主要研究内容和组织结构。 第二章，阐述了对数据挖掘理论知识的认识，介绍了数据挖掘技术的定义、 过程、主要技术、常用工具和发展趋势。 第三章，深入研究了关联规则挖掘技术，阐述了关联规则挖掘的概念、基 本理论、分类和研究趋势，介绍了几种经典的关联规则挖掘算法，分析了各种 算法的优、缺点。 第四章，提出一种基于h a s h 和项集空间划分的关联规则挖掘算法一s a v m 算法，阐述了算法的思想，给出了算法的实现步骤和伪码，分析了算法性能， 并通过实验，验证算法的正确性和执行效率。 第五章，将关联规则挖掘技术应用到税收执法管理领域，介绍了数据选择、 预处理、规则挖掘的过程和方法，得到了对加强税收执法管理有价值的结论。 第六章，总结全文。对全文的主要工作进行了概述，并对下一步研究工作 做了展望。 4 第二章数据挖掘技术 本章概述了数据挖掘的定义、过程、常用技术和知识分类，介绍了常用的 数据挖掘工具，分析了数据挖掘研究的发展趋势。 2 1 数据挖掘的定义和过程 数据挖掘( d a t am i n i n g ，d m ) ，又称数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ，k d d ) ，是近年来伴随着人工智能和数据库技术的发展 而出现的一门新兴技术。采用d m 技术可以从大量的数据中提取出隐含的、以 前不为人所知的、可信而有效的知识，能够对数据进行再分析，以期获得更加 深入的了解，并具有预测功能，即可通过已有的历史数据预测未来【3 1 1 4 1 。 d m 利用分类、关联性、序列分析、群集分析、机器学习以及其他统计方 法，从数量庞大的数据中找出隐藏的、未知的、但却对企业经营十分有用的信 息【5 儿“。在数据挖掘的应用中，通过对各种高等统计工具的使用从数据库或其 他计算机储藏中识别出对商业有用的样本或与商业有关的程序，收集与顾客相 关的数据，利用统计分析与人工智能等算法对大量数据进行筛选、推演与模型 建造等，以揭露隐含在数据与模式中的、可把原始数据转换成商机并成为决策 支持依据的新知识【7 1 1 8 。 数据挖掘又是一门交叉学科，它把人们对数据的应用从低层次的简单查询 提升到从数据中挖掘知识，提供决策支持。什么是知识? 从广义上理解，数据 和信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等 看作知识。人们把数据看作是形成知识的源泉。原始数据可以是结构化的，如 关系数据库中的数据：也可以是半结构化的，如文本、图形和图像数据：甚至是 分布于网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学 的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理、查询 优化、决策支持和过程控制等，也可以用于数据自身的维护。数据挖掘是面向 事实的，它力图在挖掘数据中发现事实，并以测试数据作为检验和修正理论的 依据，最后再把知识应用于数据中，其关键性思路可以理解为实事求是。“实 事”即“数据”，“求”就是去发现、去发掘、去探索，“是”就是在数据中 隐藏的规律，即知识。数据挖掘己经真正成为了解、探索与征服数字数据新世 界的核心技术之一。 数据挖掘主要步骤如下： ( 1 ) 数据收集 大量全面丰富的数据是数据挖掘的前提条件，没有这些海量数据，数据挖 掘也就无从谈起。因此，数据收集是数据挖掘的第一步。数据可以来自于现有 事务处理系统的现场收集，也可以从数据仓库的历史数据中得到p 】。 ( 2 ) 数据的预处理 数据预处理包括数据的清理、数据集成、数据选择和数据变换，数据的预 处理是数据挖掘的重要环节。因为从数据收集阶段得到的数据可能有噪音，表 现在数据可能存在自身的不一致性，或者有缺失数据的存在等，因此进行数据 的预处理是必须的b o l 。 ( 3 ) 数据挖掘 根据不同的需求，利用相应的数据挖掘算法对数据进行分析处理。 ( 4 ) 数据挖掘结果的评估 数据挖掘的结果有些是有实际意义的，而有些是没有实际意义的，或是与 实际情况相违背的，这就需要对挖掘结果进行评估。评估可以根据用户的经验， 也可以某种兴趣度度量来验证模型的正确性，进而调整挖掘模型，不断重复进 行数据挖掘，以便最后达到预期的结果。 ( 5 ) 分析决策 数据挖掘的最终目的是辅助决策。决策者可以根据数据挖掘的结果，结合 实际情况，调整竞争策略等。 2 2 数据挖掘技术 下面介绍数据挖掘和知识发现的几种常用技术。 ( 1 ) 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 关联规则数据挖掘是数据挖掘中最活跃的研究方法之一。最早是由a g r a w a l 等人提出的( 1 9 9 3 ) 。最初提出的动机是针对购物篮分析问题提出的，其目的是 为了发现交易数据库中不同商品之间的联系规则。典型的关联规则的例子就是 “9 0 的顾客在购买面包和黄油的同时也会购买牛奶”。 从关联规则被提出以后，诸多的研究人员对关联规则的挖掘问题进行了大 量的研究，他们的工作涉及关联规则的挖掘理论的探索，原有的算法的改进和 新算法的设计，并行关联规则挖掘( p a r a l l e la s s o c i a t i o nr u l em i n i n g ) 以及数量关 联规则挖掘( q u a n t i t i v ea s s o c i a t i o nr u l em i n i n g ) 等问题。 ( 2 ) 分类规则挖掘( c l a s s i f i c a t i o nr u l em i n i n g ) 数据分类指分析数据库中的一组对象，找出其共同属性。然后根据分类模 型，把它们划分为不同的类别。 分类可以看作是从数据库到一组预先定义的、非交叠的类别的映射。数据 挖掘中的分类主要任务是构造分类器，需要有一个训练样本数据集作为输入。 分类的目的是分析输入数据，为每一个类找到一种准确地描述或模型。分类器 的构造方法有统计方法、机器学习方法、神经网络方法等。 统计方法：包括贝叶斯法和非参数法等。常见的临近学习或基于事例的学习 6 ( i n s t a n c e b a s e dl e a r n i n g ，i b l ) 属于非参数方法。对应的知识表示则为判别函数 和原型事例( 原型事例即有代表性的典型的记录，它的表示是原始记录形式) 。 机器学习方法：包括决策树法和规则归纳法。前者对应的表示为决策树或判 别树，后者则有决策表( d e c i s i o nl i s t ) 和产生式规则等。 神经网络方法主要是b p 算法，它的模型表示是前向反馈神经网络模型( 由 代表神经元的结点和代表联接权值的边组成的一种体系结构) ，b p 算法本质上 是一种非线性判别函数。 另外，许多技术，如粗糙集等，都可以用于分类器构造中。 ( 3 ) 聚类分析( c l u s t e r i n ga n a l y s i s ) 聚类就是将数据对象分组成为多个类或簇，划分的原则是在同一个簇中的 对象之间具有较高的相似度，而不同簇中的对象差别较大。其目的是使同一类 别中的对象间的距离尽可能小，而不同类别中的对象间的距离尽可能大。对 于一个很大的多维数据集，在数据空间中数据点通常不会均匀分布。数据聚类 方法可以找出稀疏和稠密的位置，进而发现数据集的整个分布模式。当要分析 的数据缺乏描述信息，或者是无法组织成任何分类模式时，利用聚类方法可以 找到类。与分类不同的是，聚类操作中要划分的类是事先未知的，类的形成完 全是数据驱动的，属于一种无指导的学习方法，所以也称为“无指导分类”。聚 类方法包括统计方法，机器学习方法和神经网络方法。 统计中的聚类分析是基于几何距离的聚类，它是一种基于全局比较的聚类， 要求所有的数据必须预先给定，而不能动态增加新的数据对象。对于每一次聚 类决策，它对于所有数据或已存在的聚类都同等对待而忽略其距离远近。并且 它需要考察所有的对象才能决定类的划分，因此计算复杂度较高。 在机器学习中，聚类分析通常称为“无监督学习”。因为和分类学习相比， 分类学习的样本或数据对象有类别标识，而聚类学习的样本则没有，需要聚类 学习算法自动确定。在机器学习中，聚类分析也称为“概念聚类”。因为其中的 距离衡量不再是基于几何距离，而是基于一组对象的概念描述。执行概念聚类 时，需要先定义对象间相似性的量度，然后根据它确定类。确定的类为一组对 象的集合，类内相似性很高而类问相似性很低。 在神经网络中，有一类无监督自学习方法，即自组织神经网络方法，如 k o h o n e n 自组织特征映射方法和竞争学习网络等。在数据挖掘领域中，有报道 的神经网络聚类方法主要是自组织特征映射方法，i b m 在其发布的数据挖掘白 皮书中特别提到了这种方法，并用其进行数据库聚类的分割。 f 4 1 数据泛化和归纳( g e n e r a l i z a t i o na n di n d u c t i o n ) 数据泛化是把数据库中有关数据从一个较低的概念层次抽象到一个较高层 次的过程。数据库中的数据都是最基本和最原始的数据，其中包含了最基础的 信息。有时人们需要从较高层次来处理和分析数据，以发现有用和有意义的信 7 息。因此需要在不同层次上泛化和归纳数据以满足查询要求，目前比较有效和 灵活的数据泛化方法主要有数据立方体方法( d a t ac u b ea p p r o a c h ) 和面向属性 的归纳方法( a t t r i b u t e o r i e n t e di n d u c t i o na p p r o a c h ) 。 数据立方体方法也称为“多维数据库分析”或“联机分析处理”( o n l i n e a n a l y t i c a lp r o c e s s i n g ，o l a p ) ，是一种数据仓库的方法。 面向属性的归纳方法，这种方法的思路是把数据挖掘查询表达为一类似于 s q l 的数据查询语言，从数据库中收集相关数据集。然后在此数据集的基础上 应用一系列的泛化技术，如属性裁剪，概念树爬山与属性闭值控制等进行数据 泛化。泛化关系从较高层次上总结了原始关系，有了泛化关系，即可做更深一 步的操作或转换，把泛化数据转换为不同类型的知识或格式。 ( 5 ) 时间序列和序列模式挖掘( s e q u e n c ep a t t e r nm i n i n g ) 时间序列数据挖掘就是要从大量的时闻序列数据中提取人们事先不知道 的、但又是潜在有用的、与时间属性相关的信息和知识，并用于短期、中期或 长期预测，指导人们的社会、经济、军事和生活等行为。 从数学意义上来讲，如果我们对某一过程中的某一变量进行x ( t ) 观察测量， 在一系列时刻t l ，t 2 ，t n ( t 为自变量，且t l m i n s u p ( 给定的最小支持度) 。 文献e 2 0 也给出关联规则中项目集与数学中的格、不动点以及概念格之间 的联系：挖掘所有频繁项目集就相当于在项目集格上挖掘具有支持度约束的 所有结点的集合。闭项目集就是关联关系中一个伽罗瓦闭算子的不动点，挖 掘所有频繁闭项目集就相当于在闭项目集格上挖掘具有支持度约束的所有结点 的集合。关联关系中一个概念的内涵就是一个闭项目集。而且关联关系的概 念格上的每一个概念的内涵的支持度都是由其外延所确定，关联关系的概念格 不仅保留了闭项目集的信息，也同时保留了闭项目集的支持度的信息。这样， 挖掘所有的频繁闭项目集就相当于在这个概念格上挖掘所有外延满足约束的概 念。 由这些结果，可知关联规则虽然是来源于实际应用，但它有着深厚的理论 背景，这为它今后的发展提供了有力的理论依据。另外，也为今后能把图论、 格、不动点或者概念格等数学中的一些理论成果应用到关联规则中起到了一个 桥梁作用。 3 3 关联规则的分类 关联规则有很多种，根据不同的标准，可以有不同的分类方法： ( 1 ) 根据规则中所处理的值的类型，可以分为布尔型关联规则和数值型关联 规则。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之 间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数 值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理， 当然数值型关联规则中也可以包含种类变量。 例如：性别= “女”= 职业= “秘书”，是布尔型关联规则；性别= “女”= a v g ( 收入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 ( 2 ) 根据规则中涉及的数据维，可以分为单维关联规则和多维关联规则。在 单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品：而在多 维的关联规则中，要处理的数据将会涉及多个维。换句话说，单维关联规则是 处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。 例如：b u y ( x ，c o m p u t e r ) = b u y ( x ，s o f t w a r e ) 只是单维关联规则；a g e ( x ，3 0 ) = b u y ( x ，c o m p u t e r ) 足多维关联规则。 ( 3 ) 根据规则中涉及的抽象层，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不 同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则；台 式机= s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 4 经典关联规则挖掘算法 目前，常用的关联规则挖掘算法有以下几种： 3 4 1a p r i o r i 算法 一、算法概述 1 9 9 3 年，r a g r a w a l 等人提出了a p r i o r i 算法【l0 1 ，它是一种最有影响、最经 典的挖掘单维、单层、布尔关联规则的算法。该算法采用逐层搜索的迭代方法， 通过重复扫描数据库来发现所有的频繁项集。该算法基于两阶段求频繁项集的 思想，将关联规则挖掘算法分解为两个子问题： 1 求出数据库d 中满足最小支持度m i n s u p 的所有频繁项目集。 2 利用频繁项目集生成所有关联规则。 其中子问题2 的解决方法较为简单，对每个频繁项目集x ，对x 的每个非空 子集a ，考察规则。a = ( x a ) ，如果该规则满足最小支持度和最小信任度则输 出此规则。子问题1 的求解是关联规则发现的关键部分。 为了描述a p r i o r i 算法，先引入两个a p r i o r i 性质： 1 如果项目集x 是频繁项目集，则x 的任一非空子集也必定是频繁项目集。 2 如果项目集x 不是频繁项目集，则x 的任何超集也必定不是频繁项目集。 二、算法思想 根据a p r i o r i 性质，得出a p r i o r i 算法的主要步骤： ( 1 ) 产生所有的频繁1 项集的集合l 1 。扫描数据库d ，对每个事务的数据项进 行处理。若该数据项第1 次出现，则将其加入候选1 一项集的集合c l 中，并将它的 计数值设为1 ；若该数据项已在c 1 中，则将它的计数值加上1 。数据库事务扫描完 1 6 毕，得到所有的候选1 项集。将c l 中所有计数值小于m i n s u p 的项集删除，就得到 了频繁1 项集的集合l i 。 ( 2 ) 通过l k 1 与自己连接产生候选k - 项集的集合c k 。对于任意的l i l k 1 和l j l k i ( i j ) ，若( 1 i 1 = l j 1 ) a ( 1 i 2 5 b 【2 】) a a ( 1 i k 一2 】5l j k 一2 】) a ( 1 i k - 1 l j k - 1 ) ，产生一个新的结果项集l i 1 l i 2 l i k 2 】l i k l l l j k 一1 】，并将 该项集加入到候选k 项集的集合c k 中。 ( 3 ) 对c k 进行剪枝。从c k 中删除所有( k 1 ) 子集不全包含在l k - t 中的项集。 ( 4 ) 扫描数据库事务d ，对于其中的每一个事务，若它包含c k 中的候选项集 c ，则将c 的计数值加1 ( 初始值为o ) 。扫描