决策树挑出好西瓜（基于ID3、CART）

2023-11-19 20:07:16

决策树挑出好西瓜（基于ID3、CART）

一、决策树

1. 介绍

  决策树是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法
  主要算法有ID3、C4.5、CART

决策树包含三种类型的节点：

  1. 决策节点：通常用矩形框
  2. 机会节点：通常用圆圈
  3. 终节点：通常用三级形

2. 决策树事件处理流程

  1. 构建策略：
      随着树的深度增加，节点的熵迅速降低。熵降低的速度越快越好，可以得到高度最矮的决策树
  2. 决策树
    决策树的基本流程遵循“分而治之”策略。
  3. 伪代码
    输入：训练集 D = ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m ) D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)} D=(x1​,y1​),(x2​,y2​),…,(xm​,ym​); 属性集 A = a 1 , a 2 , . . . , a d A = a_1 , a _2 , . . . , a _d A=a1​,a2​,...,ad​
    过程：函数 T r e e G e n e r a t e ( D , A ) TreeGenerate(D,A) TreeGenerate(D,A)
    1: 生成节点 node;
    2: if D D D中样本全属于同一类别 C C C then
    3: 将 node 标记为 C C C类叶节点;return
    4:end if
    5: if A A A= ∅ o r or or D D D中样本在A上取值相同 then
    6:   将 node 标记为叶节点，其类别标记为D中样本数最多的类;return
    7: end if
    8: 从A中选择最优划分属性 a ∗ a_* a∗​;
    9: for a ∗ a_* a∗​的每一个值 a ∗ v d o a_*^vdo a∗v​do
    10:  为node生成一个分支;令 D v D_v Dv​表示D中在 a ∗ v a_*v a∗​v上取值为 a ∗ v a_*^v a∗v​的样本子集;
    11:  if D v D_v Dv​为空 then
    12:   将分支节点标记为叶节点，其类别标记为 D D D中样本最多的类;return
    13:  else
    14:    以 T r e e G e n e r a t e TreeGenerate TreeGenerate( D v , A D_v,A Dv​,A
    { a ∗ a_* a∗​})为分支节点。
    15:   end if
    16:end for
    输出：以node为根节点的一颗决策树
  4. 结束递归的三个条件
    • 样本全部属于同一类别
    • 此属性集合为孔或者此时所有样本的哥哥属性值相同
    • 数据集在某一个属性上没有样本

3. 理论基础

  1. 纯度 （purity）
      对于一个分支结点，如果该结点所包含的样本都属于同一类，那么它的纯度为1
    纯度越高越好，尽可能多的样本属于同一类
  2. 信息熵（information entropy）
      样本集合D中第k类样本所占的比例为 p k （ k = 1 , , 2 , . . . , ∣ y ∣ p_k（k=1,,2,...,|y| pk​（k=1,,2,...,∣y∣，则D的信息熵定义为：
    决策树挑出好西瓜（基于ID3、CART）
    E n t ( D ) Ent(D) Ent(D)值越小， D D D的纯度越高
  3. 信息增益（information gain）
      假定离散属性a有V个可能的取值 a 1 , a 2 , . . . , a V {a1,a2,...,aV} a1,a2,...,aV. 若使用a对样本集D进行分类，则会产生V个分支结点，记 D v D^v Dv为第v个分支结点包含的D中所有在属性a上取值为 a v a^v av的样本。不同分支结点样本数不同，我们给予分支结点不同的权重： ∣ D v ∣ / ∣ D ∣ |Dv|/|D| ∣Dv∣/∣D∣, 该权重赋予样本数较多的分支结点更大的影响
    决策树挑出好西瓜（基于ID3、CART）
      可以表示为划分后的信息熵。“前-后”的结果表明了本次划分所获得的信息熵减少量，也就是纯度的提升度
       G a i n ( D , a ) Gain(D,a) Gain(D,a)越大，获得的纯度提升越大，此次划分的效果越好
  4. 增益率 (gain ratio)
    基于信息增益的最优属性划分原则——信息增益准则，对可取值数据较多的属性有所偏好
    决策树挑出好西瓜（基于ID3、CART）
    决策树挑出好西瓜（基于ID3、CART）
      称为属性 a a a的固有值。属性 a a a的可能取值数目越多（即V越大），则 I V ( a ) IV(a) IV(a)的值通常会越大。这在一定程度上消除了对可取值数据较多的属性的偏好。
      事实上，增益率准则对可取值数目较少的属性有所偏好， C 4.5 C4.5 C4.5算法并不是直接使用增益率准则，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
  5. 基尼指数 (Gini index)
       C A R T CART CART决策树算法使用基尼指数来选择划分属性。数据集 D D D的纯度可用基尼值来度量：
    决策树挑出好西瓜（基于ID3、CART）
      可以这样理解基尼指数：从数据集 D D D中随机抽取两个样本，其类别标记不一致的概率。 G i n i ( D ) Gini(D) Gini(D)越小，纯度越高
    决策树挑出好西瓜（基于ID3、CART）
    在候选属性集合 A AA 中，选择那个使得划分后基尼指数最小的属性作为最优化分属性。即 a ∗ = a r g ⁡ a ∈ A m i n ⁡ G i n i i n d e x ( D , a ) a_∗ = arg ⁡_a ∈ A min ⁡ G i n i _ i n d e x ( D , a ) a∗​=arg⁡a​∈Amin⁡Ginii​ndex(D,a)

二、ID3决策树及Python实现

1. 数据处理

决策树挑出好西瓜（基于ID3、CART）

2. 步骤

  • 计算初始信息熵
  • 计算信息增益
  • 按照信息增益的大小排序
  • 选取最大的信息增益的特征，以此特征作为划分节点
  • 该特征从特征列表删除，继续返回到上一步筛选，重复操作，知道特征列表 = 0

3. 决策树实现

  1. 导入包
#导入模块
import pandas as pd
import numpy as np
from collections import Counter
from math import log2
  1. 数据的获取处理操作
#数据获取与处理
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
  1. 获取属性名称
    获取属性名称：纹理，色泽，根蒂，敲声，脐部，触感。 
#获取属性名称
def getLabels(data):
    labels = list(data.columns)[1:-1]
    return labels
  1. 获取类别标记
    获取一个样本是否好瓜的标记（是与否）。 
#获取属性名称
def getLabels(data):
    labels = list(data.columns)[1:-1]
    return labels
#获取类别标记
def targetClass(dataSet):
    classification = set([element[-1] for element in dataSet])
    return classification
  1. 叶节点标记
#将分支结点标记为叶结点，选择样本数最多的类作为类标记
def majorityRule(dataSet):
    mostKind = Counter([element[-1] for element in dataSet]).most_common(1)
    majorityKind = mostKind[0][0]
    return majorityKind
  1. 计算信息熵
#计算信息熵
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
  1. 子数据集构建
#子数据集构建
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
  1. 计算信息增益
#计算信息增益
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
  1. 选择最优属性
#选择最优属性                
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
  1. 建立决策树
#建立决策树
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 = 'E:\Ai\watermelon\watermalon.xls'
    data = getData(filePath)
    dataSet = dataDeal(data)
    labels = getLabels(data)
    myTree = createTree(dataSet,labels)
    return myTree

决策树挑出好西瓜（基于ID3、CART）
决策树挑出好西瓜（基于ID3、CART）
决策树挑出好西瓜（基于ID3、CART）
决策树挑出好西瓜（基于ID3、CART）

4. 分析

决策树挑出好西瓜（基于ID3、CART）
缺少一个色泽为浅白的叶
原始数据中不存在纹理为清晰、根蒂为稍蜷且色泽为浅白的瓜，导致决策树缺失这种情况的子叶。

三、Sklearn实现决策树

1. 基于信息增益准则方法建立决策树

  1. 导入相关库
#导入相关库
import pandas as pd
import graphviz 
from sklearn.model_selection import train_test_split
from sklearn import tree
  1. 导入数据
f = open('watermalon.csv','r')
data = pd.read_csv(f)

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

决策树挑出好西瓜（基于ID3、CART）

  1. 进行数据转换，
#将特征值数值化
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)

决策树挑出好西瓜（基于ID3、CART）
4. 建立模型并进行训练

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

决策树挑出好西瓜（基于ID3、CART）

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

决策树挑出好西瓜（基于ID3、CART）
5. 绘制决策树

# 加上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

决策树挑出好西瓜（基于ID3、CART）

2. CART算法实现

只需要将DecisionTreeClassifier函数的参数criterion的值改为gini：

clf = tree.DecisionTreeClassifier(criterion="gini")  #实例化 
clf = clf.fit(x_train, y_train) 
score = clf.score(x_test, y_test)
print(score)

决策树挑出好西瓜（基于ID3、CART）

  1. 绘制决策树
# 加上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

决策树挑出好西瓜（基于ID3、CART）

四、总结

  1. Sklearn库使用时，必须将特征量以及标签转化为数值型才能生成模型
  2. 对于数据量的大小，绘制出的树状模型波动较大

五、参考

机器学习笔记（4）——ID3决策树算法及其Python实现
【机器学习】机器学习之决策树（基于ID3、CART挑选西瓜）
【机器学习】 - 决策树（西瓜数据集）
西瓜书中ID3决策树的实现。
决策树ID3详解（西瓜案例）
信息熵的计算
（一）《机器学习》（周志华）第4章 决策树 笔记 理论及实现——“西瓜树”

上一篇：读书笔记:《流畅的Python》第六章 使用一等函数实现设计模式


下一篇：SAP Commerce Cloud Spartacus UI 的购物车 Cart 功能