1、,数据挖掘原理与算法,1,2020年4月7日星期二,DMKD Sides By MAO,By 毛国君，段立娟，王石，石云Pub.清华大学出版社，2004使用说明：本书是一本全面介绍数据挖掘和知识发现技术的 专业书籍，可作为计算机专业研究生或高年级本科生 教材。共分8章，各章相对独立成篇，以利于读者选 择性学习。本课件供全书讲解之用，为了取得好的教学效果，教师应该根据学生层次、教学大纲或课时安 排进行必要裁减。,第一章 绪论,2,2020年4月7日星期二,DMKD Sides By MAO,内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识
2、表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析,数据挖掘技术的商业需求分析,3,2020年4月7日星期二,DMKD Sides By MAO,随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，网络环境成为主流等等。产生“数据丰富而信息贫乏（Data Rich&Information Poor）”现象。在强大的商业需求的驱动下，商家们开始注意到 有效地解决大容量数据的利用问题具有巨大的商 机；学者们开始思考如何从大容量数据集中获取 有用信息和知识的方法。随着信息技术的高速发展，人们希望能够提供更 高层次的数据处理功能。新的需求推动新的
3、技术 的诞生。数据（Data）、信息（Information）和知识（Knowledge）是广义数据表现的不同形式。,数据、信息和知识,4,2020年4月7日星期二,DMKD Sides By MAO,data,information,knowledge,数据挖掘产生的技术背景,5,2020年4月7日星期二,DMKD Sides By MAO,数据挖掘是相关学科充分发展的基础上被提出和 发展的。主要的相关技术：数据库等信息技术的发展统计学深入应用人工智能技术的研究和应用,数据挖掘是一个多学科交叉技术,6,2020年4月7日星期二,DMKD Sides By MAO,Data Mining,Da
4、tabase Technology,Statistics,Other Disciplines,Information Science,AI/Machine Learning,Visualization,数据库系统的发展,7,2020年4月7日星期二,DMKD Sides By MAO,60年代：简单文件处理系统向数据库系统变革。70年代：层次、网络和关系型数据库普及。80年代：RDBS及其相关工具、数据索引及数据组 织技术被广泛采用；中期开始，分布式数据库广 发讨论，关系数据库技术和新型技术的结合。90年代：数据库领域中的新内容、新应用、新技 术层出不穷，形成了庞大的数据库家族；人们期 望分析
5、预测、决策支持等高级应用，Data mining and data warehousing等出现。本世纪开始：Data mining 得到理论/技术深化。,统计学的深入应用,8,2020年4月7日星期二,DMKD Sides By MAO,强大有效的数理统计方法和工具，已成为信息咨 询业的基础。统计分析技术是基于严格的数学理论和高超的应 用技巧的。,数据挖掘技术是数理统计分析应用的延伸和发展。和数据库技术的结合性研究,人工智能技术的研究和应用,9,2020年4月7日星期二,DMKD Sides By MAO,人工智能是计算机科学研究中争议最多而又仍始 终保持强大生命的研究领域。专家系统曾经是人
6、工智能研究工作者的骄傲，但,是诸多难题限制了专家系统的应用：,知识获取成为专家系统研究中公认的瓶颈问题。知识表示成为一大难题：知识工程师在整理表达从领域专家那里 获得的知识时勉强抽象出来的规则有很强的工艺色彩。,对常识和百科知识出奇地贫乏：人工智能学家Feigenbaum估计，一般人拥有的常识存入计算机大约有100万条事实和抽象经验法则，离开常识的专家系统有时会比傻子还傻。,数据挖掘继承了专家系统的高度实用性特点，并 且以数据为基本出发点，客观地挖掘知识。机器学习得到了充分的研究和发展：理论和算法。数据挖掘研究在继承已有的人工智能相关领域，特别是机器学习的研究成果的基础上，成为新的 研究分支。
7、,第一章 绪论,10,2020年4月7日星期二,DMKD Sides By MAO,内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析,数据挖掘处于研究和应用探索阶段,11,2020年4月7日星期二,DMKD Sides By MAO,经过十几年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成果而形成独具特色的 研究分支。大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段：一方面，数据挖掘的概念已经被广泛接受。另一方面，数据挖掘的大
8、面积应用还有待时日。随着KDD在学术界和工业界的影响越来越大，数 据挖掘的研究向着更深入和实用技术方向发展：大学等研究机构的大多数基础性研究集中在数据挖掘理论、挖掘算法等的探讨上。公司的研究更注重和实际商业问题结合。数据挖掘的经济价值已经显现出来：Gartner报告中列举重要影响的五项关键技术，其中KDD和人 工智能排名第一。,数据挖掘研究聚焦点,12,2020年4月7日星期二,DMKD Sides By MAO,数据挖掘在如下几个方面需要重点开展工作：,数据挖掘技术与特定商业逻辑的平滑集成问题：数据挖掘需要代表性的应 用实例来证明（像“啤酒与尿布”）。数据挖掘技术与特定数据存储类型的适应问题
9、：不同的数据存储方式会影响数据挖掘的具体实现机制、目标定位、技术有效性等。,大型数据的选择与规格化问题：数据的噪音、信息丢失等问题的处理；针对特定挖掘方法进行数据规格化等问题。数据挖掘系统的构架与交互式挖掘技术：,在具体的实现机制、技术路线以及各阶段的功能定位等方面仍需细化,和深入研究。,良好的交互式挖掘（Interaction Mining）也是数据挖掘系统成功的,前提。数据挖掘语言与系统的可视化问题：可视化挖掘除了要和良好的交互式技 术结合外，还必须在挖掘结果或过程的可视化进行探索和实践。,数据挖掘理论与算法研究,一方面，在已有的理论框架下有许多面向实际应用目标的挖掘理论等,待探索和创新。
10、,另一方面，随着数据挖掘技术本身和相关技术的发展，新的挖掘理论,和算法的诞生是必然的。,第一章 绪论,13,2020年4月7日星期二,DMKD Sides By MAO,内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析,14,2020年4月7日星期二,DMKD Sides By MAO,从商业角度看数据挖掘技术 数据挖掘从本质上说是一种新的商业信息处理技 术：,数据挖掘技术把人们对数据的应用，从低层次的联机查询操作，提高到决策支持、分析预测等
11、更高级应用上。,通过对数据的统计、分析、综合和推理，发现数据间的关联性、未来趋势以及一般性的概括知识等，这些知识性的信息可以用来 指导高级商务活动。从决策、分析和预测等高级商业目的看，原始数 据只是未被开采的矿山，需要挖掘和提炼才能获 得对商业目的有用的规律性知识。,从商业角度看，数据挖掘就是按企业的既定业务 目标，对大量的企业数据进行深层次分析以揭示 隐藏的、未知的规律性并将其模型化，从而支持 商业决策活动。,数据挖掘的技术含义,15,2020年4月7日星期二,DMKD Sides By MAO,数 据 库 中 的 知 识 发 现（KDD：Knowledge Discovery in Dat
12、abases）是比数据挖掘出现更早 的一个名词。KDD与Data Mining的关系，有不同的看法：KDD看成数据挖掘的一个特例：这是早期比较流行的观点，这种描 述强调了数据挖掘在源数据形式上的多样性。数据挖掘是KDD的一个关键步骤：这种观点得到大多数学者认同，有它的合理性。KDD与Data Mining含义相同：事实上，在现今的许多场合，如技术综述等，这两个术语仍然不加区分地使用着。也有其他的说法：KDD在人工智能界更流行，而Data Mining在数据库界使用 更多。在研究领域被称作KDD，在工程领域则称之为数据挖掘。,数据挖掘定义,16,2020年4月7日星期二,DMKD Sides B
13、y MAO,数据挖掘定义有广义和狭义之分。从广义的观点，数据挖掘是从大型数据集（可能是不完全的、有 噪声的、不确定性的、各种存储形式的）中，挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的过程。从这种狭义的观点上，我们可以定义数据挖掘是从特定形式的数据集中提炼知识的过程。下列技术不是数据挖掘：OLTP Expert systems Small MLStatistical programs,数据挖掘研究的理论基础,17,2020年4月7日星期二,DMKD Sides By MAO,数据挖掘方法可以是基于数学理论的，也可以是 非数学的；可以是演绎的，也可以是归纳的。从研究者可能是来自于数据库
14、、人工智能、数理 统计、计算机科学以及其他方面的学者和工程技 术人员，他们会从不同的视点进行探讨性研究。有下面一些重要的理论视点值得关注：模式发现（Pattern Discovery）架构规则发现（Rule Discovery）架构基于概率和统计理论微观经济学观点（Microeconomic View）基于数据压缩（Data Compression）理论基于归纳数据库（Inductive Database）理论可视化数据挖掘（Visual Data Mining）等等,第一章 绪论,18,2020年4月7日星期二,DMKD Sides By MAO,内容提要数据挖掘技术的产生与发展数据挖掘研究
15、的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析,根据挖掘任务,19,2020年4月7日星期二,DMKD Sides By MAO,分类或预测模型发现数据总结与聚类发现关联规则发现序列模式发现相似模式发现混沌模式发现依赖关系或依赖模型发现异常和趋势发现等,根据挖掘对象,20,2020年4月7日星期二,DMKD Sides By MAO,关系数据库挖掘面向对象数据库挖掘空间数据库挖掘时态数据库挖掘文本数据源挖掘多媒体数据库挖掘异质数据库挖掘遗产数据库挖掘web数据挖掘等,根据挖掘方法,2
16、1,2020年4月7日星期二,DMKD Sides By MAO,机器学习方法 统计方法聚类分析方法神经网络（Neural Network）方法 遗传算法（Genetic Algorithm）方法数据库方法近似推理和不确定性推理方法基于证据理论和元模式的方法现代数学分析方法粗糙集（Rough Set）或模糊集方法 集成方法等,根据知识类型,22,2020年4月7日星期二,DMKD Sides By MAO,挖掘广义型知识挖掘差异型知识挖掘关联型知识挖掘预测型知识挖掘偏离型（异常）知识挖掘不确定性知识等,第一章 绪论,23,2020年4月7日星期二,DMKD Sides By MAO,内容提要数
17、据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析,知识表示模式分类,24,2020年4月7日星期二,DMKD Sides By MAO,数据挖掘的目的是发现知识，知识要通过一定的 模式给出。通过对数据挖掘中知识表示模式及其 所采用方法的分析，可以更清楚地了解数据挖掘 系统的特点。主要知识模式类型有：广义知识（Generalization）关联知识（Association）类知识（Class/Cluster）预测型知识（Prediction）特异型知识（
18、Exception）,广义知识挖掘,25,2020年4月7日星期二,DMKD Sides By MAO,广义知识是指描述类别特征的概括性知识。这类数据挖掘 系统是对细节数据的所蕴涵的概念特征信息的概括和抽象 的过程。主要方法有：概念描述（Concept Description）方法：概念描述本质上就是对某类对 象的内涵特征进行概括：特征性（Characterization）描述：描述某类对象的共同特征。区别性（Discrimination）描述：描述不同类对象之间的区别。,多维数据分析可以看作是一种广义知识挖掘的特例,多层次概念描述问题：由数据归纳出的概念是有层次的，不同层次的概念 是对原始数
19、据的不同粒度上的概念抽象。例如，“北京工业大学”能归纳出“北京市”、“中国”、“亚洲”等层次。销售表SALES（ENO，ENAME，EAGE，VALUE，DEPT），它的每 个属性的定义域都可能存在蕴涵于领域知识内的概念延伸。例如，DEPT能归纳出公司COMPANY、城市CITY或国家COUNTRY等层次概念分层（Concept Hierarchy）技术：将低层概念集映射到高层概 念集的方法，是一个常用的处理多层次概念描述的方法。,主要的概念分层方法,26,2020年4月7日星期二,DMKD Sides By MAO,模式分层（Schema Hierarchy）：利用属性在特定背景知 识下的语
20、义层次形成不同层次的模式关联。,这种关联是一种的全序或偏序关系。例如，DEPT的模式分层结构可能是：DEPTCOMPANYCITYCOUNTRY。,集合分组分层（Set-Grouping Hierarchy）：将属性在特定 背景知识下的取值范围合理分割，形成替代的离散值或区 间集合。,例如，年龄EAGE可以抽象成20，29，30，39，40，49，50，59 或者青年，中年，老年。,操作导出分层（Operation-Drived Hierarchy）：有些属性 可能包含多类信息。,例如，一个跨国公司的雇员号可能包含这个雇员的所在的部门、城市、国 家和雇佣的时间等。对这类对象可以作为背景知识定义
21、它的结构，通过编 码解析等操作完成概念的抽象。基于规则分层（Rule-Based Hierarchy）：通过定义背景知 识的抽象规则，形成不同层次上的概念的抽象。,关联知识挖掘,27,2020年4月7日星期二,DMKD Sides By MAO,关联知识挖掘的目的就是找出数据库中隐藏的关 联信息。关联知识反映一个事件和其他事件之间的依赖或关联。关联可分为简单关联、时序（Time Series）关联、因果关联、数 量关联等。从广义上讲，关联分析是数据挖掘的本质。关联规则挖掘（Association Rule Mining）是关联 知识发现的最常用方法：关联规则的研究最早的分支之一，最著名的Apr
22、iori算法。是数据挖掘研究中比较深入的分支，许多关联规则挖掘的理论和 算法已经被提出。,类知识挖掘,28,2020年4月7日星期二,DMKD Sides By MAO,类知识（Class）刻画了一类事物，这类事物具有 某种意义上的共同特征，并明显和不同类事物相 区别。,有两个基本的方法来挖掘类知识：,分类：分类是数据挖掘中的一个重要的目标和任务，是目前的研 究和应用最多的分支之一。,分类的目的是学会一个分类模型（称作分类器），该模型能把,数据库中的数据项映射到给定类别中。,分类技术是一种有指导的学习（Supervised Learning），即,每个训练样本的数据对象已经有类标识，通过学习可
23、以形成表,达数据对象与类标识间对应的知识。,聚类：数据挖掘的目标之一是进行聚类分析。,聚类是把一组个体按照相似性归成若干类别，它的目的是使得,属于同一类别的个体之间的差别尽可能的小，而不同类别上的,个体间的差别尽可能的大。,聚类属于无指导学习（Unsupervised Learning），当一组,数据对象可以由一个概念（区别于其他的概念）来描述时，就,形成一个簇（Cluster）。刻画了数据所蕴涵的类知识。,分类中的基础方法,29,2020年4月7日星期二,DMKD Sides By MAO,决策树方法：基本的分类技术之一，如ID3及其改进算法ID4、ID5、C4.5、C5.0等；针对大训练样
24、本集的SLIQ、SPRINT、雨林（Rainforest）BOAT 等算法。贝叶斯分类：具有坚实的理论基础，理论上具有 较小的出错率。但是，它的适应性差。神经网络：作为一个相对独立的研究分支已经很早被提出，具有高度的抗干扰能力和可以对未训练数据进行分类等优点，因此产生了神经网络和 数据挖掘技术的结合性研究。遗传算法：是基于进化理论的机器学习方法。类比学习：最典型的方法是k-最临近分类（k-Nearest Neighbor Classification）方法，它属于懒 散学习法。其他方法：如粗糙集（Rough Set）、模糊集（Fuzzy Set）方法等。,主要聚类的技术,30,2020年4月7
25、日星期二,DMKD Sides By MAO,基于划分的聚类方法：k-平均算法是统计学中的一个经典 聚类方法，它以预先定义好的簇平均值，构造划分，评价 和选择他们。基于层次的聚类方法：通过对源数据库中的数据进行层次 分解，达到目标簇的逐步生成。,凝聚（Agglomeration）：由小到大逐步合并、评价。分裂（Division）由大到小逐步分裂、评价。,基于密度的聚类方法：基于密度的聚类方法是通过度量区 域所包含的对象数目来形成最终目标的。,如果一个区域的密度超过指定的值，那么它就需要进一步分解。,基于网格的聚类方法：对象空间离散化成有限的网格单元，聚类工作在这种网格结构上进行。基于模型的聚类
26、方法：每个簇假定一个模型，寻找数据对 给定模型的最佳拟和。,预测型知识挖掘,31,2020年4月7日星期二,DMKD Sides By MAO,预测型知识（Prediction）是指由历史的数据产生 的并能推测未来数据趋势的知识。预测性挖掘主要是对未来数据的概念分类和趋势 输出。分类技术可以用于产生预测型的类知识。统计学中的回归方法等可以通过历史数据直接产生对未来数据预测的连续值，因而这些预测型知识已经蕴藏在诸如趋势曲线等输 出形式中。预测型知识的挖掘可以结合经典的统计方法、神 经网络和机器学习等技术来研究。,预测型知识挖掘中的典型方法,32,2020年4月7日星期二,DMKD Sides B
27、y MAO,趋势预测模式：主要是针对那些具有时序（Time Series）属性的数据，如股票价格等，或者是序列 项目（Sequence Items）的数据，如年龄和薪水对 照等，发现长期的趋势变化等。周期分析模式：主要是针对那些数据分布和时间 的依赖性很强的数据进行周期模式的挖掘。例如，服装在某季节或所有季节的销售周期。序列模式：主要是针对历史事件发生次序的分析 形成预测模式来对未来行为进行预测。例如，预 测“三年前购买计算机的客户有很大概率会买数 字相机”。神经网络：在预测型知识挖掘中，神经网络也是 很有用的模式结构。,特异型知识挖掘,33,2020年4月7日星期二,DMKD Sides B
28、y MAO,特异型知识（Exception）是源数据中所蕴涵的极端特例或 明显区别于其他数据的知识描述，它揭示了事物偏离常规 的异常规律。特异知识挖掘的价值：例如，在Web站点发现那些区别于正常登录行为的用户特点可以防止非法 入侵。金融、电信欺诈等分类中的反常实例、不满足普通规则的特例、观测结果与模型预测值的偏 差、数据聚类外的离群值等许多技术可以扩展到特异型知识挖掘中,如：孤立点（Outlier）分析：孤立点是指不符合数据的一般模型的数据。在 类知识挖掘中，孤立点分析是不能归入正常类知识中的零散数据的再分析。,异常序列分析：在一系列行为或事件对应的序列中发现明显不符合一般规 律的特异型知识。
29、特异规则发现：产生并评价虽然具有低支持度但可能很有价值的规则。,第一章 绪论,34,2020年4月7日星期二,DMKD Sides By MAO,内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析,数据挖掘方法与数据存储类型,35,2020年4月7日星期二,DMKD Sides By MAO,数据挖掘技术应该应用到任何数据存储方式的知 识挖掘中，但是因为源数据的存储类型的不同，挖掘的挑战性和技术会不同。,近年来的研究表明数据挖掘所涉及的数据存储
30、类 型越来越丰富，除了一些有通用价值的模型、构 架等研究外，也开展了一些针对复杂或新型数据 存储方式下的挖掘技术或算法的研究。主要的数据类型：事务数据库（Transactional Database）关系型数据库（Related Database）数据仓库（Data Warehouse）在关系模型基础上发展的新型数据库面向应用的新型数据源Web数据,事务数据库中的数据挖掘,36,2020年4月7日星期二,DMKD Sides By MAO,一个事务数据库是对事务型数据的收集。1993年，当Agrawal等开始讨论数据挖掘问题时，是以购物 篮分析（Market Basket Analysis）作
31、为商业应用背景的。从事务数据库中发现知识是数据挖掘中研究较早 但至今仍然很活跃的问题。通过特定的技术对事 务数据库进行挖掘，可以获得动态行为所蕴藏的 关联规则、分类、聚类以及预测等知识模式。第三章将详细讲解,关系型数据库中的数据挖掘,37,2020年4月7日星期二,DMKD Sides By MAO,关系型数据库是由一系列数据表组成的，相当成熟：,成熟的语义模型（像实体-关系模型）；成熟的DBMS（像Oracle）成熟的查询语言（像SQL语言；可视化的辅助工具和优化软件。,一些更深入和亟待解决的问题：多维知识挖掘：传统的事务数据库挖掘所研究的知识一般是单维（Single-Demension）的
32、，但是，在关系型数据库中，多维的知识更普遍 和有应用价值。单维：“购买计算机的人也购买打印机”。多维：“什么样购买计算机的人也购买打印机的可能性更大？”。,多表挖掘：关系型数据库是一系列表的集合。因此，多表挖掘是必然的。数量数据挖掘：关系型数据库经常包含非离散数量属性（如工资）。多层知识挖掘：数据及其关联总是可在多个不同的概念层上来理解它。知识评价问题：对传统的数据挖掘框架的知识评价问题，也是关系型数据 库中数据挖掘走向实际应用必须要解决的问题。约束数据挖掘问题：数据挖掘系统在用户的约束指导下进行，可以提高挖 掘效率和准确度。,数据仓库中的数据挖掘,38,2020年4月7日星期二,DMKD S
33、ides By MAO,数据仓库中的数据是按着主题来组织的。存储的数据可以 从历史的观点提供信息。虽然目前的一些数据仓库辅助工 具可以帮助完成数据分析，但是发现蕴藏在数据内部的知 识模式及其按知识工程方法来完成高层次的工作仍需要数 据挖掘技术支持。数据挖掘不仅伴随数据仓库而产生，而且随着应用深入产 生了许多新的课题。,如果我们把数据挖掘作为高级数据分析手段来看，那么它是伴随数据仓库 技术提出并发展起来的。OLAP尽管在许多方面和数据挖掘是有区别的，但是它们在应用目标上有很大的重合度。数据挖掘更看中数据分析后所形成的知识表示模式，而OLAP更注重利用多维等高级数据模型实现数据的聚合。从某种意义上讲，我们可以把数据挖 掘看作是OLAP的高级形式，与此更接近的名词可能算是OLAM（联机分析挖 掘）。,新型数据库中的数据挖掘,39,2020年4月7日星期二,DMKD Sides By MAO,对象
