第1章 绪论

1.1 数据挖掘概述

1.1.1 数据挖掘的发展状况

技术进步已经使得存储大量的数据不是问题，数据库存储的数据量呈指数级增长，随之而来的是按传统方法对众多的数据进行利用和管理已经达不到人们的要求。数据本身是对某个现象、事件、企业或部门的活动的记载，它们是有意义的，巨大的数据量使人工用传统的方法去发现数据中有价值的关系成为难事，而往往隐藏在数据中的本质性知识和关系，以及关于数据的整体特征的描述及对其发展趋势的预测，对于数据拥有者进行决策及获得利益非常重要或有参考价值，因此需要新的技术去解决信息超载带来的问题。这样就导致了数据库中的知识发现（Knowledge Discovery in Database，KDD）及数据挖掘工具的出现。KDD是从大量数据中提取出可信的、新颖的、有效的并能被人理解的模式的高级处理过程。一般将KDD中进行知识学习的阶段称为数据挖掘（Data Mining）[1]。数据挖掘是从存储在传统数据库的数据中抽取先前没有被识别出的信息，数据挖掘也是使存储的大量没有被使用的数据变成有用信息的手段。

事实上，KDD是一门交叉学科，它融合了数据库、机器学习、人工智能、模糊逻辑、统计学、知识工程、认知科学等学科的方法。在不同的研究群体中，对其给予了不同的名称，如在人工智能和机器学习界称为KDD，在统计、数据库及管理界称为数据挖掘，还有其他一些说法，如信息抽取、信息发现、知识发现、信息收获、数据考古等。本书采用与文献[1]一致的说法，把KDD看成一个过程，数据挖掘是其中的一个阶段，在有些情况下，并不加以严格区别。

20世纪90年代，人们对数据挖掘越来越关注。KDD这个术语首先出现在1989年8月在美国底特律召开的第11届国际人工智能联合会议的专题讨论会上，1991年、1993年和1994年举行了KDD专题讨论会。随着参加会议人数的增多，从1995年开始，每年都要举办一次KDD国际会议。1997年，KDD拥有了自己的专业杂志Knowledge Discovery and Data Mining。除研究外，也出现了相当数量的KDD产品和应用系统，如由IBM Almaden研究所的R.Agrawal等人研究开发的面向大型数据库的Quest系统，其中包括挖掘关联规则、分类规则、序列模式和相似序列等；由加拿大Simon Fraser大学的J.Han等人研究开发的DBMiner系统，是一个交互式多层次裁决系统，主要挖掘关联规则、分类规则、预测等；Angoss International公司的KnowledgeSEEKER系统；SAS Institute公司的Enterprise Miner系统等[2]。

数据挖掘已经有许多成功的案例[3]。贝尔大西洋公司（Bell Atlantic）通过对客户电话问题的收集，采用数据挖掘创建的一组规则取代专家系统，这些学习得到的规则可以减少公司做出错误决定，每年为公司节省1000多万美元，由于学习规则通过在实例上训练而得到，因此容易维护，并且可以适应不同的地区和开销的变化。美国万国宝通银行（American Express）通过机器学习产生的规则对贷款申请者进行预测，预测贷款者是否会拖欠贷款的准确率可达到70%。英国石油公司（British Petroleum Corporation）通过使用机器学习创建了一组设定控制参数的规则，可以对从地下抽取出的原油和天然气的分离进行控制，专家需要一天多才能完成的任务，用机器学习的规则只需要10分钟。R.R.Donnelly（一家美国大型印刷公司）对凹版印刷滚筒上出现凹槽的情况，使用机器学习为控制过程参数（如油墨、温度等）创建规则，减少条带，学习得到的规则更适合具体的工厂，在某工厂中可以将条带出现的次数从538次降低到26次。新西兰奶牛场每年都需要决定哪些牛用于产奶、哪些牛送去屠宰，他们用机器学习来研究奶牛的血统、产奶史、健康状况、脾气等属性，然后做出决定。制药业采用序列相似性及药物机理，进行归纳逻辑规则的提取，以发现新药。医学界采用概率关系模型来进行流行病学的排查。天文学中采用机器学习开发的完全自动的天体分类系统，准确率可以达到92%。美国政府进行的数据挖掘研究计划在人们日常生活中产生的大量信息（如购物、电话记录、出行等）中寻找恐怖活动的警告模式。

1.1.2 数据挖掘的概念

数据挖掘从字面意义上可以理解为从众多的数据中挖掘出有用的知识或信息。自从数据挖掘开始盛行，对于数据挖掘的定义就众说纷纭。有说这种说法词不达意的，建议把其改成“从数据中挖掘知识”，或改成“数据中的知识发现”[4]。我们认同把数据挖掘看成知识发现过程的一个特定的基本步骤，即人们面对大量数据的时候，从数据中抽取和挖掘新的模式。

Fayyad[1]给出的知识发现的定义：KDD是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。文献[5]对此定义中的概念给出了解释，“数据集”是一组事实F（如关系数据库中的记录）。“模式”是一个用语言L来表示的表达式E，它可用来描述数据集F的某个子集FE。E作为一个模式，要求它比对数据子集FE的枚举要简单（所用的描述信息量要少）。“过程”在KDD中通常指多阶段的处理，涉及数据准备、模式搜索、知识评价及反复的修改求精；该过程要求是非平凡的，意思是要有一定程度的智能性、自动性（仅仅给出所有数据的总和不能算作一个发现过程）。“有效”是指发现的模式对于新的数据仍保持一定的可信度。“新颖”要求发现的模式是新的。“潜在有用”是指发现的知识将来有实际效用，如用于决策支持系统可提高经济效益。“最终可理解”要求发现的模式能被用户理解，目前主要是体现在简洁性上。“有效、新颖、潜在有用和最终可理解”综合在一起称为兴趣。

知识发现过程可以分为三个主要阶段：数据预处理、数据挖掘及数据挖掘结果评估和表示。知识发现过程如图1.1所示。

1.数据预处理

数据预处理可以分为以下几部分。

（1）数据清理：对数据中的噪声、缺值、重复、不一致等进行消除。

（2）数据集成：对多数据源的数据进行组合，比如可以放在数据仓库中。

（3）数据选择：根据需要从原始数据中提取与分析任务相关的一组数据。

（4）数据变换：将数据变换或统一成适合挖掘的形式，比如把连续数据转换为离散数据，便于符号运算。

目前较为流行的做法是在建立数据仓库时进行数据预处理，在数据仓库中主要进行降维工作，为数据挖掘做准备。

2.数据挖掘

它是知识发现的基本步骤，即使用智能方法和技术提取有用的数据模式。在此过程中确定挖掘的任务并与用户或知识库进行交互，完成诸如数据总结、分类、聚类、关联规则或序列模式等的发现。在这个过程中智能方法或技术可以用各种算法实现，将找到的有意义、有趣的模式提供给客户，或者作为新知识存放到知识库中。在算法的选择上要考虑不同的数据类型及用户的要求，以及对发现模式的描述形式及知识的表示。

3.数据挖掘结果评估和表示

数据挖掘过程发现的模式要通过用户或系统的评估，这种评估根据某种兴趣度量，识别出能够表示知识的真正有趣的模式。而在知识的表示方面，要把挖掘出的知识向用户展示出来。

J.Han和M.Kamber[4]从功能的角度给出了数据挖掘的定义：数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量数据中发现有趣知识的过程。基于这样的定义，数据挖掘系统的主要组成如下（见图1.2）。

·数据库或其他信息库：是一个或多个数据库、数据仓库、电子数据表、Internet或其他类型的信息库。这些数据可以是经过数据清理及集成的。

·服务器：现在许多服务器中存放着许多数据库或信息库，根据用户的数据挖掘要求，由相关的数据库、数据仓库或其他信息库提供数据源。

·知识库：知识是人们对信息的加工成果，它们是客观的，是与领域相关的。这些知识存储在知识库中，用于指导搜索或评估结果模式的兴趣度。知识是人类智慧的结晶，知识可分为陈述性知识、过程性知识和控制性知识。在知识库中如何描述和表示人类已获得的知识，是最终获得有用模式的基础[5]。

·数据挖掘引擎：由若干功能模块组成，对数据可以实施特征化、关联分析、分类、预测、聚类分析等数据挖掘的算法，得到相应的挖掘结果。

·模式评估：使用相关的评估规则，依据用户的兴趣度度量，与数据挖掘的功能模块进行交互，使挖掘出的模式得到评估，评估模式的过程是一个模式演化的过程，在数据挖掘中引导有兴趣的模式出现。

·用户界面：在用户和数据挖掘系统之间通信，实现用户与系统的交互，它既用于说明数据挖掘任务、提供信息、帮助挖掘过程的实现，也用于数据挖掘中间和最终结果的显示。

通过数据挖掘，可以从数据库或其他信息库提取有趣新颖的知识、规律或深层信息，并可以从不同角度观察或查阅它们。知识发现的结果可以用于决策、过程控制、信息管理和查询。

1.1.3 数据挖掘技术概述

把从数据中发现有用的知识比喻为挖掘，这种比喻是把数据库当作“矿石”，从中发现“金子”[3]。挖掘宝藏是需要手段的，从传统的锹挖到现代的钻探，随挖掘技术而定。数据挖掘也是如此。随着人们要求的不断提高及研究的实际问题的不同，形成了各种数据挖掘技术。

数据挖掘技术可按三种情况分类[6]：挖掘对象、挖掘任务、挖掘方法。

按挖掘对象分类是指作用在什么类型的数据库上，数据库类型的不同反映了数据库的逻辑结构的不同，依此可分为结构化数据库和非结构化数据库。结构化数据库包括关系数据库、事务数据库、面向对象数据库、演绎（Deductive）数据库、空间（Spatial）数据库、时间（Temporal）数据库等；而非结构化数据库包括多媒体数据库、文本数据库、异构（Heterogeneous）数据库、Internet信息库等。

按挖掘任务分类是指挖掘何种知识，有几种典型的知识可以挖掘出来，包括关联规则、特征（Characteristic）规则、分类规则、判别（Discriminant）规则、聚类、偏差（Deviation）分析、模式分析等。如果以挖掘知识的抽象层次划分，又有一般性知识、原始层次的知识、高层次的知识和多层次的知识等。

按挖掘方法分类是指采用何种方法，可以按驱动方法划分为自动知识挖掘、数据驱动挖掘、查询驱动挖掘及交互数据挖掘，也可以划分为一般化（Generalization）挖掘、基于模式挖掘、依据统计和数学理论的挖掘及综合（Integrated）方法。

数据挖掘技术大致包括：机器学习方法，包括关联规则发现、决策树、分类及分类树、遗传算法、归纳树等；统计方法，包括回归分析（多元分析、自回归、Bayesian网络、分类和回归树、预测模型等）、判别分析（贝叶斯分析、非参数判别等）；模式识别方法，包括聚类分析（系统聚类、动态聚类等）、辨识树、K-近邻和最近邻、神经网络、顺序（Equential）模式发现、相似时序发现等；模糊逻辑方法；语义查询优化方法；可视化方法等[7]。下面简单介绍数据挖掘技术中目前研究的热点技术。

1.遗传算法

J.H.Holland[8]提出的遗传算法（Genetic Algorithm，GA）在进化计算中是举足轻重的算法。GA是一种基于适者生存的生物进化与遗传机理的随机搜索算法，是一种全局优化算法。遗传算法由以下5个基本要素构成：

① 参数编码；

② 初始群体设定；

③ 适应度函数设计；

④ 遗传操作设计；

⑤ 控制参数设定。

Holland将染色体编码成二进制代码串，种群就由具有每一位二进制数表示的串组成。对每个串进行适应度函数运算，对适应度的评定即决定把合适的串保留下来进行遗传，分别做“杂交”和“变异”操作，在产生的新一代种群中注入一些随机因素以保持种群的多样性，直到种群达到适应度函数最大化为止。

遗传算法遵循的原则如下[3]：

① 进化发生在染色体中，即染色体因基因的重组而动态变化。

② 适者生存，即复制那些具有更高适应度的有机体的染色体，而这种复制是因适应度函数而定的，有它的相对性。

③ 种群具有多样性，变异可以使有机体保持多样性。

Holland提出的遗传算法思想：首先利用随机方式产生初始群体，群体中的每个个体称为染色体，对应着优化问题的一个可能解。染色体的最小组成元素就称为基因，对应可能解的某一特征，即设计变量。染色体的评价函数值反映可能解的优劣，按照优胜劣汰原则对染色体进行选择，相对“好”的个体得以繁殖，相对“差”的个体将死亡。群体性能通过选择、杂交、变异等过程得到改善，经过若干代繁衍进化就可使群体性能趋于最佳。

遗传算法基本步骤如下。

（1）建立一个待优化的问题：

式中x,y,z是自变量，可以是数值或逻辑变量，甚至可以是符号。每组(x,y,z)∈D构成问题的一个可能解，所以D既可以看成x,y,z的定义域，也可看成问题的约束条件或所有满足约束条件的解空间。F是属于实数域R的一个实数，也可看成对每一组可能解(xi,yi,zi)∈D的质量优劣的度量，函数f表示从解空间到实数域R的一个映射，唯一的要求就是给定一组解(xi,yi,zi)∈D都可以算出一个对应的F。目标就是要找到(x0,y0,z0)∈D使F=f(x0,y0,z0)最大。

（2）编码：对每一个选定的自变量进行编码，常用一定比特数的二进制代码来代表一个自变量的各种取值，将各自变量的二进制代码连到一起即得到一个二进制代码串，该串就代表了优化问题的一个可能解。如自变量x,y,z的一组取值可用12比特的二进制代码表示为100010011010。

（3）产生祖先群体：计算机按随机方法在可能解中产生给定数量的二进制代码串来构成一个原始的祖先群体，其中的每个二进制代码串就代表这一群体中的一位祖先，对每位祖先（可能解）计算其相应的函数值Fi。按Fi的大小来评价祖先的染色体的素质。GA算子的任务就是从这些祖先出发，模拟进化过程的优胜劣汰，逐次迭代，最后得出非常优秀的群体与个体，以达到优化的目的。

（4）选种与繁殖：选种与繁殖模拟生物进化的自然选择功能，从原始群体中随机取一对个体作为繁殖后代的双亲，选种的规则是适应度高的个体有更多的繁殖后代的机会，以使优良特征得以遗传和保留。

（5）杂交（也称交叉）：以概率Pc将祖先群体中随机选中的双亲进行杂交，最简单的杂交方法是随机选择一个截断点或两个截断点，将双亲的二进制代码串在截断点处切开，然后交换其尾部。

（6）变异：变异用来模拟生物在自然的遗传环境中，由于各种偶然因素引起的基因突变。其方法是以一定的概率P，选取祖先群体中若干个体，随机选取某一位，将该位的数码翻转，即由1改为0或由0改为1。变异增加了群体基因材料的多样性和自然选择的余地，有利的变异将由于自然选择的作用得以遗传和保留，而有害的变异则将在逐代遗传中被淘汰。

综上所述，通过选种、杂交和变异得到的新一代群体将替代上一代群体。一般新群体的平均素质比上一代群体要好。重复第3～5步，如此迭代下去，各代群体的优良基因成分逐渐积累，群体的平均适应度和最佳个体的适应度不断上升，直到迭代过程找到最优解。

遗传算法具有稳健性、自适应性，其在解决大空间、多峰值、非线性、全局优化等复杂度高的问题时具有很强的优势。因此，遗传算法在数据挖掘技术中逐渐显示出其重要的地位。遗传算法在数据挖掘中主要应用于数据回归和关联规则的获取。数据挖掘采用进化计算在给定的目标集中挖掘有趣的规则，在获得有趣规则的过程中采用遗传算法对属性间的相关性进行处理，在训练集中采用非线性多元回归[9]等方法。

2.支持向量机

近几年对支持向量机（SVM）[3][10]的研究在数据挖掘领域非常活跃，它适用于大规模数据挖掘问题，目前在分类上使用较多。SVM是基于统计学习方法的，属于有监督的学习算法，为学习机提供样本集及相应的类别标识。

SVM构造了一个分隔两类的超平面，现在也可以扩展到多类问题上。在构造的过程中SVM算法试图使两类之间的间隔达到最大化，使其最小泛化误差与期望值最为接近。最小泛化误差是指当对新的样本数据进行分类时，超平面可以使其分类预测错误的概率最小化。这样的分类器可以达到类别分离边缘的最大化。数据集中落在边界平面上的点称为支持向量（Support Vector），支持向量机指支持向量算法。Vapnik[11][12]证明了如下结论：如果训练向量被一个最佳超平面准确无误地分隔，那么在测试样本上的期望误差率由支持向量的个数和训练样本的个数之比来界定。由于该比值和问题的维度无关，因此，如果可以找到一个较小的支持向量集，就可以保证得到很好的泛化能力。图1.3所示的具有训练误差的线性分类器，可以使误分类的个数最小化，即使被正确分类的样本间隔最大化。

1.1.4 数据挖掘方法比较

上节中已经讨论了大部分数据挖掘技术，这些技术实际上体现了不同领域、不同角度给出的实现方法[13]，大体可以分为从数学角度出发的数理统计方法、从仿生角度出发的神经网络法、从知识角度出发的机器学习方法、从处理不确定性角度出发的模糊逻辑及粗糙集方法等。文献[13]从以下几个方面对数据挖掘方法进行了比较。

·描述模型的能力：此方法是否能够从数据中挖掘出复杂的模型。

·可伸缩性：此方法对目标数据集合的大小的敏感度，即是否适用于大型数据库。

·精确性：此方法对挖掘出的模型是否精确。

·稳健性：此方法对非法输入、错误数据及环境因素的适应能力。

·抗噪声能力：若目标数据中存在数据丢失、失真等情况，此方法是否能够自动恢复正确的值或仅仅将噪声过滤。

·知识的可理解性：此方法发现的知识是否能够为人所理解，是否能够作为先验知识被再利用。

·是否需要主观知识：此方法在挖掘过程中，是否依赖于外部专家的主观知识。

·开放性：此方法是否能够结合领域知识来高效地发现知识。

·适用的数据类型：此方法是否只适用于数值类型的数据或符号类型的数据，或者两者皆可。

依据上述几方面，可以得出，统计模式识别方法具有良好的理论基础，描述模型的能力较强，可伸缩性、精确性、稳健性、抗噪声能力和开放性都较好，比较适合数值信息。但这类方法大多需要对概率分布做主观假设，因此需要主观知识支持；并且发现的结果多为数学公式，不易理解。机器学习方法描述模型的能力较强，结果的可理解性、开放性较好，处理符号信息能力强。但它的精确性、稳健性和抗噪声能力一般，需要以算法的复杂度为代价，并且往往面向经过整理的小训练集，因此可伸缩性差。神经网络法的模型描述能力强，精确性、稳健性和抗噪声能力都较好，一般不需要主观知识的支持。但它需要对数据做多遍扫描，训练时间较长，可伸缩性差；由于知识是以网络结构和连接权值的形式来表达的，因此结果的可理解性和开放性都很差。对于知识的可理解性，虽然可以通过观察输入和输出来分析网络内部的知识，或者通过网络剪枝来简化网络的结构从而提取规则，但效果都不理想。粗糙集方法的伸缩性较强，稳健性和抗噪声能力也较强，知识的可理解性和开放性较好，比较适合符号信息。此外，粗糙集方法可以对数据进行预处理，去掉多余属性，可以提高挖掘效率，降低错误率，但其模型描述能力一般。面向数据库的方法适合大型数据库的知识挖掘，伸缩性强，精确性、抗噪声能力和稳健性较好，对一般数据和符号数据都适合，知识的开放性和可理解性都较强。但其依赖数据模型，只能发现比较简单的描述性知识，用它来发现复杂模型较难。

通过上述比较可以看出，各种方法有其不同的适应领域，在使用上要有所选择。

1.1.5 数据挖掘面临的问题

数据挖掘技术经过二十几年的发展已经渐趋成熟，但有些问题还没有解决或解决得不够理想。为获得一个有效的数据挖掘系统，还必须解决以下问题[2][6]。

（1）巨量数据与不同类型的数据。数据库的大型化和高维化一直是数据挖掘面临的主要问题，寻找缩减属性及缩小搜索空间的方法和降低线性计算复杂度及时间的有效算法始终是其研究的方向之一。不同的应用形成了各种不同类型的数据，一个强有力的知识发现系统应能处理结构化、半结构化和非结构化数据。然而，在一个系统中完美地实现上述目标还有相当大的困难，但通用的数据挖掘系统一直是人们追求的方向。

（2）挖掘结果的有用性、正确性判定。数据挖掘是面向应用的，数据源本身的不完全性直接影响挖掘结果的有用性和正确性，对噪声、缺值和异常数据的处理方法的研究是数据预处理阶段的主要任务。要系统地研究如何判定挖掘结果的质量，包括结果的可靠性、正确性、有用性。

（3）交互性与领域知识在知识发现过程中的作用。知识发现过程是一个反复进行的过程，在不同的抽象层上人的参与和领域知识的指导可以加速挖掘进程。系统应该允许用户交互地进行数据挖掘请求，动态地改变数据焦点，进一步深化数据挖掘进程，灵活地从不同的角度和抽象层观察数据和数据挖掘结果。交互性和背景知识或领域知识能使数据挖掘过程具有可控性。

（4）知识的表达和解释机制。不同种类的知识表示是不同的，必须知道如何对知识进行表达才能使数据挖掘得到的知识从不同的角度以不同的方式被用户接受，所以挖掘出的知识表示及结果的解释也是研究方向之一，而且结果的过滤也很重要。

（5）分布数据源的挖掘。局域网和广域网的遍布使数据源具有分布性和异构性，从不同的格式化或非格式化的具有各式各样语义的数据源中挖掘知识是对数据挖掘提出的又一个挑战，它能促进并行和分布数据挖掘算法的发展。而且，数据的动态变化常常会产生数据不一致问题，因而挖掘出的知识也面临着更新与维护。

（6）私有权保护和数据安全。因为对数据可以从不同的角度及不同的抽象层来观察，知识发现有可能导致对私有权的侵犯或威胁数据安全，所以研究采取哪些措施防止暴露敏感信息是很重要的。

（7）KDD系统与其他决策支持系统的结合。当前的数据挖掘系统尚不能支持多平台，仅是面向某种特定应用的，有些是基于PC的，有些是面向大型主机的，有些是面向客户−服务器环境的，有的系统对数据库中记录的格式是有要求的，因此，数据挖掘系统与其他决策支持系统的有机结合是一个非常重要的问题。