（计算机软件与理论专业论文）olam技术在税务领域的应用研究.pdf

山东大学硕士学位论文 摘要 随着数据库技术在税务系统应用的不断深入，潍坊市国家税务局积累 了大量的税务管理信息。如何能够实现对这些信息的深层次分析利用，是 潍坊市国税局近年来一直关注的问题。o l a m ( o l a pm i n i n g ) ，联机分析挖掘， 是一种将o l a p 技术和数据挖掘技术结合起来，集中了数据仓库、o l a p 和数 据挖掘技术优势的技术，它使得挖掘能够在用户的指挥下，在数据库或数 据仓库的不同部分，在不同抽象层次上进行。这种技术对解决税务机关的 数据分析利用问题提供了很好的解决途径，本文就此作了初步的研究。 关联规则分析是联机分析挖掘研究的一个重要内容，其耳的是找出给 定的数据集中的项之间有意义的联系。关联规则挖掘最经典的算法是 a p r i o r i ，它适合于在事物数据库中挖掘单维、布尔型关联规则。如何实现 多层多维关联规则的挖掘是近年来研究比较多的一个问题，本文总结了一 个在关系数据库中挖掘多维关联规则的基本算法m u l t i d i m e r u l e ，并提出了 一个基于o l a m 技术和元规则约束的多维关联规则挖掘算法t a x r u l e 。算法 t a x r u l e 引入了用户交互的概念，通过o l a p 操作和元规则，让用户参与关 联规则的分析挖掘过程。同时，利用元规则的约束，只分析用户感兴趣的 规则，使算法的针对性加强，效率得到了提高。 联机分析挖掘的应用是一个复杂的系统工程，实旌这样一个工程需要 花费很多的时间、人力、物力和财力。本文提出了一个基于o l a m 技术的税 收分析与决策支持平台的基本框架，用于指导税务系统联机分析挖掘项目 的开发。这个框架包括税收业务源数据层、分析数据存储层、联机分析挖 掘层和用户交互层四个层次。税收业务源数据层是指各单位现有的数据资 源，通过数据的e t l 操作后，将所需数据放入数据仓库，即分析数据存储 层，完成分析数据存储层的建立。利用o l a m 技术对分析数据存储层的数据 进行分析挖掘，最后在用户交互层展现分析挖掘的结果。 关键词：联机分析挖掘、关联规则、算法、税务管理信息 一些查奎兰堕主堂篁笙壅 一 as t u d yo fo l a p m in in gt e c h n o l o g ie s a p p l ic a t e d in t a x t a tlo nm a n a g e m e n t a b s tr a c t w i t ht h ea p p l i c a t i o no fd a t a b a s et e c h n o l o g i e s ，a ne n o r m o u sa m o u n t o fd a t aa b o u t t a x a t i o nm a n a g e m e n t iss t o r e da tw e i f a n gn a t i o n a l t a x t a t i o nb u r e a u m o r ea n dm o r e t a x e o l l e c t o r sp a yt h e i rr e s p e c tt o a n a l y s et h i sc o l le c t e dd a t aa n dm i n i n gi n t e r e s t i n gk n o w l e d g e f r o m i t o l a m ( o l a pm i n i n g ) i s am e c h a n i s mw h i c hi n t e g r a t e s 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 w i t hd a t am i n i n gs ot h a tt h eq u a l i t y a n d e f f i c ie n c yo fm i n i n gc a nb ei m p r o v e d i nt h i s p a p e r ，w ed i s c u s sh o w o l a pm i n i n gs h o u l db ea p p l ic a r e d i nt a x a t i o nm a n a g e m e n t a s s o c i a t i o nr u l e sm i n i n gis o n eo ft h ei m p o r t a n t f u n c t i o n so f d a t am i n i n g ，w h ic hd i s c o r e r sas e to fi n t e r e s t i n ga s s o c i a t i o nf r o m r e l e v a n ts e t ( s ) o fd a t ai nad a t a b a s e a 1 9 0 r i t h ma p r i o r ii st h em o s t f a m o u sm e t h e df o rm i n i n gs i n g l e - d i m e n s i o n a la n db o o l e na s s o c i a t i o n r u l e sf r o mt r a n s a c t i o nd a t a b a s e s t h ep r o h l e m ish o wt om i n e m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sf r o mr e l a t i o n a ld a t a b a s e s i n t h is p a p e r ，a na l g o r i t h m b a s e do i lo l a m t e c h n o l o g y a n dm e t a r l l le c o n s t r a i n to fm u l t i d i m e n s i o n a la s s o c i a t i o nr u l e s ，t a x r u l e ，i s i n t r o d u e e d i t se f f i c i e n t m e n ti sr e a l i z e db yt h e i n s t r u c t f r o m u s e rs u c ha sa t t r ib u t i o n1 i s t ，m e t a r u l ea n ds oo n t h ew o r k so fa p p l i c a t i n go l a pm i n i n gt e c h n 0 1 0 9 yi ss 0c o m p l e x t h a tag r e a td e a lo fti m e ，m o n e ya n dm a n p o w e rw i1lb es p e n d e d ，t h e n ，a p l a t f o r mo ft a x a t i o na n a l y s i sa n dm i n i n gi si n t r o d u c e di nt h i s p a p e r t od i r e c tt h ep r o c e s so fo l a pm i n i n gw o r k s 0 nt h is p l a t f o r m ，t h e r e a r ef o u rl e v e l s ：( 1 ) t a xs o u r c ed a t a ，( 2 ) d a t as t o r e ，( 3 ) o l a me n g i n ea n d ( 4 ) u s e r s in t e r f a c e t h e a n a l y s e n e e d e dd a t aisl o a d e di n t o d a t a 山东大学硕士学位论文 w a r e h o u s ef r o mt a xs o u r c ed a t a b y e t l o r p e r a t i o n sa c e o r d i n g r u l e s w i t ht h e h e i p o fo l a m e n g i n e ，u s e r s c e i n a n a l y s ea n d m i n e e a s i l y a tl a s t ，t h er e s u l to fo l a pm i n i n gw i l lb es h o w nt ou s e r sb v s e m et 0 0 1s k e y w o r d s ：o l a pm i n i n ga s s o c i a t i o nr u l e s a l g o r i t h mt a x a t i o n m a n a g e m e n td a t a 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究所取得的成果。除文中已经注明引用的内容 外，本论文不包含任何其他个人或集体已经发表或撰写过的科 研成果。对本文的研究作出重要贡献的个人和集体，均已在文 中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：鼍潞k 一 日期：趋咝且鱼l 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定， 同意学校保留或向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅：本人授权山东大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 止 p 论文作者签名：套照垒一导师签名：氇a 魈期：垫丝垒盐 山东大学硕士学位论文 第一章绪论 1 1 课题的来源和选题的意义 潍坊市国税系统从八十年代中期开始探索计算机技术的应用，经历了 用p c 机填开税票、在局域网上建立小型税务管理信息系统、到今天的基于 大型关系数据库和广域网的税务管理信息系统。经过近二十年的不断探索， 特别是从2 0 0 1 年开通了金税工程、启用了中国税收征管信息管理系统 ( c t a i s c h i n at a x a t i o na d m i n is t r a t i o ni n f o r m a t i o ns y s t e m ) 以来， 潍坊市国家税务局积累了大量的原始数据，其中包括增值税专用发票、纳 税人档案、申报征收数据、专用税票、税收会计统计报表、重点税源监控 数据和各类税收调查数据等。这些数据已经成为税务管理和税务决策的宝 贵资源，但由于( 1 ) 这些数据是基于多种平台( 如d o s 、u n i x 、w i n d o w s 等) ，具有不同结构( 如o r a c l e 、s y b a s e 、s q l s e r v e r 等) 的；( 2 ) 由于业 务的变化、o l t p 系统的升级和更新换代，使得数据具有多种存储形式，表 达方式不统一；( 3 ) 由于数据分散，管理者和决策者很难以一个统一的视 图来获得整个国税局的全局信息：( 4 ) 数据缺损和不完整使得从不同角度 和口径得到的统计结果可能出现不一致。所有这些问题，导致税务数据的 利用率较低：一方面，在业务系统中保存了大量的数据，另方面，税务 人员经常为无法获得用于决策支持的依据而苦恼。如何充分地利用这些数 据资源，从中及时发现有用的知识，提高信息的利用率，已经成为税务系 统计算机应用的一个新课题。o l a m 技术的不断发展和成熟，为解决这一问 题提供了有效的手段和方法。 国家税务总局从2 0 0 1 年开始探讨税务数据的综合利用问题，于2 0 0 2 年1 月制定出台了数据仓库框架整体设计，规范了系统定位、业务需求、 数据格式、实旖平台和建设步骤等技术问题。广东省国税和北京市国税作 为国家税务总局的试点单位，采用o r a c l e 数据库+ e s s b a s e 在线分析服务器 + b i o f f i c e 展示工具的组合解决方案，经过1 年半的建设，初步建成了税 收分析与辅助决策系统；浙江省地税、南京市地税、武汉市地税等单位也 先后进行了数据仓库项目的建设。所有这些应用都着眼于数据仓库的建立 坐奎查堂堡主堂! 堇堡茎 和o l a f 分析，只有少数系统提供数据挖掘工具集。o l a p 分析虽然可给周户 提供在不同角度、不同抽象级别的视图，但是由于事先对用户需求的了解 可能不十分全面深入，视图中缺乏所应包含的维度，从不同的视图得到的 结果可能并不相同，容易产生错误引导，因此用户需要做大量的工作才能 得出正确的结果，但是仍有可能遗漏数据之间重要的模式和联系，因此很 难发现数据中隐含的深层次的信息；而数据挖掘能够发现隐藏在数据间的 有用的信息，但使用产品化的工具集，用户一般不能很好地掌握每种算法 的思想以及适合的分析类型，应用效果不是很好。目前还没有比较成功的 采用0 l a m 技术进行税务数据分析的应用。 本文对o l a m 技术在税务系统的应用进行了有益的探索，特别是税务数 据关联规则挖掘”“”，提出了一个基于o l a m 技术和约束的多维关联规则挖 掘算法t a x r u le ，并设计了一个基于o l a m 技术的税收分析与决策支持平台， 对其中部分功能的具体实现进行了探讨。 1 2o l a m 技术的发展与研究现状 o l a p ( 联机分析处理) 与d m ( 数据挖掘) 都是数据库( 数据仓库) 的分析工 具，在实际应用中各有侧重。前者是验证型的，它建立在多维视图的基础上， 是针对特定空间问题的数据进行联机访问和分析利用信息多种可能的观 察形式进行快捷、稳定、致和交互性的存取，允许管理决策入员对数掘 进行深入观察，强调执行效率和对用户命令的及时响应，而且它的直接数据 源般是数据仓库：后者是挖掘型的，建立在各种数据源的基础上，重在发 现隐藏在数据深层次的对人们有用的模式( p a t t e r n s ) ，般并不过多地考 虐执行效率和响应速度。 利用o l a p 技术，用户能够积极参与分析过程，动态地提出分析要求， 选择分析算法，对数据进行由浅及深的分析。数据挖掘技术可以实现数据 的深层次分析和分柝过程的自动化，其中，分析过程的自动化是指其分析 过程不需要用户的参与，这是它的优点，也正是它的不足心3 。因为在实际 工作中，用户也希望参与到挖掘过程中来，例如只想对数据的某子集进 行挖掘、对不同抽取水平、不同集成水平的数据进行挖掘、根据自己的需 山东大学硕士学位论文 要动态选择挖掘算法等等。o l a p 与数据挖掘各有所长，如果能将二者结合 起来，发展一种建立在o l a p 和数据仓库基础上的新的挖掘技术，将更能适 应实际工作的需要。联机分析挖掘，o l a m - - - - o n l i n ea n a l y t i c a lm i n i n g ， 正是二者相结合的产物，又称为o l a pm i n i n g 。加拿大的j i aw e i h a n 首先提 出了这一概念，他指出“联机分析挖掘是一种集成了o l a p 操作和数据挖掘 的机制，它使得挖掘能够在用户的指挥下，在数据库或数据仓库的不同部 分，在不同抽象层次上进行。” 发展o l a m 技术有以下几个有利条件“1 ： ( 1 ) 数据仓库为o l a m 准备了高质量的数据 数据挖掘工具的操作对象是一些经过清理、变换、集成等预处理的数 据，通常这种处理过程是十分昂贵的，而d w ( d a t aw a r e h o u s e ，数据仓库) 作 为o l a p 的数据源，存储的正是这样高质量的、有价值的数据，它能为o l a p 提供数据，当然也可以为数据挖掘提供数据。 ( 2 ) 成熟的分析工具为o l a m 提供了技术基础 目前，人们围绕数据仓库和o l a p 技术做了大量的研究，已经形成了许 多实用的工具，包括存取、集成、合并数据、多个异种数据库的转换、 o d b c o l e o b 连接、w e b 访问和服务工具以及报表和o l a p 分析工具等。最 大限度地借鉴和利用这些现成的工具，可以使o l a m 的研究从一个较高的起 点出发，使o l a m 应用能够尽快取得效果。 ( 3 ) 探测性数据分析 成功的数据挖掘需要对数据进行探侧性( e x p o r a t o r y ) 分析。比如，挖掘 所需的数据可能只是一部分、一定范围的数据。因此，对多维数据模型的切 片、切块、下钻等操作，同样可以应用于d m 的过程中。也就是说，可以将d m 建立在多维模型( 或说超立方体) 的基础之上。 ( 4 ) 用户参与 用户的参与对数据挖掘同样重要。用户动态地提出挖掘要求、选择挖 掘算法可以大大提高挖掘结果的实用性，因此可以将o l a p 的c l i e n t s e r v e r 结构应用于数据挖掘中来。 山东大学硕士学位论文 o l a m 技术的核心是基于超立方体的挖掘算法。超立方体计算( 切片、 切块、下钻、旋转等操作) 与传统挖掘算法( 关联、分类、聚类等基于关 系型或事务型的挖掘算法) 的结合使得数据挖掘有了极大的灵活性和交互 性。根据立方体计算和数据挖掘所进行的次序的不同可以有以下几种模式： ( 1 ) 先进行立方体计算、后进行数据挖掘。在进行数据挖掘以前，先 对多维数据进行一定的立方体计算， 级别。 ( 2 ) 先对多维数据作数据挖掘， 结果做进一步的深入分析。 以选择合适的数据范围和恰当的抽象 然后再利用立方体计算对挖掘出来的 ( 3 ) 立方体计算与数据挖掘同时进行。在挖掘的过程中，可以根据需 要对数据视图做相应的多维操作，这也意味着同一个挖掘算法可以应用于 多维数据视图的不同部分。 ( 4 ) 回溯。挖掘过程是对多维数据视图的一个不断深入计算和访问的 过程，在实际中，用户很有可能因为算法的复杂性而在超立方体中“迷失 方向”。因此挖掘算法应该能够提供给用户类似退回上次操作的初始状态一 样的回溯功能。 目前，对o l a m 技术的研究总体上处于理论探讨、应用实验阶段，对算 法研究的较多，实际应用较少。在税务系统的应用，更多地偏重于o l a p ， 极少涉及挖掘，仅有的几个数据挖掘案例也不十分成功。 o l a m 是学术界研究的一大热点，国内属于起步阶段，复旦大学的朱扬 勇、黄超提出了一个“基于多维模型的交互式数据挖掘框架，交互式 数据挖掘环境不仅能够让用户可以从多个角度观察数据和模式，而且能够 让用户从多个角度来观察数据任务的执行情况，对o l a m 技术进行了扩充和 规范。 1 3 论文研究内容及组织 在后面的章节中，我们将研究o l a m 技术及其在税务领域的应用。 在第二章，我们分析了关联规则挖掘问题，在仔细研究了由事务数据 库挖掘单维、布尔型关联规则的经典算法a p r i o r i 后，总结了一个在关系 山东大学硕士学位论文 数据库中挖掘多维关联的基本算法m u l t i d i m e r u l e ，在它的基础上又设计了 一个基于o l a m 技术和元规则约束的挖掘多维关联规则的算法t a x r u l e 。在 第三章中，我们结合税务领域信息化管理的特点，设计了一个基于o l a m 技 术的税收分析与决策支持平台，对其中部分功能的具体实现进行了探讨。 最后，在第四章对全文进行了总结，并提出了下一步的工作。 坐堡奎堂堕圭堂垡笙奎 一_ _ 一 第二章多层和多维关联规则挖掘 2 1引言 关联规则发现是r a g r a w a l 等人 4 3 吲首先提出的。关联规则是形式如 下的一种规则：“在购买面包和黄油的顾客中，有9 0 的人同时也买了牛奶” ( 面包+ 黄油专牛奶) 。用于关联规则挖掘的主要对象是事务型数据库 ( t r a n s a c t i o n a ld a t a b a s e s ) ，一个事务一般由如下几个部分组成：事务 标识符，事务中包含的项目集( i t e m s ) 。 由于数据库技术的广泛应用，商场及超市在其数据库中存储了大量的 销售数据。如果对这些历史数据进行分析，则可以对顾客的购买行为提供 极有价值的信息。例如，可以对货架上的商品进行规划摆放( 如把顾客经 常同时买的商品放在一起) 、可以帮助如何规划市场( 怎样相互搭配进货) 。 由此可见，从事务数据中发现关联规则，对于改进零售业等商业活动的决 策非常重要。 纳税评估，是指税务机关根据纳税人的申报信息及日常掌握的各种税 收征管资料和信息，运用一定的技术手段和方法，对纳税人定时期的纳 税情况进行综合分析、审核、评价、判定，以便于及时发现存在的问题， 提高税收征管质量的一项管理工作。其中纳税人税收负担分析( 简称税负 分析) 是纳税评估的一项主要内容，税负分祈是比较分析某些税种( 如增 值税) 、不同行业、不同地区、不同登记注册类型和不同经营方式的税收负 担水平和税负变化趋势。这类分析，不仅要就本地区的经济发展进行不同 时期的纵向比较，而且要与周边地区乃至全国平均水平进行同一时期的横 向比较，以正确判断本地区税源管理工作的水准，找出差距，明确进一步 努力的方向和途径。 以往的纳税负担分析基本上局限于统计分析，般是分行业、分经济 类型统计计算平均税负，找出高于或低于平均税负的纳税人等。 关联规则分析可用于挖掘纳税人税收负担数据，可以帮助管理人员从 大量的信息中找出某些感兴趣的、“隐含的”的规律。这是因为每一条数据 中包含许多属性信息，如纳税人所属行业、所属区域、注册类型、经营方 山东大学硕士学位论文 式、税负程度等。我们可将每一个纳税人的税负数据情况看作是一个事务， 将行业、区域等属性信总看作是物品。这样我们就可以用关联规则挖掘技 术对税负数据进行挖掘，从而发现税负的属性信息同时出现的一些情况， 如： i f( h 0 1 ) a n d ( d 0 2 ) t h e nf 5 w i t hc o n f ( 0 8 ) ，s u p p ( 0 3 ) 这条规则的含义是如果某纳税人属于潍坊市奎文区管辖，并且是商业 企业，那么他的税收负担是5 级。这一规则的信任度为0 8 ，支持度为0 3 。 也就是说属于潍坊市奎文区管辖的商业纳税人，有8 0 的纳税人其税负负担 属于5 级，属于潍坊市奎文区管辖的商业纳税入税负属于5 级的在所有纳 税人中的比例为3 0 。 根据这条规则，管理者可以通过适当调整某些个体纳税人的定额，也 可以通过重点监测不符合这条规则的纳税人的销售和纳税情况，以指导纳 税人合理地进行税负规划。 2 2 关联规则的形式描述”1 设，= f ，i ：，f 。) 是项目集合，设任务相关的数据d 是数据库事务的集 合，其中每一个事务是项的集合，可表示为 t i d ，t ，其中t = ( f ，i ：，f 。) ， f ，i ( j = 1 , 2 ，k ) ，它表示该事务中涉及的项目集，t i d 为事务标识符，它唯 一标识一个事务。 定义2 2 1 ：如果项目集x t ，我们说事务 t i d ，t 包含项目集x 。 定义2 2 2 ：关联规则是形如x jy 的逻辑蕴含式，其中zc ，y 。 定义2 2 3 ：如果事务数据库中有s 的事务包含x ，那么称项目集x 的 支持度为s ，即s u p p o r t ( x ) = s ： 定义2 2 4 ：如果事务数据库中有s 的事务同时包含x 和y ，那么我们 说关联规则z j y 的支持度为s ，即s u p p o r t ( x ；y ) = s ： 定义2 2 5 ：如果事务数据库中包含x 的事务中有c 的事务也包含y ， 那么我们说关联规则x j y 的信任度为c ，即c o n f i d e n c e ( y ) ：c 。 如果不考虑关联规则的支持度和信任度，那么在事务数据库中存在无 些查查堂堡主兰垡笙奎 穷多的关联规则。事实上，人们一股只x c 满f ：- 定的支持度和信任度的关 联规则感兴趣。因此，为了发现有意义的关联规则，需要给定两个阈值： 最小支持度( m i n i m u ms u p p o r t ) 和最小信任度( m i n i m u mc o n f i d e n c e ) 。 前者规定关联规则必须满足的最小支持度，简称为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 的规则称作强规则。 定义2 2 6 ：项的集合称为项集，包含k 个项的项集称为k 一项集。 定义2 2 7 ：项集的出现频率是包含项集的事务的个数，简称为项集的 频率。如果项集的出现频率大予或等于最小支持度m i n s u p 与d 中事务总数 的乘积，称项集满足最小支持度m i n s u p 。如果项集满足最小支持度，则称 它为频繁项集，频繁k 一项集的集合，通常记作l k 2 3 关联规则的分类 关联规则有很多种，根据不同的标准，可以有不同的分类方法： 1 、根据规则中所处理的值的类型，可以分为布尔关联规则和数值关联 规则。如果规则考虑的是项的存在与否，则它是布尔关联规则，如果规则 考虑的是量化的项之问的关聪，则它是数值关联规则。 2 、根据规则中涉及的数据维，可以分为单维关联规则和多维关联规则。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品； 而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话， 单维关联规则是处理单个属性中的一些关系：多维关联规则是处理各个属 性之间的某些关系。例如： b u y ( x ，c o m p u t e r ) 2 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 打印机，是一个细节数据上的单层关联规 则：台式机2 s o n y 打印机，是一个较高层次和细节层次之间的多层关联规 山东大学硕士学位论文 则。 2 4 关联规则挖掘的核心算法a p r i o r i ”，“1 5 - 1 6 1 a g r a w a l 等人于1 9 9 3 年“1 首先提出了挖掘顾客交易数据库中项集间的 关联规则问题，其核心方法是基于频繁项集理论的递推方法。以后诸多的 研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原 有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规 则的效率；提出各种变体，如泛化的关联规则、周期关联规则等，对关联 规则的应用进行推广。 a g r a w a l 等“1 在1 9 9 4 年设计了一个基本算法a p r i o r i ，一个最有影响、 最经典的挖掘单维、单层、布尔关联规则的算法。这个算法基于两阶段频 繁项集的思想，将关联规则挖掘算法的设计分解为以下两个子问题： 1 、求出d 中满足最小支持度m i n s u p 的所有频繁项目集： 2 、利用频繁项目集生成所有关联规则。 其中子问题2 的解决方法较为简单，对每个频繁项目集j ，对的每个 非空子集a ，考察规则。j q - n ) ，如果该规则满足最小支持度和最小信任度 则输出此规则。 予问题1 的求解是关联规则发现的关键部分。 为了描述这一问题，我们引入以下引理； 引理2 4 1 ：如果项目集x 是频繁项目集，则x 的任一子集必定也是频 繁项目集；反过来说，如果x 的任一子集不是频繁项目集，则x 肯定不是 频繁项目集。 由该引理，我们就得到求频繁项目集的方法： ( 1 ) 先生成长度为1 的频繁项目集，记为“1 。 ( 2 ) 在l k 的基础上生成候选项目集( c a n d i d a t ei t e m s e t ) c k + 1 要求候选项目集的所有的子集均为频繁项目集。 ( 3 ) 扫描事务数据库d ，计算每个候选项目集的支持度，如果大于 m i n s u p ，则加入到l k + 1 中( l k + 1 初始为空集) 。 ( 4 ) 如果l k + i 为空集，则结束，所求结果即为z 1 j y 三 2 1 y ：否贸 些奎查堂堡主堂垡丝苎 转2 ，继续。 a l g o t i t h m ：a p r i o r i i n p u t ：( 1 ) 格式为( t i d ，i t e m s e t ) 的事务数据库d ，其中t i d 为事务标 识符，i t e m s e t 为该事务所对应项目集： ( 2 ) 用户最低支持m i n s u p ； o u t p u t ：所有的频繁项目集： b e g i n 1 ) l l = f i n d f r e q u e n t j i t e m s e t s ( d ) ； 2 ) f o r ( k = 2 ：l 中：k + + ) 3 ) c k = a p r o i r i g e n ( lk 1 ，m i n s u p ) ： 4 ) f o re a c ht r a n s a c t i o nt d s c a ndf o rc o u n t s 5 ) c t = s u b s e t ( c k ，t ) ：g e t t h es u b s e t so ftt h a ta r e c a n d i d a t e s 6 ) f o re a c hc a n d id a t ec c 。 7 ) c c o u n t + + ： 8 ) ) 9 ) l k = c ck ic c o u n t m i n s u p 10 ) 11 )r e t u r n l = u k l k e n d 其中，a p r i o r i g e n 是以频繁( k 一1 ) 一项目序列集l 。为自变量的候选生 成函数。该函数返回所有频繁k 一项目集的超集，分链接和修剪两步执行： ( 1 )链接( j o i n ) 1 ) f o re a c hi t e m s e t1 1 lk - l 2 ) f o re a c hi t e n l s e t12 l 3 ) i f ( 1 ， 1 = l 。 1 ) 八( 1 。 2 ：l ： 2 ) 八( 1 ， k 一2 = l ： k 一2 ) 八 ( 1 ， k 一1 m i n s u p ，那么将c 放入l l 。 将l l 中所有的谓词变量放入a l 。 s t e p 袅对于k = 2 ，a k = a k lma k l ，对于a k 中的每个元素a ，如果 k - d 数据方体已经存在，则将k d 数据方体中所有的格放入c k ；如果k d 数据方体不存在则计算它：生成方体的所有的格( k 个谓词q i 所有可能的 维一值对) 。搜索关系数据库，分别对每个格在关系数据库中的出现计数， 存储在方体的单元中，将k d 数据方体中所有的格放入c k 。 s t e p3 ：对于c k 中的每个元素c ，如果它的任何一个子集不是频繁的， 那么删除e 。 s t e p 套，对于c k 中的每个元素c ，如果它的单元中的计数 m i n s u p ， 那么将c 放入l k 。 s t e p5 7 重复s t e p2 s t e p4 ，直至l k 为空集。 s t e p 函由频繁谓词集合产生强关联规则。 2 5 4 算法m u l t i d i m e r u l e 的形式化描述 算法：m u l t i d i m e r u l e 找出频繁谓词集 输入：关系数据表d ，最小支持度阈值m i n s u p 山东大学硕士学位论文 集合 输出：d 中的频繁谓词集l 方法： ( 1 ) i f 卜d 方体e x i s tt h e nc z = l d 数据方体中所有的格的集合 e l s e 计算卜d 数据方体，cz = l d 数据方体中所有的格的集合 f o re a c hr d f f o re a c hc c i f i fr q i = 0 i j t h e nq i j c o u n t + + ) q i j c o u n t m i n s u p pt h e nq i j l l a t = q i iq i j l 1 ) ( 2 ) f o r ( k = 2 ：l k - z 中：k + + ) a k = a k l qa k l f o re a c ha a k i f k - d 数据方体存在 t h e n c k = k d 数据方体中所有的格的集合 e l s e 计算k d 数据方体，c k = k d 数据方体中所有的格的 f o re a c hr d f o re a c hc c k i f c 的任何一个子集不是频繁的t h e nd e l e t ec i fr q i 2 q i j a n dr q k = q k 1 a n d r q 。= q 。i n t h e n c c o u n t + + ： ) * c 是形如q 。 j q t 1 q 。 n 共p 个谓词的 维一值对，其中i ，k ，m = ( 1 ，2 ，p ) 女 i f c c o u n t m i n s u p pt h e nc l k ( 3 ) r e t u r nl = u k l k 坐查奎堂堡主堂焦丝苎 下面，用一个简单的例子来说明算法的执行过程。假设用户给定的关 系数据库如表2 2 所示 纳税人识别号行业 区域税负 3 7 0 7 0 0 01药品零售业潍坊市潍城区二级 3 7 0 7 0 0 0 2超级市场零售业潍坊市奎文区三级 3 7 0 7 0 0 0 3超级市场零售业潍坊市潍城区一级 3 7 0 7 0 0 0 4药品零售业潍坊市潍城区二级 3 7 0 7 0 0 0 5超级市场零售业潍坊市奎文区一级 3 7 0 7 0 0 0 6超级市场零售业潍坊市潍城区二级 3 7 0 7 0 0 0 7药品零售业 潍坊市奎文区二级 3 7 0 7 0 0 0 8超级市场零售业潍坊市奎文区一级 3 7 0 7 0 0 0 9药品零售业潍坊市奎文区三级 3 7 0 7 0 0 1 0超级市场零售业潍坊市潍城区二级 鬏2 2 纳税人税负数据 上表中共有l o 条记录，以纳税人识别号加以标识。共有四个维：纳税 人识别号、行业、区域和税负。假定m i n s u p = 4 ，算法执行过程如下： 1 、算法执行完第一步后，得到频繁卜谓词集： l 。= 行业( 药品零售业) ，行业( 超级市场零售业) ， 区域( 潍坊市潍城区) ，区域( 潍坊市奎文区) ， 税负( 一级) ，税负( 二级) 、税负( 三级) ) a 1 = i 行业，区域，税负) 2 、a 22 a 1 n a a 1 = 行业八区域，行业八税负，区域八税负 c 2 2 行业( 药品零售业) 八区域( 潍坊市潍城区) ， 行业( 药品零售业) ，区域( 潍坊市奎文区) ， 行业( 超级市场零售业) 八区域( 潍坊市潍城区) 。 行业( 超级市场零售业) 八区域( 潍坊市奎文区) ， 行业( 药品零售业) a 税负( 一级) ， 生查查堂堡主堂垡笙塞 行业( 药品零售业) 八税负( 二级) ， 行业( 药品零售业) a 税负( 三级) ， 行业( 超级市场零售业) 八税负( 一级) ， 行业( 超级市场零售业) 八税负( 二级) ， 行业( 超级市场零售业) 八税负( 三级) ， 区域( 潍坊市潍城区) 八税负( 一级) ， 区域( 潍坊市潍城区) 八税负( 二级) ， 区域( 潍坊市潍城区) 八税负( 三级) ， 区域( 潍坊市奎文区) 八税负( 一级) 区域( 潍坊市奎文区) 八税负( 二级) ， 区域( 潍坊市奎文区) a 税负( 三级) l 2 = 区域( 潍坊市潍城区) 八税负( 二级) ，4 0 ) 3 、l3 = 中 4 、l = l ，ul 2 算法m u l t i d i m e r u le 的基础是数据立方体的计算，对于一个有n 维， 每个维上有m 层概念层的多维主题数据，通过聚集运算可以产生n + m 1 8 个 子立方体，这个空间对于维度来说是指数级的( e x p o n e n t i a l ) ，如果一个关 系数据库的维数较多，算法m u l t i d i m e r u l e 将会引起“组合爆炸”。算法 m u l t i d i m e r u l e 可以找出所有的频繁p 一谓词，由此可以推导出强关联规则， 这些维间关联规则反映的是关系数据表中不同的属性值组合同时出现的支 持度和可信度。在很多情况下，有些属性的组合是没有意义的，因此，很 有必要引入约束机制，以减少属性组合的可能，提高算法效率。在下面的 章节中，我们又提出了一个适合税务数据的基于约束的关联规则挖掘算法。 2 6 基于0 l a m 技术和约束的多维关联规则挖掘 o l a m 是0 l a p 操作与数据挖掘的集成，它可以根据用户的要求，在数据 集的不同部分、不同抽象层次上进行数据挖掘。运用0 l a m 技术进行关联规 则挖掘的核心是基于数据立方体的关联规则挖掘算法。如何将传统的0 l a p 山东大学硕士学位论文 操作与关联规则挖掘结合起来昵? 我们知道，根据结合方式的不同， o l a m 技术可以分为四种模式：一是先对多维数据进行o l a p 操作，利用o l a p 操 作选择合适的数据范围和抽象级别，再在o l a p 操作的结果集上进行数据挖 掘；二是先对多维数据进行数据挖掘，再利用o l a p 操作对挖掘结果作进一 步的深入分析；三是在挖掘过程中对多维数据进行o l a p 操作：四是在数据 挖掘和o l a p 操作同时进行的过程中提供回溯功能，允许用户返回上次操作 开始时的初始状态。关联规则挖掘比较适合第一种方式。 2 6 1o l a p 操作 o l a p 操作使用多维数据立方体作为数据模型，为用户提供了多视角、 多层次观察和分析数据的手段，用户可以利用o l a p 操作进行选择用于挖掘 的数据集或对挖掘结果进一步分析等工作，以提高数据挖掘的效率和交互 性。 2 6 1 1 多维数据模型一一m u l t i d i m e n s i o n a ld a t ac u b e 一主题数据：销售额，维：产品，地域，时间 维：产品，地域，时问 时间维 t i me 的层次 产母维地拱 年 大头国k 季美 具体每品城书知亩 分占 图2 1 多维数据立方体示意 多维数据模型将数据看作数据立方体形式，能够满足用户多视角、多 粒度层次的观察和分析的要求，即能够提供m u l t i d i m e n s i o n a lv i e w s 和 m u l t i p leg r a n u l a rv ie w s 。数据立方体( m u l t i d i m e n s i o n a ld a t ac u b e ) 是o l a p 主题数据的组织模型，是“面向主题，支持决策，支持多层次、多 山东大学硕士学位论文 _ _ _ _ _ 一一 粒度分析”的思想得以实现的载体，如图2 1 所示。 一个数据立方体( d a t ac u b e ) 由表示主题数据的“度量”和“维”来 定义，可以形式地描述为： d e f i n ec u b e 数据立方体名一s t a r 维名l ，维名2 ，维名n ： 主题数据度量值1 = 聚集运算符l ( 度量值字段名) ， 主题数据度量值2 = 聚集运算符2 ( 度量值字段名) ， 主题数据度量值m = 聚集运算符m ( 度量值字段名) 按照这种形式化的定义，则图2 1 所示的销售主题数据立方用描述性 的语言则可以表示为： d e f i n ec u b es a l e s s t a r t i m e ，p r o d u c t ，l o c a t i o n ： d o l l a r s s o l d = s u m ( s a l e s i n d o l l a r s ) ， u n i t s o l d = c o u n t ( 术) 1 、维：维是人们观察问题的特定角度。例如：时间维、产品维、地理 维。 2 、维层次：人们在观察数据的某个特定角度( 即某个维) 还可以存在细 节程度不同的多个描述方面，我们称这多个描述方面为维的层次。例如： 时间维可以有日期、月份、季度、年四个不同的层次。 3 、维成员：维的一个取值成为该维的一个维成员。如果维已经分成了 多层次的，则维成员就是不同维层次取值的组合。例如：某公司销售数据 在省、市、县，地理维有三个层次，则“山东省”，“山东省潍坊