1.1知识
人类从工业社会向知识社会演进时，政治经济重心正从“生产”转向“发现、发明和创新”。知识是创新的核心，知识创新成为知识经济发展的最主要的动力源泉，对物质文明发展发挥了巨大的推动作用。知识就是力量。
在信息科学中,信息是根据表示数据所用的约定而赋予数据的意义。数据是事物、概念或指令的一种形式化的表示形式,以适合于人工或自然方式进行通信、解释或处理。信息是数据所表达的客观事实。数据是信息的载体,与具体的介质和编码方法有关。1948年，香农（C．E．Shannon）的开创性文章《通信的数学理论》，为信息论和编码技术奠定了理论基础，提出了著名的Shannon信息论。他用熵的概念来研究信息的容量，采用比特作为度量信息的单位。
信息经过加工和改造形成知识。知识是指人们通过学习、积累、发现、发明各种知识的总和，是人类认识过程中的一种结果形式，它是人类在实践的基础上产生又经过实践检验的对客观实际的可靠的反映。知识是人脑创新的成果，是人类智慧的结晶。智慧是人类文明的源泉，是推动历史发展的永恒动力，是生产力诸要素中的核心。
知识的数学本质和复杂性问题是知识科学两个基本的问题。从数学的观点来看，知识是什么？科尔莫戈罗夫(A.N.Kolmogorov)提出了描述信息复杂性的概念［233］，那么，对知识复杂性应如何描述？知识的基本单位是什么？
知识模型是指知识的形式化描述和操作方式。经典的知识模型包括产生式系统、框架、语义网络、面向对象的知识模型等。在分布智能中研究面向主体的模型，在语义Web中研究面向本体的模型。在分布、开放、动态、海量的知识环境中要提高知识的共享程度和使用效率，必须研究新型的知识模型。

第1章绪论










知识发现（第二版）

知识一般可分为陈述性知识、过程性知识和控制性知识。陈述性知识提供概念和事实，描述系统状态、环境和条件，是人们知道了什么。例如,一个知识检索系统中,陈述性知识包括陈述具体事实的数据库内容。过程性知识提供有关状态的变化、问题求解过程的操作、演算和动作的知识。智能信息检索系统利用过程性知识来处理陈述性知识。用控制策略表示问题的知识常称为控制性知识。控制性知识，即元知识，包含有关各种处理过程、策略和结构的知识,常用来协调整个问题求解的过程［552］。一般认为，知识具有下列特性： 
（1） 知识的客观性。虽然知识是人脑对信息与知识加工的成果，但这些成果是客观的，人类对自然、社会、思维规律的认识是客观的，这些规律的运行是不以人的意志为转移的。
（2） 知识的相对性。人类对自然、社会、思维规律的认识必须有一个过程。在一段时间内认为正确的东西，经过变革，可能发生变化。1991年第12届国际人工智能大会上，IJCAI的计算机和思维奖授予MIT的Brooks。他提出基于行为的人工智能，认为智能不要知识表示［39］，智能不要推理［40］。2001年第17届国际人工智能大会上，IJCAI的计算机和思维奖授予Stanford大学的Koller，以表彰她在概率推理、机器学习方面的贡献［214］。 
 (3) 知识的进化性。人类在认识客观世界和主观世界的过程中，不断对真理的长河加入新的内容，知识不断更新，例如对物质结构的认识、对基因的认识等。
（4） 知识的依附性。知识有载体，载体分层次。离开载体的知识是不存在的，载体消失，知识也随之消失。
（5） 知识的可重用性。在使用过程中知识可以反复重用。当然，要根据具体情况作具体分析，灵活应用知识。
（6） 知识的共享性。基础研究一般由政府进行投资，所得到的科学知识具有共享性； 但最新的技术知识受到知识产权法的保护，使用者只有支付一定的费用，才能获得这种知识的使用权。保护知识产权是发展技术和知识经济的重要国策。 


1.2知识发现的过程
知识发现是从数据集中抽取和精化新的模式。 知识发现的范围非常广泛,可以是经济、工业、农业、军事、社会、商业、科学的数据或卫星观测得到的数据。数据的形态有数字、符号、图形、图像、声音等。数据组织方式也各不相同,可以是有结构、半结构、非结构的。知识发现的结果可以表示成各种形式,包括规则、法则、科学规律、方程或概念网等。
目前,关系型数据库应用广泛,并且具有统一的组织结构、一体化的查询语言、关系之间及属性之间具有平等性等优点。因此,数据库知识发现（knowledge discovery in databases，KDD）的研究非常活跃。该术语于1989年出现，Fayyad定义为“KDD是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程”［102］。在上面的定义中，涉及几个需要进一步解释的概念： “数据集”、“模式”、“过程”、“有效性”、“新颖性”、“潜在有用性”和“最终可理解性”。数据集是一组事实F（如关系数据库中的记录）。模式是一个用语言L来表示的一个表达式E，它可用来描述数据集F的某个子集FE，E作为一个模式要求它比对数据子集FE的枚举要简单（所用的描述信息量要少）。过程在KDD中通常指多阶段的一个过程，涉及数据准备、模式搜索、知识评价，以及反复的修改求精； 该过程要求是非平凡的，意思是要有一定程度的智能性、自动性（仅仅给出所有数据的总和不能算作是一个发现过程）。有效性是指发现的模式对于新的数据仍保持有一定的可信度。新颖性要求发现的模式应该是新的。潜在有用性是指发现的知识将来有实际效用，如用于决策支持系统里可提高经济效益。最终可理解性要求发现的模式能被用户理解，目前它主要是体现在简洁性上。有效性、新颖性、潜在有用性和最终可理解性综合在一起称为兴趣性。
由于知识发现是一门受到来自各种不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。除了KDD外，主要还有如下若干种称法： 数据挖掘（data mining）、知识抽取（information extraction）、信息发现（information discovery）、智能数据分析（intelligent data analysis）、探索式数据分析（exploratory data analysis）、信息收获（information harvesting）和数据考古（data archeology）,等等。其中，最常用的术语是“知识发现”和“数据挖掘”。相对来讲，数据挖掘主要流行于统计界（最早出现于统计文献中）、数据分析、数据库和管理信息系统界，而知识发现则主要流行于人工智能和机器学习界。
知识发现过程可粗略地理解为三部曲： 数据准备、数据挖掘以及结果的解释评估（interpretation and evaluation）（见图1.1）。


图1.1知识发现过程示意图


1. 数据准备
数据准备又可分为三个子步骤： 数据选取（data selection）、数据预处理（data preprocessing）和数据变换（data transformation）。数据选取的目的是确定发现任务的操作对象，即目标数据（target data），它是根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换（如把连续值数据转换为离散型的数据，以便于符号归纳； 或是把离散型的转换为连续值型的，以便于神经网络归纳）等。当数据开采的对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成了。数据变换的主要目的是消减数据维数或降维（dimension reduction），即从初始特征中找出真正有用的特征以减少数据开采时要考虑的特征或变量个数。

2. 数据挖掘
数据挖掘阶段首先要确定开采的任务或目的是什么，如数据总结、分类、聚类、关联规则发现或序列模式发现等。确定了开采任务后，就要决定使用什么样的开采算法。同样的任务可以用不同的算法来实现。选择实现算法有两个考虑因素： 一是不同的数据有不同的特点，因此需要用与之相关的算法来开采； 二是用户或实际运行系统的要求，有的用户可能希望获取描述型的（descriptive）、容易理解的知识（采用规则表示的开采方法显然要好于神经网络之类的方法），而有的用户或系统的目的是获取预测准确度尽可能高的预测型（predictive）知识。
完成了上述准备工作后，就可以实施数据挖掘操作了。具体的数据挖掘方法将在后面章节中作较为详细的论述。需要指出的是，尽管数据挖掘算法是知识发现的核心，也是目前研究人员主要的努力方向，但要获得好的挖掘效果，必须对各种挖掘算法的要求或前提假设有充分的理解。

3. 结果解释和评估
数据挖掘阶段发现的模式，经过用户或机器的评估，可能存在冗余或无关的模式，这时需要将其剔除； 也有可能模式不满足用户要求，这时则需要让整个发现过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的数据挖掘参数值，甚至换一种挖掘算法（如当发现任务是分类时，有多种分类方法，不同的方法对不同的数据有不同的效果）。另外，由于KDD最终是面向人类用户的，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示，如把分类决策树转换为“if...then...”规则。
知识发现过程中要注意以下几点： 
（1） 数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏受两个要素的影响： 一是所采用的数据挖掘技术的有效性，二是用于挖掘的数据的质量和数量（数据量的大小）。如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换，则挖掘的结果是不会令人满意的。
（2） 整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现选择的数据不太好，或使用的挖掘技术产生不了期望的结果，这时，用户需要重复先前的过程，甚至从头重新开始。
（3） 可视化在数据挖掘的各个阶段都扮演着重要的作用。特别是，在数据准备阶段，用户可能要使用散点图、直方图等统计可视化技术来显示有关数据，以期对数据有一个初步的理解，从而为更好地选取数据打下基础。在挖掘阶段，用户则要使用与领域问题有关的可视化工具。在表示结果阶段，则可能要用到可视化技术。


1.3知识发现的任务
1. 数据总结 


数据总结的目的是浓缩数据,给出它的紧凑描述。传统的也是最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。由于数据库中的数据或对象所包含的信息总是最原始、基本的信息(这是为了不遗漏任何可能有用的数据信息)，人们有时希望能从较高层次的视图上处理或浏览数据,因此需要对数据进行不同层次的泛化以适应各种查询要求。目前主要有两种数据泛化技术： 多维数据分析方法和面向属性的归纳方法。 
多维数据分析方法是一种数据仓库技术,也称为联机分析处理(OLAP)。数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作,这类操作的计算量特别大。因此一种很自然的想法是,预先计算汇集操作结果并存储起来,以便于决策支持系统使用。存储汇集操作结果的地方称为多维数据库。多维数据分析技术已经在决策支持系统中获得了成功应用,如著名的SAS数据分析软件包、Business Object公司的决策支持系统Business Object以及IBM公司的决策分析工具都使用了多维数据分析技术。 
采用多维数据分析方法进行数据总结,针对的是数据仓库,数据仓库存储的是脱机历史数据。为了处理联机数据,研究人员提出了一种面向属性的归纳方法。它的思路是,直接对用户感兴趣的数据视图(用一般的SQL查询语言即可获得)进行泛化,而不是像多维数据分析方法那样预先存储泛化数据。方法的提出者将这种数据泛化技术称为面向属性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关系,它从较高的层次上总结了低层次上的原始关系。有了泛化关系后,就可以对它进行各种深入的操作而生成满足用户需要的知识,如在泛化关系基础上生成特性规则、判别规则、分类规则以及关联规则等。 

2. 概念描述
用户常常需要抽象的、有意义的描述。经过归纳的抽象描述能概括大量关于类的信息。有两种典型的描述：  特征描述和判别描述。特征描述从与学习任务相关的一组数据中提取出关于这些数据的特征式，这些特征式表达了该数据集的总体特征； 而判别描述则描述了两个或更多个类之间有何差异。

3. 分类 
分类在数据挖掘中是一项非常重要的任务,目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从历史数据纪录中自动推导出对给定数据的推广描述,从而能对未来数据进行预测。和回归方法不同的是,分类的输出是离散的类别值,而回归的输出则是连续数值。这里我们将不讨论回归方法。 
要构造分类器,需要有一个作为输入的训练样本数据集。训练集由一组数据库记录或元组构成,每个元组是一个由有关字段(又称属性或特征)值组成的特征向量,此外,训练样本还有一个类别标记。一个具体样本的形式可为： (v1,v2,…,vn；  c)； 其中vi表示字段值,c表示类别。 
分类器的构造方法有统计方法、机器学习方法、神经网络方法等。统计方法包括贝叶斯法和非参数法(近邻学习或基于范例的学习),对应的知识表示则为判别函数和原型事例。机器学习方法包括决策树法和规则归纳法,前者对应的表示为决策树或判别树,后者则一般为产生式规则。神经网络方法主要是BP算法,它的模型表示是前向反馈神经网络模型(由代表神经元的节点和代表连接权值的边组成的一种体系结构),BP算法本质上是一种非线性判别函数。粗糙集(rough set)的知识表示采用产生式规则。 
不同的分类器有不同的特点。有三种分类器评价或比较尺度： ①预测准确度； ②计算复杂度； ③模型描述的简洁度。预测准确度是用得最多的一种比较尺度,特别是对于预测型分类任务,目前公认的方法是10趟分层交叉验证法。计算复杂度依赖于具体的实现细节和硬件环境,在数据挖掘中,由于操作对象是巨量的数据库,因此空间和时间的复杂度问题将是一个非常重要的环节。对于描述型的分类任务,模型描述越简洁越受欢迎。例如,采用规则表示的分类器构造法就更有用,而神经网络方法产生的结果就难以理解。 
另外要注意的是,分类的效果一般和数据的特点有关,有的数据噪声大,有的有缺值,有的分布稀疏,有的字段或属性间相关性强,有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于所有不同特点的数据。 

4. 聚类 
根据数据的不同特征，将其划分为不同的数据类。它的目的是使得属于同一类别的个体之间的距离尽可能小,而不同类别上的个体间的距离尽可能大。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。 
在统计方法中,聚类亦称聚类分析,它是多元数据分析的三大方法之一(其他两种是回归分析和判别分析)。它主要研究基于几何距离的聚类,如欧氏距离、明考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类,它需要考察所有的个体才能决定类的划分。因此它要求所有的数据必须预先给定,而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度,难以适用于数据库非常大的情况。 
在机器学习中，聚类称为无监督或无教师归纳。因为和分类学习相比,分类学习的例子或数据对象有类别标记,而要聚类的例子则没有标记,需要由聚类学习算法来自动确定。在很多人工智能文献中,聚类也称概念聚类，因为这里的距离不再是统计方法中的几何距离,而是根据概念的描述来确定的。当聚类对象可以动态增加时,概念聚类则称为概念生成。 
在神经网络中,有一类无监督学习方法——自组织神经网络方法，如Kohonen自组织特征映射网络、竞争学习网络等。在数据挖掘领域里,见诸报道的神经网络聚类方法主要是自组织特征映射方法。IBM在其发布的数据挖掘白皮书中就特别提到了使用此方法进行数据库聚类分析。 

5. 相关性分析
相关性分析的目的是发现特征之间或数据之间的相互依赖关系。数据相关性关系代表一类重要的可发现的知识。一个依赖关系存在于两个元素之间。如果从一个元素A的值可以推出另一个元素B的值(A→B),则称B依赖于A。这里所谓的元素可以是字段,也可以是字段间的关系。数据依赖关系有广泛的应用。
依赖关系的分析结果有时可以直接提供给终端用户。然而,通常强的依赖关系反映的是固有的领域结构而不是什么新的或有兴趣的事物。 自动地查找依赖关系可能是一种有用的方法。这类知识可被其他模式抽取算法使用。常用技术有回归分析、关联规则、信念网络等。

6. 偏差分析
偏差分析包括分类中的反常实例、例外模式、观测结果对期望值的偏离，以及量值随时间的变化等。其基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现异常,可以引起人们对特殊情况的加倍注意。异常包括如下几种可能引起人们兴趣的模式： 不满足常规类的异常例子；  出现在其他模式边缘的奇异点；  与父类或兄弟类不同的类；  在不同时刻发生了显著变化的某个元素或集合；  观察值与模型推测出的期望值之间有显著差异的事例等。偏差分析的一个重要特征就是它可以有效过滤大量不感兴趣的模式。

7. 建模
建模就是通过数据挖掘，构造描述一种活动或状态的数学模型。机器学习中的知识发现，实际上就是对一些自然现象进行建模，重新发现科学定律，如BACON［343］和SDS［423］。


1.4知识发现的方法
1.4.1统计方法


统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。科学规律性的东西一般总是隐藏得比较深，最初总是通过统计分析从其数量表现上看出一些线索，然后提出一定的假说或学说，再作深入的理论研究。当理论研究提出一定的结论时，往往还需要在实践中加以验证。就是说，观测一些自然现象或专门安排的实验所得资料，是否与理论相符、在多大的程度上相符、偏离可能是朝哪个方向等问题，都需要用统计分析的方法处理。
近百年来，统计学得到了极大的发展。我们可用下面的框架粗略地刻画统计学发展的过程： 
1900—1920年数据描述
1920—1940年统计模型的曙光
1940—1960年数理统计时代
1960—1980年随机模型假设的挑战
1980—1990年松弛结构模型假设
1990—1999年复杂的数据结构建模

其中，从1960年至1980年间，统计学领域出现了一场革命，要从观测数据对依赖关系进行估计，只要知道未知依赖关系所属的函数集的某些一般的性质就足够了。引导这一革命的是20世纪60年代的四项发现： 
（1） Tikhonov,Ivanov 和 Philips 发现的关于解决不适定问题的正则化原则； 
（2） Parzen,Rosenblatt和Chentsov 发现的非参数统计学； 
（3） Vapnik 和Chervonenkis 发现的在泛函数空间的大数定律及其与学习过程的关系； 
（4） Kolmogorov,Solomonoff和Chaitin 发现的算法复杂性及其与归纳推理的关系。
这四项发现也成为人们对学习过程研究的重要基础。下面我们列出与统计学有关的机器学习方法。

1. 传统方法
统计学在解决机器学习问题中起着基础性的作用。传统的统计学所研究的主要是渐近理论，即当样本趋向于无穷多时的统计性质。统计方法主要考虑测试预想的假设和数据模型拟合。它依赖于显式的基本概率模型。统计方法处理过程可以分为三个阶段： 
（1） 搜集数据： 采样、实验设计； 
（2） 分析数据： 建模、知识发现、可视化； 
（3） 进行推理： 预测、分类。
常见的统计方法有回归分析（多元回归、自回归等）、判别分析（贝叶斯判别、费歇尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）、探索性分析（主元分析法、相关分析法等）等。 

2. 模糊集
模糊集是表示和处理不确定性数据的重要方法。模糊集不仅可以处理不完全数据、噪声或不精确数据，而且在开发数据的不确定性模型方面是有用的，可以提供比传统方法更灵巧、更平滑的性能。

3. 支持向量机
支持向量机（support vector machine,SVM）建立在计算学习理论的结构风险最小化原则之上，其主要思想针对两类分类问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误率［402］。而且SVM一个重要的优点是可以处理线性不可分的情况。

4. 粗糙集
粗糙集（rough set） 理论由 Zdziskew Pawlak在1982年提出［289］。 它是一种新的数学工具，用于处理含糊性和不确定性,在数据挖掘中发挥着重要作用。在求核属性算法中Skowron提出差别矩阵，胡小华进行了改进［179］。粗糙集是由集合的下近似、上近似来定义的。下近似中的每一个成员都是该集合的确定成员，而不是上近似中的成员肯定不是该集合的成员。粗糙集的上近似是下近似和边界区的合并。边界区的成员可能是该集合的成员，但不是确定的成员。可以认为粗糙集是具有三值隶属函数的模糊集，即是、不是、也许。与模糊集一样，它是一种处理数据不确定性的数学工具，常与规则归纳、分类和聚类方法结合起来使用，很少单独使用。
1.4.2机器学习
Simon对学习的定义是： “如果一个系统能够通过执行某种过程而改进它的性能，这就是学习”。这个说法的要点是： 第一，学习是一个过程； 第二，学习是相对一个系统而言； 第三，学习改变系统性能。过程、系统与改变性能是学习的三个要点。对上述说法，第一点是自然的。第二点中的系统则相当复杂，一般是指一台计算机，但是，也可以是计算系统，甚至包括人的人机计算系统。第三点则只强调“改进系统性能”，而未限制这种“改进”的方法。显然，Simon对学习的这个说法是思辨的,对计算机科学家来说,这是远远不够的。计算机学家更关心对不同系统实现机器学习的过程，以及改变性能的效果。图1.2给出一个简单的学习系统模型。


图1.2一个简单的学习系统模型

在20世纪50年代，机器学习采用了两种不同的研究方法。在控制理论中，使用多项式等为基函数，利用优化的方法建立模型，以刻画被控对象的行为，这个过程在控制理论中称为辨识或参数估计，甚至笼统地称为建模。而以Rosenblatt的感知机为代表的研究，则是从MP模型出发，具体地说，就是将扩展为多个神经元的MP模型作为优化算法的数学基函数。但是，从数学上，其区别仅仅是它们使用了不同的基函数，以及由此所带来的问题。这两种以优化为基础的方法至今还影响着机器学习的发展。