机器学习——决策树(2020最新版)

左手的ㄟ右手 2022-11-26 01:53 215阅读 0赞

1、什么是决策树(Decision Tree)

20200810114437366.png

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70

2、决策树算法发展

20200810114515812.png

3、决策树的例子

根据age、income、student、credit_rating属性来推断是否会买电脑:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 1

然后画出如下的决策树:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 2

4、熵(entropy)的概念

20200810114655725.png

(1) 熵其实可以代表不确定性,如果一个事情的熵越大,代表不确定性越大;熵越小,说明事情是比较确定的。

4.1 信息熵的计算

20200810114729159.png

所以分别得到骰子A、B、C的信息熵:

20200810114757217.png

所以有骰子ABC可知,信息熵越大,不确定性越大。

5、ID3算法(选择根节点的算法)

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 3

(1) 把信息增益最大的那个作为根节点,如下图,age的信息增益最大,为0.246,即age为根节点。

20200810114859987.png

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 4

再分别累计使用ID3算法选择下一个节点的根节点:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 5

6、连续变量的处理、C4.5算法的提出

20200810115007614.png

(2) ID3算法比较倾向选择分支数(属性值)比较多的那个参数(下面图中age是三个属性值,而students、credit-rating、income都只有两个属性值)

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 6

而为了优化这种倾向于选择因子数较多的变量的特点,提出来C4.5算法:

20200810115052407.png

7、决策树的一个例子ID3 algorithm(dataset:是否要购买电脑)+如何画决策树

  1. # -*- coding: utf-8 -*- #
  2. """
  3. -------------------------------------------------------------------------------
  4. FileName: decision_tree_ID3
  5. Author: newlinfeng
  6. Date: 2020/8/3 0003 10:17
  7. Description: 使用是否购买电脑的数据集,来构建一个决策树例子(ID3)
  8. -------------------------------------------------------------------------------
  9. """
  10. from sklearn.feature_extraction import DictVectorizer
  11. from sklearn import tree
  12. from sklearn import preprocessing
  13. import csv
  14. #读入数据
  15. Dtree = open(r'AllElectronics.csv', 'r')
  16. #这次不是使用numpy来读(如果都是数字,可以使用这种方式来读,但现在这个csv里面都是字符,需要使用csv来读取),而是使用csv来读
  17. reader = csv.reader(Dtree)
  18. #获取第一行数据
  19. #__next__():读取文件里面的第一行
  20. headers = reader.__next__()
  21. print(headers)
  22. #定义两个列表
  23. featureList = [] #保存特征的
  24. labelList = [] #保存标签的
  25. for row in reader: #每次从reader里面读取一行
  26. #把label存入list
  27. labelList.append(row[-1]) #拿到每一行的最后一列的数据存入标签的list中
  28. rowDict = {} #定义了一个空的字典
  29. for i in range(1, len(row)-1): #某一行的每一列(除第一行,最后一列以外)对应元素遍历,存入rowDict中
  30. #建立一个数据字典
  31. rowDict[headers[i]] = row[i]
  32. #把数据字典存入list
  33. featureList.append(rowDict) #再将每个rowDict保存到特征list
  34. print('特征List初始化后的值:', featureList)
  35. print('标签List初始化后的值:', labelList)
  36. #由于算法无法使用字符来进行计算和分析,只能使用数字,所以需要将上面的数据进行转化
  37. vec = DictVectorizer() #这个DictVectorizer类主要是将字典结构的字符转换为数字形式
  38. x_data = vec.fit_transform(featureList).toarray()
  39. print('featureList数字化转换成x_data: ' + str(x_data))
  40. #打印属性名称
  41. print(vec.get_feature_names())
  42. #打印标签list
  43. print("labelList:"+str(labelList))
  44. #把标签转换成01表示
  45. lb = preprocessing.LabelBinarizer()
  46. y_data = lb.fit_transform(labelList)
  47. print("labelList转换后的y_data:"+str(y_data) )
  48. #创建一个决策树模型
  49. # DecisionTreeClassifier:决策树分类器;criterion属性表示使用不同的算法,默认是gini的方式,这里是entropy是信息熵的方式
  50. model = tree.DecisionTreeClassifier(criterion='entropy')
  51. #输入数据建立模型
  52. model.fit(x_data, y_data)
  53. #测试
  54. x_test = x_data[0] #选取x_data中的第0行元素
  55. print("x_test:", str(x_test))
  56. #reshape() 把x_test从一维数据变成二维数据
  57. predict = model.predict(x_test.reshape(1, -1))
  58. print("predict:"+str(predict))
  59. '''
  60. 导出决策树
  61. @todo:
  62. 1.pip install graphviz
  63. 2.http://www.graphviz.org
  64. '''
  65. import graphviz #http://www.graphviz.org
  66. dot_data = tree.export_graphviz(model,
  67. out_file=None,
  68. feature_names=vec.get_feature_names(),
  69. class_names=lb.classes_,
  70. filled=True,
  71. rounded=True,
  72. special_characters=True)
  73. graph = graphviz.Source(dot_data)
  74. graph.render('computer')

(1) 这里需要注意,在第一次安装完毕graphviz之后,需要讲Pycharm重启一下,否则画图会报如下错误:

  1. graphviz.backend.ExecutableNotFound: failed to execute ['dot', '-Tpdf', '-O', 'cart'], make sure the Graphviz executables are on your systems' PATH

最终决策树的pdf文件为:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 7

7、CART算法

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 8

7.1 CART算法举例

20200810115314961.png

20200810115331140.png

第一步:

20200810115351949.png

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 9

第二步:

20200810115421864.png

20200810115436562.png

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 10

20200810115507773.png

20200810115531890.png

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 11

20200810115604829.png

最后构建的CART:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 12

8、抵抗决策树的过拟合问题:决策树的剪枝

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 13

9、决策树的优缺点

20200810120032816.png

10、使用CART算法来实现决策树的一个问题

  1. # -*- coding: utf-8 -*- #
  2. """
  3. -------------------------------------------------------------------------------
  4. FileName: decision_tree_CART
  5. Author: newlinfeng
  6. Date: 2020/8/3 0003 22:22
  7. Description: 使用CART算法实现决策树的例子
  8. -------------------------------------------------------------------------------
  9. """
  10. from sklearn import tree
  11. import numpy as np
  12. #载入数据
  13. data = np.genfromtxt("cart.csv", delimiter=",")
  14. x_data = data[1:, 1:-1]
  15. y_data = data[1:, -1]
  16. #创建决策树模型
  17. model = tree.DecisionTreeClassifier()
  18. #输入数据建立模型
  19. model.fit(x_data, y_data)
  20. #导出决策树
  21. import graphviz
  22. dot_data = tree.export_graphviz(model,
  23. out_file=None,
  24. feature_names=['house_yes', 'house_no', 'single', 'married', 'divorced', 'income'],
  25. class_names=['no', 'yes'],
  26. filled=True,
  27. rounded=True,
  28. special_characters=True)
  29. graph = graphviz.Source(dot_data)
  30. graph.render('cart')

得到的decision tree的PDF:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 14

11、决策树-线性二分类(linear dichotomy)

  1. # -*- coding: utf-8 -*- #
  2. """
  3. -------------------------------------------------------------------------------
  4. FileName: linear_dichotomy
  5. Author: newlinfeng
  6. Date: 2020/8/4 0004 9:05
  7. Description: 使用决策树解决线性二分类的问题
  8. -------------------------------------------------------------------------------
  9. """
  10. import matplotlib.pyplot as plt
  11. import numpy as np
  12. from sklearn.metrics import classification_report
  13. from sklearn import tree
  14. #载入数据
  15. data = np.genfromtxt("LR-testSet.csv", delimiter=',')
  16. x_data = data[:, :-1]
  17. y_data = data[:, -1]
  18. plt.scatter(x_data[:, 0], x_data[:, 1], c=y_data)
  19. plt.show()
  20. #创建决策树模型
  21. model = tree.DecisionTreeClassifier()
  22. #输入数据建立模型
  23. model.fit(x_data, y_data)
  24. #导出决策树
  25. import graphviz
  26. dot_data = tree.export_graphviz(model,
  27. out_file=None,
  28. feature_names=['x', 'y'],
  29. class_names=['label0', 'label1'],
  30. filled=True,
  31. rounded=True,
  32. special_characters=True)
  33. graph = graphviz.Source(dot_data)
  34. #输入数据建立模型
  35. model.fit(x_data, y_data)
  36. #获取数据值所在的范围
  37. x_min, x_max = x_data[:, 0].min() - 1, x_data[:, 0].max()+1
  38. y_min, y_max = x_data[:, 1].min() - 1, x_data[:, 1].max()+1
  39. #生成网络矩阵
  40. xx, yy = np.meshgrid(np.arange(x_min, y_max, 0.02),
  41. np.arange(y_min, y_max, 0.02))
  42. #ravel与flatten类似,多维数组转一维。flatten不会改变原始数据,ravel会改变原始数据
  43. z = model.predict(np.c_[xx.ravel(), yy.ravel()])
  44. z = z.reshape(xx.shape)
  45. #等高线图
  46. cs = plt.contourf(xx, yy, z)
  47. #样本散点图
  48. plt.scatter(x_data[:, 0], x_data[:, 1], c=y_data)
  49. plt.show()
  50. predictions = model.predict(x_data)
  51. print(classification_report(predictions,y_data))

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 15

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 16

12、决策树-非线性二分类(non-linear dichotomy)/出现了过拟合

  1. # -*- coding: utf-8 -*- #
  2. """
  3. -------------------------------------------------------------------------------
  4. FileName: non-linear_dichotomy
  5. Author: newlinfeng
  6. Date: 2020/8/5 0005 15:16
  7. Description: 使用决策树解决非线性二分类
  8. -------------------------------------------------------------------------------
  9. """
  10. import matplotlib.pyplot as plt
  11. import numpy as np
  12. from sklearn.metrics import classification_report
  13. from sklearn import tree
  14. from sklearn.model_selection import train_test_split
  15. #载入数据
  16. data = np.genfromtxt("LR-testSet2.txt", delimiter=',')
  17. x_data = data[:, :-1]
  18. y_data = data[:, -1]
  19. plt.scatter(x_data[:, 0], x_data[:, 1], c=y_data)
  20. plt.show()
  21. #分割数据,默认情况下是3/4是训练集和训练集标签;1/4是测试集和测试集标签
  22. x_train, x_test, y_train, y_test = train_test_split(x_data, y_data)
  23. #创建决策树模型
  24. #max_depth, 树的深度
  25. #min_samples_split 内部节点再划分所需要最小样本数
  26. model = tree.DecisionTreeClassifier()
  27. #输入数据建立模型
  28. model.fit(x_train, y_train)
  29. #导出决策树
  30. import graphviz
  31. dot_data = tree.export_graphviz(model,
  32. out_file=None,
  33. feature_names= ['x', 'y'],
  34. class_names = ['label0', 'label1'],
  35. filled=True,
  36. rounded = True,
  37. special_characters=True)
  38. graph = graphviz.Source(dot_data)
  39. # graph.render('non-linear_dichotomy') #决策树导出为pdf
  40. #获取数据值所在的范围
  41. x_min, x_max = x_data[:, 0].min() - 1, x_data[:, 0].max()+1
  42. y_min, y_max = x_data[:, 1].min() - 1, x_data[:, 1].max()+1
  43. #生成网络矩阵
  44. xx, yy = np.meshgrid(np.arange(x_min, y_max, 0.02),
  45. np.arange(y_min, y_max, 0.02))
  46. #ravel与flatten类似,多维数组转一维。flatten不会改变原始数据,ravel会改变原始数据
  47. z = model.predict(np.c_[xx.ravel(), yy.ravel()])
  48. z = z.reshape(xx.shape)
  49. #等高线图
  50. cs = plt.contourf(xx, yy, z)
  51. #样本散点图
  52. plt.scatter(x_data[:, 0], x_data[:, 1], c=y_data)
  53. plt.show()
  54. #使用训练集预测效果非常好,几个标准都为1
  55. predictions = model.predict(x_train)
  56. print(classification_report(predictions,y_train))
  57. #使用训练集预测效果非常差,几个标准都为只有50%
  58. predictions = model.predict(x_test)
  59. print(classification_report(predictions,y_test))

决策树导出为PDF展示,结构较为复杂:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 17

描述的决策边界:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 18

最终结果却出现了过拟合:即:训练集中很好,测试集中表现很差,如下图:

训练集进行预测,很好:

20200810121027936.png

测试集进行预测,很差:

20200810121046744.png

12.1 使用剪枝来抵抗过拟合

剪枝的方式如下:

(1) 在DecisionTreeClassifier()方法中设置树的深度max_depth

20200810121125538.png

(2) 在DecisionTreeClassifier()方法中设置树的内部节点再划分所需要最小样本数min_samples_split

20200810121143505.png

经过上述的两个参数的修改,可以将评分从50%提高到80%左右,和之前使用逻辑回归得到的评价差不多:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld2xpbmZlbmc_size_16_color_FFFFFF_t_70 19

2020-08-10 更新

发表评论

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

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

相关阅读

    相关 机器学习-决策

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

    相关 机器学习基础--决策

    决策树是很基础很经典的一个分类方法,基本上很多工业中很使用且常用的算法基础都是决策树,比如boost,GBDT,CART(分类回归树),我们后需会慢慢分析,决策时定义如下: