决策树原理推导与使用

一、初步理解决策树

首先要理解什么是树

自然界中的树是由根节点和叶子节点组成；算法中最简单的树结构：二叉树，左子树所有节点的值均小于等于根节点的值，右子树的所有节点值均大于等于根节点值；讲这两个的目的是为了让大家理解，决策树其实也是做了一样的事情，他反复的在根节点判断，哪些样本该去左侧子树，哪些样本该去右侧子树，直到左侧子树和右侧子树都变成了叶子节点；

根节点

什么是根节点，根节点是每一个可以分叉的节点，只要这个节点还可以分叉，那这个节点就是根节点

叶子节点

叶子节点就是不可以分叉的节点

根节点的分叉

那怎么样才知道一个节点可不可以分叉呢？一个节点如果要分叉，肯定需要知道两个东西：分叉的依据以及哪些样本去左分叉、哪些样本去右分叉；

决策树的特征

在决策树中，分叉的依据叫做特征，你可以选择样本所有特征中的某一个作为这个节点的分叉依据；

 决定一批样本去左分叉，一批样本去右分叉的依据是看样本满不满足这个特征，比如满足这个特征的去右边，不满足的去左边

根节点的层级

 树是根节点是有层级结构的，那哪些根节点应该在上层，哪些根节点是在下层呢，这就需要引入一些概念：条件概率、信息熵、信息增益

条件概率

什么是条件概率：P(A|B)，B情况发生时再发生A的概率，比如B是明天下雨，A是明天加班，那P(A|B)就是明天下雨后，还需要加班的概率；

信息熵

信息熵，这是信息学中的概念，是一个具体数值，表示一批样本中信息的混乱程度；

公式：

 

公式中pi表示这一批样本中最终属于第i个分类的概率

比如对于下面的例子，最终的类别有两种--录取、不录取：

 

而且最终录取了2个，没有录取7个，所以这一批样本的信息熵为：

-(2/9)*log(2/9) - (7/9)*log(7/9) = 0.764

条件信息熵

条件概率，前面已经讲过

提出条件信息熵的目的，是为了计算最终的信息增益，某种条件的信息增益 = 信息熵 - 条件信息熵

具体计算方法：

 

同理，其中pi是这一批次样本中第i类的概率

比较难理解的可能就是H(Y|X=xi)了，这个对比信息熵不难发现，只是原来的X变成了Y|X=xi，前面讲过，这两个都是表示的批次，前面的批次是X，表示所有样本，现在的批次是 Y|X=xi ，表示满足条件X = xi的样本。

举个例子，比如条件是python，那就有两类样本：会、不会，会的有四个，不会的有五个。会python的那批样本的信息熵和不会python的那批样本的信息熵分别算出来，计算方法和之前讲的信息熵的计算方法一致，所以就可以计算出两个信息熵 ：

H(Y|X = 会python） = -(1/4)log(1/4) - (3/4)log(3/4) = 0.811

H(Y|X = 不会python） = -(1/5)log(1/5) - (4/5)log(4/5) = 0.722

最终结果带入条件信息熵的公式，可以计算出条件信息熵：

H(Y|X) = -(2/9)*0.811 - (7/9)*0.722 =  0.762

信息增益

信息增益，即使信息熵的变化，决策树中一般用 分叉前的信息熵 - 信息后的信息熵 表示信息增益，所以信息增益越大，说明用这个根节点分叉越有效，也即是这个特征用来分类对整体越有效

上面计算了以python这个特征分类的信息熵和条件信息熵，最终得到的信息增益：

0.764 - 0.762 = 0.002

几乎毫无增益，可以得出结论，一个人会不会python和最终有没有被录取屁关系没有

信息增益比

这个概念是为了消除特征的样本数量对最终结果的影响

--公式：

 

可以看出信息增益比是 信息增益 / HA(D)

其中HA(D)

 

Di表示的是样本中分类为i的样本个数

D表示总样本个数

根节点分层方法

即是先使用哪些特征来做根节点，后使用哪些特征来做根节点

一般方法是计算所有特征的信息增益，按照信息增益大小，依次调用先选取最优的特征，然后用同样的方法选取次优的特征，直到满足预设的条件。

常见的有 2 种算法，ID3 和 C4.5。

ID3 是以信息增益为选择依据，C4.5 以信息增益比为算法依据。

二、决策树使用

理解上上面的概念，就可以使用决策树了，我们要使用的是升级的决策树：梯度迭代树，其实就是把多棵决策树集成起来，利用上一棵树来调整下一棵树。

梯度迭代树

将每次决策树的分类或者预测结果的误差来调整下一轮预测模型，调整方法是引入损失函数，调整方向是最小化这个损失。这个概念就是另外一部分的知识，有兴趣可以参考这个文章：https://www.cnblogs.com/pinard/p/6140514.html

代码实例：

from pyspark.ml import Pipeline
from pyspark.ml.classification import GBTClassifier
from pyspark.ml.feature import StringIndexer, VectorIndexer
from pyspark.ml.evaluation import MulticlassClassificationEvaluator,RegressionEvaluator
from pyspark.sql import HiveContext
from pyspark import SparkContext, SparkConf
sc = SparkContext.getOrCreate()
spark = HiveContext(sc)
data = spark.read.format("libsvm").load("F:\\AAAA-测试数据文件夹\\sample_libsvm_data.txt")

#=============label和feature的特征转换==============================================================================================
labelIndexer = StringIndexer(inputCol="label", outputCol="indexedLabel").fit(data)
# Automatically identify categorical features, and index them.
# maxCategories=4既是不重复取值个数小于maxCategories的时候，这些值被重新设置为0-k,k=maxCategories-1
featureIndexer = VectorIndexer(inputCol="features", outputCol="indexedFeatures", maxCategories=4).fit(data)
#=============特征转换 end===============================================================================================

#=============切分数据集为训练集、测试集=================================================================================
(trainingData, testData) = data.randomSplit([0.7, 0.3])
#=============数据集切分 end============================================================================================

#=============定义GDBT模型==============================================================================================
gbt = GBTClassifier(labelCol="indexedLabel", featuresCol="indexedFeatures", maxIter=10)
#=============模型定义 end==============================================================================================

#=============设置工作流pipline=========================================================================================
pipeline = Pipeline(stages=[labelIndexer, featureIndexer, gbt])
#=============工作流设置 end============================================================================================

#=============使用这个pipline，训练模型==================================================================================
model = pipeline.fit(trainingData)
#=============模型训练 end==============================================================================================

#=============使用测试集预测============================================================================================
predictions = model.transform(testData)
predictions.select("prediction", "indexedLabel", "features").show(5)
#============预测 end===================================================================================================

#============计算预测的准确率============================================================================================
# 这个计算准确率和RegressionEvaluator计算有啥区别？
#测试下：MulticlassClassificationEvaluator : 错误率：0.0571429，这个是计算错误率
#        RegressionEvaluator : 这个是计算验证结果的均值、方差这些
# evaluator = MulticlassClassificationEvaluator(
#     labelCol="indexedLabel", predictionCol="prediction", metricName="accuracy")
# accuracy = evaluator.evaluate(predictions)
# print("Test Error = %g" % (1.0 - accuracy))

evaluator = RegressionEvaluator(labelCol="indexedLabel", predictionCol="prediction", metricName="rmse")
rmse = evaluator.evaluate(predictions)
print("Root Mean Squared Error (RMSE) on test data = %g" % rmse)
#============准确率预测 end=============================================================================================