第8章人工智能数据挖掘46

第八章数据挖掘人工智能华中师范大学计算机科学系第八章数据挖掘数据挖掘（DataMining）是一个多学科交叉研究领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术的研究成果。经过十几年的研究，产生了许多新概念和方法。特别是最近几年来，一些基本概念和方法趋于清晰，它的研究正向着更深入的方向发展。数据挖掘技术正在以一种全新的概念改变着人类利用数据的方式，它被认为是未来信息处理的骨干技术之一，网络之后的下一个技术热点。8.1数据挖掘概述8.1.1数据挖掘的定义数据挖掘（DataMining）是一门受到来自各种不同领域的研究者关注的交叉性学科，有很多不同的术语名称，除了常用的“数据挖掘”和“知识发现”之外，与数据挖掘相近的同义词有数据融合、数据分析、知识抽取、信息发现、数据采掘、知识获取、数据考古、信息收获和决策支持等。从技术的角度讲，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明，只要能支持特定的发现问题即可。实际上，利用数据挖掘从数据集中所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。8.1数据挖掘概述从商业的角度讲，数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。8.1数据挖掘概述8.1.2数据挖掘与数据库中的知识发现（1）KDD看成数据挖掘的一个特例数据挖掘系统可以在关系数据库、事务数据库、数据仓库、空间数据库（SpatialDatabase）、文本数据（TextData）以及诸如WEB等多种数据组织形式中挖掘知识，既然如此，那么可以说数据库中的知识发现只是数据挖掘的一个方面，这是早期比较流行的观点。因此，从这个意义说，数据挖掘就是从数据库、数据仓库以及其它数据存储方式中挖掘有用知识的过程。这种描述强调了数据挖掘在源数据形式上的多样性。(2)数据挖掘是KDD过程的一个步骤在“知识发现96国际会议”上，许多学者建议对这两个名词加以区分。核心思想是：KDD是从数据库中发现知识的全部过程，而DataMining则是此全部过程的一个特定的、关键步骤，这种观点有它的合理性。虽然我们可以从数据仓库、WEB等源数据中挖掘知识，但是这些数据源都是和数据库技术相关的。数据仓库是由源数据库集成而来的，即使是像WEB这样的数据源恐怕也离不开数据库技术来组织和存储抽取的信息。因此KDD是一个更广义的范畴，它包括数据清洗、数据集成、数据选择、数据转换、数据挖掘、模式生成及评估等一系列步骤。这样，我们可以把KDD看作是一些基本功能构件的系统化协同工作系统，而数据挖掘则是这个系统中的一个关键的部分。8.1数据挖掘概述（3）KDD与DataMining含义相同也有些人认为，KDD与DataMining只是叫法不一样，它们的含义基本相同。事实上，在现今的文献中，许多场合，如技术综述等，这两个术语仍然不加区分地使用着。也有人说，KDD在人工智能界更流行；DataMining在数据库界使用更多。所以，从广义的观点，数据挖掘是从大型数据集（可能是不完全的、有噪声的、不确定性的、各种存储形式的）中，挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的过程。从上面的描述中可以看出，数据挖掘概念可以在不同的技术层面上来理解，但是其核心仍然是从数据中挖掘知识。从本质来讲，数据挖掘与知识发现是有区别的，但是在很多场合人们往往不严格区分数据挖掘和数据库中的知识发现，两者互为使用。一般在科研领域中称为KDD，而在工程领域则多称为数据挖掘。8.1数据挖掘概述8.1.3数据挖掘研究的理论基础数据挖掘方法可以是基于数学理论的，也可以是非数学的；可以是演绎的，也可以是归纳的。从研究的历史看，它们可能是数据库、人工智能、数理统计、计算机科学以及其它方面的学者和工程技术人员，在数据挖掘的探讨性研究过程中创立的理论体系。1997年，Mannila对当时流行的数据挖掘的理论框架给出了综述。结合最新的研究成果，有下面一些重要的理论框架可以帮助我们准确地理解数据挖掘的概念与技术特点。模式发现架规则发现架构基于概率和统计理论微观经济学观点基于数据压缩理论基于归纳数据库理论8.1数据挖掘概述8.1.4数据挖掘与其它数据处理方法的区别及联系1．数据挖掘与传统分析方法的区别数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先未知，有效和可实用三个特征。先前未知的信息是指该信息是预先未曾预料到的，既数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值，在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系。2.数据挖掘和数据仓库大部分情况下，数据挖掘都要先把数据从数据仓库中拿到数据挖掘库或数据集市中（见图8.1）。从数据仓库中直接得到进行数据挖掘的数据有许多好处。8.1数据挖掘概述数据仓库的数据清理和数据挖掘的数据清理差不多，如果数据在导入数据仓库时已经清理过，那很可能在做数据挖掘时就没必要在清理一次了，而且所有的数据不一致的问题都已经被解决了。数据挖掘库可能是数据仓库的一个逻辑上的子集，而不一定非得是物理上单独的数据库。但如果数据仓库的计算资源已经很紧张，那最好还是建立一个单独的数据挖掘库图8.1数据挖掘苦聪数据仓库中得出8.1数据挖掘概述3.数据挖掘和在线分析处理（OLAP）数据挖掘和OLAP是完全不同的工具，基于的技术也大相径庭。OLAP是决策支持领域的一部分。传统的查询和报表工具是告诉人们数据库中都有什么，OLAP则更进一步告诉人们下一步会怎么样和如果人们采取这样的措施又会怎么样。用户首先建立一个假设，然后用OLAP检索数据库来验证这个假设是否正确。数据挖掘与OLAP不同的地方是，数据挖掘不是用于验证某个假定的模式（模型）的正确性，而是在数据库中自己寻找模型。它在本质上是一个归纳的过程。数据挖掘和OLAP具有一定的互补性。在利用数据挖掘出来的结论采取行动之前，也许要验证一下如果采取这样的行动会带来什么样的影响，那么OLAP工具能回答这些问题。8.1数据挖掘概述4.数据挖掘与机器学习和统计分析方法数据挖掘利用了人工智能（AI）和统计分析的进步所带来的好处。这两门学科都致力于模式发现和预测。数据挖掘不是为了替代传统的统计分析技术。相反，它是统计分析方法学的延伸和扩展。大多数的统计分析技术都基于完善的数学理论和高超的技巧，预测的准确度还是令人满意的，但对使用者的要求很高。而随着计算机计算能力的不断增强，我们有可能利用计算机强大的计算能力只通过相对简单和固定的方法完成同样的功能。一些新兴的技术同样在知识发现领域取得了很好的效果，如神经元网络和决策树，在足够多的数据和计算能力下，它们几乎不用人的关照自动就能完成许多有价值的功能。8.1数据挖掘概述8.1.5数据挖掘的内容随着DM和KDD研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三根强大的技术支柱：数据库、人工智能和数理统计。因此，KDD大会程序委员会曾经由这三个学科的权威人物同时来任主席。目前DMKD的主要研究内容包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘等。数据挖掘所发现的知识最常见的有以下四类。广义知识关联知识分类知识预测型知识8.1数据挖掘概述8.1.6数据挖掘的研究历史和现状数据库中发现知识（KDD）是在1989年召开的第11届国际人工智能联合学术会议(IJCAI)上首次提出的。在这届学术会议上举行了以KDD为主题的学术研讨会，在1991年、1993年和1994年相继举行了KDD专题研讨会。随着KDD的深入研究以及KDD在许多领域的成功应用，于1995年在加拿大召开了第一届知识发现和数据挖掘国际学术会议，此后每年都召开大规模的国际会议，其研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。第一本关于DM和KDD的国际学术杂志《DataMiningandKnowledgeDiscovery》也于97年3月创刊发行。亚太地区于1997年在新加坡召开了首次KDD研讨会，其后又在澳大利亚的墨尔本召开了第二届，在中国北京召开了第三届。目前，在IJCAI、AAAI、VLDB、ACM-SIGMOD等代表人工智能与数据库技术研究最高水平的国际学术会议上，数据挖掘和知识发现的研究都占有较大的比例，数据挖掘和知识发现的研究已经成为当今计算机科学与技术研究、应用的热点领域之一。8.2数据挖掘技术简介根据挖掘的任务可以分为：分类和预测模型发现、数据总结和聚类、关联规则发现、序列模式发现、相似模式发现和混沌模式发现等。根据挖掘对象来分，数据挖掘方法有面向关系数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、面向对象数据库、异质数据库以及WEB信息等。根据挖掘方法来分，数据挖掘方法可分为机器学习方法、统计方法、神经网络方法和数据库方法。其中机器学习可细分为归纳学习方法、基于范例学习、遗传算法等；统计方法可细分为回归分析、判别分析、聚类分析、探索性分析等；神经网络方法可细分为前向神经网络、自组织神经网络等；数据库方法主要是多维数据分析或联机分析方法，另外还有面向属性的归纳方法。8.2数据挖掘技术简介8.2.1分类和预测分类是数据挖掘中一项非常重要的任务，目前在商业上的应用最多。分类的目的是提出一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类和回归都可用于预测，预测的目的是从历史数据记录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺省值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合各种特点的数据。下面介绍几种常用的分类算法。8.2数据挖掘技术简介1．决策树构造一个决策树分类器通常分为两步：树的生成和剪枝。树的生成采用自上而下的递归分治法。如果当前训练例子集合中的所有实例是同类的,构造一个叶节点,节点内容即是该类别。否则,根据某种策略选择一个属性,按照该属性的不同取值,把当前实例集合划分为若干子集合。对每个子集合重复此过程,直到当前集中的实例是同类的为止。剪枝就是剪去那些不会增大树的错误预测率的分枝。经过剪枝,不仅能有效的克服噪声,还使树变得简单,容易理解。生成最优的决策树同样是NP问题。目前的决策树算法通过启发式属性选择策略来解决问题。8.2数据挖掘技术简介2．AQ算法存在大量的基于规则的分类方法，以及对规则进行后处理如剪枝等工作。AQ是一种典型的基于规则的方法。AQ是一种覆盖算法，由Micalski和洪家荣提出。算法的核心是所