python实现ID3决策树算法

ID3决策树是以信息增益作为决策标准的一种贪心决策树算法

# -*- coding: utf-8 -*-

from numpy import *
import math
import copy
import cPickle as pickle

class ID3DTree(object):
  def __init__(self): # 构造方法
    self.tree = {} # 生成树
    self.dataSet = [] # 数据集
    self.labels = [] # 标签集

  # 数据导入函数
  def loadDataSet(self, path, labels):
    recordList = []
    fp = open(path, "rb") # 读取文件内容
    content = fp.read()
    fp.close()
    rowList = content.splitlines() # 按行转换为一维表
    recordList = [row.split("\t") for row in rowList if row.strip()] # strip()函数删除空格、Tab等
    self.dataSet = recordList
    self.labels = labels

  # 执行决策树函数
  def train(self):
    labels = copy.deepcopy(self.labels)
    self.tree = self.buildTree(self.dataSet, labels)

  # 构件决策树:穿件决策树主程序
  def buildTree(self, dataSet, lables):
    cateList = [data[-1] for data in dataSet] # 抽取源数据集中的决策标签列
    # 程序终止条件1:如果classList只有一种决策标签,停止划分,返回这个决策标签
    if cateList.count(cateList[0]) == len(cateList):
      return cateList[0]
    # 程序终止条件2:如果数据集的第一个决策标签只有一个,返回这个标签
    if len(dataSet[0]) == 1:
      return self.maxCate(cateList)
    # 核心部分
    bestFeat = self.getBestFeat(dataSet) # 返回数据集的最优特征轴
    bestFeatLabel = lables[bestFeat]
    tree = {bestFeatLabel: {}}
    del (lables[bestFeat])
    # 抽取最优特征轴的列向量
    uniqueVals = set([data[bestFeat] for data in dataSet]) # 去重
    for value in uniqueVals: # 决策树递归生长
      subLables = lables[:] # 将删除后的特征类别集建立子类别集
      # 按最优特征列和值分隔数据集
      splitDataset = self.splitDataSet(dataSet, bestFeat, value)
      subTree = self.buildTree(splitDataset, subLables) # 构建子树
      tree[bestFeatLabel][value] = subTree
    return tree

  # 计算出现次数最多的类别标签
  def maxCate(self, cateList):
    items = dict([(cateList.count(i), i) for i in cateList])
    return items[max(items.keys())]

  # 计算最优特征
  def getBestFeat(self, dataSet):
    # 计算特征向量维,其中最后一列用于类别标签
    numFeatures = len(dataSet[0]) - 1 # 特征向量维数=行向量维数-1
    baseEntropy = self.computeEntropy(dataSet) # 基础熵
    bestInfoGain = 0.0 # 初始化最优的信息增益
    bestFeature = -1 # 初始化最优的特征轴
    # 外循环:遍历数据集各列,计算最优特征轴
    # i为数据集列索引:取值范围0~(numFeatures-1)
    for i in xrange(numFeatures):
      uniqueVals = set([data[i] for data in dataSet]) # 去重
      newEntropy = 0.0
      for value in uniqueVals:
        subDataSet = self.splitDataSet(dataSet, i, value)
        prob = len(subDataSet) / float(len(dataSet))
        newEntropy += prob * self.computeEntropy(subDataSet)
      infoGain = baseEntropy - newEntropy
      if (infoGain > bestInfoGain): # 信息增益大于0
        bestInfoGain = infoGain # 用当前信息增益值替代之前的最优增益值
        bestFeature = i # 重置最优特征为当前列
    return bestFeature

  # 计算信息熵
  # @staticmethod
  def computeEntropy(self, dataSet):
    dataLen = float(len(dataSet))
    cateList = [data[-1] for data in dataSet] # 从数据集中得到类别标签
    # 得到类别为key、 出现次数value的字典
    items = dict([(i, cateList.count(i)) for i in cateList])
    infoEntropy = 0.0
    for key in items: # 香农熵: = -p*log2(p) --infoEntropy = -prob * log(prob, 2)
      prob = float(items[key]) / dataLen
      infoEntropy -= prob * math.log(prob, 2)
    return infoEntropy

  # 划分数据集: 分割数据集; 删除特征轴所在的数据列,返回剩余的数据集
  # dataSet : 数据集; axis: 特征轴; value: 特征轴的取值
  def splitDataSet(self, dataSet, axis, value):
    rtnList = []
    for featVec in dataSet:
      if featVec[axis] == value:
        rFeatVec = featVec[:axis] # list操作:提取0~(axis-1)的元素
        rFeatVec.extend(featVec[axis + 1:])
        rtnList.append(rFeatVec)
    return rtnList
  # 存取树到文件
  def storetree(self, inputTree, filename):
    fw = open(filename,'w')
    pickle.dump(inputTree, fw)
    fw.close()

  # 从文件抓取树
  def grabTree(self, filename):
    fr = open(filename)
    return pickle.load(fr)

调用代码

# -*- coding: utf-8 -*-

from numpy import *
from ID3DTree import *

dtree = ID3DTree()
# ["age", "revenue", "student", "credit"]对应年龄、收入、学生、信誉4个特征
dtree.loadDataSet("dataset.dat", ["age", "revenue", "student", "credit"])
dtree.train()

dtree.storetree(dtree.tree, "data.tree")
mytree = dtree.grabTree("data.tree")
print mytree

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • python代码实现ID3决策树算法

    本文实例为大家分享了python实现ID3决策树算法的具体代码,供大家参考,具体内容如下 ''''' Created on Jan 30, 2015 @author: 史帅 ''' from math import log import operator import re def fileToDataSet(fileName): ''''' 此方法功能是:从文件中读取样本集数据,样本数据的格式为:数据以空白字符分割,最后一列为类标签 参数: fileName:存放样本集数据的文件路径 返回值:

  • python实现决策树ID3算法的示例代码

    在周志华的西瓜书和李航的统计机器学习中对决策树ID3算法都有很详细的解释,如何实现呢?核心点有如下几个步骤 step1:计算香农熵 from math import log import operator # 计算香农熵 def calculate_entropy(data): label_counts = {} for feature_data in data: laber = feature_data[-1] # 最后一行是laber if laber not in label_counts

  • 解读python如何实现决策树算法

    数据描述 每条数据项储存在列表中,最后一列储存结果 多条数据项形成数据集 data=[[d1,d2,d3...dn,result], [d1,d2,d3...dn,result], . . [d1,d2,d3...dn,result]] 决策树数据结构 class DecisionNode: '''决策树节点 ''' def __init__(self,col=-1,value=None,results=None,tb=None,fb=None): '''初始化决策树节点 args: col -

  • python决策树之C4.5算法详解

    本文为大家分享了决策树之C4.5算法,供大家参考,具体内容如下 1. C4.5算法简介   C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化.C4.5算法对ID3算法主要做了一下几点改进:   (1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足:   (2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理:   (3)构造决策树之后进行剪枝操作:   (4)能够处理具有缺失属性值的训练数据. 2

  • Python决策树和随机森林算法实例详解

    本文实例讲述了Python决策树和随机森林算法.分享给大家供大家参考,具体如下: 决策树和随机森林都是常用的分类算法,它们的判断逻辑和人的思维方式非常类似,人们常常在遇到多个条件组合问题的时候,也通常可以画出一颗决策树来帮助决策判断.本文简要介绍了决策树和随机森林的算法以及实现,并使用随机森林算法和决策树算法来检测FTP暴力破解和POP3暴力破解,详细代码可以参考: https://github.com/traviszeng/MLWithWebSecurity 决策树算法 决策树表现了对象属性和

  • python实现C4.5决策树算法

    C4.5算法使用信息增益率来代替ID3的信息增益进行特征的选择,克服了信息增益选择特征时偏向于特征值个数较多的不足.信息增益率的定义如下: # -*- coding: utf-8 -*- from numpy import * import math import copy import cPickle as pickle class C45DTree(object): def __init__(self): # 构造方法 self.tree = {} # 生成树 self.dataSet =

  • Python实现决策树C4.5算法的示例

    为什么要改进成C4.5算法 原理 C4.5算法是在ID3算法上的一种改进,它与ID3算法最大的区别就是特征选择上有所不同,一个是基于信息增益比,一个是基于信息增益. 之所以这样做是因为信息增益倾向于选择取值比较多的特征(特征越多,条件熵(特征划分后的类别变量的熵)越小,信息增益就越大):因此在信息增益下面加一个分母,该分母是当前所选特征的熵,注意:这里而不是类别变量的熵了. 这样就构成了新的特征选择准则,叫做信息增益比.为什么加了这样一个分母就会消除ID3算法倾向于选择取值较多的特征呢? 因为特

  • python实现决策树C4.5算法详解(在ID3基础上改进)

    一.概论 C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点.而C4.5引入了新概念"信息增益率",C4.5是选择信息增益率最大的属性作为树节点. 二.信息增益 以上公式是求信息增益率(ID3的知识点) 三.信息增益率 信息增益率是在求出信息增益值在除以. 例如下面公式为求属性为"outlook"的值: 四.C4.5的完整代码 from numpy import * from scipy import * from mat

  • Python机器学习之决策树算法实例详解

    本文实例讲述了Python机器学习之决策树算法.分享给大家供大家参考,具体如下: 决策树学习是应用最广泛的归纳推理算法之一,是一种逼近离散值目标函数的方法,在这种方法中学习到的函数被表示为一棵决策树.决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,机器学习算法最终将使用这些从数据集中创造的规则.决策树的优点为:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据.缺点为:可能产生过度匹配的问题.决策树适于处理离散型和连续型的数据. 在决策树中最重要的就是如何选取

  • 基于ID3决策树算法的实现(Python版)

    实例如下: # -*- coding:utf-8 -*- from numpy import * import numpy as np import pandas as pd from math import log import operator #计算数据集的香农熵 def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} #给所有可能分类创建字典 for featVec in dataSet: currentLa

  • Python决策树分类算法学习

    从这一章开始进入正式的算法学习. 首先我们学习经典而有效的分类算法:决策树分类算法. 1.决策树算法 决策树用树形结构对样本的属性进行分类,是最直观的分类算法,而且也可以用于回归.不过对于一些特殊的逻辑分类会有困难.典型的如异或(XOR)逻辑,决策树并不擅长解决此类问题. 决策树的构建不是唯一的,遗憾的是最优决策树的构建属于NP问题.因此如何构建一棵好的决策树是研究的重点. J. Ross Quinlan在1975提出将信息熵的概念引入决策树的构建,这就是鼎鼎大名的ID3算法.后续的C4.5,

  • Python机器学习之决策树算法

    一.决策树原理 决策树是用样本的属性作为结点,用属性的取值作为分支的树结构. 决策树的根结点是所有样本中信息量最大的属性.树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性.决策树的叶结点是样本的类别值.决策树是一种知识表示形式,它是对所有样本数据的高度概括决策树能准确地识别所有样本的类别,也能有效地识别新样本的类别. 决策树算法ID3的基本思想: 首先找出最有判别力的属性,把样例分成多个子集,每个子集又选择最有判别力的属性进行划分,一直进行到所有子集仅包含同一类型的数据为止.最后

  • python实现决策树分类算法

    本文实例为大家分享了python实现决策树分类算法的具体代码,供大家参考,具体内容如下 1.概述 决策树(decision tree)--是一种被广泛使用的分类算法. 相比贝叶斯算法,决策树的优势在于构造过程不需要任何领域知识或参数设置 在实际应用中,对于探测式的知识发现,决策树更加适用. 2.算法思想 通俗来说,决策树分类的思想类似于找对象.现想象一个女孩的母亲要给这个女孩介绍男朋友,于是有了下面的对话: 女儿:多大年纪了? 母亲:26. 女儿:长的帅不帅? 母亲:挺帅的. 女儿:收入高不?

随机推荐