（计算机应用技术专业论文）多值属性关联规则的研究与实现.pdf

论文题目： 专业： 硕士生： 指导教师： 多值属性关联规则的研究与实现 计算机应用技术 易季辉( 签名) 杨君锐( 签名) 摘要 在信息爆炸的时代，面对“人们被数据淹没，同时却仍然感到知识饥饿”的挑战， 数据挖掘技术应运而生，并得以蓬勃发展。关联规则挖掘是一个重要的研究领域。目前 对其的研究主要是集中在以支持信任理论为基础对布尔型数据进行挖掘，并且已取得 了一些研究成果，要从这些数据中挖掘潜在的规则，现有的布尔型关联规则方法就显得 力不从心了。如何划分区段是实现多值属性关联规则问题到布尔型关联规则问题转变的 关键。挖掘多值属性关联规则的关键步骤是把数值型属性所在的域分成多个区间。 在划分区段方面，现有的方法多是把数值属性所在的域划分成等宽的或等深的区 间，或者在一个( 或一组) 属性上使用聚类算法。虽然这些算法能很好的解决多值型的数 据挖掘问题，但是不能避免最小支持度和最小可信度冲突的问题，而且有可能错过一些 重要的规则。本文所提方法是，把一个交易作为一个a 维向量，并且在多个n 维向量上 对所有属性使用迭代自组织的数据分析算法( i s o d a t a ) 进行聚类。由于i s o d a t a 的试 探特性，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进 行分类。把聚类投影到数值型属性所在的区间形成可能重叠的区间，最后使用布尔型关 联规则挖掘算法来挖掘关联规则。该算法既考虑了交易之间的距离，又考虑了属性之间 的关系，而且能避免最小支持度和最小可信度之间的冲突。实验结果显示，该方法能有 效地挖掘多值属性关联规则，而且能够发现可能被以前的算法错过的重要的规则。 关键词：数据挖掘；关联规则：多值属性；频集；聚类 研究类型：理论研究 s u b j e c t ：t h er e s e a r c ha n di m p l e m e n t a t i o no fq u a n t i t a t i v ea s s o c i a t i o n r u l e s s p e c i a l t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e：y ij ih u i i n s t r u c t o r ：y a n gj u nr u i a b s t r a c t ( s i g n a t u r e ( s i g n a t ur e i nt h ee r ao fi n f o r m a t i o ne x p l o s i o n , f a c e dt ot h ec h a l l e n g e st h a t p e o p l ew e r ed r o w n e d d a t a , w h i l es t i l lf e e lk n o w l e d g eh u n g e r ，d a t am i n i n gt e c h n i q u e sh a v ee m e b e da n df l o u r i s h d a t am i n i n go fa s s o c i a t i o nr u l e sh a sb e c o m ea l li m p o r t a n tr e s e a r c ha r e a t h ec u r r e n tr e s e a r c h a l em o s t l yb a s e do nt h es u p p o r t - c o n f i d e n c et h e o r yo fb o o l e a nd a t am i n i n g ，a n dm a d es o m e r e s e a r c ha c l l i e v e m e n b ，b u tt h ee x i s t e dm e t h o d so fb o o l e a na s s o c i a t i o nr u l e sf r o mt h e s ed a t a m i n i n gp o t e n t i a lr u l e sa r ei n s u f f i c i e n t t h ec r i t i c a lo fq u a n t i t a t i v ea s s o c i a t i o nr u l e sp r o b l e mt o b o o l e a na s s o c i a t i o nr u l e sp r o b l e mc h a n g i n gi sb o wt od i v i d et h es e c t i o n s t h ec r i t i c a lp a r to f q u a n t i t a t i v ea s s o c i a t i o nr u l em i n i n gi st op a r t i t i o nt h ed o m a i n so fq u a n t i t a t i v ea t t r i b u t e si n t o i n t e r v a l s t h ee x i s t e dm e t h o d si nd i v i d et h es e c t i o n sd e a l t 、i t l lt h i sp r o b l e mb yd i v i d i n gt h e d o m a i n so fq u a n t i t a t i v ea t t r i b u t e si n t oe q u i - d e p t ho re q u i - w i d t hi n t e r v a l s ，o ru s i n gac l u s t e r i n g a l g o r i t h mo n as i n g l ea t t r i b u t e ( o ras e to fa t t r i b u t e s ) a l o n e a l t h o u g ht h e s ea l g o r i t h m sc a l lb e s a t i s f a c t o r i l yr e s o l v e dq u a n t i t a t i v ed a t am i n i n g , b u tc a nn o ta v o i dt h ec o n f l i c tb e t w e e nt h e m i n i m u ms u p p o r ta n dt h em i n i m u mc o n f i d e n c ep r o b l e m ，a n dr i s km i s s i n gs o m ei m p o r t a n t r u l e s i nt h i sp a p e r , t h ep r o p o s e dm e t h o di st h ef a c tt h a tat r a n s a c t i o na san - d i m e n s i o n a l v e c t o ra n da p p l yai t e r a t i v es e l f - o r g a n i z i n gd a t at e c h n i q u e sa l g o r i t h m ( i s o d a t a ) t oa l l a t t r i b u t e sc l u s t e r e d b e c a u s ee x p l o r eo fi s o d a t a ，a n dc a nb ec o m b i n e dh u m a n - c o m p u t e r i n t e r a c t i o na n du s e dt h ei n t e r m e d i a t er e s u l t so ft h ee x p e r i e n c eg a i n e dt oc l a s s i f yb e t t e r c l u s t e r i n ga l g o r i t h mt ot h ev e c t o r s ，t h e np r o j e c tt h ec l u s t e r si n t ot h ed o m a i n so ft h e q u a n t i t a t i v ea t t r i b u t e st of o r mo v e r l a p p e di n t e r v a l s f i n a l l yu s eac l a s s i c a lb o o l e a na l g o r i t h m t of m da s s o c i a t i o nr u l e s t h i sa p p r o a c ht a k e st h er e l a t i o n sa n dt h ed i s t a n c e sa m o n ga t t r i b u t e s i n t oa c c o 删毒a n dc a l lr e s o l v et h ec o n f l i c tb e t w e e nt h em i n i m u ms u p p o r tp r o b l e ma n dt h e m i n i m u mc o n f i d e n c ep r o b l e mb ya l l o w i n gi n t e r v a l st ob eo v e r l a p p e d e x p e r i m e n t a lr e s u l t s s h o wt h a t t h i sa p p r o a c hc a ne f f i c i e n t l yf r e dq u a n t i t a t i v ea s s o c i a t i o nr u l e s ，a n dc a nf i n d i m p o r t a n ta s s o c i a t i o nr u l e sw h i c hm a yb em i s s e db yt h ep r e v i o u sa l g o r i t h m 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 q u a n t i t a t i v ef r e q u e n ts e t c l u s t e r t h e s i s：t h e o r e t i c a lr e s e a r c h 姿料技大学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作 及其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不 包含其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科 技大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者躲昌霉弭日期彬、众7 。】 7 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期 间论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位 论文研究课题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名： 导毒罄 指导教师签名：t 刃秀铭 9 海多只7 b 1 绪论 1 1 选题背景及研究意义 1 1 1 选题背景 l 绪论 数据库应用已进入了成熟阶段，而且已渗透到了社会数据处理的各个层面。在商业 领域，数据库保存了各个公司多年积累的用户信息、交易记录以及生产数据；在科学研 究领域，数据库保存了大量的实验数据、观测数据和调查数据。在这些数据库中都蕴含 了大量的人们还没有发现的信息和知识。全球范围内数据库中存储信息量的急剧增大和 现有技术的局限性形成了一对矛盾，面对如此丰富的信息和数据却不能很好的利用，形 成了现今“数据监狱 和“数据爆炸但知识匮乏 的尴尬局面。因此在商业领域和科学 研究领域都迫切要求发展这样的技术，能够从如此海量的数据中抽取出模式，找出数据 变化的规律和数据之间的相互依存关系，使人们能够从宏观的高层次的角度来审视数 据，充分发掘数据的潜力，指导人们的行为，为决策和科学发现提供有力的支持。由于 数据量的不断扩张，现今数据库的应用已从原始的数据收集、存储以及对联机事物处理 的支持转向了大规模数据的重组、联机分析处理、数据仓库、知识发现( 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 ，k d d ) 、数据挖掘( d a t am i n i n g ，d m ) 等等更深层次利用数据的 阶段。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖 掘技术的应用领域十分广阔，它可以从关系数据库、数据仓库、文本和多媒体数据库、 事务数据库和互联网等各种数据源上设法获取诸如分类模型、聚类模型、回归模型、关 联模型和时间序列模型等多种知识模型。可以说，有数据积累的地方，就有数据挖掘技 术的用武之地。目前，数据挖掘技术在货篮数据分析、金融风险预测、产品质量分析、 电信、分子生物学、基因工程研究、站点访问模式发现以及信息搜索等领域得到了广泛 的应用，数据挖掘技术被认为是数据库和人工智能领域中研究、开发和应用最活跃的分 支之一，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可 视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领 域，形成了新的研究热点。 k d d 一词是在1 9 8 9 年8 月于美国底特律市召开的第一届k d d 国际学术会议上正 式形成的【，国际k d d 学术会议起初每两年召开一次，1 9 9 3 年后才每年召开一次。在 几次国际k d d 学术会议上讨论的问题有：定性知识和定量知识的发现；数据汇总； 西安科技大学硕士学位论文 知识发现方法；数据依赖关系的发现和分析；发现过程中知识的应用；继承的 交互式的知识发现系统；知识发现的应用。 数据挖掘的主要目的是从大量的数据源中采用和发展有关的理论、方法和工具来提 取有用的和使人感兴趣的知识和模式。数据挖掘是从实际的海量数据源中发现知识。由 于数据的完整性、一致性和正确性难以保证，因此数据挖掘算法的效率、有效性和扩充 性就非常关键。数据挖掘与传统的数据库查询是不同的，它们的区别主要表现在：前者 是主动的、不生成严格的结果集和不同层次的挖掘，而后者则是被动的、只对字段进行 严格的查询【2 】。归纳起来，数据挖掘有如下特点： ( 1 ) 处理的数据规模十分庞大； ( 2 ) 由于用户不能形成精确的查询要求，因此需要靠数据挖掘技术来寻找其可能感 兴趣的东西； ( 3 ) 数据挖掘对数据的迅速变化作出快速响应，以提供决策支持信息； ( 4 ) 数据挖掘既要发现潜在规则，还要管理和维护规则，随着新数据的不断加入， 规则需要随着新数据更新； ( 5 ) 数据挖掘中规则的发现基于统计规律，发现的规则不必适合于所有数据，而且 当达到某一阈值时，便认为有此规则。 数据挖掘是当前人工智能、数据库和信息决策研究的新领域，其可应用于决策支持、 市场分析、经济预测等，引起了国内外学术界的和工商界的广泛关注。在数据挖掘中， 关联规贝, u ( a s s o c i a t i o nr u l e s ) 是比较重要的一种模式，也是知识模式最活跃的一个分支之 一。关联规则是数据挖掘的重要研究方向，侧重于确定数据库中不同领域间的联系【3 l 。 关联规则就是从大量的数量中挖掘出有价值描述数据项之间相互联系的有关知识。 随着收集和存储在数据库中的数据规模越来越大，人们对从这些数据中挖掘相应的关联 知识越来越有兴趣。例如从大量的商业交易记录中发现有价值的关联知识就可帮助进行 商品目录的设计、交叉营销或帮助进行其它有关的商业决策。 关联规则挖掘的一个典型例子是购物篮分析。条码技术的发展使得零售机构能够收 集和存储大量的销售记录，这些销售记录称为篮子数据( b a s k e td a t a ) 。记录顾客在一次购 物中购买的商品信息的篮子数据称为事务( t r a n s a c t i o n ) 。在现代化的超级市场中，售货员 可以用条码扫描器方便而准确的记录所有的事务。许多组织已经收集并存储了大量的篮 子数据，这些数据是他们从事营销活动和商业决策的重要基础和依据。但是现有的数据 库管理系统并没有提供足够的工具从这些数据中发现有价值的信息和知识。 1 1 2 研究意义 关联规则挖掘是由r a k e s ha g r a w a l 等人于1 9 9 3 年首次提出的一个重要的数据挖掘 研究课题【4 j o 自关联规则诞生以来，国内外业界人士对其进行了大量研究，并广泛地应 2 1 绪论 用于多个领域，如商业营销、仓储规划、网络故障分析、商品广告邮寄分析、目录设计、 股票交易分析、电子通信、医疗预测等领域。 目前，全世界拥有的巨大数据资源，需要将这些数据资源转换为信息和知识资源。 数据挖掘的出现迎合这种需求。数据挖掘经过二十几年的迅速发展，目前已经存在多种 挖掘技术，如关联规则、人工神经网络、决策树、遗传算法、最近邻技术等。其中，关 联规则的提取是数据挖掘技术研究的一个重要课题。由于其比较符合人类认知世界的思 维模式，所以关联规则的挖掘被广泛应用于各行各业。但由于数据挖掘不是面向任务( 或 问题) 的，所以导致其不易被掌握，且容易偏离了数据挖掘的目标。目前的数据挖掘系 统或工具很少能真正让用户参与到挖掘过程中，将相关领域的知识融入数据挖掘系统。 随着这些问题的不断解决，将使数据挖掘技术的研究更加深入。 今天，数据挖掘的研究正方兴未艾，焦点将会集中在研究专门用于知识发现的数据 挖掘语言，寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理解， 也便于在知识发现过程的人机交互；目前加强该方面的研究，如何对海量的数据库进行 预处理，数据挖掘过程可视化，交互性和提高挖掘的效率，数据挖掘将具有更为普遍的 意义。 目前对关联规则研究的另一个表现是大都集中在布尔型关联规则方面，即是在属性 值为布尔量的关系表中寻找属性值为“1 ”属性之间的关系，对这类问题的研究是不论 项目属性如何一律采用统一的最小支持度和最小信任度阈值来发现知识，而没有考虑交 易中的数量问题，对这类问题的算法卜7 j 能较好地分析非稠密数据，如超市数据。但是 这样由于仅仅关注项目或项目集的出现频率，而屏蔽掉了各项目自身固有的属性特征， 使模型与实际运用之间产生差异。现实世界中有许多数据是稠密的，如人口统计数据， 更一般的如关系型数据。由于它们具有：某些属性出现频率相当高( 如性别属性) ；某些 属性间有很强的关联性；个别属性出现在每一个事务中等现象，这时再采用传统的挖掘 算法卜7 l 来发现知识就无能为力了，因此必须采用新的挖掘方法多值属性关联规则 挖掘【引。 1 2 国内外研究动态及发展趋势 1 2 1 国内研究现状 近年来，国内的许多科研单位和高等院校竞相开展数据挖掘的基础理论及其应用研 究，并取得了较丰硕的研究成果。我国数据挖掘的研究已经初具规模。 陆建江、宋自林等8 1 采用f c m 算法来划分数量型属性，并进一步讨论了模糊关联 规则；刘常昱、李德毅等9 】利用正态云来软化划分边界，并提出正态云关联规则的概念， 而陆建江、钱祖平【10 】又对此进行了改进；张朝晖、陆玉昌u 提出了一种聚类算法，根据 3 西安科技大学硕士学位论文 数据库中数据的分布情况决定数量型属性值的区段划分，并将相关的区段进行合并，然 后转化为布尔型关联规则进行挖掘等。 1 2 2 国外研究现状 世界上对数据挖掘的正式研究始于1 9 8 9 年8 月举行的第一届k d d 国际学术会议， 数据库中的知识发现k d d 在该次会议上被提出。到目前为止，k d d 国际研讨会的研究 重点逐渐从发现方法转向系统应用，并注重多种发现策略和技术的集成，以及多学科之 间的相互渗透。与国内相比，国外对数据挖掘的研究较早，已形成整体力量。 1 9 9 6 年，s r i k a n t 和a g r a w a l 首先提出多值属性关联规则挖掘问题【1 2 1 ，并用基于支 持度的部分k 度完全方法( p a r t i a lk - c o m p l e t e n e s s ) 对连续属性区域进行分割，将多值属性 关联规则的挖掘转化为布尔型关联规则的挖掘；k u o kcm 、f u a 等【”】采用模糊c 均值 算法来划分数量型属性，提出了数量型属性模糊关联规则的概念，并通过组合语言值来 讨论语言值关联规则的挖掘问题。 1 2 3 数据挖掘研究的发展趋势 数据挖掘是一个新兴的研究领域，许多问题还有待于研究，目前的研究方向主要包 括以下几个方面。 ( 1 ) 算法效率和可伸缩性 数据挖掘通常是直接面向海量数据库，因此，数据挖掘系统必须能有效地处理海量 数据，其算法必须是高效和可伸缩的。 ( 2 ) 处理不同类型的数据和数据源 目前数据挖掘系统处理的数据库大多是关系数据库。随着数据库应用范围的日益扩 大和规模、功能的日益完善【1 4 1 ，数据库中将包含大量复杂的数据类型，甚至出现新的数 据库模型，因此，保证数据挖掘系统能有效地处理此类数据库中的数据是至关重要的。 ( 3 ) 数据挖掘系统的交互性 数据挖掘中操作者的适当参与能加速数据挖掘过程。一方面，交互界面为用户表达 要求和策略提供方便；另一方面，交互界面又把生成的结果传递给用户，由于生成的结 果可以多种多样，因此，准确而直观地描述挖掘结果和友好而高效的用户界面一直是研 究的重要课题。 ， ( 4 ) w e b 挖掘 由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来越重要的角色，因此， w e b 挖掘是数据挖掘中一个重要的研究领域。 ( 5 ) 数据挖掘中的隐私保护与信息安全【1 扣1 7 1 数据挖掘能从不同的角度、不同的抽象层上看待数据，这将潜在地影响数据的私有 4 1 绪论 性和安全性。随着计算机网络的日益普及，研究数据挖掘可能导致的非法数据入侵是实 际应用中亟待解决的问题之一。 ( 6 ) 探索新的应用领域： 早期的数据挖掘主要集中在帮助企业提高竞争能力。随着数据挖掘的日益普及，它 的应用领域也在不断扩大，由于通用数据挖掘系统在处理特定应用问题时有其局限性， 因此，目前的一种趋势是开发针对特定应用的数据挖掘系统。 ( 7 ) 数据挖掘语言的标准化 标准的数据挖掘语言或有关方面的标准化工作将有助于数据挖掘系统的研究和开 发，有利于用户学习和实用数据挖掘系统。 ( 8 ) 可视化数据挖掘 它是从大量数据中发现知识的有效途经。系统研究和开发可视化数据挖掘技术有助 于推进数据挖掘作为数据分析的基本工具。 1 3 论文的主要内容和结构 本论文分为六章，其内容和结构如下： 第l 章主要介绍选题背景及数据挖掘国内外的发展趋势等内容； 第2 章对数据挖掘的理论概述、功能、模式、研究与应用等内容进行了介绍； 第3 章对关联规则的概念及a p r i o r i 算法的描述进行了较全面和深入的介绍和分析； 第4 章对多值属性关联规则的相关内容与m a q a 算法及f c m 算法进行介绍和研究； 第5 章对i s o d a t a 算法的进行了介绍和分析，并就如何解决多值属性关联规则挖 掘提出了一个新的解决方案并通过实验验证； 第6 章对全文进行了总结，并提出了下一步待研究的内容。 1 4 本章小结 本章是论文的绪论部分，介绍了课题研究的背景和意义，并对国内外该领域的研究 情况进行简单介绍，说明了文章内容的组织结构。 5 西安科技大学硕士学位论文 2 1 数据挖掘与知识发现 2 数据挖掘综述 数据挖掘的理论研究可分为宏观研究和微观研究两方面，其中宏观研究主要是从总 体上进行把握，如数据挖掘的必要性、内涵和理论综述等；微观研究主要包括：数据挖 掘的任务、方法、技术、语言和系统研究等。 从宏观研究方面数据挖掘的含义可以理解为： ( 1 ) 公认的是w j f r a w l e y 等给出的定义【1 8 j ：数据挖掘，就是从大型数据库的数据中 提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在有用的信息，提取的知 识可表示为概念( c o n c e p t s ) 、规贝j j ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。此 定义把数据挖掘的对象仅定义为数据库。 ( 2 ) 有人认为，广义地讲，数据挖掘是在一些事实或观察的集合中寻找模式的决策支 持过程【1 9 1 。也就是说，数据挖掘的对象不仅是数据库，也可以是文件系统，或其他任何 数据集合。 数据挖掘与数据库知识发现( k d d ) 的区别和联系：长期以来，数据挖掘和数据库知 识发现两个术语的范畴和使用界限一直不很清晰，直到k d d 9 6 国际会议上，f a y y a d 、 p i a t e t s k ys h a p i r o 和s m y t h 就这两个术语的关系作了如下阐述1 2 0 1 ：k d d 是指从数据库中 发现知识的全部过程，d m 则是全部过程中的一个特定步骤。 目前数据挖掘主要有以下几种方法。 ( 1 ) 统计学方法 统计学方法通过回归分析、时间序列、判别分析、因子分析和聚类分析等统计分析 方法，完成从抽样分析中提取未知的数学模型。数据挖掘主要是对高级多元统计方法应 用的拓展和深化。统计学方法是数据挖掘研究的重要途径之一。 ( 2 ) 关联规则挖掘 挖掘关联规则就是发现存在于大数据集中的关联性或相关性。用于产生关联规则的 方法有i p r i o r i 方法等。肖利、王能斌等【2 l 】提出了挖掘转移规则，用以弥补关联规则的 不足，使得在特定的情况下，具有一定的普遍性和实用价值，可以为决策者提供一个新 的预测模型。糜元根【2 2 】认为，云模型可以用于采掘关联规则。云模型还是一种新模型， 其适用范围较窄，有待进一步的深入研究。 ( 3 ) 决策树方法 用树枝状展现训练集中资料受各变量的影响情形之预测模型，根据对目标变量产生 之效用的不同而建构分类的规则，在问题维数高的领域可以得到很好的分类结果。常用 6 2 数据挖掘综述 jilni l lh 暑宣暑宣暑；i i 暑i 置i i 宣置宣葺暑暑暑；暑i 暑i i i i i i 暑i 置鼍宣 的方法有c a r t ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e s ) 2 3 1 及c h a i d ( c h is q u a r ea u t o m a t i c i n t e r a c t i o nd e t e c t o r ) t 2 4 1 。 ( 4 ) 神经网络方法 模拟人脑神经元方法，以m p 模型和h e b b 学习规则为基础，建立了三大类神经网 络模型：前馈式、反馈式和自组织网络，从而完成分类、聚类、特征挖掘等多种数据挖 掘任务。 ( 5 ) 多层次数据汇总归纳 将一个数据集合归纳成更高概念层次信息的数据挖掘技术被称为数据汇总。概念汇 总是将数据库中的相关数据由低概念层抽象到高概念层，主要有数据立方体和面向对象 的归纳两种方法。 ( 6 ) 覆盖正例排斥反例方法 利用覆盖所有正例和排斥所有反例的思想来寻找规则，比较典型的方法有m i c h a l s k i 等人的a q l 5 方法【2 5 1 、洪家荣改进的a e 5 方法【2 6 1 等。 ( 7 ) 可视化技术 可视化技术采用直观的图形方式将信息模式和数据的关联成趋势呈现给用户，以便 用户交互地分析数据关系。 ( 8 ) 粗集方法 粗集作为一种数据分析的方法首先由p a w l a k 提出。它能从不精确的、模糊的、不 确定的数据中发现知识伫7 1 。粗集理论在知识获取和数据挖掘中得到了广泛的应用，它为 数据挖掘提供了理论基础。杨辉和王烷尘【2 8 】提出的用于数据挖掘的粗集产生多重知识库 的新方法，改善了分类的精确性，提高了学习过程的有效性。 ( 9 ) 遗传算法 遗传算法【2 9 】是一种仿生全局优化方法。它模拟生命进化机制，将较劣的初始解通过 一组遗传算子，在求解空间按一定的随机规则迭代搜索，直到求得问题的最优解，但其 算法较复杂，还有收敛于局部极小的过早收敛等难题未得到彻底解决。 ( 1 0 ) 证据理论 证据理论作为一种不确定推理方法，在数据挖掘中的应用不多见。a n a n d 等【3 0 1 提出 基于证据理论( e v i d e n c et h e o r y ) 的数据挖掘一般框架e d m ，和其他方法结合使用，效果 更佳 7 西安科技大学硕士学位论文 2 2 数据挖掘过程 图2 1 数据挖掘一般过程 数据挖掘一般过程如图2 1 所示。数据挖掘的一般过程包括五个步骤。( 1 ) 预处理数 据：收集和净化来自数据源的信息，并加以存储，一般是将其存放在数据仓库中。( 2 ) 模型搜索：利用数据挖掘工具在数据中查找模型，这个搜索过程可以由系统自动执行， 从底向上搜索原始事实以发现它们之间的某种联系，也可以加入用户交互过程，由分析 人员主动发问，从上到下地寻找以验证假定的正确性。对于一个问题的搜索过程可能用 到许多工具。例如，神经网络、基于规则的系统、基于实例的推理、机器学习、统计方 法等。( 3 ) 评价输出结果：一般地说，数据挖掘的搜索过程需要反复多次，因为当分析人 员评价输出结果后，他们可能会形成一些新的问题或要求对某一方面做更精细的查询。 ( 4 ) 生成最后的结果报告。( 5 ) 解释结果报告。对结果进行解释，依据此结果采取相应的 商业措施，这是一个人工过程。 数据挖掘是一项从大量的记录数据中提取有价值的、人们感兴趣的知识，这些知识 是隐含的、事先未知的有用信息，提取的知识一般可表示为概念( c o n c e p t s ) 、规贝j j ( r u l e s ) 、 规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。 人们把大型数据库或数据仓库看作是形成知识的源泉。原始数据可以是结构化的数 据，如关系数据库中的数据；也可以是半结构化的数据，如文本、图形和图像数据；甚 至是分布在网络上的异构型数据。发现知识的方法：可以是数学的，也可以是非数学的； 可以是演绎的，也可以是归纳的。发现的知识可被用于信息管理、查询优化、决策支持 和过程控制等，也可用于数据自身的维护。因而，有许多人把数据挖掘视为数据库中的 知识发现的同义词。知识发现是从数据中发现有用知识的整个过程。知识发现过程如下： ( 1 ) 数据清理去除噪声或不一致数据； ( 2 ) 数据集成多种数据源可以组合在一起； 8 2 数据挖掘综述 ( 3 ) 数据选择从数据库中检索与分析任务相关数据； ( 4 ) 数据变换数据变换或统一城市和挖掘的形式，如汇总或聚集操作； ( 5 ) 数据挖掘基本步骤，使用智能方法提取数据模式： ( 6 ) 模式评估根据某种兴趣度度量，识别表示知识的真正有趣的知识； ( 7 ) 知识表示使用可视化和知识表示技术，向用户提供挖掘的知识。 数据挖掘是知识发现最核心的部分。数据挖掘与传统分析的区别在于：数据挖掘使 用基于发现的方法；运用模式匹配；运用了数据之间的重要联系。因此，数据挖掘是一 门以数据库、人工智能、数理统计、可视化四大支柱技术为基础，多学科交叉、渗透、 融合形成的交叉学科。 2 3 数据挖掘的功能及模式 数据挖掘需指定数据挖掘任务中要寻找的模式类型。数据挖掘的任务一般可以分两 类：描述和预测。描述性挖掘任务是用于刻画数据库中数据的一般特性；预测性挖掘任 务是指在当前数据上进行推断，以进行预测。在某些情况下，用户并不知道挖掘出什么 样的模式才是有趣的，因此同时搜索多种不同的模式，再从搜索的结果中选择自己认为 感兴趣的模式。这就要求数据挖掘系统能够挖掘出多种类型的模式，以适应不同的需求 或应用。另外，数据挖掘系统应当能够发现不同抽象层面的模式，应当允许用户给出提 示，指导有趣模式的搜索。 2 3 1 数据挖掘的功能 根据数据挖掘任务是不同的，数据挖掘的功能可分为：概念类描述、关联分析、分 类和预测、聚类分析、孤立点分析、演变分析、偏差检测( 异常分析) 、最近邻技术、特 征规则分析等。 ( 1 ) 概念类描述 数据通过与类或概念相关联，用汇总的、简洁的、精确的方式描述概念和类，称为 概念类描述。这种描述可以通过以下方法得到： 数据特征化( d a t ac h a r a c t e r i z a t i o n ) ：目标类数据的一般特征或特性的汇总。用户指定 类的数据通过数据库查询收集。 数据区分( d a t ad i s c r i m i n a t i o n ) ：将目标类对象的一般特征与一个或多个对比类对象 的一般特征比较；目标类和对比类由用户指定，而对应的数据通过数据库查询检索。数 据特征化和比较，同时应用数据特征化和数据区分来进行概念类的描述。 ( 2 ) 关联分析 关联分析指若两个或多个数据项的取值重复出现且概率很高时，它就存在着某种关 联，可以建立起这些数据项的关联规则。关联分析发现关联规则，这些规则展示了给定 9 西安科技大学硕士学位论文 数据集中数据项之间的潜在的联系。关联分析广泛应用于购物篮或事务数据分析中。 ( 3 ) 分类和预测 分类找出描述并区分数据类或概念的模型，以便能够使用模型预测类、标记未知的 对象类。分类是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的内 涵描述，一般用规则或决策树模式表示【1 6 】。在数据挖掘中，分类算法的研究成果较多， 常用的数据分类算法有c a r t 、c 4 5 、i d 3 、s l i q 、k n n 、g ak n n 等。 预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性值或值 区间。分类和预测的区别在于：分类是预测分类标号( 或离散值) ；预测是建立连续值函 数模型。预测是利用历史数据找出变化规律，即建立模型，并用此模型来预测未来数据 的种类特征等。 ( 4 ) 聚类分析 聚类是一种常见的描述工作，搜索并识别一个有限的种类( c a t e g o r i e s ) 集合或簇 c l u s t e r s ) 的集合，从而描述数据，即识别出一组聚类规则、将数据分成若干类。这些类 可能相互排斥而且是无穷举的( 无遗漏的) ，或包含了更丰富的表达形式，如层次的种类 或重叠的种类。经过分类后的数据，在各类之间相似程度很小，而在某一类内部，其数 据的相似性则很大。数据聚类是将物理的或抽象的对象分成几个群体，具有群内相似群 间差异的特点。数据聚类常见的算法有p a m 、c l a r a 、c l a r a n s 、b i r c h 等。 ( 5 ) 孤立点分析 数据库中可能包含某些数据库对象，这些对象的行为或模型与一般数据不一致。这 些数据对象称为孤立点。这孤立点可能是度量或执行错误所导致的，也可能是固有的数 据变异性的结果。许多数据挖掘算法试图使孤立点的影响最小化或排除它们。然而，在 一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那些更加有趣。因为孤立点本 身可能是非常重要的。 ( 6 ) 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。它包括时间 序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 ( 7 ) 偏差检测( 异常分析) 数据库中的数据常有一些异常记录，从数据库中检测出这些偏差很有意义。偏差检 测的基本方法是寻找观测结果与参照之间的差别。 ( 8 ) 最近邻技术 这种技术通过k 个最与之相近的历史记录的组合来辨别新的记录，有时也称这种技 术为k 最近邻方法。 ( 9 ) 特征规则分析 从与学习任务相关的一组数据中提取出关于这些数据的特征式，用以表达该数据集 1 0 2 数据挖掘综述 的总体特征。 2 3 2 数据挖掘的模式 数据挖掘发现的知识模式有多种不同的类型，常见的模式有：分类模式、聚类模式、 关联模式、序列模式等。 ( 1 ) 分类模式 分类模式是反映同类事物间的共性以及异类事物间差异的特征知识。它可以提取数 据类的特征模型，进而预测事物发展的趋势。分类模式往往表现为一棵分类树，从树根 开始搜索，沿着满足条件的分支走，走到树叶就能确定类别。己经有许多数据分类的方 法，如决策树、统计方法、神经网络等。其中，决策树方法由于具有速度快、精度高、 生成模式简单等优点而广泛应用。 ( 2 ) 聚类模式 聚类模式与分类模式不同，它在事先不知道分组及如何分组的情况下，根据一定的 基本规则，把数据划分到不同的组中，组之间的差别应尽可能大，而在组内的差别则应 尽可能小。聚类模式的挖掘可以采用统计方法、机器学习方法等。 ( 3 ) 关联模式 关联模式也称为关联规则，是数据挖掘的一个重要课题。关联规则广泛应用于购物 篮或者事务数据的分析当中。从大量超市购物事务记录中发现有趣的关联关系，可以指 导商家建立有利的市场经营策略，如商品的进货数量比例、摆放顺序以及促销的时机等。 例如通过对顾客的购物情况分析，可以决定将牛奶和面包放在一起销售，以同时增加两 种商品的营业额。 ( 4 ) 序列模式 序列模式与关联模式相仿，主要把数据之间的关联性与时间联系起来。序列模式不 仅需要考虑事件是否发生，而且需要考虑事件发生的时间因素。对序列模式的挖掘，有 一些参数的取值，将严重影响挖掘效果。这包括持续时间、事件重叠窗口以及被发现模 式中的时间间隔。 2 4 数据挖掘的研究热点与应用领域 2 4 1 数据挖掘的研究热点 就目前来看，将来的几个热点包括空间数据、多媒体数据、时序数据、文本数据、 w e b 数据挖掘和生物信息或基因的数据挖掘。下面就这几个方面加以简单介绍。 ( 1 ) 空间数据挖掘 空间数据挖掘是指对空间数据库中非显式存在的知识、空间关系或其他有意义的模 西安科技大学硕士学位论文 式等的提取。空间数据库存储了大量与空间有关的数据，它与关系数据库的结构有着显 著的区别，空间数据库包含了拓扑或距离信息，通常按复杂的、多维的空间索引结构组 织数据。空间数据挖掘在地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，g i s ) 、图像数据 库探测、环境研究等许多空间领域有着广泛的应用。 ( 2 ) 多媒体数据挖掘 以图像数据挖掘为例，包括相似性搜索、分类和预测分析以及关联挖掘。音频和视 频的挖掘可以跟数据挖掘的可视化相结合，用音频数据来代替可视化挖掘是一个新颖的 选择。 ( 3 ) 时序数据和序列数据的挖掘 包括趋势分析、时序分析中的相似搜索、序列模式挖掘和周期模式挖掘。 ( 4 ) 文本数据库挖掘 现实世界中可获取的大部分信息都是存储在文本数据库中的，文档数据的存储格式 是呈半结构化。朱锡钧，陆汝占认为目前对半结构化数据进行数据挖掘采用的途径是： 先将u s d 准结构化，再转换成结构化数据，套用现有数据挖掘方法进行数据挖掘。另 外，可以利用半结构化数据自己独特的数据模型、查询语言和存储管理工具来实现挖掘。 国内的研究者也对半结构化数据模型进行了许多研究。 ( 5 ) w e b 数据挖掘 随着因特网的高速发展，万维网的规模己相当庞大，万维网可能是目前最大的数据 库，如何将数据挖掘技术应用于万维网上的数据挖掘，即w e b 挖掘，是一项极具挑战 性的任务。 w r e b 挖掘有很多应用。其中一种应用是针对性广告。“瞄准”( t a r g e t i n g ) 技术用于引 导商业销售或者向最有收益部分群体发送广告。为了使收益最大化，把广告发送给( 而 且只给) 那些最有可能购买的潜在顾客，这就节省了广告的费用。目前数据挖掘技术都 可以用于对指定观众进行针对性广告，这样广告费用降低但不会影响效果。 ( 6 ) 生物信息或基因的数据挖掘 生物信息或基因数据挖掘则完全属于一个新领域，对它的研究对于人类自身有着重 要的意义。例如，基因的组合千变万化，患有某种疾病的人的基因和正常人的基因到底 差别多大? 能否找出其中不同的地方，进而对其不同之处加以改变，使之成为正常基 因? 这都需要数据挖掘技术的支持。 对于生物信息或基因的数据挖掘和通常的数据挖掘相比，无论在数据的复杂程度、 数据量、分析和建立模型的算法而言，都要复杂得多。从分析算法上讲，更需要一些新 的和好的算法。现在很多厂商正在致力于这方面的研究，但就技术和软件而言，还远没 有达到成熟的地步。 1 2 2 数据挖掘综述 2 4 2 数据挖掘的应用领域 数据挖掘工具的出现，已经让人们意识到数据挖掘技术带来的有利的应用前景。其 应用主要体现在以下几个方面。 ( 1 ) 科学研究领域 从科学研究方法学的角度看，随着先进的科学数据收集工具的使用，如遥感遥测、 天文观测、d n a 分子技术等，数据量非常大，传统的数据分析工具己经无能为力，因 此迫切需要一种强大的智能性自动数据分析工具。这种需求推动了数据挖掘技术在科学 研究领域的应用发展，并取得了一些重要的成果。例如，在d n a 数据分析方面，人类 有约1 0 0 0 0 0 个基因，一个基因通常由上百个核昔酸按一定的顺序组织而成。核昔酸不 同的次序形成不同的基因，几乎是不计其数的。要从中找出导致各种疾病的特定基因序 列模式就非数据挖掘技术莫属。 另外，数据挖掘在社会科学领域的应用前景也被越来越多的人所认识到。从大量的 历史数据中