Hi,手机边的你还好吗?上篇推文给大家简单介绍了下逻辑回归,大家都知道逻辑回归既可以做分类也可以做回归,也是在我们实际工作中应用比较广且模型准确的较好一个模型。今天再给大家在介绍一个应用性广且既可分类也可回归的算法:决策树。本文主要介绍分类决策树。
1、决策树
决策树基本上是每一本机器学习入门书籍必讲的东西,其决策过程和平时我们的思维很相似,所以非常好理解,同时有一堆信息论的东西在里面。决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树由结点(node)和 有向边(directed edge)组成。结点有两种类型:内部结点(internal node)和叶节点(leaf node)。内部结点表示一个特征或属性,叶节点表示一个类。一般的,一颗决策树包含一个根结点、若干个内部结点和若干个叶结点,叶结点对应于决策结果,其他每个结点则对应于一个属性测试,每个结点包含的样本集合根据属性测试的结果被划分到子结点中,根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列,决策树学习的目的是为了产生一颗泛化能力强,即处理未见示例能力强的决策树。
例如:当我们在超市买西瓜的时候如何判断一个西瓜是否好瓜?通常我们会进行一系列判断决策,比如看西瓜的色泽、根蒂、敲声等等,当我们判断西瓜色泽为青绿的时候我们会进一步看其根蒂,如果根蒂蜷缩,我们再去根据其敲声判断是否好瓜,这就是一个决策过程。生成一颗西瓜问题的决策树如下图所示,色泽、根蒂、敲声是决策树内部结点,而决策结果好瓜或坏瓜是叶子结点。
周志华老师一书中强调:
决策树的生成是一个递归过程。在决策树算法中有三种情形会导致递归返回:
(1)当前节点包含的样本全部属于同一个类别,无需划分。
(2)当前属性集为空,或是所有样本在所有属性集上取值相同,无法划分。此时,把当前节点标记为叶节点,并将其类别设定为该节点所含样本最多的类别。
(3)当前节点包含的样本集合为空,不能划分。此时,同样把当前节点标记为叶节点,但将其类别设定为其父节点所含样本最多的类别。
注意:(2)和(3)不同,(2)是后验概率,(3)是把父节点的样本分布作为当前节点的先验概率。
2、ID3(信息增益)
先看一个定义,信息熵:度量样本集合纯度最常用指标,假定当前样本集合D中第k类样本所占的比例为Pk(k=1,2,…,|y|),则D的信息熵为:
E(D)值越小,则D的纯度越高。
而对于样本离散属性,用a对样本进行划分得到样本D,所以属性a划分样本集D获得的信息增益为:
信息增益Gain(D,a)越大,则属性a来划分样本获得的纯度提升越大。
注:该部分的示例求解可参考周志华P75,简单也易懂。
3、C4.5(信息增益率)
ID3的信息增益划分法对可取数值较多的属性有所偏好,为减少这种偏好可能带来的不利影响,C4.5算法不采用信息增益,取而代之的是信息增益率来选择最优划分特征属性。信息增益率定义为:
其中:
IV(a)称为属性a的“固有值”。属性a的可能值数目越多(即V越大),则IV(a)的值通常会越大。
4、基尼系数(CART树)
CART决策树是一棵二叉树,内部节点特征取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支。CART决策树使用“基尼系数”来选择划分属性。基尼系数的定义如下:
那么对于属性a其基尼系数即为:
Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率。因此,Gini(D)越小,则数据集D的纯度越高。
以上就是决策树的一些基础原理,有讲的不明白的可以参考:
[1] 周志华. 机器学习 : Machinelearning[M]. 清华大学出版社, 2016.
[2] Peter. 机器学习实战[M]. 人民邮电出版社
[3] https://blog.csdn.net/ice_martin/article/details/63683657
5、Python实例
下面根据实例给出python代码:
(这个例子是经典案例,利用鸢尾花数据iris,对鸢尾花进行分类。)
(1)依据原理公式,直接python实现
由于该处代码较多,看起来比较枯燥这里就不给大家直接呈现了,如有想了解的小伙伴可以通过访问我的github查看,github地址:https://github.com/superzhang90/Meet-Algorithm/blob/master/DecisionTree/DecisionTree_20180603.py
(2)引入python中scikit-learn机器学习库
#通过sklearn包进行分类
from sklearn importdatasets #导入方法类
fromsklearn.cross_validation import train_test_split
from sklearn.metricsimport accuracy_score
from sklearn.treeimport DecisionTreeClassifier
import numpy as np
import matplotlib.pyplotas plt
#加载iris 数据集
iris =datasets.load_iris('E:\Python\work\iris.txt')
#特征数据
iris_feature = iris[0]
#分类数据
iris_target = iris[1]##该处sklearn已经将分类自动转成0,1,2
feature_train,feature_test, target_train, target_test = train_test_split(iris_feature,iris_target, test_size=0.33, random_state=42)
# 参数均置为默认状态
dt_model =DecisionTreeClassifier()
# 使用训练集训练模型
dt_model.fit(feature_train,target_train)
# 使用模型对测试集进行预测
predict_results =dt_model.predict(feature_test)
print(accuracy_score(predict_results, target_test))
#获取花卉两列数据集
X = feature_test
L1 = [x[0] for x inX]
print (L1)
L2 = [x[1] for x inX]
print (L2)
#画出数据分布情况
plt.scatter(L1, L2,c=predict_results, marker='x') #cmap=plt.cm.Paired
plt.title("DTC")
plt.show()
以上就是今天介绍的决策树的三种经典方法,对于决策树的剪枝问题,下次推文的时候会详细介绍下,谢谢您的阅读!
如需要原数据及源代码,可关注公众号:遇见YI算法,发送消息给小哪吒。
也可关注我的github:
https://github.com/superzhang90/Meet-Algorithm/blob/master/DecisionTree/DecisionTree_20180603.py
领取专属 10元无门槛券
私享最新 技术干货