决策树问题

2022-03-25

5分钟阅读时长

原理

简要描述一下决策树的原理
1. 决策树解决二分类问题时，每一次决策都选择一种最佳属性进行划分，最终得到结果。
2. 为了得到最佳划分，就需要在每次划分中获得更多的信息，引入信息熵（信息的混乱程度）来刻画划分过程中获得的信息量大小；
3. 信息熵根据信息整体的随机变量进行定义，度量的是整体信息的混乱程度，因此当需要对某种属性进行划分时就需要条件熵；
4. 根据在数据集整体上分类的不确定性（经验熵）减去在数据集上根据属性A分类的不确定性（条件熵）称为信息增益。信息增益越大，分类能力就越强。
5. 使用信息增益，分类器会倾向于选择每个类别更少的样本的分类方式（比如说样本编号、网络端口），为了消除这种影响，将信息增益除以原来的熵，使划分结果更加科学。每步中都计算每个特征的信息增益比，选取信息增益比最大的特征作为最佳划分特征。
6. 连续值离散化：连续型属性的值从小到大进行排序，计算各区间的中位点，组成候选划分点，依次计算以这些划分点划分的信息增益，当信息增益最大时选择此划分点作为该属性的最佳划分点

决策树数据处理

dataSet=np.concatenate((x_train, y_train), axis=1)
dataSet=dataSet.tolist()
testSet=np.concatenate((x_test, y_test), axis=1)
testSet=testSet.tolist()

实现思路

计算信息熵

输入：数据集dataSet，特征值索引labelIndex

输出：对应的信息熵shannonEnt；
划分数据集

输入：数据集dataSet，列索引axis （按哪个特征划分） ，划分特征的值value，属性离散/连续

输出：
1. 若为离散属性，则返回属性值相等的样本去掉该列属性之后合并成的数据集
2. 若为连续属性，则分别返回小于和大于该属性值的样本去掉该列属性之后合并成的数据集
计算信息增益

输入：数据集dataSet，特征值索引labelIndex，特征值类型labelPropertyi（离散/连续）

算法：
1. 计算根节点的信息熵（作为原信息熵）
2. 获得特征值列表（使用set函数去除重复值，注意去除后数据类型为元组）
3. 对离散的特征：
  
  对每个特征值，都尝试划分数据集，计算其信息熵
4. 对连续的特征：
  
  用list函数将元组转为列表；
  
  用sort函数对特征值排序；
  
  特别地，如果只有一个值，就视作是只有左子集而无右子集，对其进行划分并计算信息熵；
  
  对每两个相邻的值计算平均值，以此作为划分点计算划分后的数据集的信息熵，按样本个数加权相加，取其中距离零点的信息熵（因为信息熵算的是负数因此这里取最小的）；
输出：信息增益gain
计算信息增益比率

输入：数据集dataSet，特征值索引labelIndex，特征值类型labelPropertyi（离散/连续）

算法：
1. 类似计算信息增益；
2. 信息增益除以经验熵得到信息增益比率；
3. 记录最佳划分点；
输出：信息增益比率gainRatio，最佳划分点bestPartVaulei
选择最佳划分方式

输入：数据集，特征值类型离散/连续

算法：
1. 对每个特征循环：
  
  调用计算信息增益比率函数求解出信息增益比率；同时信息增益比率函数调用信息增益函数求解各信息增益；
2. 求出平均信息增益，取信息增益大于平均增益及信息增益比率最大的划分点
输出：最佳划分属性的索引和划分值

返回出现次数最多的类别（多数表决）

使用字典存储各个类别，统计它们出现的次数:

classCount = {}
    for i in range(len(classList)):
        if classList[i] not in classCount.keys():
            classCount[classList[i]] = 0
        classCount[classList[i]] += 1

按值对字典排序。

sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1), reverse=True)

返回最多的类别和数量

return(sortedClassCount[0][0], sortedClassCount[0][1])

递归创建决策树

输入：数据集dataSet，特征labels，特征属性离散/连续

算法：

首先得到所有的类别向量（特征向量）；
1. 如果只有一个类别，返回类别和数量；
2. 如果所有的特征都被遍历完了（每次划分的特征会被移除到数据集外），则返回最多的类别和数量；
3. 如果无法通过划分选出最优的特征，返回出现次数最多的类别；
使用字典构建决策树：
1. 根节点为最佳划分点，划分点内容判断的是值是否小于特征；
2. 左子树为对小于最佳划分点创建决策树；
3. 右子树为对大于最佳划分点创建决策树；
最后返回根节点；

输出：决策树
决策树节点测试

输入：决策树某节点，标签classList，特征labels，特征属性labelProperties，测试样本testVec

算法：

获得当前节点和其子树，每个结点都是一个条件判断语句，小于号左边是划分特征，小于号右边是值；
1. 使用dict.keys()方法得到当前节点的划分，类型为dict，使用list()[0]将该划分转为字符串；
2. 使用str().find('<')方法找到小于号所在的位置，作为索引lessIndex；
3. 使用str()[:lessIndex]得到根据哪个特征划分；
4. 使用list.index()方法找到该特征划分的索引值；
5. 通过取字典的该特征键值对，获得子树；
进入子树：
1. 使用dict.keys()得到子树的键，Y或者N；
2. 条件值为str()[lessIndex+1:]；
3. 判断下一级子树类型是不是字典：
  1. 是字典则分支不是叶子结点，将Y或者N的子树作为节点，递归；
  2. 不是字典则分支是叶子节点，返回标签；
输出：标签

注释：程序中是返回标签字典，取字典中非0值的键作为标签；
决策树测试

输入：决策树根节点，标签classList，测试集dataTest，特征labels，特征属性labelProperties离散/连续

算法：遍历测试集，对每个测试集样本调用决策树节点测试，返回标签（见8的注释）与测试集的标签比对，不符合则错误个数增加；

输出：错误个数；
求分类正确率

输入：错误个数，总样本个数

输出：正确率

决策树问题

原理

实现思路

坐忘道琼峰 Sitting Oblivion Tao EndlessPeak

本页内容