决策树和朴素贝叶斯算法简介

本节主要介绍数据挖掘中常见的分类方法决策树和朴素贝叶斯算法。

决策树算法

决策树（Decision Tree，DT）分类法是一个简单且广泛使用的分类技术。

决策树是一个树状预测模型，它是由结点和有向边组成的层次结构。树中包含3种结点：根结点、内部结点和叶子结点。决策树只有一个根结点，是全体训练数据的集合。

树中的一个内部结点表示一个特征属性上的测试，对应的分支表示这个特征属性在某个值域上的输出。一个叶子结点存放一个类别，也就是说，带有分类标签的数据集合即为实例所属的分类。

1. 决策树案例

使用决策树进行决策的过程就是，从根结点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子结点，将叶子结点存放的类别作为决策结果。

图 1 是一个预测一个人是否会购买电脑的决策树。利用这棵树，可以对新记录进行分类。从根结点（年龄）开始，如果某个人的年龄为中年，就直接判断这个人会买电脑，如果是青少年，则需要进一步判断是否是学生，如果是老年，则需要进一步判断其信用等级。
假设客户甲具备以下 4 个属性：年龄 20、低收入、是学生、信用一般。通过决策树的根结点判断年龄，判断结果为客户甲是青少年，符合左边分支，再判断客户甲是否是学生，判断结果为用户甲是学生，符合右边分支，最终用户甲落在“yes”的叶子结点上。所以预测客户甲会购买电脑。

2. 决策树的建立

决策树算法有很多，如 ID3、C4.5、CART 等。这些算法均采用自上而下的贪婪算法建立决策树，每个内部结点都选择分类效果最好的属性来分裂结点，可以分成两个或者更多的子结点，继续此过程直到这棵决策树能够将全部的训练数据准确地进行分类，或所有属性都被用到为止。

1）特征选择

按照贪婪算法建立决策树时，首先需要进行特征选择，也就是使用哪个属性作为判断结点。选择一个合适的特征作为判断结点，可以加快分类的速度，减少决策树的深度。

特征选择的目标就是使得分类后的数据集比较纯。如何衡量一个数据集的纯度？这里就需要引入数据纯度概念——信息增益。

信息是个很抽象的概念。人们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。

1948 年，信息论之父 Shannon 提出了“信息熵”的概念，才解决了对信息的量化度量问题。通俗来讲，可以把信息熵理解成某种特定信息的出现概率。信息嫡表示的是信息的不确定度，当各种特定信息出现的概率均匀分布时，不确定度最大，此时嫡就最大。反之，当其中的某个特定信息出现的概率远远大于其他特定信息的时候，不确定度最小，此时熵就很小。

所以，在建立决策树的时候，希望选择的特征能够使分类后的数据集的信息熵尽可能变小，也就是不确定性尽量变小。当选择某个特征对数据集进行分类时，分类后的数据集的信息嫡会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。

ID3 算法使用信息增益作为属性选择度量方法，也就是说，针对每个可以用来作为树结点的特征，计算如果采用该特征作为树结点的信息增益。然后选择信息增益最大的那个特征作为下一个树结点。

2）剪枝

在分类模型建立的过程中，很容易出现过拟合的现象。过拟合是指在模型学习训练中，训练样本达到非常高的逼近精度，但对检验样本的逼近误差随着训练次数呈现出先下降后上升的现象。过拟合时训练误差很小，但是检验误差很大，不利于实际应用。

决策树的过拟合现象可以通过剪枝进行一定的修复。剪枝分为预先剪枝和后剪枝两种。

预先剪枝是指，在决策树生长过程中，使用一定条件加以限制，使得在产生完全拟合的决策树之前就停止生长。

预先剪枝的判断方法也有很多，例如，信息增益小于一定阈值的时候通过剪枝使决策树停止生长。但如何确定一个合适的阈值也需要一定的依据，阈值太高会导致模型拟合不足，阈值太低又导致模型过拟合。

后剪枝是指，在决策树生长完成之后，按照自底向上的方式修剪决策树。后剪枝有两种方式，一种是用新的叶子结点替换子树，该结点的预测类由子树数据集中的多数类决定，另一种是用子树中最常使用的分支代替子树。

预先剪枝可能会过早地终止决策树的生长，而后剪枝一般能够产生更好的效果。但后剪枝在子树被剪掉后，决策树生长过程中的一部分计算就被浪费了。

3. Spark MLlib 决策树算法

Spark MLlib 支持连续型和离散型的特征变量，也就是既支持预测也支持分类。

在 Spark MLlib 中、建立决策树时是按照信息增益选择划分特征的，它采用前向剪枝的方法来防止过拟合，当任意一个以下情况发生时，Spark MLlib 的决策树结点就终止划分，形成叶子结点。

• 树高度达到指定的最大高度 maxDepth。
• 当前结点的所有属性分裂带来的信息増益都小于指定的阈值 minInstancesPerNode。
• 结点分割出的子结点的最少样本数量小于阈值 minInstancesPerNode。

Spark MLlib 的决策树算法是由 DecisionTree 类实现的，该类支持二元或多标签分类，并且还支持预测。用户通过配置参数 Strategy 来说明是进行分类，还是进行预测，以及使用什么方法进行分类。

1）Spark MLlib 的 DecisionTree 的训练函数

DecisionTree 调用 trainClassifier 方法进行分类训练，参数如下所示。

def trainClassifier(
    input: RDD[LabeledPoint],
    numClasses: Int,
    categoricalFeaturesInfo: Map[Int,Int], impurity: String,
    maxDepth:Int,
    maxBins:Int): DecisionTreeModel

该训练函数将返回一个决策树模型，函数各个参数的含义如下。

名称	说明
Input	表示输入数据集，每个 RDD 元素代表一个数据点，每个数据点都包含标签和数据特征，对分类来讲，标签的值是 {0,1,...,numClasses-1}。
numClasses	表示分类的数量，默认值是 2。
categoricalFeaturesInfo	存储离散性属性的映射关系，例如，（5→4)表示数据点的第 5 个特征是离散性属性，有 4 个类别，取值为{0,1,2,3}。
impurity	表示信息纯度的计算方法，包括 Gini 参数或信息熵。
maxDepth	表示树的最大深度。
maxBins	表示每个结点的分支的最大值。

2）Spark MLlib 的 DecisionTree 的预测函数

DecisionTreeModel.predict 方法可以接收不同格式的数据输入参数，包括向量、RDD，返回的是计算出来的预测值。该方法的 API 如下。

def predict(features:Vector):Double
def predict(features: RDD[Vector]): RDD[Double]

其中，第一种预测方法是接收一个数据点，输入参数是一个描述输入数据点的特征向量，返回的是输入数据点的预测值。第二种预测方法可以接收一组数据点，输入参数是一个 RDD，RDD 中的每一个元素都是描述一个数据点的特征向量，该方法对每个数据点的预测值以 RDD 的方式返回。

4. Spark MLlib 决策树算法实例

实例：导入训练数据集，使用 ID3 决策树建立分类模型，采用信息增益作为选择分裂特征的纯度参数，最后使用构造好的决策树，对两个数据样本进行分类预测。

该实例使用的数据存放在 dt.data 文档中，提供了 6 个点的特征数据和与其对应的标签，数据如下所示。

1 1:1 2:0 3:0 4:1
0 1:1 2:0 3:1 4:1
0 1:0 2:1 3:0 4:0
1 1:1 2:1 3:0 4:0
1 1:1 2:0 3:0 4:0
1 1:1 2:1 3:0 4:0

数据文件的每一行是一个数据样本，其中，第 1 列为其标签，后面 4 列为数据样本的 4 个特征值，格式为（key: value）。

实现的代码如下所示。

import org.apache.spark.mllib.tree.DecisionTree
import org.apache.spark.mllib.util.MLUtils
import org.apache.spark.{SparkConf, SparkContext}

object DecisionTreeByEntropy {
    def main(args: Array[String]) {
    val conf = new SparkConf().setMaster("local[4]").setAppName ( "DecisionTreeByEntropy")
    val sc = new SparkContext (conf)

    //上载和分解数据
    val data = MLUtils.loadLibSVMFile (sc, ("/home/hadoop/exercise/dt.data"))
    val numClasses = 2 //设定分类数量
    val categoricalFeaturesInfo = Map[Int,Int]() //设定输入格式
    val impurity = "entropy" //设定信息增益的计算方式 val maxDepth = 5 //设定树的最大高度
    val maxBins = 3 //设定分裂数据集如最大个数

    //建立模型并打印结果
    val model = DecisionTree.trainClassifier(data,numClasses,categoricalFeaturesInfo,impurity,maxDepth,maxBins)
    printIn ("model.depth:"+ model.depth)
    printIn ("model.numNodes:" + model.numNodes) printIn ("model.topNode:" + model.topNode)

    //从数据集中抽取两个数据样本进行预测并打印结果
    val labelAndPreds = data.take(2).map { point =>
        val prediction = model.predict(point.features)
        (point.label, prediction)
    }
    labelAndPreds.foreach(printIn)
    sc.stop
    }
}

运行以上代码将输出构建的决策分类树的信息，包括树的高度、结点数和树的根结点的详细信息，以及两个样本的实际值和预测值。具体信息如下。

model.depth:2
model.numNodes:5
model.topNode:id = 1, isLeaf = false, predict = 1.0 (prob = 0.6666666666666666),
impurity = 0.9182958340544896, split = Some(Feature = 0, threshold = 0.0, featureType = Continuous, categories = List())r
stats = Some(gain = 0.31668908831502096, impurity = 0.9182958340544896,
left impurity = 0.0, right impurity = 0.7219280948873623)
(1.0,1.0)
(0.0,0.0)

5. 算法优缺点

决策树是非常流行的分类算法。一般情况下，不需要任何领域知识或参数设置，它就可以处理高维数据。它对知识的表示是直观的，并且具有描述性，非常容易理解，有助于人工分析。用决策树进行学习和分类的步骤非常简单，效率高。决策树只需要一次构建，就可以反复使用，但每一次预测的最大计算次数不能超过决策树的深度。

一般来讲，决策树具有较好的分类准确率，但是决策树的成功应用可能依赖于所拥有的建模数据。

朴素贝叶斯算法

朴素贝叶斯（Nawe Bayes）算法是一种十分简单的分类算法。它的基础思想是，对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属 于哪个类别。

1. 贝叶斯公式

朴素贝叶斯分类算法的核心是贝叶斯公式，即 P(B|A)=P(A|B)P(B)/P(A)。换个表达形式 会更清晰一些，P(类别|特征)=P(特征|类别)P(类别)/P(特征)。

如果 X 是一个待分类的数据元组，由 n 个属性描述，H 是一个假设，如 X 属于类 C， 则分类问题中，计算概率P(H|X)的含义是，已知元组 X 的每个元素对应的属性值，求出；V 属于 C 类的概率。

例如，X 的属性值为 age=25, income=$5 000, H 对应的假设是，X 会买电脑。

• P(H|X)：表示在已知某客户信息 age=25，income=$5 000 的条件下，该客户会买电脑的概率。
• P(H)：表示对于任何给定的客户信息，该客户会购买电脑的概率。
• P(X|H)：表示已知客户会买电脑，那么该客户的属性值为 age=25, income=$5 000 的概率。
• P(X)：表示在所有的客户信息集合中，客户的属性值为 age=25, income=$5 000 的概率。

2. 工作原理

1）设 D 为样本训练集，每一个样本 X 都是由 n 个属性值组成的，即 X=(x1,x2,...,xn))，对应的属性集为 A1,A2,A3,…,An。

2）假设有 m 个类标签，即C1,C2,…,Cm。对于某待分类元素 X，朴素分类器会把 P(C1|X) (i=1,2,…,m)值最大的类标签 C1 作为的类别。因此目标就是找出 P(C1|X) 中的最大值 (P(C1|X)=P(X|C1)P(C1)|P(X)

3）如果 n 的值特别大，也就是说样本元组有很多属性，那么对于 P(X|C1) 的计算会相当复杂。所以朴素贝叶斯算法做了一个假设，即对于样本元组中的每个属性，由于它们都互相条件独立，因此有 P(X|C1)=P(X1|C1)P(X2|C1)...(Xn|C1)。由于可以从训练集中计算出来，所以训练样本空间中，属于类 C1 并且对应属性 A1 的概率等于 x1 的数目除以样本空间中属于类 C1 的样本数目。

4）为了预测 X 所属的类标签，可以根据前面的步骤算出每一个类标签 C1 对应的 P(X|C1)P(C1) 值，当某一个类标签 C1，对于任意 j(1≤j≤m,j≠i)，都有 P(X|C1)P(1)>P(X|C1)P(C1) 时，则认为 X 属于类标签 C1。

3. Spark MLlib 朴素贝叶斯算法

Spark MLlib 的朴素贝叶斯算法主要是计算每个类别的先验概率，各类别下各个特征属性的条件概率的，其分布式实现方法是对样本进行聚合操作，统计所有标签出现的次数、对应特征之和。

聚合操作后，可以通过聚合结果计算先验概率、条件概率，得到朴素贝叶斯分类模型。预测时，根据模型的先验概率、条件概率，计算每个样本属于每个类别的概率，最后取最大项作为样本的类别。

Spark MLlib 支持 Multinomial Naive Bayes 和 Bernoulli Naive Bayes。Multinomial Naive Bayes 主要用于文本的主题分类，分析时会考虑单词出现的次数，即词频，而 Binarzied Multinomial Naive Bayes 不考虑词频，只考虑这个单词有没有出现，主要用于文本情绪分析。可以通过参数指定算法使用哪个模型。

Spark MLlib 的 Native Bayes 调用 train 方法进行分类训练，其参数如下所示。

def train(
    input:RDD[LabeledPoint],
    lambda:double,
    modelType:String):NativeBayesModel

该训练函数将返回一个朴素贝叶斯模型，函数各个参数的含义如下。

• input 表示输入数据集，每个 RDD 元素代表一个数据点，每个数据点包含标签和数据特征，对分类来讲，标签的值是 {0,1,...,numClasses-1}。
• lambda 是一个加法平滑参数，默认值是 1.0。
• modelType 用于指定是使用 Multinomial Native Bayes 还是 Bernoulli Native Bayes 算法模型，默认是 Multinomial Naive Bayes。

Spark MLlib 的 Native Bayes 的预测函数 NativeBayesModel.predict 方法与 DecisionTree 的预测函数一样，可以接收不同的数据输入参数，包向量、RDD，返回的是计算出来的预测值。

4. Spark MLlib 朴素贝叶斯算法实例

以表 1 的购买电脑样本数据作为训练数据集，使用 Multinomial Native Bayes 建立分类模型，然后使用构造好的分类模型，对一个数据样本进行分类预测。

表 1 购买电脑样本数据

age	income	student	credit_rating	buys_computer
≤30	high	no	fair	no
≤30	high	no	excellent	no
31~40	high	no	fair	yes
>40	medium	no	fair	yes
>40	low	yes	fair	yes
>40	low	yes	excellent	no
31~40	low	yes	excellent	yes
≤30	medium	no	fair	no
≤30	low	yes	fair	yes
>40	medium	yes	fair	yes
≤30	medium	yes	excellent	yes
31~40	medium	no	excellent	yes
31~40	high	yes	fair	yes
>40	medium	no	excellent	no

该实例使用的数据存放在 sample_computer.data 文档中，数据文件的每一行是一个数据样本，其中，第 1 列为其标签，后面 4 列为数据样本的 4 个特征值。标签与特征值以“，”分割，特征值之间用空格分隔，如下所示。

buys_computer,age income student credit_rating

其中，buys_computer 的取值为，no 为 0，yes 为 1；age 的取值为，≤30 为 0，31~40 为 1，>40 为 2；income 的取值为，low 为 0，medium 为 1，high 为 2；student 的取值为，no 为 0，yes 为 1，credit_rating 的取值为，fair 为 0，excellent 为 1。

对应于表 1 的数据的前 3 行数据如下。

实现的代码如下所示：

import org.apache.spark.mllib.classification.{NaiveBayes,NaiveBayesModel}
import org.apache.spark.mllib.linalg.Vectors
import org.apache.spark.mllib.regression.LabeledPoint
import org.apache.spark.{SparkContext,SparkConf}

object NaiveBayes {
    def main (args : Array[String]) : Unit = {
        val conf = new SparkConf().setMaster("local").setAppName("NaiveBayes")
        val sc = new SparkContext(conf)
        val path ="../data/sample_computer.data"
        val data = sc.textFile(path)
        val parsedData = data.map {
            line =>
                val parts = line.split(','))
                LabeledPoint (parts(0).toDouble,Vectors.dense (parts(1).split('').map(_.toDouble)))
        }
        //样本划分 train 和 test 数据样本 60% 用于 train
        val splits = parsedData.randomSplit(Array(0.6,0.4),seed = 11L)
        val training = splits(0)
        val test = splits(1)
        //获得训练模型，第一个参数为数据，第二个参数为平滑参数，默认为1
        val model = NaiveBayes.train(training,lambda = 1.0)
        //对测试样本进行测试
        val predictionAndLabel = test.map(p => (model.predict(p.features),p.label))
        //对模型进行准确度分析
        val accuracy = 1.0 *predictionAndLabel.filter (x => x._1 == x._2).count()/test.count.()
        //打印一个预测值
        printIn ("NaiveBayes精度------>" + accuracy)
        printIn ("假如 age<=30, income=medium, student=yes,credit_rating=fair,是否购买电脑：" + model.predict(Vectors.dense(0.0,2.0,0.0,1.0)))
        //保存model
        val ModelPath = "../model/NativeBayes_model.obj"
        model.save(sc.ModelPath)
    }
}

5. 算法优缺点

朴素贝叶斯算法的主要优点就是算法逻辑简单，易于实现；同时，分类过程的时空开销小，只会涉及二维存储。

理论上，朴素贝叶斯算法与其他分类方法相比，具有最小的误差率。但是实际上并非总是如此，这是因为朴素贝叶斯模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性较大时，分类效果不好，而在属性相关性较小时，朴素贝叶斯算法的性能最为良好。