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

晗尔滨工程大学硕士学位论文 摘要 关联规则是数据挖掘中一个重要的研究内容。典型的关联规则发现算法 是由r a g r a w a l 等提出的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 算法的不足，提出了一种高效的关联规则挖掘算法n e a ，利用频繁项目集厶、 和候选项目集e 中的结果对数据库进行筛选，减少候选项在数据库中查找的 记录数，提高了整个算法的效率；针对数据库置信度、支持度不断调整的需 要，分别给出了m i n s u p o r t 和m i n c o n f i d e n c e 增大、减小时关联规则快速的 更新算法m i n s u p c h a n g e 和m i n c o n f c h a n g e ，并与a p r i o r i 算法作了分析比较； 最后将关联规则数据挖掘的方法运用到课堂教学评价中。从教学评价数据中 进行数据挖掘，找到课堂教学效果与教师基本情况的关系，从而更好地开展 教学工作，提高教学质量。 关键词：数据挖掘；关联规则；频繁项目集；支持度：置信度 哈尔滨 _ 程大学硕士学位论文 a b s t r a c t a s s o c i a t i o nr u l em i n i n gi so n eo ft h em o s ti m p o r t a n tp a r t si nd a t am i n i n g t h et y p i c a l a l g o r i t h mo fa s s o c i a t i o nr u l ei sa p r i o r iw h i c hw a sp u tf o r w a r db yr a g r a w a l t h ep r o p o s e d a l g o d t h ms o a l st h ew h o l ed a t ab a s ed u r i n ge a c hl o o pi nc a l c u l a t i n gs u p p o r to f t h ec a n d i d a t e i t e m s e t h o w e v e r , t h ee f f i c i e n c yo fm i n i n gi sl o w t h e r e f o r em o r ee f f e c t i v ea l g o r i t h m sm u s t b ed e v e l o p e d t h i st h e s i se x p l o r e sa s s o c i a t i o nr u l ea l g o r i t h mi nd a t am i n i n g ，a n da n a l y z e st h ec l a s s i c a l a l g o r i t h ma p r i 耐i nd e t a i l t h ep r o c e d u r eo ft h ep r o p o s e da l g o r i t h mi sp r e s e n t e da n dt h e d e f i c i e n c yi sp r o p o s e d a ne f f i c i e n ta s s o c i a t i o nr u l ea l g o r i t h mn e a i sd e v e l o p e di nt e r m so f t h ed e f e c to f t h ep r o p o s e da l g o r i t h mb yu s i n g 血er e s u l t sf r o ms e t so f 厶a n dc kt of i l t e r o u tt h ed a t a b a s e t h e r e f o r e 血en u m b e ro fr e c o r d ss e a r c h e di nc a b d i d a t es e t sf r o m t h ed a t a b a s ei sr e d u c e d a n dt h ee f f i c i e n c yo ft h ea l g o r i t h mi se n h a n c e d t h e e f f i c i e n tu p d a t e da l g o r i t h m sm i n s u p c h a n g ea n dm i n c o n f e h a n g ea r ep r e s e n t e d w h e nt h ev a l u e so fm i n s u pa n dm i n c o n fi n c r e a s eo rd e c r e a s e a n dt h e c o m p a r i s i o nw i t ha p r i 耐i sm a d e f i n a l l y , t h ei m p r o v e da l g o r i t h mn e a i sa p p l i e d i nt h ee v a l u a t i o no ft e a c h i n g i no r d e rt of i n do u tt h er e l a t i o n s h i pb e t w e e n t e a c h i n ga n dt h eq u a l i f i c a t i o no ft h et e a c h e r s ，d a t am i n i n gi sp e r f o r m e d ，t h u st h e t e a c h i n ge f f i c i e n c ya n dq u a l i t ya r ei m p r o v e d k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o nn i l e ；f r e q u e n ti t e m s e t ；s u p p o r t ；c o n f i d e n c e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的 指导下，由作者本人独立完成的。有关观点、方法、 数据和文献的引用已在文中指出，并与参考文献相对 应。除文中已注明引用的内容外，本论文不包含任何 其他个人或集体已经公开发表的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律结果由本人 承担。 作者( 签字) ： 日期：璐月么日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1数据挖掘的意义及研究现状 近年来，随着计算机技术突飞猛进的发展、数据管理技术的成功应用、 各部门信息化程度的不断提高，人们所拥有的数据量急剧增大。这些数据十 分繁杂，要从中发现有价值的信息和知识，达到决策的目的，是一个非常艰 巨的任务。利用传统的数据分析方法( 例如统计) ，人们无法有效地理解并使 用这些数据，只能获得这些数据的表层信息，很难对数据进行深层次的处理， 而且不能获得数据属性之间的内在关系和隐含的信息，即不能获得重要的有 价值的知识。大型数据库系统也不能从根本上解决这一问题，决策者们需要 得到这些蕴含在海量数据中的知识并用于决策指导。我们陷入“数据富有但 知识贫乏”的尴尬局面。显然，人们需要一种崭新的、高级的数据分析工具 来完成理解己有的数据并用于预测未来走势的任务。在这种情况下，“数据挖 掘”种新型的数据分析技术于1 9 9 5 年诞生了。十多年来，数据挖掘的研究 工作取得了很大的进展，各种数据挖掘软件的应用极大地推动了人们掌握、 处理信息的能力，并为人们带来了很好的经济效益。 1 9 8 9 年8 月，在美国底特律召开的第1 1 届国际人工智能联合会议的专 题讨论会上首次出现k d d 这个术语，即数据库中的知识发现( 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 ) ，是指低层数据一直抽象到高层知识的整 个过程。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行k d d 专题讨论会，汇集来 自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算 法、知识表示、知识运用等问题。随着参与人员的不断增多，k d d 国际会议 发展成为年会。1 9 9 5 年，在美国计算机年会( a c m ) 上，提出了数据挖掘( d m ： d a t am i n i n g ) 的概念。1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖 掘国际学术会议不仅进行了学术讨论，并且有3 0 多家软件公司展示了他们的 数据挖掘软件产品，不少软件已在北美、欧洲等国得到应用。 由于数据库中的数据被形象地比喻为矿床，因此，数据挖掘一词很快流 传开来。由于它应用的普遍性及由此带来的高效益，数据挖掘已成为一个具 哈尔滨工程大学硕士学位论文 有广阔应用前景的热门研究方向。目前，世界上比较有影响的典型数据挖掘 系统有：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 tm 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 e s t u d i e 、r u l eq u e s tr e s e a r c h 公司的s e e 5 、还有c o v e rs 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 bm i n e r 、q u e s t 等。 在g a r t n e rg r o u p 的一次高级技术调查中，将数据挖掘和人工智能列为 “未来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将 并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。 根据最近g a r t n e r 的h p c 研究表明，“随着数据捕获、传输和存储技术的快速 发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用 更为广阔的并行处理系统来创建新的商业增长点。” 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量，直到1 9 9 3 年国家自然科学基金才首次支持该领域的研究项目，到9 0 年代中后期，初步 形成了知识发现和数据挖掘的基本框架。自9 0 年代中期一批研究成果( 学术 论文) 逐渐发表在计算机学报、计算机研究与发展、软件学报、人 工智能与模式识别等刊物上，研究重点也正在从发现方法转向系统应用， 并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。但是 基本上还是以学术研究为主，实际应用上处于起步阶段。目前，国内的许多 科研单位和高等院校竞相开展知识发现的基础理论及其应用研究，研究所涉 及的领域很多，一般集中于算法的研究，数据挖掘的实际应用以及有关数据 挖掘理论方面的研究，如北京系统工程研究所对模糊方法在知识发现中的应 用进行了较深入的研究；北京大学也在开展对数据立方体代数的研究i 华中 科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林 大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川大学 和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据 挖掘。但是到目前为止还没有商用工具闯世，像复旦大学设计的基于关联规 则的数据挖掘工具a r m i n e r 等也只是处于实验室研究阶段。目前进行的大多 数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划等。 1 2 数据挖掘中的关联规则 哈尔滨工程大学硕士学位论文 目前，数据挖掘的主要技术为关联规则、聚类、粗糙集、神经网络和遗 传算法等方面。关联规则表示数据库中一组对象之间某种关联关系的规则。 例如，关联规则可以表示为“购买了项目a 和b 的顾客中有9 5 的人又买了c 和d ”。从这些规则可找出顾客购买行为模式，可以应用于商品货架设计、生 产安排、针对性的市场营销等。采用关联模型比较典型的例予是“啤酒和尿 布”的故事。在美国，一些年轻的父亲下班后经常到超市去买婴儿尿布，超 市经过对顾客的购物信息进行挖掘，发现在购买婴儿尿布的年轻父亲中，有 3 0 n4 0 的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤 酒放在一起。结果销售额明显增加了。 关联规则问题由a g r a w a l 等人于1 9 9 3 年首先提出，以后诸多的研究人员 对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进 行优化，如引入随机采样、并行的思想、增加衡量标准、规则约减、改变存 储结构等，以提高算法挖掘规则的效率。对关联规则的应用进行推广，从最 初的商业指导到生活中的其他领域，如教育、科研、医学等。 1 3本文的主要工作 本文的研究工作源于上述的背景。目的是对数据库知识发现进行深入的 研究，主要围绕关联规则对数据挖掘理论和方法进行了以下几方面的工作： 1 归纳了数据挖掘技术的总体研究情况，包括数据挖掘的定义、与其它 学科的关系、挖掘的主要过程、分类和主要技术手段。 2 对关联规则算法( 特别是a p r i o r i 算法) 进行深入研究，在深刻理解 算法的基础上，针对算法中存在的问题提出一种高效的关联规则挖掘算法， 并对快速更新算法进行探讨。 3 ，介绍我国高校教学评价的意义、现状及发展趋势，讨论改进的关联规 则在高校教学评价系统中的应用。从教学评价数据中进行数据挖掘，找到课 堂教学效果与教师状态的关系问题；在班级排课时，注意一个教学班中配备 教师的年龄、职称、学历等的合理分配，使学生能够较好地保持良好的学习 状态，从而为教学部门提供了决策支持信息，促使更好地开展教学工作，提 高教学质量。 4 ，最后进行模式的理解和评估。 哈尔滨工程大学硕士学位论文 第2 章数据挖掘技术 2 1数据挖掘概述 2 1 1 数据挖掘的定义 简单的说，数据挖掘( d a t am i n i n g ) 就是从大量数据中提取或“挖掘”知 识。目前，数据挖掘界普遍认为： 定义2 1 数据挖掘( d a t am i n i n g ) ：就是从大量的、不完全的、有噪声的、 模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、 但又是潜在有用信息和知识的过程。啪旧。 这个定义包括以下四个层次的含义： 1 数据源必须是真实的、大量的、含噪声的； 2 发现的是用户感兴趣的知识： 3 发现的知识要可接受、可理解、可运用，最好能用自然语言表达发现 结果： 4 并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科 学定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对 的，是有特定前提和约束条件、面向特定领域的。 还有很多和这一术语相近的术语，如数据库中的知识发现 k d d ( 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 ) ，智能数据分析、知识抽取、信息 发现、数据考古、数据采集、信息收割、商业智能、数据融合以及决策支持 等。国内的学者也把d a t am i n i n g 译为数据采掘或数据开采。数据挖掘技术 是面向应用的。它不仅是面向特定数据库的简单检索查询调用，而且要对这 些数据进行微观或宏观的统计、分析、综合和推理，以指导实际问题的求解， 企图发现事件间的相互关联，甚至利用已有的数据对未来的活动进行预测。 同时还能够易于被用户理解，最好能用自然语言表达发现结果。因此数据挖 掘的研究成果很讲求实际。 从统计学角度来看：数据挖掘是指分析所观察的数据集以发现可信的数 据间的未知关系并提供给数据拥有者可理解的、新颖的和有用的归纳数据。 4 哈尔滨工程大学硕士学位论文 从数据库的观点来看：数据挖掘是指从存储在数据库、数据仓库或其它 信息仓库中的大量数据中发现有趣的知识的过程”3 。 从机器学习的角度来看：数据挖掘定义为从数据中抽取隐含的、目前未 知的和潜在有用的信息。 数据挖掘过程是种决策支持过程，例如在企业客户分析决策过程中， 其高度自动化地分析企业原有历史数据，做出归纳性的推理，从中挖掘出潜 在的模式，预测客户的行为，帮助企业的决策者调整市场策略、减少风险、 做出正确的决策。 本质上，数据挖掘( d m ) 与数据库中的知识发现( k d d ) 是不同的，虽然有很 多人将数据挖掘和k d d 等同看待，其实数据挖掘仅仅是数据库中的知识发现 ( k d d ) 的一个环节，是采用具体的数据挖掘算法从数据中自动高效地提取有用 模式的过程，而k d d 是包含数据挖掘、数据准备等环节的循环往复过程。 数据挖掘是一个交叉的学科领域，包括了数据库技术、统计学、机器学 习、可视化和信息科学。数据挖掘中主要采用的技术有神经网络、模糊理论、 粗糙集理论、知识表示、归纳逻辑和高性能计算等。 2 1 2 数据挖掘的分类 数据挖掘作为一个交叉性的学科领域，受到了多个学科的影响，包括上 面提到的数据库系统、统计学、机器学习、可视化和信息科学等。由于数据 挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不同类型的数 据挖掘系统。弄清楚数据挖掘的分类，有助于帮助用户区分数据挖掘系统， 确认最满足其需要的数据挖掘系统。根据不同的分类标准，数据挖掘系统可 以分类如下： 1 基于数据库类型的分类 根据数据模型分为：关系型数据挖掘系统、对象型数据挖掘系统、对象 关系型数据挖掘系统、事务型数据挖掘系统、基于数据仓库的数据挖掘系统 等。 根据所处理数据的特定类型分为：演绎数据挖掘系统、空闯数据挖掘系 统、时间序列数据挖掘系统、多媒体数据挖掘系统、文本数据挖掘系统、万 维网数据挖掘系统等。 哈尔滨工程大学硕士学位论文 2 基于所挖掘知识类型的分类 根据所挖掘的知识类型分为：特征( c h a r a c t e r i z a t i o n ) 、区分 ( d i s c r i m i n a t i o n ) 、关联( a s s o c i a t j o n ) 、分类( c l a s s i f i c a t i o i l ) 、聚类 ( c l u s t e r i n g ) 、孤立点分析( 异常数据) ( o u t l i e r ) 、演变分析( e v o l u t i o n a n a l y s i s ) 、偏差分析( d e v i a t i o i la n a l y s i s ) 、相似性分析( s i m i l a r i t y a n a l y s i s ) 等。其中，特征规则挖掘系统，用于从与学习任务相关的一组数 据中提取这些数据的特征式，特征式表达了该数据集的总体特征，即主要采 集隐含于目标数据库中的特征规则集合。区分规则挖掘系统，发现和提取待 学习数据( 目标数据) 的某些特征或属性，使之与对比数据区分，即采集隐 含于数据库中的数据的偶然性、相关于特定模型的趋势等，形成区分模型的 相似匹配的规则。关联规则挖掘系统，通过关联性发现一组项目之间的关联 关系和相关关系，并将这些关系表示为规则形式，即在数据集中采集关联规 则的集合。分类规则挖掘系统，产生对大量的数据的分类，采集相应的分类 规则的集合。聚类规则挖掘系统，搜索并识别一个有限的种类的集合或簇集 合，以描述数据；聚类也意味着基于概念聚类、原理聚类一个数据集( 识别 一组聚类规则) ，以把类似的事件聚合在一起。孤立点是指不符合数据的一般 模式的数据对象，孤立点分析即挖掘这样的孤立点。偏差分析规则挖掘系统， 用于探测现状、历史记录或标准之间的显著变化和偏差，采集不同概念层测 试的阈值，形成检测规则的集合。3 ，等等。一个全面的数据挖掘系统应该提 供多种的或集成的数据挖掘功能。 数据挖掘系统还可以根据所挖掘知识的粒度或抽象层进行分类，包括： 一般性知识挖掘系统、原始层知识挖掘系统、多层知识挖掘系统等。其中一 般性知识挖掘系统，用以采集隐藏于目标数据集中数据的一般性的、概括的 知识( 高抽象层) ；原始层知识挖掘系统，用以采集隐藏于原始数据层中的数 据的规律性( 原始数据层) ；多层知识挖掘系统，则在多个抽象层上采集知识。 数据挖掘系统也可分类为挖掘数据规则性( 如通常出现的模式) 和数据不规 则性( 如异常或孤立点) 。一个高级的数据挖掘系统应当支持多抽象层的知识 发现。 3 基于所采用技术的分类 基于所采用的数据挖掘技术分类，目前主要分为：自动的数据挖掘系统、 哈尔滨工程大学硕士学位论文 证实驱动挖掘系统、发现驱动挖掘系统和交互式数据挖掘系统。 自动的数据挖掘系统，指数据挖掘系统自动地从大量的数据中发现未知 的、有用的模式，是数据挖掘的高级阶段。 证实驱动挖掘系统，通常需要用户根据经验创建假设( 或模型) ，然后使 用证实驱动操作测试假设( 或挖掘与模式匹配的数据) ，测试的过程即数据挖 掘的过程。所抽取的信息可能是事实或趋势。证实驱动数据挖掘的操作有查 询和报告、多维分析和统计分析。其中，查询的目的是有效地表示一个假设； 而报告是分析结果的说明；多维分析针对每一维的层次结构，利用特定的查 询语言和可视化工具进行分析；统计分析是将统计学与数据挖掘和可视化技 术结合进行数据分析的结果。 发现驱动挖掘系统，在目标数据集上利用历史数据自动创建模型，以预 测将来的行为，模式创建的过程即数据挖掘的过程。所挖掘的知识可能是回 归或分类模型、数据库记录间的关系、误差情况等。基于驱动技术的两种挖 掘技术，一种用于验证模式，而另一种用于创建模型。 交互式数据挖掘系统，是指利用交互式处理方式，逐渐明确数据挖掘的 目标，动态改变数据聚集及搜索方式，逐步加深数据挖掘过程的一种数据挖 掘系统。 4 基于数据挖掘方法的分类 根据所采用的数据分析方法的不同( 如面向数据库和数据仓库的方法、 机器学习的方法、统计学方法、模式识别方法、神经网络方法、可视化等) 也有不同的分类。复杂的、集成化数据挖掘系统，应集成多种数据挖掘方法 对目标数据进行挖掘。 5 基于数据挖掘应用的分类 数据挖掘系统根据其应用来分类，产生了金融数据的数据挖掘系统、电 信数据的数据挖掘系统、d n a 序列数据挖掘系统、股票市场数据挖掘系统、 w w w 数据挖掘系统等等。不同的应用通常需要集成对于该应用有效的方法， 而普通的、全功能的数据挖掘系统并不一定适合特定领域的数据挖掘任务。 2 1 3 数据挖掘的任务及内容 一、数据挖掘的任务 7 哈尔滨工程大学硕士学位论文 数据挖掘技术来自应用的需要，要对这些数据进行统计、分析、综合和 推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有 的数据对未来的活动进行预测。数据挖掘的发现任务主要是： 1 数据总结 数据总结的目的是对数据进行浓缩，给出它的紧凑描述。数据挖掘主要 关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关 数据从低层次抽象到高层次上的过程。 2 分类 分类的目的是建立一个分类函数或分类模型( 也称作分类器) ，该模型能 把数据库的数据项映射到给定类别中的某一个。例：信用卡申请者，分类为 低、中、高风险。 3 聚类 聚类是把一组个体按照相似性归类，即“物以类聚”。它的目的是使属于 同一类别的个体之间的距离尽可能地小，而不同类别的个体间的距离尽可能 地大。 例如： ( 1 ) 一些特定症状的聚集可能预示了一个特定的疾病。 ( 2 ) 租借图书类型不相似的客户聚集，可能暗示成员属于不同的亚文化 群。 4 关联规则 决定哪些事情将一起发生。是形式如下的一种规则，“在购买面包和黄油 的顾客中，有9 0 的人同时也买了牛奶”( 面包+ 黄油十牛奶) 。关联规则发现 的思路还可以用于序列模式发现。用户在购买物品时，除了具有上述关联规 律，还有时间或序列上的规律。 例如： ( 1 ) 超市中客户在购买a 的同时，经常会购买b ，即a 等b ( 关联规则) 。 ( 2 ) 客户在购买a 后，隔一段时间，会购买b ( 序列分析) 。 二、数据挖掘的内容 数据挖掘的内容最常见的有以下四类： 1 广义知识( g e n e r a l i z a t i o n ) 哈尔滨工程大学硕士学位论文 广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表 征的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物 共同性质，是对数据的概括、精炼和抽象。 广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归 约等。数据立方体还有其他一些别名，如“多维数据库”、“实现视图”、“o l a p ” 等。该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如 计数、求和、平均值、最大值等，并将这些实现视图储存在多维数据库中。 既然很多聚集函数需经常重复计算，那么在多维数据立方体中存放预先计算 好的结果将能保证快速响应，并可灵活地提供不同角度和不同抽象层次上的 数据视图。另一种广义知识发现方法是加拿大s i m o nf r a s e r 大学提出的面向 属性的归约方法。这种方法以类s q l 语言表示数据挖掘查询，收集数据库中 的相关数据集，然后在相关数据集上应用一系列数据推广技术进行数据推广， 包括属性删除、概念树提升、属性阈值控制、计数及其他聚集函数传播等。 2 关联知识( a s s o c i a t i o n ) 它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属 性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。 最为著名的关联规则发现方法是ra g r a w a l 提出的a p r i o r i 算法。关联规则 的发现可分为两步。第一步是迭代识别所有的频繁项目集，要求频繁项目集 的支持率不低于用户设定的最低值：第二步是从频繁项目集中构造置信度不 低于用户设定的最低值的规则。识别或发现所有频繁项目集是关联规则发现 算法的核心，也是计算量最大的部分。 3 分类知识( c l a s s i f i c a t i o n c l u s t e r i n g ) 它反映同类事物共同性质的特征型知识和不同事物之间的差异特征型知 识。最为典型的分类方法是基于决策树的分类方法。它是从实例集中构造决 策树，是一种有指导的学习方法。该方法先根据训练子集( 又称为窗口) 形 成决策树。如果该树不能对所有对象给出正确的分类，那么选择一些例外加 入到窗口中，重复该过程一直到形成正确的决策集。最终结果是一棵树，其 叶结点是类名，中间结点是带有分枝的属性，该分枝对应该属性的某一可能 值。最为典型的决策树学习系统是i d 3 ，它采用自顶向下不回溯策略，能保 证找到一个简单的树。 9 哈尔滨工程大学硕士学位论文 数据分类还有统计、粗糙集( r o u g h s e t ) 等方法。线性回归和线性辨别 分析是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分 类器。最近也有人研究使用神经网络方法在数据库中进行分类和规则提取。 4 预测型知识( p r e d i c t i o n ) 它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也 可以认为是以时间为关键属性的关联知识。 目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。 1 9 6 8 年b o x 和j e n k i n s 提出了一套比较完善的时间序列建模理论和分析方 法，这些经典的数学方法通过建立随机模型，如自回归模型、自回归滑动平 均模型、求和自回归滑动平均模型和季节调整模型等，进行时间序列的预测。 由于大量的时间序列是非平稳的，其特征参数和数据分布随着时间的推移而 发生变化。因此，仅仅通过对某段历史数据的训练，建立单一的神经网络预 测模型，还无法完成准确的预测任务。为此，人们提出了基于统计学和基于 精确性的再训练方法，当发现现存预测模型不再适用于当前数据时，对模型 重新训练，获得新的权重参数，建立新的模型。也有许多系统借助并行算法 的计算优势进行时间序列预测。 2 2数据挖掘的过程 2 2 1 确定挖掘对象 清晰地定义出挖掘对象，认清挖掘的目的是数据挖掘的重要一步。挖掘 的最终结构是不可预测的，但要探索的问题应该是有预见的，为了数据挖掘 而数据挖掘则带有盲目性，是不会成功的。 2 2 2 数据准备 数据准备对于数据挖掘的成功应用至关重要，如果没有数据的预处理阶 段，单纯进行数据挖掘将成为一个盲目搜索的过程，可能会得出毫无意义或 错误的结果。数据准备大致分为3 步： 1 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于 数据挖掘应用的数据。 哈尔滨工程大学硕士学位论文 2 数据的预处理 研究数据的质量，为进一步的分析作准备。并确定将要进行的挖掘操作 的类型。 3 数据的转换 将数据转换成一个分析模型。建立一个真正适合挖掘算法的分析模型是 数据挖掘成功的关键。 2 2 3 挖掘知识和信息 作为数据挖掘技术的核心，知识与信息的挖掘主要有下面几部分构成： 1 确定挖掘的任务类型。确定系统要实现的功能及任务，是属于分类或 关联等中哪种类型。 2 选择合适的挖掘技术。在确定挖掘任务的基础上，选择适当的数据挖 掘技术。如分类模型常由有指导的神经元网络或归纳技术( 如决策树) 来实现； 聚类常用聚类分析技术：关联分析使用关联发现和序列发现技术等。 3 选择算法。根据选定的技术选择一具体的算法，如采用i d 3 算法为定 性的变量建立分类模型；b p 算法用于解决连续的定量变量的情况等。 4 挖掘数据。用选定的算法或算法组合在模式空间中进行反复迭代的搜 索，从数据集合中抽取出隐藏的、新颖的模式。 2 2 4 模式的解释和评价 对数据挖掘发现的模式进行解释和评价，过滤出有用的知识。具体包括 消除无关的、多余的模式，过滤出要呈现给用户的信息：利用可视化技术将 有意义的模式以图形或逻辑可视化的形式表示，转化为用户可理解的语言。 可用于解释当前或历史现象，预测未来可能发生的情况，使决策者参照从过 去发生的事实中抽取的信息迸行决策制定。 2 3数据挖掘的未来发展趋势 自从数据挖掘的概念提出之后，数据挖掘的研究得到了国内外学者的广 泛关注和深入的研究，数据挖掘技术也日臻成熟和完善。但当前数据挖掘研 究和应用的整体水平仍然处于起步阶段，还存在许多问题需要解决，概括说 来，未来数据挖掘的研究主要集中在以下几个方向： 哈尔滨工程大学硕士学位论文 1 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言， 也许会像s q l 语言一样走向现代化和标准化。 2 寻求数据挖掘过程的可视化方法，使知识发现的过程能够被用户理解， 也便于在知识发现的过程中进行人机交互。 3 研究网络环境下的数据挖掘技术( w e bm i n i n g ) ，特别是在i n t e r n e t 上建立数据挖掘服务器，并且与数据库服务器整合，实现w e bm i n i n g 。 4 加强对各种非结构化数据的挖掘，如文本数据、图形数据、视频图像 数据、声音数据乃至综合多媒体数据的挖掘。 5 证实技术，数据挖掘使用特定的分析方法或逻辑形式发现知识，但是 系统缺乏交互证实( c r o s s v a l i d a t i o n ) 所发现知识的能力，另一种情况是 待挖掘的数据本身可能存在错误，数据挖掘技术必须能够确定结论具有何种 程度的有效性。 2 4本章小结 本章首先对数据挖掘进行概述：给出了数据挖掘的定义、分类及数据挖 掘的任务和本质；接着描述了数据挖掘的过程：包括确定挖掘对象、数据准 备、挖掘知识和信息及模式的解释和评价；最后展望了数据挖掘的未来发展 趋势。 哈尔滨工程大学硕士学位论文 第3 章关联规则研究 3 1关联规则的基本概念 在数据挖掘的知识模式中，关联规则模式是比较重要的一种，也是最活 跃的一个分支。关联规则表示数据库中一组对象之间某种关联关系的规则。 例如，关联规则可以表示为“购买了项目a 和b 的顾客中有9 5 的人又买了c 和d ”。从这些规则可找出顾客购买行为模式，可以应用于商品货架设计、生 产安排、针对性的市场营销等。 采用关联模型比较典型的例子是“啤酒和尿布”的故事。关联规则问题 由a g r a w a l 等人于1 9 9 3 年首先提出，随即引起了广泛的关注。许多研究者( 包 括r a g r a w a l 本人) 对关联规则挖掘问题进行深入的研究，对最初的关联规 则挖掘算法进行了改进和扩展。同时，关联规则的挖掘被应用到许多其它领 域的数据库，取得了良好的挖掘效果。 为了准确地描述关联规则挖掘问题，便于问题的讨论，给出关联规则挖 掘问题的正式定义： 定义3 1 关联规则挖掘的数据集记为d ( d 为事务数据库) ，d = ( ，t 。， “，j ，如= ，i 2 ，f ，i p ( k 2 i ，2 ，n ) 为一条事务； f ，中的元素i i ( j ：1 ，2 ，p ) 称为项目( i t e m ) 。 定义3 2 设i = ( ，f 2 ， 是事务数据库d 中全体项目组成的集合， i 的任何子集x 称为d 中的项目集( i t e m s e t ) ，f x f = k 称集合x 为k 项目集。 设气和x 分别为d 中的事务和项目集，如果x ，称事务f 。包含项目集x 。 事务和项目集虽然都是项目的集合，但两者有不同的含义。事务是数据 库d 的组成元素( 类似于关系数据库中的记录或元组) ，而项目仅仅是为挖掘 关联规则而规定的项目组合( 类似于关系数据库中的字段) 。事务与项目集的 包含关系表明对该事务来说，此项目集中的各个项目是相互关联的。 定义3 3 数据集d 中包含项目集x 的事务数称为项目集x 的支持数， 记为吒。项目集x 的支持率，记作：s u p p o r t ( x ) ，即概率p ( x ) 。 哈尔滨工程大学硕士学位论文 s u p p o r t ( x ) 2 面o x l o o ( 31 ) 其中| d i 是数据集d 的事务数。若s u p p o r t ( x ) 不小于用户指定的最小 支持率( 记作：m i n s u p p o r t ) ，则称x 为频繁项目集( 或大项目集) ，否则称 x 为非频繁项目集( 或小项目集) 。 定理3 4 设x 、y 是数据集d 中的项目集， ( i ) 若x y ，则s u p p o r t ( x ) s u p p o r t ( y ) ( 3 - 2 ) ( i i ) 若x c y ，如果x 是非频繁项目集，则y 也是非频繁项目集 ( i i i ) 若x c y ，如果y 是频繁项目集，则x 也是频繁项目集 定义3 5 若x 、y 为项目集，且x n y = o ，蕴涵式x j y 称为关联规则， x 、y 分别称为关联规则x j y 的前提和结论。项目集( x uy ) 的支持率称为关 联规则x j y 的支持率，是d 中事务包含( x u y ) 的百分比，即概率p ( x u y ) ， 记作：s u p p o r t ( x 号y ) 。 s u p p o r t ( x j y ) = s u p p o r t ( x u y ) = p ( x u y )( 3 - 3 ) 关联规则x j y 的置信度是d 中事务包含x 的同时也包含y 的百分比， 即条件概率p ( wx ) ，记作：c o n f i d e n c e ( x j y ) 。 c 。n f i d e n c e ( x j y ) ：s u p p o r t ( 鬲x n y ) x 1 0 0 ：p ( yl x ) ( 3 4 ) s u p p o r t t 五j 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规 则在整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。一般 来说，只有支持度和置信度均较高的关联规则才可能是用户感兴趣的、有用 的关联规则。 通常用户根据挖掘需要指定最小支持度( 记为m i n s u p p o r t ) 和最小置信 度( 记为m i n c o n f i d e n o e ) 。前者描述了关联规则的最低重要程度，后者规定 了关联规则必须满足的最低可靠性。 定义3 6 如果s u p p o r t ( x j y ) 2 m i n s u p p o r t 且c o n f i d e n c e ( x j y ) m i n c o n f i d e n c e ，称关联规则x j y 为强规则，否则称关联规则x y 为弱 规则。 关联规则的挖掘问题就是在事务数据库d 中求解所有支持度和置信度均 分别超过m i n s u p p o r t 和m i n c o n f i d e n o e 的关联规则，即要求解满足s u d d o r 1 4 哈尔滨工程大学硕士学位论文 i i i ( x j y ) m i n s u p p o r t 和c o n f i d e n c e ( x j y ) a m i n c o n f i d e n c e 的规则x j y 。 下面通过一个例子说明，设i = ( a ，b ，c ，d ，e ，f ，g ，h ，i 的分类如图3 1 。 数据库d 如表3 1 ，其中的每条记录的含义是一次购买行为所购买的商品。 令m i n s u p = 3 0 ，m i n c o n f = 6 0 。具有m i n s u p 的商品集( 大商品集) 如表3 2 。 从大商品集得到的规则如表3 3 。 a f c d e g h 图3 ，1i 的分类 表3 1 销售数据集合表3 2 频繁项目集合 交易号交易包含的商品 1 0 0c 2 0 0d ，h 3 0 0e ，h 4 0 0g 5 0 0g 6 0 0d 表3 , 3 关联规则 规 则支持度可信度 b h3 3 6 6 6 b f3 3 6 6 6 h b3 3 1 0 0 h j a3 3 1 0 0 3 2 关联规则的分类 我们将关联规则按不同的情况进行分类 商品集支持度 ( d ) 2 b ) 3 ( a ) 4 f g )2 h )2 f f 4 b ，h 2 a ，h 2 ( b ，f 2 ( a ，f 2 哈尔滨工程大学硕士学位论文 1 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值 型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 的层次的：而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品： 而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单 维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之 间的某些关系。 4 基于关联规则带约束条件与否，可以分为不带约束的关联规则和约束 性关联规刚。 我们通常所研究的关联规则，都是不带约束的关联规则。而在实际中， 用户往往并不是对所有的关联规则都感兴趣，而只想知道关于某方面的关联 规则，如那些至少包含用户指定的项目集中一项的规则等。这时就需要定义 约束条件，进行约束性关联规则的挖掘。 3 3 挖掘关联规则的步骤 关联规则挖掘的任务就是要挖掘出数据库d 中所有的强规则，可以把关 联规则挖掘划分为两个子问题。“： ( 1 ) 根据最小支持率找出数据集d 中的所有频繁项目集： ( 2 ) 根据频繁项目集和最小置信度产生关联规则。 第一个子问题的任务是迅速高效的找出d 中全部频繁项目集，是关联规 则挖掘的中心问题，是衡量关联规则挖掘算法的标准：第二个子问题求解是 比较容易的、直接的，目前所有的关联规则挖掘算法都是针对第一个子问题 而提出的。关联规则挖掘的基本模型如图3 2 。 图3 2 中d 为数据集，a l g o r i t h m 一1 为频繁项目集的搜索算法， a l g o r i t h m - 2 为关联规则的产生算法，r 为挖出的关联规则集合。用户通过指 6 哈尔滨1 程大学硕士学位论文 定m i n s u p p o r t 、m i n c o n f i d e n c e 分别与算法m g o r i t h m - i 和m g o r i t h m - 2 交 互，并通过与r 的交互对挖掘结果进行解释和评价。 图3 ，2 关联规则挖掘的基本模型 关联规则挖掘算法主要考虑的问题有两个“”“： ( i ) 减少操作。关联规则挖掘的数据集有时候可达g b 甚至t b 数量级， 频繁的i o 操作必将影响关联规则的挖掘效率，减少i o 操作主要是减少扫 描数据集d 的次数； ( 2 ) 降低需要计算支持率的项目集( 常称之为候选项目集) 的数量，使其 与频繁项目集的数量接近，候选项目集数量的降低可以节省为处理部分候选 项目集所需的计算时间和存储空间。 到目前为止，关联规则挖掘产生了大量的挖掘算法，大致可分为搜索算 法、层次算法、数据集划分算法、抽样算法等等“”“7 m 。国内外对这些算法 的研究已经有很多，层次算法有时也称为