当前位置:   article > 正文

决策树及其python实现(机器学习)_micropython tree data

micropython tree data

1.决策树

1.1介绍

什么是决策树?

 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点有向边组成。结点有两种类型:内部结点叶节点。内部结点表示一个特征或属性,叶节点表示一个类

1.2 决策树学习的三个步骤

特征选择
特征选择决定了使用哪些特征来做判断。在训练数据集中,每个样本的属性可能有很多个,不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征,也就是分类能力较强的特征。
在特征选择中通常使用的准则是:信息增益。

决策树生成
选择好特征后,就从根节点触发,对节点计算所有特征的信息增益,选择信息增益最大的特征作为节点特征,根据该特征的不同取值建立子节点;对每个子节点使用相同的方式生成新的子节点,直到信息增益很小或者没有特征可以选择为止。

决策树剪枝
剪枝的主要目的是对抗「过拟合」,通过主动去掉部分分支来降低过拟合的风险。

      1.3 三种典型的决策树

ID3 算法

ID3 是最早提出的决策树算法,他就是利用信息增益来选择特征的。

C4.5 算法

他是 ID3 的改进版,他不是直接使用信息增益,而是引入“信息增益比”指标作为特征的选择依据。

CART(Classification and Regression Tree)

这种算法即可以用于分类,也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型。

1.3.1 ID3算法

1.信息熵

信息熵 ”是 度量样本集合纯度最常用的一种指标 ,假定当前样本集合 D 中第 k 类样本所占的比例为 p k ( K =1, 2, ..., | y |)  , D 的信息熵为
Ent\left ( D \right )=-\sum_{K=1}^{\left | y \right |}pk\log _{2}^{pk}

Ent(D)的值越小,则D的纯度越高

计算信息熵时约定:若p = 0,则plog2p=0

Ent(D)的最小值为0,最大值为log2|y|

2.信息增益

离散属性aV个可能的取值{a1, a2, ..., aV},用a来进行划分,则会产生V个分支结点,其中第v个分支结点包含了D中所有在属性a上取值av的样本,记为Dv。则可计算出用属性a对样本集D进行划分所获得的“信息增益”:

Gain\left ( D,a \right )=Ent\left ( D \right )-\frac{\left |D ^v \right |}{^{^{D}}}Ent\left ( D^v\right )

1.3.2C4.5算法

1.增益率

信息增益的缺点在于对取值数目较多的属性有所偏好

C4.5决策树算法不直接使用信息增益,而是使用增益率(gain ratio)来选择最优划分属性,用公式表述为:

Gain-ration(D,a)=\frac{Gain(D,a)}{IV(a)}

其中,G a i n ( D , a ) 同上文中的信息增益,
IV(a)=\sum_{v=1}^{V}\frac{\left | D^v \right |}{\left | D \right |}\log _{2}^{\frac{}{}}\frac{\left | D^v \right |}{\left | D \right |}

被称为特征a的固有值,属性a的取值越多 IV(a)的值越大,Gain_ration越小

1.3.3 CART

CART决策树与前面两个都不同,它采用基尼指数划分属性,计算公式如下

Ginin(D,a)=\sum_{k=1}^{\left | y \right |}p_{k}(1-p_{k})=1-\sum_{k=1}^{\left | y \right |}p_{k}^{2}

∣y∣表示类别个数

当做二分类时,公式可以简化为:

Ginin(D)=2p(1-p)

2.python实现

数据集使用西瓜数据集2.0

数据集链接

链接:https://pan.baidu.com/s/1trGDz9M1BT6reFzfXeEzkQ 
提取码:6666

ID3决策树基础代码实现
根据决策树算法,可知I3D决策树的算法流程如下:

先根据最大信息增益选取一个特征作为根节点
以根节点特征的取值作为分支递归生成节点,在递归中注意:
每次取特征值时需要删除之前取过的数据
当当前样本只有一类时,返回该类别作叶子结点,即分类结果
当当前所有样本的特征值都一样时,选样本最多的类作为叶子结点
使用测试特征测试决策树预测能力

  1. import pandas as pd
  2. import numpy as np
  3. #计算信息熵
  4. def cal_information_entropy(data):
  5. data_label = data.iloc[:,-1]
  6. label_class =data_label.value_counts() #总共有多少类
  7. Ent = 0
  8. for k in label_class.keys():
  9. p_k = label_class[k]/len(data_label)
  10. Ent += -p_k*np.log2(p_k)
  11. return Ent
  12. #计算给定数据属性a的信息增益
  13. def cal_information_gain(data, a):
  14. Ent = cal_information_entropy(data)
  15. feature_class = data[a].value_counts() #特征有多少种可能
  16. gain = 0
  17. for v in feature_class.keys():
  18. weight = feature_class[v]/data.shape[0]
  19. Ent_v = cal_information_entropy(data.loc[data[a] == v])
  20. gain += weight*Ent_v
  21. return Ent - gain
  22. #获取标签最多的那一类
  23. def get_most_label(data):
  24. data_label = data.iloc[:,-1]
  25. label_sort = data_label.value_counts(sort=True)
  26. return label_sort.keys()[0]
  27. #挑选最优特征,即信息增益最大的特征
  28. def get_best_feature(data):
  29. features = data.columns[:-1]
  30. res = {}
  31. for a in features:
  32. temp = cal_information_gain(data, a)
  33. res[a] = temp
  34. res = sorted(res.items(),key=lambda x:x[1],reverse=True)
  35. return res[0][0]
  36. ##将数据转化为(属性值:数据)的元组形式返回,并删除之前的特征列
  37. def drop_exist_feature(data, best_feature):
  38. attr = pd.unique(data[best_feature])
  39. new_data = [(nd, data[data[best_feature] == nd]) for nd in attr]
  40. new_data = [(n[0], n[1].drop([best_feature], axis=1)) for n in new_data]
  41. return new_data
  42. #创建决策树
  43. def create_tree(data):
  44. data_label = data.iloc[:,-1]
  45. if len(data_label.value_counts()) == 1: #只有一类
  46. return data_label.values[0]
  47. if all(len(data[i].value_counts()) == 1 for i in data.iloc[:,:-1].columns): #所有数据的特征值一样,选样本最多的类作为分类结果
  48. return get_most_label(data)
  49. best_feature = get_best_feature(data) #根据信息增益得到的最优划分特征
  50. Tree = {best_feature:{}} #用字典形式存储决策树
  51. exist_vals = pd.unique(data[best_feature]) #当前数据下最佳特征的取值
  52. if len(exist_vals) != len(column_count[best_feature]): #如果特征的取值相比于原来的少了
  53. no_exist_attr = set(column_count[best_feature]) - set(exist_vals) #少的那些特征
  54. for no_feat in no_exist_attr:
  55. Tree[best_feature][no_feat] = get_most_label(data) #缺失的特征分类为当前类别最多的
  56. for item in drop_exist_feature(data,best_feature): #根据特征值的不同递归创建决策树
  57. Tree[best_feature][item[0]] = create_tree(item[1])
  58. return Tree
  59. #{'纹理': {'清晰': {'根蒂': {'蜷缩': 1, '稍蜷': {'色泽': {'青绿': 1, '乌黑': {'触感': {'硬滑': 1, '软粘': 0}}}}, '硬挺': 0}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
  60. def predict(Tree, test_data):
  61. first_feature = next(iter(Tree))
  62. second_dict = Tree[first_feature]
  63. input_first = test_data.get(first_feature)
  64. if input_first is None:
  65. return None # 返回一个适当的默认值,表示无法进行分类
  66. input_value = second_dict.get(input_first)
  67. if input_value is None:
  68. return None # 返回一个适当的默认值,表示无法进行分类
  69. if isinstance(input_value, dict): #判断分支还是不是字典
  70. class_label = predict(input_value, test_data)
  71. else:
  72. class_label = input_value
  73. return class_label
  74. if __name__ == '__main__':
  75. #读取数据
  76. data = pd.read_csv(r'C:\Users\zhoutao\Desktop\data_word.csv')
  77. #统计每个特征的取值情况作为全局变量
  78. column_count = dict([(ds, list(pd.unique(data[ds]))) for ds in data.iloc[:, :-1].columns])
  79. #创建决策树
  80. dicision_Tree = create_tree(data)
  81. print(dicision_Tree)
  82. #测试数据
  83. test_data_1 = {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '稍糊', '脐部': '凹陷', '触感': '硬滑'}
  84. test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}
  85. result = predict(dicision_Tree, test_data_2)
  86. if result is None:
  87. print('无法分类')
  88. else:
  89. print('分类结果为' + '好瓜' if result == 1 else '坏瓜')

c4.5决策树基础代码实现

基本上和ID3一样只是特征选取部分需要修改

原先的代码(将以下的代码修改即可)

  1. #获取标签最多的那一类
  2. def get_most_label(data):
  3. data_label = data.iloc[:,-1]
  4. label_sort = data_label.value_counts(sort=True)
  5. return label_sort.keys()[0]
  6. #挑选最优特征,即信息增益最大的特征
  7. def get_best_feature(data):
  8. features = data.columns[:-1]
  9. res = {}
  10. for a in features:
  11. temp = cal_information_gain(data, a)
  12. res[a] = temp
  13. res = sorted(res.items(),key=lambda x:x[1],reverse=True)
  14. return res[0][0]

这是修改好的代码

  1. def cal_gain_ratio(data , a):
  2. #先计算固有值intrinsic_value
  3. IV_a = 0
  4. feature_class = data[a].value_counts() # 特征有多少种可能
  5. for v in feature_class.keys():
  6. weight = feature_class[v]/data.shape[0]
  7. IV_a += -weight*np.log2(weight)
  8. gain_ration = cal_information_gain(data,a)/IV_a
  9. return gain_ration
  10. #获取标签最多的那一类
  11. def get_most_label(data):
  12. data_label = data.iloc[:,-1]
  13. label_sort = data_label.value_counts(sort=True)
  14. return label_sort.keys()[0]
  15. #挑选最优特征,即在信息增益大于平均水平的特征中选取增益率最高的特征
  16. def get_best_feature(data):
  17. features = data.columns[:-1]
  18. res = {}
  19. for a in features:
  20. temp = cal_information_gain(data, a)
  21. gain_ration = cal_gain_ratio(data,a)
  22. res[a] = (temp,gain_ration)
  23. res = sorted(res.items(),key=lambda x:x[1][0],reverse=True) #按信息增益排名
  24. res_avg = sum([x[1][0] for x in res])/len(res) #信息增益平均水平
  25. good_res = [x for x in res if x[1][0] >= res_avg] #选取信息增益高于平均水平的特征
  26. result =sorted(good_res,key=lambda x:x[1][1],reverse=True) #将信息增益高的特征按照增益率进行排名
  27. return result[0][0] #返回高信息增益中增益率最大的特征

3.小结

增益率会对可取值数目较小的特征有偏好,为了避免这个问题,C4.5并不是直接使用增益率的大小进行划分特征,而是先从候选划分特征中找出信息增益高于平均水平的属性,再从中选择增益率最高的那个特征

参考文献

周志华《机器学习》

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/696257
推荐阅读
相关标签
  

闽ICP备14008679号