（计算机应用技术专业论文）面向增量更新的数据挖掘算法及其应用研究.pdf

浙江工业大学硕士学位论文 面向增量更新的数据挖掘算法及其应用研究 摘要 由于传统的数据挖掘算法都面向静态数据，而数据库中的数据却 日益更新，造成数据挖掘的结果不及时，从而影响了正确判断和决策， 因此研究面向增量更新的数据挖掘算法具有重大的意义。本文主要研 究关联规则和聚类的增量更新挖掘算法。 提出了新的关联规则增量更新p f u p 算法，该算法借鉴强频繁项 集概念，利用强频繁项集连接生成小数量的候选项集，采用了预剪枝 策略减少了对数据库的扫描次数。仿真实验表明，在相同的数据库和 支持度的情况下，p f u p 算法的执行时间比f u p 算法减少了5 0 左右。 然后，在p f u p 算法上，引入了事务压缩优化措旌，实验仿真证明该 算法具有更好的优越性。 重点研究基于密度的增量聚类挖掘算法，介绍d b s c a n 算法的基 本概念和算法思想以及目前两种基于密度的增量聚类算法。由于增量 聚类算法只是考虑数据库增加和删除的情况，提出了当m i n p t s 发生变 化的增量聚类算法u d b s c a n ，并通过实验仿真得到理论的正确性。 最后，在医疗保险系统中应用并实现了一个o l a m 应用模型。该 模型使用浙江省某市医疗保险数据库中2 0 0 5 年的医保数据，建立了面 向医疗保险费用和诊断项目为主题的数据仓库，从多维的角度来分析 数据，并通过关联增量算法挖掘出及时的且具有价值的信息。 关键词：关联规则，聚类，增量更新，联机分析挖掘 浙江工业大学硕士学位论文 t h er e s e a r c ha n d a p p l i c a t i o n so f d a t am i n i n g a l g o r i t h m so r i e n t e di n c r e m e n t a lu p d a t i n g a b s t r a c t d u et ot h ep r o b l e mt h a tt h et r a d i t i o n a ld a t am i n i n ga l g o r i t h m so r i e n t t os t a t i cd a t aa n dt h ed a t ai nt h ed a t a b a s eu p d a t e sd a yb yd a y , i ft h er e s u l t o fd a t am i n i n gc o u l dn o tu p d a t e do nt i m e ，i tw i l li n f l u e n c et h es t r a t e g yo r r i g h tj u d g e m e n t s oi th a sp r o d i g i o u ss i g n i f i c a n c et or e s e a r c h0 1 1t h ed a t a m i n i n ga l g o r i t h m sf o rt h ei n c r e m e n t a lu p d a t i n g t h i sp a p e rm a i n l ya i m s a tt h er e s e a r c ho na s s o c i a t i o nr u l e sa n dc l u s t e r i n ga l g o r i t h m sf o rt h e i n c r e m e n t a lu p d a t i n g an e wi n c r e m e n t a lu p d a t i n ga s s o c i a t i o nr u l e sa l g o r i t h mp f u pi s p r e s e n t e di nt h ep a p e r i tj o i n st h es t r o n gl a r g ei t e m s e t si n t ot h es m a l l q u a n t i t a t i v eo fc a n d i d a t ei t e m s e t so nt h eb a s i so fs t r o n gl a r g ei t o m s e t s c o n c e p t ，a n da d o p t st h ee a r l yp r u n i n gs t r a t e g yt oc u td o w nt h et i m e so f s c a no fd a t a b a s e n es i m u l a t i o l ls h o w st h a tt h ee x e c u t i o nt i m eo fp f u p a l g o r i t h mh a sr e d u c e dt oa b o u t5 0 c o m p a r e dw i t hf u pa l g o r i t h mi nt h e c a s eo ft h es a m ed a t a b a s ea n ds u p p o r t t h e n o nt h eb a s i so ft h ep f u p a l g o r i t h m , t h em e a s u r e o f r e d u c i n g t r a n s a c t i o n si s a d o p t e d t h e 浙江工业大学硕士学位论文 s i m u l a t i o ns h o w st h a tt h en e wa l g o r i t h mh a st h eb e t t e rs u p e r i o r i t y t h i sp a p e rf o c u s e st h er e s e a r c ho i lt h ei n c r e m e n t a lc l u s t e r i n gm i n i n g a l g o r i t h m sb a s e do nd e n s i t y f i r s t l y , i ti n t r o d u c e st h eb a s i cc o n c e p ta n d t h ei d e ao fd b s c a n a l g o r i t h m , a n ds h o w st h er e c e n tt w oa l g o r i t h m so f t h ei n c r e m e n t a l c l u s t e r i n ga l g o r i t h mb a s e do nd e n s i t y b e c a u s e t h e i n c r e m e n t a lc l u s t e r i n ga l g o r i t h mj u s tc o n s i d e r st h es i t u a t i o no f i n c r e a s i n g d a t ao rd e l e t i n gd a t a ，an e wi n c r e m e n t a lc l u s t e r i n ga l g o r i t h mu d b s c a n i sp u tf o r w a r d , i nw h i c ht h em i n p t sc h a n g e s t h en e wa l g o r i t h mp r o v e s t h es u p e r i o r i t yb yt h es i m u l a t i o n f i n a l l y , a no l a ma p p l i c a t i o nm o d e lh a sb e e nd e s i g n e d a n d i m p l e m e n t e di nt h es y s t e mo fm e d i c a li n s u r a n c e t h em o d e le m p l o y st h e m e d i c a ld a t ao f2 0 0 5f r o mm e d i c a li n s u r a n c ed a t ab a s eo fs o m ec i t yi n z h e j i a n gp r o v i n c ea n db u i l d sd a t aw a r e h o u s eo nt h et h e m eo fm e d i c a l i n s u r a n c ea n dd i a g n o s i s i ta n a l y z e st h ed a t af r o mm u l t i d i m e n s i o n a l v i e w p o i n t sa n du s e st h ei n c r e m e n t a la s s o c i a t i o nr u l e sa l g o r i t h m st og a i n t h ev a l u a b l ei n f o r m a t i o n t i m e l y k e yw o r d s ：a s s o c i a t i o nr u l e s ，c l u s t e r i n g ，i n c r e m e n t a lu p d a t i n g ，o n l i n e a n a l y s i sa n dm i n i n g 1 1 1 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体己经发表或撰写过的研究成果，也不含为获得浙江 工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的 法律责任。 作者签名：张良蕉 日期：2 岬年，上月2 占日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ) 作者签名：淡寅、盔 翩签呀 日期：2 垆位月2 j 日 日期柙年2 月 浙江工业大学硕士学位论文 第一章绪论 1 1 研究背景与意义 数据挖掘( d a t am i n i n g ) 是数据处理的一个热点和前沿研究领域，是从大量 的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、 人们事先不知道的、但又是潜在有用的信息和知识的过程。而关联规则是发现数 据库中不同项目之间的联系，是数据挖掘的主要研究方向之一。关联规则被广泛 应用于大型零售组织的决策支持中，对确定市场策略、提高决策支持能力提供了 有力的技术和工具保证。最常见的例子就是“9 0 的客户在购买面包和黄油的同 时也会购买牛奶”在交易数据项目之问开采关联规则问题是a g r a w a l 等人于 1 9 9 3 年提出的，在1 9 9 4 年提出了挖掘关联规则的经典a p r i o r i t l 】算法之后，有很 多学者对其进行研究并提出了一些新的算法。聚类是利用数据对象之间的某种具 体的或抽象的相似性实现有意义的划分过程。聚类分析能够帮助用户在大规模数 据对象集合上构造有意义的划分，将复杂的大系统分解为较小的易于求解的子模 块，从而达到分而治之它是辨识数据模型和关系的第一个步骤，选择好的聚类 算法对后续的研究工作是非常关键的。 由于现有的许多关联规则算法和聚类算法大多针对历史静态数据库，很多专 家针对在前人算法的基础上设计了更为高效的算法。但是现在数据变化日新月 异，原来产生的关联规则或者聚类发生了变化，最传统的方法是重新执行原来的 算法，但是却造成原来存在的一些结果被浪费掉，且运算复杂度会很高，需要占 用大量的时问和空间，导致用户满意度下降，从而限制数据挖掘的应用和发展。 因此更新算法的设计阶段是数据挖掘的核心步骤，更新算法是影响数据挖掘效率 的最重要的因素。研究设计出快速高效的更新算法能有效提高数据挖掘的效率， 扩展数据挖掘的应用范围，对于数据挖掘具有十分重要的意义。 1 2 数据挖掘 1 1 2 1 国内外研究现状 数据挖掘一词首次出现在1 9 8 9 年举行的第十一届国际联合人工智能学术会 议上。到目前为止，由美国人工智能协会主办的k d d 国际研讨会己经召开了8 次， 浙江工业大学硕士学位论文 规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向 系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。世 界上比较有影响的典型数据挖掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司 的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i n e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的 w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e s 、还有c o v e r s t o r y 、e x p l o r a 、 k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i n e r ，q u c s t 等。1 9 9 9 年，亚太地区在北京 召开的第三届p a k d d 会议收至0 1 5 8 篇论文，空前热烈。e e 的k n o w l e d g e a n d d a t a e n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络和信 息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨 论，甚至到了脍炙人口的程度。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年国家 自然科学基金首次支持我们对该领域的研究项日。目前，国内的许多科研单位和 高等院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华大学、 中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系 统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也 在开展对数据立方体代数的研究；华中科技大学、复旦大学、浙江大学、中国科 技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化 和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化 数据的知识发现以及w e b 数据挖掘。 最近，g a l t n e * tg r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未来 三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体 系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。根据最近g a r m e r 的h p c t 2 1 研究表明，“随着数据捕获、传输和存储技术的快速发展，大型系统用 户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系 统来创建新的商业增长点。” 1 2 2 数据挖掘定义 作为一个新兴的研究领域，数据挖掘得到了研究者的广泛关注【3 , 4 1 ，主要从 计算性能【5 l 、数据库嘲、统计学 7 1 、模式识别i s 、知识发现【明等不同角度对数据挖 掘进行了研究。f r a w l e y ，p i a t e s k y - s h a p i r o 与m a t h e u s 对数据挖掘给出了如下定义： 2 浙江工业大学硕士学位论文 数据挖掘是对观测或收集到的数据集( 通常是非常大的) 进行分析，目的是发现未 知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据【1 0 1 。 数据挖掘汇集了统计学、机器学习、人工智能、数据库、模式识别等学科的 内容，是一门新兴的交叉学科。通过数据挖掘推导出的关系称为模型、模式，包 括线性方程、规则、聚类、图、树等。 1 从商业角度来说，数据挖掘是一种新的商业信息处理技术，其主要特点是对 商业数据库中的大量数据进行抽取、转换、分析和其它模型化处理，从中提取辅 助商业决策的关键性信息。所有企业面临的一个共同问题是：企业数据量非常大， 而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利 于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得 名【1 。 1 1 2 3 数据挖掘流程 1 、数据准备 数据挖掘所处理的数据集通常不仅具有海量数据，而且可能存在大量的噪声 数据、冗余数据、稀疏数据或不安全数据等。解决数据的应用质量问题是数据挖 掘的基础；充分利用有用的数据，清除虚假无用的数据是数据挖掘技术的基础。 数据准备包括数据抽取、清理、转换和加载，具体包括数据的清理、集成、选择、 变换、规约，以及数据的质量分析等步骤。 ( 1 ) 数据清理：数据清理是在数据中消除错误和不一致，并解决对象识别问 题的过程。数据清理包括空值处理、噪声数据处理及不一致数据处理等。数据的 不一致性导致数据挖掘结果的可信度降低。数据清理去除噪声或无关数据，并处 理数据中缺失的数据域。 7 ( 2 ) 数据集成：就是将多个数据源中的数据合并存放在一个统一的数据存储 中。数据集成将多数据源中的数据进行合并处理，解决语义模糊性并整合成一致 的数据存储。 ( 3 ) 数据选择：数据选择是在对发现任务各数据本身内容理解的基础上，寻 找依赖于发现目标的表达数据的有用特征，以缩减数据规模，从而在尽可能保持 数据原貌的前提下最大限度地精简数据量。通过数据选择可以使得数据的规律性 和潜在特性更加明显，提高挖掘效率。 浙江工业大学硕士学位论文 ( 4 ) 数据变换；数据变换将数据转换成适合于挖掘的形式。可包括以下内容： 平滑：去掉数据中的噪声。这种技术包括分箱、聚类和回归。 聚集：对数据进行汇总和聚集。例如，可以聚集日销售数据，计算月和年销 售额。 数据概化：使用概念分层，用高层次概念替换低层次“原始”数据。 规范化；将属性数据按比例缩放，使之落入一个小的特定区问，如0 0 到1 0 属性构造：可以构造新的属性并添加到属性集中，以帮助挖掘过程 ( 5 ) 数据归约：数据归约将辨别出需要挖掘的数据集合，缩小处理范围，是 在数据选择基础上对挖掘数据的进一步约简。主要方法如数据立方体聚集、维归 约、数据压缩、数值压缩。 2 、建立模型 数据挖掘中的建模实际上就是利用已知的数据和知识建立一种模型，这种模 型可以有效地描述已知的数据知识，希望该模型能有效地应用到未知的数据或相 似的情况中。也就是说，建模把一些专业经验，一般规律或普遍情况抽象成一种 分析模型。一旦模型建好之后，就可以把它应用到那些情形相似而结果未知的 判断中 3 、模式评估 数据挖掘得到的模式有可能是没有实际意义或没有实用价值的，也有可能不 能准确的反映真实意义，甚至在某些情况下是与事实相反的，因此对于数据挖掘 的结果要进行评估，确定数据挖掘是否存在偏差，挖掘结果是否正确，确定哪些 是有效的、有用的模式，是否满足用户需求。 4 、数据可视化和知识管理 数据可视化将各种分析结果转化为有组织结构表示的视觉信号集合，如空间 几何形状、颜色、亮度等，并以丰富的图形、表格甚至动画等直观、形象地表现 出来，便于使用者观察和分析数据。目前常用的可视化绘制方法有：几何法、彩 色法、多媒体法和光学法。 1 2 4 数据挖掘分类 在通常情况下，数据挖掘技术一般可以分为两大类1 2 】：直接数据挖掘和间 接数据挖掘。 4 浙江工业大学硕士学位论文 直接数据挖掘：目标是利用可用的数据建立一个模型，这个模型对剩余的数 据，对一个特定的变量( 可以理解成数据库中表的属性，即列) 进行描述。 间接数据挖掘：目标中没有选出某一具体的变量，用模型进行描述；而是在 所有的变量中建立起某种关系 另外，数据挖掘技术常用的有六种关系： 分类( c l a s s i f i c a t i o n ) 估值( e s t i m a t i o n ) 预言( p r e d i c t i o n ) 相关性分组或关联规则( a m n i 哆g r o u p i n go ra s s o c i a t i o nr u l e s ) 聚类( c l u s t e r i n g ) ， 描述和可视化( d e s c r i p t i o na n dv i s u a l i z a t i o n ) 其中分类、估值、预言属于直接数据挖掘；后三种属于间接数据挖掘。这两 种分类方法可以相互结合，构成一个完整的分类方法。如图 图1 1 数据挖掘分类图 由于本文重点讨论关联规则算法、聚类算法在增量更新方面的改进及医疗保 险系统中的应用，则下面将着重介绍关联规则算法、聚类算法。 1 2 5 数据挖掘的主要方法 数据挖掘技术发展至今，已经形成几个主流的挖掘方法：关联规则、聚类分 析、分类等。虽然他们的目标都是找出数据之间的关系，但是在具体操作原理上 却各有侧重点，下面介绍几种方法： l 、聚类分析 5 浙江工业大学硬士学位论文 聚类( c l u s t e r i n g ) 是数据挖掘领域最为常见的技术之一，用于发现数据库中未 知的对象类【1 3 1 4 ，l 习。通过聚类形成的每一个组称为一个簇( c l u s t e r i n g ) 类。 聚类是现实世界中普遍存在的现象，其应用也非常广泛。据文献所载，在破 产预测、手写体字符的计算机识别、交通管理与塞车状况预测等方面都有过成功 的应用。另外，在数据库知识发现的数据准备阶段也常采用聚类的方法除去异常 值的影响。 在2 0 世纪7 0 年代，聚类分析己经有了比较深入的研究16 ，1 ”8 1 9 1 。聚类的方法 主要有统计学方法和机器学习的方法： ( 1 ) 在统计学中，聚类一般称为聚类分析( c l u s t e r a n a l y s i s ) ，主要研究基于几 何距离的聚类。在使用上，首先要定义多维空间和距离，计算维重，以距离作为 相似性的判别标准。 ( 2 ) 在机器学习中，聚类称为无监督学( u n s u p c a v i s e x ls t u d y ) ，主要体现在聚 类学习的例子或数据对象没有类别标记，需要由聚类学习算法自动计算。 从数据库知识发现的角度来讲，对聚类问题的研究是要从大量的数据集中智 能地、自动地抽取出有价值的聚类知识，因此聚类分析也称为聚类知识发现。 聚类方法是数据挖掘中的核心技术，虽然己被广泛、深入地研究，但应用在 数据挖掘领域的时间不长，期间产生了许多不同的聚类方法。一般来说，聚类方 法可划分以下几类： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) 在给定的一个包含1 1 个对象的数据集中，划分方法是将数据集划分为k 个子 集，其中每一个子集均代表一个聚类( k c 神。也就是说将数据分成k 组，并且需 要同时满足两个条件：第一是每组至少包括一个对象；第二是每个对象只能属于 一个组。 在给定需要划分的个数k 后，一个划分方法创建一个初始划分，然后利用循 环再定位技术，也就是通过变动不同划分中的对象来改变划分内容。对于划分结 果好与坏的衡量标准是在同一组中的对象的相近或彼此关联程度。 为获得基于划分聚类分析的全局最优结果就需要穷举所有可能的对象划分。 最常用、最知名的算法有k _ m e a n s 2 0 和k - m c d o i d s 2 1 1 。在k - m e a n s 算法中每一个聚 类均用相应聚类中对象的均值来表示；而在k m e d o i d s 算法中每一个聚类均用相 6 浙江工业大学硕士学位论文 应聚类中离聚类中心最近的对象来表示 、( 2 ) 层次方法( h i e r a r c h i c a lm o t h o d ) 该方法是通过分解所给定的数据对象集来创建一个层次。层次方法可以分为 自下而上和自上而下两种。自下而上的层次方法是从每一个对象均作为一个单独 的组开始，逐步的将这些组进行合并，直到合并到层次顶端或满足中止条件为止。 自上而下的层次方法是从所有对象均属于一个组开始，每一的循环将其分解成更 小的组，直到每一个对象构成一个组或满足中止条件为止。 层次方法存在一个明显的缺陷是在进行分解或合并之后无法回溯，使得该方 法无法纠正自身的错误决策。但这一点也有一个可用之处，就是在进行合并或分 解是无需考虑不同选择所造成的组合爆炸问题。 将循环再定位与层次方法相结合使用是很有效的，c u r e 2 2 1 、b i r c h z 3 1 等具 有可扩展性的聚类算法就是采用这种组合方法进行设计的。该组合方法是首先利 用自下而上的层次方法，然后再利用再定位技术对结果进行调整。 ( 3 ) 密度方法( d e s i t y - b a s e dm e t h o d ) 基于密度的聚类方法就是不断的增长所获得的聚类直到达到某个确定的阈 值。阈值的含义是一个聚类中的对象数，或是一个给定半径内必须包含至少的对 象数。这种方法可以发现任何形状的聚类，并消除数据中的异常数据。而其它基 于对象间距离的聚类方法只能发现圆形或球状的聚类。 基于密度的典型的聚类算法有：d b s c a n 2 4 l ，o p t i c s e z 5 】。 ( 4 ) 网格方法( g r i d - b a s c x lm e t h o d ) 网格方法是将对象空间分成有限数目的单元以形成网格结构，所有的聚类操 作是在网格结构上进行的。此种方法主要优点是由于与数据对象无关而只与划分 对象空间的网格数有关，因此处理的时间较快。 s t i n g 2 6 1 方法就是一个典型的基于网格的方法。 ( 5 ) 模型方法( m o d e l - b a s e dm e t h o d ) 基于模型的聚类方法就是为每个聚类假设一个模型，然后再去发现符合相应 模型的数据对象。这种方法经常是基于假设：数据是根据潜在的概率分布生成的。 基于模型的方法主要有两类f 2 7 l ： 一类是统计学方法 7 浙江工业大学硕士学位论文 概念聚类是机器学习中的一种聚类方法，给出一组未标记的对象，产生对象 的一个分类模式。概念聚类除了确定相似对象的分组外，还为每组对象发现了特 征描述，即每组对象代表了一个概念或类。 另一类是神经网络方法 神经网络方法将每个簇描述为一个标本。标本作为聚类的“原型”，不一定 对应一个特定的数据实例或对象。根据某种距离度量，新的对象可以被分配给与 标本最相似的簇，新对象的属性可以根据该簇标本的属性来预测。竞争学习和白 组织特征映射是两个主要的神经网络方法。 就某一种聚类方法而言，往往是多种聚类思想融合的结果，并不能简单地将 其归为上述的某一类算法。特别是近些年，随着对聚类研究的不断深入，新的聚 类算法在不断的涌现。但每一种聚类算法都有其优点和特色，也都存在着一定的 不足。 2 、关联规则 关联规则挖掘就是从大量的数据中，发现能用来描述数据项之间相互联系的 有关知识。由于在商业领域日积月累产生了海量的交易数据，人们越来越对存储 在数据库中数据的彼此之间联系表现出浓厚的兴趣。例如：在银行数据中，购买 基金的客户，是否也会购买理财产品。如果银行能从中知道两者的联系信息，将 有助于银行有目的性的开展营销策略，甚至可以进行联合销售活动。 关联规则有两个度量值，一个是支持度( s u p p o r t ) ，用于衡量被挖掘出的关联 规则的有用性；一个是信任度( c o n f i d e n c e ) ，用于衡量被挖掘出的关联规则的准 确性。如购买基金的客户，同时也对银行的理财产品有兴趣的话，则可用如下的 关联规则来表示； f u n d mf i n a n c ep r o d u c t 【s u p p o r t = 2 0 ，c o n f d e n c e = 8 0 在上述的关联规则中，支持度为2 0 ，表示在所有的交易记录中，有2 0 的 交易记录同时包含了基金和理财产品。可信度为8 0 ，表示有8 0 的客户在购买 基金的同时购买了理财产品。通常由用户和专家确定最小支持度阈值和最小信任 度阈值，如果支持度和信任度满足此条件，就认为该关联规则是有意义的。 关联规则主要分两步进行： 先发现所有的频繁项集，并且这些项集的频度应大于等于最小支持频度；再 8 浙江工业大学硕士学位论文 根据所获得的频繁项集产生强关联规则，并且这些规则应满足最小信任度阈值。 关联规则挖掘主要应用于市场定位、决策分析和商业管理等领域，尤其在市 场购物分析中应用较多。 根据不同的标准，关联规则挖掘可以分为不同的类别，主要有： 1 、据所处理数据的类型可分为布尔型和定量型。布尔型关联规则描述的是 各离散符号属性之间的关联关系：定量型关联规则描述的是数值属性多维关联关 系。 2 、根据规则中数据的维数，可分为单维和多维两种。单维关联描述的是一 个属性内的关系，而多维关联描述的是属性间的相互关系。 3 、根据规则所设计的抽象层次，关联规则可分为单层次和多层次。单层次 关联仅在一个层次挖掘有关的项，而多层次关联则涉及多个抽象层次。 关联规则挖掘最常用并且有效的算法是a p r i o r i 算法其基本思想是利用“一 个频繁项集的子集均是频繁的”这一性质，按层次循环进行挖掘。在第k 循环 仪 2 ) ，它根据频繁k 项集构造体+ 1 ) 项集，然后扫描数据库一遍以发现频度1 ) 项集的全体。 1 3o l a m 技术在医疗保险中的应用 医疗保险是我国社会保障体系的重要组成部分，它是一项政策性强、涉及面 广、工作量大、关系到群众切身利益的工作。现在参保人数越来越多，涉及到的 医、药机构很多，因此要满足参保人员的基本医疗保险需求，又要保持基金的收 支平衡，单靠人工管理是不可能完成的。面对劳动者和参保人员，医疗保险部门 要提供记录一生，管理一生，服务一生的全过程管理与服务，必须有一个庞大的 信息系统做支撑。因此，2 0 0 0 年3 月国家劳动和社会保障部颁布关于印发城镇 职工基本医疗保险管理信息系统建设指导意见的通知，旨在规范各地职工医疗 保险管理信息系统建设，提高医疗保险管理社会化服务水平，推动全国社会医疗 保险管理信息系统一体化建设。按照这个指导意见的要求，医保信息系统建设在 我国各地展开。 近年来，我国致力于与民政、税务、医院等行业联网的“大社保”网络建设， 这直接促成了全国的社保信息化建设高潮。在这个高潮中，医疗保险信息系统建 设得到了长足的发展。但随着医疗保险改革的深入，越来越多的企业和职工加入 9 浙江工业大学硕士学位论文 了医疗保险，参保人数不断增加，医疗业务处理的信息量也急剧增大，也就越来 越迫切的要求管理决策部门做到决策科学化和服务社会化。医保决策者在这样的 业务数据库查询和分析，会长时间运行，耗费大量的资源，影响到业务系统的顺 利运行。这样的医疗保险系统的处理能力显得捉襟见肘，缓慢的处理过程使得医 保系统的使用人员和参保用户极不满意 2 8 1 ，这种建立在业务系统上的决策支持 系统己经不能适应医保行业的发展和决策要求。因此，在医保行业实施决策支持 系统必须摒弃传统的决策支持系统解决方案，采用新体系结构基于数据仓库的 决策支持系统满足其要求。 由于现在医疗系统中存在大量的问题，如发现不合理用药、过度医疗；发现 医疗机构串换药品、大处方等违规行为；发现可能的分解住院行为等。如此行为 直接影响其他参保人员和医院等的利益，因此目前专家正在采取一系列措施来解 决这个问题。因此，将o l a m ( o nl i n e a n a l y t i c a lm i n i n g ：联机分析挖掘技术) 技 术应用到医疗保险系统具有很大的应用背景 由于数据仓库是数据库技术发展到一定阶段的产物，是为支持机构的决策处 理过程而设计的仓储，其目的是为智能化事务决策提供必要的信息管理。o l a p ( o nl i n e a n a l y t i c a lp r o c e s s ：联机分析处理) 是一种多维分析工具，依靠用户提出 问题或假设，通过下钻、旋转、切片等操作，把信息从多个层次、多个角度展现 给用户，得出对假设的肯定或否定但是由于事先对用户需求的了解可能不全面， 没有包含应有的维度，容易产生错误引导以致遗漏数据之间重要的模式和联系， 因此很难发现数据中隐含的深层次的信息。o l a m 却克服了上述缺点，兼有o l a p 多维分析的在线性、灵活性和数据挖掘对数据处理的深入性，是o l a p 和数据挖 掘的结合。 本文首先将o l a m 技术应用到医疗保险系统中，建立了合理的医疗保险数据 仓库，在此基础上进行o l a p 分析和关联规则挖掘，得到医疗保险系统中一些内 在的信息等。 1 4 本文的内容组织 论文内容组织具体如下： 第一章首先介绍了课题研究的背景和意义；然后阐述了数据挖掘的定义、国 内外研究现状、数据挖掘流程、数据挖掘分类以及主要的数据挖掘算法；最后介 1 0 浙江工业大学硕士学位论文 绍医疗保险系统的研究现状以及o l a m 技术的应用必要性。 第二章首先描述了a p r i o r i 算法；接着介绍了一些关联规则优化算法：然后 描述了目前主要的关联规则增量更新算法；最后详细的阐述f l i p 算法的原理和 具体算法。 第三章在前一章的基础上首先提出了一种新的改进算j 去- - - p f u p 算法，阐述 该算法思想并通过仿真实验验证该算法的正确性。接着借鉴了关联规则的优化技 术，提出了o p f u p 算法，同样阐述算法思想和实验仿真得到该理论的正确性。 第四章首先对增量聚类算法进行简单的综述；然后详细叙述了d b s c a n 算法 的原理；并介绍目前两种基于密度的增量聚类算法：单个更新的增量d b s c a n 算法和批量增量聚类。由于现在的增量聚类算法都是针对数据增加或删除的情 况，因此提出了m i n p t s 发生变化时的增量聚类算法，描述算法的原理并通过实验 仿真来验证理论的正确性。 第五章在医疗保险系统中设计并实现了一个o l a m 应用模型。该模型使用 浙江省某市医疗保险数据库中2 0 0 5 年的医保数据，建立了面向医疗保险费用和 诊断项目为主题的数据仓库，从多维的角度来分析数据仓库的数据，并且运用了 关联增量算法挖掘出及时的且具有价值的信息。 第六章首先总结本文，然后对数据挖掘增量更新算法和基于o l a m 的医疗保 险系统的发展提出了展望。 浙江工业大学硕士学位论文 第二章关联规则中增量式更新算法 增量式更新算法能充分利用已挖掘出的知识来提高挖掘效率，是数据挖掘高 效算法研究中一个主要方向。根据实际应用需求，关联规则的更新问题可以分为 以下几种情况：( 1 ) 事务数据库不变，最小支持度发生变化时，关联规则的高效 更新问题；( 2 ) 最小支持度不变，一个事务数据集d l 添加到事务数据库d 中去时， 如何生成最新事务数据库( d u d l ) 中的关联规则的问题；( 3 ) 最小支持度不变，从 事务数据库d 中删除一个事务数据集d 2 ( d 2 d ) 后，如何高效地生成事务数据库 p d 2 ) 中的关联规则的问题。这三种情况是关联规则更新问题的基础和核心。 本文在第( 2 ) 种情况下，提出了两种改进的关联规则增量更新算法，但是这两 种算法是在f u p 算法的基础上提出的。f u p 算法是基于a p r i o r i 算法的框架。因 此本文介绍了a p r i o r i 和f u p 算法的原理及一些改进措施。 2 1 经典的a p r i o r i 算法 ， 1 9 9 4 ，a g r a w a l 等在先前工作的基础上，完善了一个称为a p r i o r i 的关联规 则挖掘算法。这个算法一直作为经典的关联规则挖掘算法被引用。它是最为典型 的一种层次算法，其核心技术被其他各类布尔关联规则挖掘算法所广泛采用。 2 1 1 算法描述 a p r i o r i 算法是通过项目集元素数据不断增长来逐步完成频繁项目集发现的。 首先产生1 频繁项目集l l ，然后产生2 一频繁项目集k ，直到不能再扩展频繁项 目集的元素数目而算法停止。在第k 次循环中，先产生1 【- 候选项目集的集合c k ， 然后通过扫描数据库生成支持度并测试产生k 频繁项目集h 。 下面是具体的算法： 算法l 用于寻找所有的频繁项目集。该算法在第一次迭代时，直接构成候选 1 项目集c t 。算法在第k 次迭代时，先根据上一次迭代过程中找到的频繁项目集 l ，产生本次迭代的项目集q 。然后依次扫描数据库d 中的事务，确定包含在 每条事务中且属于c k 的项目集。当所有事务都扫描完成之后，即可得到瓯中各 项目集的支持度。再根据d 和给定的最小支持度确定c k 中的频繁项目集。重复 上述过程直到没有新的频繁项目集产生为止。具体算法如下： 1 2 浙江工业大学硕士学位论文 算法l 使用根据候选生成的逐层迭代找出频繁项目集 输入：事务数据库d 和最小支持度阈值( r a i n _ s u p ) 输出：d 中的频繁项目集l 方法： ( 1 ) l r - f m d _ _ f r e q u e n t _ 1 i t e m s e t s ( d ) ； ( 2 ) f o r ( k = 2 ；i _ t 习玉+ + ) ( 3 )c 产a p d o t g e n ( h 1 ) ；c k 是k 个元素的候选集 ( 4 )f o r e a c h t r a n s a c t i o n t d ； 扫描d 找出所有事务的计数 ( 5 )c t = s u b s e t ( c k ，t ) ；c k 是所有t 包含的候选集元素 ( 6 ) f o re a c hc a n d i d a t ec c i 一 ( 7 ) c c o u n t + + ； ( 8 ) ( 9 ) h = c a c k f c c o u n t ；蛩n i n _ s u p ) ( 1 0 ) ) ( t dr e t u r n = o i 山； 算法l 中调用了a p r i o r i _ g e n ( i _ , 0 是为了通过o ( 1 ) 频繁项目集产生k - 候选项 目集。算法2 描述了a p f i o r i _ g e n 过程。 算法2a p r i o r i _ g e n ( l k 1 是频繁( k 1 ) _ 项目集) ( 1 ) f o re a c hi t e m s e t1 1 h , - i ( 2 ) f o re a c hi t e m s e t1 2 e 【l ( 3 )i 1 1 【l 】一1 2 【l 】) ( 1 1 【2 】= _ 1 2 【2 】) a ( i x k - 1 1 2 k - 1 ) t h e n ( 4 )c = i t 睁司1 2 ；，连接步：把1 2 的第k - 1 个元素连到1 1 后 ( 5 ) i f h a si n f r c q u e n t _ s u b s c t ( c ，l k o t h e n (6)deletec ；l 剪枝步：删除含有非频繁项目子集的候选元素 ( 7 )e l s e a d d c t o c k ； ( 8 ) ( 9 ) r e t u mc k ； 算法2 中调用了h 勰_ i n f f e q u e n t _ s u b s e t ( c ，l k i ) ，是为了判断c 是否需要加入 到k - 候选集中。按着a g r a w a l 的项目集格空间理论，含有非频繁项目子集的元素 1 3 浙江工业大学硕士学位论文 不可能是频繁项目集，因此应该裁减掉，以提高效率算法3 描述了 l h a si l l 丘u e n ts u b s e t 过程。 算法3h 嬲i n f i c q u c n t , s u b s c l ( c ，l k 1 卜判断候选集的元素 ( 1 ) f o re a c h ( k 一1 ) 一s u b s e tso f c ( 2 ) i f s 叠l k 1t h e n ( 3 ) r e t u r nt u r e ； ( 4 ) r e t u r nf a l s e ； 这里c 是候选k - 项目集，l k 1 是频繁( 1 【- 1 ) - 项目集 该算法中有两个关键步骤：连接步和剪枝步。 1 、连接步：为找出h ( 频繁k - 项目集) ，通过h i 与自身连接( l k - 1 争司l k 1 ) 产 生候选l ( - 项目集，该候选项目集记作c k ( 其中，l k - l 中的元素是可连接的) 。 2 、剪枝步：q 是k 的超集，即它的成员可以是频繁的也可以是不频繁的， 但所有的频繁l ，- 项目集都包含在c k 中扫描数据库，确定c k 中每一个候选项的 计数，从而确定k 然而，瓯可能很大，这样所涉及的计算量就很大。为压缩 c k ，使用a p r i o r i 性质：任何非频繁的( i ，- 1 ) 项目集都不可能是频繁k - 项目集的子 集。因此，如果一个候选l - 项目集的o 卜1 ) - 予集不在【* l 中，则该候选集也不可 能是频繁的，从而可以从c k 中删除。 一旦从数据库d 中的事务中找出频繁集。就可以由它们产生关联规则。 算法如