关联规则挖掘技术与数据处理平台现状

（1）主要数据挖掘技术。

数据挖掘是指从大规模的数据中发现有意义的模式并揭示出数据间的未知依赖关系的过程。数据挖掘通常通过统计、在线分析处理、情报检索、机器学习、专家系统（依靠过去的经验法则）和模式识别等诸多方法，在数据库、数据仓库或者其他信息库中的大批量的、模糊的、有噪声的、随机的数据集合中获取有效的、潜在的、有用的、可被理解的知识。数据挖掘过程由以下三个阶段组成：数据准备、数据挖掘、结果表达和解释。

数据挖掘的功能就是用来指定挖掘任务所要寻找的模式类型。一般来说，数据挖掘任务及其对应的分析方法可以分为以下几种类型。

①关联分析（association analysis）。

通常，在多个变量属性之间会存在着某种规律性，我们把这种能寻找出来的规律称为关联。数据之间的关联是大型数据集中存在的一类可被发现的、重要的知识。运用关联分析可以找出大量数据集中属性之间所隐藏的关系。

其中，关联又可分为三种类型：简单关联、时序关联以及因果关联。人们为了度量其所发现规则的相关性，采用设置支持度和置信度阈值这两种基本方式，在后来的研究中，又不断地引入了兴趣度、相关性和提升度等参数来检验所挖掘的关联规则的准确性和实用性，使其更符合实际需求。

②聚类分析（clustering）。

把复杂的数据根据其属性的相近程度归类，使每一个类别的数据间的属性相近，不同类别的则相异，称为聚类。

③分类（classification）。

分类是利用样本数据集通过分类算法进而得出精确的分类器。分类一般被用于规则描述和预测。与聚类算法不同，分类器支持事前训练（从数据中选出已经分好类的训练集，在该训练集上运用数据挖掘分类的技术，建立分类模型，对于没有分类的数据进行分类），且分类的类别预先定义且类别数量确定。聚集不依赖于预先定义好的类，无须预先训练。

④预测（predication）。

预测就是利用历史的数据集找出其中的变化规律，然后建立模型，并通过此模型来对未来采集到的数据种类、特征以及规律进行预测。预测所关心的是预测规律的精度以及不确定性，并用预测方差进行度量。预测通常通过分类得出预测模型。

⑤时序模式（time-series pattern）。

通过时间序列搜索出数据集中重复发生、概率较高的模式，称为时序模式。同预测一样，时序模式也可解释为用历史的数据来预测未来的值，但通过时序模式的方式所预测的数据变量所处的时间不相同。

（2）关联规则挖掘技术。

①基本算法。

关联规则挖掘是数据挖掘领域研究的重要内容，其目的是为了发现同样的项目集或者属性出现的相关性，即找到频繁出现的项目集（频繁集或其属性的所有子集，以及它们之间的相关性）。利用相关的概念，即支持度和置信度的度量准则来寻找其中符合条件的关系。

关联规则挖掘可以分为两个步骤：找出全局数据库中所有的频繁项集；获得所有的频繁项集后，产生相应的大于最小置信度的强关联规则。

关联规则挖掘技术发展至今，有多种基于关联规则挖掘算法的演化，最为知名和得到广泛应用的算法包括经典Apriori 算法及其演化算法——基于频繁树增长的挖掘模型（FP-Growth）。

a.Apriori 算法。Apriori 算法是R.Agrawal 和R.Srikant 在1993年提出的关联规则挖掘的原创性算法，其命名源于算法使用了频繁项集性质的先验知识，该算法的核心思想是使用了逐层迭代来产生候选项集，即用频繁k 项集去寻找候选（k+1）项集。直到所有满足条件的项集生成。每迭代一次，需要重新扫描数据库一次。

算法需要重复扫描数据库，因此，若数据库中存在长度大的频繁项集时，将增加扫描数据库的次数，同时，当数据库很大的时候，也会增加每一次扫描全部项集的时间。

b.FP-Growth 算法。FP-Growth 算法运用频繁树结构存储频繁项集，利用具有较高压缩比的树形结构存储事务，其最大特点是不需要生成大量的候选频繁项集即可直接找出所有的频繁项集，降低了算法开销。

②并行实现技术。

Apriori 算法需要多次扫描数据集，每次扫描都会涉及相当高的计算复杂度，因此，采用并行执行策略，能够大幅减少处理时间，提高算法执行效率。(www.xing528.com)

目前已经提出的并行关联规则算法主要有Agrawal 等人提出基于Apriori 的CD 算法、DD 算法、CaD 算法。

a.CD 算法。CD 算法的基本思想是将数据集划分到每个节点，每个节点统计候选集计数。该算法的优点是各处理器之间不用交换数据，只需交换计数。因此，处理器在扫描数据时各自独立。

b.DD 算法。DD 算法将候选集和数据划分到每个处理器（CD算法中只划分数据集，每个处理器拥有完整的候选集）。每个处理器通过和其他处理器交换数据集获取本地候选集的全局计数，然后通过交换本地候选集的全局计数获取全部候选集的全局计数。

c.CaD 算法。CD 算法与DD 算法在每一次计算结束时均需同步计算或频繁项集，在处理器负载不均衡的情况下，负载较轻处理器先处理完相关任务后将等待负载较重处理器的处理结果。CaD 算法的设计思想是在每一次计算结束时无须同步。

（3）云计算平台。

云计算主要是指一个系统平台或者一种类型的应用程序，能够按需进行动态部署、配置、重配以及取消服务。云计算平台由一系列可以动态升级和被虚拟化的资源组成，具备以下特征：资源配置动态化、池化和透明化；基于虚拟化技术快速部署资源或获得服务；提供可被监控与量测的服务；减少用户终端的处理负担等。

云计算可提供以下几个层面的服务：基础设施服务（IaaS），平台服务（PaaS）和软件服务（SaaS）。主流的商业云计算平台包括亚马逊的EC2 平台、谷歌的Google AppEngine 服务、IBM 的蓝云平台、EMC 的Atoms 云存储系统与私有云解决方案、Saleforce 的Force.com 服务、微软的Azure 平台等。监狱作为一个对信息安全要求较高的场所，采用国外商业云计算平台会给信息安全带来极大的隐患。

近年来，随着云计算技术和应用的逐步发展，先后出现了多个开源云计算平台，主要包括：Eucalyptus 开源云计算平台、Enomalism 弹性计算平台与Hadoop 开源云计算平台。

Eucalyptus 开源云计算平台是加州大学圣巴巴拉分校为进行云计算研究而实现的亚马逊EC2 开源版本，Eucalyptus 依赖于Linux和Xen 进行操作系统虚拟化，它与商业服务接口兼容。

Enomalism 弹性计算平台作为一个可编程的虚拟云架构，提供了一个功能类似于亚马逊EC2 的云计算框架。与Eucalyptus 开源云计算平台不同，Enomalism 同时支持Xen 和Kernel Virtual Machine（KVM）两种虚拟机制。

Hadoop 是Apache 软件基金会发布的一个开源分布式计算平台，以分布式、高容错性、高伸缩性的Hadoop 文件系统HDFS 和MapReduce 计算模型为核心，为用户提供了系统底层细节透明的分布式基础架构。Hadoop 具有的高可靠性、高扩展性、高效性和高容错能力允许用户将Hadoop 部署在低廉的硬件上，有效组织计算、存储资源，搭建自己的分布式计算平台，并可充分利用集群的计算和存储能力，完成海量数据的处理。

目前Hadoop 已经发展成为包含多个子项目的集合，Hadoop 项目的主体结构如图3-1所示。

HDFS 作为一个分布式文件系统，具有高容错性，能够部署在低廉硬件上，通过提供高吞吐率来访问应用程序的数据，适合那些有着超大数据集的应用程序。HDFS 放宽了可移植操作系统接口POSIX 的要求，能够实现以流的形式访问文件系统中的数据。

MapReduce 作为一种分布式并行计算模型，它可以将任务分发到由上千台商用机器组成的集群上，并以一种高容错的方式并行处理大量的数据集。MapReduce 在执行时先指定一个map 映射函数，把输入键值对映射成一组新的键值对，经过一定处理后交给reduce化简函数。reduce 函数对相同键下的所有值进行处理后再输出键值对作为最终的结果。

图3-1　Hadoop 项目的主体结构图

HBase 是一个分布式的、面向列的非关系型开源数据库，不同于一般的关系数据库，HBase 是一个适合于存储非结构化数据的数据库，只有简单的字符串类型，它是基于列而不是基于行的模式进行数据存储管理。HBase 适合于存储稀疏数据，能够对海量异构数据提供随机访问和实时读写功能，支持基于MapReduce 模型进行海量数据的并行处理。

Hive 最早由Facebook 设计，是一个建立在Hadoop 技术架构基础之上的数据仓库，提供了一些用于数据整理、特殊查询和分析存储在Hadoop 文件中的数据集的工具。Hive 提供了一种结构化数据的机制，支持类似于传统关系型数据库中SQL 语句——Hive QL 语言查询数据。Hive 编译器自动将把Hive QL 编译成一组MapReduce任务，实现与Hadoop 技术架构的一致性。

Pig 是一个对大型数据集进行分析和评估的平台，能够处理大型的数据集。Pig 的底层由一个编译器组成，它在运行时产生一些MapReduce 程序序列。Pig 的用户开发语言采用了Pig Latin 的脚本语言。

Mahout 是可伸缩的机器学习算法库，通过MapReduce 计算模型实现，主要提供了聚类、分类、协同过滤和频繁项集挖掘等基本算法。Mahout 虽然实现了很多机器学习算法，但仍有一些算法处于开发和测试的状态。

ZooKeeper 作为一个为分布式计算框架设计的管理和监测用开源服务，是Hadoop 集群管理中必不可少的模块，用于为开发者提供同步、配置管理、分组和命名等服务。

目前，Hadoop 受到了国内外互联网知名企业的重视，得到了广泛应用：雅虎通过Hadoop 集群支持广告系统和Web 搜索；Facebook 通过Hadoop 集群支持用户行为分析与机器学习；阿里巴巴使用Hadoop 系统用于存储并分析淘宝交易的相关数据；百度使用Hadoop 进行搜索日志的分析和网页数据挖掘。

Hadoop 的发行版本除了Apache 社区提供的开源Hadoop 外，IBM、英特尔、华为、EMC、Cloudera、Hortonworks、MapR 等公司先后推出了具有专业技术支持的商业版本。