数据挖掘技术的算法与应用读书报告
第一章 数据仓库
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数据仓库体系结构
企业数据仓库的建设，是以现有企业业务系统和大量业务数据的积累为基础。数据仓库不是静态的概念，只有把信息及时交给需要这些信息的使用者，供他们做出改善其业务经营的决策，信息才能发挥作用，信息才有意义。而把信息加以整理归纳和重组，并及时提供给相应的管理决策人员，是数据仓库的根本任务。因此，从产业界的角度看，数据仓库建设是一个工程，是一个过程。整个数据仓库系统是一个包含四个层次的体系结构，具体由下图表示:
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]
数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先未知,有效和可实用三个特征。
基于并行系统的数据库管理系统也给数据挖掘技术的应用带来了便利。如果你有一个庞大而复杂的数据挖掘问题要求通过访问数据库取得数据，那么效率最高的办法就是利用一个本地的并行数据库。
2.2 数据挖掘研究的内容和本质
随着DM/KDD研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三根强大的技术支柱：数据库、人工智能和数理统计。因此，KDD大会程序委员会曾经由这三个学科的权威人物同时来任主席。目前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 数据挖掘未来研究方向及热点
当前，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 生物信息或基因数据挖掘
生物信息或基因数据挖掘则完全属于另外一个领域，在商业上很难讲有多大的价值，但对于人类却受益非浅。例如，基因的组合千变万化，得某种病的人的基因和正常人的基因到底差别多大？能否找出其中不同的地方，进而对其不同之处加以改变，使之成为正常基因？这都需要数据挖掘技术的支持。
对于生物信息或基因的数据挖掘和通常的数据挖掘相比，无论在数据的复杂程度、数据量还有分析和建立模型的算法而言，都要复杂得多。从分析算法上讲，更需要一些新的和好的算法。现在很多厂商正在致力于这方面的研究。但就技术和软件而言，还远没有达到成熟的地步。
2.4.3 文本的数据挖掘
人们很关心的另外一个话题是文本数据挖掘。举个例子，在客户服务中心，把同客户的谈话转化为文本数据，再对这些数据进行挖掘，进而了解客户对服务的满意程度和客户的需求以及客户之间的相互关系等信息。从这个例子可以看出，无论是在数据结构还是在分析处理方法方面，文本数据挖掘和前面谈到的数据挖掘相差很大。文本数据挖掘并不是一件容易的事情，尤其是在分析方法方面，还有很多需要研究的专题。目前市场上有一些类似的软件，但大部分方法只是把文本移来移去，或简单地计算一下某些词汇的出现频率，并没有真正的分析功能。
随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、越来越复杂，数据挖掘将发挥出越来越大的作用。[9]
2.5 小结
本章主要介绍数据挖掘的相关知识。看看是否发现有什么可以研究的，并了解其过程以及未来研究的方向热点等问题。
第三章 关联规则3.1 概论
数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。
关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。
Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。
最近也有独立于Agrawal的频集方法的工作，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。也有一些工作注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。
现在面临一个尴尬的境地——数据丰富信息匮乏（data rich but information poor）！快速增长的海量数据，已经远远的超过了人们的理解能力，如果不借助强有力的工具，很难弄清大堆数据中所蕴含的知识。结果，重要决策只是基于制定决策者的个人经验，而不是基于信息丰富的数据。数据挖掘就这样应运而生，数据挖掘填补了数据和信息之间的鸿沟。[11]
3.2 基本概念
在1993年，R.Agrawal等人首次提出了关联规则的概念。
支持度（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，k32，Ij∈I，产生只包含集合{I1，I2，...，Ik}中的项的所有规则(最多k条)，其中每一条规则的右部只有一项，(即形如[Y-Ii]TIi，"1￡i￡k)，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。其核心思想如下：
(1) L1 = {large 1-itemsets};(2) for (k=2; Lk-11F; 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.count3minsup}
(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 频集算法的几种优化方法
虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，还是存在不令人满意的地方，于是人们相继提出了一些优化的方法。
3.4.1 基于划分的方法
Savasere等[14]设计了一个基于划分(partition)的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频集。更多的关于生成频集的并行化方法可以在中找到。
3.4.2 基于Hash的方法
一个高效地产生频集的基于杂凑(hash)的算法由Park等提出来。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。
3.4.3 基于采样的方法
基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点，他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。Lin和Dunham在中讨论了反扭曲(Anti-skew)算法来挖掘关联规则，在那里他们引入的技术使得扫描数据库的次数少于2次，算法使用了一个采样处理来收集有关数据的次数来减少扫描遍数。Brin等提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是，在计算k-项集时，一旦我们认为某个(k+1)-项集可能是频集时，就并行地计算这个(k+1)-项集的支持度，算法需要的总的扫描次数通常少于最大的频集的项数。这里他们也使用了杂凑技术，并提出产生“相关规则”（Correlation Rules）的一个新方法，这是基于他们的工作基础上的。
3.4.4 减少交易的个数
减少用于未来扫描的事务集的大小。一个基本的原理就是当一个事务不包含长度为k的大项集，则必然不包含长度为k+1的大项集。从而我们就可以将这些事务移去，这样在下一遍的扫描中就可以要进行扫描的事务集的个数。这个就是AprioriTid的基本思想。
3.4.5 其他的频集挖掘方法
上面我们介绍的都是基于Apriori的频集方法。即使进行了优化，但是Apriori方法一些固有的缺陷还是无法克服：
(1)可能产生大量的候选集。当长度为1的频集有10000个的时候，长度为2的候选集个数将会超过10M。还有就是如果要生成一个很长的规则的时候，要产生的中间元素也是巨大量的。
(2)无法对稀有信息进行分析。由于频集使用了参数minsup，所以就无法对小于minsup的事件进行分析；而如果将minsup设成一个很低的值，那么算法的效率就成了一个很难处理的问题。
下面将介绍两种方法，分别用于解决以上两个问题。
在[18]中提到了解决问题1的一种方法。采用了一种FP-growth的方法。他们采用了分而治之的策略：在经过了第一次的扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息。随后我们再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。
第二个问题是基于这个的一个想法：Apriori算法得出的关系都是频繁出现的，但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不是频繁出现的。在Apriori算法中，起决定作用的是支持度，而我们现在将把可信度放在第一位，挖掘一些具有非常高可信度的规则。在[19]中介绍了对于这个问题的一个解决方法。整个算法基本上分成三个步骤：计算特征、生成候选集、过滤候选集。在三个步骤中，关键的地方就是在计算特征时Hash方法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。基本的方法有两类：Min_Hashing(MH)和Locality_Sensitive_Hashing(LSH)。Min_Hashing的基本想法是：将一条记录中的头k个为1的字段的位置作为一个Hash函数。Locality_Sentitive_Hashing的基本想法是：将整个数据库用一种基于概率的方法进行分类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。我们再对这两个方法比较一下。MH的遗漏率为零，错误率可以由k严格控制，但是时空效率相对的较差。LSH的遗漏率和错误率是无法同时降低的，但是它的时空效率却相对的好很多。所以应该视具体的情况而定。最后的实验数据也说明这种方法的确能产生一些有用的规则。
3.5 多层和多维关联规则的挖掘
随着数据仓库和OLAP技术研究的深入，可以预见大量的数据将经过整合、预处理，从而存入数据仓库之中。在当前，大多数的数据仓库的应用都是进行统计、建立多维以及OLAP的分析工作。随着数据挖掘研究的深入，已经有了OLAP和数据挖掘相结合的方法[20,21]。
首先一个有效的数据挖掘方法应该可以进行探索性的数据分析。用户往往希望能在数据库中穿行，选择各种相关的数据，在不同的细节层次上进行分析，以各种不同的形式呈现知识。基于OLAP的挖掘就可以提供在不同数据集、不同的细节上的挖掘，可以进行切片、切块、展开、过滤等各种对规则的操作。然后再加上一些可视化的工具，就能大大的提高数据挖掘的灵活性和能力。接着，我们来看一下多层和多维关联规则的定义。
多层关联规则：对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。
多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层间关联规则。
多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过，在支持度设置的问题上有一些要考虑的东西。
同层关联规则可以采用两种支持度策略：
(1)统一的最小支持度。对于不同的层次，都使用同一个最小支持度。这样对于用户和算法实现来说都比较的容易，但是弊端也是显然的。
(2)递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度相对较小。同时还可以利用上层挖掘得到的信息进行一些过滤的工作。层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来定。
以上我们研究的基本上都是同一个字段的值之间的关系，比如用户购买的物品。用多维数据库的语言就是单维或者叫维内的关联规则，这些规则一般都是在交易数据库中挖掘的。但是对于多维数据库而言，还有一类多维的关联规则。例如：年龄（X，“20...30”）ù职业（X,“学生”）==> 购买(X，“笔记本电脑”)在这里我们就涉及到三个维上的数据：年龄、职业、购买。根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。年龄（X，“20...30”）ù购买(X，“笔记本电脑”) ==> 购买(X，“打印机”)这个规则就是混合维关联规则。
在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类：种类型和数值型。对于种类型的字段，原先的算法都可以处理。而对于数值型的字段，需要进行一定的处理之后才可以进行。处理数值型字段的方法基本上有以下几种：
(1)数值字段被分成一些预定义的层次结构。这些区间都是由用户预先定义的。得出的规则也叫做静态数量关联规则。
(2)数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间，落在其中则为1，反之为0。这种分法是动态的。得出的规则叫布尔数量关联规则。
(3)数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素。得出的规则叫基于距离的关联规则。
(4)直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出一些有用的规则。得出的规则叫多层数量关联规则。
在OLAP中挖掘多层、多维的关联规则是一个很自然的过程。因为OLAP本身的基础就是一个多层多维分析的工具，只是在没有使用数据挖掘技术之前，OLAP只能做一些简单的统计，而不能发现其中一些深层次的有关系的规则。当我们将OLAP和DataMining技术结合在一起就形成了一个新的体系OLAM（On-Line Analytical Mining）[20]。
3.6 关联规则价值衡量的方法
当我们用数据挖掘的算法得出了一些结果之后，数据挖掘系统如何知道哪些规则对于用户来说是有用的、有价值的？这里有两个层面：用户主观的层面和系统客观的层面。
3.6.1 系统客观层面
很多的算法都使用“支持度-可信度”的框架。这样的结构有时会产生一些错误的结果。看如下的一个例子：假设一个提供早餐的零售商调查了4000名学生在早晨进行什么运动，得到的结果是2200名学生打篮球，2750名学生晨跑，1800名学生打篮球、晨跑。那么如果设minsup为40%，minconf为60%，我们可以得到如下的关联规则：打篮球T晨跑（1）这条规则其实是错误的，因为晨跑的学生的比例是68%，甚至大于60%。然而打篮球和晨跑可能是否定关联的，即当我们考虑如下的关联时：打篮球T（不）晨跑 （2）虽然这条规则的支持度和可信度都比那条蕴涵正向关联的规则（1）低，但是它更精确。 然而，如果我们把支持度和可信度设得足够低，那么我们将得到两条矛盾的规则。但另一方面，如果我们把那些参数设得足够高，我们只能得到不精确的规则。总之，没有一对支持度和可信度的组合可以产生完全正确的关联。
于是人们引入了兴趣度，用来修剪无趣的规则，即避免生成“错觉”的关联规则。一般一条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强度之比，然而在许多应用中已发现，只要人们仍把支持度作为最初的项集产生的主要决定因素，那么要么把支持度设得足够低以使得不丢失任何有意义的规则，或者冒丢失一些重要规则的风险；对前一种情形计算效率是个问题，而后一种情形则有可能丢失从用户观点来看是有意义的规则的问题。
在[12]中作者给出了感兴趣的规则的定义（R-interesting），在[13]中他们又对此作了改进。在[10]中把事件依赖性的统计定义扩展到兴趣度的定义上来；[15]定义了否定关联规则的兴趣度。
除了把兴趣度作为修剪无价值规则的工具，现在已有许多其他的工作来重新认识项集，如Brin等[3]考虑的相关规则。在[4]中讨论了蕴涵规则(implication rule)，规则的蕴涵强度在[0,￥]之间变化，其中蕴涵强度为1表示完全无关的规则，￥表示完备的规则，如果蕴涵强度大于1则表示更大的期望存在性。
另一个度量值——“收集强度”(collective strength)在[22]中被定义，他们设想使用“大于期望值”来发现有意义的关联规则。项集的“收集强度”是[0,￥]之间的一个数值，其中0表示完备的否定相关性，而值￥表示完备的正相关性。详细的讨论可以在[10]中找到。
3.6.2 用户主观层面
上面的讨论只是基于系统方面的考虑，但是一个规则的有用与否最终取决于用户的感觉。只有用户可以决定规则的有效性、可行性。所以我们应该将用户的需求和系统更加紧密的结合起来。
可以采用一种基于约束(consraint-based)[21]的挖掘。具体约束的内容可以有：
(1)数据约束。用户可以指定对哪些数据进行挖掘，而不一定是全部的数据。
(2)指定挖掘的维和层次。用户可以指定对数据哪些维以及这些维上的哪些层次进行挖掘。
(3)规则约束。可以指定哪些类型的规则是我们所需要的。引入一个模板（template）的概念，用户使用它来确定哪些规则是令人感兴趣的而哪些则不然：如果一条规则匹配一个包含的模板（inclusive template），则是令人感兴趣的，然而如果一条规则匹配一个限制的模板（rextrictive template），则被认为是缺乏兴趣的。
其中有些条件可以和算法紧密的结合，从而即提高了效率，又使挖掘的目的更加的明确化了。其他的方法还有：Kleinberg等人的工作是希望建立一套理论来判断所得模式的价值，他们认为这个问题仅能在微观经济学框架里被解决，他们的模型提出了一个可以发展的方向。他们引入并研究了一个新的优化问题——分段(Segmentation)问题，这个框架包含了一些标准的组合分类问题。这个模型根据基本的目标函数，对“被挖掘的数据”的价值提供一个特殊的算法的视角，显示了从这方面导出的具体的优化问题的广泛的应用领域。
在[5]中Korn等就利用猜测误差(这里他们使用“均方根”来定义)来作为一些从给定的数据集所发现的规则的“好处”(goodness)的度量，他们所定义的比例规则就是如下的规则：顾客大多数分别花费 1 : 2 : 5的钱在“面包”:“牛奶”:“奶油”上通过确定未知的(等价的，被隐藏的，丢失的)值，比例规则可以用来作决策支持。如果数据点线性地相关的话，那么比例规则能达到更紧凑的描述，即关联规则更好地描述了相关性。
3.7 小结
本章主要介绍关联规则的内容及基本概念和基本算法，还有评价关联规则的方法。
参考资料：[1]陈京民编著.数据仓库原理、设计与应用.中国水利水电出版社,2004,1
[2] 数据挖掘实践 (美)Olivia Parr Rud著；朱扬勇等译
[3] 数据仓库与数据挖掘技术 夏火松主编。70-71,
[4] 数据挖掘教程 (美)Richard J。Roiger，(美)Michael W。Geatz著；翁敬农译。 4
[5]数据仓库及其在电信领域中的应用 段云峰等编著. 39,47,56
[6] SQL Server 2000数据仓库应用与开发 罗运模等编著
[7] 数据仓库技术指南 (美)Lou Agosta著；潇湘工作室译 258
上一篇： 讲道理你立刻回对方不啊