决策树（基于增益率）之python实现

柔情只为你懂 2023-06-02 09:12 121阅读 0赞

如图，为使用到的公式，信息熵表明样本的混乱程度，增益表示熵减少了，即样本开始分类，增益率是为了平衡增益准则对可取值较多的属性的偏好，同时增益率带来了对可取值偏小的属性的偏好，实际中，先用增益进行筛选，选取大于增益平均值的，然后再选取其中增益率最高的。

1254945-20190930001754338-1882954161.jpg

以下代码纯粹手写，未参考其他人代码，如果问题，请不吝赐教。

1，计算信息熵的函数

  1. import numpy as np
  2. # 计算信息熵
  3. # data:like np.array
  4. # data.shape=(num_data,data_features+1) 即属性与label放一起了
  5. def entropy(data,num_class):
  6.     class_set=list(set(data[:,-1]))
  7.     result=0
  8.     length=len(data)
  9. #     这里修改一下，不使用num_class
  10.     for i in range(len(class_set)):
  11.         l=len(data[data[:,-1]==class_set[i]])
  12.         p=l/length
  13.         result-=p*np.log2(p)
  14.     return result

2，计算增益及属性a的固有值（IV）

  1. # 计算不同属性的信息增益
  2. # detail_features：特征构成的list，每个特征的可取值构成list元素，即也是list
  3. def calculate_gain(data,detail_features,num_class):
  4. 　　'''返回各属性对应的信息增益及平均值'''
  5.     result=[]
  6.     ent_data=entropy(data,num_class)
  7.     for i in range(len(detail_features)):
  8.         res=ent_data
  9.         for j in range(len(detail_features[i])):
  10.             part_data=data[data[:,i]==detail_features[i][j]]
  11.             length=len(part_data)
  12.             res-=length*entropy(part_data,num_class)/len(data)
  13.         result.append(res)
  14.     return result,np.array(result).mean()
  15. # 计算某个属性的固有值
  16. def IVa(data,attr_index):
  17.     attr_values=list(set(data[:,attr_index]))
  18.     v=len(attr_values)
  19.     res=0
  20.     for i in range(v):
  21.         part_data=data[data[:,attr_index]==attr_values[i]]
  22.         p=len(part_data)/len(data)
  23.         res-=p*np.log2(p)
  24.     return res

3，构建节点类，以便构建树

  1. class Node:
  2.     def __init__(self,key,childs):
  3.         self.childs=[]
  4.         self.key=key
  5.     def add_node(self,node):
  6.         self.childs.append(node)

4，构建树

  1. # 判断数据是否在所有属性的取值都一样，以致无法划分
  2. def same_data(data,attrs):
  3.     for i in range(len(attrs)):
  4.         if len(set(data[:,i]))>1:
  5.             return False
  6.     return True
  8. # attrs:属性的具体形式
  9. def create_tree(data,attrs,num_class,root):
  10. #     注意这里3个退出条件
  11.     #     1，如果数据为空，不能划分，此时这个叶节点不知标记为哪个分类了
  12.     if len(data)==0:
  13.         return
  14. #   2，如果属性集为空，或所有样本在所有属性的取值相同，无法划分，返回样本最多的类别
  15.     if len(attrs)==0 or same_data(data,attrs):
  16.         class_set=list(set(data[:,-1]))
  17.         max_len=0
  18.         index=0
  19.         for i in range(len(class_set)):
  20.             if len(data[data[:,-1]==class_set[i]])>max_len:
  21.                 max_len=len(data[data[:,-1]==class_set[i]])
  22.                 index=i
  23.         root.key=root.key+class_set[index]
  24.         return 
  25. #     3，如果当前节点包含同一类的样本，无需划分
  26.     if len(set(data[:,-1]))==1:
  27.         root.key=root.key+data[0,-1]
  28.         return
  29.     ent=entropy(data,num_class)
  30.     gain_result,mean=calculate_gain(data,attrs,num_class)
  31.     max=0
  32.     max_index=-1
  33. #     求增益率最大
  34.     for i in range(len(gain_result)):
  35.         if gain_result[i]>=mean:
  36.             iva=IVa(data,i)
  37.             if gain_result[i]/iva>max:
  38.                 max=gain_result[i]/iva
  39.                 max_index=i
  40.     for j in range(len(attrs[max_index])):
  41.         part_data=data[data[:,max_index]==attrs[max_index][j]]
  42. #         删除该列特征
  43.         part_data=np.delete(part_data,max_index,axis=1)
  44. #         添加节点
  45.         root.add_node(Node(key=attrs[max_index][j],childs=[]))
  46. #         删除某一类已判断属性
  47.         new_attrs=attrs[0:max_index]
  48.         new_attrs.extend(attrs[max_index+1:])
  49.         create_tree(part_data,new_attrs,num_class,root.childs[j])

5，使用西瓜数据集2.0测试，数据这里就手写了，比较少

  1. def createDataSet():
  2.     """
  3.     创建测试的数据集
  4.     :return:
  5.     """
  6.     dataSet = [
  7.         # 1
  8.         ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
  9.         # 2
  10.         ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
  11.         # 3
  12.         ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
  13.         # 4
  14.         ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
  15.         # 5
  16.         ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
  17.         # 6
  18.         ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],
  19.         # 7
  20.         ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],
  21.         # 8
  22.         ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],
  24.         # ----------------------------------------------------
  25.         # 9
  26.         ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],
  27.         # 10
  28.         ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],
  29.         # 11
  30.         ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],
  31.         # 12
  32.         ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],
  33.         # 13
  34.         ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],
  35.         # 14
  36.         ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],
  37.         # 15
  38.         ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],
  39.         # 16
  40.         ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],
  41.         # 17
  42.         ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']
  43.     ]
  45.     # 特征值列表
  46.     labels = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']
  48.     # 特征对应的所有可能的情况
  49.     labels_full = []
  51.     for i in range(len(labels)):
  52.         items=[item[i] for item in dataSet]
  53.         uniqueLabel = set(items)
  54.         labels_full.append(list(uniqueLabel))
  55.     return np.array(dataSet), labels, labels_full

6，开始构建树

  1. dataset,labels,labels_full=createDataSet()
  3. root=Node('',[])
  4. create_tree(dataset, labels_full, 2, root)

7，打印树结构

  1. def print_root(n,root):print(n,root.key)
  2.     for node in root.childs:
  3.         print_root(n+1,node)
  4. print_root(0,root)

打印结果为：数字表示层次

  1. 0 
  2. 1 模糊坏瓜
  3. 1 稍糊
  4. 2 硬滑坏瓜
  5. 2 软粘好瓜
  6. 1 清晰
  7. 2 硬滑好瓜
  8. 2 软粘
  9. 3 青绿
  10. 4 稍蜷好瓜
  11. 4 蜷缩
  12. 4 硬挺坏瓜
  13. 3 乌黑坏瓜
  14. 3 浅白

8，绘制树形结构，这里我就手动绘制了。图中有2个叶节点为空白，即模型不知道该推测其为好瓜还是坏瓜。这里我暂时没有好的思路解决，只能随机处理？

1254945-20190930003445547-1304609911.jpg

9，总结

首先，暂时没有添加predict函数。其次，这是个简陋版的实现，有很多待优化的地方，如连续值处理、缺失值处理、剪枝防止过拟合，树的创建使用的是递归（样本大导致栈溢出，改成队列实现较好），也有基于基尼指数的实现，还有多变量决策树（可实现复杂的分类边界）。

转载于:https://www.cnblogs.com/lunge-blog/p/11610661.html

发表评论

表情：
评论列表 （有 0 条评论，121人围观）

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

相关阅读