数据挖掘研究生课件第一章绪论

第一章绪论

内容提要数据挖掘技术的产生与发展

数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析数据挖掘技术的商业需求分析随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，网络环境成为主流等等。产生“数据丰富而信息贫乏（DataRich&InformationPoor）”现象。在强大的商业需求的驱动下，商家们开始注意到有效地解决大容量数据的利用问题具有巨大的商机；学者们开始思考如何从大容量数据集中获取有用信息和知识的方法。随着信息技术的高速发展，人们希望能够提供更高层次的数据处理功能。新的需求推动新的技术的诞生。数据（Data）、信息（Information）和知识（Knowledge）是广义数据表现的不同形式。数据、信息和知识datainformationknowledge数据挖掘产生的技术背景数据挖掘是相关学科充分发展的基础上被提出和发展的。主要的相关技术：数据库等信息技术的发展统计学深入应用人工智能技术的研究和应用数据挖掘是一个多学科交叉技术

DataMiningDatabaseTechnologyStatisticsOtherDisciplinesInformationScienceAI/MachineLearningVisualization数据库系统的发展60年代：简单文件处理系统向数据库系统变革。70年代：层次、网络和关系型数据库普及。

80年代：RDBS及其相关工具、数据索引及数据组织技术被广泛采用；中期开始，分布式数据库广发讨论，关系数据库技术和新型技术的结合。90年代：数据库领域中的新内容、新应用、新技术层出不穷，形成了庞大的数据库家族；人们期望分析预测、决策支持等高级应用，Datamininganddatawarehousing等出现。本世纪开始：Datamining得到理论/技术深化。统计学的深入应用强大有效的数理统计方法和工具，已成为信息咨询业的基础。统计分析技术是基于严格的数学理论和高超的应用技巧的。数据挖掘技术是数理统计分析应用的延伸和发展。和数据库技术的结合性研究人工智能技术的研究和应用人工智能：争议最多，强大生命专家系统曾经的骄傲，但是诸多难题：知识获取成为专家系统研究中公认的瓶颈问题。知识表示成为一大难题：知识工程师与领域专家。对常识和百科知识出奇地贫乏：人工智能学家Feigenbaum估计，一般人拥有的常识存入计算机大约有100万条事实和抽象经验法则，离开常识的专家系统有时会比傻子还傻。数据挖掘继承了专家系统的高度实用性特点，并且以数据为基本出发点，客观地挖掘知识。机器学习得到了充分研究和发展：理论和算法。数据挖掘研究在继承已有的人工智能，特别是机器学习的研究成果基础上，成为新的研究分支。第一章绪论

内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势

数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析数据挖掘处于研究和应用探索阶段经过十几年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成果、独具特色支。大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段：一方面，数据挖掘的概念已经被广泛接受。另一方面，数据挖掘的大面积应用还有待时日。随着KDD在学术界和工业界的影响越来越大，数据挖掘的研究向着更深入和实用技术方向发展：大学等研究机构的大多数基础性研究集中在数据挖掘理论、挖掘算法等的探讨上。公司的研究更注重和实际商业问题结合。数据挖掘的经济价值已经显现出来：Gartner报告中列举重要影响的五项关键技术，其中KDD和人工智能排名第一。数据挖掘研究聚焦点数据挖掘在如下几个方面需要重点开展工作：数据挖掘技术与特定商业逻辑的平滑集成问题：“啤酒与尿布”数据挖掘技术与特定数据存储类型的适应问题：大型数据的选择与规格化问题：数据的噪音、信息丢失等问题的处理；针对特定挖掘方法进行数据规格化等问题。数据挖掘系统的构架与交互式挖掘技术：在具体的实现机制等方面仍需细化和深入研究。良好的交互式挖掘（InteractionMining）。数据挖掘语言与系统的可视化问题数据挖掘理论与算法研究一方面，面向实际应用目标的挖掘理论等待探索和创新。另一方面，随着数据挖掘技术本身和相关技术的发展。第一章绪论

内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析从商业角度看数据挖掘技术数据挖掘从本质上是一种新商业信息处理技术：从低层次的联机查询，提高到决策支持、分析预测等高级应用。通过对数据的统计、分析、综合和推理，发现数据间的关联性、未来趋势以及一般性的概括知识等，这些知识性的信息可以用来指导高级商务活动。从决策、分析和预测等高级商业目的看，原始数据只是未被开采的矿山，需要挖掘和提炼才能获得对商业目的有用的规律性知识。从商业角度看，数据挖掘是按企业的既定业务目标，对大量企业数据进行深层次分析以揭示隐藏、未知的规律性并将其模型化，支持商业决策。数据挖掘的技术含义数据库中的知识发现（KDD：KnowledgeDiscoveryinDatabases）是比数据挖掘出现更早的一个名词。KDD与DataMining的关系，有不同的看法：KDD看成数据挖掘的一个特例：这是早期比较流行的观点。数据挖掘是KDD的一个关键步骤：这种观点得到大多数学者认同。KDD与DataMining含义相同：事实上，在现今的许多场合，如技术综述等，这两个术语仍然不加区分地使用着。也有其他的说法：KDD在人工智能界更流行，而DataMining在数据库界更多。在研究领域被称作KDD，在工程领域则称之为数据挖掘。数据挖掘定义数据挖掘定义有广义和狭义之分。从广义的观点，数据挖掘是从大型数据集（可能是不完全的、有噪声的、不确定性的、各种存储形式的）中，挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的过程。从这种狭义的观点上，我们可以定义数据挖掘是从特定形式的数据集中提炼知识的过程。下列技术不是数据挖掘：OLTPExpertsystemsSmallMLStatisticalprograms

数据挖掘研究的理论基础数据挖掘方法可以是基于数学理论的，也可以是非数学的；可以是演绎的，也可以是归纳的。从研究者可能是来自于数据库、人工智能、数理统计、计算机科学以及其他方面的学者和工程技术人员，他们会从不同的视点进行探讨性研究。有下面一些重要的理论视点值得关注：模式发现（PatternDiscovery）架构规则发现（RuleDiscovery）架构基于概率和统计理论微观经济学观点（MicroeconomicView）基于数据压缩（DataCompression）理论基于归纳数据库（InductiveDatabase）理论可视化数据挖掘（VisualDataMining）等等第一章绪论

内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析根据挖掘任务分类或预测模型发现数据总结与聚类发现关联规则发现序列模式发现相似模式发现混沌模式发现依赖关系或依赖模型发现异常和趋势发现等根据挖掘对象关系数据库挖掘面向对象数据库挖掘空间数据库挖掘时态数据库挖掘文本数据源挖掘多媒体数据库挖掘异质数据库挖掘遗产数据库挖掘web数据挖掘等根据挖掘方法机器学习方法统计方法聚类分析方法神经网络（NeuralNetwork）方法遗传算法（GeneticAlgorithm）方法数据库方法近似推理和不确定性推理方法基于证据理论和元模式的方法现代数学分析方法粗糙集（RoughSet）或模糊集方法集成方法等根据知识类型挖掘广义型知识挖掘差异型知识挖掘关联型知识挖掘预测型知识挖掘偏离型（异常）知识挖掘不确定性知识等第一章绪论

内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析知识表示模式分类数据挖掘的目的是发现知识，知识要通过一定的模式给出。通过对数据挖掘中知识表示模式及其所采用方法的分析，可以更清楚地了解数据挖掘系统的特点。主要知识模式类型有：广义知识（Generalization）关联知识（Association）类知识（Class/Cluster）预测型知识（Prediction）特异型知识（Exception）

广义知识挖掘广义知识是指描述类别特征的概括性知识。对细节数据的所蕴涵的概念特征的概括和抽象的过程。主要方法有：概念描述（ConceptDescription）：对某类对象内涵特征的概括：特征性（Characterization）描述：描述某类对象的共同特征。区别性（Discrimination）描述：描述不同类对象之间的区别。多维数据分析可以看作是一种广义知识挖掘的特例多层次概念描述问题：由数据归纳出的概念是有层次的。例如，“北京工业大学”能归纳出“北京市”、“中国”、“亚洲”等层次。销售表SALES（ENO，ENAME，EAGE，VALUE，DEPT），它的每个属性的定义域都可能存在蕴涵于领域知识内的概念延伸，如DEPT。概念分层（ConceptHierarchy）技术：将低层概念集映射到高层概念集的方法，是一个常用的处理多层次概念描述的方法。主要的概念分层方法模式分层（SchemaHierarchy）：利用属性在特定背景知识下的语义层次形成不同层次的模式关联。这种关联是一种的全序或偏序关系。例如，DEPT的模式分层结构可能是：DEPT→COMPANY→CITY→COUNTRY。集合分组分层（Set-GroupingHierarchy）：将属性在特定背景知识下的取值范围合理分割，形成替代的离散值或区间集合。例如，年龄EAGE可以抽象成{[20，29]，[30，39]，[40，49]，[50，59]}或者{青年，中年，老年}。操作导出分层（Operation-DrivedHierarchy）：有些属性可能包含多类信息。例如，一个跨国公司的雇员号可能包含这个雇员的所在的部门、城市、国家和雇佣的时间等。对这类对象可以作为背景知识定义它的结构，通过编码解析等操作完成概念的抽象。基于规则分层（Rule-BasedHierarchy）：通过定义背景知识的抽象规则，形成不同层次上的概念的抽象。关联知识挖掘关联知识挖掘的目的就是找出数据库中隐藏的关联信息。关联知识反映一个事件和其他事件之间的依赖或关联。关联可分为简单关联、时序（TimeSeries）关联、因果关联、数量关联等。从广义上讲，关联分析是数据挖掘的本质。关联规则挖掘（AssociationRuleMining）是关联知识发现的最常用方法：关联规则的研究最早的分支之一，最著名的Apriori算法。是数据挖掘研究中比较深入的分支，许多关联规则挖掘的理论和算法已经被提出。类知识挖掘类知识（Class）刻画了一类事物，这类事物具有共同特征，并明显和不同类事物相区别。

有两个基本的方法来挖掘类知识：分类：分类是数据挖掘中的一个重要的目标和任务，研究最多。分类的目的是学会一个分类模型（称作分类器）：数据→类分类技术是一种有指导的学习（SupervisedLearning）。聚类：数据挖掘的目标之一是进行聚类分析。聚类是把一组个体按照相似性归成若干类别，目的是使属于同一类别的个体之间的差别尽可能小，而不同类别上的个体间的差别尽可能的大。聚类属于无指导学习（UnsupervisedLearning）），形成的簇（Cluster），刻画了数据所蕴涵的类知识。分类中的基础方法决策树方法：基本分类技术之一，如ID3及改进算法ID4、ID5、C4.5、C5.0等；针对大训练样本集的SLIQ、SPRINT、雨林（Rainforest）BOAT等。贝叶斯分类：具有坚实的理论基础，理论上具有较小的出错率。但是，它的适应性差。神经网络：作为一个相对独立的研究分支已经很早被提出，高的抗干扰能力，可以对未训练数据进行分类等优点。遗传算法：是基于进化理论的机器学习方法。类比学习：最典型的方法是k-最临近分类（k-NearestNeighborClassification）方法，它属于懒散学习法。其他方法：如粗糙集（RoughSet）、模糊集（FuzzySet）方法等。

主要聚类的技术基于划分的聚类方法：k-平均算法是统计学中的一个经典聚类方法，它以预先定义好的簇平均值，构造划分。基于层次的聚类方法：通过对源数据库中的数据进行层次分解，达到目标簇的逐步生成。凝聚（Agglomeration）：由小到大逐步合并、评价。分裂（Division）由大到小逐步分裂、评价。基于密度的聚类方法：基于密度的聚类方法是通过度量区域所包含的对象数目来形成最终目标的。如果一个区域的密度超过指定的值，那么它就需要进一步分解。基于网格的聚类方法：对象空间离散化成有限的网格单元，聚类工作在这种网格结构上进行。基于模型的聚类方法：每个簇假定一个模型，寻找数据对给定模型的最佳拟和。预测型知识挖掘预测型知识（Prediction）是指由历史的数据产生的并能推测未来数据趋势的知识。预测性挖掘主要是对未来数据的概念分类和趋势输出。分类技术可以用于产生预测型的类知识。统计学中的回归方法等可以通过历史数据直接产生对未来数据预测的连续值，因而这些预测型知识已经蕴藏在诸如趋势曲线等输出形式中。预测型知识的挖掘可以结合经典的统计方法、神经网络和机器学习等技术来研究。预测型知识挖掘中的典型方法趋势预测模式：主要是针对那些具有时序（TimeSeries）属性的数据，如股票价格等，或者是序列项目（SequenceItems）的数据，如年龄和薪水对照等，发现长期的趋势变化等。周期分析模式：主要是针对那些数据分布和时间的依赖性很强的数据进行周期模式的挖掘。例如，服装在某季节或所有季节的销售周期。序列模式：主要是针对历史事件发生次序的分析形成预测模式来对未来行为进行预测。例如，预测“三年前购买计算机的客户有很大概率会买数字相机”。神经网络：在预测型知识挖掘中，神经网络也是很有用的模式结构。特异型知识挖掘特异型知识（Exception）是源数据中所蕴涵的极端特例或明显区别于其他数据的知识描述，它揭示了事物偏离常规的异常规律。特异知识挖掘的价值：例如，在Web站点发现那些区别于正常登录行为的用户特点以防止入侵。金融、电信欺诈等分类中的反常实例、不满足普通规则的特例、观测结果与模型预测值的偏差、数据聚类外的离群值等许多技术可以扩展到特异型知识挖掘中,如：孤立点（Outlier）分析：孤立点是指不符合数据一般模型的数据。在类知识挖掘中，孤立点分析是不能归入正常类知识中的零散数据再分析。异常序列分析：在一系列行为或事件对应的序列中发现明显不符合一般规律的特异型知识。特异规则发现：产生并评价虽然具有低支持度但可能很有价值的规则。第一章绪论

内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题

粗糙集方法及其在数据挖掘中的应用数据挖掘的应用分析数据挖掘方法与数据存储类型数据挖掘技术应该应用到任何数据存储方式的知识挖掘中，但是因为源数据的存储类型的不同，挖掘的挑战性和技术会不同。近年来的研究表明数据挖掘所涉及的数据存储类型越来越丰富，除了一些有通用价值的模型、构架等研究外，也开展了一些针对复杂或新型数据存储方式下的挖掘技术或算法的研究。主要的数据类型：事务数据库（TransactionalDatabase）关系型数据库（RelatedDatabase）数据仓库（DataWarehouse）在关系模型基础上发展的新型数据库面向应用的新型数据源Web数据事务数据库中的数据挖掘一个事务数据库是对事务型数据的收集。1993年，当Agrawal等开始讨论数据挖掘问题时，是以购物篮分析（MarketBasketAnalysis）作为商业应用背景的。从事务数据库中发现知识是数据挖掘中研究较早但至今仍然很活跃的问题。通过特定的技术对事务数据库进行挖掘，可以获得动态行为所蕴藏的关联规则、分类、聚类以及预测等知识模式。第三章将详细讲解关系型数据库中的数据挖掘关系型数据库是由一系列数据表组成的，相当成熟：成熟的语义模型（像实体-关系模型）；成熟的DBMS（像Oracle）成熟的查询语言（像SQL语言；可视化的辅助工具和优化软件。一些更深入和亟待解决的问题：多维知识挖掘：传统的事务数据库挖掘所研究的知识一般是单维的，但是，在关系型数据库中，多维的知识更普遍和有应用价值。单维：“购买计算机的人也购买打印机”。多维：“什么样购买计算机的人也购买打印机的可能性更大？”。多表挖掘：关系型数据库是一系列表集合。因此，多表挖掘是必然的。数量数据挖掘：关系型数据库经常包含非离散数量属性（如工资）。多层知识挖掘：数据及其关联总是可在多个不同的概念层上来理解它。知识评价问题：是关系型数据库中数据挖掘在应用必须要解决的问题。约束数据挖掘问题：在约束指导下进行，提高效率和准确度。数据仓库中的数据挖掘数据仓库中的数据是按着主题来组织的。存储的数据可以从历史的观点提供信息。虽然一些数据仓库辅助工具可以帮助完成数据分析，但是发现蕴藏在数据内部的知识模式及其按知识工程方法来完成高层次的工作仍需要数据挖掘技术支持。数据挖掘不仅伴随数据仓库而产生，而且随着应用深入产生了许多新的课题。如果我们把数据挖掘作为高级数据分析手段来看，那么它是伴随数据仓库技术提出并发展起来的。OLAP尽管在许多方面和数据挖掘是有区别的，但是它们在应用目标上有很大的重合度。数据挖掘更看中数据分析后所形成的知识表示模式，而OLAP更注重利用多维等高级数据模型实现数据的聚合。某种意义上，可以把数据挖掘看作是OLAP的高级形式，OLAM（联机分析挖掘）。新型数据库中的数据挖掘对象—关系型数据库（Object-RalationalDatabase）挖掘；面向对象数据库的挖掘；空间数据库的挖掘；时态数据库的挖掘；工程数据库（EngineeringDatabase）的挖掘；多媒体数据库（MultimediaDatabase）的挖掘；等等Web数据源中的数据挖掘随着Internet的广泛使用，Web蕴藏着丰富有用信息。面向Web的数据挖掘比面向数据库的数据挖掘要复杂多：异构数据源环境：每个站点的信息和组织都不一样；存在大量的无结构的文本信息、复杂的多媒体信息；站点使用和安全性、私密性要求各异等等。数据的复杂性：有些是无结构的（如Web页），通常都是用长的句子或短语来表达文档类信息；有些可能是半结构的（如Email，HTML页）。动态变化的应用环境：Web的信息是频繁变化的，像新闻、股票等信息是实时更新的。这种高变化也体现在页面的动态链接和随机存取上。Web上的用户是难以预测的。Web上的数据环境是高噪音的。Web挖掘的研究主要流派Web结构挖掘：挖掘Web上的链接结构。通过Web页面间的链接信息可以识别出权威页面（AuthoritativePage）、安全隐患（非法链接）等。Web使用挖掘对Web上的Log日志记录的挖掘Web上的Log日志记录了包括URL请求、IP地址及时间等访问信息。分析和发现Log日志中蕴藏的规律可以帮助我们识别潜在的客户、跟踪Web服务的质量以及侦探非法访问的隐患等。Web内容挖掘：Web的内容是丰富的，而且构成成分是复杂的（无结构的、半结构的等），对内容的分析是重要而艰巨的工作。Web的内容主要是包含文本、声音、图片等的文档信息。文本挖掘（TextMining）和Web搜索引擎（SearchEngine）等相关领域的研究。多媒体信息挖掘技术。第一章绪论

内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题粗糙集方法及其在数据挖掘中的应用

数据挖掘的应用分析粗糙集理论简介粗糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰科学家Z.Pawlak在1982年首先提出的。粗糙集一经提出就立刻引起数据挖掘研究人员的注意，并被广泛讨论。粗糙集的知识形成思想可以概括为：一种类别对应于一个概念，知识由概念组成。粗糙集对不精确概念的描述方法是通过下近似（LowerApproximation）和上近似（UpperApproximation）概念来表示：一个概念（或集合）的下近似概念（或集合）中的元素肯定属于该概念（或集合）一个概念（或集合）的上近似概念（或集合）只是可能属于该概念。信息系统粗糙集把客观世界抽象为一个信息系统。一个信息系统Ｓ是四元组Ｓ＝＜Ｕ，Ａ，Ｖ，ｆ＞：U是对象（或事例）的有限集合，记为U＝{x1，x2，...，xn}。A是属性的有限集合，记为A＝{A1，A2，...Am}。属性集A常常又划分为两个集合C和D，即A＝C∪D，C∩D＝，C表示条件属性集，D表示决策属性集。V是属性的值域集，记为V＝{V1，V2，...，Vm}，其中Vi是属性Ai的值域；f是信息函数（InformationFunction），即ｆ：Ｕ×ＡＶ，f（xi，Aj）∈Vj。f（e，a）的值确定记录e关于属性a的取值。基于某个属性集A的所有等价记录的集合，被定义为等价类。属于同一等价类的记录称为基于属性集A的划分。近似空间（ApproximationSpace）近似空间有一个二元组＜Ｕ，Ｒ（Ｂ）＞给出：U是对象（或事例）的有限集合，记为U＝{x1，x2，...，xn}；B是A的属性子集，R（B）是U上的二元等价关系，即R（B）={（x1，x2）|f（x1，b）=f（x2，b），b∈B}。R（B）也称无区别关系（IndiscernibilityRelation）。

R（B）把U划分为k个等价类R*（B）={X1，X2，...，Xk}。即对任意的x1，x2∈Xi，有（x1，x2）∈R（B）

；对任意的x1∈Xi，x2∈Xj，ij，有（x1，x2）

R（B）

。下近似和上近似定义对任意一个概念（或集合）O，B是U的一个子集，O的下近似定义为：其中[x]R（B）表示x在R（B）上的等价类。O的上近似定义为：设有两个属性集B1，B2，B1是B2的真子集，如果R（B1）=R（B2），则称B2可归约为B1。如果属性集B不可进一步归约，则称B是U的一个约简或归约子。粗糙集中的约简概念极小属性集：去掉任何一个属性，都将使得该属性集对应的规则覆盖反例，即导致规则与例子的不一致。极大属性集：向它加入任何一个不属于它的属性，则会使得该属性集对应的规则覆盖更少的正例。粗糙集中的约简是极小属性集，约简对应的规则为极小规则，极大属性集对应的规则为极大规则。挖掘的目标：获得的极小规则的尽可能简洁形式（即极小属性集尽可能的小）。基于极小规则和极大规则的概念，我们就可以实现极小规则和极大规则的生成。粗糙集在KDD中的应用举例规则学习和决策表推导。在保证简化后的决策系统具有与原先系统一样的分类能力的前提条件下，通过使用知识简约和范畴简约，将决策系统简化并且找到最小（最短）决策规则集合，以达到最大限度泛化的目的。知识简约。简约和相对简约在粗糙集中十分重要，它反应了一个决策系统的本质。通过对条件属性集合的简约，可以保证简化后的决策系统具有与原先系统一样的分类能力。属性相关分析。粗糙集方法中的属性重要程度可以用来衡量该属性对分类的影响程度，它与ID3中的信息增益类似，可以证明两者在一定条件下是等价的。进行数据预处理。粗糙集方法可以去掉多余属性，可提高发现效率，降低错误率等

第一章绪论

内容提要数据挖掘技术的产生与发展数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题