机器学习方法之决策树

╰半夏微凉° 2022-02-27 05:00 514阅读 0赞

决策树是一个类似于流程图的树结构:其中,每个内部结点表示在一个属性上的测试,每个分支代表一个属性输出,而每个树叶结点代表类或类分布。树的最顶层是根结点。

1.png
上图中是否出去玩取决于天气情况(sunny、overcast、rain)和空气湿度(humidity、windy)这2个属性的值。

信息熵

决策树算法种类很多,本文主要介绍ID3算法。ID3算法在1970-1980年,由J.Ross. Quinlan提出。在介绍决策树算法前,我们先引入熵(entropy)的概念。

信息和抽象,具体该如何度量呢?1948年,香农提出了**信息熵(entropy)**的概念。
一条信息的信息量大小和它的不确定性有直接的关系,要搞清楚一件非常非常不确定的事情,或者是我们一无所知的事情,需要了解大量信息==>信息量的度量就等于不确定性的多少。
我们用比特(bit)来衡量信息的多少,变量的不确定性越大,熵也就越大。计算公式如下,其中 P ( x i ) P(x_i) P(xi)表示每种事件发生的可能性。

9.png

ID3算法

该算法在选择每一个属性判断结点的时候是根据信息增益(Information Gain)。通过下面公式可以计算A来作为节点分类获取了多少信息。
G a i n ( A ) = I n f o ( D ) − I n f o A ( D ) Gain(A) = Info(D) - InfoA(D) Gain(A)=Info(D)−InfoA(D)

2.png
上图是一个买车的实例,一个人是否买车取决于他的年龄、收入、信用度和他是否是学生。下图(右)是原始数据,下图(左)是简单的决策树划分。那我们是如何确定age作为第一个属性结点的呢?
一共有14条数据,其中9人买车,5人没买车,所以根据公式可以算出 I n f o ( D ) Info(D) Info(D)的值。接着我们计算选择age作为属性结点的信息熵。age有三个取值,其中youth有5条信息(2人买车,3人没买),middle_aged有4条信息(全部买车),senior有5条信息(3人买车,2人没买),所以根据公式可以算出 I n f o a g e ( D ) Info_{age}(D) Infoage(D)和 G a i n ( a g e ) Gain(age) Gain(age)的值,如下所示:

3.png
4.png
5.png
类似, G a i n ( i n c o m e ) = 0.029 , G a i n ( s t u d e n t ) = 0.151 , G a i n ( c r e d i t r a t i n g ) = 0.048 Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048 Gain(income)=0.029,Gain(student)=0.151,Gain(creditrating)=0.048
所以,选择age作为第一个根节点。重复。。。

最终我们得到了如下所示的决策树。
6.png

算法流程

  1. 从根节点出发,根节点包括所有的训练样本。
  2. 一个节点(包括根节点),若节点内所有样本均属于同一类别,那么将该节点就成为叶节点,并将该节点标记为样本个数最多的类别。
  3. 否则利用采用信息增益法来选择用于对样本进行划分的特征,该特征即为测试特征,特征的每一个值都对应着从该节点产生的一个分支及被划分的一个子集。在决策树中,所有的特征均为符号值,即离散值。如果某个特征的值为连续值,那么需要先将其离散化。
  4. 递归上述划分子集及产生叶节点的过程,这样每一个子集都会产生一个决策(子)树,直到所有节点变成叶节点。
  5. 递归操作的停止条件就是:

(1) 一个节点中所有的样本均为同一类别,那么产生叶节点
(2) 没有特征可以用来对该节点样本进行划分,这里用attribute_list=null为表示。此时也强制产生叶节点,该节点的类别为样本个数最多的类别
(3) 没有样本能满足剩余特征的取值,即test_attribute=a_i 对应的样本为空。此时也强制产生叶节点,该节点的类别为样本个数最多的类别

l流程图如下所示:
7.png

代码实现

  1. from sklearn.feature_extraction import DictVectorizer
  2. import csv
  3. from sklearn import tree
  4. from sklearn import preprocessing
  5. import pydotplus
  6. #读入csv文件
  7. Extradata = open("G:/PycharmProjects/Machine_Learning/Decision_Tree/AllElectronics.csv","r",encoding="utf-8")
  8. reader = csv.reader(Extradata)
  9. headers = next(reader) #逐行读取数据 python3中为nex(),python2 中为reader.next()
  10. #print(headers)
  11. featureList = [] #特征列表
  12. labelList = [] #标签列表
  13. for row in reader:
  14. labelList.append(row[len(row)-1]) #读取每行数据最后一列的标签,存入标签列表
  15. rowDict = {
  16. } #创建字典,存储每行特征数据
  17. for i in range(1,len(row)-1):#从第2列开始到倒数第2列读取特征数据
  18. rowDict[headers[i]] = row[i] #对应键值对存储数据
  19. featureList.append(rowDict) #将每行特征数据字典存入特征列表
  20. #print(featureList)
  21. #向量化特征数据
  22. vec = DictVectorizer()
  23. dum_X = vec.fit_transform(featureList).toarray()
  24. # print("dum_X: " + str(dum_X))
  25. # print(vec.get_feature_names())
  26. #
  27. # print("labelList: " + str(labelList))
  28. ##向量化标签数据
  29. label = preprocessing.LabelBinarizer()
  30. dum_Y = label.fit_transform(labelList)
  31. #print("dum_Y: " + str(dum_Y))
  32. #调用sklearn方法构建决策树
  33. classfiy = tree.DecisionTreeClassifier(criterion='entropy')
  34. classfiy = classfiy.fit(dum_X,dum_Y)
  35. #print("classfiy: " + str(classfiy))
  36. #将决策树存为dot文件
  37. with open("G:/PycharmProjects/Machine_Learning/Decision_Tree/AllElectronics.dot", 'w') as f:
  38. f = tree.export_graphviz(classfiy,feature_names=vec.get_feature_names(),out_file=f)
  39. #可视化决策树的模型,并存为pdf文件
  40. dot_data = tree.export_graphviz(classfiy,out_file=None)
  41. graph = pydotplus.graph_from_dot_data(dot_data )
  42. graph.write_pdf("aa.pdf")
  43. #验证决策树分类模型
  44. oneRow_X = dum_X[0,:]
  45. #print("oneRow_X: " + str(oneRow_X))
  46. newRow_X = oneRow_X
  47. #修改特征数据的值
  48. newRow_X[0] = 1
  49. newRow_X[2] = 0
  50. newRow_X[3] = 1
  51. newRow_X[4] = 0
  52. #print("newRow_X: " + str(newRow_X))
  53. finalRow_X = newRow_X.reshape(1,10) #将一位数组转换为二维数组
  54. predict_Y = classfiy.predict(finalRow_X) #调用决策树模型预测,注意,finalRow_X要求二维
  55. #predict_Y = classfiy.predict([[1., 0., 0., 0., 1., 1., 0., 0., 1., 0.]])
  56. print("predict_Y: " + str(predict_Y))

代码中预测结果见下图:
10.png

最后生成的决策树模型见下图:
8.png

其他决策树算法

  1. C4.5: Quinlan
    Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)
    **共同点:**都是贪心算法,自上而下(Top-down approach)
    **区别:**属性选择度量方法不同: C4.5 (gain ratio), CART(gini index), ID3 (Information Gain)









































算法 支持模型 树结构 特征选择 连续值处理 缺失值处理 剪枝
ID3 分类 多叉树 信息增益 不支持 不支持 不支持
C4.5 分类 多叉树 信息增益比 支持 支持 支持
CART 分类、回归 二叉树 基尼系数、均方差 支持 支持 支持

决策树的优缺点

优点

  1. 简单直观,生成的决策树很直观。
  2. 基本不需要预处理,不需要提前归一化,处理缺失值。
  3. 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
  4. 可以处理多维度输出的分类问题。
  5. 相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以得到很好的解释
  6. 可以交叉验证的剪枝来选择模型,从而提高泛化能力。

缺点

  1. 决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
  2. 决策树会因为样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
  3. 寻找最优的决策树是一个NP难的问题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习之类的方法来改善。
    4.有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。
  4. 如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

参考资料

Scikit-learn中的决策树

发表评论

表情:
评论列表 (有 0 条评论,514人围观)

还没有评论,来说两句吧...

相关阅读

    相关 机器学习决策算法

    1-1 基本流程 决策树是一个有监督分类与回归算法。 决策树的生成只考虑局部最优,相对的,决策树剪枝则考虑全局最优。 一、概念: 决策树:是一种树形结构,其中每个

    相关 机器学习-决策

    决策树是常见的机器学习算法。类似于人类在面临决策问题时的自然处理机制,是基于树结构来进行决策的。例如,我们要对“这是好瓜吗?”的问题进行决策,通常会进行一系列的子决策:我们会先

    相关 机器学习实战决策

    你是否玩过二十个问题的游戏,游戏的规则很简单:参与游戏的一方在脑海里想某个事物,其他参与者向他提问题,只允许提20个问题,问题的答案也只能用对或错回答。问问题的人通过 推断分解

    相关 机器学习决策

    决策树 【关键词】树,熵,信息增益 决策树的优缺点 优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。既能用于分类,也能用

    相关 机器学习方法决策

    决策树是一个类似于流程图的树结构:其中,每个内部结点表示在一个属性上的测试,每个分支代表一个属性输出,而每个树叶结点代表类或类分布。树的最顶层是根结点。 ![1.png][]