基于Hadoop的并行朴素贝叶斯分类算法

□周国军，程裕强，吴庆军

（玉林师范学院 数学与信息科学学院，广西 玉林 537000）

基于Hadoop的并行朴素贝叶斯分类算法

□周国军，程裕强，吴庆军

（玉林师范学院 数学与信息科学学院，广西 玉林 537000）

串行的朴素贝叶斯分类算法对大数据分类需要较长的执行时间，针对这个问题，设计了一种基于Hadoop的并行朴素贝叶斯分类算法.并行算法使用一个MapReduce任务对训练子集并行计算各个类别的先验概率和每个属性值的条件概率，从而实现了分类模型的构造，使用一个MapReduce任务对测试子集并行计算被正确分类的样本数，输出分类器的分类准确率.使用大数据集测试了串行算法与并行算法的运行时间，结果表明并行算法具有更高的执行效率.

Hadoop平台；朴素贝叶斯分类；MapReduce；并行计算

1　引言

朴素贝叶斯分类是一种利用统计学知识进行分类的算法，在样本各属性之间条件独立的前提下，该算法表现出较高的分类准确率，在文本分类[1]、故障诊断[2]等领域有较好的应用价值.随着大数据时代的到来，为了能较快地从海量数据中挖掘出有价值的知识，这对数据挖掘方法提出了更高的要求.串行的朴素贝叶斯分类算法对海量数据分类的计算量巨大，仅仅依靠单机系统的功能和性能难以达到预期效果[3].将朴素贝叶斯分类算法并行化，利用多个节点的计算能力对大数据构造和测试分类器是解决这个问题的有效途径.

MapReduce[4]是一种处理大数据的并行计算模型，本文根据云计算平台Hadoop[5]的MapReduce模型及其分布式缓存机制，设计了一种基于Hadoop的并行朴素贝叶斯分类算法.并行算法利用了Hadoop集群的计算能力，将大数据集分解成多个子数据集分配给多个节点并行处理，从而减少了构造和测试分类模型的时间，提高了对大数据分类的效率.

2　朴素贝叶斯分类算法

朴素贝叶斯分类算法的理论基础是贝叶斯定理，该算法的基本原理[6]介绍如下.

设D是一个训练数据集，D中的样本分为m个类C1,C2,…,Cm.每个样本用n个属性值描述，通常将样本表示为一个n维向量S={x1,x2,…,xn}.对于一个给定的待分类样本X和类别Ci（1≤i≤m），朴素贝叶斯分类算法使用最高的后验概率P(Ci|X)来预测X所属的类别.根据贝叶斯定理，P(Ci|X)的计算方法如下：

式(1)中的P(X)对于所有的类别为常数，因此，只需要对不同的类别Ci计算P(X|Ci)P(Ci)的最大值.类别Ci的先验概率P(Ci)的计算方法如下：

在属性个数较多的情况下，P(X|Ci)的计算开销很大.为了简化计算，可以假定各属性之间有条件地相互独立，在该假定成立的前提上，P(X|Ci)的计算方法如下：

式(3)中的P(xk|Ci)的值有可能为零，为了避免计算零概率值可以采用拉普拉斯校准，P(xk|Ci)的计算方法如下：

式(4)中的|xk|是第k个属性的值为xk且类别为Ci的样本数，|Ci|是类别为Ci的样本数，q是第k个属性的取值个数.

从朴素贝叶斯分类器中不能得到分类规则，训练分类器的目标是要得到P(Ci)和P(xk|Ci)，其中，1≤i≤m，1≤k≤n.测试分类器的主要过程是：对每个测试样本X和每个Ci分别计算P(X|Ci)P(Ci)的值，将取得最大值的Ci与该样本预先给定的类别比较，根据比较结果统计被正确分类的样本数.

3　云计算平台Hadoop简介

Hadoop平台的硬件基础是由大量计算机组成的集群，其核心组件是Hadoop分布式文件系统HDFS和MapReduce框架.其中，HDFS用于将数据文件以块的形式存储在集群的多个节点上，MapReduce框架通过在多个节点上并行执行Map和Reduce函数来高效处理数据[7].

从用户的角度来说，在Hadoop平台上处理大数据的关键任务是设计和实现Map、Reduce函数，由于Hadoop为用户提供了大量的接口、抽象类和工具，方便了应用程序的编写、调试和性能度量[8].MapReduce程序的输入输出是键/值对表示的数据，Map函数对数据分片进行处理并输出中间结果，其数据流可以表示为Map：(key1,value1)→list(key2,value2).Reduce函数对Map函数产生的中间结果进行处理并输出最终结果，其数据流可以表示为Reduce：(key2,list(value2))→list(key3,value3).

为了实现文件共享，Hadoop提供了分布式缓存机制，用于将文件分布到集群的所有节点上.对于执行Map任务的所有节点都需要的“背景”数据，将它们设置为分布式缓存文件，各节点就可以将这些文件读入内存，从而提高了数据访问效率[9].

4　基于Hadoop的并行朴素贝叶斯分类算法

并行朴素贝叶斯分类算法的基本思想是将训练集和测试集分解成多个数据分片，多个节点对数据分片并行构造、测试分类模型.由于利用了多个节点的计算能力，减少了构造和测试分类模型的时间，提高了对大数据分类的效率.

使用哈希表容易实现朴素贝叶斯分类器的训练和测试，算法所采用的哈希表结构如表1所示.表中的符号说明如下：m是类别的个数，n是属性的个数.用属性编号代替属性名，属性k表示数据集的第k个属性.k～xk～Ci表示第k个属性值为xk且类别为Ci的样本，“～”用于分开属性值和类别，可以用没有出现在数据集中的任何字符代替“～”，由于不同的属性可能有相同的属性值，为了区分不同属性，在属性值的前面加上属性编号k.

表1　算法的哈希表结构

假设数据集是文本文件，每一行记录对应一个样本，格式为“x1,x2,…,xn,Ci”，即样本的类别Ci放在一行的末尾.假设数据集的类别和属性描述信息存放在一个文本文件中，第一行记录的内容为数据集包含的所有类别Ci，格式为“C1,C2,…,Cm”，从第2行开始，每一行记录的内容为一个属性的所有取值，格式为“a1,a2, …”.算法的主要步骤描述如下：

（1）使用一个MapReduce任务（Job1）对训练集分片并行计算类别Ci包含的样本数，并行计算第k个属性值为xk且类别为Ci的样本数.说明：为了区分Ci和k～xk～Ci，在Map、Reduce函数中给Ci添加了一个前缀字符“～”.

5　实验及结果分析

使用7台配置相同的计算机搭建了一个Hadoop集群，Hadoop版本是1.2.1，JDK版本是1.7.0_51，操作系统是Ubuntu 12.04，实验数据是UCI机器学习库中的Nursery数据集（http://archive.ics.uci.edu/ml/datasets.html）.使用Java编程实现了朴素贝叶斯分类的串行算法和本文设计的并行算法，由于串行算法和并行算法具有相同的分类准确率，因此只对算法的执行效率进行测试和比较.

图1　并行算法的执行时间

采用复制样本的方法分别将Nursery数据集的规模扩大为5GB、10GB、15GB，在单机环境下执行串行算法所用的时间分别是337s，692s，1105s.将1台计算机作为管理节点（JobTracker），其余的计算机作为计算节点（TaskTracker），分别使用不同的TaskTracker节点数，在Hadoop集群上执行并行算法所用的时间如图1所示.

当使用3个TaskTracker节点时，并行算法对5GB、10GB、15GB数据的执行时间都小于串行算法的执行时间，当使用4~6个TaskTracker节点时，并行算法的执行时间进一步减少.从图1可以看出，随着节点数的增加，数据规模越大，并行算法的执行时间减少得越多，可见本文设计的并行朴素贝叶斯分类算法对大数据分类能取得较高的执行效率.

6　结束语

为了提高朴素贝叶斯分类算法对大数据分类的执行效率，设计了一种基于Hadoop的并行朴素贝叶斯分类算法.并行算法利用了Hadoop集群中多个节点的计算能力，减少了构造和测试分类器的时间.使用大数据集在Hadoop平台上测试了并行算法的性能，实验结果表明并行算法能取得较高的执行效率，适用于对大数据分类.但是，本文设计的并行算法在主函数中需要两次读取Job的输出文件，在类别个数和属性值个数较多的情况下需要较多的I/O时间，如何减少主函数的I/O操作时间还有待进一步研究. ■

[1]江小平，李成华，向文 等.云计算环境下朴素贝叶斯文本分类算法的实现[J].计算机应用，2011，31(9)：2551-2554.

[2]姚成玉，李男，冯中魁 等.基于粗糙集属性约简和贝叶斯分类器的故障诊断[J].中国机械工程，2015，26(14)：1969-1977.

[3]张依杨，向阳，蒋锐权 等.朴素贝叶斯算法的MapReduce并行化分析与实现[J].计算机技术与发展，2013，23(3)：23-26.

[4]Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[5]The Apache Software Foundation. Hadoop[EB/OL]. (2015-07-08) [2015-09-10]. http://hadoop.apache.org/.

[6]Jiawei Han, Micheline Kamber, Jian Pei.数据挖掘:概念与技术(第3版)[M].范明，孟小峰，译.北京：机械工业出版社，2012.

[7]陈吉荣，乐嘉锦.基于Hadoop生态系统的大数据解决方案综述[J].计算机工程与科学，2013，35(10)：25-35.

[8]郝树魁. Hadoop HDFS和MapReduce架构浅析[J].邮电设计技术，2012，(07)：37-42.

[9]涂金金,杨明,郭丽娜.基于MapReduce的基因读段定位改进算法[J].计算机科学，2015，42(8)：82-85.

【责任编辑 谢明俊】

Parallel Naive Bayesian Classification Algorithm Based on Hadoop

ZHOU Guo-jun, CHENG Yu-qiang, WU Qing-jun
(School of Computer Science and Engineering, Yulin Normal University, Yulin, Guangxi 537000)

The serial Naive Bayesian classification algorithm needs long execution time for big data. To solve this problem, a parallel Naive Bayesian classification algorithm based on Hadoop is designed. The key points of the parallel algorithm are as follows: Prior probability of each class and conditional probability of each attribute value are computed in parallel with a MapReduce task, which classification model is constructed; the number of correctly classified samples is computed for test subset with another MapReduce task, and classification accuracy is output. The execution time of serial algorithm is compared to that of parallel algorithm by experiment, and the result shows that parallel algorithm has higher execution efficiency.

Hadoop platform; Naive Bayesian classification; MapReduce; parallel computing

TP311.1

A

1004-4671（2015）05-0105-06

2015-09-15

玉林师范学院校级一般项目（项目编号：2014YJYB03）。

周国军（1975～），男，湖南宁远人，玉林师范学院数学与信息科学学院讲师，硕士。研究方向：数据挖掘。