第1章绪论
1.1知 识 发 现
在许多领域中，随着数据的不断增多，一些大型数据库的规模已经远远超过人工所能分析的程度，因此数据库和知识发现（knowledge discovery in database，KDD）技术应运而生(李嶶和李宛州，2001)。知识发现也是市场竞争的需要，它为决策者提供重要的、前所未有的信息或知识，从而产生不可估量的效益。
1.1.1知识发现的历程
随着数据库系统的广泛开发和数据库技术的迅速发展，数据以前所未有的速度大量聚集在计算机中，但与之相配合的数据分析和知识提取技术在相当长一段时间里没有大的进展，使得存储的大量原始数据没有被充分利用，没有转化成为指导生产的“知识”，而是出现了“数据的海洋，知识的荒漠”这样一种奇怪的现象。于是，知识发现在这种背景下应运而生，并很快发展成为国际上数据库和信息决策领域最前沿的研究方向之一。
知识发现的研究经历了从机器学习到机器发现再到知识发现几个阶段，从20世纪80年代末，人们开始研究知识发现，1989年8月在美国底特律召开的第11届国际人工智能联合会议的专题讨论会上首次出现知识发现这个术语，法耶兹(Fayyad)首次给出了知识发现的定义“知识发现是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程”。随后在1991年、1993年和1994年都举行了知识发现专题讨论会，集中讨论海量数据分析算法、数据统计、知识表达、知识运用等问题。随着知识发现在学术界和工业界的影响越来越大，知识发现组委会于1995年把专题讨论会更名为国际会议，并改为大会代表自愿报名参加。1995年在加拿大蒙特利尔市召开了第一次知识发现国际学术会议，以后每年召开一次。
1.1.2知识发现的内容
在知识发现′96国际会议上对知识发现做了如下定义：知识发现是识别出存在于数据库中有效的、新颖的、具有潜在效果的乃至最终可理解的模式的非平凡过程。知识发现是将数据变成信息、信息变为知识、知识形成策略、策略构成智能的活动，从而指导人类有效地分析问题和解决问题。知识发现过程从数据矿山中找到蕴藏的知识金块，将为知识创新和知识经济的发展作出积极的贡献。
知识发现的范围非常广泛，可以是经济、工业、农业、军事、社会、商业、科学、医疗卫生等的数据或卫星观测得到的数据。数据的形态有数字、符号、图形、图像、声音等。数据组织方式也各不相同，可以是结构化、半结构化、非结构化的。知识发现的结果可以表示成各种形式，包括规则、法则、科学规律、方程或语义网络等。
数据库知识发现的研究非常活跃。在法耶兹的定义中，涉及几个需要进一步解释的概念：“数据集”、“模式”、“过程”、“有效性”、“新颖性”、“潜在有用性”和“最终可理解性”。数据集是一组事实F（如关系数据库中的记录），模式是一个用语言L来表示的一个表达式E，它可用来描述数据集F的某个子集FE，E作为一个模式要求它比对数据子集FE的枚举要简单（所用的描述信息量要少）。过程在知识发现中通常指多阶段的一个过程，涉及数据准备、模式搜索、知识评价，以及反复地修改求精；该过程要求是非平凡的，意思是要有一定程度的智能性、自动性。有效性是指发现的模式对于新的数据仍保持有一定的可信度。新颖性要求发现的模式应该是新的。潜在有用性是指发现的知识将来有实际效用，如用于决策支持系统（decision support system，DSS）中可提高经济效益。最终可理解性要求发现的模式能被用户理解，目前它主要体现在简洁性上。有效性、新颖性、潜在有用性和最终可理解性综合在一起称为兴趣性。
知识发现与智能决策第1章绪论1.1.3知识发现的过程
知识发现是一门受到来自各种不同领域的研究者关注的交叉性学科，因此它还有很多不同的术语名称。除了知识发现外，主要还有如下若干种称法：数据挖掘（data mining）、知识抽取（information extraction）、信息发现（information discovery）、智能数据分析（intelligent data analysis）、探索式数据分析（exploratory data analysis）、信息收获（information harvesting）和数据考古（data archeology）等。其中最常用的术语是“知识发现”和“数据挖掘”。数据挖掘主要流行于统计界（最早出现于统计文献中）、数据分析、数据库和管理信息系统（management inform ation system， MIS）领域，而知识发现则主要流行于人工智能和机器学习领域。
知识发现过程（图1-1）可粗略地理解为三部曲：数据准备、数据挖掘和结果的解释评估。
图1-1知识发现过程示意图
1.1.3.1数据准备
数据准备又可分为三个子步骤：数据选取（data selection）、数据预处理（data preprocessing）和数据变换（data transformation）。数据选取的目的是确定发现任务的操作对象，即目标数据（target data），它是根据用户的需要从原始数据库中抽取的一组数据。原始数据库可以是异构的数据库和多源性数据文件。数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换（如把连续值数据转换为离散型的数据，以便于符号归纳；或是把离散型的转换为连续值型的，以便于概念性归纳）等。当数据挖掘的对象是数据仓库时，数据预处理已经在生成数据仓库时完成了，主要是通过在源数据中抽取数据，按数据仓库的逻辑数据模型的要求进行数据转换，再按物理数据模型的要求装载到数据仓库中去，即进行数据抽取、转换、加载(extract、transform、load，ETL)过程。数据变换的主要目的是消减数据维数或降维（dimension reduction），即从初始特征中找出真正有用的特征以减少数据开采时要考虑的特征或变量个数。
1.1.3.2数据挖掘
数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据总结、概念描述、分类、聚类、关联规则发现或序列模式发现和相关性分析等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。同样的任务可以用不同的算法来实现。选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获取描述型的（descriptive）、容易理解的知识，而有的用户或系统的目的是获取预测准确度尽可能高的预测型（predictive）知识。完成上述准备工作后，就可以实施数据挖掘操作了。具体的数据挖掘方法将在后面章节中作较为详细的论述。需要指出的是，尽管数据挖掘算法是知识发现的核心，也是目前研究人员主要的努力方向，但要获得好的挖掘效果，必须对各种挖掘算法的要求或前提假设有充分的理解。
1.1.3.3结果解释和评估
数据挖掘阶段发现的模式，经过用户或机器的评估，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求，这时则需要让整个发现过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的数据挖掘参数值，甚至换一种挖掘算法（如当发现任务是分类时，有多种分类方法，不同的方法对不同的数据有不同的效果）。另外，知识发现最终是面向人类用户的，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示，如把分类决策树转换为“if…then…”规则等。
知识发现过程中要注意以下几点：
1）数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏受两个要素的影响：一是所采用的数据挖掘技术的有效性，二是用于挖掘的数据的质量和数量（数据量的大小）。如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换，则挖掘的结果是不会令人满意的。
2）整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现选择的数据不太好，或使用的挖掘技术产生不了期望的结果，这时，用户需要重复先前的过程，甚至重新开始。
3）可视化在数据挖掘的各个阶段都扮演着重要的作用。特别是在数据准备阶段，用户可能要使用散点图、直方图等统计可视化技术来显示有关数据，以对数据有一个初步的理解，从而为更好地选取数据打下基础。在挖掘阶段，用户则要使用与领域问题有关的可视化工具。在表示结果阶段，则可能要用到可视化技术。
1.1.4知识发现的方法
知识发现的方法大致可分为如下几大类。
1.1.4.1统计方法
统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。科学规律性的东西一般总是隐藏得比较深，最初总是通过统计分析从其数量表现上看出一些线索，然后提出一定的假说或学说，再作深入的理论研究。当理论研究提出一定的结论时，往往还需要在实践中加以验证。就是说，观测一些自然现象或专门安排的实验所得资料，是否与理论相符、在多大的程度上相符、可能朝哪个方向偏离等问题，都需要用统计分析的方法处理。
近百年来，统计学得到了极大的发展。我们可用图1-2的框架粗略地刻画统计学发展的过程。
图1-2统计学发现过程图
其中，从1960~1980年，引导这一革命的是20世纪60年代的四项发现：①吉洪诺夫（Tikhonov）、伊万诺夫（Ivanov）和菲利浦（Philips）发现的关于解决不适定问题的正则化原则。②帕仁（Parzen）、罗森布拉特（Rosenblatt）和陈瑟夫（Chentsov）发现的非参数统计学。③瓦普尼克（Vapnik）和车温尼克思（Chervonenkis）发现的在泛函数空间的大数定律及其与学习过程的关系。④柯尔莫哥洛夫（Kolmogorov）、索洛莫诺夫（Solomonoff）和沙坦（Chaitin）发现的算法复杂性及其与归纳推理的关系。
这四项发现也成为人们对学习过程研究的重要基础。下面我们列出与统计学有关的机器学习方法。
（1）传统方法
统计学在解决机器学习问题中起着基础性的作用。传统的统计学所研究的主要是渐近理论，即当样本趋向于无穷多时的统计性质。统计方法主要考虑测试预想的假设和数据模型拟合。它依赖于显式的基本概率模型。统计方法处理过程可分为三个阶段：①搜集数据：采样、实验设计。②分析数据：建模、知识发现、可视化。③进行推理：预测、分类。
常见的统计方法有回归分析（多元回归、自回归等）、判别分析（贝叶斯判别、费歇尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）、探索性分析（主元分析法、相关分析法等）等。
（2）模糊集
模糊集是表示和处理不确定性数据的重要方法。模糊集不仅可以处理不完全数据、噪声或不精确数据，而且在开发数据的不确定性模型方面是有用的，可以提供比传统方法更灵巧、更平滑的性能。
（3）支持向量机
支持向量机（support vector machine，SVM）建立在计算学习理论的结构风险最小化原则之上，其主要思想针对两类分类问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误率。而且SVM有一个重要的优点就是可以处理线性不可分的情况。
（4）粗糙集
粗糙集（rough set）理论由帕夫拉克（Z.Pawlak）在1982年提出。它是一种新的数学工具，用于处理含糊性和不确定性问题，在数据挖掘中发挥着重要的作用。粗糙集是由集合的下近似、上近似来定义的。下近似中的每一个成员都是该集合的确定成员，而不是上近似中的成员肯定不是该集合的成员。粗糙集的上近似是下近似和边界区的合并。边界区的成员可能是该集合的成员，但不是确定的成员。可以认为粗糙集是具有三值隶属函数的模糊集，即是、不是、也许。与模糊集一样，它是一种处理数据不确定性的数学工具，常与规则归纳、分类和聚类方法结合起来使用，很少单独使用。
1.1.4.2机器学习
西蒙（Simon）对机器学习的定义是：“如果一个系统能够通过执行某种过程而改进它的性能，这就是学习”。这个说法的要点是：第一，学习是一个过程；第二，学习是相对一个系统而言的；第三，学习改变系统性能。过程、系统和改变性能是学习的三个要点。对上述说法，第一点是自然的。第二点中的系统则相当复杂，一般是指一台计算机，但是，也可以是计算系统
书单推荐
