数据挖掘的基本知识

§7.1　数据挖掘的基本知识

数据库技术和计算机网络技术的发展，使得信息的处理速度与传播速度变得迅速起来。信息在人们的日常生活以及经济生活中显得日益重要。目前，数据库技术已经成功的运用于诸如企业管理、政务处理、科学工程等事务数据处理中，并发挥着重要的作用。随着数据库技术快速发展，在数据库技术越来越多的实际应用的中，正以GB计量的速度产生着大量的数据。比如大型商场的顾客交易数据、证券市场的客户交易数据、现在已经广泛使用的Internet上的巨大的信息数据量，现代医疗技术设备的使用也存储了大量的医学数据等等。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前，数据库系统可以高效地实现数据的录入、查询、统计等功能，但是，无法发现数据之间存在的关系和规则，无法根据现有的数据预测未来的发展趋势，有效地利用这些数据作出推断。这就导致了“数据爆炸但知识贫乏”的现象。运用数据挖掘技术在这些数据当中我们可以找出“金子”来，发现出有用的信息和知识，为正确的决断、决策提供服务。

一、数据挖掘的概念

1．数据挖掘的定义

所谓数据挖掘，就是从大型数据库（包括Web数据库）的数据中提取人们感兴趣的知识。这些知识是隐含的、事先未知的潜在有用信息，提取的知识表示为概念(白领、金领)、规则（如果……那么……）、规律（买了计算机的人就会买软件）、模式（销售模式）等形式。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。

何为知识？从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一个交叉学科领域，受多个学科影响，涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域。还受数据挖掘方法的影响。它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。第五章所讲的内容从广义上也可归进数据挖掘的范畴。

2．数据挖掘与传统分析方法的区别

数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先未知，有效和可实用三个特征。先前未知的信息是指该信息是预先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值。在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系。

3．数据挖掘与数据仓库，在线分析处理（OLAP）之间的关系

数据仓库是一个用以更好地支持企业或组织的决策分析处理的数据集合，它有面向主题、集成、相对稳定、随时间不断变化四个特性，将数据仓库与传统的面向事务处理的数据库区分开来。数据仓库的关键技术包括数据的抽取、清洗、转换、加载和维护技术。

联机分析处理（OLAP）是以海量数据为基础的复杂分析技术。它支持各级管理决策人员从不同的角度、快速灵活地对数据仓库中的数据进行复杂查询和多维分析处理，并且能以直观易懂的形式将查询和分析结果展现给决策人员。OLAP使用的逻辑数据模型为多维数据模型。常用的OLAP多维分析操作有上卷、下钻、切片、切块、旋转等。多维数据模型在物理实现时，主要有三种方式：ROLAP结构、MOLAP结构和HOLAP结构。其中ROLAP是基于关系数据库的OLAP实现，MOLAP是基于多维数据组织的OLAP实现，HOLAP是基于混合数据组织的OLAP实现。

在理论研究上，OLAP技术的研究人员主要来自数据库界，重点研究CUBE压缩与计算、实体化视图的选择与维护、多维数据的索引和多维查询处理等技术，以便能够在海量数据上提供秒级的分析请求响应时间。数据挖掘技术的研究人员来自人工智能、统计、数据库界，其研究主要集中在各种挖掘算法和评价方法上，研究可伸缩的数据挖掘方法、基于约束的挖掘方法、复杂数据类型的挖掘等。

联机分析处理和数据挖掘虽然是数据仓库上获取两种不同目标的数据增值技术，但这两类技术如果能够在一定程度上融合，会使分析操作智能化，使挖掘操作目标化，从而全面提升商务智能技术的实用价值。即：一方面，联机分析技术可以为数据挖掘提供预期的挖掘对象和目标，避免挖掘的盲目性；另一方面，数据挖掘技术可以使联机分析处理智能化，减少分析人员手工操作的繁杂性，减轻分析人员的负担。例如，当分析人员在手工分析操作中发现离群点数据，可以有针对性地直接对此数据利用数据挖掘技术寻找原因，从中找出恶意违规或发现新的需求点。又如，在数据分析过程中，通过跟踪分析人员的操作过程，利用数据挖掘技术预测他可能感兴趣的操作和数据，提前预计算或预取数据，从而提高分析操作的响应时间。

二、数据挖掘的任务

数据挖掘的任务是从数据中发现知识或模式。模式有很多种，按功能可分有两大类：预测型（Predictive）模式和描述型（Descriptive）模式。

预测型模式是可以根据数据项的值精确定出某种结果的模式。挖掘预测型模式所使用的数据也都是可以明确知道结果的。例如，根据各种动物的资料，可以建立这样的模式：凡是胎生的动物都是哺乳类动物。当有新的动物资料时，就可以根据这个模式判别此动物是否是哺乳动物。

描述型模式是对数据中存在的规则做一种描述，或者根据数据的相似性把数据分组。描述型模式不能直接用于预测。例如，在地球上，70％的表面被水覆盖，30％是土地。

在实际应用中，根据模式的实际作用细分为以下5种：

1．关联模式（Association analysis）

在数据库的数据挖掘中，关联规则就是描述在一个事务中物品之间同时出现的规律的知识模式。数据库中的数据一般都存在着关联关系，也就是说，两个或多个变量的取值之间存在某种规律性。这种关联关系有简单关联和时序关联两种。简单关联，例如：购买面包的顾客中有90％的人同时购买牛奶。时序关联，例如：若AT＆T股票连续上涨两天且DEC股票不下跌，则第三天IBM股票上涨的可能性为75％。它在简单关联中增加了时间属性。

关联分析的目的是找出数据库中隐藏的关联网，描述一组数据项目的密切度或关系。有时并不知道数据库中数据的关联是否存在精确的关联函数，，即使知道也是不确定的，因此关联分析生成的规则带有置信度，置信度级别度量了关联规则的强度。

关联模型的一个典型例子是市场菜篮分析（Marketing Basket Analysis），通过挖掘数据派生关联规则，可以了解客户的行为，如图7.1所示。

图7.1　市场菜篮子分析

采用关联模型的成功典型案例是总部位于美国阿肯色州的Wal Mart零售商的“尿布与啤酒”的故事。Wal Mart拥有世界上最大的数据仓库系统，它利用数据挖掘工具对数据仓库中的原始交易数据进行分析，得到了一个意外发现：和尿布一起购买最多的商品竟然是啤酒。如果不是借助于数据仓库和数据挖掘，商家绝不可能发现这个隐藏在背后的事实：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30％～40％的人同时也为自己买一些啤酒。有了这个发现后，超市调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。

同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。比如：热销的商品可以放近一些，以便进一步刺激这些商品的销售；又比如，可以利用计算机硬件和软件的购买关联性，将硬件和软件放在商店的两端，以便诱发购买这些商品的顾客一路挑选其他商品（家庭安全系统）。

发现关联规则常用的算法是Apriori算法，先求出频繁项集。其主要的思想就是利用了频繁项集的子集仍是频繁项集的性质，首先寻找到1-频繁项集，扩充为2-可能频繁项集，再通过扫描数据库进行评价，得到2-频繁项集；依照由（k－1）-频繁项集扩充为k-可能频繁项集，再通过扫描数据库评价，得到k-频繁项集的方法，循环递推逐层搜索迭代，直到不能再有更长的频繁项集发现为止。找到的频繁项集的支持度都是满足大于或者等于最小支持度的。其次，对一个频繁项集，例如，ABD，如果确定一个规则AB→D，由于ABD是满足最小支持度的，所以，AB和D肯定也是满足最小支持度，只要计算可信度即可。

其中，#（ABD）和#（AB）分别表示项集ABD和AB的频度。如果)(DABConf→大于给定的最小可信度，那么AB→D就是一条满足要求的规则。所以，此算法的重点在于先找出频繁项集。

事务间的关联关系可以用支持度和置信度两个指标来衡量。如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣。因此，为了发现出有意义的关联规则，一般需要给定两个阈值：最小支持度和最小可信度。

2．分类模式（Classification）

分类模式是一个分类函数（分类器），该模型能够根据数据的属性将数据分派到不同的组中。即：分析数据的各种属性，并找出数据的属性模型，确定哪些数据属于哪些组。这样我们就可以利用该模型来分析已有数据，并预测新数据将属于哪一个组。

分类应用的实例很多。例如，我们可以将银行网点分为好、一般和较差三种类型，并以此分析这三种类型银行网点的各种属性，特别是位置、盈利情况等属性，并决定它们分类的关键属性及相互间关系。此后就可以根据这些关键属性对每一个预期的银行网点进行分析，以便决定预期银行网点属于哪一种类型。

3．回归模式（Regression）

回归模式的函数定义与分类模式相似，它们的差别在于分类模式的预测值是离散的，回归模式的预测值是连续的。如给出某种动物的特征，可以用分类模式判定这种动物是哺乳动物还是鸟类；给出某个人的教育情况、工作经验，可以用回归模式判定这个人的年工资在哪个范围内，是在6000元以下，还是在6000元到1万元之间，还是在1万元以上。

4．聚类模式（Clustering）

聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽可能小。与分类模式不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪一（几）个数据项来定义组。一般来说，业务知识丰富的人应该可以理解这些组的含义，如果产生的模式无法理解或不可用，则该模式可能是无意义的，需要回到上阶段重新组织数据。

聚类算法主要有划分法和层次法两种。划分法中聚类的个数事先给定。层次法是把所有的数据组织成一棵聚类树，对聚类树经过裁剪和组合。

（1）划分方法：给定一个N个对象的数据库，把数据划分为K个组。同时满足要求：每个组至少包含一个对象，每个对象必须属于且只属于一个组。常用的算法（如K-Means算法）是开始时为每个聚类指定一个初始中点，然后以初始中点为中心形成聚类，再用迭代法反复修改初始的聚类，直到无明显改进为止。常见算法有K-平均法，K-中心点法

（2）层次方法：层次分解，又有凝聚和分裂两种。一种是凝聚，即自底向上，一开始将每个对象作为单独的一个组，然后合并相似的对象，直到达到终止条件。另一种是分裂，即自顶向下，一开始将所有对象放在一个组中，然后分裂为更小的组，直到达到终止条件。

5．偏差分析（Deviation）

在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结果与参照之间的差别。

在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使用最普遍的模式。分类模式、回归模式、时间序列关联模式也被认为是受监督知识，因为在建立模式前数据的结果是已知的，可以直接用来检测模式的准确性，模式的产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数据作为样本，用另一部分数据来检验、校正模式。聚类模式、关联模式、序列模式则是非监督知识，因为在模式建立前结果是未知的，模式的产生不受任何监督。

三、数据挖掘的过程

1．确定业务对象

清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘则带有盲目性，是不会成功的。在医学领域的数据挖掘，我们必须跟医学专家进行交流，定义问题、并决定医学目标、确定关键人群、了解该问题目前的解决途径。这个步骤中的一个关键性的目的是决定数据挖掘的目标和衡量其成功的标准，并且准备出一份实现该项目计划的步骤。

2．数据准备

（1）数据的选择

搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据挖掘应用的数据。这包括最初的数据收集，对得到的原始数据进行抽样分析，列出数据类型（包括数据大小、格式，很可能还应包括数据的属性等级）。最初的数据探索可以回答部分数据挖掘的目的，从而肯定最初的假设，或产生对新特征的探求。

（2）数据的预处理

研究数据的质量，为进一步的分析作准备。这包括对数据库进行采样，以及对数据进行重要性和相关性检验。接着要对选出的数据进行净化处理，包括矫正、去除或忽略噪声，决定如何处理某些特殊值等等。在数据收集过程中完全去除噪声是非常困难的，这就意味着要求数据挖掘方法对噪声不是特别敏感，并要求以后加入的数据的噪声与现在的数据的噪声是近似的。缺失特征值产生了很大的问题，因为大多数的数据挖掘术要求有一个完整的数据记录，解决这一问题的通常方法是用最有可能的值去取代缺失值。新产生的数据可以通过衍生新特性、离散化、转换某些特性等途径加入到已经建构起来的数据行列之中去。最后采样得到的数据必须从已知数据库中分离出来，重新规范化来满足不同数据挖掘方法的需求。比如最初的原始资料可能会包括医生对病人情况的记录和一些原始图片，因为这些资料不适合于直接使用，我们通过处理这些资料和图片，提取有用的特征信息，取得第二手资料，加入数据库，所以如何有效进行规范化，就成为后续工作是否能够顺利进行的关键。

（3）数据的转换

将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。数据挖掘的算法繁多，常用的包括人工神经网络、决策树、遗传算法、最临近技术、规则归纳、可视化技术等。值得注意的是我们不能笼统地说某种算法优于其他算法。其中预测的精确性在很大程度上取决于被挖掘的数据，而方法的选择很多时候也取决于约定俗成的经验。数据挖掘不是一个单向的过程，即使对于同一个问题，也可能有多种算法。这个时候，需要评估对于某一特定问题和特定数据哪一种算法表现好。

3．数据挖掘

对所得到的经过转换的数据进行挖掘，用数据挖掘方法来揭示新发现，将数据转化为知识，如广义知识，关联知识，分类知识和预测型知识等等。

4．数据挖掘结果的评估

解释并评估结果。首先，得到的知识必须是精确的。其次，发现的知识必须对使用者是可以理解的，从而为使用者进行决策提供了坚实的基础。通常，知识的可理解性与参数的简洁性是相关的。最后，发掘的知识必须是有新意的，有使用价值的。对结论进行医学上的解释，并与最初的项目目标进行比较，通过使用不同的数据挖掘方式以期得到了改进后的模型。在整个数据挖掘的过程中可能包含着失败、错误的步骤，以及不同的尝试方法。从所有可能的方法中决定最后采用的方法，包括将方法按等级分类，选择最佳的方法，并记录下做这种选择的原因。

5．知识的同化

数据挖掘的最终目的是辅助决策。将分析所得到的知识集成到业务信息系统的组织结构中去，结合实际情况，调整竞争策略等。这也是数据挖掘和知识发现的另一个重要任务。

四、数据挖掘常用方法

目前，国外有许多研究机构、公司和学术组织在从事数据挖掘工具的研究和开发。这些数据挖掘工具采用的主要方法包括决策树、相关规则、神经元网络、遗传算法，以及可视化、OLAP联机分析处理等。另外也采用了传统的统计方法。以下着重介绍目前常用的几种数据挖掘技术及算法：

1．决策树

决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。比如，在贷款申请中，要对申请的风险大小做出判断，图7.2是为了解决这个问题而建立的一棵决策树，从中我们可以看到决策树的基本组成部分：决策节点、分支和叶子。

图7.2　决策树示意图

决策树中最上面的节点称为根节点，是整个决策树的开始。本例中根节点是“收入＞￥50000”，对此问题的不同回答产生了“是”和“否”两个分支。决策树的每个节点子节点的个数与决策树在用的算法有关。如CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。

每个分支要么是一个新的决策节点，要么是树的结尾，称为叶子。在沿着决策树从上到下遍历的过程中，在每个节点都会遇到一个问题，对每个节点上问题的不同回答导致不同的分支，最后会到达一个叶子节点。这个过程就是利用决策树进行分类的过程，利用几个变量（每个变量对应一个问题）来判断所属的类别（最后每个叶子会对应一个类别）。

假如负责借贷的银行官员利用上面这棵决策树来决定支持哪些贷款和拒绝哪些贷款，那么他就可以用贷款申请表来运行这棵决策树，用决策树来判断风险的大小。“年收入＞￥5000”和“高负债”的用户被认为是“高风险”，同时“收入＜￥50000”但“工作时间＞5年”的申请，则被认为“低风险”而建议贷款给他。

数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。常用的算法有CHAID、CART、Quest和C5.0。

建立决策树的过程，即树的生长过程是不断的把数据进行切分的过程，每次切分对应一个问题，也对应着一个节点。对每个切分都要求分成的组之间的“差异”最大。

各种决策树算法之间的主要区别就是对这个“差异”衡量方式的区别。对具体衡量方式算法的讨论超出了本文的范围，在此我们只需要把切分看成是把一组数据分成几份，份与份之间尽量不同，而同一份内的数据尽量相同。这个切分的过程也可称为数据的“纯化”。在上述例子中，包含两个类别——低风险和高风险。如果经过一次切分后得到的分组，每个分组中的数据都属于同一个类别，显然达到这样效果的切分方法就是我们所追求的。

这里讨论的例子都是非常简单的，树也容易理解，当然实际中应用的决策树可能非常复杂。假定我们利用历史数据建立了一个包含几百个属性、输出的类有十几种的决策树，这样的一棵树对人来说可能太复杂了，但每一条从根节点到叶子节点的路径所描述的含义仍然是可以理解的。决策树的这种易理解性对数据挖掘的使用者来说是一个显著的优点。

然而决策树的这种明确性可能带来误导。比如，决策树每个节点对应分割的定义都是非常明确毫不含糊的，但在实际生活中这种明确可能带来麻烦（凭什么说年收入￥50 000的人具有较小的信用风险而￥50000的人就没有）。

建立一颗决策树可能只要对数据库进行几遍扫描之后就能完成，这也意味着需要的计算资源较少，而且可以很容易的处理包含很多预测变量的情况，因此决策树模型可以建立得很快，并适合应用到大量的数据上。

决策树的缺点是所有的分割都受根节点的第一次分割的影响，只要第一次分割有一点点不同，那么由此得到的整个决策树就会完全不同。而且，通常的分割算法在决定怎么在一个节点进行分割时，都只考察一个预测变量，即节点用于分割的问题只与一个变量有关。这样生成的决策树在有些本应很明确的情况下可能变得复杂而且意义含混，为此目前新提出的一些算法开始在一个节点同时用多个变量来决定分割的方法。决策树很擅长处理非数值型数据，甚至有些决策树算法专为处理非数值型数据而设计。

2．人工神经网络

神经网络建立在自学习的数学模型基础之上。它可以对大量复杂的数据进行分析，并可以完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络常用于两类问题：分类和回归。

人工神经网络的基本处理单元为人工神经元，它的结构和功能可以用如图7.3所示的模型来描述。

图7.3　人工神经网络的节点：人工神经元

从外部环境或者别的神经元的输出构成该神经元的输入向量（x₁，x₂，…，x_n）^T，其中x_i为别的神经元的输出或兴奋水平。联结两个神经元的可调值称为权值。所有和神经元j相联结的权值构成向量W_j=（w_ji，w_j2， …，w_jn）^T，其中w_ji代表处理单元i和j之间的连接权值。通常再加上一个域值常数θ_j，则神经单元的计算过程可以表示为：

其中，f（a）为激励函数，最为常用的激励函数为Sigmoid函数：

或者双曲函数：

人工神经网络就是由这样许多神经元模型构成，这种由许多神经元组成的信息处理网络具有并行分布结构。每个神经元具有单一输出，并且能够与其他神经元连接，神经元之间的连接方法不同，则构成不同的网络模型。按照神经网络内部信息传递方向，神经网络可以分为两种类型：

（1）递归网络。在递归网络中，多个神经元互联组织成一个互联神经网络，如图7.4所示。所有节点都具有信息处理功能，而且每个节点既可以从外界接受输入，同时又可以向外界输出，有些神经元的输出被反馈至同层或前层神经元。因此，信号能够从正向和反向流通。Hopfield网络，Elmman网络和Jordan网络是递归网络有代表性的例子。递归网络又叫做反馈网络。

（2）前馈型神经网络。前馈型神经网络具有递阶分层结构，从信息处理能力看，网络中的节点分为两种，一种是输入节点，只负责从外界引入信息后向前传递给第一隐含层；另一种是具有处理能力的节点，包括各隐含层和输出层节点。从输入层至输出层的信号通过单向连接流通；神经元从一层连接至下一层，不存在同层神经元间的连接。因此这类网络很容易串联起来建立多层前馈网络。最常见的、应用最广泛的前馈型神经网络是多层感知器网络，它的层次结构和功能明了易懂，如图7.5所示，而且算法也比较成熟。

图7.4　递归网络的结构

图7.5　多层感知器网络的结构

应用多层感知器网络需要解决的关键问题是学习算法，1986年，以Rumelhart和McClelland为首的科研小组完整而简明地提出了误差反向传播（Error Back Propagation，EBP）算法，系统地解决了多层网络中隐含单元连接权的学习问题，使多层前馈网络能逼近任意非线性函数，从而为多层前馈网络在科学技术领域中的广泛应用奠定了坚实基础。

BP算法的基本思想是，学习过程由信号的正向传播与误差的反向传播两个过程组成。正向传播时，输入样本从输入层传入，经各隐含层逐层处理后，传向输出层。若输出层的实际输出与期望的输出（教师信号）不符，则转入误差的反向传播阶段。误差反传是将输出误差以某种形式通过隐含层向输入层逐层反传，并将误差分摊给各层的所有单元，从而获得各层单元的误差信号，此误差信号即作为修正各单元权值的依据。这种信号正向传播与误差反向传播的各层权值调整过程周而复始地进行。权值不断调整的过程，也就是网络的学习训练过程，此过程一直进行到网络输出的误差减少到可以接受的程度，或进行到预先设定的学习次数为止。

将BP算法用于具有非线性转移函数的三层前馈网络，可以以任意精度逼近任何非线性函数，这一非凡优势使多层前馈网络得到越来越广泛的应用。然而，标准的BP算法在实际应用中暴露出不少内在的缺陷，比如，在训练时容易形成局部极小而得不到全局最优；隐节点的选取大多数时候靠试凑，缺少理论指导；训练次数比较多，使得网络学习效率比较低，收敛速度比较慢；同时训练时学习新样本有遗忘旧样本的趋势。

针对上述问题，国内外已提出不少有效的改进算法，如增加动量项、自适应调节学习速率、加入遗忘机制和与其他算法结合优化等。

3．遗传算法

遗传算法是一种基于自然群体遗传进化机制的高效探索算法，是美国学者Holland教授于1975年首先提出来的。它摒弃了传统的寻优搜索方式，而是模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机优化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优或者近似最优解。

Holland创建的遗传算法是一种概率搜索算法，它是利用某种编码技术作用于称为染色体的数串，其基本思想是模拟进化过程。该算法通过有组织地然而是随机地信息交换重新组合那些适应性好的串，在每一代中，利用上一代串结构中适应好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。遗传算法是一类随机化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串，类似于自然进化。遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。

基因：组成染色体的单元，可以表示为一个二进制位，一个整数或一个字符等。

染色体或个体：表示待求解问题的一个可能解，由若干基因组成，是GA操作的基本对象。

群体：一定数量的个体组成了群体，表示GA的遗传搜索空间。

适应度或适度：代表一个个体所对应解的优劣，通常由某一适应度函数表示。

选择：GA的基本操作之一，即根据个体的适应度，在群体中按照一定的概率选择可以作为父本的个体，选择依据是适应度大的个体被选中的概率高。选择操作体现了适者生存，优胜劣汰的进化机制。

交叉：GA的基本操作之一，即将父本个体按照一定的概率随机地交换基因形成新的个体。

变异：GA的基本操作之一，即按照一定概率随机改变某个体的基因值。

串行遗传算法基本步骤

（1）对待解决问题进行编码；

（2）随机初始化群体X(0)：=（x₁，x₂，…，x_n）；

（3）对当前群体X(t)中每个个体x_i计算其适应度F(x_i)，适应度表示了该个体的性能好坏；

（4）应用选择算子产生中间代Xr(t)；

（5）对Xr(t)应用其他的算子，产生新一代群体X(t+1)。这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想；

（6）t=t+1；如果不满足终止条件继续(3)。

遗传算法是模拟生物在自然环境中的遗传和进化过程，而形成的一种自适应全局优化概率搜索算法。它提供了一种求解复杂系统优化问题的通用框架，它基本上不依赖于问题的领域，故广泛地应用在很多学科。如：函数及组合优化、生产调度、自动控制、图像处理、自动编程、机器学习和人工生命等等

遗传算法在医学中也有非常广泛的应用，比如它可以用于医学图像和信号处理、治疗优化、医疗特征参数估计和医学决策支持系统中诊断规则的提取等。

遗传算法的特点是全局寻优算法，不易陷入局部最优，隐并行性，适合大规模并行分布处理，易于和其他技术如神经网络相结合，形成性能更优的问题求解方法，可以解决复杂的优化求解问题，挖掘对象属性之间的内部关系，不要求对象属性的独立性和具有较强的容噪特性。

4．粗糙集方法

粗糙集理论是20世纪80年代波兰数学家Z．Pawlak首先提出的一个数据分析数学工具，它将分类与知识联系在一起。在关系型数据库中，将一张表的行元素看成对象，列元素看成属性（分为条件属性和决策属性）。等价关系R定义为对象集中对象在某个（或某几个）属性上取相同的值，这样的等价关系将对象集划分成相应于等价关系R的等价类。可以进行属性的约简，删除多余的对象，在最小约简上，分属性为条件属性上的等价类E与决策属性上的等价类Y之间有3种情况：下近似——Y包含E；上近似——Y和E的交非空；无关——Y和E的交为空。对下近似建立确定性规则Y=＞E，对上近似建立不确定性规则（含可信度），对无关情况不存在规则。

粗糙集方法论广泛应用于决策支持系统中。例如，在诊断某种疾病时，该疾病表征可能有很多。根据以往对该病的诊断记录可以形成一个数据表。该表的属性分为两类：条件属性和结论属性。条件属性可以是病人出现没有出现某症状；结论属性就是该疾病。通过属性约简，可以分析出规则，在规则中用较少的属性对是否该疾病作出判断。

5．统计分析方法。利用统计学不完全归纳近似推理和不确定理论中的置信度理论，通过对数据对象的大量实例的考察，在一定置信度下建立字段间的统计关系。在数据库字段项之间存在两种关系：函数关系（能用函数公式表示的确定性关系）和相关关系（不能用函数公式表示，但仍是相关确定关系）。对它们的分析采用如下方法：回归分析、相关分析、主成分分析。回归分析方法常常可以建立数学模型用于预测；相关分析可以分析建立的数学模型是否有效；主成分分析可以使我们从繁多的影响结论的因素中找出关键性因素，实现对主要问题的把握。

6．最近邻技术。通过k个与之最相近的历史记录的组合来辨别新记录。这种技术可用作聚类、偏差分析等挖掘任务。

7．模糊集方法。模糊性是客观存在的。在实际中，系统的复杂性越高，精确化能力就越低，即模糊性就越强，这是Zadeh总结出的互克性原理。利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。

8．可视化技术。可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清楚，为用户参与KDD的过程提供方便。例如，把数据库中的多维数据变成多种图形，这对揭示数据的状况、内在本质及规律性起了很大作用。

五、数据挖掘技术的发展趋势

随着信息量的迅速扩张和应用的不断深入，对数据库的挖掘算法必然要适应数据的不断更新改造，也就是说所发现的知识应该随着数据库的内容改变动态变化。例如，发现关联规则的很多算法都基于两个共同的前提：（1）交易数据库中的元组数不变；（2）最小支持度也不变。关联规则的增量式更新算法则是对以上两个前提不成立时的关联规则的发现问题。也就是说一种是考虑最小支持度最小可信度不变，数据库中的元组数发生了变化，寻求在关联规则的算法；另一种是数据库中的元组数不发生改变，而最小支持度最小可信度发生变化后寻求关联规则的算法。这就是数据挖掘的知识维护与更新的问题研究。

另一方面，随着科学技术的发展，信息形式的多样化，要挖掘数据的输入形式也越来越复杂。实际应用中经常需要对一些半结构化、非结构化的复杂类型数据形式，如文本、数学公式、图形、图像、视频或Web资源等等。目前，挖掘的知识类型已经由关联规则、分类、聚类、相似模式、混沌模式、预测等扩展到了非结构化、半结构化文本、客户访问模式、音视频等复杂类型的数据。分子结构数据库的挖掘、生物信息挖掘、XML文档等新的数据挖掘领域已经出现。在医学中经常也会经常对一些医学图像进行类比，通过类比对某种疾病进行分析，然后作出判断等。

Web上有海量的数据信息，怎样对这些数据进行处理后应用，成了现今数据库技术的研究热点。数据挖掘就是从大量的数据中发现隐含的规律性的内容，解决数据的应用质量问题。充分利用有用的数据，废弃虚伪无用的数据，是数据挖掘技术的最重要的应用。相对于Web的数据而言，传统的数据库中的数据结构性很强，即其中的数据为完全结构化的数据，而Web上的数据最大特点就是半结构化。所谓半结构化是相对于完全结构化的传统数据库的数据而言。显然，面向Web的数据挖掘比面向单个数据仓库的数据挖掘要复杂得多。

Web上的数据与传统的数据库中的数据不同，传统的数据库都有一定的数据模型，可以根据模型来具体描述特定的数据。而Web上的数据非常复杂，没有特定的模型描述，每一站点的数据都各自独立设计，并且数据本身具有自述性和动态可变性。因而，Web上的数据具有一定的结构性，但因自述层次的存在，从而是一种非完全结构化的数据，这也被称之为半结构化数据。半结构化是Web上数据的最大特点。所以，研究能处理复杂类型数据的挖掘算法成为当今数据挖掘的重要发展趋势。