基于map和redule并行的svm分类算法

基于map和redule并行的svm分类算法

0svm分类算法的特点云计算是互联网发展的产物。大多数基于网络统计和分析的数据都是大规模和有限的数据。面对如此庞大且不断增长的数据信息,如何高效、准确地组织和分类这些数据信息是当代信息科学技术领域的一大难题。传统平台在数据分类时效率低下,有2个主要原因:传统平台在很大程度上受到了计算力伸缩性的制约,平台的计算力不易得到扩展和伸缩;分类算法大多以串行的方式运行,很少被并行化处理,分类过程不能高效并行化进行。SVM(supportvectormachine,支持向量机)分类算法有很好的泛化能力与学习能力。该算法是以结构风险最小化为目标,所求得的解是全局最优解。该算法可以解决“维数灾难”问题。但SVM分类算法的分类准确度易受到数据集、分类器及训练参数的影响,传统的支持向量机模型参数及其核函数参数的取值大多都是随机值或经验值,随机性和主观经验性过强,这导致分类的准确度不高。笔者在云计算环境下为数据分类提供弹性的集群计算力来满足计算的需求,使平台的计算力得到扩展,并在其平台下对分类算法进行MapReduce并行化处理和运行,利用基于优化理论的遗传算法对支持向量机模型参数和核函数参数进行优化,对数据进行实验仿真,与未优化的SVM算法进行了对比以验证算法的有效性。1麦擦模型和应用1.1map+rin-pcr的算法组成、特点MapReduce采用“分而治之”的思想,把对大规模数据集的操作,分发给一个主节点管理下的各分节点共同完成,通过整合各分节点的中间结果而得到最终结果。包括Map、Partition、Shuffle、Combine、Sort、Reduce这几个过程。中间过程的功能可以合并到Map、Reduce中,主要用于实现对Map、Reduce两个过程的性能优化。上述处理过程能被高度抽象为2个函数,即Map和Reduce:Map负责把任务分解成多个任务;Reduce负责把分解后多任务处理的结果汇总起来。在Map阶段,MapReduce框架将任务的输入数据分割成固定大小的片段(Splits),随后将每个Split进一步分解成一批键值对<K1,V1>。Hadoop为每个Split创建一个Map任务,用于执行用户自定义的Map函数,并将对应Split中的<K1,V1>对作为输入,得到计算的中间结果<K2,V2>。接着将中间结果按照K2进行排序,并将Key值相同的Value放在一起形成一个新的列表,形成<K2,list(V2)>元组。最后再根据Key值的范围对这些元组进行分组,对应不同的Reduce任务。在Reduce阶段,Reduce把从不同Map接收来的数据整合在一起并进行排序,然后调用用户自定义的Reduce函数,对输入的<K2,list(V2)>对进行相应的处理,得到键值对<K3,V3>并输出到HDFS(hadoopdistributedfilesystem)上(图1)。1.2子测试分类结果在svm算法相比传统的单机进行SVM数据分类来说,单机要完成对整个数据集的运算,但在Hadoop平台上计算力容易得到扩展和伸缩,根据MapReduce的并行计算特点,可以利用Map操作和Reduce操作在多个子计算节点(DataNode)上同时进行数据处理。根据SVM算法数据分类的原理可知,在分类之前必须先求出分类模型,也就是要用Map操作找出所有子训练数据里面的子支持向量SVs(supportvectors),然后利用Reduce操作再将各个子计算节点上的子支持向量进行合并,汇总成关于数据集的完整的支持向量AllSVs(allsupportvectors),这些完整的支持向量才能唯一确定数据的分类超平面,即通过支持向量而得到最终的分类器;然后再利用分类器对每个子计算节点上的子测试数据进行Map操作,得出子分类测试结果Rs(results),进一步利用Reduce操作将这些子计算节点上的子测试分类结果进行合并汇总,得到最终的分类结果AllRs(allresults)。具体的流程如图2所示。2采用遗传统计法优化svm模型参数和选定核函数参数2.1参数的最优化处理在开源云计算平台Hadoop下基于SVM的大规模数据分类的过程可以描述成下述步骤:(1)首先要将其数据进行预处理(清理、规范化),然后再将数据分块成为满足HDFS要求的数据块,并存储在集群的各个机器上;(2)SVM分类器模型以及相关核函数的选取。本文选取的SVM模型为带惩罚参数的模型和分类准确度比较高的径向基核函数(RBF);(3)参数的最优化处理。本文利用遗传算法来寻找SVM模型参数和核函数参数的最优参数值;(4)对样本数据进行训练和预测。利用步骤(3)得到的最优化参数对训练数据进行训练,将训练得到的分类模型用于测试数据的测试。2.2基于ga的svm模型优化遗传算法(geneticalgorithm,GA)是一种基于生物遗传和进化机制的,适合复杂系统、多目标问题优化的自适应概率优化技术。它具有较强的实用性、高效性,鲁棒性强、全局寻优以及内在的隐并行性的特点,并且它没有传统搜索算法的函数连续性和求导的局限性,已经在很多领域得到了广泛的应用。利用GA对SVM模型参数和核函数参数进行优化的过程如图3所示。图3中利用GA对SVM模型参数c和核函数参数g进行优化的具体步骤如下所示:(1)输入经过预处理后的训练数据样本;(2)GA相关参数及SVM模型参数和核函数参数的初始化;(3)利用随机函数初始化种群,以SVM算法所求得的准确度作为个体适应度函数;(4)确定适应度的标准;(5)判断当前的个体极值是否为种群的全局最优解,如果是,就确定最优解;若不是,则种群代数增加进行循环操作,对GA的个体进行选择、变异、交叉操作,产生新个体,并计算出新个体的适应度值;(6)确定最终的最优解,并输出相应的最优解(Bestc&g)。3参数优化后分类准确度c=0.75,Pm=0.25;SVM模型参数c取值范围为1~100,核函数参数g取值范围为0~800。基于遗传算法对SVM模型参数c和核函数参数g寻优的结果如图4所示。由图4得出,GA算法在进化代数为75代时停止进化,并在此找到了基于全局最优的SVM模型参数c值为40.005,核函数参数g值为0.073242。数据分类模型训练的优良与否和分类准确度的高低都与数据样本质量有着密切的关系,因此在此实验之前本文已经对数据进行了去噪、规范化、降维等前期预处理。表1是由实验得出的参数优化前后分类准确度的对比。经实验对比可见,通过对SVM模型参数和核函数参数运用GA算法进行优化处理后,前两个数据集分类的准确度都有明显的提高,第3个数据集测试集样本数比训练集样本数要大一些,导致一定程度的欠学习,从而导致训练的模型精度不高,所以经过寻优处理后分类精度提高的不是十分明显。总体而言,经优化后的分类准确度比传统未优化的分类准确度效果更好,该方法具有一定的实用性。为了衡量数据在开源云计算平台Hadoop集群上运行的效率,本文定义一个加速度比的变量:加速度比(speedup)=传统单机平台运行时间/Hadoop集群平台运行时间。3个数据集分类加速度比的实验运行结果见图5。可以看到,单机的运行效率比单个Hadoop计算节点运行的效率要高一些,这是因为单个Hadoop节点需要额外加载一些Hadoop平台运行相关的系统资源,这样就导致了计算分类的资源减少了,从而效率没有单机速度快。由于集群节点之间有相互的网络通信、数据的传输以及同步开销,所以分类的加速度比不会随着节点个数的增加而达到绝对的线性增加。但总体而言,SVM数据分类经过MapReduce处理后,随着Hadoop集群上节点数的动态伸缩性的增加,加速度比也在呈现较为平缓的增加,因此,该方法对提高数据分类效率有一定的实用性和可行性。4svm分类算法的优化分析了传统平台进行数据分类时的平台计算力伸缩性的瓶颈和分类算法未并行化执行的局限性,并从SVM的原理出发,讨论了SVM分类算法在分类模型和相关核函数在参数选择上的不足,因此,本文利用普通PC机器组成Hadoop集群平台来满足计算力伸缩性需求,在此平台上发挥MapReduce并行性的优势,使分类算法的执行能在较短时间内完成分类任务,并运用GA算法对SVM模型参数和核函数参数取值进行了优化处理,从局部上改善了SVM