数据挖掘与知识发现(讲稿1---概述)

《数据挖掘与知识发现(讲稿1---概述)》由会员分享，可在线阅读，更多相关《数据挖掘与知识发现(讲稿1---概述)（24页珍藏版）》请在装配图网上搜索。

1、装订线数据挖掘与知识发现讲稿 主讲：刘以安前期基础课程：数据库、人工智能参考书：知识发现，清华大学出版社，史忠植编，2004第1章 概述随着信息社会和知识经济时代的来临，信息正以前所未有的速度膨胀。面对浩如烟海的信息资源，人类的自然智能越来越显得难于驾驭。如何用人造的智能去模仿和扩展人类的自然智能，实现信息的智能化处理，是信息社会和知识经济所面临的一个重大课题。人工智能作为一门研究机器（计算机）智能的学科，其目的是要用人工的方法和技术，研制智能机器或智能系统，来模仿、延伸和拓展人的智能。因此，人工智能是人类迈向信息、迎接知识经济挑战所必须具备的一项核心技术。难怪有人把人工智能同原子能技术、空间

2、技术一起称为20世纪的三大尖端科技成就。但人工智能系统较率低，不能应用于实际。随着计算机、Internet的普及，以及数据库（DB）技术的迅速发展和数据库管理系统（DBMS）的广泛应用，导致许多领域积累了海量数据（如，从普通的超市业务数据、信用卡记录数据、电话呼叫清单、政府统计数据到不太普通的天体图像、分子数据库和医疗记录等）。现有的DB技术大多可高效地实现数据查询、统计和维护等管理功能，但却无法发现数据中存在的关联和规则，无法根据现有的数据预测未来的发展趋势。数据库中存在着大量数据，却缺乏从这些数据中自动、高效地获取知识的手段，出现了“数据丰富，知识贫乏”的现象。此外，在数据操纵方面：信息的

3、提取及其相关处理技术却远远落后。为此，针对庞大的数据库及其中的海量数据信息源，仅依靠传统的数据检索机制和统计分析方法已远不能满足需要。需求是发展之母，数据管理系统（DBMS）和人工智能中机器学习两种技术的发展和结合，促成了在数据库中发现知识这一新技术的诞生，即基于数据库知识发现（Knowledge Discovery in Database,KDD）及其核心技术-数据挖掘产生并迅速发展起来。它的出现为自动和智能地把海量数据转化成有用的信息和知识提供了手段。1.1 知识知识不仅是人工智能领域中研究的重要对象，而且也是知识工程与知识发现处理的重要对象。什么是知识？（到目前为止，知识还没有统一的严格

4、的形式化定义）知识是人们在改造客观世界的实践中积累起来的认识和经验，是一切智能行为的基础。广义地说，知识是人们通过学习、发现或感悟到的对世界的认识总和，是人类认识的结晶。狭义地说，知识是一种有组织的经验、价值观、相关信息和洞察力的组合。与知识相关联的两个概念是数据和信息所谓数据是指人们为了描述客观世界中的具体事物而引入的一些数字、字符、文字等符号或符号的组合。如，“建国50岁”中的“建国”、“50岁”都是数据。所谓信息是指不同的有用数据组成的一种结构。如“建国80岁”，就是一条信息。数据、信息和知识间的关系是：l 数据是信息的载体和表示；l 信息是数据在特定场合下的含义，或者说信息是数据的语义

5、。如“建国80岁”。但相同的数据在不同的场合会有不同的含义。l 信息仅是对客观事物的一般性描述，它还不是知识。只有经过对其进行加工、整理、解释、挑选和改造，形成对客观世界规律性认识后才能称为知识。可见，知识是对信息进行智能性加工所形成的对客观世界规律性的认识。（如，水，在标准大气压下，加热到100度就会沸腾）实现对信息的加工过程，实际上也是一种把信息关联在一起的过程。因此，也可把有关信息关联在一起所形成的信息结构称为知识。从这种意义上讲，“信息”与“关联”是构成知识的两个要素。信息之间关联的形式很多，其中最常用的一种形式为： 如果 则 （IF THEN）如，“如果他学过人工智能课程，则他应该知

6、道什么叫知识”。1.2 什么是知识工程？知识工程的概念出现于1977年的人工智能联合会议上，由费根鲍姆教授提出的，至今也没有严格的定义，但人们普遍认为，知识工程是以知识为处理对象，借用工程化的思想，应用人工智能的原理、方法和技术去设计、构造和维护知识型系统的一门学科，是人工智能的一个应用分支。知识工程的目的是在研究知识的基础上，开发智能系统。所以，知识工程的核心则是专家系统。由此知，知识的获取、知识的表示、知识的运用便构成知识工程的三大要素。知识工程的研究内容，主要包括：基础理论研究、实用技术的开发、知识型系统工具研究和智能机等相关课题的研究。其中，基础理论研究包括：知识的本质、知识的表示、推

7、理、获取和学习方法等；实用技术主要研究解决建立知识系统过程中遇到的问题，包括：实用知识表示方法、实用知识获取技术、实用知识推理方法、知识库结构系统、知识系统体系结构、知识库管理技术、知识型系统的调试与评估技术、实用解释技术、实用接口技术等；知识型系统工具研究，主要是为了给系统的开发提供良好的环境工具，以提高系统研制的质量和缩短系统研制周期等。 知识工程系统的特点n 知识工程系统能解决专家水平的问题；n 系统能快速的进行假设和搜索解答；n 系统能做出具有专家水平的解答；n 系统具有大量的基础知识和通用的问题求解能力；n 系统应能选择问题的恰当表示方式，其中的知识型系统是一个符号系统；n 系统具有

8、自动推理的能力，能从结构步骤分析、解决、推理问题等，这些都表现出具有人工智能及其系统的特点。因此，同样可以说，知识工程是人工智能的一个重要应用分支 知识工程与人工智能的关系传统人工智能不能进入实用阶段，主要原因有n 人工智能系统的知识库中只含有少量的规则和事实；n 人工智能系统的效率极低。而知识工程是人工智能在知识信息处理方面的发展，它研究如何由计算机表示知识，进行问题的自动求解。知识工程的研究使人工智能的研究从理论转向了应用，从基于推理的模型转向基于知识的模型，是新一代计算机的重要理论基础。它的根本目的是在研究知识的基础上，开发人工智能系统，补充和扩大大脑的功能，开创人-机共同思考的时代。

9、知识工程与专家系统的关系专家系统是知识工程的核心。知识工程的发展首先决定于专家系统的发展，专家系统的发展必将推动人工智能的应用。专家系统的开发有三个基本的要素：领域专家、知识工程师、大量实例。在建立专家系统时，首先由知识工程师把领域专家的专门知识总结出来，以适当的形式存入计算机，建立起知识库（KB），根据这些专门知识，系统可以进行推理，做出判断和决策，能够解决一些只有人类专家才能解决的困难问题，专家系统主要是指软件系统。通常一个最基本的专家系统应由：知识库、数据库、推理机、解释机构、知识获取机构和用户界面6个部分组成。图1 专家系统的基本结构其主要功能描述如下： （1）知识库(Knowledg

10、e Base)知识库是指以某种存储结构存储领域专家的知识，包括事实和可行的操作与规则等。为了建立专家库，需对领域问题的专家知识，用相应的知识表示方法将其表示出来，然后再进行形式化，并经编码放入知识库中。所以，专家库的建立，首先要解决知识获取与知识表示的问题。知识获取是指知识工程师如何从领域专家那里获得将要纳入知识库的知识。知识表示要解决的问题是如何使用计算机能够理解的形式来表示和存储知识的问题。通常，知识库中的知识分为两大类型：一类是领域中的事实，称为事实性知识，这是一种广泛公用的知识，也即写在书本上的知识及常识；另一类是启发性知识，它是领域专家在长期工作实践中积累起来的经验总结。（2）数据库

11、也称全局数据库或综合数据库。是用于存储与求解问题有关的初始数据（如，事实、数据、初始状态（证据）和推理过程中得到的中间数据。如，在医疗专家系统中，数据库中存放的仅是当前患者的情况，如姓名、年龄、症状等及推理过程中得到的一些中间结果、病情等；在气象专家系统中，数据库中存放的是当前气象要素，如云量、温度、气压以及推理得到的中间结果等。由此看出，专家系统数据库只是一个存储很少的用于暂存中间信息的工作存储器（也称内涵数据库），而不是通常概念上的用于存放大量信息的数据库（也称外延数据库）。（3）推理机推理机是一组用来控制、协调整个专家系统的程序。它根据全局数据库的当前内容，从知识库中选择可匹配的规则，并

12、通过执行规则来修改数据库中的内容，再通过不断地推理导出问题的结论。推理机中包含如何从知识库中选择规则的策略和当有多个可用规则时如何消解规则冲突的策略。（4）解释机构用于向用户解释专家系统的行为，包括解释“系统是怎样得出这一结论的”、“系统为什么要提出这样的问题来询问用户”等用户需要解释的问题。（5）知识获取机构知识获取是专家系统的一种辅助功能，它可为修改知识库中的原有知识和扩充新知识提供相应手段。知识获取机构的基本任务是把知识加入到知识库中，并负责维持知识的一致性及完整性，建立起性能良好的知识库。通常，不同的专家系统，知识获取功能和实现方法差别较大。如， 有的系统首先由知识工程师向领域专家获取

13、知识，然后通过相应的知识编辑软件把知识送到知识库中； 有的系统自身就具有部分学习功能，由系统直接与领域专家对话获取知识； 有的系统具有较强的学习功能，可在系统运行过程中通过归纳、总结，得出新的知识。总之，不管采用方式，知识获取都是目前专家系统研究中的一个重要问题。所以，知识工程的概念从1977年提出至今，现已成为一门新兴的边缘学科。它是人工智能，数据库技术，数理逻辑，认知科学，心理学等学科交叉发展的结果。1.3知识发现KDD（Knowledge Discovery in Database）一词是于1989年8月在美国底特律市召开的第一届KDD国际学术会议上正式形成的。研究的问题主要有： 定性知

14、识和定量知识的发现； 知识发现方法； 知识发现的应用等。KDD的含义，由Fayyad定义为：从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。涉及几个概念：“数据集”、“模式”、“过程”、“有效性”、“新颖性”、“潜在有用性”和“最终可理解性”。数据集：数据库记录的集合F；模式：即知识，它给出了数据特性或数据之间的关系，是对数据所包含的信息更抽象的描述。按功能可以分为预测型模式和描述型模式。在实际应用中，可以细分为关联模式、分类模式、聚类模式和序列模式等。过程：通常在KDD中指多阶段的处理，涉及数据准备、模式搜索、知识评价以及反复的修改求精；该过程要求是非平凡的，意

15、思是要有一定程度的智能性、自动性；有效性：是指发现的模式对于新的数据仍保持一定的可信度；新颖性：要求发现的模式应该是新的；潜在有用性：是指发现的知识将来有实际效用，如，用于决策支持系统里可提高经济效益；最终可理解性：要求发现的模式能被用户理解，目前它主要体现在简洁性上。其中，“有效性”、“新颖性”、“潜在有用性”和“最终可理解性”综合在一起称为兴趣性。KDD的研究内容是：如何自动地去处理数据库中大量的原始数据，从中挖掘搜索出具有规则、富有意义的模式。它的发现过程主要有三个步骤： 数据准备，又包括数据选取（Data selection）、数据预处理（Data preprocessing）和数据变

16、换（Data transformation）三个子步骤； 数据挖掘（Data Mining）阶段； 结果解释和评价。即：KDD=数据准备+DM+解释评价。图1 KDD过程由上图知，知识发现的过程可粗略的理解为三部曲：数据准备（Data preparation）、数据挖掘(Data mining)以及结果的解释评估(interpreparation and evaluation)。 数据准备又可分为：数据选取、数据预处理和数据变换三个子步骤。l 数据选取的目的是确定发现任务的操作对象，即目标数据。它是根据用户的需求从原始数据库中抽取的一组数据。l 数据预处理一般包括消除噪声、推导计算缺值数据、消

17、除重复记录、完成数据类型转换（如，把连续值数据转换为离散型数据，以便符号归纳；或把离散型数据转换为连续值型数据，以便神经网络归纳）等；l 数据变换的主要目的是消减数据的维数或降维，即从初始特征中找出真正有用的特征，以减少数据开采时要考虑的特征或变量个数。 数据挖掘阶段：）确定开采的任务或目的，如数据总结、分类、聚类、关联规则发现或序列模式发现等；）确定使用的开采算法。选择实现算法有两个考虑因素：（1） 不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；（2） 用户或实际运行系统的要求，有的用户可能希望获取描述型的、容易理解的知识（如，采用规则表示的挖掘方法显然好于神经网络之类的方法），而

18、有的用户只希望获取预测准确度尽可能高的预测型知识。选择了挖掘算法后，就可以实施数据挖掘操作，获取有用的模式。 结果解释和评价，对数据挖掘发现出来的模式，应经用户或机器评价后才能成为知识。因为 ）挖掘出来的模式可能存在冗余或无关的模式，此时需将其剔除； ）挖掘出来的模式可能不满足用户要求，这时应退回到发现阶段之前，如重选数据、采取新的变换方法和新的开采算法等 ）KDD最终是要面向人类用户，因此，应对挖掘发现的模式进行可视化（如散点图、直方图等），或把结果转换为用户易懂的另一种表示，如把分类决策树转换为“ifthen”规则。由此过程可得：1、数据挖掘仅仅是整个知识发现过程中的一个步骤。挖掘质量的好

19、坏有两个影响要素：（1） 是所采用的数据挖掘技术的有效性；（2） 是采用的数据质量和数量（数据量的大小）。如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换，则挖掘的结果不会成功。2、整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现选择的数据不太满意，或使用的挖掘技术产生不了期望的结果。这时，用户需要重复先前的过程，甚至从头重新开始。3、可视化技术在数据挖掘的各个阶段都起着重要的作用。特别是在数据准备阶段，用户可能要使用散点图、直方图等统计可视化技术来显示有关数据，以期对数据有一个初步的了解，从而为更好地选取数据打下基础；在挖掘阶段，用户则要使用与领域问题有关的可视化工具

20、；在表示结果阶段，则可能要用到可视化技术以使得发现的知识更易于理解。问题：数据挖掘的可视化主要包括哪些研究内容? 目前流行的可视化技术主要有哪几种? 答: 数据挖掘的可视化主要研究包括(1) 数据的可视化: 将数据的不同粒度或不同的抽象级别用多种可视化方式进行描述.对被挖掘的原始数据的可视化有助于确定合适的模型进行数据挖掘处理;(2) 数据结果的可视化: 将数据挖掘后得到的知识和结果用可视化形式表示出来.知识表达、解释和评价的可视化有助于理解所获得的知识并检验知识的真伪和实用性；(3) 数据挖掘过程的可视化：用可视化形式描述各种挖掘过程，用户通过可视化方式可以了解挖掘数据的来源、数据的抽取过程

21、、具体的挖掘计算和推理过程等。 目前流行的可视化技术主要有：（1） 面向像素技术：其基本思想是将每个数据值映射到一个有色的像素上并将属于某个属性的数据值表示在一个独立的窗口中；（2） 几何投影技术：其目标是在多维数据集中找到“有意义”的投影，是一种平行坐标轴可视化技术。该技术通过使用相互平行而且等距的坐标轴将多维空间映射成两维显示。（3） 基于图标技术：是将一个多级数据项映射成一个图标，是一种条状图技术。在该技术中，用两维来进行坐标显示，而剩下的维则被映射成条状图标的角度或条状图标的长度；（4） 层次技术：是对多维空间进行细分，然后以一种层次的形式表示这些子空间。由于KDD是一门受到来自各种不

22、同领域的研究者关注的交叉学科（如涉及：统计学、机器学习、数据库技术、模式识别、人工智能和可视化等），因此导致了很多不同的术语名称。除KDD外，主要还有：“数据挖掘”、知识抽取（knowledge extraction）、信息发现、智能数据分析、探索式数据分析、信息收获、数据考古学（data archaeology）、数据捕捞（data dredging）等等。其中，最常用的术语是“知识发现”和“数据挖掘”。1995年在加拿大召开了第一届知识发现和数据挖掘（Data Ming, DM）国际学术会议。由于把数据库中的“数据”形象地比喻成矿床，把KDD比作从数据矿山中找到蕴藏的知识金块。从此“数据挖

23、掘”一词很快流传开来。又由于数据挖掘是KDD过程中的关键步骤，所以目前多数人不加区分地使用知识发现和数据挖掘这两个术语。相对来讲，数据挖掘主要流行于统计界、数据分析、数据库和管理信息系统界；而知识发现主要流行于人工智能和机器学习界。1.4 知识发现的对象知识发现的对象是数据集。数据集类型有：关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据库源、多媒体数据库、异质数据库以及万维网（Web）数据库等。其中，关系数据库是典型的结构化数据。目前，随着技术的发展，数据挖掘对象已逐步扩大到半结构化或非结构化数据，如Web数据、图像和视频数据以及文本数据等。1、关系数据库对关系数据库，数据挖掘方

24、法主要是研究数据库中属性之间的关系，挖掘出多个属性取值之间的规则。由于关系数据库的特点，促使了数据挖掘方法的改善。关系数据库的特点如下： 数据动态性数据的动态变化是数据库的一个主要特点。由于数据的存取和修改，使数据的内容经常发生变化，这就要求数据挖掘方法能适应这种变化。渐增式数据挖掘方法就是针对数据变化，使挖掘的规则（知识）能满足变化后的数据库内容。 数据不完整性数据不完整性主要反映在数据库中记录的域值丢失或不存在（空值）。这种不完整数据给数据挖掘带来了困难。为此，必须对数据进行预处理，填补该数据域的可能值。数据噪声由于数据录入等原因，造成错误的数据，即数据噪声。含噪声的数据挖掘会影响抽取模式

25、的准确性，并增加了数据挖掘的困难度。 数据冗余性这表现在同一信息在多处重复出现。函数依赖是一个通常的冗余形式。冗余信息可能造成错误的数据挖掘，至少有些挖掘的知识是用户不感兴趣的。为了避免这种情况发生，数据挖掘时，需要知道数据库中有哪些固有的依赖关系。 数据稀疏性表现在实例空间中数据稀疏，数据稀疏会使数据挖掘丢失有用的模式。 海量数据数据库中的数据在不断增长，已出现很多海量数据库。数据挖掘方法需要逐步适应这种海量数据挖掘，如建立有效的索引机制和快速查询方法等。2、文本数据库文本是以文字串形式表示的数据文件。文本分析包括：关键词或特征提取；相似检索；文本聚类和文本分类等。文本中的特征如人名、地名、

26、组织名等是某些文本中的重要信息，特征提取对掌握该文本的内容很重要。 关键词或特征提取一篇文本中，标题是该文本的高度概括。标题中的关键词是标题的核心内容。关键词的提取对于掌握该文本的内容至关重要。文本中的特征如人名、地名、组织名等是某些文本中的重要信息，特征提取对掌握该文本的内容很重要。 相似检索对文本中关键词的相似检索是了解文本内容的一种重要方法。如，“专家系统”与“人工智能”两个关键词是有一定联系的，研究专家系统的文本，一定属于人工智能的研究领域。 文本聚类对于文本标题中关键词（主题词）的相似匹配是对文本聚类的一种简单方法。定义关键词的相似度，将便于文本的简单聚类，类中文本满足关键词的相似度

27、，类间文本的关键词超过相似度。 文本分类将文本分类到各文本类中，一般需要采用一个算法，这些算法包括分类器算法、近邻算法等，这需要按文本中的关键词或特征的相似度来区分。3、图像与视频数据库图像与视频数据库是典型的多媒体数据库。数据以点阵信息及帧形式存储，数据量很大。图像与视频的数据挖掘包括：图像与视频特征提取；基于内容的相似检索；视频镜头的编辑与组织等。 图像与视频特征提取图像与视频特征有颜色、纹理和形状等。这些特征提取是用基于内容的相似检索。如，海水是蓝色、海滩是黄色、房屋的形状及颜色等，都需要从大量图像和视频数据中提取。 基于内容的相似检索根据图像、视频特征的分布、比例等进行基于内容的相似检

28、索，可以将图像和视频数据进行聚类以及分类，也能完成对新图像或视频的识别。如，对遥感图像或视频的识别，这种应用非常广泛，例如，森林火灾的发现与报警，河流水灾的预报等。 视频镜头的编辑与组织镜头代表一段连续动作（视频数据流）。典型的镜头编辑如足球的射门、某段新闻节目等，都需要在冗长的视频数据流中进行自动裁取。经过编辑的镜头，按某种需要重新组织，将形成特定需求的新视频节目。如足球射门集锦，某个新闻事件的连续报道等。4、Web数据库随着Internet的发展和普及，网站数目的迅速增长及上网人数的剧烈增多，使网络数据量呈指数增长，Web数据挖掘已成为新课题。Web数据挖掘具有如下特点： 异构数据集成和挖

29、掘Web上每一站点是一个数据源，各数据源都是异构的，形成了一个巨大的异构的数据库环境。将这些站点的异构数据进行集成，给用户提供一个统一的视图，才能在Web上进行数据挖掘。 半结构化数据模型抽取Web上的数据非常复杂，没有特定的模型描述。虽然每个站点上的数据是结构化的，但各自的设计对整个网络而言是一个非完全结构化的数据，称为半结构化数据。对半结构化数据模型的查询和集成，需要寻找一种半结构化模型抽取技术来自动抽取各站点的数据。如，XML是一种半结构化的数据模型，容易实现Web中的信息共享与交换。总之，Web数据挖掘正在逐步形成热点。1.5 知识发现的分类知识发现涉及多个学科，主要包括数据库、统计学

30、和机器学习等三大主要技术。数据库技术经过20世纪80年代的大发展，除关系数据库外，又陆续出现面向对象数据库、多媒体数据库、分布式数据库以及Web数据库等。数据库的应用从一般查询到模糊查询和智能查询，数据库计算已趋向并行计算。从以上数据库中挖掘知识正在兴起并已得到迅速发展。统计学是一门古老学科，现已逐渐走向社会。成为社会调查、了解民意以及制定决策的重要手段。机器学习是人工智能的重要分支。它是在专家系统获取知识出现瓶颈后发展起来的。机器学习的大部分方法和技术已演变为数据挖掘方法和技术。知识发现可按数据库类型、知识发现对象、知识发现任务、知识发现方法与技术，以及应用等几个方面进行分类。（1）按数据库

31、类型分类知识发现主要是在关系数据库中挖掘知识。随着数据库类型的不断增加，逐步出现了不同数据库的知识发现。现有：关系数据的知识发现、模糊数据的知识发现、历史数据的知识发现和空间数据的知识发现等多种不同数据库的知识发现类型。（2）按知识发现的对象分类知识发现除了对数据库这个主要的对象进行知识发现外，还有文本数据知识发现、多媒体数据知识发现和Web网数据知识发现等。由于对象不同，知识发现的方法相差很大，文本、多媒体、Web网数据均是非结构化数据，知识发现的难度将很大。（3）按知识发现的任务分类知识发现的任务主要有：关联分析、时序模式、聚类、分类、偏差检测以及预测六项。故按知识发现的任务分类有：关联规

32、则知识发现、序列知识发现、聚类知识发现、分类知识发现、偏差分析知识发现以及预测知识发现等类型。（4）按知识发现方法和技术分类归纳学习类、仿生物技术类、公式发现类、统计分析类、模糊数学类、可视化技术类等等。1.6 知识发现的方法可粗分为：统计方法、机器学习方法、神经网络方法、数据库方法和可视化方法。统计方法可细分为：回归分析、判别分析、聚类分析、探索性分析等；机器学习可细分为：归纳学习方法、基于范例学习、遗传算法等；神经网络可细分为：前向神经网络、自组织神经网络等；数据库方法主要是：多维数据分析或OLAP方法，另外还有面向属性的归纳方法。对可视化方法主要是把数据、信息和知识转化为可视的表示形式的

33、过程。1.7 知识发现的任务数据挖掘与知识发现是一个以数据库、人工智能、数理统计、可视化四大支柱技术为基础，多学科交叉、渗透、融合形成的新的交叉学科。数据挖掘的任务是从大量的数据中发现模式。根据数据挖掘的任务可分为多种类型，其中比较典型的有： 预测模型 关联分析 分类分析 聚类分析 序列分析 偏差检测 模式相似性挖掘 Web数据挖掘预测模型（Predictive Modeling）：所谓预测即从数据库或数据仓库中已知的数据推测未知的数据或对象集中某些属性的值分布。建立预测模型的常用方法： 回归分析 线性模型 关联规则 决策树预测 遗传算法 神经网络关联（Association）分析：关联规则描

34、述了一组数据项之间的密切度或关系。关联分析用于发现项目集之间的关联。在关联规则挖掘算法中，通常给出了置信度和支持度两个概念，对于置信度和支持度均大于给定阈值的规则称为强规则，而关联分析主要就是对强规则的挖掘。关联规则挖掘近几年研究较多。现在，关联规则的挖掘已经从单一概念层次关联规则的发现发展到多概念层次的关联规则的发现，并把研究的重点放在提高算法的效率和规模可收缩性上。它广泛地运用于帮助市场导向、商品目录设计客户关系管理）（CRM）和其他各种商业决策过程中。关联分析算法：APRIORI算法、DHP算法、DIC算法、PARTITION算法及它们的各种改进算法等。另外，对于大规模、分布在不同站点上

35、的数据库或数据仓库，关联规则的挖掘可以使用并行算法，如：Count分布算法、Data分布算法、Candidate 分布算法、智能Data分布算法（IDD）和DMA分布算法等。分类（Classification）分析：所谓分类是根据数据的特征为每个类别建立一个模型，根据数据的属性将数据分配到不同的组中。在实际应用过程中，分类规则可以分析分组中数据的各种属性，并找出数据的属性模型，从而确定哪些数据属于哪些组。这样就可以利用该模型来分析已有数据，并预测新数据将属于哪一个组。类的描述可以是显式的，如用一组特征概念描述；也可以是隐式的，如用一个数学公式或数学模型描述。分类分析已经成功地用于顾客分类、疾病

36、分类、商业建模和信用卡分析等。分类分析的常用方法： 约略（Rough）集 决策树 神经网络 统计分析法目前，分类方法和研究成果很多，判别方法的好坏，可从下面3个方面进行：（1）预测准确度（对非样本数据的判别准确度）； （2）计算复杂度； （3）模式简洁度（在同样效果情况下，希望决策树小或规则少）。注：在数据库中，往往存在噪声数据，缺损值和疏密不均匀等问题，他们对分类算法获取的知识将产生坏的影响。聚类(Clustering)分析：所谓聚类是指一组彼此间非常“相似”的数据对象的集合。相似的程度可以通过距离函数来表示，由用户或专家指定。聚类分析是按照某种相近程度度量方法将数据分成互不相同的一些分组。

37、每一个分组中的数据相近，不同分组之间的数据相差较大。好的聚类方法可以产生高质量的聚类，保证每一聚类内部的相似性很高，而各聚类之间的相似性很低。聚类分析的核心是将某些定性的相近程度测量方法转换成定量测试方法。采用聚类分析，系统可以根据部分数据发现规律，找出对全体数据的描述。聚类分析的常用方法： 随机搜索聚类法 特征聚类 CF树序列（Sequence）分析：序列分析主要用于分析数据仓库中的某类与时间相关的数据，搜索类似的序列或子序列，并挖掘时序模式、周期性、趋势和偏离等。例如，它可以导出类似“若AT&T股票连续上涨两天且DEC股票不下跌，则第三天IBM股票上涨的可能性为75%”的数据关系。序列模式

38、可以看成是一种特定的关联模型，它在关联模型中增加了时间属性。偏差检测（Deviation Detection）：用于检测并解释数据分类的偏差，它有助于滤掉知识发现引擎所抽取的无关信息，也可滤掉那些不合适的数据，同时可产生新的关注性事实。偏差包括很多有用的知识，如以下4类：（1） 分类中的反常实例；（2） 模式的例外；（3） 观察结果对模型预测的偏差；（4） 量值随时间的变化。偏差检测的基本方法是寻找观察结果与参照之间的差别。观察结果常常是某一个域的值或多个域值的汇总。参照是给定模型的预测、外界提供的标准或另一观察。模式相似性挖掘：用于在时间数据库或空间数据库中搜索相似模式时，从所有对象中找出用

39、户定义范围内的对象；或找出所有元素对，元素对中两者的距离小于用户定义的距离范围。模式相似性挖掘的方法有相似度测量法、遗传算法等。Web数据挖掘：万维网是一个巨大的、分布广泛的和全球性的信息服务中心，其中包含了丰富的超链接信息，为数据挖掘提供了丰富的资源。Web数据挖掘包括Web使用模式挖掘、Web结构挖掘和Web内容挖掘等。Web使用模式挖掘：在Web环境中，文档和对象一般都是通过链接来便于用户访问。捕捉用户的存取模式或发现一个Web网站最频繁的访问路径称为Web使用模式挖掘或Web路径挖掘。Web结构挖掘：是挖掘Web的链接结构，并找出关于某一主题的权威网站。Web内容挖掘：是指在大量训练样

40、本的基础上，得到数据对象之间的内在特征，并以此为依据进行有目的的信息筛选，从而获得指定内容的信息。基于Web的研究：搜索引擎的设计、文件自动分类技术、关键词的自动提取、半结构化信息的提取及Web上新型应用的研究等。1.8 数据挖掘的知识表示数据挖掘各种方法获得的知识的表示形式主要有6种：规则、决策树、知识基（浓缩数据）、网络权值、公式和案例。（1）规则规则由前提条件和结论两部分组成。前提条件由字段项（属性）取值的合取和析取组合而成，结论为决策字段项（属性）的取值或者类别组成。如，下例为两类人群9个元组（记录）表：身高头发眼睛第一类人矮金色蓝色高红色蓝色高金色蓝色矮金色灰色第二类人高金色黑色矮黑

41、色蓝色高黑色蓝色高黑色灰色矮黑色黑色利用数据挖掘方法，将能很快得到如下规则知识： IF（发色=金色红色）（眼睛=蓝色灰色）THEN 第一类人 IF（发色=黑色）（眼睛=黑色） THEN 第二类人即：凡是具有金色或红色的头发，并且同时具有蓝色或灰色眼睛的人属于第一类人；凡是具有黑色头发或黑色眼睛的人属于第二类人。（2）决策树如ID3方法的决策树，是由信息量最大的字段（属性）作为根结点，它的各个取值为分枝，对各个分枝所划分的数据元组（记录）子集，重复建树过程，扩展决策树，最后得到相同类别的子集，以该类别作为叶结点。如，上例的人群数据库，按ID3方法得到的决策树为（3）知识基（浓缩数据） 数据挖掘方

42、法能计算出数据库中字段项的重要程度，对于不重要的字段可以删除，对于数据库中的元组能按一定的原则合并。这样，通过可大大压缩数据库中的元组和字段项，最后得到浓缩数据，称为知识基。它是原数据库的精华，很容易转换成规则知识。如，上例的人群数据库，通过计算可以得出身高是不重要的字段，删除该项后，再合并相同数据元组，得到如下的浓缩数据表。（4）网络权值 神经网络方法经过对训练样本的学习后，所得到的知识是网络连接权值和结点的阈值。一般表示为矩阵和向量。如，异或问题的网络权值和阈值分别如下：样本：0 0 0 1 1 0 1 1（5）公式对于科学和工程数据库，一般存放的是大量实验数据（数值）。它们中蕴涵着一定的

43、规律性，通过公式发现算法，可以找出各种变量间的相互关系，用公式表示。如，太阳系行星运动数据中，包含行星运动周期（旋转一周所需时间，天），以及它与太阳的距离（围绕太阳旋转的椭圆轨道的长半轴，百万公里），具体数据如下表：水星金星地球火星木星土星周期P882253656874343.510767.5距离d581081492287781430由此，可得到开普勒第三定律：d/P=25.（6）案例案例是指人们经历过的一次完整的事件。当人们要解决一个新问题时，总是先回顾自己以前处理过的类似事件（案例），利用以前案例中解决问题的方法或者处理的结果，作为参考并进行适当的修改，以解决当前新问题。利用这种思想建立起

44、基于案例推理（Case Based Reasoning,CBR）。CBR的基础是案例库，在案例库中存放着大量成功或失败的案例。CBR利用相似检索技术，对新问题到案例库中搜索相似案例，再经过对旧案例的修改来解决新问题。可见，案例是解决新问题的一种知识。案例知识一般表示为三元组：l 问题描述：对求解的问题及周围世界或环境的所有特征的描述；l 解描述：对问题求解方案的描述；l 效果描述：描述解决方案后的结果情况，是失败还是成功。1.9 数据挖掘及知识发现的实际应用DM（KDD）工具和软件已在各个部门得到很好的应用，并收到明显的效益。1 金融方面：银行信用卡和保险行业，预测存/贷款趋势，优化存/贷款策

45、略，用DM将市场分成有意义的群组和部门，从而协助市场经理和业务执行人员更好地集中于有促进作用的活动和设计新的市场运动。2 在客户关系管理方面：DM能找出产品使用模式或协助了解客户行为，从而可以改进通道管理（如银行分支和ATM等）。又如正确时间销售（RightTimeMarKeting）就是基于顾客生活周期模型来实施的。3 在零售业/市场营销方面：是数据挖掘技术应用最早也是最重要的领域，DM用于顾客购货篮的分析可以协助货架布置，促销活动时间，促销商品组合以及了解滞销和畅销商品状况等商业活动。通过对一种厂家商品在各连锁店的市场共享分析,客户统计以及历史状况的分析，可以确定销售和广告业务的有效性。4

46、 在过程控制/质量监督保证方面：DM协助管理大数量变量之间的相互作用，DM能自动发现出某些不正常的数据分布，暴露制造和装配操作过程中变化情况和各种因素，从而协助质量工程师很快地注意到问题发生范围和采取改正措施。5 在远程通讯部门：基于DM的分析协助组织策略变更以适应外部世界的变化，确定市场变化模式以指导销售计划。在网络容量利用方面，DM能提供对客户组类服务使用的结构和模式的了解，从而指导容量计划人员对网络设施作出最佳投资决策。6化学/制药行业：从各种文献资料总自动抽取有关化学反应的信息，发现新的有用化学成分。在遥感领域针对每天从卫星上及其它方面来的巨额数据，对气象预报，臭氧层监测等能起很大作用

47、。7军事方面：使用DM进行军事信息系统中的目标特征提取、态势关联规则挖掘等。总之，DM可广泛应用于银行金融、零售与批发、制造、保险、公共设施、政府、教育、远程通讯、软件开发、运输等各个企事业单位及国防科研上。据报导，DM的投资回报率有达400%甚至10倍的事例。1.10 知识发现与创新自90年代以来，基于数据库/数据仓库技术的知识发现研究，一直是人们关注和研究的热点。所谓数据仓库，按数据仓库之父Bill Inmon的定义，就是一个“面向主题的”、“完整的”、“非易失的”、“不同时间的”、“用于支持决策管理的”数据集合。实质上，数据仓库就是将异构的数据集成起来，经过加工整理变成一个可用的数据资源

48、。目前，基于数据仓库的分析工具主要有：数据挖掘和联机分析处理（OLAP：OnLine Analysis Process）。它们的最本质区别在于，数据挖掘是一种挖掘性分析工具，它主要是利用各种分析方法（算法）主动地去挖掘大量数据中蕴含的规律；而OLAP则是一种求证性的分析工具，即已有一个假设，通过OLAP来得到验证。OLAP所采用的验证方法多是基于数据立方体法，即通过对数据立方体的切片、切块、旋转、钻取等操作来实现对数据立方体快速的多维成取。所谓多维存取，是从不同的角度根据数据仓库中的不同主题来得出不同的结论。数据挖掘和OLAP这两种分析工具本身是相辅相成的。OLAP可以帮助人们提出假设，也可以

49、验证数据挖掘预测的结果；数据挖掘能够挖掘出一个结论，但这结论是否正确，可用OLAP去验证。传统的数据库提供的是操作型数据环境，现在的数据仓库提供的是分析型数据环境。Internet上数据的最大特点是半结构化的。所谓半结构化是相对于结构化和非结构化而言的。如传统数据库中的数据结构性很强，称之为完全结构化的数据，而同时还存在诸如一本书、一张图片等完全无结构的数据。而Internet上存在的数据既不是完全结构化的也不是完全非结构化的，因为它的页面也具有描述层次的，存在一定的结构，所以称之为半结构的数据。Web上的每一个站点就是一个数据源，且是异构数据源，一个站点和另一个站的信息和组织形式不同，这就构

50、成了一个更大的、复杂性更高的数据库。要想对此进行数据挖掘，首先必须研究站点之间异构数据的集成问题。因为只有将这些站点上的数据都集成起来，提供给用户一个统一的视图或视角，才有可能从巨大的数据资源中获取所需的东西。所以，寻找一个半结构化数据模型成为解决集成问题的一个关键技术。此外，还需一项技术能够自动地从现有数据中将这个模型抽取出来，这就是所谓的模型抽取技术。因为半结构化数据模型和半结构化数据模型抽取技术是面向Internet数据挖掘技术实施的前提，因此堪称是当今知识发现研究领域的最大热点。“创新是一个民族的灵魂”，发现与发明统称为创新。在知识经济点主导地位的21世纪，拥有持续创新能力和大量高素质

51、人才资源的国家，显然将具备发展知识经济的巨大潜力。面对浩如烟海的信息资源（商业上的条形码，科学上先进仪器观察的数据，Internet网上的资源信息等）的迅速增长，人们迫切需要新的技术和工具，以便能从大量的数据中智能地、自动地抽取有价值的知识。知识发现技术和系统研究将极大地推动知识创新的开展，促进经济的持续发展。我们综合性大学里的所有学科，实际上可以成四大类（自然科学、社会科学、人文科学、其它），第一就是大家熟悉的自然科学，对于自然科学来说，最高水平的创新一定是创新知识。大学是以知识为纽带把大家联系在一起，教学是传播知识，科研是创新知识，图书馆在收藏知识，我们为社会服务在运用知识，我们进行国际交

52、流是交换知识，创新知识大概是自然科学的一个最高要求。除了创新知识之外，还有工程技术类的学科，这只不过是在运用规律和知识，对这些学科来说，最高水平的创新不是新知识的产生。如，“中国制造”大学之大不在大楼，而在大师。一个大学要受人尊重，不在大学的规模，不在大学的速度，而在这个大学有一代代受人尊敬的大师。每个人都有一个属于自己的知识空间。这个空间边界就是与未知世界的接触面。自己的知识空间越大，与未知世界的接触面积也就越大，因此就越会感觉自己的无知。扩充知识空间的过程叫学习。从小学到中学再到大学，我们的知识空间在不断扩大。两个人知识空间的碰撞叫交流。全世界知识的总和形成人类知识大空间，这个大空间的边界叫前沿。作为研究生必须拥有一小块与人类知识空间共同的边界，必须在前沿工作。如果他们在这块边界上有所突破，就叫做发现或叫做发明。这样的突破，扩充了研究生个人的知识空间，同时也就扩充了人类的知识大空间。本课程的教学目的：数据挖掘与知识发现是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。数据挖掘与知识发现将信息变为知识，从数据矿山中找到蕴藏的知识金块，将为知识创新和知识经济的发展作出贡献。本课程将全面而又系统地介绍了数据挖掘与知识发现的方法和技术，力图反映当前的最新成果。本课程面向计算机、信息技术以及相关专业博士生、硕士生。24