论文部分内容阅读
摘要：随着信息技术以及互联网技术的快速发展，数据种类和数量呈现出了膨胀性增长的态势，善于使用大规模的数据，并且能够充分挖掘数据单种的商业信息，能够帮助企业快速做出战略决策，促进企业改革创新，为企业提供全新的商业增长点。使得Web数据挖掘工作的研究成為热点。大数据涌现对于传统简单数据挖掘算法提出了更高的要求，基于Hadoop平台的Map/Reduce模型也在不断改进。作为当前最流向的分布式计算模型Map/Reduce从众多的模型当中脱颖而出，并高速发展。该文主要研究了结合Map/Reduce的模型基础上利用K-mean算法实现挖掘数据的快速高校、占用CPU更少。
关键词：数据挖掘；Map/Reduce；Hadoop云计算平台
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2018）23-0028-03
尽管数据挖掘相关的理论研究工作逐渐成熟，可是随着数据规模不断增大的情况下，人们对于快速高效处理数据提出了全新的要求。这几年，互联网的普及率居高不下，互联网网页规模每年保持在78.6%的增长率，并达到了几百亿到上千亿的规模。此外，诸如Facebook[1-4]、微博等社交网络平台的用户数量也在不断攀升。而真实世界当中数据规模日益膨胀也带动了互联网数据的增长。GB、TB、PB级别的数据规模对于互联网数据而言已经是司空见惯的事情，单台机器明显无法出现这种数量级别的数据。从商业领域看，是否能够快速而高效的处理大规模数据已经成为决定企业能够实现信息化的决定因素。假如错过了这个机会，在当前信息技术快速发展的时代背景下，企业发展将无法跟上时代的步伐，最终会被淘汰。当前如何快速高效的处理大规模的数据，逐渐成为一个全新的挑战。
1 Map/Reduce计算过程
第一，存在多个Map任务，所有任务的输入其实都是分布式文件系统当中的某一个以及多个文件块。Map任务能够把文件块转变成为键值对序列。用户通过Map函数代码能够自行编写输入数据形成键值对的形式[5]。
第二，主控制器可以从Map任务当中获取键值对，并且按照大小顺序对他们进行排序。这部分键会被分配到Reduce任务当中，因此键值相同的键值对通常会被分配到相同的Reduce任务当中。
第三，Reduce任务每一次都会对某个键产生作用，并且通过某种方式将和该键存在一定关联性的值组合在一起。用户能够通过Reduce函数代码来自行决定组合的形式。
2 Hadoop云计算平台
Hadoop可以对大量的数据做分布式处理，是Map/Reduce的Java实现。用户不需要掌握分布式底层细节，就能够开发分布式程序。Hadoop云计算平台具有以下优点[6-7]。首先，Hadoop一般运行在通过普通商用计算机所构成的大型集群上，例如淘宝集群、百度云计算集群。其次，Hadoop有着比较高的健壮性。在架构设计的过程中，就已经架设了平台当中的研究会失去效果并且采取了一定的保护措施，所以，Hadoop对于节点实效的问题能够从容的应对。再次，能哦故利用Hadoop集群节点的个数有效提升计算能力以及存储能力。最后，用户能够轻易地编写出Hadoop平台上的分布式程序[8-12]。
3 基于Map/Reduce的改进选择算法在Web数据挖掘中的应用
3.1 Map/Reduce算法模式
公式当中的P（n）为临界函数，n=1，2，3…，函数作用主要是对次数进行统一调度，可能够保持服务点数目的有效连接。
因为文件信息数量较大，使用直接访问的形式会降低访问效率，导致服务器负荷严重，所以使用二进制序列的形式来进行运算处理，能够节省更多的内存空间。P（n）的获取方法如下所示。
dq指的是服务店q在第n次调用过程中存在一个长度是m的二进制序列，在这个序列当中最小值的位置是dq（a），并且初始值是0。
从上述模型当中能够看出，在每次转换以及调用数据的时候，都会刷新一次服务点，刷新以后的服务点包括了很多从服务点当中产生的比当前调用次数n要小的服务点信息。数据挖掘的时候，使用两步循环Map/Reduce模型算法进行描述。其步骤为：
然后的步骤就是把第二步利用Reduce函数整合挖掘数据信息，分类以后的数据信息，将这些数据信息交给Map函数对其进行最终的输入。服务器利用Reduce把整合以后的数据信息输出，获得结果。
3.2 实验过程以及结果分析
本实验环境主要表现为，在服务上安装有vSphere虚拟化软件，一共创建有10个虚拟机，硬件条件如下表所示。
其中一台虚拟机作为实验主服务器，专门用来存储网络日志、挖掘相关数据，对数据信息分布以及运行情况进行分析等。
4 基于Map/Reduce的改进选择算法
4.1 K-means算法
K-means算法主要是将K作为主要参数，将数据集内部的N个数据源形成K个子集，能够保证子集内部的数据元组合具备一定相似度，并且子集之间数据元组存在着较低的相似度。相似度是按照子集内部的对象平均值计算而来的。K-Means算法具体流程为：在全体数据集当中选择K个数据元祖当作是初始聚类中心，数据集内部剩下的数据元组，需要计算其和聚类中心之间的相似度，依次把他们划归到与之相似的聚类当中，然后重新计算每个归并以后所取得新数据元组的聚类中心，反复进行这个过程，一直到预先指派的测度函数能够收敛到阈值为止。
4.2 K-Means算法Map/Reduce化
本次研究的重点在于，在K-Means算法基础上，分析其Map/Reduce化以后K-Means算法的具体方案，并且研究云计算化后算法性能，具体执行步骤如下所示： 1） 选择k个初始聚类中心，比如cp[0]=D[0]，cp[k-1]=D[k-1]，此后将这些聚类中心当中的初始聚类数据全部复制到Original Cluster[]当中，并且把Original Cluster[]做分块处理，按照计算节点集群的结果，把Original Cluster[]分配到每个节点当中。
2） Map：对于D[0]……D[n]数据，需要计算出其cp[0]……cp[n-1]的距离，距离最近的标记为c[i]，其总数能够用Ci进行表示，与此同时在Map/Reduce框架下，将键值对应i以及D[k]。
3） Reduce：因为i本身是Map/Reduce框架当中的键值所对的Key，这确保了同一个Key所有D[k]都能够分配到相同的Reduce进程当中，根据此Reduce进程就能够计算聚类中心，并且把该聚类中心放入Destination Cluster[]当中。
4） 对比Original Cluster[]以及Destination Cluster[]处理方式的不同，假如二者变化要比预先给定的值小，那么聚类完成，反之，需要将Destination Cluster[]放入到Original Cluster[]，并继续上述操作。
能够发现，K-mean算法在Map/Reduce化改进过程相对简单，其原因在于Map/Reduce框架本身就是一致，开发人员所需要做的就是剥离出可供Map/Reduce的内容，并构造相应的键值对，其他的监控、调度、通讯任务则全部可以交给Map/Reduce框架来实现。
4.3 实验结果
本文数据集选取了QQ音乐当中的某个电台媒体库，数据集当中汇集了广告、歌曲、片花等110万数据记录，与此同时还包含了600万条听众点播，2000万条网络互动消息。
第一组实验当中使用了网络互动消息记录当中所获取的1000万条数据，内部配置DataNode上Reduce节点数属1，Map节点数为1，2，5，10，100.K-means算法最终耗时为612s、466s、307s、163s、199s。由此可见Map节点在10的时候，其具有最高的运行效率。
第二组实验当中采用了全部数据集，DataNode上面的Reduce节点数是1，Map节点数是10，分别是用了100万、500万、1000万、1500万、1800万、2000万数据量运算。K-Means算法耗费的时间分别是66s，169s，288s，352s，429s，475s。由此可见，在Map节点数保持不变的情况下，随着数据量不断增大，耗费的时间也随之增加，二者之间呈现出正比例的关系。
分别测试出数据集在1、3、5、7、9个节点集群当中K-means并行计算的时间和比率，可以计算出其加速比S1、S3、S5、S7、S9，最终的结果如图3所示。伴随着数据量的持续增加，节点数也会相应地增加，从图中能够发现，处理同一个数据集的加速比是慢慢增大的，换言之云数据挖掘过程中的K-means算法具备了更大的计算能力。
5 结束语
当前，企业逐渐开始关注互联网数据的挖掘工作，希望以此搜集到更多的商业价值。可是伴随着数据复杂程度不断加大，数据量持续增多，高纬度以及大规模的数据处理所消耗的时间与精力是很多企业难以承受的，并且开发出可以处理这些数据的框架难度逐渐提升，具备高可靠性以及高容错的云计算平台可以很好地解决这方面的问题。使用Map/Reduce算法对数据进行整合，可以有效地缩短Web数据挖掘时间，有效提升效率，从而最大显著提升扩展性、可用性以及协同性的特征。
参考文献：
[1] Shim K. MapReduce Algorithms for Big Data Analysis[C]// International Workshop on Databases in Networked Information Systems. Springer Berlin Heidelberg， 2013：44-48.
[2] Plimpton S J， Devine K D. MapReduce in MPI for Large-scale graph algorithms[J].Parallel Computing， 2011，37（9）：610-632.
[3] 方少卿，周剑，张明新.基于Map/Reduce的改进选择算法在云计算的Web数据挖掘中的研究[J].计算机应用研究，2013，30（2）：377-379.
[4] 范苗苗，符琳，杨罗，等.基于Map Reduce的云数据挖掘模型的设计与实现[J].信息通信，2017（3）：141-142.
[5] 张家瑞. 基于MapReduce的数据挖掘平台设计与实现[J].网络安全技术与应用，2014（11）：49.
[6] 王勃，徐靜.基于云计算的Web数据挖掘Map/Reduce算法的研究[J].计算机与数字工程， 2014（7）：1157-1159.
[7] 李悦，高晶，雷鸣.基于云计算技术的Web数据挖掘的算法研究[J].科技资讯，2014，12（18）：17.
[8] 李彬，刘莉莉.基于MapReduce的Web日志挖掘[J].计算机工程与应用，2012， 48（22）：95-98.
[9] ZHU Xiang， 朱湘， JIN Song-chang，等.一种基于Hadoop平台的海量Web数据挖掘系统研究与实现[C]//.中国通信学会学术年会，2012.
[10] 盛昀瑶，陈爱民.基于MapReduce的Web日志挖掘算法研究[J].现代计算机，2017（16）：14-18.
[11] 程苗.基于云计算的Web数据挖掘[J].计算机科学， 2011， 38（b10）：146-149.
[12] 刘骞，陈明.基于改进的Map/Reduce及模式空间划分的数据挖掘[J].微电子学与计算机，2011， 28（8）：140-142.
【通联编辑：梁书】
关键词：数据挖掘；Map/Reduce；Hadoop云计算平台
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2018）23-0028-03
尽管数据挖掘相关的理论研究工作逐渐成熟，可是随着数据规模不断增大的情况下，人们对于快速高效处理数据提出了全新的要求。这几年，互联网的普及率居高不下，互联网网页规模每年保持在78.6%的增长率，并达到了几百亿到上千亿的规模。此外，诸如Facebook[1-4]、微博等社交网络平台的用户数量也在不断攀升。而真实世界当中数据规模日益膨胀也带动了互联网数据的增长。GB、TB、PB级别的数据规模对于互联网数据而言已经是司空见惯的事情，单台机器明显无法出现这种数量级别的数据。从商业领域看，是否能够快速而高效的处理大规模数据已经成为决定企业能够实现信息化的决定因素。假如错过了这个机会，在当前信息技术快速发展的时代背景下，企业发展将无法跟上时代的步伐，最终会被淘汰。当前如何快速高效的处理大规模的数据，逐渐成为一个全新的挑战。
1 Map/Reduce计算过程
第一，存在多个Map任务，所有任务的输入其实都是分布式文件系统当中的某一个以及多个文件块。Map任务能够把文件块转变成为键值对序列。用户通过Map函数代码能够自行编写输入数据形成键值对的形式[5]。
第二，主控制器可以从Map任务当中获取键值对，并且按照大小顺序对他们进行排序。这部分键会被分配到Reduce任务当中，因此键值相同的键值对通常会被分配到相同的Reduce任务当中。
第三，Reduce任务每一次都会对某个键产生作用，并且通过某种方式将和该键存在一定关联性的值组合在一起。用户能够通过Reduce函数代码来自行决定组合的形式。
2 Hadoop云计算平台
Hadoop可以对大量的数据做分布式处理，是Map/Reduce的Java实现。用户不需要掌握分布式底层细节，就能够开发分布式程序。Hadoop云计算平台具有以下优点[6-7]。首先，Hadoop一般运行在通过普通商用计算机所构成的大型集群上，例如淘宝集群、百度云计算集群。其次，Hadoop有着比较高的健壮性。在架构设计的过程中，就已经架设了平台当中的研究会失去效果并且采取了一定的保护措施，所以，Hadoop对于节点实效的问题能够从容的应对。再次，能哦故利用Hadoop集群节点的个数有效提升计算能力以及存储能力。最后，用户能够轻易地编写出Hadoop平台上的分布式程序[8-12]。
3 基于Map/Reduce的改进选择算法在Web数据挖掘中的应用
3.1 Map/Reduce算法模式
公式当中的P（n）为临界函数，n=1，2，3…，函数作用主要是对次数进行统一调度，可能够保持服务点数目的有效连接。
因为文件信息数量较大，使用直接访问的形式会降低访问效率，导致服务器负荷严重，所以使用二进制序列的形式来进行运算处理，能够节省更多的内存空间。P（n）的获取方法如下所示。
dq指的是服务店q在第n次调用过程中存在一个长度是m的二进制序列，在这个序列当中最小值的位置是dq（a），并且初始值是0。
从上述模型当中能够看出，在每次转换以及调用数据的时候，都会刷新一次服务点，刷新以后的服务点包括了很多从服务点当中产生的比当前调用次数n要小的服务点信息。数据挖掘的时候，使用两步循环Map/Reduce模型算法进行描述。其步骤为：
然后的步骤就是把第二步利用Reduce函数整合挖掘数据信息，分类以后的数据信息，将这些数据信息交给Map函数对其进行最终的输入。服务器利用Reduce把整合以后的数据信息输出，获得结果。
3.2 实验过程以及结果分析
本实验环境主要表现为，在服务上安装有vSphere虚拟化软件，一共创建有10个虚拟机，硬件条件如下表所示。
其中一台虚拟机作为实验主服务器，专门用来存储网络日志、挖掘相关数据，对数据信息分布以及运行情况进行分析等。
4 基于Map/Reduce的改进选择算法
4.1 K-means算法
K-means算法主要是将K作为主要参数，将数据集内部的N个数据源形成K个子集，能够保证子集内部的数据元组合具备一定相似度，并且子集之间数据元组存在着较低的相似度。相似度是按照子集内部的对象平均值计算而来的。K-Means算法具体流程为：在全体数据集当中选择K个数据元祖当作是初始聚类中心，数据集内部剩下的数据元组，需要计算其和聚类中心之间的相似度，依次把他们划归到与之相似的聚类当中，然后重新计算每个归并以后所取得新数据元组的聚类中心，反复进行这个过程，一直到预先指派的测度函数能够收敛到阈值为止。
4.2 K-Means算法Map/Reduce化
本次研究的重点在于，在K-Means算法基础上，分析其Map/Reduce化以后K-Means算法的具体方案，并且研究云计算化后算法性能，具体执行步骤如下所示： 1） 选择k个初始聚类中心，比如cp[0]=D[0]，cp[k-1]=D[k-1]，此后将这些聚类中心当中的初始聚类数据全部复制到Original Cluster[]当中，并且把Original Cluster[]做分块处理，按照计算节点集群的结果，把Original Cluster[]分配到每个节点当中。
2） Map：对于D[0]……D[n]数据，需要计算出其cp[0]……cp[n-1]的距离，距离最近的标记为c[i]，其总数能够用Ci进行表示，与此同时在Map/Reduce框架下，将键值对应i以及D[k]。
3） Reduce：因为i本身是Map/Reduce框架当中的键值所对的Key，这确保了同一个Key所有D[k]都能够分配到相同的Reduce进程当中，根据此Reduce进程就能够计算聚类中心，并且把该聚类中心放入Destination Cluster[]当中。
4） 对比Original Cluster[]以及Destination Cluster[]处理方式的不同，假如二者变化要比预先给定的值小，那么聚类完成，反之，需要将Destination Cluster[]放入到Original Cluster[]，并继续上述操作。
能够发现，K-mean算法在Map/Reduce化改进过程相对简单，其原因在于Map/Reduce框架本身就是一致，开发人员所需要做的就是剥离出可供Map/Reduce的内容，并构造相应的键值对，其他的监控、调度、通讯任务则全部可以交给Map/Reduce框架来实现。
4.3 实验结果
本文数据集选取了QQ音乐当中的某个电台媒体库，数据集当中汇集了广告、歌曲、片花等110万数据记录，与此同时还包含了600万条听众点播，2000万条网络互动消息。
第一组实验当中使用了网络互动消息记录当中所获取的1000万条数据，内部配置DataNode上Reduce节点数属1，Map节点数为1，2，5，10，100.K-means算法最终耗时为612s、466s、307s、163s、199s。由此可见Map节点在10的时候，其具有最高的运行效率。
第二组实验当中采用了全部数据集，DataNode上面的Reduce节点数是1，Map节点数是10，分别是用了100万、500万、1000万、1500万、1800万、2000万数据量运算。K-Means算法耗费的时间分别是66s，169s，288s，352s，429s，475s。由此可见，在Map节点数保持不变的情况下，随着数据量不断增大，耗费的时间也随之增加，二者之间呈现出正比例的关系。
分别测试出数据集在1、3、5、7、9个节点集群当中K-means并行计算的时间和比率，可以计算出其加速比S1、S3、S5、S7、S9，最终的结果如图3所示。伴随着数据量的持续增加，节点数也会相应地增加，从图中能够发现，处理同一个数据集的加速比是慢慢增大的，换言之云数据挖掘过程中的K-means算法具备了更大的计算能力。
5 结束语
当前，企业逐渐开始关注互联网数据的挖掘工作，希望以此搜集到更多的商业价值。可是伴随着数据复杂程度不断加大，数据量持续增多，高纬度以及大规模的数据处理所消耗的时间与精力是很多企业难以承受的，并且开发出可以处理这些数据的框架难度逐渐提升，具备高可靠性以及高容错的云计算平台可以很好地解决这方面的问题。使用Map/Reduce算法对数据进行整合，可以有效地缩短Web数据挖掘时间，有效提升效率，从而最大显著提升扩展性、可用性以及协同性的特征。
参考文献：
[1] Shim K. MapReduce Algorithms for Big Data Analysis[C]// International Workshop on Databases in Networked Information Systems. Springer Berlin Heidelberg， 2013：44-48.
[2] Plimpton S J， Devine K D. MapReduce in MPI for Large-scale graph algorithms[J].Parallel Computing， 2011，37（9）：610-632.
[3] 方少卿，周剑，张明新.基于Map/Reduce的改进选择算法在云计算的Web数据挖掘中的研究[J].计算机应用研究，2013，30（2）：377-379.
[4] 范苗苗，符琳，杨罗，等.基于Map Reduce的云数据挖掘模型的设计与实现[J].信息通信，2017（3）：141-142.
[5] 张家瑞. 基于MapReduce的数据挖掘平台设计与实现[J].网络安全技术与应用，2014（11）：49.
[6] 王勃，徐靜.基于云计算的Web数据挖掘Map/Reduce算法的研究[J].计算机与数字工程， 2014（7）：1157-1159.
[7] 李悦，高晶，雷鸣.基于云计算技术的Web数据挖掘的算法研究[J].科技资讯，2014，12（18）：17.
[8] 李彬，刘莉莉.基于MapReduce的Web日志挖掘[J].计算机工程与应用，2012， 48（22）：95-98.
[9] ZHU Xiang， 朱湘， JIN Song-chang，等.一种基于Hadoop平台的海量Web数据挖掘系统研究与实现[C]//.中国通信学会学术年会，2012.
[10] 盛昀瑶，陈爱民.基于MapReduce的Web日志挖掘算法研究[J].现代计算机，2017（16）：14-18.
[11] 程苗.基于云计算的Web数据挖掘[J].计算机科学， 2011， 38（b10）：146-149.
[12] 刘骞，陈明.基于改进的Map/Reduce及模式空间划分的数据挖掘[J].微电子学与计算机，2011， 28（8）：140-142.
【通联编辑：梁书】