精华内容
下载资源
问答
  • 决策树算法python实现
    千次阅读
    2021-01-08 15:40:40

    先参考:机器学习笔记(4)——ID3决策树算法及其Python实现

    将文章中的ID3算法代码运行

    然后参考:机器学习笔记(5)——C4.5决策树中的连续值处理和Python实现

    按照其中修改方法对刚运行的ID3算法代码进行修改即可。

    更多相关内容
  • Entropy = 系统的凌乱程度,使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。 决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点...
  • 决策树算法python实现

    2015-05-25 14:45:20
    python实现决策树,具体步骤参考博文:http://blog.csdn.net/Dream_angel_Z/article/details/45965463
  • C4.5算法使用信息增益率来代替ID3的信息增益进行特征的选择,克服了信息增益选择特征时偏向于特征值个数较多的不足。信息增益率的定义如下: # -*- coding: utf-8 -*- from numpy import * import math import ...
  • ''' 数据集:Mnist 训练集数量:60000 测试集数量:10000 ------------------------------ 运行结果:ID3(未剪枝) 正确率:85.9% 运行时长:356s ''' import time import numpy as np def loadData(fileName): ...
  • 使用的是python3版本,自己编写的,能够完美运行,只需要运行主程序就行,数据啥的都准备好了
  • 1. 使用Python实现基本的决策树算法; 2. 主要使用pandas的DataFrame实现; 3. 为防止过度拟合,在小于20个记录时,直接选取记录中最多类别; 3. 没有画决策树图
  • 一、CART决策树算法简介 CART(Classification And Regression Trees 分类回归树)算法是一种树构建算法,既可以用于分类任务,又可以用于回归。相比于 ID3 和 C4.5 只能用于离散型数据且只能用于分类任务,CART ...

    一、CART决策树算法简介

    CART(Classification And Regression Trees 分类回归树)算法是一种树构建算法,既可以用于分类任务,又可以用于回归。相比于 ID3 和 C4.5 只能用于离散型数据且只能用于分类任务,CART 算法的适用面要广得多,既可用于离散型数据,又可以处理连续型数据,并且分类和回归任务都能处理。

    本文仅讨论基本的CART分类决策树构建,不讨论回归树和剪枝等问题。

    首先,我们要明确以下几点:
    1. CART算法是二分类常用的方法,由CART算法生成的决策树是二叉树,而 ID3 以及 C4.5 算法生成的决策树是多叉树,从运行效率角度考虑,二叉树模型会比多叉树运算效率高。
    2. CART算法通过基尼(Gini)指数来选择最优特征。

    二、基尼系数

    基尼系数代表模型的不纯度,基尼系数越小,则不纯度越低,注意这和 C4.5的信息增益比的定义恰好相反。

    分类问题中,假设有K个类,样本点属于第k类的概率为pk,则概率分布的基尼系数定义为:
    在这里插入图片描述
    若CART用于二类分类问题(不是只能用于二分类),那么概率分布的基尼系数可简化为

    在这里插入图片描述
    假设使用特征 A 将数据集 D 划分为两部分 D1 和 D2,此时按照特征 A 划分的数据集的基尼系数为:
    在这里插入图片描述

    三、CART决策树生成算法

    输入:训练数据集D,停止计算的条件
    输出:CART决策树
    根据训练数据集,从根结点开始,递归地对每个结点进行以下操作,构建二叉决策树:
    (1)计算现有特征对该数据集的基尼指数,如上面所示;
    (2)选择基尼指数最小的值对应的特征为最优特征,对应的切分点为最优切分点(若最小值对应的特征或切分点有多个,随便取一个即可);
    (3)按照最优特征和最优切分点,从现结点生成两个子结点,将训练数据集中的数据按特征和属性分配到两个子结点中;
    (4)对两个子结点递归地调用(1)(2)(3),直至满足停止条件。
    (5)生成CART树。
    算法停止的条件:结点中的样本个数小于预定阈值,或样本集的基尼指数小于预定阈值(样本基本属于同一类,如完全属于同一类则为0),或者特征集为空。

    注:最优切分点是将当前样本下分为两类(因为我们要构造二叉树)的必要条件。对于离散的情况,最优切分点是当前最优特征的某个取值;对于连续的情况,最优切分点可以是某个具体的数值。具体应用时需要遍历所有可能的最优切分点取值去找到我们需要的最优切分点。

    四、CART算法的Python实现

    from math import log
        
    # 构造数据集
    def create_dataset():
        dataset = [['youth', 'no', 'no', 'just so-so', 'no'],
                   ['youth', 'no', 'no', 'good', 'no'],
                   ['youth', 'yes', 'no', 'good', 'yes'],
                   ['youth', 'yes', 'yes', 'just so-so', 'yes'],
                   ['youth', 'no', 'no', 'just so-so', 'no'],
                   ['midlife', 'no', 'no', 'just so-so', 'no'],
                   ['midlife', 'no', 'no', 'good', 'no'],
                   ['midlife', 'yes', 'yes', 'good', 'yes'],
                   ['midlife', 'no', 'yes', 'great', 'yes'],
                   ['midlife', 'no', 'yes', 'great', 'yes'],
                   ['geriatric', 'no', 'yes', 'great', 'yes'],
                   ['geriatric', 'no', 'yes', 'good', 'yes'],
                   ['geriatric', 'yes', 'no', 'good', 'yes'],
                   ['geriatric', 'yes', 'no', 'great', 'yes'],
                   ['geriatric', 'no', 'no', 'just so-so', 'no']]
        features = ['age', 'work', 'house', 'credit']
        return dataset, features
    
    # 计算当前集合的Gini系数
    def calcGini(dataset):
        # 求总样本数
        num_of_examples = len(dataset)
        labelCnt = {}
        # 遍历整个样本集合
        for example in dataset:
            # 当前样本的标签值是该列表的最后一个元素
            currentLabel = example[-1]
            # 统计每个标签各出现了几次
            if currentLabel not in labelCnt.keys():
                labelCnt[currentLabel] = 0
            labelCnt[currentLabel] += 1
        # 得到了当前集合中每个标签的样本个数后,计算它们的p值
        for key in labelCnt:
            labelCnt[key] /= num_of_examples
            labelCnt[key] = labelCnt[key] * labelCnt[key]
        # 计算Gini系数
        Gini = 1 - sum(labelCnt.values())
        return Gini
        
    # 提取子集合
    # 功能:从dataSet中先找到所有第axis个标签值 = value的样本
    # 然后将这些样本删去第axis个标签值,再全部提取出来成为一个新的样本集
    def create_sub_dataset(dataset, index, value):
        sub_dataset = []
        for example in dataset:
            current_list = []
            if example[index] == value:
                current_list = example[:index]
                current_list.extend(example[index + 1 :])
                sub_dataset.append(current_list)
        return sub_dataset
    
    # 将当前样本集分割成特征i取值为value的一部分和取值不为value的一部分(二分)
    def split_dataset(dataset, index, value):
        sub_dataset1 = []
        sub_dataset2 = []
        for example in dataset:
            current_list = []
            if example[index] == value:
                current_list = example[:index]
                current_list.extend(example[index + 1 :])
                sub_dataset1.append(current_list)
            else:
                current_list = example[:index]
                current_list.extend(example[index + 1 :])
                sub_dataset2.append(current_list)
        return sub_dataset1, sub_dataset2
    
    def choose_best_feature(dataset):
        # 特征总数
        numFeatures = len(dataset[0]) - 1
        # 当只有一个特征时
        if numFeatures == 1:
            return 0
        # 初始化最佳基尼系数
        bestGini = 1
        # 初始化最优特征
        index_of_best_feature = -1
        # 遍历所有特征,寻找最优特征和该特征下的最优切分点
        for i in range(numFeatures):
            # 去重,每个属性值唯一
            uniqueVals = set(example[i] for example in dataset)
            # Gini字典中的每个值代表以该值对应的键作为切分点对当前集合进行划分后的Gini系数
            Gini = {}
            # 对于当前特征的每个取值
            for value in uniqueVals:
                # 先求由该值进行划分得到的两个子集
                sub_dataset1, sub_dataset2 = split_dataset(dataset,i,value)
                # 求两个子集占原集合的比例系数prob1 prob2
                prob1 = len(sub_dataset1) / float(len(dataset))
                prob2 = len(sub_dataset2) / float(len(dataset))
                # 计算子集1的Gini系数
                Gini_of_sub_dataset1 = calcGini(sub_dataset1)
                # 计算子集2的Gini系数
                Gini_of_sub_dataset2 = calcGini(sub_dataset2)
                # 计算由当前最优切分点划分后的最终Gini系数
                Gini[value] = prob1 * Gini_of_sub_dataset1 + prob2 * Gini_of_sub_dataset2
                # 更新最优特征和最优切分点
                if Gini[value] < bestGini:
                    bestGini = Gini[value]
                    index_of_best_feature = i
                    best_split_point = value
        return index_of_best_feature, best_split_point
        
    # 返回具有最多样本数的那个标签的值('yes' or 'no')
    def find_label(classList):
        # 初始化统计各标签次数的字典
        # 键为各标签,对应的值为标签出现的次数
        labelCnt = {}
        for key in classList:
            if key not in labelCnt.keys():
                labelCnt[key] = 0
            labelCnt[key] += 1
        # 将classCount按值降序排列
        # 例如:sorted_labelCnt = {'yes': 9, 'no': 6}
        sorted_labelCnt = sorted(labelCnt.items(), key = lambda a:a[1], reverse = True)
        # 下面这种写法有问题
        # sortedClassCount = sorted(labelCnt.iteritems(), key=operator.itemgetter(1), reverse=True)
        # 取sorted_labelCnt中第一个元素中的第一个值,即为所求
        return sorted_labelCnt[0][0]
        
        
    def create_decision_tree(dataset, features):
        # 求出训练集所有样本的标签
        # 对于初始数据集,其label_list = ['no', 'no', 'yes', 'yes', 'no', 'no', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']
        label_list = [example[-1] for example in dataset]
        # 先写两个递归结束的情况:
        # 若当前集合的所有样本标签相等(即样本已被分“纯”)
        # 则直接返回该标签值作为一个叶子节点
        if label_list.count(label_list[0]) == len(label_list):
            return label_list[0]
        # 若训练集的所有特征都被使用完毕,当前无可用特征,但样本仍未被分“纯”
        # 则返回所含样本最多的标签作为结果
        if len(dataset[0]) == 1:
            return find_label(label_list)
        # 下面是正式建树的过程
        # 选取进行分支的最佳特征的下标和最佳切分点
        index_of_best_feature, best_split_point = choose_best_feature(dataset)
        # 得到最佳特征
        best_feature = features[index_of_best_feature]
        # 初始化决策树
        decision_tree = {best_feature: {}}
        # 使用过当前最佳特征后将其删去
        del(features[index_of_best_feature])
        # 子特征 = 当前特征(因为刚才已经删去了用过的特征)
        sub_labels = features[:]
        # 递归调用create_decision_tree去生成新节点
        # 生成由最优切分点划分出来的二分子集
        sub_dataset1, sub_dataset2 = split_dataset(dataset,index_of_best_feature,best_split_point)
        # 构造左子树
        decision_tree[best_feature][best_split_point] = create_decision_tree(sub_dataset1, sub_labels)
        # 构造右子树
        decision_tree[best_feature]['others'] = create_decision_tree(sub_dataset2, sub_labels)
        return decision_tree
        
    # 用上面训练好的决策树对新样本分类
    def classify(decision_tree, features, test_example):
        # 根节点代表的属性
        first_feature = list(decision_tree.keys())[0]
        # second_dict是第一个分类属性的值(也是字典)
        second_dict = decision_tree[first_feature]
        # 树根代表的属性,所在属性标签中的位置,即第几个属性
        index_of_first_feature = features.index(first_feature)
        # 对于second_dict中的每一个key
        for key in second_dict.keys():
            # 不等于'others'的key
            if key != 'others':
                if test_example[index_of_first_feature] == key:
                # 若当前second_dict的key的value是一个字典
                    if type(second_dict[key]).__name__ == 'dict':
                        # 则需要递归查询
                        classLabel = classify(second_dict[key], features, test_example)
                    # 若当前second_dict的key的value是一个单独的值
                    else:
                        # 则就是要找的标签值
                        classLabel = second_dict[key]
                # 如果测试样本在当前特征的取值不等于key,就说明它在当前特征的取值属于'others'
                else:
                    # 如果second_dict['others']的值是个字符串,则直接输出
                    if isinstance(second_dict['others'],str):
                        classLabel = second_dict['others']
                    # 如果second_dict['others']的值是个字典,则递归查询
                    else:
                        classLabel = classify(second_dict['others'], features, test_example)
        return classLabel
        
    if __name__ == '__main__':
        dataset, features = create_dataset()
        decision_tree = create_decision_tree(dataset, features)
        # 打印生成的决策树
        print(decision_tree)
        # 对新样本进行分类测试
        features = ['age', 'work', 'house', 'credit']
        test_example = ['midlife', 'yes', 'no', 'great']
        print(classify(decision_tree, features, test_example))
    

    若是二分类问题,则函数calcGini和choose_best_feature可简化如下:

    # 计算样本属于第1个类的概率p
    def calcProbabilityEnt(dataset):
        numEntries = len(dataset)
        count = 0
        label = dataset[0][len(dataset[0]) - 1]
        for example in dataset:
            if example[-1] == label:
                count += 1
        probabilityEnt = float(count) / numEntries
        return probabilityEnt
    
    def choose_best_feature(dataset):
        # 特征总数
        numFeatures = len(dataset[0]) - 1
        # 当只有一个特征时
        if numFeatures == 1:
            return 0
        # 初始化最佳基尼系数
        bestGini = 1
        # 初始化最优特征
        index_of_best_feature = -1
        for i in range(numFeatures):
            # 去重,每个属性值唯一
            uniqueVals = set(example[i] for example in dataset)
            # 定义特征的值的基尼系数
            Gini = {}
            for value in uniqueVals:
                sub_dataset1, sub_dataset2 = split_dataset(dataset,i,value)
                prob1 = len(sub_dataset1) / float(len(dataset))
                prob2 = len(sub_dataset2) / float(len(dataset))
                probabilityEnt1 = calcProbabilityEnt(sub_dataset1)
                probabilityEnt2 = calcProbabilityEnt(sub_dataset2)
                Gini[value] = prob1 * 2 * probabilityEnt1 * (1 - probabilityEnt1) + prob2 * 2 * probabilityEnt2 * (1 - probabilityEnt2)
                if Gini[value] < bestGini:
                    bestGini = Gini[value]
                    index_of_best_feature = i
                    best_split_point = value
        return index_of_best_feature, best_split_point
    

    五、运行结果

    在这里插入图片描述

    展开全文
  • 主要介绍了决策树剪枝算法python实现方法,结合实例形式较为详细的分析了决策树剪枝算法的概念、原理并结合实例形式分析了Python相关实现技巧,需要的朋友可以参考下
  • 下面小编就为大家带来一篇python实现决策树C4.5算法详解(在ID3基础上改进)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • ID3决策树是以信息增益作为决策标准的一种贪心决策树算法 # -*- coding: utf-8 -*- from numpy import * import math import copy import cPickle as pickle class ID3DTree(object): def __init__(self): # 构造...
  • 决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
  • 资源详细描述可以看我的博客: 算法笔记(8)-决策树算法Python代码实现 https://blog.csdn.net/li1873997/article/details/124780441
  • 决策树的一般流程 检测数据集中的每个子项是否属于同一个分类 if so return 类标签 Else  寻找划分数据集的最好特征  划分数据集  创建分支 节点 from math import log import operator #生成样本数据集 def ...
  • python编程实现决策树算法

    千次阅读 多人点赞 2021-10-25 20:37:23
    最近布置了个课堂作业,用python实现决策树算法。整了几天勉勉强强画出了棵歪脖子树,记录一下。 大体思路: 1.创建决策树My_Decision_Tree类,类函数__init__()初始化参数、fit()进行决策树模型训练、predict()...

    最近布置了个课堂作业,用python实现决策树算法 。整了几天勉勉强强画出了棵歪脖子树,记录一下。

    大体思路:

    1.创建决策树My_Decision_Tree类,类函数__init__()初始化参数、fit()进行决策树模型训练、predict()进行预测、evaluate()进行模型评估、save_model()保存模型(csv格式)、load_model()加载模型、show_tree()使用Pillow库绘制决策树以及其他一些封装的功能函数;

    2.最佳划分点的度量通常有Gini值、Entropy、Classification error等,本程序采用Gini值,计算方法如下: 

    构建决策数模型所用到的功能函数(gini值计算相关)说明: 

    ①get_col_gini(self,threshold_point, value_series, label_series):计算一列数据在某一阈值划分点下的gini_split值;

    ②get_best_point(self,value_series, label_series):对连续型数据进行大小排序,分别计算切分点及其对应的gini_split值,找到使得gini_split值最小的最佳切分点;

    ③get_best_column(self,data,label_series):遍历数据表中的属性列,计算每列的最佳划分点和gini_split值,并对比找到最适合划分的一列及其对应的划分点;

    3.决策树构建(训练)的逻辑: 

    ①程序开始以root为父节点,先找到6列属性(剩余属性)中最适合划分的列和划分点,并将其划分为两个子节点,记录判断条件和此节点位置。删除子节点中的该列属性以避免最终决策树模型倾向于某个属性,利用剩余的属性继续构造决策树;

    ②判断各个子节点中的标签是否相同,如果为同一类则移到叶节点中,否则将此节点更新到下个流程中的父节点中;

    ③一直循环以上过程,当父节点为空时结束训练,如果所有子节点都为叶节点时则决策树完美将数据分类;当然也会出现所有属性都用完但子节点中标签依旧不唯一的情况,这时以该节点中个数较多的标签类作为分类结果,终止模型构建。

    # -*- coding: utf-8 -*-
    # @Version: Python 3.8.2
    # @Author: 707
    # @Use: 决策树算法编写
    
    import numpy as np
    import pandas as pd
    from sklearn.model_selection import train_test_split  #数据集划分
    #采用Pillow可视化决策树
    from PIL import Image
    from PIL import ImageDraw
    from PIL import ImageFont
    
    ###决策树框架###
    class My_Decision_Tree(object):
    	'''决策树框架'''
    
    	def __init__(self, arg=None):
    		##初始化类参数
    		self.arg = arg
    
    		#存放决策树中的各层判断条件
    		self.decision_df=pd.DataFrame(columns=['parent_depth','parent_pos','this_depth','this_pos','column','point','label'])
    		self.Parent_node_list=[]	#存放父节点和子节点的DataFrame
    		self.Child_node_list=[]	
    		self.leaf_list=[] #存放划分好的叶节点
    		self.branch_list=[]	#存放未能划分出来的节点
    
    	def fit(self,x_train,y_train):
    		'''传入训练集和标签构造决策树'''
    
    		'''		
    		程序逻辑:
    		(1)程序开始以root为父节点,先找到6列属性(剩余属性)中最适合划分的列和划分点,并将其划分为两个子节点,
    		记录判断条件和此节点位置。删除子节点中的该列属性以避免最终决策树模型倾向于某个属性,利用剩余的属性继续构造决策树
    		(2)判断各个子节点中的标签是否相同,如果为同一类则移到叶节点中,否则将此节点更新到下个流程中的父节点中
    		(3)一直循环以上过程,当父节点为空时结束训练,如果所有子节点都为叶节点时则决策树完美将数据分类;当然也会出现所有属性都用完但子节点
    		中标签依旧不唯一的情况,这时以该节点中个数较多的标签类作为分类结果,终止模型构建。
    
    		'''
    
    		x_data=x_train.copy()
    		if(y_train.name not in x_data.columns):
    			x_data[y_train.name]=y_train
    		
    		#把第一层(原数据)放入父节点列表Parent_node_list
    		self.Parent_node_list.append(x_data)
    		#写入第一层的决策(跟节点)
    		decision={'this_depth':1,'this_pos':0,'column':'root','label':'#'}
    		self.decision_df=self.decision_df.append(decision,ignore_index=True)
    		#开始循环计算分类节点
    		parent_count=0 #循环的父节点数
    		child_pos=0  #子节点的位置
    		depth=2 #第几层节点
    		while True:
    			parent_node=self.Parent_node_list[parent_count]
    			#找到第一个适合划分的列和划分点
    			col_1,point_1=self.get_best_column(parent_node,parent_node[y_train.name])
    			print('decision condition:',col_1,point_1)
    
    			#根据条件把父节点划分为两部分
    			Child_node1=parent_node.loc[parent_node[col_1]<=point_1]
    			Child_node2=parent_node.loc[parent_node[col_1]>point_1]
    			#每一部分的分类结果
    			result=[]
    			for child_node in [Child_node1,Child_node2]:
    				#删除已使用过的属性
    				del(child_node[col_1])
    
    				#判断子节点标签是否为一类,是则将其放入叶节点列表中
    				if(len(child_node[y_train.name].unique())==1):
    					self.leaf_list.append(child_node)
    					print('添加一个叶节点,标签类型:',child_node[y_train.name].unique()[0],'数据大小:',child_node.shape)
    					result.append(child_node[y_train.name].unique()[0])
    
    				# 判断子节点标签是否还有剩余属性可以作为分类依据,如果有则添加到子节点列表中用于后续分类
    				elif(child_node.shape[1]!=1):
    					self.Child_node_list.append(child_node)
    					print('添加一个子节点,数据大小:',child_node.shape)
    					result.append('#')
    				#都不满足说明该节点没有分完但是分不下去了,提示错误
    				else:
    					self.branch_list.append(child_node)
    					print('child_node节点已用完所有属性,仍然没分出来,剩余数据大小:')
    					print(child_node[y_train.name].value_counts())
    
    					values=child_node[y_train.name].value_counts()
    					if(len(values)==0):
    						replace=list(parent_node[y_train.name].value_counts().index)[0]
    					else:
    						replace=list(values.index)[0]
    					print('用%s作为该条件下的预测结果' %replace)
    					result.append(replace)
    
    			#找到该父节点在该层中所对应的位置
    			p_pos_list=self.decision_df.loc[(self.decision_df['this_depth']==depth-1)&(self.decision_df['label']=='#'),'this_pos']
    			p_pos_list=list(p_pos_list)
    			# print('p_pos_list:',p_pos_list)
    
    			#判断完一个父节点之后,把判断条件加入decision_df中  
    			decision1={'parent_depth':depth-1,'parent_pos':p_pos_list[parent_count],'this_depth':depth,'this_pos':child_pos,
    						'column':col_1,'point':point_1,'label':result[0]}
    			decision2={'parent_depth':depth-1,'parent_pos':p_pos_list[parent_count],'this_depth':depth,'this_pos':child_pos+1,
    						'column':col_1,'point':point_1,'label':result[1]}
    			self.decision_df=self.decision_df.append([decision1,decision2],ignore_index=True)
    
    			#当遍历完父节点列表所有值后,将子节点更新为父节点
    			child_pos+=2
    			parent_count+=1
    			if(parent_count==len(self.Parent_node_list)):
    				parent_count=0
    				child_pos=0
    				depth+=1
    				print('该层决策结束,进行下一层决策\n')
    				self.Parent_node_list=self.Child_node_list.copy()
    				self.Child_node_list.clear()
    				print('更新parent_node_list,大小:%d' %len(self.Parent_node_list))
    
    				#判断父节点列表中是否还有未分类的节点,如果没有则表示已经全部分好,结束训练
    				if(len(self.Parent_node_list)==0):
    					print('决策树构建完成')
    					#显示构建好的决策树:判断条件及结果(叶节点)
    					print(self.decision_df)
    
    					break
    
    	def predict(self,x_test):
    		'''输入测试数据进行决策判断'''
    		y_predict=list()
    		
    		if(type(x_test)==pd.core.series.Series):
    			pred=self.get_ylabel(x_test)
    			y_predict.append(pred)
    		else:
    			for index,row in x_test.iterrows():
    				pred=self.get_ylabel(row)
    				y_predict.append(pred)
    
    		y_predict=np.array(y_predict,dtype=str)
    		return y_predict
    
    
    
    	def evaluate(self,x_test,y_test):
    		'''输入测试集和标签评估决策树准确性,返回acc'''
    		y_true=np.array(y_test,dtype=str)
    		y_pred=self.predict(x_test)
    		# print(y_pred)
    		# print(y_true)
    		label_list=list(self.decision_df['label'].unique())
    		label_list.remove('#')
    		label_list=np.array(label_list,dtype=str) #类型转换
    		#创建混淆矩阵(index为true,columns为pred)
    		confusion_matrix=pd.DataFrame(data=0,columns=label_list,index=label_list)
    		for i in range(len(y_true)):
    			confusion_matrix.loc[y_true[i],y_pred[i]]+=1
    		print('混淆矩阵:')
    		print(confusion_matrix)
    		#计算准确率
    		acc=0
    		for i in range(len(label_list)):
    			acc+=confusion_matrix.iloc[i,i]
    		acc/=len(y_true)
    		print('acc:%.5f' %acc)
    		return acc
    
    	def save_model(self,path):
    		'''以csv格式保存模型'''
    		self.decision_df.to_csv(path,index=False)
    
    	def load_model(self,path):
    		'''以csv格式读取模型'''
    		self.decision_df=pd.read_csv(path)
    
    	def get_col_gini(self,threshold_point, value_series, label_series):
    	    '''Gini值计算函数'''
    
    	    # 将输入进行重组
    	    df_input = pd.DataFrame()
    	    df_input['value'] = value_series
    	    df_input['label'] = label_series
    	    # print(df_input)
    	    # 设计Gini值的计算表格
    	    label_cols = label_series.value_counts()
    	    df_gini = pd.DataFrame(columns=['node1', 'node2'], index=label_cols.index)
    	    
    	    for c in label_cols.index:
    	        df_c = df_input.loc[df_input['label'] == c]
    	        df_gini.loc[c, 'node1'] = df_c.loc[df_c['value']<= threshold_point].shape[0]
    	        df_gini.loc[c, 'node2'] = df_c.loc[df_c['value']> threshold_point].shape[0]
    
            #计算node1、node2节点gini值中和的部分
    	    sum_n1=df_gini['node1'].sum()
    	    sum_n2=df_gini['node2'].sum()
    	    # print(df_gini)
    
    	    # 计算node节点gini值
    	    gini_n1=gini_n2=0
    	    if(sum_n1==0):
    	    	for c in label_cols.index:
    	    		gini_n2+=(df_gini.loc[c,'node2']/sum_n2)**2
    	    elif(sum_n2==0):
    	    	for c in label_cols.index:
    	    		gini_n1+=(df_gini.loc[c,'node1']/sum_n1)**2
    	    else:
    	    	for c in label_cols.index:
    		    	gini_n1+=(df_gini.loc[c,'node1']/sum_n1)**2
    		    	gini_n2+=(df_gini.loc[c,'node2']/sum_n2)**2
    	    gini_n1 = 1-gini_n1
    	    gini_n2 = 1-gini_n2
    	    #计算gini_split
    	    gini_split=sum_n1/(sum_n1+sum_n2)*gini_n1 +sum_n2/(sum_n1+sum_n2)*gini_n2
    	    # print("point:%f,gini_split:%f" %(threshold_point,gini_split))
    	    return gini_split
    
    	def get_best_point(self,value_series, label_series):
    	    '''找到一列属性中最适合划分(gini值最小)的点'''
    
    	    value_array=np.array(value_series)
    	    value_array=np.sort(value_array)
    	    df_point = pd.DataFrame(columns=['point', 'gini_value'])
    
    	    # 循环属性值列,计算划分点及其gini值并添加至df_point数据表中
    	    for i in range(len(value_array) + 1):
    	        if(i == 0):
    	            point = value_array[i] - 1
    	        elif(i == len(value_array)):
    	            point = value_array[i - 1]
    	        else:
    	            point = 0.5 * (value_array[i] + value_array[i - 1])
    	        gini = self.get_col_gini(point, value_series, label_series)
    
    	        s = pd.Series(data={'point': point, 'gini_value': gini})
    	        df_point.loc[i] = s
    
    	    df_point.sort_values(by='gini_value', inplace=True)
    	    best_point = df_point.iloc[0, 0]
    	    best_gini = df_point.iloc[0,1]
    	    # print("best point for column '%s':%f" %(value_series.name,best_point))
    	    # print(df_point)
    	    return best_point,best_gini
    
    	def get_best_column(self,data,label_series):
    		'''遍历data中的属性列,计算其最佳划分点及gini值,找出最适合划分的一列和划分点'''
    		x_data=data.copy()
    		if(label_series.name in x_data.columns):
    			del(x_data[label_series.name])
    
    		gini_columns=pd.DataFrame(columns=['point','gini'],index=x_data.columns)
    		for col_name in x_data.columns:
    			point,gini=self.get_best_point(x_data[col_name],label_series)
    			s=pd.Series({'point':point,'gini':gini})
    			gini_columns.loc[col_name]=[point,gini]
    			# gini_columns=gini_columns.append(s,ignore_index=True)	#append会更改索引
    		gini_columns.sort_values(by='gini',inplace=True)
    		# print(gini_columns)
    		best_col=gini_columns.index[0]
    		best_point=gini_columns.iloc[0,0]
    		return best_col,best_point
    
    	def get_ylabel(self,x_series):
    		'''计算一行x数据(Series)对应的标签'''
    		model=self.decision_df
    
    		y_pred='#'
    		x_index=1
    		parent_index=[]
    		child_df=pd.DataFrame()
    
    		# for i in range(1):
    		while (y_pred=='#'):
    			#判断条件
    			condition=[model.loc[x_index,'column'],model.loc[x_index,'point']]
    			if(x_series[condition[0]]>condition[1]):
    				x_index+=1
    			# 	print('%s>%f' %(condition[0],condition[1]))
    			# else:
    			# 	print('%s<=%f' %(condition[0],condition[1]))
    				
    			y_pred=model.loc[x_index,'label']
    			#更新父节点索引并找到其子节点
    			parent_index=[model.loc[x_index,'this_depth'],model.loc[x_index,'this_pos']]
    			child_df=model.loc[(model['parent_depth']==parent_index[0])&(model['parent_pos']==parent_index[1])]
    			
    			#找到标签时结束
    			if(child_df.shape[0]!=0):
    				x_index=list(child_df.index)[0]
    			# 	print('跳到第%d行继续判断' %x_index)
    			# else:
    			# 	print('预测结束')
    		# print('pred:',y_pred)
    		return y_pred
    
    	def show_tree(self):
    		'''将决策树进行可视化'''
    
    		def add_text(im_draw,text_str,xy,multiline=1):
    			'''在绘图对象的某个位置添加文字'''
    			#设置大小
    			font_h,font_w=25,14
    			font_h*=multiline
    			text_len=round(len(text_str)/multiline)
    
    			font=ImageFont.truetype(font='simsun.ttc',size=20)
    			im_draw.text(xy=(xy[0]-font_w*3,xy[1]),text=text_str,font=font,fill='black',align='center')
    			#绘制矩形
    			# im_draw.rectangle(xy=(xy[0],xy[1],xy[0]+font_w*text_len,xy[1]+font_h),outline='black',width=2)
    
    		interval_x,interval_y=60,80
    		model=self.decision_df.copy()
    		model['x_pos']=model['this_pos']
    		model['y_pos']=(model['this_depth']-1)*interval_y
    		model['text']='text'
    		max_depth=model.iloc[-1,2]
    		
    		#创建图像
    		img_w,img_h=1500,600
    		tree_img=Image.new(mode='RGB',size=(img_w,img_h),color='white')
    		draw=ImageDraw.Draw(tree_img) #创建绘图对象
    
    		parent_pos=[]
    		parent_x_pos=0
    		x_pos=0
    		for x_index in model.index:
    			text=model.loc[x_index,'column']
    			if (str(model.loc[x_index,'point']) == 'nan'):
    				x_pos=img_w/4
    			else:
    				#跟新text内容和x位置
    				model.loc[x_index,'x_pos']=x_pos
    				parent_pos=[model.loc[x_index,'parent_depth'],model.loc[x_index,'parent_pos']]
    				parent_x_pos=model.loc[(model['this_depth']==parent_pos[0])&(model['this_pos']==parent_pos[1]),'x_pos']
    				depth=model.loc[x_index,'this_depth']-1
    				if(model.loc[x_index,'this_pos']%2==0):
    					text+='\n<='+('%.3f' %model.loc[x_index,'point'])
    					x_pos=parent_x_pos-interval_x*np.sqrt(max_depth-depth)
    
    				else:
    					text+='\n>'+('%.3f' %model.loc[x_index,'point'])
    					x_pos=parent_x_pos+interval_x*np.sqrt(max_depth-depth)
    				x_pos=x_pos.iloc[0]
    				if(model.loc[x_index,'label'] !='#'):
    					text+='\nClass:'+str(model.loc[x_index,'label'])
    			
    			#将文字和位置添加到
    			model.loc[x_index,'text']=text
    			model.loc[x_index,'x_pos']=x_pos
    		
    		# 调整节点横坐标位置
    		gap=140
    		for depth in model['this_depth'].unique():
    
    			if(depth!=1):
    				same_depth=model.loc[model['this_depth']==depth]
    				for x_index in same_depth.index[:-1]:
    					if(x_index==same_depth.index[0]):
    						if((model.loc[same_depth.index[0],'x_pos']-model.loc[same_depth.index[-1],'x_pos'])<gap*len(same_depth.index)):
    							#如果整体太挤,整层先往左移一段
    							for i in same_depth.index:
    								model.loc[i,'x_pos']-=gap*len(same_depth.index)/8
    					#如果相邻两个靠太近,右边的往右移一点
    					if((model.loc[x_index+1,'x_pos']-model.loc[x_index,'x_pos'])<gap):
    						model.loc[x_index+1,'x_pos']=model.loc[x_index,'x_pos']+gap
    						# model.loc[x_index,'x_pos']-=gap/2
    
    		#绘制文字和线
    		this_img_pos=[]
    		parent_img_pos=[]
    		for x_index in model.index:
    			#绘制直线
    			if(x_index !=0):
    				this_img_pos=[model.loc[x_index,'x_pos'],model.loc[x_index,'y_pos']]
    				parent_pos=[model.loc[x_index,'parent_depth'],model.loc[x_index,'parent_pos']]
    				parent_img_pos=model.loc[(model['this_depth']==parent_pos[0])&(model['this_pos']==parent_pos[1]),['x_pos','y_pos']]
    				parent_img_pos=[parent_img_pos.iloc[0,0],parent_img_pos.iloc[0,1]]
    				draw.line(xy=(parent_img_pos[0],parent_img_pos[1],this_img_pos[0],this_img_pos[1]),fill='gray',width=1)
    
    			#添加文字
    			this_pos=(model.loc[x_index,'x_pos'],model.loc[x_index,'y_pos'])
    			text=model.loc[x_index,'text']
    			add_text(im_draw=draw,text_str=text,xy=this_pos)
    		
    		#显示图片
    		tree_img.show()
    
    
    if __name__ == '__main__':
    
        # 读取文件
        data = pd.read_csv('./paras_labels.csv')
        #数据按8:2进行训练集、测试集切分
        x_train,x_test,y_train,y_test=train_test_split(data,data['label'],test_size=0.2,random_state=7)
    
    
        ds_tree=My_Decision_Tree()
    
        ds_tree.fit(x_train,y_train)
        # ds_tree.save_model('my_decision_tree%d.csv' %e)
    
        # ds_tree.load_model('my_decision_tree%d.csv' %e)
        # print(ds_tree.decision_df)
    
        print('训练集评估模型:')
        ds_tree.evaluate(x_train,y_train)
        print('测试集评估模型:')
        ds_tree.evaluate(x_test,y_test)
    
        ds_tree.show_tree()

    结果:

    用我的数据跑了一下,成功长出一棵歪脖子树,nice! 

     代码能力有限,有错误的地方欢迎大佬们交流,批评指正[狗头抱拳]

     

     

     

    展开全文
  • 本文实例为大家分享了python实现ID3决策树算法的具体代码,供大家参考,具体内容如下 ''''' Created on Jan 30, 2015 @author: 史帅 ''' from math import log import operator import re def fileToDataSet...
  • 决策树算法,学生专用,简单易懂,实验报告可用
  • 本文实例为大家分享了基于信息增益的决策树归纳的Python实现代码,供大家参考,具体内容如下 # -*- coding: utf-8 -*- import numpy as np import matplotlib.mlab as mlab import matplotlib.pyplot as plt from ...
  • python实现三种经典决策树算法

    千次阅读 2021-01-24 17:19:34
    决策树实现ID3、C4.5、CART算法 Author: 浅若清风cyf Date: 2020/12/15 一、创建数据集 手动 def createDataSet(): """ 创建测试的数据集 :return: """ dataSet = [ # 1 ['青绿', '蜷缩', '浊响', '清晰'...

    决策树实现ID3、C4.5、CART算法

    • Author: 浅若清风cyf
    • Date: 2020/12/15

    一、创建数据集

    • 手动
    def createDataSet():
        """
        创建测试的数据集
        :return:
        """
        dataSet = [
            # 1
            ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
            # 2
            ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
            # 3
            ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
            # 4
            ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
            # 5
            ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
            # 6
            ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],
            # 7
            ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],
            # 8
            ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],
    
            # ----------------------------------------------------
            # 9
            ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],
            # 10
            ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],
            # 11
            ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],
            # 12
            ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],
            # 13
            ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],
            # 14
            ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],
            # 15
            ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],
            # 16
            ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],
            # 17
            ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']
        ]
    
        # 特征值列表
        labels = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']
    
        # 特征对应的所有可能的情况
        labels_full = {}
    
        for i in range(len(labels)):
            labelList = [example[i] for example in dataSet]
            uniqueLabel = set(labelList)
            labels_full[labels[i]] = uniqueLabel
    
        return dataSet, labels, labels_full
    
    dataSet, labels, labels_full=createDataSet()
    print(dataSet)
    print(labels)
    print(labels_full)
    
    [['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'], ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'], ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'], ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'], ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'], ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'], ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'], ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'], ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'], ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'], ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'], ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']]
    ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']
    {'色泽': {'青绿', '乌黑', '浅白'}, '根蒂': {'硬挺', '蜷缩', '稍蜷'}, '敲击': {'浊响', '清脆', '沉闷'}, '纹理': {'稍糊', '清晰', '模糊'}, '脐部': {'凹陷', '稍凹', '平坦'}, '触感': {'软粘', '硬滑'}}
    
    • 从文件读取
    import numpy as np
    import pandas as pd
    # df=pd.read_excel("./watermelon20.xlsx")
    # df.to_csv('./watermelon20.csv',index=False)
    df=pd.read_csv('./watermelon20.csv')
    print(df)
    # 属性集合
    attr=df.columns.values.tolist()[1:]
    data_org=np.array(df[attr])
    # static_attr=df.columns.values.tolist()[1:]#这里的属性 不改变,仅仅作为索引
    print(attr)
    print(len(attr))
    print(data_org.shape)
    print(data_org)
    
    # print(static_attr)
    
    
        编号  色泽  根蒂  敲声  纹理  脐部  触感 好瓜
    0    1  青绿  蜷缩  浊响  清晰  凹陷  硬滑  是
    1    2  乌黑  蜷缩  沉闷  清晰  凹陷  硬滑  是
    2    3  乌黑  蜷缩  浊响  清晰  凹陷  硬滑  是
    3    4  青绿  蜷缩  沉闷  清晰  凹陷  硬滑  是
    4    5  浅白  蜷缩  浊响  清晰  凹陷  硬滑  是
    5    6  青绿  稍蜷  浊响  清晰  稍凹  软粘  是
    6    7  乌黑  稍蜷  浊响  稍糊  稍凹  软粘  是
    7    8  乌黑  稍蜷  浊响  清晰  稍凹  硬滑  是
    8    9  乌黑  稍蜷  沉闷  稍糊  稍凹  硬滑  否
    9   10  青绿  硬挺  清脆  清晰  平坦  软粘  否
    10  11  浅白  硬挺  清脆  模糊  平坦  硬滑  否
    11  12  浅白  蜷缩  浊响  模糊  平坦  软粘  否
    12  13  青绿  稍蜷  浊响  稍糊  凹陷  硬滑  否
    13  14  浅白  稍蜷  沉闷  稍糊  凹陷  硬滑  否
    14  15  乌黑  稍蜷  浊响  清晰  稍凹  软粘  否
    15  16  浅白  蜷缩  浊响  模糊  平坦  硬滑  否
    16  17  青绿  蜷缩  沉闷  稍糊  稍凹  硬滑  否
    ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '好瓜']
    7
    (17, 7)
    [['青绿' '蜷缩' '浊响' '清晰' '凹陷' '硬滑' '是']
     ['乌黑' '蜷缩' '沉闷' '清晰' '凹陷' '硬滑' '是']
     ['乌黑' '蜷缩' '浊响' '清晰' '凹陷' '硬滑' '是']
     ['青绿' '蜷缩' '沉闷' '清晰' '凹陷' '硬滑' '是']
     ['浅白' '蜷缩' '浊响' '清晰' '凹陷' '硬滑' '是']
     ['青绿' '稍蜷' '浊响' '清晰' '稍凹' '软粘' '是']
     ['乌黑' '稍蜷' '浊响' '稍糊' '稍凹' '软粘' '是']
     ['乌黑' '稍蜷' '浊响' '清晰' '稍凹' '硬滑' '是']
     ['乌黑' '稍蜷' '沉闷' '稍糊' '稍凹' '硬滑' '否']
     ['青绿' '硬挺' '清脆' '清晰' '平坦' '软粘' '否']
     ['浅白' '硬挺' '清脆' '模糊' '平坦' '硬滑' '否']
     ['浅白' '蜷缩' '浊响' '模糊' '平坦' '软粘' '否']
     ['青绿' '稍蜷' '浊响' '稍糊' '凹陷' '硬滑' '否']
     ['浅白' '稍蜷' '沉闷' '稍糊' '凹陷' '硬滑' '否']
     ['乌黑' '稍蜷' '浊响' '清晰' '稍凹' '软粘' '否']
     ['浅白' '蜷缩' '浊响' '模糊' '平坦' '硬滑' '否']
     ['青绿' '蜷缩' '沉闷' '稍糊' '稍凹' '硬滑' '否']]
    
    • 决策树结构【ID3】
    # 决策树结构:【字典的多重嵌套】
    {
            "纹理": {
                    "稍糊": {
                            "触感": {
                                    "硬滑": "否",
                                    "软粘": "是"
                            }
                    },
                    "清晰": {
                            "根蒂": {
                                    "蜷缩": "是",
                                    "硬挺": "否",
                                    "稍蜷": {
                                            "色泽": {
                                                    "青绿": "是",
                                                    "浅白": "是",
                                                    "乌黑": {
                                                            "触感": {
                                                                    "硬滑": "是",
                                                                    "软粘": "否"
                                                            }
                                                    }
                                            }
                                    }
                            }
                    },
                    "模糊": "否"
            }
    }
    
    • 决策树结构【C4.5】
    {
            "纹理": {
                    "模糊": "否",
                    "稍糊": {
                            "触感": {
                                    "软粘": "是",
                                    "硬滑": "否"
                            }
                    },
                    "清晰": {
                            "触感": {
                                    "软粘": {
                                            "色泽": {
                                                    "乌黑": "否",
                                                    "青绿": {
                                                            "根蒂": {
                                                                    "硬挺": "否",
                                                                    "蜷缩": "是",
                                                                    "稍蜷": "是"
                                                            }
                                                    },
                                                    "浅白": "否"
                                            }
                                    },
                                    "硬滑": "是"
                            }
                    }
            }
    }
    
    • 决策树结构【CART】
    {
            "清晰": {
                    "yes": {
                            "硬滑": {
                                    "yes": "是",
                                    "no": {
                                            "青绿": {
                                                    "yes": {
                                                            "稍蜷": {
                                                                    "yes": "是",
                                                                    "no": "否"
                                                            }
                                                    },
                                                    "no": "否"
                                            }
                                    }
                            }
                    },
                    "no": {
                            "乌黑": {
                                    "yes": {
                                            "浊响": {
                                                    "yes": "是",
                                                    "no": "否"
                                            }
                                    },
                                    "no": "否"
                            }
                    }
            }
    }
    
    • 可视化结果【ID3】
    import matplotlib.pyplot as plt
    import numpy as np
    fig=plt.figure(figsize=(12,8))
    img=plt.imread('./决策树正确结果.jpg')
    plt.imshow(img)
    plt.axis('off')
    plt.show()
    

    在这里插入图片描述

    • 算法伪代码
    fig=plt.figure(figsize=(16,10))
    img=plt.imread('./决策树算法流程.jpg')
    plt.imshow(np.uint8(img))
    plt.axis('off')
    plt.show()
    

    在这里插入图片描述

    • ID3:信息增益
    fig=plt.figure(figsize=(16,12))
    img=plt.imread('./决策树ID3-信息增益.jpg')
    plt.imshow(img)
    plt.axis('off')
    plt.show()
    

    在这里插入图片描述

    • C4.5:增益率
    fig=plt.figure(figsize=(16,14))
    img=plt.imread('./决策树C4.5-增益率.jpg')
    plt.imshow(img)
    plt.axis('off')
    plt.show()
    

    在这里插入图片描述

    • CART:基尼指数
    fig=plt.figure(figsize=(16,12))
    img=plt.imread('./决策树CART-基尼指数.jpg')
    plt.imshow(img)
    plt.axis('off')
    plt.show()
    

    在这里插入图片描述

    • 完整代码
    import numpy as np
    import pandas as pd
    from collections import Counter
    import pprint
    import json
    
    class DecisionTree():
        D = None  # 数据集
        attribute_list = None  # 属性集
        attribute_value_list = dict()  # 属性集对应取值集合
        tree = None  # 决策树【Notice: 字典类型是引用传值,因此需要在init中再初始化它,否则对这个类创建多个对象是该成员变量会指向同一个地址,导致数据会叠加在一起】
    
        def __init__(self):  # 构造函数:自动加载数据集
            self.tree=dict()
            df = pd.read_csv('./watermelon20.csv')
            # 属性集合
            self.attribute_list = df.columns.values.tolist()[1:]
            # 数据集(过滤掉编号)
            self.D = np.array(df[self.attribute_list])
            # 获取每个属性的每个属性值
            for i in range(len(self.attribute_list)):
                self.attribute_value_list[self.attribute_list[i]] = set(df[self.attribute_list[i]])
            # 去除类别
            self.attribute_list = self.attribute_list[:-1]
    
        # 判断集合是否属于同一个类别C【是则设为叶结点,标记为类别C】
        def isSameLabel(self, D):
            labels = [D[i][-1] for i in range(len(D))]  # 取出每个样本的标签
            return len(set(labels)) == 1  # 属于同一个类别则labels集合元素数量为1,返回True
    
        # 判断数据集中的所有属性上的取值是否相同【相同的话设为叶结点,并标记为类别多的类别】
        def isEmptyOrSameAttribute(self, D, attribute_list):
            if len(attribute_list) == 0:
                print("所有属性划分完,无法继续划分,设为叶结点")
                # print("len(attribute_list) == 0")
                return True
            else:
                attribute_index_list = []
                for i in attribute_list:
                    attribute_index_list.append(self.attribute_list.index(i))
                subset_D = D[:, np.array(attribute_index_list)]
                for i in range(1, subset_D.shape[0]):
                    if (subset_D[0] == subset_D[i]).all():
                        pass
                    else:
                        return False
            print("所有样本的所有属性相同,无法划分")
            return True
    
        # 计算信息熵
        def Ent(self, D):
            labels = D[:, -1]
            count_result = Counter(labels)
            # 统计每个标签的频数
            labels_count = np.array(list(count_result.values()))
            p = labels_count / D.shape[0]
            # 计算信息熵
            ent = -1 * np.sum(p * np.log2(p))
            return ent
    
        # 计算信息增益
        def Gain(self, D, attribute):
            # 统计属性attribute的每个取值的样本数
            attribute_values = np.squeeze(D[:, self.attribute_list.index(attribute)])  # 获取每个样本在属性attribute上的取值
            attribute_keys = np.array(list(set(list(attribute_values))))  # 获取所有属性值
            D_split = []
            for i in range(attribute_keys.shape[0]):
                mask = (attribute_values == attribute_keys[i])
                D_split.append(D[mask])  # 按照属性 attribute每个取值划分数据集
            D_split = np.array(D_split)
            # 计算每个属性值的信息熵
            ent_list = []
            attribute_i_count_list = []
            for i in range(D_split.shape[0]):
                ent_list.append(self.Ent(D_split[i]))
                attribute_i_count_list.append(D_split[i].shape[0])
            ent_list = np.array(ent_list)
            attribute_i_count_list = np.array(attribute_i_count_list)
            # 计算信息增益
            gain = self.Ent(D) - np.sum(attribute_i_count_list / D.shape[0] * ent_list)
            return gain
    
        # 计算增益率
        def Gain_ratio(self, D, attribute):
            D_attribute_values = np.squeeze(D[:, self.attribute_list.index(attribute)])  # 获取每个样本在属性attribute上的取值
            count_result=Counter(D_attribute_values)
            attribute_i_count_list=np.array(list(count_result.values()))
            IV=-1*np.sum(attribute_i_count_list/D.shape[0]*np.log2(attribute_i_count_list/D.shape[0]))
            gain_ratio=self.Gain(D,attribute)/IV
            return gain_ratio
    
        # 计算基尼值【数据集D的不纯度】
        def Gini(self,D):
            # 获取集合D的标签
            D_labels=D[:, -1]
            count_result = Counter(D_labels)
            # 统计每个标签的频数
            labels_count = np.array(list(count_result.values()))
            p = labels_count / D.shape[0]
            return 1-np.sum(p*p)
        
        # 计算基尼指数【计算属性attribute中按照某个属性划分得到的两个集合(二叉树)的基尼系数最小的作为划分属性】
        def Gini_index(self,D,attribute):
            # 获取样本集D在属性attribute上的取值
            D_attribute_values = np.squeeze(D[:, self.attribute_list.index(attribute)])  # 获取每个样本在属性attribute上的取值
            # 统计每个属性值的样本数【字典】
            count_result=Counter(D_attribute_values)
            # 统计属性的所有取值【转换成数组】
            attribute_keys=np.array(list(count_result.keys()))
    #         attribute_values_count_list=np.array(list(count_result.values()))
            # 按照不同属性值划分数据集【是/否】【CART算法是划分为二叉树,而不是多叉树】
            gini_index_list=[]
            for i in range(attribute_keys.shape[0]):
                D_split=[]
                D_split_count=[]
                mask = (D_attribute_values == attribute_keys[i])
                D_split.append(D[mask])  # 取值与属性值相同:是
                D_split.append(D[(1-mask).astype('bool')]) 
                D_split = np.array(D_split)
                D_split_count.append(D_split[0].shape[0])
                D_split_count.append(D_split[1].shape[0])
                D_split_count=np.array(D_split_count)
                # 计算按照该属性值划分后的Gini值
                gini_list=[]
                for i in range(D_split.shape[0]):
                    gini_list.append(self.Gini(D_split[i]))
                gini_list = np.array(gini_list)
                # 计算基尼指数
                gini_index = np.sum(D_split_count / D.shape[0] * gini_list)  # D.shape[0]==2
                gini_index_list.append(gini_index)
            # 选择最小的基尼指数作为属性attribute的基尼指数
            gini_index_list=np.array(gini_index_list)
            gini_index_min=np.min(gini_index_list)
            gini_index_min_attribute_value=attribute_keys[np.argmin(gini_index_list)]
            return gini_index_min,gini_index_min_attribute_value
            
    
        # 计算最优划分属性
        def get_bestAttribute(self, D, attribute_list, alg='ID3'):
            '''
            Notice: ID3和C4.5算法执行次函数有一个返回值,而CART算法有两个返回值
            '''
            if alg == 'ID3':
                best = attribute_list[0]
                max_gain = 0
                for i in attribute_list:
                    gain_i = self.Gain(D, i)
                    if gain_i > max_gain:
                        best = i
                        max_gain = gain_i
                # print('best=', best, 'max_gain=', max_gain)
                return best
            elif alg == 'C4.5':
                # 增益率准则对可取值数目较少的属性有所偏好,C4.5算法并不是直接选择增益率最大的候选划分属性,
                # 而是使用一个启发式:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的
                gain_list=[]
                for i in attribute_list:
                    gain_list.append(self.Gain(D,i))
                gain_list=np.array(gain_list)
                gain_mean=np.mean(gain_list)
                attribute_chosen=np.array(attribute_list)[gain_list>=gain_mean]  # 注意要加=,当只有一个属性值或者所有属性增益率相同时,没有属性的增益率大于平均值
                gain_rate_list=[]
                for i in attribute_chosen:
                    gain_rate_list.append(self.Gain_ratio(D,i))
                gain_rate_list=np.array(gain_rate_list)
                best = attribute_chosen[np.argmax(gain_rate_list)]
                return best
            elif alg=='CART':
                # 基尼值Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率,因此,Gini(D)值越小,数据集D的纯度越高
                # 在属性集中选择划分后基尼指数最小的属性作为最优属性
                gini_index_list=[]
                gini_index_attribute_value_list=[]
                for i in attribute_list:
                    gini_index_min,gini_index_min_attribute_value=self.Gini_index(D,i)
                    gini_index_list.append(gini_index_min)
                    gini_index_attribute_value_list.append(gini_index_min_attribute_value)
                gini_index_list=np.array(gini_index_list)
                gini_index_attribute_value_list=np.array(gini_index_attribute_value_list)
                
                best_attribute_idx=np.argmin(gini_index_list)
                return attribute_list[best_attribute_idx],gini_index_attribute_value_list[best_attribute_idx]
                
            else:
                raise Exception("请选择合法的划分属性选优算法!")
    
        # 构建决策树tree【这里树结构采用嵌套的字典类型】
        def createTree(self, tree, D, attributes,alg='ID3'):
            attribute_list = attributes.copy()
            # 判断数据集是否属于同一个类别【不用再划分】
            if self.isSameLabel(D):
                return D[0][-1]
    
            if self.isEmptyOrSameAttribute(D, attribute_list):
                # 获取样本数多的类
                labels = D[:, -1]  # 获取所有样本的标签
                labels_set = set(list(np.squeeze(labels)))  # 获取标签集合
                labels_dict = dict()  # 获取每个标签对应的样本
                for i in labels_set:  # 初始化
                    labels_dict[i] = 0
                for i in range(D.shape[0]):  # 统计每个标签的样本数
                    labels_dict[D[i][-1]] += 1
                keys = list(labels_dict.keys())
                values = list(labels_dict.values())
                return keys[np.argmax(values)]
    
            if alg=='ID3' or alg=='C4.5':
                # 选择最优划分属性【选择后需要在属性集中取出该属性再进行递归】
                best_attribute = self.get_bestAttribute(D, attribute_list, alg=alg)
    
                # 属性集取出最优属性,进行下一轮递归
                attribute_list.remove(best_attribute)
                # 获取数据集在最优属性上的所有取值
                attribute_values = self.attribute_value_list[best_attribute] 
    
                # 按照最优属性的每个值划分数据集
                D_attribute_values = np.squeeze(D[:, self.attribute_list.index(best_attribute)])  # 获取每个样本在属性attribute上的取值
                D_split = dict()
                # 按每个取值划分数据集
                for i in attribute_values:
                    mask = (D_attribute_values == i)
                    D_split[i] = D[mask]  # 按照属性 attribute每个取值划分数据集
    
                # 对最优属性的每个取值进行遍历
                subTree = dict()
    
                tree[best_attribute] = dict()
                for i in attribute_values:
                    if D_split[i].shape[0] == 0:  # 该属性上没有样本,根据父结点的样本分布作为当前结点的样本分布
                        labels=D[:,-1]
                        result=Counter(labels)
                        result_keys=list(result.keys())
                        result_values=list(result.values())
                        label=result_keys[np.argmax(result_values)]
                        subTree[i]=label
                        continue
                    subTree[i] = self.createTree(tree[best_attribute], D_split[i], attribute_list,alg=alg)
                
                tree[best_attribute] = subTree
                node=dict()    # 需要单独创建一个结点,而不能直接返回subTree或tree,会导致子节点为None
                node[best_attribute]=subTree
                return node  # 当某个属性值还需划分时,返回子树,否则该属性值的value为None
            elif alg=='CART':
                # 选择最优划分属性和最优属性值【CART算法与ID3和C4.5不同,CART算法使用属性值按是否相等划分成二叉树】
                best_attribute,best_attribute_value = self.get_bestAttribute(D, attribute_list, alg=alg)
    
                # CART算法的属性可以重复使用
    #             attribute_list.remove(best_attribute)
                # 获取数据集在最优属性上的所有取值
    #             attribute_values = self.attribute_value_list[best_attribute] 
    
                # 按照最优属性值划分成两个子数据集
                D_attribute_values = np.squeeze(D[:, self.attribute_list.index(best_attribute)])  # 获取每个样本在属性attribute上的取值
                D_split = dict()
                # 按照最优属性值划分数据集
                mask = (D_attribute_values == best_attribute_value)
                D_split['yes'] = D[mask]  
                D_split['no'] = D[(1-mask).astype('bool')]
    
                # 对最优属性的每个取值进行遍历
                subTree = dict()
    
                tree[best_attribute_value] = dict()
                attribute_values=['yes','no']
            
                for i in attribute_values:                    
                    subTree[i] = self.createTree(tree[best_attribute_value], D_split[i], attribute_list,alg=alg)
                    
                tree[best_attribute_value] = subTree
    
                node=dict()    # 需要单独创建一个结点,而不能直接返回subTree或tree,会导致子节点为None
                node[best_attribute_value]=subTree
                return node  # 当某个属性值还需划分时,返回子树,否则该属性值的value为None
    
        # 构建决策树
        def build(self,alg='ID3'):
            self.createTree(self.tree, self.D, self.attribute_list,alg=alg)
    
        # 可视化决策树【递归输出】
        def show(self,tree,blank):
            if type(tree)!=type(self.tree):
                return
            keys=list(tree.keys())
            for i in keys:
                for t in range(blank):
                    print('\t', end='')
                print('{',i,':')
                self.show(tree[i],blank+1)
                if type(tree[i])!=type(self.tree):  # 是否为叶结点
                    for t in range(blank + 1):
                        print('\t', end='')
                    print(tree[i])
                for t in range(blank):
                    print('\t', end='')
                print('}')
                
        # 可视化决策树【调包pprint】
        def showTreeDict(self):
            pprint.pprint(self.tree)
    
        # 可视化决策树【调包json】    
        def showTreeDictJson(self):
            js=json.dumps(self.tree,indent=8,ensure_ascii=False)
            print(js)
        
        # 使用ID3/C4.5生成的决策树进行判断
        def decision(self,sample):
            print("输入样本:",sample)
            attribute=list(self.tree.keys())[0]  # '纹理'
            tree=self.tree
            while True:
                if type(tree)==type(self.tree):
                    tree = tree[attribute]
                    tree=tree[sample[self.attribute_list.index(attribute)]]
                    if type(tree)==type(self.tree):
                        attribute=list(tree.keys())[0]
                else:
                    print("识别结果:",end='')
                    print('好瓜') if tree=='是' else print("坏瓜")
                    break
        
        # 使用CART生成的决策树进行判断
        def decision_CART(self,sample):
            print("输入样本:",sample)
            attribute=list(self.tree.keys())[0]  # '纹理'
            tree=self.tree
            while True:
                if type(tree)==type(self.tree):
                    # 获取树的key
                    attribute_value=list(tree.keys())[0]
                    # 检索对应的属性
                    attribute_idx=-1
                    attribute_value_set=set()
                    attribute_value_set.add(attribute_value)
                    for i in self.attribute_list:
                        if attribute_value_set.issubset(self.attribute_value_list[i]):
                            attribute_idx=self.attribute_list.index(i)
                            print(i)
                            break
                    if attribute_idx==-1:
                        raise Exception("Can't find the attribute of {}".format(attribute_value))
                    # 判断样本该属性值是否与决策树的属性值相等
                    attribute_value_equal=(attribute_value==sample[attribute_idx])
                    tree=tree[attribute_value]
                    if attribute_value_equal:
                        tree=tree['yes']
                    else:
                        tree=tree['no']
                else:
                    print("识别结果:",end='')
                    print('好瓜') if tree=='是' else print("坏瓜")
                    break
                    
    
    dt=DecisionTree()
    dt.build(alg='ID3')
    dt.showTreeDictJson()
    dt.decision(dt.D[0][:-1])
    
    {
            "纹理": {
                    "模糊": "否",
                    "稍糊": {
                            "触感": {
                                    "软粘": "是",
                                    "硬滑": "否"
                            }
                    },
                    "清晰": {
                            "根蒂": {
                                    "硬挺": "否",
                                    "蜷缩": "是",
                                    "稍蜷": {
                                            "色泽": {
                                                    "乌黑": {
                                                            "触感": {
                                                                    "软粘": "否",
                                                                    "硬滑": "是"
                                                            }
                                                    },
                                                    "青绿": "是",
                                                    "浅白": "是"
                                            }
                                    }
                            }
                    }
            }
    }
    输入样本: ['青绿' '蜷缩' '浊响' '清晰' '凹陷' '硬滑']
    识别结果:好瓜
    
    dt=DecisionTree()
    dt.build(alg='C4.5')
    dt.showTreeDictJson()
    dt.decision(dt.D[0][:-1])
    
    {
            "纹理": {
                    "模糊": "否",
                    "稍糊": {
                            "触感": {
                                    "软粘": "是",
                                    "硬滑": "否"
                            }
                    },
                    "清晰": {
                            "触感": {
                                    "软粘": {
                                            "色泽": {
                                                    "乌黑": "否",
                                                    "青绿": {
                                                            "根蒂": {
                                                                    "硬挺": "否",
                                                                    "蜷缩": "是",
                                                                    "稍蜷": "是"
                                                            }
                                                    },
                                                    "浅白": "否"
                                            }
                                    },
                                    "硬滑": "是"
                            }
                    }
            }
    }
    输入样本: ['青绿' '蜷缩' '浊响' '清晰' '凹陷' '硬滑']
    识别结果:好瓜
    
    dt=DecisionTree()
    dt.build(alg='CART')
    # pprint.pprint(dt.tree)
    # dt.show(dt.tree,0)
    dt.showTreeDictJson()
    dt.decision_CART(dt.D[0][:-1])
    
    {
            "清晰": {
                    "yes": {
                            "硬滑": {
                                    "yes": "是",
                                    "no": {
                                            "青绿": {
                                                    "yes": {
                                                            "稍蜷": {
                                                                    "yes": "是",
                                                                    "no": "否"
                                                            }
                                                    },
                                                    "no": "否"
                                            }
                                    }
                            }
                    },
                    "no": {
                            "乌黑": {
                                    "yes": {
                                            "浊响": {
                                                    "yes": "是",
                                                    "no": "否"
                                            }
                                    },
                                    "no": "否"
                            }
                    }
            }
    }
    输入样本: ['青绿' '蜷缩' '浊响' '清晰' '凹陷' '硬滑']
    纹理
    触感
    识别结果:好瓜
    

    谨以此纪念《数据挖掘与机器学习》课程期末考试手算ID3决策树!o(╥﹏╥)o ——2021.1.21

    展开全文
  • 决策树算法Python实现

    万次阅读 多人点赞 2018-08-09 16:39:25
    1 什么是决策树 决策树(Decision Tree)是一种基本的分类与回归方法,本文主要讨论分类决策树决策树模型呈树形结构,在分类问题中,表示基于特征对数据进行分类的过程。它可以认为是if-then规则的集合。每个内部...
  • python实现决策树

    2020-11-28 14:20:57
    参考:《机器学习实战》- Machine Learning in Action一、 基本思想我们所熟知的决策树的形状可能如下:使用决策树算法的目的就是生成类似于上图的分类效果。所以算法的主要步骤就是如何去选择结点。划分数据集的...
  • python实现机器学习之决策树分类算法,简单易学,而且可直接运行。
  • ID3决策树算法及其Python实现

    千次阅读 2021-10-29 09:39:25
    目录一、决策树算法基础理论决策树的学习过程ID3算法二、实现针对西瓜数据集的ID3算法实现代码参考文章 一、决策树算法 决策树是一种基于树结构来进行决策的分类算法,我们希望从给定的训练数据集学得一个模型(即...
  • 为什么要改进成C4.5算法 原理 C4.5算法是在ID3算法上的一种改进,它与ID3算法最大的区别就是特征选择上有所不同,一个是基于信息增益比,一个是基于信息增益。 之所以这样做是因为信息增益倾向于选择取值比较多的...
  • 决策树既可以用于分类也可以用于回归,它的原理是通过对一系列问题进行if/else推导,最终实现决策。
  • python实现决策树算法

    2019-03-30 19:48:30
    通过python基础语言实现机器学习中基础算法-决策树。有助于初学机器学习的小白加深对机器学习的理解。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,278
精华内容 10,911
关键字:

决策树算法python实现

友情链接: ziwu.zip