下载文档原格式
技术平台基于Hadoop电商大数据的挖掘与分析技术研究陈娥祥（福州工商学院，福建 福州 350715）摘 要：随着社会经济水平的不断提高和互联网时代的不断发展，全球数据逐渐呈现出大规模增长的趋势，为了满足海量数据处理需求，大数据挖掘与分析技术应运而生。
Hadoop的出现和应用不仅能科学、高效地处理海量数据，还能可视化展现海量数据最终处理结果，为电商企业的健康、可持续发展提供重要的数据参考和支持。
基于以上情况，以福州地区美容行业的电商系统为例，在介绍相关理论与技术的基础上分析了数据挖掘算法，从系统的整体设计、数据准备、数据挖掘分析三个方面入手，研究了电商大数据挖掘系统的设计，从实验环境、实验数据准备和实验结果分析三方面入手，探讨了系统可视化实现与效果。
希望通过这次深度分析与研究，对公司的运营决策提供有力帮助，为电商平台各方参与者、相关领域技术人员提供有效的借鉴和参考。
关键词：Hadoop；电商大数据；挖掘分析；可视化技术随着社交媒体的不断发展，企业处理数据的途径日益增加、规模日益扩大，并形成了海量的数据流。
在这样的背景下，我国逐渐进入了大数据时代，大数据的生成速度呈现出指数爆炸形式，加上数据在处理的过程中无法分解为常用的数据库，这无疑增加了企业访问和处理数据的难度。
目前，在我国电商行业的迅猛发展下，数据规模递增，为了实现对消费者购买行为相关数据的深入、全面挖掘，进一步提高电商企业的销售业绩，在Hadoop框架的应用背景下，加大对大数据挖掘与分析技术的科学应用，实现数据挖掘技术与电商平台的有效融合，是相关领域技术人员必须思考和解决的问题。
1 相关理论与技术研究1.1 Hadoop平台相关技术研究Hadoop作为一种开源编程框架，被广泛应用于Apache基础项目中。
该框架的编写语言主要以Java语言为主，能够为海量数据集的分布处理提供重要支持。
同时，在部署的过程中，使用的服务器购买价格普遍较低，缩小了物力成本，这样一来，作为开发人员就可以投入较低的成本，实现Hadoop集群搭建，极大地提高了开发效率和效果。
Google MapReduce中文版译者: alexMapReduce是一个编程模型，也是一个处理和生成超大数据集的算法模型的相关实现。
用户首先创建一个Map函数处理一个基于key/value pair的数据集合，输出中间的基于key/value pair的数据集合；然后再创建一个Reduce函数用来合并所有的具有相同中间key值的中间value值。
现实世界中有很多满足上述处理模型的例子，本论文将详细描述这个模型。
MapReduce架构的程序能够在大量的普通配置的计算机上实现并行化处理。
这个系统在运行时只关心：如何分割输入数据，在大量计算机组成的集群上的调度，集群中计算机的错误处理，管理集群中计算机之间必要的通信。
采用MapReduce架构可以使那些没有并行计算和分布式处理系统开发经验的程序员有效利用分布式系统的丰富资源。
我们的MapReduce实现运行在规模可以灵活调整的由普通机器组成的集群上：一个典型的MapReduce 计算往往由几千台机器组成、处理以TB计算的数据。
程序员发现这个系统非常好用：已经实现了数以百计的MapReduce程序，在Google的集群上，每天都有1000多个MapReduce程序在执行。
在过去的5年里，包括本文作者在内的Google的很多程序员，为了处理海量的原始数据，已经实现了数以百计的、专用的计算方法。
这些计算方法用来处理大量的原始数据，比如，文档抓取（类似网络爬虫的程序）、Web请求日志等等；也为了计算处理各种类型的衍生数据，比如倒排索引、Web文档的图结构的各种表示形势、每台主机上网络爬虫抓取的页面数量的汇总、每天被请求的最多的查询的集合等等。
大多数这样的数据处理运算在概念上很容易理解。
然而由于输入的数据量巨大，因此要想在可接受的时间内完成运算，只有将这些计算分布在成百上千的主机上。
如何处理并行计算、如何分发数据、如何处理错误？所有这些问题综合在一起，需要大量的代码处理，因此也使得原本简单的运算变得难以处理。
MapReduce编程一、实验目的1、理解MapReduce编程模型基本知识2、掌握MapReduce开发环境的搭建3、掌握MapReduce基本知识，能够运用MapReduce进行基本的开发二、实验原理MapReduce 是Hadoop两个最基础最重要的核心成员之一。
它是大规模数据（TB 级）计算的利器，Map 和Reduce 是它的主要思想，来源于函数式编程语言。
从编程的角度来说MapReduce分为Map函数和Reduce函数，Map负责将数据打散，Reduce负责对数据进行聚集，用户只需要实现map 和reduce 两个接口，即可完成TB级数据的计算。
Hadoop Map Reduce的实现采用了Master/Slave 结构。
Master 叫做JobTracker，而Slave 叫做TaskTracker。
用户提交的计算叫做Job，每一个Job会被划分成若干个Tasks。
JobTracker负责Job 和Tasks 的调度，而TaskTracker负责执行Tasks。
常见的应用包括：日志分析和数据挖掘等数据分析应用，另外，还可用于科学数据计算，如圆周率PI 的计算等。
MapReduce 框架的核心步骤主要分两部分：Map 和Reduce。
当你向MapReduce 框架提交一个计算作业时，它会首先把计算作业拆分成若干个Map 任务，然后分配到不同的节点上去执行，每一个Map 任务处理输入数据中的一部分，当Map 任务完成后，它会生成一些中间文件，这些中间文件将会作为Reduce 任务的输入数据。
Reduce 任务的主要目标就是把前面若干个Map 的输出汇总到一起并输出。
按照以上基本的描述，其工作图如下。
从工作流程来讲，MapReduce对应的作业Job首先把输入的数据集切分为若干独立的数据块，并由Map组件以Task的方式并行处理。
处理结果经过排序后，依次输入给Reduce 组件，并且以Task的形式并行处理。
mapreduce的map阶段和reduce阶段MapReduce是一个用于大数据处理的计算模型和编程框架，最初由Google公司开发并推出。
MapReduce的基本思想是利用并行计算和分布式存储的特点，将大规模的数据集分成若干个小部分，通过Map 函数将这些小部分独立地处理成一系列键值对，并通过Reduce函数合并这些键值对，形成最终的结果。
在MapReduce中，每个Map任务和Reduce任务都是独立的计算单元，可以在分布式计算集群中并行地执行，从而以极高的性能和可伸缩性处理海量数据。
MapReduce的Map阶段和Reduce阶段是这个计算模型的核心，下面分别进行详细的解释。
1. Map阶段在MapReduce中，Map阶段的主要作用是将原始数据抽象为一系列键值对，并输出到Reduce阶段进行处理。
在具体的实现中，Map函数会将输入的数据映射到一组中间结果中，并将这些结果输出到Reduce函数中处理。
Map函数的输入和输出都是键值对形式的数据，其中输入通常是一条记录，输出通常是若干个键值对。
Map函数的实现通常是通过编写一个Map任务，并将这个任务分发到MapReduce框架的计算节点中执行。
在Map任务中，会对每条输入数据进行处理，将它分解成若干个键值对，并输出到Reduce函数进行处理。
在具体的实现中，Map任务的输入可以来源于分布式文件系统中的一个或多个数据块，输出可以保存到分布式文件系统中的一个或多个文件中。
2. Reduce阶段在MapReduce中，Reduce阶段的主要作用是将Map阶段输出的中间结果进行合并，并输出最终的计算结果。
在具体的实现中，Reduce 函数会接收Map阶段输出的一组键值对，并将它们分组处理成一组新的键值对，形成最终的输出结果。
Reduce函数的实现通常是通过编写一个Reduce任务，并将这个任务分发到MapReduce框架的计算节点中执行。
在Reduce任务中，会对所有输入数据进行汇总和合并处理，并输出最终的结果。
超大集群的简单数据处理收件人：发件人：崮山路上走9遍抄送：日期：2005-08-05关于：MapReduce: Simplified Data Processing on Large ClustersJeffrey Dean Sanjay Ghemawat*************** , *****************Google , Inc.摘要MapReduce是一个编程模式，它是与处理/产生海量数据集的实现相关。
用户指定一个map函数，通过这个map函数处理key/value（键/值）对，并且产生一系列的中间key/value对，并且使用reduce 函数来合并所有的具有相同key值的中间键值对中的值部分。
现实生活中的很多任务的实现都是基于这个模式的，正如本文稍后会讲述的那样。
使用这样的函数形式实现的程序可以自动分布到一个由普通机器组成的超大几群上并发执行。
run-time系统会解决输入数据的分布细节，跨越机器集群的程序执行调度，处理机器的失效，并且管理机器之间的通讯请求。
这样的模式允许程序员可以不需要有什么并发处理或者分布式系统的经验，就可以处理超大的分布式系统得资源。
我们的MapReduce系统的实现运行在一个由普通机器组成的大型集群上，并且有着很高的扩展性：一个典型的MapReduce计算处理通常分布到上千台机器上来处理上TB的数据。
程序员会发现这样的系统很容易使用：已经开发出来了上百个MapReduce程序，并且每天在Google的集群上有上千个MapReduce job正在执行。
1 介绍在过去的5年内，Google的创造者和其他人实现了上百个用于特别计算目的的程序来出来海量的原始数据，比如蠕虫文档，web请求log，等等，用于计算出不同的数据，比如降序索引，不同的图示展示的web文档，蠕虫采集的每个host的page数量摘要，给定日期内最常用的查询等等。
绝大部分计算都是概念上很简洁的。
MapReduce名词解释
MapReduce是一种用于并行处理大规模数据的编程模型和算法。
它采用了分布式计算的思想，将数据分成若干个小块，然后分配给不同的计算节点进行处理。
MapReduce包括两个主要阶段：Map（映射）和Reduce（归约）。
在Map阶段，输入的数据会被拆分成一个个的键值对，并由多个Map任务并行处理。
每个Map任务会对输入的键值对进行处理，并生成中间结果。
在Reduce阶段，相同键的中间结果会被分组到同一个Reduce任务，并按照一定的规则进行处理和合并。
最终，Reduce任务会输出最终结果。
例如，统计一篇文档中每个单词的出现次数，就可以使用MapReduce来实现。
MapReduce的优点包括：
•可扩展性强：能够处理大规模数据集，并充分利用分布式计算的优势。
•容错性好：蜗牛节点的存在，即使有计算节点发生故障，整个任务也不会失败。
•简化并行计算：开发者只需要关注数据的映射和归约逻辑，而不用担心细节。
MapReduce的应用场景包括：
•大规模数据处理和分析
•搜索引擎索引构建
•推荐系统
•日志分析
•图计算等。
一种新型的基于Hadoop框架的分布式并行FP-Growth算法张振友;孙燕;丁铁凡;刘鹏飞【摘要】针对传统FP-Growth算法在大规模数据环境下存在的挖掘效率低和内存溢出问题,在传统FP-Growth算法的基础上,提出一种新的并行FP-Growth算法,并在分布式计算框架Hadoop的MapReduce编程模式下实现并行化处理.实验数据表明,并行的FP-Growth算法与传统的FP-Growth算法相比,具有相同数据量下计算时间短,相同时间内处理数据量增大的优点,并在一定条件下解决了大数据挖掘的内存溢出问题.【期刊名称】《河北工业科技》【年(卷),期】2016(033)002【总页数】9页(P169-177)【关键词】并行处理;分布式;数据挖掘;闭频繁项集;Hadoop;FP-Growth【作者】张振友;孙燕;丁铁凡;刘鹏飞【作者单位】华北理工大学信息工程学院,河北唐山 063009;华北理工大学信息工程学院,河北唐山 063009;华北理工大学信息工程学院,河北唐山 063009;华北理工大学信息工程学院,河北唐山 063009【正文语种】中文【中图分类】TP311.1E－mail：youzhenadd＠163．com张振友，孙燕，丁铁凡，等．一种新型的基于Hadoop框架的分布式并行FP－Growth算法［J］．河北工业科技，2016，33（2）：169－177．ZHANG Zhenyou，SUN Yan，DING Tiefan，et al．A novel distributed parallel FP－Growth algorithm based on Hadoop framework［J］．Hebei Journal of Industrial Science and Technology，2016，33（2）：169－177．关联规则挖掘的基本算法主要有Apriori算法和FP－Growth算法。
mapreduce 原理MapReduce是一个分布式计算模型，旨在解决当今海量数据处理需求的问题。
由Google发明，并被广泛应用于大数据领域。
MapReduce原理涉及到两个阶段：Map和Reduce。
Map阶段是将数据分片并交给多个Map节点进行处理。
每个Map节点都将数据处理成键值对形式，并且根据初始的设定对指定的键和值进行分类。
其作用是把大量数据切割成若干小块，在分布式集群中并行运行，减少数据交换和通信的代价。
Reduce阶段是对Map节点进行的进一步操作，将Map节点输出的键值对按照特定的规则分组，然后将不同组中同一键值的数据进行合并。
Reduce过程是对中间结果的合并和汇总，将多个Map节点输出的结果合并成最终的结果。
MapReduce的原理在处理海量数据时具有很强的优势。
在Map阶段，数据被分散在集群中的多个节点上，不同节点的处理结果互不影响，处理速度快。
在Reduce阶段，数据的汇总和合并减少了数据间的传输，极大地降低了网络传输的代价。
此外，MapReduce还提供了一些高级API，可以使开发者更方便地进行数据处理。
例如，Hadoop就是一个使用MapReduce作为计算模型的分布式计算框架，提供了多个API，如HDFS、MapReduce和YARN。
总之，MapReduce的分布式计算原理为处理海量数据提供了很大的帮助。
它将数据切分成若干小块，使得不同节点可以并行处理，同时，其Reduce阶段还可以对数据进行合并和汇总。
这一特性在目前大数据处理业务中可以发挥巨大的优势，而且还可以使用MapReduce提供的API进行更加便捷的操作。
mapreduce模型中map函数与reduce函数MapReduce是一种分布式计算模型，它主要用于大规模数据的处理和分析。
在MapReduce模型中，Map函数和Reduce函数都是非常重要的组成部分，它们分别在数据预处理和结果合并阶段发挥重要作用。
Map函数一般用来对数据进行预处理。
当MapReduce模型读取数据时，Map函数会对每个数据块进行处理。
Map函数的输入是键-值对，输出也是键-值对。
Map函数可以将输入的键-值对映射为任意数量的键-值对输出。
例如，一个典型的Map函数可以将一个文档分解为单词，并将每个单词映射为一个键-值对。
在这个例子中，键是单词，值是1或者是出现次数。
Map函数的处理结果会被传递给Reduce函数进行处理。
Reduce函数则用来合并Map函数输出的结果。
当MapReduce模型读取完所有数据后，Reduce函数会对合并后的数据进行处理。
Reduce函数的输入是一个键和一个值构成的集合，输出也是一个键和一个值构成的集合。
Reduce函数会对所有输入的键-值对进行分组，并对每个键的一组值进行处理。
Reduce函数的处理结果会成为MapReduce模型的输出。
例如，一个典型的Reduce函数可以将相同单词的计数值相加。
在这个例子中，Reduce函数的输出是一个单词及其在文档中出现的总次数。
总的来说，MapReduce模型中的Map函数和Reduce函数分别负责数据预处理和结果合并。
Map函数可以将数据进行预处理，并将处理结果传递给Reduce函数进行处理。
Reduce函数则负责对Map函数输出的结果进行合并，并生成最终的结果。
MapReduce模型的优点在于其可以处理大规模数据，并且可以利用分布式计算资源进行并行化处理，这使得MapReduce模型广泛应用于大数据处理、搜索引擎、数据挖掘、机器学习等领域。
Google MapReduce中文版译者: alexMapReduce是一个编程模型，也是一个处理和生成超大数据集的算法模型的相关实现。
用户首先创建一个Map函数处理一个基于key/value pair的数据集合，输出中间的基于key/value pair的数据集合；然后再创建一个Reduce函数用来合并所有的具有相同中间key值的中间value值。
现实世界中有很多满足上述处理模型的例子，本论文将详细描述这个模型。
MapReduce架构的程序能够在大量的普通配置的计算机上实现并行化处理。
这个系统在运行时只关心：如何分割输入数据，在大量计算机组成的集群上的调度，集群中计算机的错误处理，管理集群中计算机之间必要的通信。
采用MapReduce架构可以使那些没有并行计算和分布式处理系统开发经验的程序员有效利用分布式系统的丰富资源。
我们的MapReduce实现运行在规模可以灵活调整的由普通机器组成的集群上：一个典型的MapReduce 计算往往由几千台机器组成、处理以TB计算的数据。
程序员发现这个系统非常好用：已经实现了数以百计的MapReduce程序，在Google的集群上，每天都有1000多个MapReduce程序在执行。
在过去的5年里，包括本文作者在内的Google的很多程序员，为了处理海量的原始数据，已经实现了数以百计的、专用的计算方法。
这些计算方法用来处理大量的原始数据，比如，文档抓取（类似网络爬虫的程序）、Web请求日志等等；也为了计算处理各种类型的衍生数据，比如倒排索引、Web文档的图结构的各种表示形势、每台主机上网络爬虫抓取的页面数量的汇总、每天被请求的最多的查询的集合等等。
大多数这样的数据处理运算在概念上很容易理解。
然而由于输入的数据量巨大，因此要想在可接受的时间内完成运算，只有将这些计算分布在成百上千的主机上。
如何处理并行计算、如何分发数据、如何处理错误？所有这些问题综合在一起，需要大量的代码处理，因此也使得原本简单的运算变得难以处理。
挖掘泛化序列模式的一种有效方法
邓明荣;叶福根;史烈;潘云鹤
【期刊名称】《浙江大学学报（理学版）》
【年(卷),期】2002(029)004
【摘要】针对有时间约束的泛化序列模式的挖掘问题,提出了一种有效的挖掘方法.与已有的算法相比,主要通过采取两种技术来提高效率,一是事先找出每个数据序列支持的序列模式,从而去除了时间因素,用一个快速算法来解决匹配问题;二是在数据序列重复较多时采用直接求交的方法.在此基础上提出了一个基于数据库划分的挖掘算法.
【总页数】8页(P415-422)
【作者】邓明荣;叶福根;史烈;潘云鹤
【作者单位】浙江大学,决策优化研究所,浙江,杭州,310028;浙江大学,决策优化研究所,浙江,杭州,310028;浙江大学,计算机系,浙江,杭州,310027;浙江大学,计算机系,浙江,杭州,310027
【正文语种】中文
【中图分类】TP311
【相关文献】
1.一种挖掘多维序列模式的有效方法 [J], 肖仁财;薛安荣
2.一种模糊序列模式挖掘的有效方法 [J], 陈晓
3.一种模糊序列模式挖掘的有效方法 [J], 陈晓
4.一种模糊序列模式挖掘的有效方法 [J], 陈晓
5.一种基于MDL的日志序列模式挖掘算法 [J], 杜诗晴;王鹏;汪卫
因版权原因，仅展示原文概要，查看原文内容请购买。
mapreduce编程模型及三个步骤MapReduce编程模型是一种用于处理大规模数据集的分布式计算模型，它由Google公司提出并应用于其搜索引擎等大数据处理场景中。
该模型将计算任务划分为Map和Reduce两个阶段，并通过横向扩展多个计算节点来实现高效的并行计算。
一、MapReduce编程模型的基本思想MapReduce编程模型的基本思想是将大规模数据集拆分成多个小块，分发到不同的计算节点上进行并行处理，最终将结果合并输出。
其中，每个计算节点都具备独立的计算能力和存储空间，可以在不影响其他节点的情况下进行本地计算和存储。
具体来说，MapReduce编程模型包含三个核心组件：输入数据集、Map函数和Reduce函数。
输入数据集是指需要处理的原始数据集合，可以是文本、图像、音频等各种形式的数据。
Map函数则负责对输入数据集中每个元素进行映射操作，并输出一个键值对（key-value pair）。
最后，Reduce函数则根据Map函数输出的键值对对结果进行聚合操作，并输出最终结果。
二、MapReduce编程模型的三个步骤1. Map阶段在Map阶段中，输入数据集被切分成多个小块，并分发到不同的计算节点上。
每个计算节点都会执行相同的Map函数，对输入数据集中的每个元素进行映射操作，并输出一个键值对。
其中，键值对中的键表示元素的标识符，值则表示元素经过映射后得到的结果。
Map函数通常由用户自行定义，其输入参数包括输入数据元素和对应的标识符。
用户需要根据具体的业务需求编写相应的Map函数，并保证其具备高效、可扩展、容错等特性。
2. Shuffle阶段在Map阶段完成后，所有计算节点会将自己所产生的键值对按照键进行排序，并将相同键的值聚合在一起。
这个过程被称为Shuffle（洗牌）操作。
Shuffle操作是MapReduce编程模型中非常重要的一个步骤，它决定了Reduce阶段所需要处理的数据量和负载均衡情况。
统计与大数据分析基础知识单选题100道及答案解析1. 统计学中，描述数据集中趋势的统计量不包括（）A. 均值B. 中位数C. 众数D. 方差答案：D解析：方差是描述数据离散程度的统计量，不是集中趋势的统计量。
2. 大数据的特点不包括（）A. 数据量大B. 数据类型多样C. 数据价值密度高D. 处理速度快答案：C解析：大数据的特点包括数据量大、数据类型多样、处理速度快，但其价值密度通常较低。
3. 以下哪种抽样方法不属于概率抽样（）A. 简单随机抽样B. 分层抽样C. 整群抽样D. 方便抽样答案：D解析：方便抽样是非概率抽样方法。
4. 一组数据：10, 20, 30, 40, 50，其均值为（）A. 25B. 30C. 35D. 40答案：C解析：均值= （10 + 20 + 30 + 40 + 50）÷5 = 305. 在数据分布中，四分位数间距反映了（）A. 数据的集中趋势B. 数据的离散程度C. 数据的偏态程度D. 数据的峰态程度答案：B解析：四分位数间距是上四分位数与下四分位数之差，反映了数据的离散程度。
6. 数据可视化的主要目的是（）A. 使数据更美观B. 节省存储空间C. 增强数据的理解和分析D. 提高数据处理速度答案：C解析：数据可视化有助于更直观地理解和分析数据。
7. 大数据处理框架Hadoop 的核心组件是（）A. HiveB. HBaseC. MapReduceD. Spark答案：C解析：MapReduce 是Hadoop 的核心计算框架。
8. 以下哪个不是数据分析的步骤（）A. 数据收集B. 数据存储C. 数据清洗D. 数据可视化答案：B解析：数据存储一般不属于数据分析的典型步骤。
9. 箱线图中，箱子的长度表示（）A. 数据的全距B. 数据的四分位数间距C. 数据的均值D. 数据的中位数答案：B解析：箱子的长度代表四分位数间距。
10. 相关系数的取值范围是（）A. [-1, 1]B. [0, 1]C. (-∞, +∞)D. [0, +∞)答案：A解析：相关系数的取值在-1 到 1 之间。
简述mapreduce的原理
MapReduce是一种用于处理大规模数据集的编程模型和算法。
其原理是将大数据集分成许多小的数据块，这些小数据块可以在不同的计算机上并行处理。
MapReduce模型由两个主要的操作组成：Map操作和Reduce操作。
在Map操作中，数据集被分成小的块，并由每个计算节点进行处理。
每个节点使用自己的本地数据来执行Map操作，并生成一系列键/值对。
这些键/值对被传送到Reduce操作中进行处理。
在Reduce操作中，Map操作生成的键/值对被汇总并按键进行排序。
然后，Reduce操作将相同键的所有值集合在一起，并将它们传递给一个处理函数，以生成最终的输出结果。
MapReduce的原理是利用分布式计算和并行处理来快速处理大量的数据。
它可以处理多种类型的数据，包括结构化数据、半结构化数据和非结构化数据。
同时，它还提供了高可靠性、高可扩展性和高并发性能，使其成为处理大数据集的一种有效方法。
- 1 -。
基于PrefixSpan的序列模式挖掘改进算法
汪林林;范军
【期刊名称】《计算机工程》
【年(卷),期】2009(035)023
【摘要】针对序列模式挖掘算法PrefixSpan在挖掘过程中需要构造大量投影数据库的不足,提出IPMSP算法,在递归挖掘过程中,通过检查序列数据库关于前缀的前缀,避免对同一频繁前缀模式构造重复投影数据库,同时舍弃对非频繁项的存储并在投影序列数小于最小支持度时停止扫描投影数据库,从而提高PrefixSpan算法的时空性能.实验结果证明,IPMSP算法在时间和空间性能上优于PrefixSpan算法.【总页数】4页(P56-58,61)
【作者】汪林林;范军
【作者单位】重庆邮电大学计算机科学与技术学院,重庆400065;重庆工学院,重庆400050;重庆邮电大学计算机科学与技术学院,重庆400065
【正文语种】中文
【中图分类】TP311
【相关文献】
1.基于PrefixSpan 序列模式挖掘的一种改进算法 [J], 吴楠;胡学钢
2.基于改进PrefixSpan的序列模式挖掘算法 [J], 公伟;刘培玉;贾娴
3.基于PrefixSpan序列模式挖掘的改进算法 [J], 王斌;黄晓芳;袁平
4.基于改进PrefixSpan算法的移动Web序列模式挖掘 [J], 王素凤;邓玫
5.基于改进PrefixSpan算法的移动Web序列模式挖掘 [J], 王素凤;邓玫
因版权原因，仅展示原文概要，查看原文内容请购买。
第３２卷第１１期 ２０１５年１１月 计算机应用研究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏ１．３２ Ｎ（１．１１
ＮＯＶ．２０ｌ５
基于ＭａｐＲｅｄｕｃｅ的序列模式挖掘算法 余啸 ，马传香Ｈ，李伟亮 ，金聪 （１．湖北大学计算机与信息工程学院，武汉４３００６２；２．华中师范大学计算机科学学院，武汉４３００６２）
摘 要：针对传统ＧＳＰ算法需要多次扫描数据库、Ｉ／Ｏ开销巨大的缺点，提出了一种基于ＭａｐＲｅｄｕｃｅ编程框架 的序列模式挖掘算法ＭＲ．ＧＳＰ（ＧＳＰ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＭａｐＲｅｄｕｃｅ）。ＭＲ—ＧＳＰ算法将原序列数据库划分为多个 子序列数据库并分发到多个Ｍａｐ节点，Ｍａｐ函数扫描存放在Ｍａｐ节点内存中的予序列数据库，产生局部序列模 式，Ｒｅｄｕｃｅ函数对所有局部序列模式合并，扫描原序列数据库，计算局部序列模式的支持度，得到最终的序列模 式。相比于传统ＧＳＰ算法，ＭＲ．ＧＳＰ算法只需扫描两次原始数据库即可得到所有序列模式。实验结果表明，ＭＲ— ＧＳＰ算法在对大数据集进行序列模式挖掘时，可充分利用云计算技术的优势，提高挖掘效率． 关键词：数据挖掘；ＧＳＰ算法；序列模式；ＭａｐＲｅｄｕｃｅ；子序列数据库 中图分类号：ＴＰ１８１；ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１５）１１—３３１２—０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１５．１ １．０２５
Ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＭａｐＲｅｄｕｃｅ ｐｒｏｇｒａｍｍｉｎｇ ｆｒａｍｅｗｏｒｋ Ｙｕ Ｘｉａｏ ，Ｍａ Ｃｈｕａｎｘｉａｎｇ”，Ｌｉ Ｗｅｉｌｉａｎｇ ，Ｊｉｎ Ｃｏｎｇ。
（１．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｕｂｅｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ ４３００６２，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｃｅｎｔｒａｌ Ｃｈｉｎａ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ ４３００６２，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｆｏｒ ｔｈｅ ｄｉｓａｄｖａｎｔａｇｅｓ ｔｈａｔ ｔｒａｄｉｔｉｏｎａｌ ＧＳＰ ａｌｇｏｒｉｔｈｍ ｎｅｅｄ ｔｏ ｓｃａｎ ｔｈｅ ｄａｔａｂａｓｅ ｒｅｐｅａｔｅｄｌｙ ａｎｄ ｔｈｅ Ｉ／Ｏ ｏｖｅｒｈｅａｄ ｉｓ ｈｕｇｅ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ＭＲ－ＧＳＰ（ＧＳＰ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＭａｐＲｅｄｕｃｅ）ｂａｓｅｄ ｏｎ Ｍａｐ— Ｒｅｄｕｃｅ ｐｒｏｇｒａｍｍｉｎｇ ｆｒａｍｅｗｏｒｋ．Ｔｈｅ ＭＲ・ＧＳＰ ａｌｇｏｒｉｔｈｍ ｄｉｖｉｄｅｄ ｔｈｅ ｏｒｉｇｉｎａｌ ｓｅｑｕｅｎｃｅ ｄａｔａｂａｓｅ ｉｎｔｏ ｓｏｍｅ ｓｕｂ—ｓｅｑｕｅｎｃｅ ｄａｔａ— ｂａｓｅｓ ａｎｄ ｄｉｓｔｒｉｂｕｔｅｄ ｔｈｅｍ ｔｏ Ｍａｐ ｗｏｒｋｅｒｓ，Ｍａｐ ｆｕｎｃｔｉｏｎ ｓｃａｎｎｅｄ ｓｕｂ・ｓｅｑｕｅｎｃｅ ｄａｔａｂａｓｅｓ ｓｔｏｒｅｄ ｉｎ ｍｅｍｏｒｙ ｔｏ ｇｅｎｅｒａｔｅ ｐａｒｔｉａｌ ｓｅｑｕｅｎｃｅ ｐａｔｔｅｒｎｓ．Ｒｅｄｕｃｅ ｆｕｎｃｔｉｏｎ ｍｅｒｇｅｄ ａｌｌ ｐａｒｔｉａｌ ｓｅｑｕｅｎｃｅ ｐａｔｔｅｒｎｓ ａｎｄ ｓｃａｎｎｅｄ ｔｈｅ ｏｒｉｇｉｎａｌ ｓｅｑｕｅｎｃｅ ｄａｔａｂａｓｅ ｔｏ ｅａｌｃｕ— ｌａｔｅ ｔｈｅ ｓｕｐｐｏｒｔ ｏｆ ｐａｒｔｉａｌ ｓｅｑｕｅｎｃｅ ｐａｔｔｅｒｎｓ ａｎｄ ｇａｉｎｅｄ ｔｈｅ ｆｉｎａｌ ｓｅｑｕｅｎｃｅ ｐａｔｔｅｒｎｓ．Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｒａｄｉｔｉｏｎａｌ ＧＳＰ ａｌｇｏｒｉｔｈｍ， ｔｈｅ ＭＲ—ＧＳＰ ａｌｇｏｒｉｔｈｍ ｇａｉｎｅｄ ａｌｌ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｓ ｂｙ ｓｃａｎｎｉｎｇ ｔｈｅ ｏｒｉｇｉｎａｌ ｄａｔａｂａｓｅ ｊｕｓｔ ｔｗｉｃｅ．Ｅｘｐｅｒｉｎｌｅｎｔａｌ ｒｅｓｕｈｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ＭＲ—ＧＳＰ ａｌｇｏｒｉｔｈｍ ｃａｎ ｔａｋｅ ａｄｖａｎｔａｇｅｓ ｏｆ ｃｌｏｕｄ ｃｏｍｐｕｔｉｎｇ ｔｅｃｈｎｏｌｏｇｙ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ ｉｎ ｂｉｇ ｄａｔａ． Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｍｉｎｉｎｇ；ＧＳＰ ａｌｇｏｒｉｔｈｍ；ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ；ＭａｐＲｅｄａｃｅ；ｓｕｂ—ｓｅｑｕｅｎｃｅ ｄａｔａｂａｓｅ
序列模式挖掘最早由Ａｇｒａｗａｌ等人…于１９９５年提出。序 列模式挖掘就是挖掘序列数据库中频繁出现的有序事件或子 序列。序列模式挖掘在客户购买行为模式预测、Ｗｅｂ访问模 式预测、疾病诊断、网络入侵检测等领域都有着广泛的应用。 目前，关于序列模式挖掘算法的研究已有很多，例如，文献［２］ 提出了采用冗余候选模式的剪除策略和哈希树来实现候选模 式快速访存的ＧＳＰ算法；文献［３］提出了基于垂直数据表示的 ＳＰＡＤＥ算法；文献［４］提出了基于投影数据库的ＰｒｅｆｉｘＳｐａｎ算 法；文献［５］提出了基于位置信息的序列模式挖掘算法即ＰＶＳ 算法；文献［６］提出了一种多时间间隔序列模式挖掘算法；文 献［７］提出了一种时序关系下的闭合序列模式挖掘算法，这些 传统的串行化算法在处理海量数据和高维数据时运算能力远 远不能满足人们的要求。针对这一问题，国内外学者相继提出 了各种分布式序列模式挖掘算法。例如，文献［８］提出了基于 树投影技术的两种不同的并行化算法来解决分布内存并行计 算机的序列模式发现问题；文献［９］提出了通过语法序列树减 少数据传输量的ＤＭＧＳＰ算法；文献［１０］提出了快速挖掘全局 最大频繁项目集的ＦＭＧＳＰ算法；文献［１１］提出了一种动态与 静态任务分配机制相结合的基于多核的并行序列模式挖掘算‘ 法，但这些并行化算法实现相对复杂且适应性较差。云计算的 出现为并行化算法的实现提供了新的方式。通过云计算的大 规模并行计算，可以解决海量数据挖掘的效率问题。为此，本 文提出了基于ＭａｐＲｅｄｕｃｅ编程框架的ＭＲ—ＧＳＰ算法。
１ ＭａｐＲｅｄｕｃｅ编程框架与Ｈａｄｏｏｐ云计算平台 ＭａｐＲｅｄｕｃｅ １２）是一个用于大规模数据处理的并行编程 架。用户只需编写两个称做Ｍａｐ和Ｒｅｄｕｃｅ的函数即可，系统 能够管理Ｍａｐ或Ｒｅｄｕｃｅ并行任务的执行以及任务之间的协 调，并且能够处理上述某个任务失败的情况，同时能够保障对 硬件故障的容错性 。ＭａｐＲｅｄｕｃｅ把数据映射为多个（ｋｅｙ， ｖａｌｕｅ）对，通过Ｍａｐ函数将（ｋｅｙ，ｖａｌｕｅ）对进行转换，然后通过 Ｒｅｄｕｃｅ函数对ｋｅｙ进行聚合，实现数据操作的目的。
收稿日期：２０１４—０８．１９；修回日期：２０１４．１０—０９ 基金项目：湖北省自然科学基金资助项目（２０１１ＣＤＢ０７２）；国家社会科学基金资助项习 （１３ＢＴＱｏ５０） 作者简介：余啸（１９９４一），男，湖北汉川人，本科，主要研究方向为数据挖掘、云计算；马传香（１９７１一），女（通信作者），湖４Ｌ＃＇１州人，教授，博士，主
要研究方向为数据挖掘、云计算（ｍｘｃ８３８＠ｈｕｂｕ．ｃｏｒｎ）；李伟亮（１９８８－），湖北武汉人，硕士研究生，主要研究方向为数据挖掘、大数据；金聪（１９６０一），女， 上海人，教授，博士，主要研究方向为数字水印、图像处理、信息安全． 第１１期 余啸，等：基于ＭａｐＲｅｄｕｃｅ的序列模式挖掘算法 ・３３１３・ Ｈａｄｏｏｐ是由Ａｐａｃｈｅ基金会开发的满足可靠性、可扩展 性、分布式计算的开源软件项目ｍ ，是ＭａｐＲｅｄｕｃｅ的实现。由 于Ｈａｄｏｏｐ分布式处理和并行计算模式有效地解决了对海量数 据的存储和计算，Ｈａｄｏｏｐ得到了广泛的应用。用户可以轻松 地在Ｈａｄｏｏｐ上开发和运行处理海量数据的应用程序。 ２相关定义 定义１非空集合，＝｛ｉ ，ｋ＝１，２，…，ｎ｝称为项集，其中ｉ 称为项。 定义２序列是项集的有序排列，序列Ｓ可以表示成Ｓ＝ （， ，，２，…， ）， ｃ，。序列包含项的个数称为序列的长度。长 度为￡的序列记为 一序列。 定义３序列数据库由＜Ｓｉｄ，ｓ）组成，其中Ｓｉｄ表示序列 号，Ｓ表示序列。 构成如表１所示的一个序列数据库。 表ｌ序列数据库 ｓｉｄ Ｓ Ｓ．ｄ Ｓ Ｓｌ （｛ａ｝｛ｅ｝｛ｂ｝｛ｄ｝） ５７ （｛ａ｝｛ｂ｝｛ｃ ｄ｝｛ｄ｝） ｓ２ （｛ａ｝｛ｂ｝｛ｄ｝｛ｆ｝） Ｓｓ （｛ａ｝｛ｂ｝｛ｄ｝） （｛ａ｝｛ｇ｝｛ｄ ｈ｝｛ｆ｝） ｓ９ （｛ｄ｝｛ｅｆ｝｛ｇ｝） ｓ４ （｛ａ｝｛ｂ｝｛ｄ｝｛ｆ｝） ｓｌ０ （｛ａ｝｛ｂ｝｛ｃ｝｛ｄ｝） ｓ５ （｛ｎ｝｛ｂ｝｛ｄ｝｛ｇ ｈｆ） Ｓｌｌ （｛ｇ｝｛ｈ｝｛ｅｆ｝） ｓ６ （｛ｂ｝｛ｄ｝｛ｅ ｈ｝） Ｓｌ２ （｛ａ｝｛ｂ｝｛ｃ｝｛ｄ｝） 定义４设序列Ｏｌ＝（ａ ，ａ２，…，ａ ），序列卢＝（ｂ。，ｂ：，…， ｂｍ），ａ ＣＩ，ｂ ｃ，。如果存在整数１≤ １＜ ＜…＜ ≤ｍ，使得 ｎ ｃｂｉｌ，０２ ｃ６ ，…，口 ｃｂｊ．，则称序列Ｏｔ为序列卢的子序列，又 称序列口包含序列 。 定义５ 序列ｓ在序列数据库的支持度计数为序列数据 库中包含Ｓ的序列个数。序列Ｓ在序列数据库的支持度为包 含ｓ的序列在序列数据库中所占的百分比，记为Ｓｕｐｐｏ￣（Ｓ）。 给定最小支持度 ，如果序列Ｓ在序列数据库中的支持度不低 于 ，则称序列Ｓ为序列模式。 ３ ＭＲ．ＧＳＰ算法 ● 传统ＧＳＰ算法的基本思想是：首先扫描序列数据库得到 １一序列模式厶，然后由频繁 一序列模式 产生候选ｋ＋１一序列 Ｃ㈨，再次扫描原序列数据库，计算每个候选序列的支持度，产 生频繁ｋ＋１序列模式 ＋。，之后重复操作，直至没有新的候选 序列产生。扫描数据库的次数与序列模式的最大长度相同。 其中，产生候选序列模式主要分两步： ａ）连接。如果去掉序列模式ｓ 的第一个项目与去掉序列 模式ｓ 的最后一个项目所得到的序列相同，则可以将ｓ 与ｓ： 进行连接，即将ｓ：的最后一个项目添加到ｓ 中。 ｂ）修剪。若某候选序列模式的某个子序列不是序列模 式，则此候选序列模式不可能是序列模式，将它从候选序列模 式中删除。 令Ⅳ表示序列数据库序列数， 表示最大序列长度，那么 第一次扫描数据库时间为０（Ｔ Ｘ Ｎ）。在接下来的每一步中 连接步时间开销为０（Ｉ Ｉ×ｌ Ｉ），遍历序列数据库对候选序 列模式计数时间开销为０（Ｎ×Ｉ Ｃ Ｉ），修剪步时间开销为 Ｏ（ｆＣ １）。在最坏的情况下，ＧＳＰ算法的时间复杂度为０（Ｔ Ｘ Ⅳ）＋Ｏ（∑ｌ ｌ Ｘ ｌ己 ｌ＋Ｎ Ｘ ｌ Ｃ Ｉ＋ｌ Ｃ １）。 由以上分析可知，该算法时间开销主要集中在２一序列模 式的生成阶段和数据库的多次扫描阶段。因此，本文提出一种 基于ＭａｐＲｅｄｕｃｅ的ＭＲ—ＧＳＰ算法，通过将原序列数据库进行合 理分解划分到不同的Ｍａｐ站点上，减少了对原序列数据库的 扫描次数，改善了算法性能。ＭＲ—ＧＳＰ算法的执行流程如图１ 所示。具体执；行步骤如下： ａ）将原序列数据库平均划分为ｎ个不相交的子序列数据 库。为了在每次对候选序列模式计数时不用扫描原序列数据 库，减少Ｉ／Ｏ开销，应使每个子序列数据库都能放人内存。 ｂ）由Ｍａｓｔｅｒ节点将ｎ个子序列数据库分派给不同的Ｍａｐ 工作节点，每个节点执行传统ＧＳＰ算法，按照设定的最小支持 度，扫描存放在Ｍａｐ工作节点内存中的子序列数据库，计算出 局部序列模式。 Ｃ）将Ｍａｐ过程得到的局部序列模式传递给Ｒｅｄｕｃｅ工作 节点，归并处理得到全局候选序列模式。再一次扫描原序列数 据库，找出满足不小于系统设定的最小支持度的序列模式。
