数据挖掘技术的算法与应用【转】

研究方向前沿读书报告

数据挖掘技术的算法与应用



目录

第一章 数据仓库... 5

1.1 概论... 5

1.2 数据仓库体系结构... 6

1.3 数据仓库规划、设计与开发... 7

1.3.1 确定范围... 7

1.3.2 环境评估... 7

1.3.3 分析... 7

1.3.4 设计... 8

1.3.5 开发... 8

1.3.5 测试... 8

1.3.6 运行... 8

1.4 小结... 9

第二章 数据挖掘... 9

2.1 概论... 9

2.2 数据挖掘研究的内容和本质... 10

2.2.1 广义知识... 10

2.2.2 关联知识... 10

2.2.3 分类知识... 11

2.2.4 预测型知识... 11

2.3 数据挖掘流程... 11

2.3.1 确定业务对象... 12

2.3.2 数据准备... 12

2.3.3 数据挖掘... 12

2.3.4 结果分析... 12

2.3.5 知识的同化... 13

2.4 数据挖掘的方法... 13

2.4.1 神经网络方法... 13

2.4.2 遗传算法... 13

2.4.3 决策树方法... 14

2.4.4 粗集方法... 14

2.4.5 覆盖正例排斥反例方法... 14

2.4.6 统计分析方法... 14

2.4.7 模糊集方法... 14

2.6 数据挖掘工具的现状... 15

2.7 数据挖掘未来研究方向及热点... 16

2.4.1 网站的数据挖掘... 16

2.4.2 生物信息或基因数据挖掘... 17

2.4.3 文本的数据挖掘... 17

2.4.4 2005年十大热点问题... 17

2.5 小结... 18

第三章  关联规则... 18

3.1 概论... 18

3.2 基本概念... 18

3.3 关联规则种类... 19

3.4 主要研究方向和典型算法分析... 20

3.4.1 多循环方式的采掘算法... 20

3.4.2 增量式更新算法... 21

3.4.3 并行发现算法... 22

3.5 频集算法的几种优化方法... 24

3.4.1 基于划分的方法... 24

3.4.2 基于Hash的方法... 24

3.4.3 基于采样的方法... 25

3.4.4 减少交易的个数... 25

3.4.5 其他的频集挖掘方法... 25

3.4.6 提高效率的几种方法说明... 26

3.6 多层和多维关联规则的挖掘... 27

3.7 关联规则价值衡量的方法... 28

3.6.1 系统客观层面... 28

3.6.2 用户主观层面... 29

3.8 选择规则的方法... 29

3.9 小结... 30

第四章  正负关联规则研究... 30

4.1 概述... 30

4.2 研究现状... 31

4.3 关联规则具体研究... 31

4.3.1 关联规则挖掘的矩阵算法... 31

4.3.2 基于相关系数的正、负关联规则... 32

4.3.3 项集的相关性判断正负关联规则... 32

4.3.4 正、负关联规则间的置信度关系研究... 33

4.3.5 挖掘正负关联规则... 33

4.3.6 布尔加权关联规则的几种开采算法及比较... 34

4.3.6 关联规则的增量式更新... 34

4.3.7 并行化的分组关联规则算法... 36

4.3.8 分布式的数据挖掘... 36

4.6 研究方向的理论意义和实用价值... 38

4.7 小结... 38

第五章  可视化研究... 39

5.1 概述... 39

5.2 研究现状... 39

5.3 研究方向的理论意义和实用价值... 39

5.4 可视化具体研究... 39

5.4.1 矩阵表示... 39

5.4.2 规则多边形... 40

5.4.3 平行坐标系... 41

5.5 小结... 41

参考资料：... 42

















本报告的组织

第一章        数据仓库的内容

第二章        数据挖掘的内容

第三章        关联规则的内容

第四章        正负关联规则的研究，各种方法的具体算法 实现。

第五章        可视化研究


























第一章  数据仓库
1.1 概论

传统数据库在日常的管理事务处理中获得了巨大的成功，但是对管理人员的决策分析要求却无法满足。因为，管理人员常常希望能够对组织中的大量数据进行分析，了解业务的发展趋势。而传统数据库只保留了当前的业务处理信息，缺乏决策分析所需要的大量历史信息。为满足管理人员的决策分析需要，就需要在数据库的基础上产生适应决策分析的数据环境 ——数据仓库（DW，Data Warehouse）。[1]

目前，数据仓库一词尚没有一个统一的定义，著名的数据仓库专家W。H。Inmon在其著作《Building the Data Warehouse》一书中给予如下描述：数据仓库（Data Warehouse）是一个面向主题的（Subject Oriented）、集成的（Integrate）、相对稳定的（Non-Volatile）、反映历史变化（Time Variant）的数据集合，用于支持管理决策。对于数据仓库的概念我们可以从两个层次予以理解，首先，数据仓库用于支持决策，面向分析型数据处理，它不同于企业现有的操作型数据库；其次，数据仓库是对多个异构的数据源有效集成，集成后按照主题进行了重组，并包含历史数据，而且存放在数据仓库中的数据一般不再修改。

根据数据仓库概念的含义，数据仓库拥有以下四个特点：

1、面向主题。操作型数据库的数据组织面向事务处理任务，各个业务系统之间各自分离，而数据仓库中的数据是按照一定的主题域进行组织。主题是一个抽象的概念，是指用户使用数据仓库进行决策时所关心的重点方面，一个主题通常与多个操作型信息系统相关。

2、集成的。面向事务处理的操作型数据库通常与某些特定的应用相关，数据库之间相互独立，并且往往是异构的。而数据仓库中的数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加工、汇总和整理得到的，必须消除源数据中的不一致性，以保证数据仓库内的信息是关于整个企业的一致的全局信息。

3、相对稳定的。操作型数据库中的数据通常实时更新，数据根据需要及时发生变化。数据仓库的数据主要供企业决策分析之用，所涉及的数据操作主要是数据查询，一旦某个数据进入数据仓库以后，一般情况下将被长期保留，也就是数据仓库中一般有大量的查询操作，但修改和删除操作很少，通常只需要定期的加载、刷新。

4、反映历史变化。操作型数据库主要关心当前某一个时间段内的数据，而数据仓库中的数据通常包含历史信息，系统记录了企业从过去某一时点(如开始应用数据仓库的时点)到目前的各个阶段的信息，通过这些信息，可以对企业的发展历程和未来趋势做出定量分析和预测。

通过利用数据仓库系统，人们可以获得许多方面的知识。[7]
1.2 数据仓库体系结构

企业数据仓库的建设，是以现有企业业务系统和大量业务数据的积累为基础。数据仓库不是静态的概念，只有把信息及时交给需要这些信息的使用者，供他们做出改善其业务经营的决策，信息才能发挥作用，信息才有意义。而把信息加以整理归纳和重组，并及时提供给相应的管理决策人员，是数据仓库的根本任务。因此，从产业界的角度看，数据仓库建设是一个工程，是一个过程。整个数据仓库系统是一个包含四个层次的体系结构，具体由下图表示:

·数据源：是数据仓库系统的基础，是整个系统的数据源泉。通常包括企业内部信息和外部信息。内部信息包括存放于RDBMS中的各种业务处理数据和各类文档数据。外部信息包括各类法律法规、市场信息和竞争对手的信息等等。

·数据的存储与管理：是整个数据仓库系统的核心。数据仓库的真正关键是数据的存储和管理。数据仓库的组织管理方式决定了它有别于传统数据库，同时也决定了其对外部数据的表现形式。要决定采用什么产品和技术来建立数据仓库的核心，则需要从数据仓库的技术特点着手分析。针对现有各业务系统的数据，进行抽取、清理，并有效集成，按照主题进行组织。数据仓库按照数据的覆盖范围可以分为企业级数据仓库和部门级数据仓库（通常称为数据集市）。

·OLAP服务器：对分析需要的数据进行有效集成，按多维模型予以组织，以便进行多角度、多层次的分析，并发现趋势。其具体实现可以分为：ROLAP、MOLAP和HOLAP。ROLAP基本数据和聚合数据均存放在RDBMS之中；MOLAP基本数据和聚合数据均存放于多维数据库中；HOLAP基本数据存放于RDBMS之中，聚合数据存放于多维数据库中。

·前端工具：主要包括各种报表工具、查询工具、数据分析工具、数据挖掘工具以及各种基于数据仓库或数据集市的应用开发工具。其中数据分析工具主要针对OLAP服务器，报表工具、数据挖掘工具主要针对数据仓库。[8]
1.3 数据仓库规划、设计与开发

    对企业自身来说，数据仓库的建设是一个系统工程，是一个不断建立、发展、完善的过程，通常需要较长的时间。这就要求各企业对整个系统的建设提出一个全面、清晰的远景规划及技术实施蓝图，将整个项目的实施分成若干个阶段，以“总体规划、分步实施、步步见效”为原则，不仅可迅速从当前投资中获得收益，而且可以在已有的基础上，结合其他已有的业务系统，逐步构建起完整、健壮的数据仓库系统。

企业数据仓库的建设通常按照快速原型法予以实施，主要包括：确定范围、环境评估、分析、设计、开发、测试和运行等几个阶段。同时企业数据仓库又是一个在原型的基础上进行不断迭代的过程。
1.3.1 确定范围

确定范围的主要任务包括了解方向性分析处理需求，确定信息需求，确定数据覆盖范围。方向性需求包括：决策类型、决策者感兴趣的问题（或对象）等。在确定范围时应该重视的因素是必须用户驱动和数据驱动相结合，同时可以借鉴国内外已有的成功经验。
1.3.2 环境评估

环境评估是对企业数据仓库系统建设的硬件环境和软件环境进行选型和准备。在硬件平台选择中需要选择与数据仓库系统规模相适应的核心服务器，同时我们认为数据仓库系统平台与业务处理平台应该相分离。软件平台的选择主要包括数据仓库引擎、OLAP引擎、前端分析展现工具的选择。产品进行测试是软件选型的一种有效方法，各个企业可以根据自身的数据状况对各类产品进行测试。
1.3.3 分析

分析阶段主要包括两个方面的任务是深入了解数据源和分析数据仓库系统所包含的主题域及其相互之间的关系。分析阶段必须坚持用户参与，并且与原有系统开发或维护人员进行深入的沟通。

需求分析包括一下的工作：确定数据仓库的粒度；确定候选的衡量指标（Candidate Measure）、事实表以及维度，包括确定维度的层次结构；构建初始的多维模型。[5]
1.3.4 设计

数据仓库设计的主要任务包括与操作型系统接口的设计和数据仓库本身的设计两个部分的内容。其中与操作型系统接口的设计主要是指数据抽取、清理、转换和刷新策略的设计。从多个不同的数据源中抽取数据，需要解决数据的不一致性，保证数据的质量。其中的不一致性主要包含模式冲突和语义冲突。从操作型数据库模型到数据仓库模型的转变需要大量细致的工作，例如：－消除纯粹是操作型的数据；－将包含在多个表中的有关数据进行合理合并；－适当增加部分导出数据；－在码值中增加时间关键字；－按照合适的数据粒度进行综合。

数据仓库本身的设计包括数据仓库逻辑数据模型的设计、数据仓库物理数据模型的设计。由于目前数据仓库产品尚未形成一套统一的标准，因此在数据仓库设计阶段必须要有数据仓库专家和数据仓库系统产品提供商的参与。

目前，主流的数据仓库建模技术分为两种：实体关系建模（Entity-Relationship Modeling）以及维建模（Dimension Modeling）。其中，维建模又分为星型结构以及雪花型结构等。[5]

数据仓库设计工具的选择有：

EDA/SQL。(SAS Institute Inc。)SAS研究所

(Sybase,Inc。)Sysbase有限公司[3]

CA公司的Erwin[5]
1.3.5 开发

开发阶段所要完成的主要内容包括数据仓库建模、数据抽取和加载模块、数据访问模块以及开发实际应用。实际应用开发建议采用撌缘銛的方法，从急需的业务开始进行，应该重视的因素包括必须有行业专家的参与，同时必须有数据仓库专家的参与。
1.3.5 测试

测试是保证系统可靠性的重要手段。数据仓库测试与一般软件系统测试不同的是数据仓库的测试不仅包括对软件系统的测试，同时包括对数据的测试。在测试阶段必须保证测试的充分性，同时注意测试数据的覆盖范围。
1.3.6 运行

系统运行主要包括用户培训、数据加载、数据访问及应用等。在数据仓库系统的运行过程中，不断收集用户新的需求。

数据仓库系统的建设不可能一蹴而就，它是一个不断建立、完善、健全的过程。这个过程是随着业务量、业务范围和客户的不断发展而发展的，其成长的速度非常之快，同时随着业务的发展，数据仓库的价值也将随之增长。[8]
1.4 小结

   本章主要介绍说明数据仓库的相关概念、体系结构和设计开发等。为数据挖掘的前期工作做准备。为数据挖掘提供良好的环境。当然，数据仓库并不是数据挖掘的先决条件，因为有很多数据挖掘可直接从操作数据源中挖掘信息。
第二章  数据挖掘
2.1 概论

数据挖掘（Data Mining）是发现数据中有用模式的过程。数据挖掘会话的目的是确定数据的趋势和模式。[4] 数据挖掘强调对大量观测到的数据库的处理。它是涉及数据库管理，人工智能，机器学习，模式识别，及数据可视化等学科的边缘学科。用统计的观点看，它可以看成是通过计算机对大量的复杂数据集的自动探索性分析。

顾名思义, 数据挖掘就是从大量的数据中挖掘出有用的信息。它是根据人们的特定要求，从浩如烟海的数据中找出所需的信息来，供人们的特定需求使用。2000年7月，IDC发布了有关信息存取工具市场的报告。1999年，数据挖掘市场大概约为7。5亿美元，估计在下个5年内市场的年增长率为32。4%，其中亚太地区为26。6%。到2002年，该市场会发展到22亿美元。据国外专家预测，随着数据量的日益积累和计算机的广泛应用，在今后的5—10年内，数据挖掘将在中国形成一个新型的产业。

数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系，从而促进信息的传递。现在数据挖掘技术在商业应用中已经可以马上投入使用，因为对这种技术进行支持的三种基础技术已经发展成熟，他们是：(1) 海量数据搜集；(2)强大的多处理器计算机；(3)数据挖掘算法。Friedman[1997]列举了四个主要的技术理由激发了数据挖掘的开发、应用和研究的兴趣：（1）超大规模数据库的出现，例如商业数据仓库和计算机自动收集的数据记录；（2）先进的计算机技术，例如更快和更大的计算能力和并行体系结构；（3）对巨大量数据的快速访问；（4） 对这些数据应用精深的统计方法计算的能力。

商业数据库现在正在以一个空前的速度增长，并且数据仓库正在广泛地应用于各种行业；对计算机硬件性能越来越高的要求，也可以用现在已经成熟的并行多处理机的技术来满足；另外数据挖掘算法经过了这10多年的发展也已经成为一种成熟，稳定，且易于理解和操作的技术。

随着在80年代末一个新的术语，它就是数据库中的知识发现，简称KDD(Knowledge discovery in database)。它泛指所有从源数据中发掘模式或联系的方法，人们接受了这个术语，并用KDD来描述整个数据发掘的过程，包括最开始的制定业务目标到最终的结果分析，而用数据挖掘（data mining）来描述使用挖掘算法进行数据挖掘的子过程。[9]

数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先未知,有效和可实用三个特征。

基于并行系统的数据库管理系统也给数据挖掘技术的应用带来了便利。如果你有一个庞大而复杂的数据挖掘问题要求通过访问数据库取得数据，那么效率最高的办法就是利用一个本地的并行数据库。

现在面临一个尴尬的境地——数据丰富信息匮乏（data rich but information poor）！快速增长的海量数据，已经远远的超过了人们的理解能力，如果不借助强有力的工具，很难弄清大堆数据中所蕴含的知识。结果，重要决策只是基于制定决策者的个人经验，而不是基于信息丰富的数据。数据挖掘就这样应运而生，数据挖掘填补了数据和信息之间的鸿沟。[11]
2.2 数据挖掘研究的内容和本质

随着DM/KDD研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三根强大的技术支柱：数据库、人工智能和数理统计。因此，KDD大会程序委员会曾经由这三个学科的权威人物同时来任zhuxi。目前DM/KDD的主要研究内容包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘等。

数据挖掘所发现的知识最常见的有以下四类：
2.2.1 广义知识

广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数据的概括、精炼和抽象。

广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约等。数据立方体还有其他一些别名，如“多维数据库”、“实现视图”、“OLAP"等。该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如计数、求和、平均、最大值等，并将这些实现视图储存在多维数据库中。既然很多聚集函数需经常重复计算，那么在多维数据立方体中存放预先计算好的结果将能保证快速响应，并可灵活地提供不同角度和不同抽象层次上的数据视图。另一种广义知识发现方法是加拿大SimonFraser大学提出的面向属性的归约方法。这种方法以类SQL语言表示数据挖掘查询，收集数据库中的相关数据集，然后在相关数据集上应用一系列数据推广技术进行数据推广，包括属性删除、概念树提升、属性阈值控制、计数及其他聚集函数传播等。
2.2.2 关联知识

它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为著名的关联规则发现方法是R。Agrawal提出的Apriori算法。关联规则的发现可分为两步。第一步是迭代识别所有的频繁项目集，要求频繁项目集的支持率不低于用户设定的最低值；第二步是从频繁项目集中构造可信度不低于用户设定的最低值的规则。识别或发现所有频繁项目集是关联规则发现算法的核心，也是计算量最大的部分。
2.2.3 分类知识

它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知识。最为典型的分类方法是基于决策树的分类方法。它是从实例集中构造决策树，是一种有指导的学习方法。该方法先根据训练子集（又称为窗口）形成决策树。如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到窗口中，重复该过程一直到形成正确的决策集。最终结果是一棵树，其叶结点是类名，中间结点是带有分枝的属性，该分枝对应该属性的某一可能值。　　数据分类还有统计、粗糙集（RoughSet）等方法。线性回归和线性辨别分析是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。最近也有人研究使用神经网络方法在数据库中进行分类和规则提取。
2.2.4 预测型知识

它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可以认为是以时间为关键属性的关联知识。

目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。1968年Box和Jenkins提出了一套比较完善的时间序列建模理论和分析方法，这些经典的数学方法通过建立随机模型，如自回归模型、自回归滑动平均模型、求和自回归滑动平均模型和季节调整模型等，进行时间序列的预测。由于大量的时间序列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因此，仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确的预测任务。为此，人们提出了基于统计学和基于精确性的再训练方法，当发现现存预测模型不再适用于当前数据时，对模型重新训练，获得新的权重参数，建立新的模型。也有许多系统借助并行算法的计算优势进行时间序列预测。

此外，还可以发现其他类型的知识，如偏差型知识(Deviation)，它是对差异和极端特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数据聚类外的离群值等。所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需要。[9]
2.3 数据挖掘流程

　　数据挖掘是指一个完整的过程,该过程从大型数据库中挖掘先前未知的,有效的,可实用的信息,并使用这些信息做出决策或丰富知识。
　　数据挖掘环境可示意如下图:

　　　下图描述了数据挖掘的基本过程和主要步骤

数据挖掘的基本过程和主要步骤：

在数据挖掘中被研究的业务对象是整个过程的基础,它驱动了整个数据挖掘过程,也是检验最后结果和指引分析人员完成数据挖掘的依据和顾问。

过程中各步骤的大体内容如下:
2.3.1 确定业务对象

清晰地定义出业务问题,认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结构是不可预测的,但要探索的问题应是有预见的,为了数据挖掘而数据挖掘则带有盲目性,是不会成功的。
2.3.2 数据准备

(1) 数据的选择

搜索所有与业务对象有关的内部和外部数据信息,并从中选择出适用于数据挖掘应用的数据。

(2) 数据的预处理

研究数据的质量,为进一步的分析作准备。并确定将要进行的挖掘操作的类型。

(3) 数据的转换

将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。
2.3.3 数据挖掘

　　对所得到的经过转换的数据进行挖掘。除了完善从选择合适的挖掘算法外,其余一切工作都能自动地完成。
2.3.4 结果分析

　　解释并评估结果。其使用的分析方法一般应作数据挖掘操作而定,通常会用到可视化技术。
2.3.5 知识的同化

　将分析所得到的知识集成到业务信息系统的组织结构中去。
　　数据挖掘过程的分步实现,不同的步会需要是有不同专长的人员,他们大体可以分为三类。

业务分析人员:要求精通业务,能够解释业务对象,并根据各业务对象确定出用于数据定义和挖掘算法的业务需求。

数据分析人员:精通数据分析技术,并对统计学有较熟练的掌握,有能力把业务需求转化为数据挖掘的各步操作,并为每步操作选择合适的技术。

数据管理人员:精通数据管理技术,并从数据库或数据仓库中收集数据。
　　从上可见,数据挖掘是一个多种专家合作的过程,也是一个在资金上和技术上高投入的过程。这一过程要反复进行牞在反复过程中，不断地趋近事物的本质，不断地优先问题的解决方案。数据重组和细分添加和拆分记录选取数据样本可视化数据探索聚类分析神经网络、决策树数理统计、时间序列结论综合解释评价数据知识数据取样数据探索数据调整模型化评价。[9]
2.4 数据挖掘的方法
2.4.1 神经网络方法

神经网络由于本身良好的健壮性、自组织自适应性、并行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。典型的神经网络模型主要分3大类：以感知机、BP反向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以Hopfield的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以ART模型、Koholon模型为代表的，用于聚类的自组织映射方法。神经网络方法的缺点是"黑箱"性，人们难以理解网络的学习和决策过程。
2.4.2 遗传算法

遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中被加以应用。

Sunil已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一[4]。遗传算法的应用还体现在与神经网络、粗集等技术的结合上。如利用遗传算法优化神经网络结构，在不增加错误率的前提下，删除多余的连接和隐层单元；用遗传算法和BP算法结合训练神经网络，然后从网络提取规则等。但遗传算法的算法较复杂，收敛于局部极小的较早收敛问题尚未解决。
2.4.3 决策树方法

决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。最有影响和最早的决策树方法是由Quinlan提出的著名的基于信息熵的ID3算法。它的主要问题是：ID3是非递增学习算法；ID3决策树是单变量决策树，复杂概念的表达困难；同性间的相互关系强调不够；抗噪性差。针对上述问题，出现了许多较好的改进算法，如 Schlimmer和Fisher设计了ID4递增式学习算法;钟鸣，陈文伟等提出了IBLE算法等。
2.4.4 粗集方法

粗集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。粗集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基础。但粗集的数学基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在的。因此连续属性的离散化是制约粗集理论实用化的难点。现在国际上已经研制出来了一些基于粗集的工具应用软件，如加拿大Regina大学开发的KDD-R;美国Kansas大学开发的LERS等。
2.4.5 覆盖正例排斥反例方法

它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则保留。按此思想循环所有正例种子，将得到正例的规则(选择子的合取式)。比较典型的算法有Michalski的AQ11方法、洪家荣改进的AQ15方法以及他的AE5方法。
2.4.6 统计分析方法

在数据库字段项之间存在两种关系：函数关系(能用函数公式表示的确定性关系)和相关关系(不能用函数公式表示，但仍是相关确定性关系)，对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用统计(求大量数据中的最大值、最小值、总和、平均值等)、回归分析(用回归方程来表示变量间的数量关系)、相关分析(用相关系数来度量变量间的相关程度)、差异分析(从样本统计量的值得出差异来确定总体参数之间是否存在差异)等。
2.4.7 模糊集方法

即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础上，提出了定性定量不确定性转换模型--云模型，并形成了云理论。

2.5 如何评价数据挖掘软件

越来越多的软件供应商加入了数据挖掘这一领域的竞争。用户如何正确评价一个商业软件，选择合适的软件成为数据挖掘成功应用的关键。

评价一个数据挖掘软件主要应从以下四个主要方面：

⑴计算性能：如该软件能否在不同的商业平台运行；软件的架构；能否连接不同的数据源；操作大数据集时，性能变化是线性的还是指数的;算的效率；是否基于组件结构易于扩展；运行的稳定性等；

⑵功能性：如软件是否提供足够多样的算法；能否避免挖掘过程黑箱化；软件提供的算法能否应用于多种类型的数据；用户能否调整算法和算法的参数；软件能否从数据集随机抽取数据建立预挖掘模型；能否以不同的形式表现挖掘结果等；

⑶可用性：如用户界面是否友好；软件是否易学易用；软件面对的用户：初学者，高级用户还是专家？错误报告对用户调试是否有很大帮助；软件应用的领域：是专攻某一专业领域还是适用多个领域等；

⑷辅助功能：如是否允许用户更改数据集中的错误值或进行数据清洗；是否允许值的全局替代；能否将连续数据离散化；能否根据用户制定的规则从数据集中提取子集；能否将数据中的空值用某一适当均值或用户指定的值代替；能否将一次分析的结果反馈到另一次分析中，等等。
2.6 数据挖掘工具的现状

比较著名的有IBM Intelligent Miner、SAS Enterprise Miner、SPSS Clementine等，它们都能够提供常规的挖掘过程和挖掘模式。

(1) Intelligent Miner

由美国IBM公司开发的数据挖掘软件Intelligent Miner是一种分别面向数据库和文本信息进行数据挖掘的软件系列,它包括Intelligent Miner for Data和Intelligent Miner for Text。Intelligent Miner for Data可以挖掘包含在数据库、数据仓库和数据中心中的隐含信息,帮助用户利用传统数据库或普通文件中的结构化数据进行数据挖掘。它已经成功应用于市场分析、zhapian行为监测及客户联系管理等；Intelligent Miner for Text允许企业从文本信息进行数据挖掘，文本数据源可以是文本文件、Web页面、电子邮件、Lotus Notes数据库等等。

(2) Enterprise Miner

这是一种在我国的企业中得到采用的数据挖掘工具，比较典型的包括上海宝钢配矿系统应用和铁路部门在春运客运研究中的应用。SAS Enterprise Miner是一种通用的数据挖掘工具，按照"抽样--探索--转换--建模--评估"的方法进行数据挖掘。可以与SAS数据仓库和OLAP集成，实现从提出数据、抓住数据到得到解答的"端到端"知识发现。

(3) SPSS Clementine

SPSS Clementine是一个开放式数据挖掘工具，曾两次获得英国政府SMART 创新奖，它不但支持整个数据挖掘流程，从数据获取、转化、建模、评估到最终部署的全部过程，还支持数据挖掘的行业标准--CRISP-DM。Clementine的可视化数据挖掘使得"思路"分析成为可能，即将集中精力在要解决的问题本身，而不是局限于完成一些技术性工作（比如编写代码）。提供了多种图形化技术，有助理解数据间的关键性联系，指导用户以最便捷的途径找到问题的最终解决办法。

其它常用的数据挖掘工具还有LEVEL5 Quest 、MineSet (SGI) 、Partek 、SE-Learn 、SPSS 的数据挖掘软件Snob、Ashraf Azmy 的SuperQuery 、WINROSA 、XmdvTool 等[26]。
2.7 数据挖掘未来研究方向及热点

当前，DM/KDD研究方兴未艾，其研究与开发的总体水平相当于数据库技术在70年代所处的地位，迫切需要类似于关系模式、DBMS系统和SQL查询语言等理论和方法的指导，才能使DM/KDD的应用得以普遍推广。预计在本世纪，DM/KDD的研究还会形成更大的高潮，研究焦点可能会集中到以下几个方面：

发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也许会像SQL语言一样走向形式化和标准化；

寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，也便于在知识发现的过程中进行人机交互；

研究在网络环境下的数据挖掘技术（WebMining），特别是在因特网上建立DM/KDD服务器，并且与数据库服务器配合，实现WebMining；

加强对各种非结构化数据的开采（DataMiningforAudio＆Video），如对文本数据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的开采；

处理的数据将会涉及到更多的数据类型，这些数据类型或者比较复杂，或者是结构比较独特。为了处理这些复杂的数据，就需要一些新的和更好的分析和建立模型的方法，同时还会涉及到为处理这些复杂或独特数据所做的费时和复杂数据准备的一些工具和软件。

交互式发现；

知识的维护更新。

但是，不管怎样，需求牵引与市场推动是永恒的，DM/KDD将首先满足信息时代用户的急需，大量的基于DM/KDD的决策支持软件产品将会问世。

就目前来看，将来的几个热点包括网站的数据挖掘（Web site data mining）、生物信息或基因（Bioinformatics/genomics）的数据挖掘及其文本的数据挖掘（Textual mining）。下面就这几个方面加以简单介绍。
2.4.1 网站的数据挖掘

需求随着Web技术的发展，各类电子商务网站风起云涌，建立起一个电子商务网站并不困难，困难的是如何让您的电子商务网站有效益。要想有效益就必须吸引客户，增加能带来效益的客户忠诚度。电子商务业务的竞争比传统的业务竞争更加激烈，原因有很多方面，其中一个因素是客户从一个电子商务网站转换到竞争对手那边，只需点击几下鼠标即可。网站的内容和层次、用词、标题、奖励方案、服务等任何一个地方都有可能成为吸引客户、同时也可能成为失去客户的因素。而同时电子商务网站每天都可能有上百万次的在线交易，生成大量的记录文件（Logfiles）和登记表，如何对这些数据进行分析和挖掘，充分了解客户的喜好、购买模式，甚至是客户一时的冲动，设计出满足于不同客户群体需要的个性化网站，进而增加其竞争力，几乎变得势在必行。若想在竞争中生存进而获胜，就要比您的竞争对手更了解客户。

电子商务网站数据挖掘，在对网站进行数据挖掘时，所需要的数据主要来自于两个方面：一方面是客户的背景信息，此部分信息主要来自于客户的登记表；而另外一部分数据主要来自浏览者的点击流（Click-stream），此部分数据主要用于考察客户的行为表现。但有的时候，客户对自己的背景信息十分珍重，不肯把这部分信息填写在登记表上，这就会给数据分析和挖掘带来不便。在这种情况之下，就不得不从浏览者的表现数据中来推测客户的背景信息，进而再加以利用。

就分析和建立模型的技术和算法而言，网站的数据挖掘和原来的数据挖掘差别并不是特别大，很多方法和分析思想都可以运用。所不同的是网站的数据格式有很大一部分来自于点击流，和传统的数据库格式有区别。因而对电子商务网站进行数据挖掘所做的主要工作是数据准备。目前，有很多厂商正在致力于开发专门用于网站挖掘的软件。
2.4.2 生物信息或基因数据挖掘

　　生物信息或基因数据挖掘则完全属于另外一个领域，在商业上很难讲有多大的价值，但对于人类却受益非浅。例如，基因的组合千变万化，得某种病的人的基因和正常人的基因到底差别多大？能否找出其中不同的地方，进而对其不同之处加以改变，使之成为正常基因？这都需要数据挖掘技术的支持。

对于生物信息或基因的数据挖掘和通常的数据挖掘相比，无论在数据的复杂程度、数据量还有分析和建立模型的算法而言，都要复杂得多。从分析算法上讲，更需要一些新的和好的算法。现在很多厂商正在致力于这方面的研究。但就技术和软件而言，还远没有达到成熟的地步。

（1）       
2.4.3 文本的数据挖掘

人们很关心的另外一个话题是文本数据挖掘。举个例子，在客户服务中心，把同客户的谈话转化为文本数据，再对这些数据进行挖掘，进而了解客户对服务的满意程度和客户的需求以及客户之间的相互关系等信息。从这个例子可以看出，无论是在数据结构还是在分析处理方法方面，文本数据挖掘和前面谈到的数据挖掘相差很大。文本数据挖掘并不是一件容易的事情，尤其是在分析方法方面，还有很多需要研究的专题。目前市场上有一些类似的软件，但大部分方法只是把文本移来移去，或简单地计算一下某些词汇的出现频率，并没有真正的分析功能。

随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、越来越复杂，数据挖掘将发挥出越来越大的作用。[9]
2.4.4 2005年十大热点问题

在2005ICDM的大会上，给出了一下10个挑战性的问题：

    （1）  发展统一的数据挖掘理论

（2）       多维的数据挖掘和高速流的数据挖掘

（3）       时序系列的数据挖掘

（4）       从复杂数据中的复杂知识的挖掘

（5）       网络的数据挖掘

（6）       分布式数据挖掘和多代理的数据挖掘

（7）       生物和环境问题的数据挖掘

（8）       相关问题的数据挖掘过程

（9）       安全，隐私和数据一致性

（10）   动态、不均衡和权值数据的数据挖[12]
2.5 小结

    本章主要介绍数据挖掘的相关知识。看看是否发现有什么可以研究的，并了解其过程以及未来研究的方向热点等问题。通过对数据挖掘的了解，可以在以后的挖掘过程中相互采用比较好的算法，实现综合应用。或对自己的思想有所启发。创造更好的挖掘算法。
第三章  关联规则
3.1 概论

数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。

关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。

Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题[20]，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。

最近也有独立于Agrawal的频集方法的工作，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。也有一些工作注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。


3.2 基本概念

在1993年，R.Agrawal等人首次提出了关联规则的概念。其一般定义如下：J={ I1, I2, …, Im }是一项目集，D是一事务数据库，其中每个事务T J。每个事务都有一个标识符，称之为TID。若A一是项目集，当且仅当A T时，我们说事务T包含了A。一条关联规则就是形如A B的蕴含关系，其中A J，B J且A B= 。如果D中包含A B的比例是s，就称关联规则A B在D中的支持度为s，也可以表示为概率P（A B）；如果D中包含A的同时也包含B的比例是c ，则说关联规则A B的置信度为c，表示为条件概率P（B|A）。就是：

Support（A B）= P（A B）

Confidence（A B）= P（B|A）

支持度（support）和置信度（confidence）两个阈值是描述关联规则的两个重要概念，支持度反映关联规则在数据库中的重要性，置信度衡量关联规则的可信程度。如果某条规则同时满足最小支持度（min-support）和最小置信度（min-confidence），则称它为强关联规则。
3.3 关联规则种类

我们将关联规则按不同的情况进行分类：

(1) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。例如：性别=“女”=>职业=“秘书” ，是布尔型关联规则；性别=“女”=>avg（收入）=2300，涉及的收入是数值类型，所以是一个数值型关联规则。

(2) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如：IBM台式机=>Sony打印机，是一个细节数据上的单层关联规则；台式机=>Sony打印机，是一个较高层次和细节层次之间的多层关联规则。

(3) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒=>尿布，这条规则只涉及到用户的购买的物品；性别=“女”=>职业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。

4 关联规则挖掘的算法
(1) 经典频集方法
    Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化的关联规则、周期关联规则等，对关联规则的应用进行推广。

(2) 核心算法

Agrawal等在1993年设计了一个基本算法，提出了挖掘关联规则的一个重要方法 — 这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计可以分解为两个子问题：

(1)找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频集（Frequent Itemset）。

(2)使用第1步找到的频集产生期望的规则。这里的第2步相对简单一点。如给定了一个频集Y=I1I2...Ik，k³2，Ij∈I，产生只包含集合{I1，I2，...，Ik}中的项的所有规则(最多k条)，其中每一条规则的右部只有一项，(即形如[Y-Ii]ÞIi，"1£i£k)，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。其核心思想如下：

(1)     L1 = {large 1-itemsets};

(2)     for (k=2; Lk-1¹F; k++) do begin

(3)       Ck=Apriori-gen(Lk-1);   //新的候选集

(4)       for all transactions tÎD do begin

(5)           Ct=subset(Ck,t);    //事务t中包含的候选集

(6)           for all candidates cÎ Ct  do

(7)           c.count++;

(8)       end

(9)        Lk={cÎ Ck |c.count³minsup}

(10)    end

(11)    Answer=ÈkLk;

首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。

在论文中，Agrawal等引入了修剪技术（Pruning）来减小候选集Ck的大小，由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。文[6]中，还引入杂凑树（Hash Tree）方法来有效地计算每个项集的支持度。
3.4 主要研究方向和典型算法分析

R.Agrawal等人提出了关联规则的采掘问题以后，该问题的研究得到了长足地发展。到目前为止，其主要的研究方向有：
3.4.1 多循环方式的采掘算法

此类算法包括Agrawal等人提出的AIS[28]，Apriori、AprioriTid和AprioriHybrid[29]、Park 等人提出的DHP[30]，Savasere等人的PARTITION[31]以及Toivonen提出的抽样算法Sampling[32]等等。其中最有效和有影响的算法为：Apriori，DHP和PARTITION。

在算法AIS中，候选大项集是在扫描数据库的过程中产生的。具体地说，在对数据库进行第k 次扫描时，候选大项集(其中每一个元素的元素个数不一定是k个，可以大于k)是由第k-1次扫描所产生的边界集(Frontierset)通过增加当前事务中的项得到，同时计算候选大项集中的元素的支持数，直到某一次扫描所产生的边界集为空时停止运算。应该注意的是，第k次扫描所产生的边界集要大于本次扫描生成的大项集。本算法的缺点在于生成的候选大项集太大。

算法Apriori和AprioriTid利用“在给定的事务数据库D中，任意大项集的子集都是大项集； 任意弱项集的超集都是弱项集”这一原理对事务数据库进行多遍扫描，第一次扫描得出大1项集L1，第k(k>1)次扫描前先利用第k-1次扫描的结果(即大k-1项集Lk-1)和函数Apriori_gen[29]产生候选大k项集Ck，然后在扫描过程中确定Ck中每一元素的支持数，最后在每一遍扫 描结束时计算出大k项集Lk，算法在当候选大k项集Ck为空时结束。由于充分利用的上述原理 ，这两个算法所产生的候选大项集要比算法AIS小得多，从而提高了算法的效率。算法AprioriTid还有另外一个特点，即仅在第一次扫描时用事务数据库D计算候选大项集的支持数，其 它各次扫描用其上一次扫描生成的候选事务数据库D'来计算候选大项集的支持数。在最后的 几次扫描中，D'的大小要远远小于D，减小了I/O操作时间，提高了算法的效率。算法Aprio riHybrid是算法Apriori与算法AprioriTid的结合，当候选事务数据库D'不能完全容纳于内 存时用算法Apriori，当内存能够完全容纳候选事务数据库D'时，则用算法AprioriTid。

算法DHP利用哈希(Hashing)技术有效地改进了候选大项集的生成过程，产生了比前述算法更小的候选大项集(对大2候选集尤为明显)，同时也缩减了事务数据库的大小，减小了I/O操作时间，其效率比算法Apriori有明显提高。

算法PARTION分为两个部分。在第一部分中，算法首先将要在其中发现关联规则的事务数据 库D分为n个互不相交的事务数据库D1，D2，...，Dn，Di(i=1,2,...,n)的大小要求 能够容纳在内存之中，然后将每一个分事务数据库Di(i=1,2,...,n)读入内存并发现其 中的大项集Li，最后在第一部分结束时将所有分事务数据库的大项集合并成为一个在事务数 据库D中的潜在大项集 算法第二部分计算潜在大项集PL在事务数据库D中的支持数，并得出大项集L。该算法只对事务数据库D扫描两次，大大减少了I/O操作，从而提高了算法的效率。

算法Sampling设计思想为：对事务数据库D进行随机抽样得到抽样事务数据库D'，先以小于 用户给定的最小支持度的支持度发现存在于D'中大项集L'，再在剩下的数据库D-D'中继续计 算L'中各元素的支持数，最后以用户给定的最小支持度计算出大项集L。在大部分情况下，可以用此方法发现正确的大项集，但有时可能会漏掉一些大项集，这时可以对D进行第二次 扫描以得出漏掉的大项集。此算法在大部分情况下可以只对D进行一次扫描就得出大项集， 最坏的情况对D进行两次扫描，因而算法效率较高。
3.4.2 增量式更新算法

关联规则的增量式更新问题主要有两个：①在给定的最小支持度和最小置信度下，当一个新 的事物数据集db添加到旧的事物数据库DB中时，如何生成db(DB中的关联规则；②给定事物 数据库DB，在最小支持度和最小可信度发生变化时，如何生成数据库DB中的关联规则。文[33]考虑了关联规则更新的第一类问题，给出了一个基本框架与算法Apriori相一致的算法FUP。文[34]针对关联规则更新的第二类问题进行了研究，设计出了相应的算法IUA和PIUA。

算法FUP的基本思想为：对任意一个k(k 1)项集，若其在DB和db中都是大项集，则其一定是 大项集；若其在DB和db中都是弱项集，则其一定是弱项集；若其仅在DB(db)中是大项集，则 其支持数应加上其在db(DB)中的支持数以确定它是否为大项集。算法FUP假设在DB中发现的 大项集 (n为L中最大元素的元素个数)已被保存下来。它需要对DB和db进行多次扫描，在第 1次扫描中，算法先扫描db，将L1中的元素仍为db(DB中的大项集的元素记入L'1，并生成候 选大1项集C1，C1中的元素为db中的大1项集且不包含在L1中；然后扫描DB以决定C1中的元素 是否为db(DB中的大项集，并将是db(DB中的大项集的元素记入L'1中。在第k(k>1)次扫描前 ，先对L'k-1用Apriori_Gen()函数生成候选大k项集Ck，并除去Lk中的元素，即Ck=Ck-Lk， 对Lk进行剪枝，即对于X∈Lk，若存在Y∈Lk-1-L'k-1，则X肯定不会是db∪DB中的大k项集，应将其在Lk中删除；然后扫描db，将Lk中的元素仍为db∪DB中的大项集的元素记入L'k，记录候选大k项集Ck中的元素在db中的支持数；最后扫描DB，记录Ck中的元素在DB中的支持数，扫描结束时，将Ck中是db∪DB中大项集 的元素记入L'k中。算法在Lk和Ck均为空时结束。由于利用了对DB进行采掘的结果，本算法的效率比再一次利用算法Apriori或DHP对db∪DB进行采掘的效率要高得多。
　　算法IUA采用了一个独特的候选大项集生成算法iua_gen，在每一次对数据库DB扫描之前生成 较小的候选大项集，从而提高了算法的效率。它也要求上一次对数据库DB进行采掘时发现的 大项集 (n为L中最大元素的元素个数)在本次采掘时是可得到的。因为人们在发现关联规则时，常常需要不断地调整最小支持度和最小可信度来聚集到那些真正令其感兴趣关联规则上 ，因而本算法具有很重要的意义。
3.4.3 并行发现算法

目前已经提出的并行采掘关联规则的算法有：Agrawal等人提出的CD(Count Distribution) 、CaD(Candidate Distribution)、DD(Data Distribution)[35]，Park等人提出的PDM[36]。Chueng等人提出的算法DMA[37]和FDM[38]虽然是基于分布式数据库的采掘算法，但也可 适用于并行采掘。

算法CD具有速度较快、容易实现、要求各计算机间同步次数较少等优点，但它有通信量大和 候选大项集大等缺点。算法CaD、DD及PDM的执行效果都不如CD[37]。算法DMA虽克服了算法C D的一些弱点，但它要求各计算机间同步次数较多。算法FDM与算法DMA基本一致，区别在于F DM中增加了全局剪枝技术。

这些算法都是基于无共享体系结构，即并行计算的n台计算机之间除了用网络连接起来以外 ，其它都是完全独立的。每台计算机Pi(i=1,2,...,n)上都有自己的分事务数据库DBi，总的事务数据库 。

算法CD是算法Apriori在并行环境下的应用，它要求计算机Pi(i=1,2,...,n)对DBi进行多遍扫描。在第k次扫描，当k>1时，计算机Pi(i=1,2,...,n)首先利用第k-1次扫描所得 的大项集Lk-1和Apriori_Gen()函数生成候选大项集Ck，当k=1时，计算机Pi先扫描DBi得出 其中的大1项集，再与其它计算机得到的大1项集进行交换并进行合并，从而生成候选大1项 集C1；然后扫描DBi计算Ck中的元素在DBi中的支持数，计算机Pi广播Ck中元素的支持数，并 接收从其它计算机 传来的Ck中元素的支持数，并对这些支持数进行累加，得出Ck中 元素的全局支持数；最后计算出大k项集Lk，若Lk中元素个数为1，则算法结束。

算法DMA是基于“若项集X在DB中是大项集，则其必在某一个DBi也是大项集”的原理进行设计。算法中采用局部剪枝技术(Local pruning)，使其生成的候选大项集比算法CD要小。算法各个站点进行支持数交换时采用轮询站点技术(polling site)，使每一个项集X的通讯代 价由算法CD的o(n2)降为o(n)，其中n为站点个数。它可分为如下几步：①生成候选大k项集CHiK。根据计算机Pi(i=1，2，...，n)在k-1次循环所生成的稠密集HLiK-1，生成循环k所需用的候选大k项集CHiK，即 ②支持数计算。扫描DBi计算候选大k项集中的每个元素X的局部支持数X.supi。③交换支持数。采用轮询站点技术与其它计算机交换候选大k项集中的 元素的支持数，并计算它的全局支持数。④生成大项集Lk和稠密集。中的元素具有下列性质：它在DBi和DB中都是大项集。

(4)采掘一般或多层关联规则

在研究采掘关联规则的过程中，许多学者发现在一些实际应用中，由于数据比较少，要想在 原始的概念层次上发现强的(Strong)和有趣的(Interesting)关联规则是比较困难的，因为 好多项集往往没有足够的支持数。由于概念层次在要采掘的数据库中经常是存在的，比如在 一个连锁店会存在这样概念层次：光明牌牛奶是牛奶，牛奶是食品等，我们称高层次的项是 低层次项的父亲，这种概念层次关系通常用一个有向非循环图(DAG)来表示。于是我们就可 以在较高的概念层次上发现关联规则。基于要采掘的数据库中的概念层次和发现单一概念层 次中的关联规则的算法，学者们提出了许多高效发现一般或多层关联规则的算法，主要有： Han等人的ML_T2L1及其变种ML_T1LA、ML_TML1、ML_T2LA[39]和R.Srikant等人的Cumulate、 Stratify及其变种Estimate、EstMerge[40]等。

算法ML_T2L1的基本思想是首先根据要发现的任务从原事务数据库生成一个根据概念层次信 息进行编码的事务数据库，利用这个具有概念层次信息的新生成的数据库，自顶向下逐层递 进地在不同层次发现相应的关联规则。它实际上是算法Apriori在多概念层次环境中的扩展 。根据对在发现高层关联规则过程中所用的数据结构和所生成的中间结果共享方式的不同， 算法ML_T2L1有三个变种：ML_T1LA、ML_TML1、ML_T2LA。

算法Cumulate的基本思想与Apriori完全一样，只是在扫描到事务数据库某一事务时，将此 事务中所有项的祖先加入到本事务中，并加入三个优化：①对加入到事务中的祖先进行过滤 。②预先计算概念关系T中的每一个项的祖先，得到项集与其祖先的对照表T*。③对既包含 项集X又包含X的祖先的项集进行剪枝。

算法Stratify基于“若项集X的父亲不是大项集，则X肯定不会是大项集”的事实进行设计。其基本思想为：在概念层次有向非循环图中，定义没有父亲的项集X的深度depth(X)=0，其 它项集的深度为： 算法要对事务数据库进行多遍扫描，第k k(0)次扫描计算深度为k k(0)的所有项集Ck的支持数，并得出深度为k k(0)的大项集Lk，在第k k(1)次扫描之前，对Ck进行剪枝，即删除Ck中那些祖先包含在Ck-1-Lk-1中的元素。围绕着怎样及早决定某些深度较大的项集是否是大项集问题，文献[40]用抽样技术对算 法Stratify进行扩展，形成算法Estimate和EstMerge。

(5)采掘多值属性关联规则

关联规则可分为布尔型关联规则和多值属性关联规则。多值属性又可分为数量属性和类别属 性。多值属性关联规则采掘问题首先在文献[41]中提出。目前提出的采掘多值属性关联规则的算法大多是将多值属性关联规则采掘问题转化为布尔型关联规则采掘问题，即将多值属性 的值划分为多个区间，每个区间算作一个属性，将类别属性的每一个类别当作一个属性。

文[41]中发现的多值属性关联规则的形式为：x=qx y=qy，其前件和后件对应的都是单一的 数值，而不是一个区间，文中提出的算法比较简单，但当我们需要发现所有属性之间的关联 规则时，我们将遇到属性组合的爆炸问题。

文[42]用“偏完整性度量（partial completenessmeasure）”原则将数量属性划分为相等的几个区段，当某一区段的支持数小于用户给定的最小支持数时，我们就将其与其邻近的区段 进行合并。为了使发现的关联规则更具有趣性，文中采用了“大于期望的值（greater-than- expected-value）”准则。

文[43]认为文[42]中的属性划分方法不能很好地表示数据的分布，尤其是属性值分布不均匀 的时候，于是提出了一个聚类算法，根据数据库中数据的分布情况决定属性值如何划分区段 ，并可将相关的区段进行合并。在此基础上发现的多值关联规则更具有效性和可理解性。

(6)基于约束的关联规则采掘

基于约束的关联规则采掘的主要目的是发现更有趣的、更实用的和更特别的关联规则，这方 面的研究主要有[44～51]。

文[44]研究了在提供布尔表达式约束情况下的关联规则发现问题。这种布尔表达式约束允许 用户指定他所感兴趣的关联规则的集合，这种约束不仅可以用来对事务数据库进行预加工， 而且可以把它集成在采掘算法内部，从而提高算法的执行效率，文中根据这种集成方式的不 同给出了三种不同的算法：MultipleJoins、Reorder、Direct。

文[45]提出并分析了用户所给出的约束的两个对发现算法的剪枝步骤非常重要的属性：反单 调性(anti-monotonicity)和简洁性(succinctness)，提出了一个高效的基于约束的关联规 则采掘算法CAP。

另一种类型的基于约束的关联规则采掘方法是元模式制导的关联规则采掘算法[49～51]。这 种类型的发现算法首先由用户给定要发现的关联规则的元模式或模板，然后根据这些模板在 数据库中发现与模板相适应的实际存在的关联规则。例如文[50]就是基于这种模式提出了两 个相应的算法：大谓词增长算法(largepredicate-growing)和直接p-谓词测试算法(Direct p-predicatetesting)。

(7)其它方向
　　除了以上列举的比较常见的研究方向外，还有其它一些研究方向，如：发现关联规则的语言 [52,53]、采掘长模式和密集数据集[48,54]、采掘相关性和因果关系[55,56]、发现比例 规则[57]、发现周期(cyclic)和日历(calendric)关联规则[58,59]、采掘多维关联规则[59] 等等[60]。
3.5 频集算法的几种优化方法

虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，还是存在不令人满意的地方，于是人们相继提出了一些优化的方法。
3.4.1 基于划分的方法

Savasere等[14]设计了一个基于划分(partition)的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频集。更多的关于生成频集的并行化方法可以在中找到。
3.4.2 基于Hash的方法

一个高效地产生频集的基于杂凑(hash)的算法由Park等提出来。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改