（计算机软件与理论专业论文）交互式关联规则挖掘技术研究.pdf

摘要 随着数据库和互连网技术的发展，许多组织积累了相当丰富的数据，显然， 这些数据蕴含着很多有用的知识，于是利用这些知识为组织创造更多的财富便 成为火热的话题。但是，靠人的直觉和手工处理是无能为力的，在数据丰富但 知识贫乏的现象面前，数据挖掘技术应运而生。 本文首先详细地说明了数据挖掘技术产生的实际背景，数据挖掘技术的概 念，数据挖掘应用的相关方法，数据挖掘处理的对象以及它丰富的应用领域。 作为数据挖掘研究的重要问题，文章阐明了关联规则挖掘的定义及经典的关联 规则挖掘方法a p r i o r i 算法，分析了a p r i o r i 算法的不足之处，说明了目前为 止人们对该算法的改进。 按照以人为中心进行数据挖掘的理念，我们应该对关联规则进行交互式挖 掘，本文从两个方面对之进行了研究：约束关联规则的快速挖掘和频繁项集的 快速更新。 对于约束关联规则的快速挖掘，本文系统的分析了实际中经常遇到的约束 的种类，对约束进行了分类，为了把约束尽早的用于挖掘过程，实现用户和系 统的交互，提出了约束关联规则挖掘的体系结构及c c c 优化原则。但按照一般 的优化方法进行挖掘未必有最优的性能，对于项在规则的头和体中是否出现一 类的约束，本文提出了一种基于事务数据集修剪的挖掘方法。实验证明，该方 法较一般的优化方法有较好的性能。 在交互挖掘的过程中，用户经常要改变挖掘的条件，寻找感兴趣的规则， 于是频繁项集的更新便是一个非常关键的问题，解决此问题的最简单方法是将 a p r i o r i 算法重新执行一遍，但这显然不是高效的，因为以前挖掘的结果没有 得到充分的利用，显然，解决此问题的关键是频繁项集的更新，文章提出了数 据集，支持度和可信度变化时频繁项集的更新方法。实验证明，该方法较重新 执行一遍a p r i o r i 算法需要较少的时间。 关键词数据挖掘：关联规则：挖掘算法：约束关联挖掘：频繁项集更新 。i i a b 盘二i i a b s t r a c t w i t ht h ed e v e l o p m e n to fd a t a b a s ea n di n t e r n e t ，m a n yo r g a n i z a t i o n s h a v eb e e na c c u m u l a t i n gam o u n to fd a t a o b v i o u s l y ，t h e s ed a t ai m p l ym u c h u s e f u lk n o w l e d g e t h e r e f o r e ，u s i n gt h isk n o w l e d g ei no r d e rt oc r e a t em o r e b e n e f i tb e c o m e sah o td i s c u s s i o n h o w e v e r w ec a nd on o t h i n gb yi n t u i t i o n a n dm a n u a lw o r ka n df a c e dw i t hf a c tt h a td a t ai sr i c hb u tk n o w l e d g ei s p o o r ，d a t a m i n i n gc o m e si n t ob e i n g t h i sp a p e rf i r s t l yi n t r o d u c e si nd e t a i l t h eb a c k g r o u n df r o mw h i c h d a t a m i n i n gc o m e si n t ob e i n g ，t h ec o n c e p to fd a t a m i n i n g ，u s e dm e t h o d ， m i n e dd a t aa n da p p l i e dd o m a i n a sav e r yi m p o r t a n tr e s e a r c ht o p i c ，t h i s p a p e ri l l u s t r a t e sd e f i n eo fa s s o c i a t i o nr u l em i n i n ga n dc l a s s i cm i n i n g a l g o r i t h m ，n a m e l y a p r i o r i ，a n a l y z e st h es h o r t c o m i n go fa p r i o r ia n d i n t r o d u c e si m p r o v e m e n to fi ts of a r a c c o r d i n gt ot h ec o n c e p tt h a tm a ns h o u l db ec e n t e ro fd a t a m i n i n g ， w es h o u l di n t e r a c t i v e l ym i n ed a t a s e t t h i sp a p e rs t u d i e si t i nt w o a s c e p t s ，n a m e l yt h er a p i dm i n i n go fc o n s t r a i n ta s s o c i a t i o nr u l ea n d q u l i c k l yu p d a t ef r e q u e n ti t e ms e t f o rr a p i dm i n i n go fc o n s t r a i n ta s s o c i a t i o nr u l e ，t h i sp a p e ra n a l y z e s t y p e so fu s u a l l yu s e dc o n s t r a i n ta n dc l a s s i f i e si t t op u s hc o n s t r a i n t s i n t om i n i n gp r o c e d u r ea se a r l ya s w ec a l li no r d e rt oi m p l e m e n ti n t e r a c t i v e m i n i n g ，w ep u tf o r w a r dt h ea r c h i t e c t u r eo fc o n s t r a i n ta s s o c i a t i o nr u l e a n dc c c o p t i m i z a t i o np r i n c i p l e h o w e v e r ，g e n e r a lm i n i n gm e t h o dh a sn o t n e c e s s a r i l yo p t i m a lp e r f o r m a n c e ，a sf o rc o n s t r a i n tt h a ti t e mi se i t h e r p r e s e n c eo ra b s e n c e ，t h ep a p e rb r i n g sf o r w a r dam i n i n ga l g o r i t h m t r a n s a c t d a t a c l i p b a s e d ，t h i sa l g o r i t h mh a sb e t t e rp e r f o r m a n c et h a n g e n e r a la l g o r i t h mb yv e r i f i c a t i o n u s e r f r e q u e n t l yc h a n g i n gm i n i n g c o n d i t i o n s ot h a tf i n do u t i n t e r e s t i n gr u l e sb yi n t e r a c t i v em i n i n gp r o c e s s ，t h eu p d a t eo ff r e q u e n t i t e m s e tb e c o m e sav e r yi m p o r t a n tq u e s t i o n t h es i m p l er e s o l v et oq u e s t i o n i se x e c u t i n ga p r i o r ia g a i n ，b u ti ti sn o te f f i c i e n tb e c a u s ef o r m e rm i n i n g r e s u l tisn o tu s e d t h i sp a p e rp u t sf o r w a r du p d a t ea l g o r i t h mo ff r e q u e n t i t e m s e tw h e nd a t a s e t ，s u p p o r to rc o n f i d e n c ei sc h a n g e d t h ee x p e r i m e n t s h o w st h a tt h ea l g o r i t h mism o r ee f f i c i e n tt h a nf o r m e ro n e k e y w o r d sd a t a m i n i n g ：a s s o c i a t i o nr u l e ：m i n i n ga l g o r i t h m ；c o n s t r a i n t a s s o c i a t i o nm i n i n g ；f r e q u e n ti t e m s e tu p d a t e - 1 1 1 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：监基型3 日期：建：丛垒兰 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：! 堡：整1 8 导师签名：同期： 第1 章绪论 1 1 研究课题的来源 第1 章绪论 考虑包含很多商品项的超市，商店经理可能想了解他的顾客的购物习惯。例 如，想知道“什么商品组或集合顾客多半会在一次购物时同时购买? ”为回答这 个问题，他可以在他的商店顾客事务零售数据上运行购物篮分析。分析结果可以 用于市场规划、广告策划和分类设计。例如，购物篮分析可以帮助经理设计不同 的商店布局。一种策略是：经常一起购买的商品可以放近一些，以便进一步刺激 这些商品一起销售。例如，如果顾客购买计算机也倾向于同时购买财务管理软件。 那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是： 将硬件和软件放在商店的两端，可能诱发买这些商品的顾客一路挑选其他商品。 例如，在决定购买一台很贵的计算机之后，去看软件陈列，购买财务管理软件， 路上可能看到安全系统，可能会决定也购买家庭安全系统。购物篮分析也可以帮 助规划什么商品降价出售。如果顾客倾向于同时购买计算机和打印机，打印机降 价出售可能既促使购买打印机，又促使购买计算机。 如果我们想象全域是商店中可利用的商品的集合，则每种商品有一个布尔变 量，表示该商品的有无。每个篮子则可以用一个布尔向量表示。可以分析布尔变 量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的 形式表示。例如，购买计算机也趋向于同时购买财务管理软件可以用以下关联规 则的形式表示： c o m p u t e r = f m a n c i a l _ m a n a g e m e n t _ s o f i w a t e s u p p o r t = 2 , c o n f i d e n c e = 6 0 规则的支持度和置信度是两个规则兴趣度度量，它们分别反映规则的有用性 和确定性。上述规则的支持度2 意味着分析中的全部事务的2 同时购买计算机 和财务管理软件。置信度6 0 意昧着购买计算机的顾客6 0 也购买财务管理软 件。关联规则被认为有趣的，如果它满足最小支持度阈值和最小置信度阈值。这 些阈值可以由用户和领域专家设定。 关联规则的挖掘还可以用来分类。1 。先利用迭代方法找出所有频繁的、精确 的可能规则( p r ) ，然后使用一种启发式方法来构造分类。 北京工业大学工程硕士学位论文 关联规则挖掘工具应能挖掘出对用户有用的关联规则，在关联规则挖掘过程 中，用户可能设置错误的阈值或者想改变他们，或者可能想得到某些包含一些特 定的项或不包含某些项的特殊规则，这时，我们不应该把整个挖掘看成一个黑盒， 而应该打开这个黑盒，允许用户不断的改变规则的约束条件，使用户和挖掘工具 交互进行，以便用户得到感兴趣的关联规则，这便是本文所要讨论的主要问题。 1 2 目前研究现状 交互式关联规则挖掘主要包含两个方面的研究内容，即约束关联规则的快速 挖掘和频繁项集的快速更新。 1 2 1 国外研究及应用现状 自从i b ma l m a d e n 研究中心的r a k e s ha g r a w a l1 9 9 3 年在他的研究论文瑚 中提出数据库中的关联规则挖掘以来，国外许多专家学者对关联规则的挖掘展 开了深入细致的研究。这些研究大体上可分为关联规则的快速挖掘和频繁项集 的快速更新两类。 由于关联规则是从大量的事物数据中进行挖掘。需要消耗大量的资源，因 此挖掘效率一开始便成为一个重要的研究问题，文献 1 7 ，1 8 ，2 0 ，2 1 ，2 4 ，2 5 ， 2 6 ，2 7 等对此进行了详细的讨论，他们的一条主要思路是尽量减少数据库扫描 的次数，降低i o 的代价。在实际中我们面对的多数是有约束条件的关联规赠的 挖掘，为此加拿大s i m o nf r a s e r 大学j i a w e ih a r t 领导的数据挖掘研究小组从 1 9 9 8 年开始在他们的论文 4 ，5 ，6 ，7 ，8 】中系统地讨论了以用户为中心约束关 联规则的快速挖掘的问题，把关联规则的约束条件分为五类：单调，反单调， 简洁，可转换的约束和不可转换的约束，按照优化原则分别讨论了相应的快速 挖掘方法。但也还有一些有待进一步研究的问题，如：怎样判断一个约束是弱 约束，以及怎样把它转化为反单调或简洁的约束? 为非半简洁约束提出的策略 还不是c c c ( c o n s t r a i n t sc h e c k i n ga n dc o u n t i n g ) 优化的，怎样找到那么一 个策略是一个开放的问题。进一步扩展约束以包括更多的，更有用的约束分类 也是一个很重要的阀题。为了进一步提高挖掘速度，人们考虑利用并行与分布 计算等高性能的计算手段来加快关联规则的挖掘，文献 2 2 ，2 8 ，2 9 ，3 0 ，3 1 ， 第1 章绪论 3 2 ，3 3 ，3 4 ，3 5 1 讨论了并行与分布式数据挖掘的问题，有的甚至用到最新的分 布式人工智能和网格的技术。 在频繁项集的更新方面，国外学者讨论得较少，较早的有影响的研究论文 是n w c h e u n g ，j b a n 等人1 9 9 6 年在i n t c o n f d a t ae n g i n e e r i n g ( i c d e 9 6 ) 上的论文 m a i n t e n a n c eo fd i s c o v e r e da s s o c i a t i o nr u l e si nl a r g ed a t a b a s e s ： a ni n c r e m e n t a lu p d a t i n gt e c h n i q u e 9 1 ，它讨论了当新的事务数据加到事务 数据库时有效维护被发现的频繁项集的增量更新技术。 1 2 2 国内研究及应用现状 与国外相比，国内对关联规则挖掘的研究稍晚，还没有形成整体力量。目 前，国内已有一些科研单位和高等院校开展了关联规则挖掘的基础理论及其应 用研究，这些单位包括清华大学、中科院计算技术研究所、复旦大学、华中科 技大学、南京大学和东南大学等。华中科技大学、复旦大学、浙江大学、中国 科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则挖掘算法的 优化和改造。对关联规则增量更新技术的讨论更是如火如荼，在1 9 9 8 年华中科 技大学的冯玉才、冯剑林的论文之后，许多学者在a p r i o r i 算法的基础上研 究了关联规则的增量更新技术。如文献 3 8 4 7 等都或多或少从不同的角度提出 了一些新的有创见的观点和方法。在j i a w e ih a r t 等人于2 0 0 0 年在论文 i i 中 提出关联规则挖掘的f p - t r e e 算法以来，东南大学的朱玉全、孙志辉等人又系 统的研究了基于f p - t r e e 的关联规则增量更新技术，发表了一系列的研究论文 【1 2 ，1 3 l 4 1 5 l 。 但国内还没有人把约束关联规则的快速挖掘算法和增量式更新算法集成到 一个整体框架中，形成一个有效的关联规则挖掘工具，国内企业运用数据挖掘 技术来协助业务活动的应用还处于起步阶段。成功应用的案例还比较少，这对 数据挖掘技术和工具的研究人员以及开发商来说，我国是一个有巨大潜力的市 场。 北京= 【业大学工程顸士学位论文 1 3 课题研究的理论与实际意义 关联规则挖掘能得到大型事务数据库中频繁出现的项目集，从丽为商店经理 等人提供诸如商品摆设、营销策略等决镱支持。实际决策时，决策者往往对满足 一定约束条件的关联规则感兴趣，在挖掘约束关联规则时，如果我们把整个挖掘 过程看成一个黑盒，只是向黑盒输入约束条件，然后便执行黑盒中的过程直至得 到结果，没有用户的参与、交互，这样很可能得到很多无用的关联规则，从而也 就耗费大量的挖掘时问。比较明智、高效的方法是打开黑盒，让用户与系统不断 的交互，根据约束条件不断缩小搜索范围，减少冗余规则，从而提高挖掘效率。 同时，我们知道关联规则挖掘的主要任务是得到频繁项集，它耗费整个过程的绝 大多数时间等资源，随着用户与系统的不断交互，不断地改变约束条件需要频 繁地改变满足条件的频繁项集，因此。如何快速地更新被发现地频繁项集也是一 个很有意义的课题。 本文从两个方面研究了交互式关联规则挖掘的问题，即约束关联规则的快速 挖掘和频繁项集的快速更新，提出了对规则中项的出现有特别要求时规则的快速 挖掘算法，实验证明该算法要优于j i a w e ih a r t 他们提出的约束关联规则挖掘的一 般方法。同时讨论了当数据集、最小支持度和最小可信度发生变化时频繁项集的 快速更新算法。把它们集成到一个关联规则的挖掘模块中，实现关联规则等的交 互式挖掘。 1 4 本文组织结构 本文的结构安排如下： 第1 章绪论，简述了本研究课题的背景、研究现状及其理论与现实意义。 第2 章数据挖掘技术。论述了数据挖掘产生的历史必然性，介绍了数据挖 掘的概念，数据挖掘的功能，数据挖掘一般要经历的步骤，数据挖掘技术研究的 方向和存在的问题。 第3 章关联规则挖掘算法研究。重点介绍了a p r i o r i 和f p t r e e 两种最基 本、最典型的关联规则挖掘算法。 第4 章约束关联规则的快速挖掘。主要介绍了约束关联规则挖掘的体系结 构，约束的分类及相应的算法，提出了对规贝l j 中项的出现有特殊要求时关联规则 第1 章绪论 的快速挖掘算法，通过实验证明该算法较一般的算法有更高的效率。 第5 章频繁项集的快速更新。系统的研究了数据集、最小支持度和最小可 信度变化时频繁项集的快速更新算法。 最后，对本论文做了总结和展望。 第2 章数据挖掘技术 第2 章数据挖掘技术 数据挖掘作为一个只有十几年研究历史的较新研究领域，许多概念和技术 是逐步发展起来的。因此，本章将系统地介绍相关的概念和技术，并力求从不 同视点和流派来阐述数据挖掘的重要概念、发展和应用情况。在2 1 节，我们 介绍了数据挖掘技术产生的商业和技术背景：在2 2 节，我们阐述了数据挖掘 的概念；在2 ，3 节，我们将数据挖掘和传统数据分析进行了比较：在2 4 节， 我们将数据挖掘技术进行了分类；2 5 节，阐明了数据挖掘的功能：2 6 节， 说明了数据挖掘的过程；2 7 节，分析了数据挖掘研究中存在的问题：2 8 节， 分析了数据挖掘技术的应用现状和发展趋势；2 9 节，小结。 2 1 数据挖掘技术的产生背景 2 1 1 数据挖掘技术的商业需求分析 数据挖掘之所以吸引专家学者的研究兴趣和引起商业厂家的广泛关注，主 要在于大型数据库系统的广泛使用和把数据转换成有用知识的迫切需要。目前， 由于各种新型技术与数据库技术的有机结合，使数据库领域中的新内容、新应 用、新技术层出不穷，形成了庞大的数据库家族。但是，这些数据库的应用都 是以实时查询处理技术为基础的。从本质上说，查询是对数据库的被动使用。 由于简单查询只是数据库内容的选择性输出，因此它和人们期望的分析预测、 决策支持等高级应用仍有很大距离。 新的需求推动新的技术的诞生。数据挖掘的灵魂是深层次的数据分析方 法。数据分析是科学研究的基础，许多科学研究都是建立在数据收集和分析基 础上的。同时在目前的商业活动中，数据分析总是和一些特殊的人群的高智商 行为联系起来，因为并不是每个平常人都能从过去的销售情况预测将来发展趋 势或作出正确决策的。但是，随着一个企业或行业业务数据的不断积累，特别 是由于数据库的普及，人工去整理和理解如此大的数据源已经存在效率、准确 性等问题。因此，探讨自动化的数据分析技术，为企业提供能带来商业利润的 决策信息就成为必然。 北京工业太学工程硕士学位论文 事实上，数据( d a t a ) 、信息( i n f o r m a t i o n ) 和知识( k n o w l e d g e ) 可以看 作是广义数据表现的不同形式。毫不夸张地说，人们对于数据的拥有欲是贪婪 的，特别是计算机存储技术和网络技术的发展加速了人们收集数据的范围和容 量。这种贪婪的结果导致了“数据丰富而信息贫乏( d a t ar i c h & i n f o r m a d o n p o o r ) ”现象的产生。数据库是目前组织和存储数据的最有效方法之一，但是面 对日益膨胀的数据，数据库查询技术已表现出它的局限性。直观上说，信息或 称有效信息是指对人们有帮助的数据。例如，在现实社会中，如果人均日阅读 时间在3 0 分钟的话，一个人一天最快只能浏览一份2 0 版左右的报纸。如果你 订阅了1 0 0 份报纸，其实你每天也不过只阅读了一份而已。面对计算机中的海 量的数据，人们也处于同样的尴尬境地，缺乏获取有效信息的手段。知识是一 种概念、规则、模式和规律等。它不会象数据或信息那么具体，但是它却是人 们一直不懈追求的目标。事实上。在我们的生活中，人们只是把数据看作是形 成知识的源泉。我们是通过正面的或反面的数据或信息来形成和验证知识的， 同时又不断地利用知识来获得新的信息。因此，随着数据的膨胀和技术环境的 进步，人们对联机决策和分析等高级信息处理的要求越来越迫切。在强大的商 业需求的驱动下，商家们开始注意到有效地解决大容量数据的利用问题具有巨 大的商机；学者们开始思考如何从大容量数据集中获取有用信息和知识的方法。 因此，在二十世纪八十年代后期，产生了数据仓库和数据挖掘等信息处理思想。 2 1 2 数据挖掘产生的技术背景分析 任何技术的产生总是有它的技术背景的。数据挖掘技术的提出和普遍接受 是由于计算机及其相关技术的发展为其提供了研究和应用的技术基础。 归纳数据挖掘产生的技术背景，下面一些相关技术的发展起到了决定性的 作用： 数据库、数据仓库和i n t e m e t 等信息技术的发展； 计算机性能的提高和先进的体系结构的发展； 统计学和人工智能等方法在数据分析中的研究和应用。 数据库技术从二十世纪8 0 年代开始，已经得到广泛的普及和应用。在关 系型数据库的研究和产品提升过程中，人们直在探索组织大型数据和快速访 第2 章数据挖掘技术 问的相关技术。高性能关系数据库引擎以及相关的分布式查询、并发控制等技 术的使用，已经提升了数据库的应用能力。在数据的快速访问、集成与抽取等 问题的解决上积累了经验。数据仓库作为一种新型的数据存储和处理手段，被 数据库厂商普遍接受并且相关辅助建模和管理工具快速推向市场，成为多数据 源集成的一种有效的技术支撑环境。另外，i n t e r n e t 的普及也为人们提供了丰富 的数据源。据说，在美国电视达到5 0 0 0 万户大约用了1 5 年，而i n t e m e t 上网达 到5 0 0 0 万户仅用了4 年。而且i n t e m e t 技术本身的发展，已经不光是简单的信 息浏览，以w e b 计算为核心的的信息处理技术可以处理i n t e m e t 环境下的多种 信息源。因此，人们已经具备利用多种方式存储海量数据的能力。只有这样， 数据挖掘技术才能有它的用武之地。这些丰富多彩的数据存储、管理以及访问 技术的发展，为数据挖掘技术的研究和应用提供了丰富的土壤。 计算机芯片技术的发展，使计算机的处理和存储能力曰益提高。大家熟知 的摩尔定律告诉我们，计算机硬件的关键指标大约以每1 8 个月翻一番的速度在 增长，而且现在看来仍有日益加速的趋势。随之而来的是硬盘、c p u 等关键部 件的价格大幅度下降，使得人们收集、存储和处理数据的能力和欲望不断提高。 经过几十年的发展，计算机的体系结构，特别是并行处理技术已经逐渐成熟和 普遍应用，并成为支持大型数据处理应用的基础。计算机性能的提高和先进的 体系结构的发展使数据挖掘技术的研究和应用成为可能。 历经了十几年的发展，包括基于统计学、人工智能等在内的理论与技术性 成果已经被成功地应用到商业处理和分析中。这些应用从某种程度上为数据挖 掘技术的提出和发展起到了极大地推动作用。数据挖掘系统的核心模块技术和 算法都离不开这些理论和技术的支持。从某种意义讲，这些理论本身发展和应 用为数据挖掘提供了有价值的理论和应用积累。数理统计是一个有几百年发展 历史的应用数学学科。然而它和数据库技术的结合性研究应该说最近十几年才 被重视。以前的基于数理统计方法的应用大多都是通过专用程序来实现的。我 们知道，大多数的统计分析技术是基于严格的数学理论和高超的应用技巧的， 这使得一般的用户很难从容地驾驭它。数据挖掘技术是数理统计分析应用的延 伸和发展，假如人们利用数据库的方式从被动地查询变成了主动发现知识的话， 那么概率论和数理统计这一古老的学科可以为我们从数据归纳知识一一数据挖 北京工业大学工程确士学位论文 掘技术提供理论基础。 人工智能是计算机科学研究中争议最多但是仍始终保持强大生命的研究 领域。机器学习应该说是得到了充分的研究和发展，并且数据挖掘技术继承了 机器学习解决问题的思想。专家系统( e x p e r ts y s t e m ) 曾经被认为人工智能向 着实用性方向发展的最有希望的技术，但是，这种技术也逐渐表现出投资大、 主观性强、应用面窄等致命弱点。例如，知识获取被普遍认为是专家系统研究 中的瓶颈问题。另外，由于专家系统是主观整理知识，因此这种机制不可避免 地带有偏见和错误。数据挖掘继承了专家系统的高度实用性特点，并且以数据 为基本出发点，客观地挖掘知识。因此，可以说，数据挖掘研究在继承已有的 人工智能相关领域的研究成果的基础上，摆脱了以前象牙塔式研究模式，真正 开始客观地从数据集中发现蕴藏的知识。 2 2 数据挖掘概念 数据挖掘从产生至今已有多种定义【1 9 1 ，其中得到公认的是：数据挖掘是从 大量数据中揭示出有效的、新颖的、潜在有用的，以及最终可理解的知识和模式 的非平凡过程。其中： 数据：是用来描述事物的信息集合( 如客户购物事务库中客户购物的明细记 录) ，是我们进一步发现知识的原材料。 新颖：经过数据挖掘提取出的模式必须是新颖的。模式是否新颖可以通过 两个途径来衡量：其一是通过对比当前得到的数据和以前的数据或期望得到的数 据之间的比较来判断该模式的新颖程度：其二是通过对比发现的模式与已有的模 式的关系来判断。 潜在有用：即提出的模式应该是有实际意义的。 可理解：数据挖掘的一个目标就是将数据库中隐含的模式以容易被人理解 的形式表现出来，从而帮助人们更好地了解数据库中所包含的信息。数据挖掘不 同于以往知识获取技术，它的特点之一是发现的知识是人们( 至少是领域专家) 易于理解的，如“i f t h e n ”的形式。因此挖掘过程也是一个人机交互、 螺旋上升的过程。 模式：对于集合f 中的数据，可以用语言l 来描述其中数据的特性。表 第2 章数据挖掘技术 达式e e l ，e 所描述的数据是集合f 的一个子集f e 。只有当表达式e 比列举 的所有f 。中元素的描述方法更为简单时，才可称之为模式。“若成绩 = 8 0 ，则成 绩优良”可称为一个模式，而“若成绩为8 0 、8 1 、，则成绩优良”不能称为 一个模式。 非平凡过程：数据挖掘是对数据进行更深层处理的过程，而不是仅仅对数 据进行加减求和等简单运算或查询，因此说它是一个非平凡过程。 2 3 数据挖掘与传统数据分析的区别 数据挖掘是从海量数据中发现有意义的、新的模式和趋势的过程。它与传 统数据分析是完全不同的工具，基于的技术也大相径庭。我们先从表2 1 t 1 1 传统 数据分析和数据挖掘分析的需求不同来看看二者的区别： 表2 - 1 数据挖掘与传统数据分析的比较 t a b l e2 一lc o , p a r i s o no fd m t r a d i t i o n a ld a t aa n a l y s i s 传统数据分析数据挖掘分析 打印出上个月结算中心的花费 预测和解释下个月的需求 利用模型，告诉去年有关合同取消 解释为什么有些客户转向竞争对手， 方面的情况发现一些新的关于客户行为的模式 将优惠券邮寄给每位外出t 作且有基于历史记录确定最有能力与需求的 两个小孩的家庭主妇群体并将优惠券邮寄给他们 如果收入低于3 0 英镑，要求贷款超 对一张贷款请求，预测其无法还款的 过l o 英镑，则拒绝之可能性 依照年龄、性别、以及是否吸烟来制分析现行业业务的利润与风险，预测 定人寿保险单 公司对保险客户所需承担的风险 传统的数据分析过程在本质上是一个演绎推理的过程，是基于问题的分析， 是验证型的。其缺点有两个，首先，其答案是建立在问题所依赖的假设上的，而 假设往往是由提问者的直觉造成的，与提问者直觉相反的或与未想到问题有关的 模式就被隐藏起来。它只能给出用户希望得到的统计结果，却不能给出用户没有 考虑到，但事实上很有价值的信息。其次，如果分析的变量达到几十个或上百个， 那么再用传统的数据分析方法来分析验证这些假设将是一件非常困难的事情。 而数据挖掘是先验型的、预测型的，是在数据库中自动寻找模型，在本质上是 一个归纳的过程。它克服了传统数据分析的缺点，不存在先入为主的假想、强 北京工业大学工程硕士学位论文 一i i - 制的观点、隐含的偏好，分析的结果比较客观。数据挖掘能够自动、快速的估 计和评测数据库中大量的信息，不仅可以挖掘出显而易见的趋势，还可以挖掘 出那些微妙的、无法预料的、与直觉相反的关系和模式，这些模式往往还未被 验证，却直接关系到重要的商业决策。 2 4 数据挖掘技术的分类 数据挖掘涉及的学科领域和方法很多，有多种分类方法。 根据挖掘任务可以分为：分类或预测模型发现、数据总结与聚类发现、关 联规则发现、序列模式发现、相似模式发现、混沌模式发现、依赖关系或依赖 模型发现、异常和趋势发现等。 根据挖掘对象可以分为：关系数据库、面向对象数据库( o b j e c t o r i e n t e d d a t a b a s e ) 、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据 库、遗产数据库以及w e b 等对象的挖掘。 根据挖掘方法可以分为：机器学习方法、统计方法、聚类分析方法、探索 性分析、神经网络( n e u r a ln e t w o r k ) 方法、遗传算法( g e n e t i c a l g o r i t h m ) 、数 据库方法、近似推理和不确定性推理方法、基于证据理论和元模式的方法、现 代数学分析方法、粗糙集( r o u g hs e t ) 方法、集成方法等。 根据数据挖掘所能发现的知识可以分为：广义型知识挖掘、差异型知识挖 掘、关联型知识挖掘、预测型知识挖掘、偏离型( 异常) 知识挖掘、不确定性 知识等。 当然，这些分类方法都从不同角度，刻画了数据挖掘研究的策略和范畴， 他们是互相交叉而相互补充的。 2 5 数据挖掘的功能 数据挖掘系统的功能主要有以下几大类： 统计归纳：利用统计模型和数学模型来解释异常的数据模式。通常使用的模 型有线性分析和非线性分析、连续回归分析和逻辑回归分析、单变量和多变量分 析以及时问序列分析。统计分析工具能够提供可视化功能和分析功能来寻找数据 第2 章数据挖掘技术 间关系，构造模型来解释数据，交互式过程和迭代过程用来求精模型，最终开发 出最具适应性的模型来将数据转化为信息。 关联分析：关联分析搜索数据库的条目，从中寻找重复出现概率高的模式。 它展示了数据问未知的关联关系。其典型的应用是购物篮分析，如购买商品a 和 b 的客户有8 5 同时也购买了商品c ，用规则表示为h ，b = c ( 8 5 ) 。本文第三 章将着重对关联技术进行讨论。 分类和预测：分类和预测用于提取描述重要数据类的模型或预测未来的数据 趋势。分类可预测类标号( 或离散值) ，预测可以预测连续值。例如，建立分类 模型对银行贷款的安全风险进行分类；建立预测模型对商品的销售量、股票价格、 产品合格率等进行预测。分类技术有判定树归纳、贝叶斯分类和贝叶斯网络、神 经网络、最近i 临、基于安全的推理、遗传算法、粗糙集和模糊逻辑等。预测方法 包括线性的、非线性的和广义线性回归模型。 聚类分析：聚类将数据对象分组成为多个类或簇，在同一个簇中的对象之 间具有较高的相似度，而不同簇中的对象差别较大。聚类与分类不同，它要划 分的类是未知的。相似度是根据描述对象的属性值来计算的。聚类分析广泛应 用于模式识别、数据分析、图像处理和市场研究。在商务上，聚类分析能帮助 市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同 的客户群的特征。聚类技术有划分方法、层次方法、基于密度的方法、基于网 格的方法和基于模型的方法。 2 6 数据挖掘步骤 在实施数据挖掘之前，先制订计划，确定要采取什么样的步骤，每一步要做 什么，要达到什么样的目标。有了好的计划才能保证数据挖掘有条不紊的实施并 取得成功。数据挖掘一般包括四个步骤：确定业务对象、数据准备、挖掘操作、 结果表达和解释【1 6 l 。虽然我们把各个步骤按顺序排列，但数据挖掘过程并不是线 性的。要取得好的结果就要不断反复和重复这些步聚。 北京工业大学工程硕士学位论文 2 。6 。1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步，挖 掘的最后结果是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而 数据挖掘则带有盲目性，是不会成功的。因此，在挖掘之前要明确目的和需求。 2 6 2 数据准备 这个阶段又可进一步分成3 个子步骤：数据集成、数据选择、数据变换。 2 6 2 1 数据集成 数据挖掘可能涉及到内部多个数据源，还可能需要一些外部的数据( 如人 口统计、天气数据或信用卡使用数据等) ，这就需要将多个数据源中的数据结合 起来存放在一个一致的数据存储( 如数据仓库) ，以便于数据挖掘操作。 2 6 2 2 数据选择 这个阶段需要选择用于数据挖掘的数据( 郎源数据的子集) 。这与对数据进 行采样和选择预测变量是不同的，这里只是粗略的把一些冗余或无关的数据除 去。有时，由于资源的限制、费用的限制、数据使用的限制和数据质量等原因 也必须对数据进行选择。 2 6 2 3 数据变换 将数据转换成适合于挖掘的形式脚。数据变换可能涉及如下内容： 平滑：由于数据库中可能存在各种错误数值( 如身份证号码可能被粗心的 数据录入人员录入了年龄) ，还可能存在空缺值。这些都会最终影响模型的质基。 因此必须采取分箱、聚类和回归等技术来修正错误数值、填充空缺的数值。 聚集：有时需要对数据进行汇总和聚集。例如，可以根据日销售数据，计 算月和年销售额。通常这一步是用来为多粒度数据分析构造数据立方体。 规范化：有些算法和工具对数据范围有要求，如神经网络要求所有的变量 都在0 1 之间，这就需要对原始数据按一定比例缩放，使之落入一个特定的区 间。 属性构造：很多情况下需要从原始数据中衍生一些新的属性以提高数据挖 掘的效率和可靠性。 第2 章数据挖掘技术 2 6 3 挖掘操作 根据所要挖掘的模式类型选择适当的数据挖掘算法，选取合适的模型和参 数。当然，没有一种算法或工具适应所有的数据，通常也很难在开始时就能决 定哪种算法对你所面临的问题来说是最好的，因此很多情况下，需要建立不同 的模型( 参数或算法) ，从中选择最好的。 2 6 4 结果表达和解释 将挖掘出的结果以一种易于理解的形式表示出来，并进行解释和评价。具 体包括消除无关的、多余的模式，过滤出要呈现给用户的信息；利用可视化技 术将有意义的模式以图形或逻辑可视化的形式表示，转化为用户可以理解的语 言。一个成功的数据挖掘的应用应能将原始数据转换为更简洁、更易理解、可 明确定义关系的形式。此外还包括解决发现的结果与以前知识的潜在冲突，及 利用统计方法对模式进行评价，决定是否需要重复以前的操作，以得到最优、 最适合的模式。 2 7 数据挖掘研究中存在的问题 要理解数据挖掘，首先要弄明白数据挖掘需要解决哪些问题，目前还面临着 哪些难题。目前，数据挖掘中的许多问题都已获得解决，但数据挖掘技术的研究 还很不成熟，面临着许多问题有待解决。如数据的巨量性、动态性、噪声性、缺 值和稀疏性，发现模式的可理解性、兴趣或价值性，应用系统的集成，用户的交 互操作，知识的更新管理，复杂数据库的处理等等f 1 ”。下面对这些问题进行较为 详细地讨论。 2 7 1 有效处理巨量和高维的数据 包含上百万条记录和数千兆字节甚至几兆兆字节的数据库已经司空见惯，数 据库关系表所涉及的属性或变量数也大到成百上千的数量。这种数据的巨量和高 维性使得数据挖掘时模式的搜索空间异常巨大，同时还可能导致搜索出无意义模 北京t 业大学工程硕士学位论文 式的机会增加。传统的技术已经难以适用，如常规的机器学习方法一般只能处理 不超过几千个记录或例子的数据集。为了解决这些问题，需要有高效的，特别是 线性计算复杂度的( 近似) 算法、抽样方法、大规模并行处理技术、维数消减方 法等技术。 2 7 2 数据噪声与缺值 在商业数据库中噪声和缺值是一种常见现象。如美国人口普查数据的错误率 就高达2 0 。错误或噪声可能来自于数据录入的误操作或现实中不可避免的因素 ( 如民意调查的主观性) 。数据遗失有两类情况：一是某些宇段上缺值，另一种 是数据库在设计阶段就可能没有考虑某些重要属性或字段( 数据库并不是为数据 挖掘而设计的，它的设计有自己的考虑) ，而这些属性对于数据挖掘进行知识发 现可能很重要。因些，需要研究出可行的方法来对这些噪声数据和缺值进行有效 处理。 2 7 3 交互性用户界面( 数据挖掘可视化) 数据挖掘过程中操作者的适当参与是必不可少的。一方面，数据挖掘系统 应该为用户提供表达其要求和挖掘策略的交互界面，深化数据挖掘过程，使得 用户能从不同角度灵活看待多抽象层上的数据挖掘结果。另一方面，数据挖掘 系统要把生成的结果通过交互界面传递给用户。因此，准确而直观地描述挖掘 结果的友好而高效的用户界面一直是这方面研究的重要课题。 2 7 4 数据的动态变化和知识的更新维护 数据的动态变化常常会使得以前发现的模式不再有效，特别是数据库可能增 加、删除或改变变量。发生这些情况时则要求设计数据挖掘系统的过程中必须考 虑知识的更新维护，如怎样解决知识冲突。另外数据的动态性也提出了新的数据 挖掘问题：主动数据库挖掘研究。 第2 章数据挖掘技术 2 7 5 应用系统的集成 一个单独的数据挖掘发现系统如果不和具体的应用系统集成或结合，将毫无 意义。数据挖掘应该和数据库管理系统或l d i s 、电子表单、实时传感数据采集， 特别是决策支持系统集成在一起。 2 7 6 挖掘对象的多样化 数据库发展的一个趋势是各种类型数据的使用，特别是多媒体数据越来越 多，这要求相应的数据挖掘系统不但有处理数值数据的功能，还应能处理符号、 文本、声音、图形、图像、视频等类型数据。 以上的问题涉及数据挖掘的方方面面，它们都有待人们去进行更深入的研 究工作，这将不断的推动数据挖掘技术深入发展和广泛应用，创造出更多的社 会和经济价值。 2 8 数据挖掘的应用分析 麻省理工学院的科技评论杂志提出未来5 年对人类产生重大影响的1 0 大新兴技术，“数据挖掘”位居第三。我们知道，数据挖掘技术从一开始就是面 向应用的。由于现在各行业的业务操作都向着流程自动化的方向发展，企业内 产生了大量的业务数据。一般地，企业内的业务数据是由于商业运作而产生的， 很少是为了分析的目的而收集的。因此，数据挖掘的应用成为高层次数据分析 和决策支持