（计算机应用技术专业论文）数据挖掘中关联规则的研究及应用(1).pdf

中文摘要 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提 取隐合在其中的、人们事先不知道的、但又是潜在有剧的信息和知识的过程， 其主要目标是从大型的数据库中挖掘出对用户有价值的模式。在事务数据库中 挖掘关联规则是数据挖掘领域中一个非常重要的研究课题。 在关联规则挖掘过程中存在两个问题：一是产生大项目集；二是产生强关 联规则。埘于这两个问题，算法的复杂性是瓶颈，凼为频繁集的数f 1 和项目的 数目成指数增长，所以导致在面对大规模的数据库时，整个算法的耗时巨大， 从而最终导致挖掘算法在实际工程中的应用效果较差。 本文提出一种从大型数据库中挖掘关联规则的改进算法。该算法以经典的 a p r i o r i 算法为基础，在分析研究已有各种优化算法的基础上，提出了数据划 分的方法，分两个阶段执行。第一阶段，扫描整个数据库，将其分成若干互不 相交的予块，然后逐次调入内存，根据支持度在每个子块上的分配，对每个子 块应用a p r i o r i 算法，以产生局部频繁项集，最后将每个子块的频繁项集合并 作为第_ 阶段所用的全局候选项集；第二阶段，着眼于全局频繁项集的搜索。 根据每个伞局频繁项目集必在某个子块卜是频繁的这一性质，对第一阶段产生 的全局候选项集应用a p r i o f i 算法，由此产生全局频繁项集。整个过程只需扫 描数据库两次，大大减少了i o 操作时间，减少了产生的候选项集的数量。理 论分析表明，改进后的a p r i o r i 算法的应用效率高，用程序实现了改进前后的 算法，实验结果也表明改进后的算法效率更高，而且随着数据库规模的扩大， 效率提高更加明显。 本文还将研究成果应用到医疗信息系统，构建了一个季节流行病关系模型， 以发掘出季节与人们所可能罹患的流行病的关系，并进一步地探讨了不同疾病 间潜在的可能联系，为人们对疾病的防治提供参考。 最后，在总结令文的基础上，明确了f 一步研究的日标和方向。 关键词：数据挖掘、关联规则、a p r i o r i 算法、数据划分、关系模型 a b s t r a c t d a t am i n i n gi st or e v e a lt h ei m p l i c a t e db u tu s e f u li n f o r m a t i o nf r o mm a s s i v e ， i n c o m p l e t e ，n o i s e ，f u z z yd a t a s e t i t se s s e n t i a lt a r g e ti s t oe x t r a c tv a l u a b l ep a t t e r n f r o mt h el a r g e s c a l ed a t a b a s e a s s o c i a t i o nr u l em i n i n gi sa ni m p o r t a n tb r a n c ho fd a t a m i n i n gt h a th a so b t a i n e dm a n yv a l u a b l er e s u l t sb u tt h e r es t i l la r ead e a lo fm o r e c h a l l e n g i n gp r o b l e m st od i s c u s s t h et a s ko fm i n i n ga s s o c i a t i o nr u l e sc o n s i s t so ft w om a i ns t e p s t h ef i r s t i n v o l v e sf i n d i n gt h es e to fa l lf r e q u e n ti t e m s e t s t h es e c o n ds t e pi n v o l v e st e s t i n ga n d g e n e r a t i n ga l lh i g hc o n f i d e n c er u l e sa m o n gi t e m s e t s f o rt h eb o t hs t e p ，c o m p u t a b l e c o m p l e x i t yi st h eb o t t l e n e c ko ft h ea l g o r i t h mf o rt h en u m b e ro ff r e q u e n ti t e m s e t s i n c r e a s e sw i t ht h en u m b e ro fi t e m se x p o n e n t i a l l y t h i sp a p e rd e s c r i b ea na l g o r i t h mc a l l e dp a r t i t i o nt h a ti sf u n d a m e n t a l l yd i f f e r e n t f r o ma l lt h ep r e v i o u sa l g o r i t h m si n t h a ti ts c a n st h ed a t a b a s ea tm o s tt w ot i m e st o g e n e r a t ea l ls i g n i f i c a n ta s s o c i a t i o nr u l e s t h ea l g o r i t h me x e c u t e si nt w op h a s e s ，i n t h ef i r s tp h a s e ，t h ep a r t i t i o na l g o r i t h mi o g i c a l l yd i v i d e st h ed a t a b a s ei n t oan u m b e r o fn o n o v e r l a p p i n gp a r t i t i o n s t h ep a r t i t i o n sa r ec o n s i d e r e do n ea tat i m ea n da l l l a r g ei t e m s e t sf o rt h a tp a r t i t i o na r eg e n e r a t e d a tt h ee n do fp h a s e1 ，t h e s el a r g e i t e m s e t sa r em e r g e dt og e n e r a t eas e to fa l lp o t e n t i a ll a r g ei t e m s e t s i np h a s e1 1 ，s c a n t h ed a t a b a s es e c o n d l y , a p p l ya p r i o r ia l g o r i t h mt ot h e s ei t e m s e t sa n da c t u a ls u p p o r t s f o rt h e ma r eg e n e r a t e da n dt h ef r e q u e n ti t e m s e t sa r ei d e n t i f i e d t h ep a r t i t i o ns i z e s a r ec h o s e ns u c ht h a te a c hp a r t i t i o nc a nb ea c c o m m o d a t e di nt h em a i nm e m o r ys o t h a tt h ep a r t i t i o n sa r er e a do n l yo n c ee a c ht i m e b o t ht h et h e o r e t i c a la n a l y s i sa n dt h e e x p e r i m e n t a lc o m p a r i s o ns h o wt h a tt h ea l g o r i t h mp r o p o s e di nt h i st h e s i sh a sm o r e i m p r o v e dp e r f o r m a n c et h a na p r i o r ia l g o r i t h m t h i sa r t i c l ea p p l yt h er e s e a r c hr e s u l t st ot h em e d i c a ls e r v i c ei n f o r m a t i o ns y s t e m ， h a sc o n s t r u c t e das e a s o ne p i d e m i cd i s e a s er e l a t i o n a lm o d e l ，t od i s c o v e rt h er e l a t i o n s b e t w e e nt h ee p i d e m i cd i s e a s et h ep e o p l ew i l ls u f f e rf o r mp o s s i b l yw i t ht h es e a s o n ， a n df u r t h e rd i s c u s s e dt h eh i d d e n 、p o s s i b er e l a t i o n sa m o n gt h ed i f f e r e n td i s e a s e s ，l h i s w i l lp r o v i d et h er e f e r e n c ef o rt h cp e o p l et od i s e a s ep r e v e n t i n ga n dc o n t r o l l i n g f i n a l l y , o nt h eb a s i so fs u m m a r i z i n g t h ew h o l ep a p e r , p r o s p e c tt h er e s e a r c ha n d d e v e l o p m e n to fd a t am i n i n ga n da p r i o r ia 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 、a p r i o r i 、p a r t i t i o n 、r e l a t i o n a lm o d e l y8 8 0 6 8 6 此页若属实请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名： 关于论文使用授权的说明 日期! ! ：墨 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全都内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 一虢醉聊签龟丝丛日 注：请将此声明装订在论文的目录前。 期鱼至! 。 武汉理t 二人学硕l ：学位论文 第1 章绪论 数据挖掘( d a t am i n i n g ) 是- - 个多学科领域，它融合了数据库技术、人t 智 能、机器学习、神经网络、统计学、模式识别、知识库系统、知识获敢、信息 检索、高性能计算和数搌可视化等最新技术的研究成果。经过几十年的研究， 数据挖掘已经形成了清晰的概念和方法，并且正向着更深入的方向发展。本章 主要介绍了论文研究的背景及意义、数据挖掘的研究现状，并给出了全文的结 构安排。 1 1 论文研究的背景和意义 半个t t c 纪以来，人们利用信息技术生产和搜集数据的能力在不断提高。当 前有无数数据库被用f 商业管理、政府办公、科学研究和工程开发等，这一势 头仍将持续发展下去。特别是近年来，i n t e r n e t 的迅猛发展，网络经济、注意 力经济等概念的出现，以其巨大的社会效益和极富挑战与机遇的内涵成为信 息科学最引入注目的科研课题。于是，一个新的挑战被提了出来：在这被称之为 信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息 的江洋大海历淹没，从中及时发现有用的知识，提高信息利用率昵? 要想使数粥 真正成为个公司的资源，只有充分利用它为公司自身的业务决策和战略发展 服务彳行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，面对“信息 爆炸、但知识匾乏”的挑战，数据挖掘技术应运而生，并得以蓬勃发展，越来 越显示出其强大的生命力。 自2 0 世纪6 0 年代以来，数据库和信息技术已经系统地从原始的文件处理 演化到复杂的、功能强大的数掘库系统。随后，数据库系统的研究和开发从层 次和网状数掘库系统发展到关系数据库系统。到8 0 年代后期，由于关系技术在 数据库系统中的广泛使用，使得数据库技术取得了决定性的成果并且被广泛地 应用。但是，数据库技术作为一种基本的信息存储和管理方式，仍然以联机事 务处理o l t p ( o n l i n e t r a n s a c t i o np r o c e s s i a g ) 为核心技术应用，缺少对决策、 分析、预测等高级功能的支持机制。 经过几十年的研究和实践，数掘挖掘技术吸收了许多学科的研究成果，彤 武汉理l 。火学硕十学位论文 成了独具特色的研究分支。勿容置疑，数据挖掘研究和应用具有很大的挑战性。 目前，火多数学者认为数据挖掘处于广泛研究和探索阶段。一方面，数据挖掘 概念已经被广泛接受，而且相关的研究成果和产品得到了学者的认可，吸引了 越来越多的研究者：另一方面，目前的数据挖掘研究还存在许多有待研究和探 索的问题。 1 2 论文的研究内容 数据挖掘的目标是采用有效的算法，从大量现有的数摒集合中发现并找出 最初未知的，但最终可理解的有用的知识，并用简明的方式显示出来。数摒挖 掘的目的是否能够达到很大程度上和数据挖掘系统所采用的挖掘算法息息柑 关，因此，算法在数据挖掘中起了至关重要的作用。 本文主要是研究数据挖掘中的关联规则挖掘算法，关联规则是用于发现大 量数据中项集之问有意义的关系模式。本文首先对数据挖掘技术的产生和发展 现状做了概括性的阐述，介绍了数据挖掘的概念、主要内容、模式和主要问题， 以及数据挖掘的应用和发展；接着对数据挖掘中的关联规则做了详细的描述， 介绍了关联规则的分类、关联规则挖掘的步骤和关联规则的经典挖掘算法 a p t i o r i 算法，在总结和分析了a p r i o r i 算法的基本性质、性能和特点的基础 上，介绍了一种在a p r i o r i 算法基础卜的改进算法，该改进算法利用新的产生 候选项集的方法，提高了关联规则挖掘的效率。 本文还将研究成果应用到医疗信息系统，构建了一个季节流行病关系模型， 以发掘出季节与人们所可能罹患的流行病的关系，并进步地探讨了不同疾病 洲潜在的可能联系，为人们对疾病的防治提供参考。 1 3 论文的结构安排 本文的结构安排如下： 第1 章：主要介绍论文研究的背景和意义，论文的研究内容及结构安排。 第2 章：介绍数据挖掘的一般件理沦，包括概念、丰要内容、模式和主 2 武汉理t 大学硕：l 学位沦文 要问题，以及数据挖掘的应用和发展。 第3 章：介绍关联规则挖掘算法，包括概念、挖掘步骤和应注意的问题、关 联规则的分类以及一些典型算法。 第4 章：奉文的重点内容。对关联规则的经典算法a p r i o r i 进行了详细的讨 论，给出了a p r i o f j 算法描述，分析了a p f i o f i 算法的特点及不足，针对其不 足提出了改进算法，通过试验比较了改进的后的效率。 第5 章：以a p r i o r i 算法为基础，构建了一个季节流行病关系模型，为人 们对疾病的防治提供参考。 第6 章：总结与展望。 武汉理1 大学硕f 1 学位论文 第2 童数据挖掘综述 数据挖掘足数据库系统和新的数据库应用的一个有希望的、欣欣向荣的学 科前沿，是数掘库研究、丌发和应用最活跃的分支之一。它不满足_ j 二对数据进 行简单的查询，而是想从人量的数据中找出更多有用的知识，因此，数据挖掘 的过程又称为知识发现的过程。从某种意义上讲，数据挖掘的自主性使得计算 机具有一定的“智能”，可以实现许多人力所无法完成的事情，使计算机对人类 的辅助作用得到更大的发挥，信息资源也得剑更大的利用。木章主要介绍了数 据挖掘的概念、模式、分类，数据挖掘面i 临的主要问题，以及数据挖掘的应用 和发展趋势。 2 1 数据挖掘概念 简单地说，数据挖掘是从大量数据中提取或“挖掘”知识，也称数据库中 的知识发现( k d d ) ，是指从大型数据库或数据仓库中提取人们感兴趣的知识， 这些知识是隐含的、事先未知的潜在有用的信息，提取的知识一般可表示为概 念( c o n c e p t s ) ，规则( 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 ) 数据集成多种数据源可以组合在起 ( 3 ) 数据选择从数据库中检索、分析与任务相关的数据 ( 4 ) 数据变换将数据通过汇总或聚集操作变换成适合挖掘的形式 ( 5 ) 数据挖掘使用智能方法提取数据模式 ( 6 ) 模式评估根据某种模式度量，识别真正感兴趣的模式 ( 7 ) 知识发现使用可视化和知识表示技术，向用户提供挖掘的知识 尽管大多数人都同意数据挖掘是知识发现过程的一个步骤。然而，在产、世 界、媒体和数据库研究界，术语“数据挖掘”比术语“数挢库巾知识发现”更 流行。囚此，数据挖掘有一个更为广泛的概念：数据挖掘足从存放在数据库、数 据仓库或其他信息库中的人量数据中挖掘有兴趣知识的过程”。 武汉理上人学硕 学传论文 2 2 数据挖掘研究的理论基础 谈到知识发现和数掘挖掘，必须进一步阐述它的研究的理论基础问题。虽 然关于数据挖掘的理论基础问题仍然没有到完全成熟的地步，但是分析它的发 展可以使我们对数据挖掘的概念更清楚。坚实的理论是我们研究、开发、评价 数据挖掘方法的的基石。经过十几年的探索，一些重要的理论框架已经形成， 并且吸引着众多的研究和开发者为此进一步工作，向着更深入的方向发展。 数拥挖掘方法可以是基于数学理论的，也可以是非数学的；可以是演绎的， 也町以是归纳的。从研究的历史看，它们可能是数据库、人工智能、数理统计、 计算机科学以及其它方面的学者和工程技术人员，在数据挖掘的探讨性研究过 程q 1 创立的理论体系。1 9 9 7 年，m a n n i l a 对当时流行的数据挖掘的理论框架给 出了综述“1 。结合最新的研究成果，有下面一些重要的理论框架可以帮助我们 准确地理解数据挖掘的概念与技术特点： ( 1 ) 模式发现( p a t t e r nd i s c o v e r y ) 架构 在这种理论框架下，数据挖掘技术被认为足从源数据集中发现知识模式的 过程“。这是对机器学习方法的继承和发展，是目前比较流行的数据挖掘研 究与系统开发架构。按管这种架构，我们可以针对不同的知识模式的发现过程 进行研究。目前，在关联规则、分类聚类模型、序列模式( s e q u e n c em o d e l ) 以及决策树( d e c i s i o nt r e e ) 归纳等模式发现的技术与方法上取得了丰硕的成 果。近几年，也已经开始多模式的知识发现的研究。 ( 2 ) 规则发现( r u l ed i s c o v e r y ) 架构 a g r a w a l 等综合机器学习与数据库技术，将三类数据挖掘目标即分类、关 联及序列作为一个统一的规则发现问题来处理”。他们给出了统一的挖掘模型 和规则发现过程中的几个基本运算，解决了数据挖掘问题如何映射到模型和通 过基本运算发现规则的问题。这种基于规则发现的数据挖掘构架也是目前数据 挖掘研究的常用方法。 ( 3 ) 基于概率和统计理论 在这种理论框架卜，数据挖掘技术被看作是从大量源数据集中发现随机变 鼍的概率分布情况的过程。例如，贝叶斯置信网络模型等“。目前，这种方法 存数据挖掘的分类和聚类研究和应用中取得了很好的成果。这些技术和方法可 以看作是概率理论在机器学习中应用的发展和提高。统计学作为一个古老的学 武汉理i ：大学硕t 学位论文 科，已经在数据挖掘中得到广泛的应用。例如，传统的统计回归法在数据挖掘 中的应用。特别是，最近十年，统计学已经成为支撑数据仓库、数据挖掘技术 的重要理论基础。实际上，大多数的理论构架都离不开统计方法的介入，统计 方法在概念形成、模式匹配以及成分分析等众多方面都是基础中的基础。 ( 4 ) 微观经济学观点( m i c r o e e o n o m i cv i e w ) 在这种理论框架下，数据挖掘技术被看作是一个问题的优化过程97 。1 9 9 8 年，k l e i n b e r g 等人建立了在微观经济学框架里判断模式价值的理论体系。他 们认为，如果一个知识模式对一个企业是有效的话，那么它就是有趣的。有趣 的模式发现是一个新的优化问题，可以根据基本的目标函数，对“被挖掘的数 据”的价值提供一个特殊的算法视角，导出优化的企_ k 决策。 ( 5 ) 基于数据压缩( d a t ac o m p r e s s ) 理论 在这种理论框架下，数掘挖掘技术被看作是对数据的压缩的过程“。按着 这种观点，关联规则、决策树、聚类等算法实际一k 都是对大型数据集的不断概 念化或抽象的压缩过程。按c h a k r a b a r t i 等人的描述，最小描述长度( m d l m i l 3 i m u md e s c r i p t i o el e n g t h ) 原理可以评价一个压缩方法的优劣，即最好的压 缩方法应浚是概念本身的描述和把它作为预测器的编码特征都最小“。 ( 6 ) 基于归纳数据库( i n d u c t i v ed a t a b a s e ) 理论 在这种理论框架下，数据挖掘技术被看作是对数据库的归纳的问题”。 一个数据挖掘系统必须具有原始数据库和模式库，数据挖掘的过程就是归纳的 数据查询过程。这种构架也是目前研究者和系统研制者倾向的理论框架。 ( 7 ) 可视化数据挖掘( v is u a d a t am i n i n g ) 1 9 9 7 年，k e i m 等对可视化数据挖掘的相关技术给出了综述“。虽然可视化 数据挖掘必须结合其它技术和方法才有意义，但是，咀可视化数据处理为中心 来实现数据挖掘的交互式过程以及更好地展示挖掘结果等，已经成为数据挖掘 中的一个重要方面。这类研究的卜升趋势可以通过a c m s o g m o d 0 2 会议的相关论 文数量得到验证“。 当然，上面所述的理论框架不是孤立的，更不是互斥的。对于特定的研究 和开发领域来说，它们是相互交叉并且有所侧重的。从上面的叙述中，我们也 可以看出，数据挖掘的研究是在相关学科充分发展的基础上提出并不断发展的， 它的概念和理论仍在发展中。为了弄清相关的概念和技术路线，仍有大罱的工 作等待我们去探索和尝试。 武汉理_ t 大学硕士。学位论文 2 3 数据挖掘的模式 数据挖掘的目的是发现知识，知识要通过一定的模式给出。可用于数据挖 掘系统的知识表示模式是丰富的，通过对数据挖掘中知识表示模式及其所采用 方法的分析，可以更清楚地了解数据挖掘系统的特点。 1 广义知识挖掘 广义知谚 ( g e n e r a l i z a t i o n ) 是指拙述类别特征的概括性知谚 。我们知道，在 源数据( 如数据库) 巾存放的一般是细节性数据，而人们有时希望能从较高层次 的视图上处理或观察这些数据，通过数据进行不同层次上的泛化来寻找数据所 蕴涵的概念或逻辑，以适应数据分析的要求。数据挖掘的目的之一就是根据这 些数据的微观特性发现有普遍性的、更高层次概念的中观和宏观的知识。因此， 这类数据挖掘系统是对数据的所蕴涵的概念特征信息、汇总信息和比较信息等 的概括、精炼和抽象的过程。被挖掘出的广义知识可以结合可视化技术以直观 的图表( 如饼图、柱状图、嗵线图、立方体等) 形式展示给用户，也可以作为其 它应用( 如分类、预测) 的基础知识。 2 关联知识挖掘 关联知识( a s s o c i a t i o i l ) 反映一个事件和其它事件之阃的依赖或关联。数据 库中的数据关联是现实世界中事物联系的表现。数据库作为一种结构化的数据 组织形式，利用其依附的数据模型可能刻画了数据问的关联( 如关系数据库的主 键和外键) 。但是，数据之间的关联是复杂的，不仅是上面所说的依附在数据模 型中的关联，大部分是蕴藏的。关联知识挖掘的目的就是找出数据库中隐藏的 关联信息。关联可分为简单关联、时序( t i m es e r i e s ) 关联、因果关联、数量 关联等。这些关联并不总是事先知道的，丽是通过数据库中数据的关联分析获 得的，因而对商业决策具有新价值。 从1 义上讲，关联分析是数据挖掘的本质。既然数据挖掘的目的是发现潜 减在数据背后的知识，那么这；l , b j m 识一定是反映不同对象之间的关联。在上而 我们提到的广义知识挖掘问题实际上是挖掘数据与不同层次的概念之| 、日j 的关 联。当然，本节的关联分析还是指一类特定的数据挖掘技术，它集中在数据库 中对象之间关联及其程度的刻画。 关联规则挖掘是关联知识发现的最常用方法。最为著名的是a g r a w a l 等提 出的a p r i o r i 及其改进算法。”。”1 。为了发现出有意义的关联规则，需要给定 武汉理丁人学硕十学化论文 两个阈值：最小支持度( 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 ) 挖掘出的关联规则必须满足用户规定的最小支持度，它表示了一组项目关联存 一起需要满足的最低联系程度。挖掘出的关联规则也必须满足片= | 户规定的最小 可信度，它反映了一个关联规则的最低可靠度。在这个意义上，数据挖掘系统 的目的就是从源数据库中挖掘出满足最小支持度和最小，u 信度的关联舰则。关 联规则的研究和应用足数据挖掘中最活跃和比较深入的分支，许多关联规则挖 掘的理论和算法已经被提出。关于关联规则挖掘问题及其算法等，后面还会详 细叙述。 3 类知识挖掘 类知_ i ( c l a s s ) 刻画了一类事物，这类事物具有某种意义上的共同特征，并 明显和4 i 同类事物相区别。和其它的义献相对应，这里的类知识是指数据挖掘 的分类和聚类两类数据挖掘应用所对应的知识。 ( 1 ) 分类 分类是数据挖掘中的一个重要的同标和任务，目前的研究和在商业上应用 最多。分类的目的是学会一个分类模型( 称作分类器) ，该模型能把数据库中的 数据项映射到给定类别中。要构造分类器，需要有一个训练样本数据集作为输 入。由于数据挖掘是从源数据集中挖掘知u 的过程，这种类知识也必须来自r 源数据，应该是对源数据的过滤、抽取( 抽样) 、压缩以及概念提取等。从机器 学习的观点，分类技术是一种有指导的学习( s u p e r v i s e dl e a r n i n g ) ，即每个训 练样本的数据对象已经有类标识，通过学习可以形成表达数据对象与类标识间 对应的知识。从这个意义上说，数据挖掘的目标就是根据样本数据形成的类知 识并对源数据进行分类、进而也呵以预测未来数据的归类。用于分类的类知识 可以用分类规则、概念树，也可能以一种学习后的分类网络等形式表示出来。 ( 2 ) 聚类 聚类是把一组个体按照相似性归成若j 1 | 类别，它的目的是使得属于同一类 别的个体之间的差别尽可能的小，而不同类别上的个体问的差别尽可能的人。 数据挖掘的目标之一是进行聚类分析。通过聚类技术可以对源数据库中的记录 划分为一系列有意义的子集，进而实现对数据的分析。例如，一个商业销售企 、i p ，可能关心哪些( 同类) 客户对指定的促销策略更感兴趣。聚类和分类技术不 i 司，前者总是在特定的类标识下寻求新元素属于哪个类，而后者则是通过对数 据的分析比较生成新的类标识。聚类分析生成的类标识( 可能以某种容易理解的 武汉理【大学硕士学位论文 形式展示给用户) 刻画了数据所蕴涵的类知口 。当然，数据挖掘中的分类和聚类 技术都是在已有f | 勺技术基础上发展起来的，它们互有交叉和补充。 4 预测型知识挖掘 预测型知识( p r e d i c t i o n ) 是指由历史的军u 当前的数据j “生的并能推测未来 数据趋势的知识。这类知识可以被认为是以时间为关键属性的关联知u ，凶此 上面介绍的关联知识挖掘方法可以应用到以时间为关键属性的源数据挖掘中。 从预测的主要功能上看，t 要是对未来数据的概念分类和趋势输出。上面介绍 的分类技术可以用于产生具有对末来数据进彳亍归类的预测型知识。统计学中的 回归方法等可以通过历史数据直接产生对未来数据预测的连续值。因而这些预 测型知识已经蕴藏在诸如趋势曲线等输出形式巾。所以，一些文献，把利用历 史数据生成具有预测功能的知谚 挖掘工作归为分类问题，而把利用历史数据j “ 生并输出连续趋势曲线等问题作为预测型知识挖掘的宅要工作。这种说法有 它的合理性。如果要进一步说明的话，我们认为，分类型的知识也应该有两种 基本用途。第一，通过样本子集挖掘出的t w - j l 可能目的只是用于对现有源数据 库的所有数据进行归类，以使现有的庞大源数据在概念或类别上被“物以聚类”。 第二，有些源数据尽管它们是已经发生的历史事件的记录，但是存在对未来有 指导意义的规律性东西，如总是“老年人的癌症发病率高”。因此这类分类知识 也是预测型知识。 预测型知识的挖掘也可以借助于经典的统计方法、神经网络和机器学习等 技术，其中经典的统计学方法是基础。相关技术可以在相应的统计学教科书等 找到，因此这里不再会详细解决这些方法和算法的原理。 5 特异型知识挖掘 特异型知识( e x c e p t i o n ) 是源数据中所蕴涵的极端特例或明显区别于其它 数据的知识描述，它揭示了事物偏离常规的异常规律。数据库巾的数据常有一 些异常让录，从数据库中榆测出这些数据所蕴涵的特异知识足很有意义。例如， 在w e b 站点发现那些区别于正常登录行为的用户特点可以防止非法入侵。特异 型知识可以和其它数据挖掘技术结合起来，在挖掘普通知识的同时进一步获得 特异知识。例如，分类中的反常实例、不满足普通规则的特例、观测结果与模 型预测值的偏差、数掘聚类外的离群值等等。 2 4 数据挖掘的应用 数据挖掘技术旨在发现大量数据种所隐藏的知识，以用来解决“数据丰富、 知识贫乏”的问题。近年来随着数掘库和网络技术的广泛应用，加上使用先进 的自动数据生成和采集工具，人们所拥有的数据量急剧增加，为数据挖抓技术 在科学研究、金融投资、市场营销、保险、医疗卫生、产品制造业、通信网络 管理等行业已得到应用。 1 科学研究 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量 实验和观测数据靠传统的数据分析工具己难于对付，因此对功能强大的智能化 自动分析工具要求迫切，这种需求推动了k d d 技术在科学研究领域的应用发 展，并且已获得一些重要的应用成果。 2 金融投资 在银行和金融机构中产生的金融数据通常相对比较完整，可靠和质量较高， 因此，数据挖掘在这一领域中的应用相对比较成熟，也取得较好的社会效益和 经济效益。由于金融投资的风险很大，在进行投资决策时，需要对各种投资方 向的有关数据进行分析，以选择最佳的投资方向，而数据挖掘则是通过对己有 数据进行处理，并利用学习得到的模式进行市场预测，以选择最佳的投资方向， 可使金融投资的风险降低。通过分析市场波动的因素，建立预测模型，进行投 资分析和预测，改进预测市场波动的能力，为投资决策提供科学的依据。 3 保险业 随着社会保障体系的r i 益健全，保险业取得了蓬勃的发展，发挥着越来越 重要的作用。保险是一项风险业务，保险公司的一个重要工作就是进行风险评 估。通过研究证明，可以利用数据挖掘技术来进行风险分析，在保险公司建立 的保单及索赔信息数据库的基石；| 上，寻找保单中风险较大的领域，从而得山 些实用的控制风险的规则，以指导保险公司的工作。数据挖掘技术在保险业巾 的应用，有利于保险公司开展业绩评价、财务预算、市场分桥、风险评估和风 险预测等，大大提高企业防范和抵抗经营风险的能力和水平，也为管理人员提 供科学的决策依据。 4 零售业 零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买爿性和趋向， 武汉理i j 大学硕十学位论文 对于零售商制定销售策略是至关重要的。销售分析人员运用关联规则挖掘技术 对大量的销售数据进行分析，可以发现顾客购买模式和趋势，改进服务质量 取得更好的顾客保持力和满意程度，提高货品销售比率，设计更好的货品运输 与分销策略，减少商业成本。购物篮分析是数据挖掘技术应用赴零售业中的一 种有效方式，u 用f 销售搭配、产品目录发计、产品定价和促销等。 5 。制造业 随着现代技术越来越多地应用于制造业，产品牛产已不是人们想象中的手 工劳动，而是集成了多种先进科技的流水作业。在产品的生产制造过程中常常 伴随着大量的数据，如产品的各种加工条仆或控制参数，这些数据反映了每个 生产环节的状态，不仅为生产的顺利进行提供了保证，而且通过对这些数据的 分析，得到产品的质量与这些参数之间的关系。这样通过数据挖掘对这些数据 的分析，可以对改进产品质量提出针对性很强的建议，而且有可能提出新的更 高效节约的控制模式，从而为制造厂家带来极大的回报。 武汉理 大学颂十学位论文 第3 章关联规则挖掘算法 关呋规则的概念山a g r a w a ，i m i e l n s k i ，s w a m i 提出，是数据挖掘中一种 简单但很实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属 于无监督学习的算法。关联规则本身是一种很重要的知识，是d m 研究的主要内 容，它能表示数据之间的相互关系，对统计和决策工作有重大意义。“”。关联 规则挖掘算法一般都是基于交易数据库的，也有一些研究将其推广到一般数据 库。关联觌则的主要应用包括商场的顾客购物分析，网络故障分析等。 3 1 基本概念 简单的况，关联规则就是给定组项目( i t e m ) 和个记录集合，通过分析 记录集合，推导出1 t e m 问的相关性，关联规则广泛地应用于商业界、医疗保险、 会融业、司法部门等，因此对它的研究有着极其重要的意义。 在关联规则系统中，规则奉身是“如果条件怎么样、怎么样，那么结果或 情况就怎么样”的简单形式。可以表示为“a b ”关联规则，它包括两个部分： 左部a 称为前件，右邦b 称为后件。前件可以包括一个或多个条件，在某个绘 定的正确率中，要使后件为真，前件中的所有条件必须同时为真。后件一般只 包含一种情况，而不是多种情况。 以可信度( 也称可信度) 为目标的关联规则，主要是以可信度表示前件为真 时，后件为真的可能性。对于“a b ”关联规则，其可信度可定义为： 可信度( a b ) = 同时包含a 和b 的记录数包含a 的记录组数 对用户来说最重要的是规则的正确率。正确率达到8 0 以上的规则，表明 发现的关系是很强的。即使它们对数据库的覆盖率较低，出现的次数不多。 以支持度( 也称支持度) 为目标的关联规则表示数据库中适用于规则的记录 数量。可定义为： 支持度( a b ) = 同时包含a 和b 的记录数记录总数 支持度高表示规则经常被使用。 关联规则分析可数学形式化地描述为： 武汉理l 人学硕十学伉沦文 设【= l ，iz ，i 。) 是由m 个f i 同的项目组成的集合( 习惯上我们还称i 为项 集) 。给定一个数据库d ，且数据库d 中的每一个记录t 是l 中一组属性的集合， 即1 、i 。设x 是i 巾一组项目的集合，若x n 我们称，r 包含x 。一条关联规 则就是形如x y 的蕴涵式，其中x i ，y i ，x n y = a 。关联规则x - y 在数 据库d 中成立的条件是： ( 1 ) 它具有支持度s 。即在数据库d 中至少有s 的记录包含x u y 。 ( 2 ) 它具有可信度c 。即在数据库d 中包含的x 记录至少有c 的同时也包 含y 。 习惯上将关联规则表示为x = y ( s ，c ) 。其中，支持度定义了项目在整 个数据库中所占的比例；可信度定义了发现规则的强度。 考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物 品乙，事务3 中同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相 互之间是否有规律可循呢? 在数据库的知识发现中，关联规则就是描述这种在一 个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量 化的数字描述这种在一个事务中的物品甲的出现对于物品乙的出现有多大的影 响。 现实中，这样的例子很多。例如超级市场利用前端收款机收集存储了大量 的售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时 间，顾客购买的物品、物品的数量及金额等，这砦数据中常常隐含形式如下的 关联规则：在购买香烟的顾客中有7 0 的人同时购买了打火机。这些关联规则很 有价值，商场管理人员可以根据这些关联姚则更好地规划商场，如把香烟和打 火机这样一类的商品摆放在一起，以促进销售。 3 2 相关定义 定义1 记录t 包含项目集合x 假设有一个项目集合x ，一条记录t ，如果x c t ，则称记录，【、包含项 目集合x 。 定义2 可信度 设数据库d 中包含项目集合x 的记录中，有c 的记录同时包含项目集 合y ，则c 称为关联规则x - y 的l i 信度( c o n f i d e n c e ) 武汉理下火学硕十1 、产何论文 例2 1 ：在购买香烟的顾客当中，有7 0 酐j 人刷时购买了打火机。关联规则： 购买香烟= 购买打火机，其可信度是7 0 。该关联规则的可信度回答了这样一 个问题：如果一个顾客购买了香烟，那他购买打火机的可能性有7 0 定义3 支持度 没数据库d 中有s 的记录同时包含项目集合x 和y ，则s 称为关联规则 a = b 的支持度( s u p p o r t ) 。支持度描述了x 和y 这两个项目集合的并集在所有 的事务记录中出现的概率有多大。 可信度是对关联规则的正确率的衡量，支持度是对关联规则重要性的衡量。 支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联 规则越重要。有些关联规则的可信度虽然很高，但支持度却很低，说明该关联 规则实用的机会很小，因此实际上也不重要。 可以看m ，支持度和可信度能够比较直接形容关联规则的性质。从关联规 则定义可以看出，任意给出事务中的两个项日集，它们之间都存在关联规则。 如果不考虑关联规则的支持度和可信度，那么在事务数据库中可以发现无穷多 的关联规则，事实上，需要给定两个阈值：最小支持度和最小可信度。 定义4 最小支持度 关联规则必须满足的支持度的最小值称为最小支持度( m i n s u p ) 。 定义5 最小可信度 关联规则必须满足的可信度的最小值称为最小可信度( m i n c o n f ) 。 最小支持度和最小可信度限定了一条关联规则成立必须达到的支持率和f 确率，即关联规则a = b s u p p o r t ( = b ) 2 m i n s u pa n dc o n f id e n c e ( a = g ) m i n c o n f 。 定义6 强关联规则“” 可信度和支持度均大于用户给定的闽值的关联规则称为强关联规则。数据 挖掘的主要兴趣就是对强关联规则的挖掘。 在统计学意义上，最小支持度表示关联规则的最低重要性，最小可信度表 示关联舰则的最低可靠性。因此，强关联规则是既重要又可靠的关联规则，具 有预期的价值；不满足上述两个条件的关联规则又称为弱关联规则。 定义7 项 非空集合i = i ，i 。1 。 称为项集，其中的t 。( k = l ，2 ，m ) 称为 项。 武汉理i 人学硕- b 。学位论文 定义8 模式的长度 模式p 定义为： a 、，& ，a k ，a i ( j = 1 ，2 ，k ) ：p 所包含的项的个 数k 称为模式p 的长度。 定义9 模式集、频繁模式集 在事务数据库d 上，长度为k 的模式成为k 一模式。k 模式的集合称为k 一 模式集，记为k - i t e m s e t 。支持度大于最小覆盖率的k 一模式称为k 频繁模式。 全部k 频繁模式的集合，称为k 频繁模式集，记为频繁k i t e m s e t 。 定义l o 冗余规则 如果规则x = y 和x - ) y 属于同一关联规则集，且y e y ，那么，x 2 y 是 冗余的。 引理i 频繁模式的子模式也是频繁模式。” 定理1 非频繁模式的父模式也是非频繁模式。( 根据逆反定律可以证明定 耻成立! ) 3 3 挖掘步骤及应注意的问题 3 3 1 挖掘步骤 发现关联规则要经过以下三个步骤： i 连接数据，进行数据准备； 2 给定最小支持度和最小可信度，利用数据挖掘工具提供的算法发现关联 规则； 3 可视化显示，理解和评估关联规则。 3 3 2 应注意的问题 在关联规则的挖掘中要注意以下几点： 1 充分理解数据； 2 目标明