2021-10-28

2021-10-28 决策树之挑选好西瓜

一、决策树
决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
样本数据如下：

二、将txt导入excel
创建一个空的xsl文件，以EXCEL打开：

点击数据中的自文本：

选择要导入的txt文件：

选择分隔符号和字符集：

选择空格：

确定：

成功导入：

三、用python求解
导入python模块：

import pandas as pd
import numpy as np
from collections import Counter
from math import log2

数据获取和处理函数：

#数据获取与处理
def getData(filePath):
    data = pd.read_excel(filePath)
    return data

def dataDeal(data):
    dataList = np.array(data).tolist()
    dataSet = [element[1:] for element in dataList]
    return dataSet

获取属性名称和类别标记：

#获取属性名称
def getLabels(data):
    labels = list(data.columns)[1:-1]
    return labels
#获取类别标记
def targetClass(dataSet):
    classification = set([element[-1] for element in dataSet])
    return classification

叶节点标记：

#将分支结点标记为叶结点，选择样本数最多的类作为类标记
def majorityRule(dataSet):
    mostKind = Counter([element[-1] for element in dataSet]).most_common(1)
    majorityKind = mostKind[0][0]
    return majorityKind

计算信息熵：

#计算信息熵
def infoEntropy(dataSet):
    classColumnCnt = Counter([element[-1] for element in dataSet])
    Ent = 0
    for symbol in classColumnCnt:
        p_k = classColumnCnt[symbol]/len(dataSet)
        Ent = Ent-p_k*log2(p_k)
    return Ent

构建子数据集：

#子数据集构建
def makeAttributeData(dataSet,value,iColumn):
    attributeData = []
    for element in dataSet:
        if element[iColumn]==value:
            row = element[:iColumn]
            row.extend(element[iColumn+1:])
            attributeData.append(row)
    return attributeData

计算信息增益：

#计算信息增益
def infoGain(dataSet,iColumn):
    Ent = infoEntropy(dataSet)
    tempGain = 0.0
    attribute = set([element[iColumn] for element in dataSet])
    for value in attribute:
        attributeData = makeAttributeData(dataSet,value,iColumn)
        tempGain = tempGain+len(attributeData)/len(dataSet)*infoEntropy(attributeData)
        Gain = Ent-tempGain
    return Gain

选择最优属性：

#选择最优属性                
def selectOptimalAttribute(dataSet,labels):
    bestGain = 0
    sequence = 0
    for iColumn in range(0,len(labels)):#不计最后的类别列
        Gain = infoGain(dataSet,iColumn)
        if Gain>bestGain:
            bestGain = Gain
            sequence = iColumn
        print(labels[iColumn],Gain)
    return sequence

建立决策树：

#建立决策树
def createTree(dataSet,labels):
    classification = targetClass(dataSet) #获取类别种类（集合去重）
    if len(classification) == 1:
        return list(classification)[0]
    if len(labels) == 1:
        return majorityRule(dataSet)#返回样本种类较多的类别
    sequence = selectOptimalAttribute(dataSet,labels)
    print(labels)
    optimalAttribute = labels[sequence]
    del(labels[sequence])
    myTree = {optimalAttribute:{}}
    attribute = set([element[sequence] for element in dataSet])
    for value in attribute:
        
        print(myTree)
        print(value)
        subLabels = labels[:]
        myTree[optimalAttribute][value] =  
                createTree(makeAttributeData(dataSet,value,sequence),subLabels)
    return myTree

def main():
    filePath = 'watermalon.xls'
    data = getData(filePath)
    dataSet = dataDeal(data)
    labels = getLabels(data)
    myTree = createTree(dataSet,labels)
    return myTree

mytree = main()

print(mytree)

最终结果：

四、使用ID3算法
1. ID3算法
ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。
2. 代码实现
数据集如下：

导入包和数据：

#导入相关库
import pandas as pd
import graphviz 
from sklearn.model_selection import train_test_split
from sklearn import tree

f = open('watermalon.csv','r')
data = pd.read_csv(f)

x = data[["色泽","根蒂","敲声","纹理","脐部","触感"]].copy()
y = data['好瓜'].copy()
print(data)

数据转换：

#将特征值数值化
x = x.copy()
for i in ["色泽","根蒂","敲声","纹理","脐部","触感"]:
    for j in range(len(x)):
        if(x[i][j] == "青绿" or x[i][j] == "蜷缩" or data[i][j] == "浊响" 
           or x[i][j] == "清晰" or x[i][j] == "凹陷" or x[i][j] == "硬滑"):
            x[i][j] = 1
        elif(x[i][j] == "乌黑" or x[i][j] == "稍蜷" or data[i][j] == "沉闷" 
           or x[i][j] == "稍糊" or x[i][j] == "稍凹" or x[i][j] == "软粘"):
            x[i][j] = 2
        else:
            x[i][j] = 3
            
y = y.copy()
for i in range(len(y)):
    if(y[i] == "是"):
        y[i] = int(1)
    else:
        y[i] = int(-1) 
#需要将数据x，y转化好格式，数据框dataframe，否则格式报错
x = pd.Dataframe(x).astype(int)
y = pd.Dataframe(y).astype(int)
print(x)
print(y)

建立模型并训练：

x_train, x_test, y_train, y_test = train_test_split(x,y,test_size=0.2)
print(x_train)

#决策树学习
clf = tree.DecisionTreeClassifier(criterion="entropy")                    #实例化 
clf = clf.fit(x_train, y_train) 
score = clf.score(x_test, y_test)
print(score)

画决策树：

# 加上Graphviz2.38绝对路径
import os
os.environ["PATH"] += os.pathsep + 'D:/Some_App_Use/Anaconda/Anaconda3/Library/bin/graphviz'
    
feature_name = ["色泽","根蒂","敲声","纹理","脐部","触感"]
dot_data = tree.export_graphviz(clf ,feature_names= feature_name,class_names=["好瓜","坏瓜"],filled=True,rounded=True,out_file =None) 
graph = graphviz.Source(dot_data) 
graph

五、决策树算法——C4.5
(一）对比ID3的改进点
C4.5算法是用于生成决策树的一种经典算法，是ID3算法的一种延伸和优化。C4.5算法对ID3算法进行了改进 ，改进点主要有：

1.用信息增益率来选择划分特征，克服了用信息增益选择的不足，
2.信息增益率对可取值数目较少的属性有所偏好；
3.能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
4.能够处理具有缺失属性值的训练数据；
5.在构造树的过程中进行剪枝；
（二）特征选择
特征选择也即选择最优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。 随着划分过程不断进行，希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。
（三）信息增益率
信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5算法采用信息增益率来选择最优划分属性。增益率公式:


信息增益率准则对可取值数目较少的属性有所偏好。所以，C4.5算法不是直接选择信息增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。
（四）对连续特征的处理
当属性类型为离散型，无须对数据进行离散化处理；

当属性类型为连续型，则需要对数据进行离散化处理。具体思路如下：

（五）对缺失值的处理
ID3算法不能处理缺失值，而C4.5算法可以处理缺失值（常用概率权重方法），主要有三种情况，具体如下：

1.在有缺失值的特征上如何计算信息增益率？
根据缺失比例，折算信息增益（无缺失值样本所占的比例乘以无缺失值样本子集的信息增益）和信息增益率

2.选定了划分属性，若样本在该属性上的值是缺失的，那么如何对这个样本进行划分？
将样本以不同概率同时划分到不同节点中，概率是根据其他非缺失属性的比例来得到的

3.对新的样本进行分类时，如果测试样本特性有缺失值如何判断其类别？
走所有分支，计算每个类别的概率，取概率最大的类别赋值给该样本

（六）剪枝
1.剪枝原因
因为过拟合的树在泛化能力的表现非常差。

剪枝又分为前剪枝和后剪枝，前剪枝是指在构造树的过程中就知道哪些节点可以剪掉 。 后剪枝是指构造出完整的决策树之后再来考查哪些子树可以剪掉。
2.剪前枝
在节点划分前确定是否继续增长，及早停止增长的主要方法有：

1.节点内数据样本数小于切分最小样本数阈值；
2.所有节点特征都已分裂；
3.节点划分前准确率比划分后准确率高。 前剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。
3.剪后枝
在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

C4.5算法采用悲观剪枝方法。根据剪枝前后的误判率来判定是否进行子树的修剪， 如果剪枝后与剪枝前相比其误判率是保持或者下降，则这棵子树就可以被替换为一个叶子节点。 因此，不需要单独的剪枝数据集。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。
把一颗子树（具有多个叶子节点）的剪枝后用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。对于一颗叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么一颗子树，它有L个叶子节点，那么该子树的误判率估计为：


样的话，我们可以看到一颗子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点，其误判个数J也需要加上一个惩罚因子，变成J+0.5。 [公式] 对于样本的误判率e，可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布。
那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e，e通过下式来计算

那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数的均值和标准差：

把子树替换成叶子节点后，该叶子的误判次数也是一个伯努利分布，因为子树合并为一个叶子节点了，所以，L=1，将其代入上面计算误判率的公式中，可以得到叶子节点的误判率为:

因此叶子节点的误判次数均值为:

六、决策树算法——CART算符
ID3和C4.5算法，生成的决策树是多叉树，只能处理分类不能处理回归。而CART（classification and regression tree）分类回归树算法，既可用于分类也可用于回归。 分类树的输出是样本的类别， 回归树的输出是一个实数。
ID3中使用了信息增益选择特征，增益大优先选择。C4.5中，采用信息增益率选择特征，减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数选择特征，基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）相反。
CART算法步骤
1.特征选择；
2.递归建立决策树；
3.决策树剪枝；
基尼系数
数据集D的纯度可用基尼值来度量:



在属性A的条件下，样本D的基尼系数定义为:

对连续特征和离散特征的处理
与C4.5思想相同，都是将连续的特征离散化。区别在选择划分点时，C4.5是信息增益率，CART是基尼系数。

离散特征
思路：不停的二分离散特征
在ID3、C4.5，特征A被选取建立决策树节点，如果它有3个类别A1,A2,A3，我们会在决策树上建立一个三叉点，这样决策树是多叉树，而且离散特征只会参与一次节点的建立。

七、总结
对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。