（计算机应用技术专业论文）数据挖掘中关联规则算法的分析与优化研究.pdf

摘要 随着数据库技术的成熟和数据应用的普及，人类积累的数据量币在以指数速 度增长。当数据量极度增长时，如果没有有效的方法，由计算机及信息技术来提 取有用信息和知识，人们也会感到面对信息海洋像大海捞针一样束手无策。面对 这一挑战，数据挖掘技术应运而生。数据挖掘( d a t am i n i n g ，d m ) 就是从大量 的数据中挖掘出人们感兴趣的知识，它是一类深层次的数据分析方法，被认为是 解决“数据爆炸知识贫乏”的有效方法之一，最近几年罩已被数据库界广泛研究。 经过若干年的研究和实践，其经济价值已经显现出来，被广泛应用于科学研究、 金融投资、市场营销、保险、医疗卫生、产品制造业、通信网络管理等行业。它 包含关联规则挖掘、预测、分类、聚类、演化分析等多种技术手段，其中关联规 则挖掘是一种主要的也是用途最广的数据挖掘方法。 本文对k d d ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e 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 ) 等概念作了阐述，为 深入讨论作了充分的准备。在对现有关联规则文献的研究基础上，详细的分析了 关联规则的基本概念和基本性质，并且对关联规则的典型频繁集挖掘算法a p r i o f i 算法进行了归纳、分析和研究，为a p r i o r i 改进算法的提出和构造建立了理论上 的必要性前提。 本文的重点是a p r i o r i 算法的分析研究和改进设计。在研究经典a p r i o r i 算法 的基础上，给出了一个新的算法，分别从减小事务数据库与候选项目集中的项目 规模和引入加权支持度两个方面对a p r i o f i 算法进行了优化与改进：一方面，针 对在a p r i o r i 算法下，要扫描的事务数据库规模与a p r i o r i 算法生成的候选频繁项 目集个数过多这两个瓶颈问题，新算法尽量缩减两者的规模，使之尽可能高效的 产生出频繁项集；另一方面，针对数据库中项目分布不均匀，出现概率相差较大， 所挖掘出的关联规则将可能涉及不到出现频率较低的项目的问题，通过给它们赋 以不同权值，即引入加权支持度，从而可以挖掘出a p r i o r i 挖掘不出但却极具价 值的规则。经过优化改进，新算法在时问上的消耗要少于a p r i o r i 算法，提高了 算法的效率；同时，由于加入权值，使得算法能够挖掘出隐藏在小概率事件后的 关联规则，而这些规则恰恰是一般算法易于丢弃或挖掘不出的。 关键词：数掘挖掘，关联规则，a p r i o r i 算法，加权 a b s t r a c t a l o n gw i t ht h em a t u r i t yo fd a t a b a s et e c h n o l o g ya n d t h ep o p u l a r i t yo fd a t a a p p l i c a t i o n s ，t h e a m o u n to fd a t aw h i c h h u m a na c c u m u l a t e d i s g 。o w l n g e x p o n e n t i a l l y w h e nt h ea m o u n to f d a t ag r o wt ot h en t hp o w e r , i ft h e r ei sn oe 仃e c t l v e w a v p e o p l ew h ow a n tt ou s et h ec o m p u t e ra n di n f o r m a t i o nt c c h n o l o g y t oe x t r a c t u s e f u li n f b r m a t i 叩a n dk n o w l e d g ew o u l d a l s oh a v eb e e nf a c et h eo c e a n s o t i n f b 咖a t i o nh e l p l e s s ，l i k ean e e d l ei nah a y s t a c k f a c i n gt h i sc h a l l e n g e ，d a t am l n 】n g c a m ei n t ob e i n g d a t am i n i n g ( d m ) i st om i n et h ek n o w l e d g ew h i c hp e o p l e a r e i n t e r e s t e di nf r o mal a r g en u m b e ro fd a t a ，w h i c hi s ak i n do fi n d e p t hd a t aa n a l y s i s m e t h o d ，b ec o n s i d e r e do n eo ft h ee f f e c t i v ew a y st os o l v e ”d a t ae x p l o s i o na n d l a c ko f i m o v 订e d g e i nr e c e n ty e a r si t h a sb e e ne x t e n s i v er e s e a r c h e di nd a t a b a s ei n d u s t r y a f i e ts e v e r a ly e a r so fr e s e a r c ha n dp r a c t i c e ，i t se c o n o m i cv a l u eh a se m e r g e d a n dh a s b e e nw i d e l yu s e di ns c i e n t i f i cr e s e a r c h 、f i n a n c i a li n v e s t m e n t 、m a r k e t i n g 、i n s u m n c e 、 m e d i c a la n dh e a l t h 、p r o d u c tm a n u f a c t u r i n g 、c o m m u n i c a t i o n sn e t w o r km a n a g e m e n t a n do t h e ri n d u s t r i e s i tc o n t a i n st h ea s s o c i a t i o nm l em i n i n g ，f o r e c a s t i n g ，c l a s s i f i c a t l o n ， c l u s t e r i n g , t h ea n a l y s i so ft h ee v o l u t i o na n d o t h e rt e c h n o l o g ym e a n s u r e s a s s o c i a t l o n r u l em i n i n gi st h em a j o ra n dm o s tw i d e l yu s e dm e t h o do fd a t am m m g t h i sa r t i c l ee l a b o r a t eo nk 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 ) 、d a t a m i n i n g 、a s s o c i a t i o nr u l e sa n do t h e rc o n c e p t s ，w h i c h w e r em a d ef u l lp r e p a r a t i o n s f o ri n - d e p t hd i s c u s s i o n s o nt h eb a s i so fr e s e a r c h o ne x i s t i n ga s s o c i a t l o n 川i e s l i t e r a t u r e d e t a i l e da n a l y s et h eb a s i cc o n c e p t sa n df u n d a m e n t a l n a t u r eo ft h e a s s o c i a t i o nr u l e sa n ds u m m a r i z e 、a n a l y s ea n d r e s e a r c ht h ea s s o c i a t i o nr u l e s 7 sa p r i o n a l g o r i t h m w h i c hi sat y p i c a lf r e q u e n t - m i n i n ga l g o r i t h m ，f o ra p r i o r i i m p r 0 、7 e d a l g o r i t h m ，se v o l v i n ga n ds t r u c t u r ee s t a b l i s h i n gn e c e s s a r yp r e c o n d i t i o n i nt h et h e o 阱 t h i sa r t i c l ef o c u s e so na p r i o r ii m p r o v e da l g o r i t h m sd e s i g n a n da n a l y s i s r e s e a r c h o nt h eb a s eo ft h es t u d yo fc l a s s i c a la p r i o r ia l g o r i t h mw h i c hg w e sa b e w a i g o r i t h mf r o mr e d u c i n gd a t a b a s es e r v i c e s ，c a n d i d a t ei t e m s e t s s c a l eo f t h ep r o j e c t a n di n t r o d u c t i o no fw e i g h t e ds u p p o r tt oo p t i m i z ea n di m p r o v et h ea p n o na l g o r i t h m ： o nt h eo n eh a n d ，f o rt h ea p r i o r ia l g o r i t h m ，t h e r ea f et w o b o t t l e n e c kp r o b l e m sw h i c ha r e t h es c a n e dd a t a b a s es e r v i c e s s c a l ea n dt h en u m b e ro fc a n d i d a t ef r e q u e n ti t e m s e t st h a t a p r i o r ia l g o r i t h mg e n e r a t ei st o ol a r g e t h en e wa l g o r i t h mr e d u c et h e s c a l eo ft h et w o p r o b l e m sa sf a ra sp o s s i b l e ，w h i c hc a np r o d u c ef r e q u e n ti t e m s e t sa se f 矗c i e n t l va s p o s s i b l e ；o nt h eo t h e rh a n d ，f a c i n gt h ep r o b l e mo ft h ep r o j e c tu n e v e n l yd i s t r i b u t ei n t h ed a t a b a s e ，e m e r g e n c eo fal a r g e rd i f f e r e n c eb e t w e e nt h ep r o b a b i l i t y , s oa s s o c i a t i o n r u l e sw h i c hd i go u tm a yb en o tc o n t a i nt h el o w e r f r e q u e n c yp r o j e c t s ，t h r o u g hg i v i n g t h e md i f f e r e n tw e i g h t ，t h a ti st oi n t r o d u c et h ew e i g h t e ds u p p o r t ，i tc a nd i go u tv c r y v a l u a b l er u l e sw h i c ha p r i o r ia l g o r i t h mc a n t a f t e rb e i n g o p t i m i z e da n di m p r o v e d t h e n e w a l g o r i t h mi nt e r m so ft i m ec o n s u m p t i o ni sl e s st h a nt h ea p r i o r ia l g o r i t h m ，w h i c h i m p r o v e dt h ee f f i c i e n c yo ft h ea l g o r i t h m ；a tt h es a m et i m e ，b e i n ga d d e dt h ew e i g h t t h e a l g o r i t h mc a nd i go u ta s s o c i a t i o nr u l e sw h i c hh i d d e ni nas m a l lp r o b a b i l i t ve v e n ta n d t h e s er u l e sa r ej u s tw h i c ht h eg e n e r a la l g o r i t h mc a ne a s i l yd i s c a r d e do rc a nn o td i g o u t 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 ，a p r i o r ia l g o r i t h m ，w e i g h t 独创性声明 本人卢明所节交的学位论文是本人在导师指导下进行的研究j ：作和取得的研究成果，除 了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得云洼王些太堂或其他教育机构的学位或证j i s 而使用过的材料。与我一同r ：作 的同忠对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名： 签字日期茹斫年z 月z s 日 学位论文版权使用授权书 本学位论文作者完全了解云洼王些盍堂有关保留、使用学t ：7 = 论文的规定。特授权 丞洼工些盔堂可以将学何论文的全部或部分内容编入有关数据库进行检索，井采圳影印、 缩印或扫描筲复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部fj 或机构送交论 文的复印f j l l 磁盘。 ( 保密的学位论文在解密后适圳本授权说明) 学位论文作者签名： 签字日期：加。7 年2 月西日 导师签名习骗 一 签字日期：2 哆年2 月巧日 学位论文的主要创新点 一、在新算法中提出了删除无效事务的思想，减少了每一次扫描所 涉及的事务数，一方面，在计算长度超过k 的项集支持度时，删除数 据库中长度小于和等于k 的，已经没有实际意义的事务；另一方面， 删除每次计算c k 支持度的过程中包含c 中的项集的个数小于k 的 事务。综合以上两方面提高了算法的效率。 二、在减少候选频繁项目集规模的思路下，基于通过计算项目集的 多段支持度而判断生成某些候选频繁项集是否有价值的修剪策略，达 到减少每次迭代所生成的候选频繁项目集中项目个数的目的，提高了 算法的效率。 三、引入了加权支持度度量指标，运用基于加权支持度的关联规则 对数据挖掘方法进行补充和完善，从而可以挖掘出a p r i o r i 算法挖掘 不出但却具有潜在价值的规则。 第一章绪论 第一章绪论 数据挖掘( d a t am i n i n g ) 技术是近几年国内外迅速发展起来的- - f - j 交叉学 科，涉及到数据库、统计学、人工智能与机器学习等多个领域。经过几十年的 研究，数据挖掘已经形成了清晰的概念和方法，并且j 下向更深入的方向发展。 本章主要介绍了论文研究的背景及意义，数据挖掘的国内外动态，给出本人的 主要工作以及全文的结构安排。 1 1 论文研究的背景及意义 在信息爆炸的时代，面对“人们被数据淹没，同时却仍然感到知识饥饿” 的挑战，数据挖掘( d a t am i n i n g ) 技术应运而生，并得以蓬勃发展，越来越显 示出其强大的生命力。数据挖掘是数据库研究中的一个很有应用价值的新领域， 融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术，知识 发现技术的相关研究为数据挖掘技术提供了坚实的理论基础。 数据挖掘就是从大量的数据中挖掘出有用的知识，因此数据挖掘算法的好 坏将直接影响到所发现知识的好坏。目自订大多数的研究都集中在数据挖掘的算 法和应用上。数据挖掘有很多研究方向，目前的研究主要集中在分类、聚类、 关联规则挖掘、序列模式发现、异常和趋势发现等方面。其中关联规则挖掘在 商业领域的成功应用，使它成为数据挖掘中最成熟、最重要、最活跃的研究内 容。关联的主要应用对象是事务数据库，侧重于确定数据中不同项目( 商品) 之间的联系，找出这样的数据信息对于确定市场策略是很有价值的“。决策者 可以根据这些信息来指导商品的分类设计、产品摆放、促销策略等，还可以应 用到附加邮递、目录设计、追加销售、仓储规划以及基于购买模式对客户进行 划分等方面。 关联规则挖掘算法主要有两大类，一类是有候选项集产生的算法，以 a g r a w a l 等人于1 9 9 3 年首先提出的a p r i o r i 算法为代表；一类是无候选项集产 生的算法，以h a n 等人提出的f p g r o w t h 算法为代表。无论是哪一类挖掘算法 其基本目的都是求满足用户指定最小支持度的项目集。而频繁项目集发现算法 的现存问题一是候选项目集的数量，二是事务数据库的扫描次数，三是随着网 络及数据库应用的发展，现有的算法还要考虑存储空间及时问等限制。本课题 在研究分析了a p r i o d 算法的基础上，针对频繁项目集合的发现算法瓶颈问题， 天津一l ：业人学硕士学位论文 提出了新的改进措施，提高发现频繁项目集的效率，并引入了加权支持度的概 念，使得能够挖掘出隐藏在小概率事件后的关联规则。 1 2 国内外研究现状及发展 数据挖掘技术是9 0 年代兴起的一项决策支持的新技术，通常将其视为数据 库中知识发现( k n o w l e d g ed i s e o v e r yi nd a t a b a s e ) 过程中最重要的一个步骤。 目前，数据挖掘技术及知识发现己成为计算机科学界的一大研究热点。美 国人工智能协会主办的k d d 国际研讨会及数掘库、人工智能、信息处理、知 识工程等领域的国际学术刊物都开辟了知识发现专刊，i e e e 的k n o w l e d g ea n d d a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊，代表了当时k d d 研究的最新成果和动态，较全面地论述了k d d 系统方法论、发现结果的评价、 k d d 系统设计的逻辑方法，集中讨论了数据库的动态性冗余、高噪声和不确定 性、空值等问题，k d d 系统与其它传统的机器学习、专家系统、人工神经网络、 数理统计分析系统的联系和区别，以及相应的基本对策。 不仅如此，在i n t e r n e t 上还有不少k i ) d 电子出版物，其中以半月刊 k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威嵋1 ，另一份在线周刊为d s * ( d s 代表决 策支持) ，1 9 9 7 年1 0 月7 只丌始出版。在网上，还有一个自由论坛d me m a i l c l u b ，人们通过电子邮件相互讨论d m k d 的热点问题。而领导整个潮流的 d m k d 丌发和研究中心则是设在美国e m d e n 的i b m 公司丌发部。 关联规则挖掘是数据挖掘的一个重要问题，当自订对关联规则的研究集中在 对挖掘算法的改进上，其中有许多研究热点，如在处理极大量数据时如何提高 算法的效率当数据迅速更新时如何改进算法数值型变量的处理问题等。 从i e e et r a n s a c t i o n so nk n o w l e d g ea n dd a t ae n g i n e e r i n g 以及a c m s i g m o di n t l c o n f m a n a g e m e n to fd a t a 近年来的文献中可以看出，大部分的有 关数据挖掘的文章主要集中于讨论如何提高关联规则挖掘的性能，这包括算法 的有效性、可伸缩性和并行处理，当然也有一些提出了新的挖掘技术。 关联规则挖掘首先由a g r a w a l ，i m i e l i n s k i 和s w a m i 提出。a p r i o r i 算法由 a g r a w a l 和s r i k a n t 提出。”，后来人们又在此基础上对a p r i o r i 算法进行了一系列 的改进，比较著名的包括使用h a s h 表提高关联规则挖掘效率，采用事务压缩技 术对所扫描的事务集进行压缩，采用划分技术对事务集进行分割，采用选样技 术来进行挖掘以及采用动态项集计数的方法等。 我国的数据挖掘研究开始于9 0 年代中期，到9 0 年代中后期，初步形成了 知识发现和数据挖掘的的基本框架。自9 0 年代中期一批研究成果( 学术论文) 2 第一章绪论 逐渐发表在计算机学报、计算机研究与发展、软件学报、人工智能与 模式识别等刊物上，研究重点也正在从发现方法转向系统应用，并且注重多 种发现策略和技术的集成，以及多种学科之间的相互渗透。但是基本上还是以 学术研究为主，实际应用上处于起步阶段。国内进行的大多数研究项目是由政 府资助进行的，如国家自然科学基金、8 6 3 计划、“九五”计划等。1 9 9 3 年国家 自然科学基金首次支持该领域的研究项目。国内从事数据挖掘研究的人员主要 在大学，也有部分在研究所或公司，所涉及的研究领域很多，一般集中于学习 算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方面的研究。如清华 大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中， 华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉 林大学等单位丌展了对关联规则丌采算法的优化和改造。 1 3 课题的主要工作及论文组织 1 3 1 本课题的主要工作 本文的研究工作源于数据挖掘研究和关联规则挖掘研究，目的是对数据库 知识发现进行深入的研究和探讨数据挖掘中关联规则算法的优化问题。主要做 了以下几个部分工作： 1 、对数掘挖掘技术做了深入研究，探讨其基本概念、体系结构和技术应用， 提出了未来的数据挖掘技术的发展方向。 2 、对关联规则的基本概念和性质给予了详细的描述，探讨关联规则挖掘的 基本过程，并介绍了关联规则的分类，提出了关联规则的研究方向。 3 、对关联规则挖掘算法进行了分析，详细阐述了经典的有候选频繁项目集 的a p r i o r i 算法与无侯选频繁项目集的f p g r o w t h 算法，包括其基本思想、基本 模型和算法，分析了该算法的特性和特点，同时介绍了其他学者对此算法的一 些改进。在此基础上，针对于频繁项目发现算法的瓶颈问题与关联规则生成中 存在的两大自订提假设，提出了一些新的、有效的解决措施，以提高算法效率。 具体改进措施可从以下几个方面着手： ( 1 ) 通过减少数掘库事务数目的方法，有效降低事务记录的个数和减少数 据库扫描次数，提高算法的效率。 ( 2 ) 通过减少候选频繁项目集中的数量，降低每次迭代所生成的频繁项目 集的个数，提高算法的效率。 ( 3 ) 通过引入加权支持度的理论，运用基于加权支持度的关联规则挖掘算 法对数据库进行挖掘，能够在一定程度上改善原有算法的不足。 3 天津i ：业人学硕十学位论文 4 、利用实例验证自己提出的新的挖掘算法。 1 3 2 本文的组织结构 本文的内容安排如下： 第一章是本文的绪论。在该章里介绍了本文研究的背景与意义，介绍了国 内外发展的动态以及本论文的主要工作和组织结构。 第二章介绍了数据挖掘的概念；数据挖掘的分类；数据挖掘的具体应用技 术和应用领域；最后讨论了数据挖掘未来的研究方向。 第三章介绍了关联规则的概念及其挖掘的过程，并概括介绍关联规则的分 类及未来的发展方向，并详细分析了关联规则的两个经典算法：a p r i o r i 算法及 f p - g r o w t h 算法。 第四章首先分析了a p r i o r i 算法的瓶颈问题以及几个经典的改进算法，并在 此基础上，从待扫描的数据库的规模以及候选频繁项目集方面，通过理论推导 和实验提出了一种新的改进算法，并证明改进算法提高了算法的效率。 第五章通过分析a p r i o r i 算法的“支持度一可信度”框架的不足，引入了加 权支持度的概念，提高了生成的关联规则的有效性。 第六章为全文的总结与展望。 4 第二章数据挖掘综述 第二章数据挖掘综述 随着数据库技术的成熟和数据应用的普及，人类积累的数据量f 在以指数速 度增长。进入上个世纪九十年代，伴随着因特网的出现和发展，以及随之而来的 企业内部网和企业外部网以及虚拟私有网的产生和应用，将整个世界联成一个小 小的地球村，人们可以跨越时空地在网上交换数据信息和协同工作。这样，展现 在人们面前的已不是局限于本部门，本单位和本行业的庞大数据库，而是浩瀚无 垠的信息海洋，数据洪水正向人们滚滚涌来。当数据量极度增长时，如果没有有 效的方法，由计算机及信息技术来提取有用信息和知识，人们也会感到面对信息 海洋像大海捞针一样束手无策。据估计，一个大型企业数据库中的数据，只有百 分之七得到很好的应用。这样，相对于“数据过剩 和“信息爆炸”，人们又感 到“信息贫乏”和“数据关在牢笼中”，奈斯伯特( j o h nn a i s b e t t ) 惊呼“人类正 被数据淹没，却饥渴于知识”。 面临浩瀚无际的数据，人们呼唤从数据汪洋中来一个去粗存精，去伪存真的 技术。从数据中发现知识( 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 ，k d d ) 及其核心技 术一数掘挖掘便应运而生了。数据挖掘这个术语首先出现于1 9 8 9 年8 月美国底 特律召丌的第1 1 届国际人工智能联合会议上，是- 1 7 交叉学科，涉及到机器学 习，模式识别，统计学，智能数据库，知识获取，数据可视化，高性能计算，专 家系统等各个领域。 2 1 数据挖掘的概念 2 1 1 数据挖掘的定义 数据挖掘包含丰富的内涵，是一个多学科交叉研究领域，可以从不同的角度 来看待数据挖掘的定义。 谈到数据挖掘，必须提到数据库中的知识发现( 1 d ) 。1 9 8 9 年8 月在美国 召丌的第十一届国际人工智能联合会议的专题讨论会上首次出现了k d d 这个术 语。k d d 的出现很好地满足了数掘处理的需要。关于k d d 与数据挖掘的关系， 有许多不同的看法，代表了不同的数据挖掘的数据含义。 1 、k d d 是数据挖掘的一个特例幢“。这种看法认为既然数据挖掘系统可以自 爱关系型数据库、事务数掘库、数据仓库、空白j 数据库、文本数据以及诸如w e b 5 天津：1 ：业人学硕十学位论文 等多种数据组织形式中挖掘知识，那么数据库中的知识发现知识数据挖掘的一个 方面。这时候早期比较流行的观点，在许多文献可以看到这种说法。因此，从这 个意义说，数据挖掘就是从数据库、数据仓库以及其它数据存储方式中挖掘有用 知识的过程。这种描述强调了数据挖掘在源数据形式上的多样性。 2 、数据挖掘是k d d 过程的一个步骤曙1 。其核心思想是：k d d 是从数据中 发现知识的全部过程，而数据挖掘是此过程中的一个特定的、关键的步骤。这种 观点认为虽然可以从数据仓库、w e b 等数据中挖掘知识，但是这些数据都是和 数据库技术相关的。因此，k d d 是一个更广义的范畴，它包括数据清洗、数据 集成、数据选择、数据转换、数掘挖掘、模式生成及评估等一系列步骤。把数据 挖掘作为k d d 的一个重要步骤看待，可以使我们更容易聚焦研究重点，有效解 决问题。目前，人们在数据挖掘算法的研究上，基本属于这样的范畴。 3 、数据挖掘与k d d 含义相同嵋1 。有些人认为，k d d 与数据挖掘只是叫法 不同，它们的含义基本相同。事实上，在许多的文献中，许多场合，如技术综述 等，这两个术语仍然不加以区分地使用。 从上面的描述中可以看出，数据挖掘概念可以在不同的技术层面上来理解， 但是其核心仍然是从数据中挖掘知识。尽管将数据挖掘视为数据库知识发现过程 的一个基本步骤更为科学，但是在产业界、媒体和数据库研究界，将数据挖掘直 接当作数据库中的知识发现更为流行。 2 1 2 数据挖掘的体系结构 一个典型的数据挖掘系统可以由以下几个主要成分组成： 1 、数据清理：消除噪声或不一致的数据； 2 、数据集成：多种数掘源可以组合在一起； 3 、数据过滤：从数据库中检索与分析任务相关的数据： 4 、数据挖掘：通过一系列步骤，使用智能方法提取数据模式； 5 、模式的评估：根据某种兴趣度量，识别表示知识的真正有趣的模式； 6 、图形用户界面：使用可视化和知识表现技术，向用户提供挖掘知识。 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或作为新 的知识存取放在知识库中。因此从数据挖掘的广义观点来看，数据挖掘是从存放 在数据库、数据仓库、或其它信息库中的大量数据中挖掘有趣知识的过程。基于 这种观点，典型的数据挖掘体系结构如图2 1 所示。 6 第二章数据挖掘综述 图2 1 典璎的数据挖掘体系结构 要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数 据库的简单检索查询调用，而且要对这些数据进行微观、宏观的统计、分析、综 合和推理，以指导实际问题的求解，企图发现事件问的相互关联，甚至利用已有 的数据对未来的活动进行预测。这样一来，就把人们对数据的应用，从低层次的 末端查询操作，提高到为各级经营决策者提供决策支持。这种需求驱动力，比数 据库查询更为强大。 2 1 3 数据挖掘的分类 数据挖掘是一个以数据库、人工智能、数理统计、可视化四大支柱技术为基 础，多学科交叉、渗透、融合形成的新的交叉学科，其研究内容十分广泛。目前 存在很多数据挖掘方法或算法，因此有必要对这些方法进行分门别类。描述或晚 7 大沣i ：业人学硕十学位论文 明一个算法涉及三个部分：输入、输出和处理过程。数据挖掘算法的输入是数据 库，算法的输出是要发现的知识或模式，算法的处理过程则涉及具体的搜索方法。 从算法的输入、输出和处理过程三个角度，我们可以确定这样几种分类标准：挖 掘对象、挖掘方法、挖掘任务。 根据挖掘对象分类，有如下若干种数掘库或数据源：关系数据库、面向对象 数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、 历史数据库，以及万维网( w e b ) 。 根掘挖掘方法分类，可耜分为：统计方法，机器学习方法，神经网络方法和 数据库方法。统计方法可细分为：回归分析，判别分析，聚类分析，探索性分析 等。机器学习可细分为：归纳学习方法，基于范例学习，遗传算法等。神经网络 方法可细分为：前向神经网络，自组织神经网络等。数据库方法主要是多维数据 分析或o l a p 方法，另外还有面向属性的归纳方法。 根据挖掘任务分类，数据挖掘主要发现以下五类知识： 1 、广义型知识：根掘数据的微观特性发现其表征的、带有普遍性的、较高 层次概念的、中观或宏观的知识。 2 、分类型知识：反映同类事务共同性质的特征型知识和不同事物之问差异 性特征知识。用于反映数据的汇聚模式或根据对象的属性区分其所属类别。 3 、关联型知识：反映一个事件和其它事件之问依赖或关联的知识，又称依 赖关系。这类知识可用于数据库中的归一化，查询优化等。 4 、预测型知识：通过时f b j 序列型数据，有历史的和当i 订的数掘去预测未来 的情况。它实际上是一种以时f h j 为关键属性的关联知识。 5 、偏差型知识：通过分析标准类以外的特例，数据聚类外的离群值，实际 观测值和系统预测值f u j 的显著差别，来对差异和极端特例进行描述。 2 2 数据挖掘的常用技术 数据挖掘的技术基础是人工智能( a l ，a r t i f i c i a li n t e l l i g e n c e ) 但又不仅限于此。 数据挖掘仅利用了人工智能中的部分己经成熟的算法和技术，其问题的复杂性和 难度都比人工智能有所降低。数掂挖掘领域中常用的技术方法m 。有： 1 、规则归纳( r u l e si n d u c t i o n ) ，即通过统计方法归纳、提取有价值的i f - t h e n 规则，例如关联规则挖掘等。 2 、决策树( d e c i s i o nt r e e s ) m 。，该方法用树形结构表示决策集合，由决策集 合通过对数据集的分类产生规则。决策树方法是利用信息熵寻找数据库中具有最 大信息量的字段，建立决策树的一个结点，再根据字段的不同取值建立树的分支， 8 第二章数据挖掘综述 在每个分支子集中，重复建立树的下层结点和分支，最终形成决策树。国际上最 有影响的决策树方法是由o u l u l a n 研制的i d 3 方法。典型的应用是对分类规贝怕勺 挖掘。 3 、神经网络( n e u r a ln e t w o r k s ) m 1 ，该方法模拟人脑神经网络的某些功能， 以完成分类、聚类、特征规则等多种数据挖掘任务。 4 、遗传算法( g e n e t i c a l g o r i t h m s l ，这是一种模拟生物进化过程的算法，最 早由h o l l a n d 于2 0 世纪7 0 年代提出。它是基于群体的、具有随机和定向搜索特 征的迭代过程，这些过程有基因组合、交叉、变异和自然选择四种典型操作。如 何把数据挖掘任务表达为一种搜索问题则是遗传算法的应用关键。 5 、模糊技术( f u z z yt e c h n o l o g y ) l s j 利用模糊集理论对实际问题进行模糊评 判、模糊决策、模糊模式识别和模糊聚类分析。模糊性是客观存在的，系统的复 杂性越高，模糊性越强。模糊集理论用隶属度来刻画模糊事物的办此亦彼性，而 李德毅教授在传统模糊集理论和概率统计的基础上提出了定性定量不确定性转 换模型一云模型1 ，并形成了云理论。云模型用期望值、熵和超熵表达定性概念， 将概念的模糊性和随机性结合在一起。为数据挖掘提供了概念和知识表达、定性 定量转换、概念的综合和分解等新方法。 6 、粗糙集理论( r o u g hs e tt h e o r y ) 【l ，用来描述知识的不精确性和不完全性。 粗糙集的一些理论和方法可用来从数据库中发现分类规则，其基本思想是将数据 库中的属性分为条件和结论属性，对数据库中的一条记录根据各个属性的不同属 性值分成相应的子集，然后基于条件属性划分的子集与结论属性划分的子集嵋j 的 上下近似关系生成判定规则。 粗糙集方法与传统的统计及模糊集方法不同的是它只依赖数据内部的知识， 用数据之问的关系表示知识的不确定性；而后者需要依赖先验知识对不确定性进 行定量描述，如统计分析中的先验概率、模糊集理论中的模糊度等。用粗糙集方 法处理不确定性问题的最大优点在于不需要数据的预先或附加的信息，而且容易 掌握。 7 、可视化方法( v i s u a l i z a t i o na p p r o a c h ) 。，即采用直观的图形方式将信息模 式、数据的关联或趋势呈现给决策者，决策者可以通过可视化技术交互地分析数 据关系。可视化技术是指用图形、图像的方式来显示知识，是数据挖掘中一种很 重要的技术。它拓宽了传统图表的功能，使用户对数据的剖析更清楚。通过可视 化技术可以把数据库中的多维数据变成多种图形，这对提示数据的状况、内在本 质及规律性起到了很大作用。 可视化数据挖掘可以分为数据可视化、数据挖掘结果可视化、数据挖掘过程 可视化和交互式数据可视化挖掘等。 9 天沣i ：业人学硕十学位论文 2 3 数据挖掘的任务 典型的数据挖掘任务有概念描述、关联分析、分类和预测、聚类分析、孤立 点分析、w e b 挖掘等。其中关联规则挖掘是目前最活跃、研究最深入的领域。 1 、概念描述 概念描述本质上就是对某类对象的内涵特征进行概括。一个概念常常是对一 个包含大量数据的数据集合总体情况的概述。如对一个商店所售电脑基本情况的 概述总结就会获得所售电脑基本情况的一个整体概念。对含有大量数据的数据集 合进行概述性的总结并获得简明、准确的描述，这中描述就称为概念描述。概念 描述分为特征性描述和区别性描述。前者描述某类对象的共同特征，后者描述不 同对象之间的区别。 2 、关联分析 从广义上讲，关联分析是数据挖掘的本质。既然数据挖掘的目的是发现潜在 数据背后的知识，那么这种知识一定是反映不同对象之间的关联。它集中在数据 库中对象之间关联及其程度的刻画。 关联知识反映一个事件和其它事件之间的依赖或关联。数据库中的数据一般 都存在着关联关系，也就是说，两个或多个变量的取值之间存在某种规律性。数 据库中的数据关联是现实世界中事物联系的表现。数据库作为一种结构化的数据 组织形式，利用其依附的数据模型可能刻画了数据问的关联。但是，数掘之问的 关联是复杂的、有时是隐含的。关联分析的目的就是要找出数据库中隐藏的关联 信息。这种关联有简单关联、时序关联、因果关联、数量关联等。这些关联并不 总是事先知道的，而是通过数据库中数据的关联分析获得的，因而对商业决策具 有新价值。 3 、分类和预测 分类是数据挖掘中的一个重要的目标和任务。目前的研究在商业上应用最 多。分类就是对数据的过滤、抽取、压缩以及概念提取等。分类的目的是学会一 个分类函数或分类模型( 也常常称作分类器) 。由于数据挖掘是从数据中挖掘知 识的过程，因此要构造这样一个分类器，这种类知识也必须来自于数据，即需要 一个训练样本数据作为输入。分类器的作用就是能够根据数据的属性将数据分派 到不同的组中，即：分析数据的各种属性，并找出数据的属性模型，确定哪些数 据属于哪些组。这样我们就可以利用该分类器来分析已有数据，并预测新数据属 于哪一个组，即数据对象的类标记，然而，在某些应用中，人们可能希望预测某 些空缺的或不知道的数据值，而不是类标记。当被预测的是数值数据时，通常称 之为预测。分类模式可以采用多种形式表示，如分类规则，判定数，数学公式或 1 0 第二章数据挖掘综述 神经网络。可以应用于分类知识挖掘的一些有代表性的技术有：决策数、贝叶斯 分类、神经网络分类、遗传算法、类比学习和案例学习，以及粗躁集和模糊集等 方法。 4 、聚类分析 一般把学习算法分为有导师( 或监督) 和无导师学习两种方式，主要区别是 有没有类信息作为指导。聚类是典型的无导师学习算法，一般用于自动分类。数 据挖掘的目标之一就是进行聚类分析。聚类就是将数据对象分组成多个类或簇， 同一个类中的对象具有较高的相似度，而不同类中的对象差异较大。一般情况下， 聚类分析不要求训练数据提供类标记，聚类可以用于产生这种标记。聚类按照某 个特定标准( 通常是某种距离) ，最终形成的每个类，在空间上都是一个稠密的 区域。所形成的每个类可以导出规则。聚类分析与分类和预测不同，前者总是在 类标识下寻求新元素属于哪个类；而后者通过对数据的分析比较生成新的类标 识。聚类分析生成的类标识( 可能以某种容易理解的形式展示给用户) 刻画类数 据所蕴涵的类知识。当然，数据挖掘中的分类和聚类技术都是在已有的技术基础 上发展起来的，它们互有交叉和补充。聚类技术主要是以统计方法、机器学习、 神经网络等方法为基础。常用的聚类算法有基于划分、层次、密度、网格和模型 的五大聚类算法。作为统计学的一个重要分支。聚类分析有很广泛的应用，包括 市场或客户分割、模式识别、生物学研究、空间数据分析、互联网文档分类及许 多其它方面。 5 、孤立点分析 一个数据库中的数据一般不可能都符合分类预测或聚类分析所获得的模型。 那些不符合大多数数据对象所构成的规律或模型的数据对象就被称为孤立点。在 数据正常类知识时，通常总是把它们作为噪音来处理。因此以i j i 许多数据挖掘方 法都是在正式进行数据挖掘之前就将这类孤立点数掘作为噪声或者意外而将其 排出在数据挖掘的分析处理范围之外。然而在一些应用场合中，如信用欺诈、入 侵检测等小概率发生的事件往往比较经常发生的事件更有挖掘价值。因此当人们 发现这些数据可以为某类应用提供有用信息时，就为数据挖掘提供了一个新的研 究课题，即孤立点分析。发现和检测孤立点的方法已经广泛讨论，主要有基于概 率统计、基于距离和基于偏差等检测技术的三类方法。 6 、w e b 挖掘 i n t e r n e t 不仅涉及新闻、广告、消费信息、金融管理、教育、政府、电子商 务和许多其它信息服务，而且w e b 还包含了丰富和动态的链接信息，以及w e b 页面的访问和使用信息，这为数据挖掘提供了丰富的资源。解决上述问题的一个 途径，就是将传统的数据挖掘技术和w e b 结合起来，进行w e b 挖掘。w e b 挖 天津i