作者：荀亚玲
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
并行数据挖掘及性能优化——关联规则与数据相关性分析试读：
前言
数据已经渗透到当今每一个行业和业务职能领域，成为重要的生产要素。大数据虽然孕育于信息通信技术的日渐普及和成熟过程中，但它对社会经济生活产生的影响绝不限于技术层面。本质上，它为我们看待世界提供了一种全新的方法，即决策行为将日益基于数据分析做出，而不是像过去那样更多地凭借经验和直觉做出。数据挖掘是实现大数据知识发现的有效手段和途径，能帮助人们从海量数据中找到未知的、可能有用的、隐藏的规则，可以通过关联分析、聚类分析、时序分析等各种算法发现一些无法通过观察图表得出的深层次“知识”。关联规则作为数据挖掘领域中的一个主要研究内容，可以在不知道或无法确定数据的关联函数或模型时，有效发现大量数据项集之间有趣的关联信息，其已在零售、快消、电商、金融、搜索引擎、智能推荐等领域大有作为。自1993年Agrawal等人首先提出关联规则以来，关联规则的理论研究已经吸引了大量的国内外研究者。围绕关联规则的研究主要集中于两个方面：扩展经典关联规则能够解决问题的范围；改善经典关联规则挖掘算法效率和规则兴趣性。本书侧重于第二方面的研究内容。现有的关联规则挖掘算法因其时空复杂性和I/O代价高，难以适应大数据分析处理任务，利用集群系统、并行技术的强大数据处理能力，研究面向大数据的关联规则挖掘方法和性能优化，对于如今信息爆炸的大数据时代具有重要意义。
近年来，作者一直进行数据挖掘与并行计算方面的研究，围绕大数据时代数据处理的核心理论与技术问题，将数据挖掘技术、并行算法设计及计算模型的优化技术有机结合，试图改善“信息丰富而知识贫乏”的窘境。本书是作者近年来相关科研成果的总结，全书主要内容分为三篇共9章，具体章节编排如下：
第一篇是基础理论篇（包括第1、2章）。该篇对本书涉及的一些相关概念和理论知识做了简要介绍。其中，第1章主要介绍数据挖掘、关联规则、集群系统与并行计算模型及大数据的相关概念、理论基础及应用；第2章对目前影响MapReduce集群性能的关键因素——数据放置策略的研究与进展进行了综述和分析。
第二篇是关联规则并行挖掘及性能优化篇（包括第3～8章）。该篇对并行环境下的关联规则挖掘算法及研究过程中发现的一些性能问题进行了深入探讨与研究。第3章和第4章均研究了基于MapReduce集群环境的关联规则挖掘算法；第5章提出基于约束的频繁项集并行挖掘算法，以提高挖掘结果的针对性，同时也考虑了挖掘过程中的负载均衡问题；第6章和第7章针对频繁项集并行挖掘过程中存在的数据非本地性问题，分别提出了一种新的数据划分策略和任务重定向方法；为了更好地适应关联规则挖掘的高迭代计算任务，第8章提出一种基于Spark平台的挖掘算法。
第三篇是应用篇（包括第9章）。本篇以某钢铁企业的冷轧辊产品生产为背景，将上述研究成果应用于冷轧辊产品质量控制过程的相关性分析中，从而为企业开展产品质量控制提供了一种新的技术方法和解决思路。
本书的完成得到了太原科技大学计算机学院数据挖掘和智能信息系统实验室团队成员的大力支持，尤其是张继福教授提出了宝贵建议，硕士研究生吴晓婷、闫晓妩、李永红、于晓龙等在实验过程中给予了大量帮助。另外，美国奥本大学秦啸教授在研究过程中给予了许多有益的指导和建议。在此一并致以诚挚的谢意。
本书所涉及的研究工作得到了国家自然科学基金资助项目（No.61602335、No.61876122、No.U1731126）、太原科技大学博士科研启动基金项目（No.20172017）的资助，在此谨向相关机构表示深深的感谢。
由于作者水平有限，书中难免有不妥之处，欢迎各位专家和广大读者批评指正。
作 者
2019年3月第一篇 基础理论篇
大数据时代信息技术领域的巨大变革深刻影响了社会生产和人民生活的方方面面，各行各业迅猛发展，各领域呈现出新产品、新技术、新服务和新的发展业态。大数据的战略意义不在于拥有庞大的数据资源，而在于通过“加工”数据实现数据的“增值”。数据挖掘是实现大数据知识发现的有效手段和途径，利用数据挖掘技术能够深层次地探寻大数据背后的价值。关联规则作为数据挖掘领域中的一个主要研究内容，可以在不知道或无法确定数据的关联函数或模型时，能够有效发现大量数据项集之间“有趣的”关联信息。然而，数据的爆炸性增长，动辄达到数百TB、PB甚至EB级的规模，再加之数据类型复杂、高维等数据特征，使得挖掘如此大规模的数据集需要巨大的计算资源，这已远远超出了现有的计算技术和信息系统的处理能力。于是在很大程度上，高性能的并行计算、分布式计算和集群系统的应用就成为解决该问题行之有效的手段。
本篇共包括两章内容（第1、2章）。第1章介绍了数据挖掘、关联规则、集群系统与并行计算模型及大数据的相关概念、理论基础及应用；第2章对在并行计算和分布式计算领域得到广泛且成功应用的MapReduce编程模型的数据放置策略进行了深入分析，并探讨了MapReduce集群环境下数据放置策略的研究现状及研究热点。第1章 绪论1.1 数据挖掘[1]1.1.1 数据挖掘的产生和定义
计算机技术、网络技术和移动通信技术等现代先进技术的飞速发展和普及应用，使得人们获取数据的途径和手段迅猛增多。随着行业应用系统的规模的不断扩大，其所产生的数据爆炸性增长，人们还未来得及适应信息时代的发展就又步入了信息爆炸的大数据时代。正如麦肯锡公司在2011年6月发表的一份报告中指出的那样：数据是新时期的基础生活资料与市场要素，重要程度不亚于物质资产和人力资本，大数据将成为企业提高生产力和竞争力的主要方式与关键要素。然而，数据本身并没有价值，研究大数据的意义在于发现和理解隐藏在其背后的信息内容及信息与信息之间的联系。大数据相当于一个“富饶的矿藏”，有价值的信息就隐藏在其中，包括关联、聚类、分类、趋势、异常等。跨越数据与知识之间的鸿沟需要强有力的分析工具的支撑。对大数据而言，传统的数据统计分析技术和数据库技术已不能满足需求，因此，人们结合机器学习、知识工程、统计学、数据库技术及数据可视化技术，提出了一种强有力的“采矿工具”——数据挖掘技术。
数据挖掘（Data Mining，DM）的概念在1995年由美国计算机协会（ACM）提出。数据挖掘就是从大量的、模糊的、有噪声的、不完全的、随机的数据中，提取隐含的、未知的、非平凡的及有潜在应用价值的信息或者模式的过程。数据挖掘的两个高层次目标是预测和描述。其中，预测是指用一些数据集中已知的变量或字段预测用户感兴趣的变量或字段的值，如各大网站上的推送广告、购物网站上的商品推荐等；而描述则是要找到被描述数据可以被理解的模式，如将杂乱无章的数据进行分类或聚类等。如图1-1所示，完整的数据挖掘过程包含三大阶段：数据准备、数据挖掘和结果输出。图1-1 完整的数据挖掘过程
目前，国内外学者已研究和开发出了一些数据挖掘系统，比较有代表性的通用数据挖掘系统有IBM公司开发的Intelligent Miner、加拿大西蒙弗雷泽大学开发的DBMiner和SGI公司与美国斯坦福大学联合开发的MineSet等。一个结构合理的数据挖掘系统应该具有以下几个特点：①系统功能和辅助工具具有完备性；②系统具有可扩展性；③支持多种数据源；④具有大数据处理能力；⑤具有良好的用户界面和结果展示能力。目前数据挖掘系统主要有集中式数据挖掘系统和分布式数据挖掘系统。
集中式数据挖掘系统是当前发展得较为成熟的数据挖掘系统，其体系结构如图1-2所示，许多商业性的数据挖掘应用软件都是基于该结构的，但不同产品的具体实现技术又不尽相同。控制层用于控制系统的执行流程，协调各功能部件间的关系和执行顺序，其任务主要包括对数据挖掘任务进行解析，并根据解析结果确定数据范围和应该采用的数据挖掘算法。数据源层负责在数据挖掘前将分散存储在多个数据源中的数据通过数据清理和数据集成等预处理操作集成到一个统一的数据库/数据仓库中。待挖掘数据层为挖掘层提供符合数据挖掘算法要求的待挖掘数据集。挖掘层是集中式数据挖掘系统的核心，用来运行各种数据挖掘算法。知识评价及知识库层在将挖掘结果呈现给用户之前通过知识评价有效地去除冗余的、无用的挖掘结果。用户界面及知识展示层通过友好的用户界面及数据可视化技术展示挖掘结果，其可以大大提高系统的易用性。图1-2 集中式数据挖掘系统的体系结构
随着网络技术和分布式数据库技术的发展和成熟，分布式数据库已经得到越来越广泛的应用，原来数据的集中式存储和管理方式也逐渐转变为分布式存储和管理方式。与集中式数据挖掘系统不同，分布式数据挖掘系统当前主要处在研究阶段，还没有出现成熟的商业产品。分布式数据挖掘的研究热点当前主要集中在对超大规模数据集的处理及提高分布式挖掘系统的整体性能上。Grossman等人提出了一种称为PDS的集成框架，该框架首次集成了支持远程数据分析和分布式数据挖掘的数据服务，该框架可用于进行GB级大数据的分布式数据挖掘。[2，3]
1.1.2 数据挖掘的任务与分类
根据发现知识类型的方法的不同，可将数据挖掘的任务类型归纳为以下几类。（1）数据特征化与数据区分
数据特征化是指从与学习任务相关的样本数据集中提取这些数据的特征，从而获取该数据集的总体特征。而数据区分则是发现或提取与学习任务相关的数据的特征，使之与对比数据能够区分开来。（2）分类
分类就是找出一组能够描述数据集合典型特征的模型（或函数），以便能够分类识别未知数据的归属或类别，即将未知事例映射到某一种离散的类别上。分类模型（或函数）可以通过分类挖掘算法从一组训练样本数据（其类别归属已知）中学习获得。典型的分类算法有：决策树算法、神经网络算法、遗传算法和贝叶斯算法等。（3）聚类
聚类就是把源数据按照某个规则划分成若干类的过程，该过程使得属于同一类别的个体之间的差别尽可能小，而不同类别上的个体间的差别尽可能大。聚类和分类方法的不同之处在于：分类是在特定的类标识下指导新元素的分类，而聚类则是通过对数据的分析生成新的类标识。典型的聚类算法有基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法和基于网格的聚类算法。（4）关联分析
关联分析是发现大量数据中项集之间“有趣的”关联或联系的过程。通过对项集进行关联分析，可以找出关联规则。支持度和置信度是两个对关联规则兴趣度进行度量的指标，满足最小支持度或最小置信度要求的规则称为“有趣的”；同时满足最小支持度和最小置信度要求的规则称作强规则。（5）离群点分析
离群点分析是指从数据集中找出一些行为和特征不同于其他数据对象的数据点的过程，这些数据点被称为离群点。在实际应用中，人们常把离群点视为噪声或异常，然而有时候人们可能对离群点更感兴趣。（6）数据演化分析
数据演化分析就是对随时间变化的数据对象的变化规律和变化趋势进行建模描述的过程。这一建模手段包括概念描述、对比概念描述、关联分析、分类分析和时间相关数据分析等。[4-6]
1.1.3 研究前沿和发展趋势
商业化数据挖掘软件的出现进一步推动了数据挖掘技术的普及和发展，但在实际应用中仍存在不少需要继续研究改进之处。现将数据挖掘的研究前沿和发展趋势介绍如下。（1）复杂类型数据的挖掘。包括挖掘序列数据，如符号序列和生物学序列数据；挖掘图和网络数据；挖掘其他类型数据，如时间/空间数据、信息物理系统数据、多媒体数据、文本和Web数据及数据流。（2）可视化和交互性。一个具有良好的可视化和交互功能的数据挖掘系统可以使用户直观地理解数据挖掘任务的定义和执行过程，减少用户挖掘知识的盲目性和挖掘过程中大量无关模式的产生，提高系统的挖掘效率及用户对挖掘结果的满意度和可信度。（3）可扩展性。由于用户的应用环境是不断变化的，因此可扩展性对数据挖掘系统来说非常重要，系统应该支持多种数据源的挖掘及挖掘算法的可扩展性，允许用户根据需要添加新的算法。（4）与特定行业应用相结合。随着应用环境的发展，通用的数据挖掘系统已越来越不能满足用户的需要，用户如果不了解挖掘算法的特性就很难得出好的模型。因此，数据挖掘系统应该和特定行业应用紧密结合，为该应用领域提供一个完整的解决方案。（5）广泛认可的理论基础。数据分析和数据挖掘应具备广泛认可的理论基础，如回归、广义线性模型、方差分析、混合效应模型、因素分析、判别分析、生存分析和质量控制，以及基于数据归约、数据压缩、概率统计理论和基于模式发现的归纳数据库等数据挖掘的理论基础。（6）隐私保护和数据安全问题。数据挖掘带来的主要社会问题是隐私保护和数据安全，数据挖掘应合理合法地处理数据挖掘得到的结果，而不应泄露底层的敏感数据。数据挖掘应在保持数据挖掘结果总体质量的同时保护隐私和确保数据安全。（7）支持移动环境。目前将数据挖掘和移动计算相结合是一个新的研究方向。因此，能够挖掘移动系统、嵌入式系统等其他计算设备所产生数据的数据挖掘系统是未来的一个新的发展趋势。1.2 关联规则[3]
1.2.1 关联规则及其分类
关联规则是由R.Agrawal等人首先提出的一个能够客观反映大量数据中各数据项之间关联或者相关关系的重要研究课题。关联规则最初是针对购物篮分析（Market Basket Analysis）问题提出的，如“90%的顾客在购买A产品时，也会购买B产品”就是一个关联规则的例子。目前关联规则的应用领域主要包括顾客购物分析、目录设计、商品广告、邮寄分析、销售仓储规划及网络故障诊断分析等。
关联规则挖掘过程包含两个阶段：第一阶段用于发现给定事务集中的所有频繁项集，频繁项集是指在事务集中的出现频率超过了某个给定阈值（即最小支持度）的项集；第二阶段是依据第一阶段产生的频繁项集获取关联规则，该规则需在最小置信度的约束下产生。其中，最小支持度和最小置信度是关联规则的两个非常重要的参数，分别反映了规则的有用性和确定性。下面详细介绍关联规则的一些相关概念。
事务集 D由一组交易记录组成，通常可表示为 D={t， t， t，123…， t}，一般为有限集合，其中 t（i=1，2，…， n）为任意的一条ni交易记录，是一个非空项集。每条交易记录 T通常由一组项目列表（Itemlist）组成且都与一个唯一的标识符 TID相对应。所有交易记录中包含的所有项目的集合通常可表示为 I={I， I， I，…， I}，那123m么有 T ⊆ I。设 A、B均是一个项集，关联规则是形如 A⇒B的蕴含式，其中 A∩ B=∅。规则 A⇒B成立，应具有支持度 s（Support），s是事务集 D中包含 A∪ B的概率 P（A∪ B），即 D中事务同时包含 A和 B的百分比；规则 A⇒B还需满足置信度要求 c（Confident），c表示事务集 D中包含 A事务的同时也包含 B事务的百分比，即条件概率 P（B|A）。支持度和置信度公式为：
式中 Count（A）、Count （ A∩ B）分别用来表示项集 A、 A∩ B出现的频度，即包含该项集的事务数。如果一条规则同时满足最小支持度（min_sup）和最小置信度（min_conf）要求，则该规则是有意义的，该规则被称为强规则。
在关联规则挖掘的两个步骤中，第一个步骤相对复杂且比较耗费系统资源，第二个步骤相对简单，因此目前对关联规则的研究主要集中在第一个步骤上，即频繁项集挖掘（FIM）。频繁项集挖掘主要涉及以下两方面的性能问题：①数据集的扫描次数——随着待挖掘数据集规模的增大，减少数据集扫描次数可以大大减少系统扫描时间和降低I/O开销，从而提高关联规则挖掘效率；②候选项集的数量——如果候选项集数量较大，处理这些候选项集所需要的计算时间和存储空间都将急剧增加，因此，应使候选项集的数量与频繁项集的数量尽量接近。
关联规则其实存在于我们日常生活的许多方面中，根据不同标准大致有以下几种类型的挖掘方式。（1）基于所处理变量的类别，关联规则可以分为布尔型关联规则和数值型关联规则。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值型关联规则可以和多维关联规则或多层关联规则结合起来，对数值型字段进行处理，将其进行动态分割或者直接对原始数据进行处理。当然数值型关联规则中也可以包含种类变量。例如，性别=“女” ⇒职业=“秘书”，是布尔型关联规则；而性别=“女” ⇒ avg（收入）=2300，其中收入是数值类型，所以这是一个数值型关联规则。（2）基于规则中数据的抽象层次，关联规则可以分为单层关联规则和多层关联规则。在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同层次的；而在多层关联规则中，对数据的多层性已经进行了充分考虑。例如，IBM 台式机 ⇒ Sony 打印机，是一个细节数据上的单层关联规则；台式机 ⇒ Sony打印机，是一个较高层次和细节层次之间的多层关联规则。（3）基于规则中涉及的数据的维数，关联规则可以分为单维关联规则和多维关联规则。在单维关联规则中，只涉及数据的一个维度，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维度。换句话说，单维关联规则处理单个属性中的一些关系；多维关联规则处理各属性之间的某些关系。例如，啤酒 ⇒尿布，这条关联规则只涉及用户购买的物品；性别=“女” ⇒职业=“秘书”，这条规则就涉及两个字段的信息，是一条两个维度上的关联规则。[3，7]1.2.2 关联规则挖掘算法
目前关联规则挖掘已经有很多比较成熟的算法。传统的关联规则算法主要分为Apriori算法和FP-Growth算法两大类。在实际应用中，用户通常对关联规则的子集感兴趣，为此Srikant等人提出了基于约束的关联规则；当引入概念层次的概念后，在适当的等级上挖掘出来的数据项间的关联规则可能是非常有用的，因此多层关联规则挖掘被提出；为了减少频繁项集的产生，闭模式挖掘和极大模式挖掘算法被提出；另外多维关联规则等基于不同应用背景的关联规则算法也被大量的研究者关注，尤其是大数据环境下的分布式/并行关联规则更是备受关注。本节主要介绍传统关联规则挖掘算法和并行/分布式关联规则挖掘算法。
1.传统关联规则挖掘算法
如前所述，频繁项集挖掘是影响关联规则挖掘性能的关键步骤，因此，对关联规则挖掘算法的研究主要集中在该阶段。目前，频繁项集主要通过Apriori算法和FP-Growth算法生成。
Apriori算法是一种挖掘频繁项集的经典方法。Apriori算法是一种自底向上逐层搜索的迭代方法，即k-项集用于生成(k+1)-项集，每次迭代过程都需要重新扫描数据集，而且由k-项集进行自连接生成(k+1)-项集时会产生大量的候选项集。也就是说，Apriori算法是一个多趟搜索算法，即最长的频繁项集有多长，Apriori算法就需要扫描多少趟数据集。当面对海量数据集时，Apriori算法的I/O开销很大。Apriori算法最大的性能问题在于对项集及其支持度的计算。假设事务集中包n含项目个数为n，Apriori算法需要计算2个项集，若n很大，将会产生组合爆炸。为了改进Apriori算法，一些研究人员做出了努力：Park等人提出了DHP算法，该算法利用Hash技术对候选项集的生成过程进行了改进；Savasere等人提出了Partition算法，该算法首先对数据集进行分区，然后基于这些分区分别寻找其对应的频繁项集，最后合并得到最终的频繁项集，该算法的整个过程只需要两次数据集扫描；Toivonen等人提出了基于抽样的Sampling算法，该算法也仅通过两次数据集扫描获取频繁项集，首先通过随机数据抽样寻找样本频繁项集，然后再获取全体频繁项集；Brin等人提出了DIC算法对候选项集进行动态计算，该算法与Sampling算法相比，需要计算频繁项集更少，因此，效率也更高。
虽然上述的Partition算法、Sampling算法和DIC算法等都试图减少对数据集的扫描次数，但仍存在着很多问题。Sampling算法首先从原始数据集中通过随机抽样得到部分样本数据，然后利用样本来寻找频繁项集，但数据集中数据分布不均匀的情况是经常存在的，因此这种随机抽样可能无法保证抽取到的样本具有代表性。Partition算法先对数据集做了分区操作，然后分别挖掘，最后再经过汇总得到最终结果。该方法虽然减轻了I/O负担，但事实上它却增加了CPU负担。DIC算法虽然采用了动态计算的策略，但其与Apriori算法没有本质区别，即DIC算法还属于多趟搜索算法。这些算法在计算过程中会生成大量不必要的候选项集，因此计算量很大。当面对海量数据集时，上述算法的性能问题会更加明显。由此可见，以上算法只有在最小支持度和最小置信度都设置得比较大或增加设置其他一些约束条件后，挖掘效率才会有明显提高，否则候选项集的产生过程将会出现组合爆炸问题。在频繁项集挖掘过程中，必须对所有项集及其支持度进行计数，这也是影响频繁项集挖掘算法效率的关键所在。该类算法每一轮的计算不仅占用大量CPU时间，而且还涉及频繁的I/O操作，因此只有从本质上改变这种自底向上的逐层计算模式，才能从根本上提高算法效率。
为了提高Apriori算法的性能，韩家炜等人提出了另外一种挖掘思路，即频繁模式增长（FP-Growth）算法。该算法采用频繁模式树（FP-tree）存储结构将数据集进行压缩存储，并基于FP-tree完成频繁模式（也称频繁项集）挖掘。FP-Growth算法在效率上较Apriori算法有较大的提高。FP-Growth算法利用一种紧缩的数据结构FP-tree来存储和查找频繁项集所需要的全部信息，它通过逐个读入事务来把事务追加到FP-tree中。这样，对于FP-tree中某个节点对应的项，存在一个或多个从根节点到达该节点的路径。显然，一些相同的项目或项集可能会被包含在不同的事务中，因此它们的路径可能部分重叠，而且这种重叠路径越多，FP-tree的压缩效果越好。当FP-tree足够小时，就可以被放置于内存中并直接从内存中挖掘频繁项集，而不必重复地扫描存放在硬盘上的数据。FP-Growth算法的步骤描述如下。（1）导出频繁1-项集。逐条扫描数据集，对所有项目进行支持度计数，将满足最小支持度要求的频繁1-项集按支持度计数实现降序排列，并记作L。（2）构造FP-tree。首先，创建树的根节点，标记为“null”，然后对数据集进行第二次扫描，其中每条事务记录中的项按L中的次序处理，即按支持度计数降序排列，并创建或增加每个事务在FP-tree中的一个分枝，与此同时，当存在共同前缀时，为共同前缀对应的节点计数增加1，并为在前缀后的项目创建节点和链接。为便于树的遍历，还会创建一个项目头表，使每个频繁1-项集通过一个节点链指向它在树中的位置。经过这样的数据压缩处理后，对频繁项集的挖掘就转换成对FP-tree的挖掘。（3）挖掘FP-tree生成的所有频繁项集。从每个长度为1的频繁项集开始，构造该模式的条件模式基，此条件模式基由FP-tree中与后缀模式一起出现的前缀路径集构成，然后基于条件模式基构造它对应的条件FP-tree，并递归地对该树进行挖掘，模式增长通过后缀模式与条件FP-tree产生的频繁项集连接实现。
FP-Growth算法只需要通过两次数据集扫描将数据集压缩到一个称为FP-tree的树结构中，并通过对FP-tree的递归挖掘产生最终的频繁项集，避免了过多候选项集的产生。FP-Growth算法的瓶颈主要在于：①需要构造基于内存的FP-tree；②对FP-tree的挖掘过程需要递归进行，从而产生了大量的条件FP-tree。人们基于此提出了很多改进算法：Liu G等人采用了一种简单的压缩数据结构AFOPT（频繁度升序前缀树）存储条件数据集，该数据结构利用数组来存储单分支，以节省存储空间，后续的挖掘过程对AFOPT进行自顶向下深度优先遍历；Pramudiono等人使用了与FP-tree类似的树结构，但是遍历方法与FP-tree不同，采用了自顶向下和自底向上相结合的遍历方法；CFP-tree在磁盘上存储预计算的频繁项集以节省存储空间，且在挖掘过程中同时使用前缀共享和后缀共享。但当数据集很大时，构造基于内存的树结构及递归挖掘过程中存储大量中间结果仍然是不现实的，因此人们开始借助更高性能的并行/分布式平台来解决该问题。
2.并行/分布式关联规则挖掘算法
基于Apriori算法的并行挖掘算法可以分为两大类：①计数分布类，如计数分布（CD）算法、快速并行挖掘算法、并行数据挖掘（PDM）算法；②数据分布类，如数据分布（DD）算法、智能数据分布（IDD）算法。在计数分布算法中，并行系统的每个处理器计算所有候选项集的局部支持度计数。然后，所有处理器通过交换本地支持度计数计算所有候选项集的全局支持度计数。CD算法和PDM算法具有简单的通信模式，因为在每次迭代中每个处理器只需要一次通信。在数据分布类算法中，每个处理器仅保存所有候选项集的一个子集的支持度计数。每个处理器负责发送其本地数据分区到所有其他处理器来计算支持度计数。一般情况下，DD算法比CD算法具有更高的通信开销，因为传输事务数据要比传输支持度计数需要更高的通信带宽。
现有的基于Apriori算法的并行挖掘算法，其梯级运行模式会导致较高的通信和同步开销。为了减少扫描数据集和交换候选项集所需要的时间，基于FP-Growth算法的并行算法被提出，并逐渐取代了基于Apriori算法的并行算法。早期，几个基于多核处理器且采用多线程计算的FP-Growth算法被提出，这些并行算法的主要缺点是：当数据集很大时，构建基于内存的FP-tree是不可行的，当数据海量和高维时，这个问题尤为明显。
集群和其他无共享多处理器系统是解决上述内存问题的一种可扩展计算平台。例如，Pramudiono和Kitsuregawa提出了一种集群下的并行FP-Growth算法；在无共享多处理器环境下，Javed和Khokhar提出了一种采用消息传递接口实现的高效并行算法，他们提出的基于Pfp-tree的并行算法通过合理地划分FP-tree和处理器上的频繁项目列表，有效地减少了同步开销；Tang和Turkia利用扩展的条件数据集和k-前缀搜索空间划分，提出了基于FP-tree的一种新的实现方法；Yu和Zhou提出了两种并行挖掘算法，即基于Tidset的并行FP-tree（TPFP-tree）挖掘算法和平衡Tidset的并行FP-tree（BTP-tree）挖掘算法，TPFP-tree算法使用事务标识集直接选择事务，而不需要扫描整个数据集。像大多数集群环境下的并行挖掘算法一样，TPFP-tree采用了消息传递接口编程模型。这些并行算法在实现过程中，会暴露出并行计算平台可能存在的一些性能问题，如并行平台存在数据放置问题，任务调度缺乏对异构环境的考虑，节点之间通信量大，异步代价大，计算负载不均衡等。针对这些问题，一些优化策略被提出。
负载均衡技术已被广泛应用以提高并行挖掘算法的性能。Cong等人设计了一种基于采样的并行数据挖掘框架，这一框架通过合理地划分频繁项集并将其分配给合适的处理节点来解决负载不均衡的问题。在计算所分配项目的投影数据集后，每个处理器异步地利用模式增长方式挖掘投影数据集，从而不需要相互通信。为了优化异构环境下的挖掘性能，Yu等人开发了BTP-tree算法，它是TPFP-tree算法的扩展，BTP-tree算法采用的负载均衡方案考虑了异构节点的计算能力，从而有效地改善了异构环境下的频繁项集并行挖掘能力。Zhou等人基于Pfp算法，提出了一种平衡的并行FP-Growth算法。
集群环境下面向集群数据密集型应用的频繁项集挖掘已经获得了越来越多的关注，高效的数据划分策略已经被提出用以改进并行频繁项集挖掘算法的性能。Zhou等人提出一个基于MapReduce的Apriori算法，其中引入了新的动态划分机制和数据分发机制，以提高挖掘性能。该方法把输入数据分割成相对较小的分片，以灵活地进行负载均衡处理。此外，主节点并不是将所有数据一次分配出去，而是将剩余的数据基于工作负载的动态变化和每个计算节点的能力再进行分配。同样，Jumbo采用了动态分区分配技术，使每个任务处理不止一个分区，因此这些分区可以动态地重新分配给不同的任务以提高Pfp算法的负载均衡性能。为了优化数据块分配方法，Uthayopas等人研究了I/O和执行调度策略，用来平衡数据处理负载，从而提高多核集群关联规则挖掘算法的性能。为了选择合适的数据块分配策略，他们采用了3种基本的数据放置策略，即循环放置、区域放置和随机放置，但该方法在关联规则挖掘过程中忽略了数据特征。[8]1.3 集群系统与并行计算模型
1.3.1 集群系统
数据挖掘是对大数据处理方法的探索，然而由于行业数据的爆炸性增长和数据类型的复杂、时变、高维等数据特征，传统的数据挖掘算法已经不适应发展的速度了，人们已经开始借助于高性能的并行/分布式平台提高挖掘效率。
在摩尔定律的作用下，以前程序员不需要考虑计算机的性能会跟不上软件的发展，然而由于受到散热问题、功耗问题及处理器材料物理特性的限制，人们再不能期待通过单一地提高单个处理器的处理能力而不需要改变软件就获得“免费”的性能提升了。Intel、AMD和IBM等芯片厂商着手从多/众核这个角度来挖掘CPU的性能，但是这将使软件编程方式发生重大变革，而且现有的软件无法直接利用多核的优势提高执行性能，因此，并行/分布式处理技术成为最大限度利用多/众核处理器能力的必要手段。由于多/众核处理器的处理能力仍然有限，廉价、灵活的集群环境就成为目前并行/分布式计算最主要的开发环境。
集群是由一组相互独立的、通过高速网络互联的计算节点构成的一个群组，并以单一系统的模式对其加以管理。当用户使用集群时，就像是在使用一台单独的计算机。与传统的高性能计算机技术相比，集群具有以下特点：①高处理性能，当面对需要很强运算处理能力的计算任务时，普通计算节点甚至大型服务器也很难胜任，而集群可以将几百台甚至更多计算机的运算能力集中起来以满足需求。②低成本，集群可以将任何配置的计算机作为一个计算节点，因此集群系统造价低，与专用超级计算机相比具有很高的性价比。③高可扩展性，当用户需要扩展计算性能时，只需要将新的计算节点加入集群即可。由于采用集群技术，对用户来讲整个过程是透明的，用户体验几乎不会受到影响。④高可靠性，当一个计算节点发生故障时可以将计算任务自动迁移到别的计算节点完成，整个集群仍可以继续工作，因此集群在保证了系统可靠性的同时，也降低了故障损失。
根据涉及的关键技术，集群的体系结构可以归纳为四个层次。①网络层：涉及网络互联结构、通信设备与技术、通信协议等技术。②节点机及操作系统层：涉及高性能客户机、分层或基于微内核的操作系统等。③集群系统管理层：涉及资源调度与管理、负载均衡、并行安全等性能问题。④应用层：涉及并行开发环境、并行应用、用户交互等技术。不同层次解决的问题不同，集群技术是这4个层次的有机结合，这四个层次缺一不可。
1.3.2 并行计算模型
对用户而言，他们主要关注能够以并行、易用、可扩展、透明且容错的方式使用大规模廉价集群的方法，即将简单的业务处理逻辑从复杂的实现细节中提取出来，使用户和程序员不需要关心底层的实现和运行细节。设计合理的并行计算模型是解决该问题的关键。计算模型是一种涵盖存储模型、执行模型、调度模型、容错模型的综合抽象模型，可以有效屏蔽集群底层大量繁杂的并行、调度、管理和性能控制等细节。在大数据背景下，工业界和学术界对并行计算模型进行了广泛且深入的研究，以应对新形势下的大规模数据处理，现将其归纳如下。（1）面向批处理的并行计算模型
目前，典型的面向批处理的并行计算模型有最早受到关注且被广泛成功应用的MapReduce模型和由微软推出的Dryad模型。MapReduce模型随着其开源实例Hadoop的兴起，已经形成了比较完善的海量数据分析生态系统，并且大量的外围系统的补充开发为MapReduce模型成功应用提供了支撑。MapReduce模型具有可扩展性、可用性、容错性等优点，且通过将复杂的处理流程抽象为Map函数和Reduce函数提高了其可编程性。然而MapReduce模型更关注节点间的高层次并行，对多核CPU或GPU的适应性较差。Phoenix采用共享内存方式，底层实现建立在P-threads上，为MapReduce模型在多核环境下的实现提供了优化方案。此外，随着MapReduce模型被广泛深入地应用，其存在的问题也日益突出，如对迭代算法的支持、数据倾斜、调度效率、对关系代数的支持等问题。MapReduce模型作为通用的大数据分布式并行计算模型，没有针对具体应用领域及新型硬件进行专门的优化，这将使其很难应对大数据处理架构多样化模式并存的挑战。（2）面向流处理的并行计算模型
实时数据流的典型特征：数据蕴含的价值会随着时间的流逝而降低，即数据价值具有时效性。当数据以大量、连续时变的方式到达系统时，低延迟成为面向数据流处理的最基本要求。面向批处理的MapReduce模型在处理流数据时具有很大的局限性。
面向大数据应用，一些研究者尝试将MapReduce模型与典型的数据流系统进行融合，但MapReduce模型本身的局限性使其不能从根本上适应流数据处理。因此，适用于大规模流数据处理的计算模型成为业界研究的热点，如Yahoo推出的S4模型、Facebook开发的Puma模型及Twitter的Storm模型等。但这些系统模型均致力于解决企业自身的实际应用问题，适用范围非常有限。（3）面向大图数据的并行计算模型
在大数据时代，大规模图不断涌现，传统的图数据处理技术已不能满足需求，于是大图数据处理模式逐渐转向并行处理模式。被广泛使用的MapReduce模型不能适应大图处理过程中的迭代计算和以顶点为中心的处理方式。因此，人们研究了大图并行计算模型，根据存储架构上的不同，大图并行计算模型可以分为两类：面向分布式内存架构的模型和面向单机多核共享内存架构的模型。Pregel、Giraph是应用分布内存架构的典型代表。而由于图结构具有高耦合性，基于分布式内存架构的图计算的网络通信代价会很高，因此合理的图划分成为优化分布式大图计算的有效手段，如GraphX。显然，多核共享内存的大图并行计算模型能有效利用多核处理器及新型存储技术的高并发能力克服图划分和网络通信问题，但其计算能力又相对有限。（4）基于内存的并行计算模型
以上并行计算模型受限于廉价计算机构建的运行环境，面临着内存容量有限、I/O效率低下、实时性差等诸多问题。因此，在新型实时应用的驱动下，以最短响应时间为设计目标的、基于内存的计算模型出现了，其中最具有代表性的要数目前最为火热的Spark并行计算模型，其是UC Berkeley开源类Hadoop和MapReduce的通用并行计算框架。Spark将中间结果保存至内存，不需要读写外部文件系统，避免了高延迟的磁盘访问，而且能更好地适应交互式迭代计算。弹性分布式数据集RDD是Spark提供的最主要的抽象模型，RDD是只读的、记录分区的集合，这些集合是弹性的，任何集合只能通过在其他RDD执行确定的转换操作（如Map、Filter和Join等）而创建，在部分数据集丢失的情况下利用Lineage容错机制进行重建。Spark提供了比Hadoop的Map和Reduce更为丰富的数据集操作类型，这种多样化的数据集操作类型给开发上层应用的用户提供了方便。
1.3.3 大数据处理架构Hadoop与Spark
MapReduce是目前应用于大数据处理最成功的计算模型，是进行大数据分析的最具吸引力的工具之一。Hadoop是典型的通过MapReduce框架开源实现的分布式系统基础架构，由于其具有较好的容错性、高可靠性、高扩展性及高效性而得到广泛应用。当Hadoop被广泛应用时，基于内存计算的Spark并行计算架构被提出。Spark拥有Hadoop的优点，但不同于Hadoop的是，其将计算过程中的输出结果保存至内存中，而不再需要读写外部文件系统，因此Spark能更好地适用于需要迭代计算的MapReduce编程模型。
1.Hadoop
Hadoop是一种基于批处理技术的开源分布式计算平台，使用Java语言编写，其主要由两大核心部件组成，即HDFS（Hadoop Distribute File System，分布式文件系统）和MapReduce编程模型，二者分别是GFS（Google File System）和GMR（Google MapReduce）的开源实现。（1）MapReduce编程模型
Google工程师Jeff Dean和Sanjay Ghemawat于2004年提出了MapReduce基本原理和主要设计思想——用于处理大规模数据的并行处理框架，其思想来源于函数式编程语言的Map函数和Reduce函数。MapReduce通过将数据处理过程分解为Map和Reduce两个步骤，为用户和编程人员提供一个既简单又强大的接口，从而可以把大规模计算自动地并发和分布式执行。
MapReduce定义的抽象编程接口均将数据转换为键值（key/value）对形式来处理。Map接口定义为：
Map即数据映射，由该接口定义可知，输入数据将被转化为(k,v)形式的键值对，经用户自定义的Map函数处理后，将其映射成11一组新的键值对(k, v)。Reduce接口的定义为：22
Reduce即数据规约，Reduce函数将Map函数的结果[(k, v)]作为22输入，并对该输入中具有相同键值的数据进一步归并排序后形成(k,list[v])，然后被用户定义的Reduce函数对其做化简、合并等操作，22得到最终的输出结果[(k, v)]，该结果仍然以键值对的形式出现。33
虽然接口设计简单，但在实际的数据处理过程中会涉及很多复杂的细节问题，图1-3详细描述了MapReduce的并行处理过程。图1-3 MapReduce的并行处理过程
从图1-3可以看出，一个MapReduce作业（Job）通常会把输入数据集划分为若干个独立的数据分片（Splits），并由Map任务（Map Tasks）以完全并行的方式处理，随后Map任务的输出被分区、排序及合并等一系列中间操作处理后复制至相应的Reduce任务（Reduce Tasks）并执行得到最终结果。MapReduce框架由一个单独的Master JobTracker和每个集群节点的一个Slave TaskTracker组成，JobTracker负责整个作业执行过程中的应用程序的总体协调工作，TaskTracker则具体负责执行作业被划分后的各计算任务。在整个数据处理过程中，JobTracker和TaskTracker之间通过TaskTracker的周期性“心跳”进行通信，整个框架依据该“心跳”负责任务的调度、监控及容错等很多底层的细节处理。由于JobTracker既要负责任务状态的监控又要负责任务的具体调度工作，很容易遭遇单点性能瓶颈。针对该问题，Hadoop 0.23版本对MapReduce进行了优化，其主要思想是将资源管理功能交给另一种资源协调者（Yet Another Resource Negotiator，YARN）来进行管理。YARN将JobTracker的功能进行拆分，通过创建一个全局的ResourceManager（RM）来负责总体的任务调度和创建若干个针对应用程序的ApplicationMaster（AM）来完成具体的作业。
Hadoop运行在大型集群上对海量数据进行处理，需要对大量的任务进行合理的分配与管理，即Hadoop性能与其具体的调度算法直接相关。Hadoop自带的调度算法有三种，即最简单的先进先出调度算法（FIFO）、基于容量的计算能力调度算法（Capacity Scheduler）和公平调度算法（Fair Scheduler）。除此以外，一些学者还根据具体的应用领域或不同集群环境特征提出了适用于异构集群的LATE（Longest Approximate Time to End）调度算法及自适应的调度算法等。
FIFO调度算法中用户作业都被提交到一个单一的队列中，并按照先进先出的原则进行调度。FIFO算法的实现较为简单、开销相对较小，但FIFO调度算法存在的问题也是显而易见的：当队列中存在大作业时，占用资源时间较短的小作业可能需要花费较长的时间等待，即可能需要较长的响应时间。当面对多用户情况时，这个问题会产生严重的不公平。计算能力调度算法由Yahoo提出，该方法能够支持多个队列进行调度，且在每个队列内部也采用FIFO算法调度。计算能力调度算法支持作业按优先级进行调度，但不能抢占已开始执行作业的资源。在进行作业选择时，每个队列都设置一个权值，即为该队列中的任务数与该队列应分得的计算资源的比值。一旦集群中有计算节点处于空闲状态，调度算法就选择一个权值最低的队列，并按照“先进先出”策略选择其中的一个作业执行。另外，计算能力调度算法在选择作业时，还需考虑作业所属的用户能够使用的计算资源限制，其目的是为了保证用户获取计算资源的公平性。公平调度算法是由Facebook开发的，其将整个集群的计算资源按照“池”来划分，并用“池”来管理作业，每个用户可以获得一个计算资源相对公平的资源池来执行自己的作业。在每个资源池的内部，既可以采用FIFO调度算法进行调度，又可以采用公平调度算法来进行作业调度，还可以在其中加入相应的优先级进行作业调度。
总之，MapReduce编程模型使用户和程序员不需要关心底层的一些实现细节，这些细节包括：如何将输入数据进行分块、划分；如何进行作业调度；当集群内出现节点故障等容错问题时，如何处置；节点间如何通信等。即后台复杂的并行执行和任务调度细节对更高层的用户和编程人员来讲是透明的，这样可以使用户比较容易地使用一个大的分布式系统提供的计算资源，同时还可使得由普通计算机组成的巨大计算“组”具有极高的计算性能。因此，MapReduce编程模型自出现以来，在工业界和学术界得到了广泛的关注。（2）HDFS
在MapReduce的整个数据处理过程中，所有任务的输入和输出都由HDFS来管理。HDFS是一个高度容错的分布式文件系统，其采用了主从模式的管理方式，即采用元数据集中管理、数据块分散存储的模式。HDFS中包含一个名称节点（NameNode）和多个数据节点（DataNode）。NameNode是文件系统的管理者，负责文件命名空间的管理及完成对外部客户访问的控制。DataNode是具体的工作节点，用于存储实际的数据，并根据客户端或NameNode的调度存储和检索数据，它创建了数据块的多个副本，从而可以在不同的集群中进行快速且可靠的数据访问。
HDFS具有高容错性，这是通过数据备份的方式来实现的。HDFS在数据建立阶段，即上传数据至文件系统时，将文件按固定大小的块进行数据划分（默认大小为128MB），系统会按照一定的策略将这些数据块分散存储到各个DataNode上。为了保证数据的安全性和系统容错性，HDFS会对每一个数据块进行备份，在默认情况下，系统为每个数据块存放3个副本。整个数据放置过程，Hadoop采用了默认的机架感知策略，如图1-4所示。其基本数据存储策略为：在运行客户端的节点上存放第一个副本，当客户端运行在集群之外时，系统会随机选择一个节点存放副本，但会避开那些太忙或存储太满的节点；第二个副本会被放在与第一个副本不同且随机的另一机架上的某个节点上；第三个副本则在放置第二个副本的机架上随机选择一个节点来存放。该数据放置策略考虑了系统的读取性能、写入带宽及数据块分布的均匀性，为集群系统提供了很好的容错性和稳定性，同时实现了很好的负载均衡。图1-4 Hadoop机架感知数据放置策略
2.Spark
继Hadoop之后，Spark凭借其先进的设计理念和与Hadoop平台的兼容性，不论在研究领域还是在生产领域都已经出现逐步替代Hadoop的趋势。在前面对Hadoop的介绍中，我们知道Hadoop通过HDFS读写和管理数据，由此引入了大量的磁盘I/O和网络I/O，且HDFS采用了如图1-4所示的策略用多副本方式进行数据容错，这更凸显了Hadoop的I/O瓶颈。此外，当Hadoop面对复杂的挖掘任务时，往往需要串接多个MapReduce作业才能完成，由此会造成多个作业之间数据交互导致的冗余磁盘读写开销和资源的多次申请，这使得基于MapReduce的算法会面对更为严重的性能问题。而Spark作为大数据分析处理工具的后起之秀，凭借其基于内存的计算模式和有效的容错机制等优势，可以自动调度复杂的计算任务，避免中间结果的磁盘读写和资源申请过程，非常适合复杂的数据挖掘算法。Spark由UC Berkeley的研究人员提出，他们在论文中描述：对一些数据密集型的计算，如逻辑回归，Spark运行速度比Hadoop快了40倍左右。对很多迭代程序来讲，该方法可以使数据通过内存来进行交互，从而大大加快了任务运行速率。
Spark采用Scala语言实现，集成面向对象和函数式编程的各种特性，且Scala运行在Java虚拟机上，可以直接调用Java类库，为数据处理提供了独一无二的环境。Spark通过构建弹性分布数据集RDD提供基于内存的集群计算。RDD是分区的、只读的、不可变的并能够被并行操作的数据集合，可以从HDFS上读取得到，也可以通过在其他RDD上执行确定的转换操作（如Map、Filter等）得到。RDD保存的并不是真实的数据，而是一些元数据信息，即该RDD是通过哪些RDD上附加哪些操作得到的。因此，RDD的这些特性使其实现容错的开销很低，仅需要通过RDD间的“血统”（Lineage）来重新生成丢失的分区。
Spark提供了丰富的数据集操作类型，使用户对RDD的使用可以像操作本地数据一样，不像Hadoop只提供了Map和Reduce两种操作。这种多样化的数据集操作类型，给开发上层应用的用户提供了方便。这些操作被分为两大类，即动作（Actions）和转换（Transformations）。Actions是在RDD上进行计算后返回结果给驱动程序或写入文件系统的，Transformations是将现有的RDD转换返回一个新的RDD。其中，Transformations是延时执行的，即采用的是惰性策略，如果只是提交Transformations是不会按提交任务来执行的，只有在Actions提交时任务才会被触发，该设计思想让Spark运行更加有效。RDD的一系列操作使RDD之间的依赖关系形成一个有向无环图DAG，DAGScheduler根据DAG的分析结果将一个作业分成为多个阶段并调度执行。
如图1-5所示为Spark集群架构，可以看出，Spark集群中存在两种角色，即驱动程序Driver和工作结点Worker。Driver将SparkContext对象作为程序的入口，在初始化过程中集群管理器会创建DAGScheduler作业调度和TaskScheduler任务调度。在执行阶段，Driver将执行代码传给各Worker，Worker对相应分区的数据进行实际的并行计算，并将计算后的RDD数据集缓存在本地内存中。图1-5 Spark集群架构1.4 大数据环境下的数据挖掘及应用[9]
1.4.1 大数据
大数据这一概念几乎已经家喻户晓，其已经渗透到人们生活中的各个领域。计算机技术、网络技术和移动通信技术等现代先进技术的飞速发展和普及应用，使人们获取数据的途径和手段增多，且行业应用系统规模的不断扩大，其应用所产生的数据量呈爆炸性增长。
其实，著名未来学家阿尔文·托夫勒早在1980年，便在《第三次浪潮》中将大数据热情地赞颂为“第三次浪潮的华彩乐章”。但由于当时计算机技术、网络技术的发展尚不成熟，大数据这一概念未能引
试读结束[说明：试读内容隐藏了图片]