基于朴素贝叶斯分类算法实现

实现了基于朴素贝叶斯分类算法

基于朴素贝叶斯的数据分类算法的实现

李永超

(南京大学 计算机科学与技术系, 南京 210093)

Implementation of Data Classification Algorithm Based on Naïve Bayesian

Yongchao Li

(Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China)

Abstract: I implemented a data classification algorithm, which is based on Naïve Bayesian. Data classification is an imperative way of analyzing data, it extracts models depicting important data classifications [1]. There are many methods for data classifications, such as Decision Tree Regression, Naïve Bayesion, Rule-Based Classification, SVM, and so on. Each of the method listed above performs well in data classifications and each has outstanding features as well as fallbacks. According to the precedent experiments in which Naïve Bayesian based classification method is compared to other classification methods including Decision Tree and Neural Network classification, Naïve Bayesian performance as good as these methods [1]. To implement the algorithm, I designed two main classes—TrainingData and TestData,--both of which will be explained explicitly in the remaining part of this article. The experiment is based on a training dataset, which is split into two classes labeled 1 and -1 respectively. A test dataset is given and it is required to split the test dataset into two classes according to the given training dataset and its training label.

Key words: Data Classification; Naïve Bayesian; Algorithm

摘 要: 我实现了一个基于朴素贝叶斯的数据分类算法。数据分类是一种重要的数据分析形式，它提取刻画重要数据类的模型[1]。如今有很多数据分类方法，例如决策树回归，朴素贝叶斯，基于规则的分类，支持向量机等。他们各自应用在数据分类时都具有优良的性能。他们各自都有自身突出的优势同时也具有不同的缺点。朴素贝叶斯方法与决策树和神经网络分类法的各种比较实验表明，在某些情况下朴素贝叶斯可以与他们在性能上媲美[1]。我设计了两个主要的类TrainingData和TestData来实现我的算法，本文的随后部分将对这两个类详细解释。算法执行实验的数据是一个训练数据集和它的训练标签。训练数据集被分为两类，分别标以1和-1。要求将给定的测试数据集按照训练数据集和相应的训练标记分成两类。 关键词: 数据分类；朴素贝叶斯；算法

1 引言

数据挖掘技术正越来越广泛的被应用，从医疗到军事，从教育到地质勘探，数据挖掘技术在各个领域都发挥了积极地作用。数据分类是数据挖掘技术中重要的数据分析形式，在现实中有极其广泛的应用场景。银行贷款员要将提供的贷款分为“安全的”和“风险的”以降低产生不必要损失的可能性，医院需要根据病人的诊断数据划分出“健康”与“非健康”。

数据分类的方法有很多——决策树回归，朴素贝叶斯，基于规则的分类，支持向量机等。将他们按各自的特点应用于不同的场景，都能起到不错的分类效果。本文实现了一个基于朴素贝叶斯的数据分类算法，

实现了基于朴素贝叶斯分类算法

并且根据给定的训练数据集对测试数据集进行了分类。已知测试数据集中某条数据的各维属性，预测其所属分类，根据贝叶斯定理，即要计算一个后验概率。在对测试数据进行分类预测之前，需要提取训练数据集中的信息，对连续数据采用将其近似化为高斯分布的方法，通过从数据集求出相应的分布参数，得到训练数据集的有用特征，从而预测测试数据的分类。

本文其余部分安排如下：第2节简单介绍贝叶斯定理与朴素贝叶斯分类方法，第3节详细讲解基于朴素贝叶斯的分类算法，第4节对算法的执行结果进行展示，第5节将对所做工作进行总结。

2 贝叶斯定理与朴素贝叶斯分类

假设事件B存在一个完整划分I = {B1,B2,B3,...,Bi}，已知事件A发生的条件概率可以用以下公式求出：

图 1 贝叶斯公式[2]

这就是贝叶斯定理。P（Bi|A）称作后验概率，P(A|Bi)为先验概率，通常是已知先验概率来求后验概率。贝叶斯定理为提供了“预测”的实用模型，即已知某事实（例如某数据项以及其n维属性），预测另一个事实发生的可能性大小（例如该数据项属于分类A的可能性大小），可以借助贝叶斯公式将该问题转换为对已知概率模型的计算。

将朴素贝叶斯用于数据分类的过程如下[1]：

（1）

（2） 设训练元组和它所有的分类构成的集合为T，每条元组数据由n个属性，A1,A2,A3,…,An，向量X={x1,x2,x3,…,xn}表示某条元组具体的各属性值； 假设元组被分为m个类，C1,C2,C3,…,Cm，对于要将测试数据划分到m个类中的问题，可以

通过建立如下概率模型解决：

已知某测试元组D以及其属性的度量X，令Pi=P(Ci|X)，表示已知属性度量，求属于Ci分类

的条件概率。令Pj=max{ Pj}(j = 1,2,3,…,m)，则认为D应分为i类；

（3） 由贝叶斯公式可得：pi = ( | ) ( )P( ) 。 朴素贝叶斯将元组数据各维属性近似看做独立变量，

因此有P(X|Ci) = ∑ =1 ( | )；

（4） 对于连续分布的属性维，朴素贝叶斯将其近似为高斯分布：

图 2 高斯分布[3]

（5） 由于对于每条元组P(X)为常量，因此只需比较Qi = P(X|Ci)P(Ci) 的大小，令

Qi = max{ P(X|Cj)P(Cj)}(j = 1,2,3,…,m)，则将元组划分为i类。

3 基于朴素贝叶斯的分类算法

3.1 数据结构设计

3.1.1 TrainingData

TrainingData类，描述训练元组集合，包含下述成员属性：

实现了基于朴素贝叶斯分类算法

ClassCount—类别数目，训练数据被分为ClassCount个类别；

ClassFreq—这是一个数组，维度为ClassCount，存放每一类数据在训练数据中出现的频率，将其近似为P(Ci)；

TupleData—数据元组，是一个维度为ClassCount的数组，按类别存放数据元组。

TrainingData的数据由文本文件给出，每一行对应一个元组。在实例化TrainingData对象时指定文本文件，将数据导入对象中。

3.1.2 TupleData

TupleData类，描述元组，具有的成员属性如下：

dataItems—维度为x的数组，x为数据集中某类元组数目，存放元组数据；

u,o—各自是维度为m的数组，m为元组数据的属性维度，用来描述高斯分布的平均数和标准差属性。

3.1.3 TestData

TestData类，描述测试数据集，具有如下成员属性：

TupleData—存放测试数据的元组数据；

ClassCount—在对象实例化时传进来，用于分类，描述分类个数；

ItemCount—描述测试数据集中元组个数。

TestData中重要的成员方法是doClassification，将TrainingData作为参数，根据指定的训练数据进行数据分类。

3.2 算法流程

算法主要有两个步骤，首先计算训练数据中各属性高斯分布的参数，然后计算P(X|Ci)P(Ci)，决定各个测试元组的分类。

3.2.1 计算高斯分布参数

用伪代码来描述高斯分布参数是如何计算的：

算法1 计算各属性高斯分布的期望

for(训练数据集中每个属性Ai)

for(训练数据集中每个元组Dj)

Sum += Ai，j

属性Ai高斯分布期望 = Sum/元组个数

算法2 计算各属性高斯分布的标准差

for(训练数据集中每个属性Ai)

for(训练数据集中每个元组Dj)

Sum +=（Ai ，j– Ai的期望）2

属性Ai高斯分布标准差 = √ /元组个数

对于每一个分类，按上述算法计算出其各维属性的高斯分布参数。

实现了基于朴素贝叶斯分类算法

3.2.2 计算P(X|Ci)P(Ci)

由于朴素贝叶斯假设元组各属性独立分布，所以P(X|Ci) = ∑ =1 ( | )。为测试数据计算每条元组P(X|Ci) P(Ci)伪代码如下：

算法3 计算P(X|Ci)P(Ci)

for(测试数据中元组Di)

for(类别Ci)

Sum = P(Ci)

for(元组Di属性Aj)

Sum *= P(xi|Ci)

计算P(xi|C)时，将xi代入属性Ai的高斯分布公式中。

将元组Di归于j类当且仅当P(X|Cj)P(Cj) = max{ P(X|Ci)P(Ci)}(i = 1,2,3,…,m)。

3.3 复杂度分析

假设训练数据有n个元组，每个元组m个属性，数据被分为k类。则计算高斯参数需要做2nmk次加法运算，时间复杂度为o(n3)。

假设测试数据有x个元组，每个元组y个属性。分类过程需要做xym次乘法运算，时间复杂度为o(n3)。 故朴素贝叶斯分类算法的时间复杂度为o(n3)。

4 测试

算法实现用java语言。源文件清单如下：

TrainingData.java—实现TrainNingData类；

TupleData.java—实现TupleData.java类；

TestData.java—实现TestData类；

RunTest.java—main函数所在类。

表1 测试环境：

4.1 测试数据

训练数据集：共有700条数据，每条数据42个属性；

训练数据集标签：有两类标签，1和-1；

测试数据集：共有400条数据，每条数据42个属性。

4.2 分类结果

首先计算高斯参数，图3 展现了计算高斯参数的结果：

实现了基于朴素贝叶斯分类算法

图3 高斯参数计算结果

例如某条数据class0 attribute4 u = 0.08197001932011333 o = 1.6795295639086947，表示分类0，第4条属性的期望为0.08197001932011333，标准差为1.6795295639086947。

最后得出分类结果如下：

图4 测试数据分类结果

每一行对应测试数据中某元组的分类。完整的分类信息存放在output.txt文件中。

5 总结

本文阐述了一个基于朴素贝叶斯分类法的实现并给出了算法测试结果。朴素贝叶斯分类方法在某些领域的应用可以与决策树和神经网络分类法相媲美[1]

。然而朴素贝叶斯分类法存在严重的缺陷，这个缺陷源

实现了基于朴素贝叶斯分类算法

于如下两个假设：

某维属性值之间相互独立； 连续分布的属性值服从高斯分布。

这可能会影响数据分类的准确性。因此实际应用中应根据特定的场景选择适当的数据分类算法。 References:

[1]Jia Han, Micheline Kamber, Jian Pei著。范明，孟小峰译。数据挖掘——概念与技术，机械工业出版社，2012.7；

[2] ；

[3] ；

本文来源：https://www.bwwdw.com/article/7hi4.html