python代码实现ID3决策树算法

本文实例为大家分享了python实现ID3决策树算法的具体代码,供大家参考,具体内容如下

'''''
Created on Jan 30, 2015 

@author: 史帅
''' 

from math import log
import operator
import re 

def fileToDataSet(fileName):
  '''''
  此方法功能是:从文件中读取样本集数据,样本数据的格式为:数据以空白字符分割,最后一列为类标签 

    参数:
      fileName:存放样本集数据的文件路径 

    返回值:
      dataSet:样本集数据组成的二维数组
  '''
  file=open(fileName, mode='r')
  lines=file.readlines()
  dataSet=[]
  index=0
  p=re.compile(r"\s+")
  for line in lines:
    line=p.split(line.strip())
    dataSet.append(line)
    index+=1
  return dataSet 

def calculateShannonEntropy(dataSet):
  '''''
  此方法功能是:计算样本集数据类别的信息熵,样本数据的格式为二维数组 

    参数:
      dataSet:样本集数据组成的二维数组 

    返回值:
      shannonEntropy:样本集数据类别的信息熵
  '''
  dataCount=len(dataSet)
  classCountDic={}
  for data in dataSet:
    label=data[-1]
    if label not in classCountDic.keys():
      classCountDic[label]=0
    classCountDic[label]+=1
  shannonEntropy=0.0
  for key in classCountDic:
    prob=float(classCountDic[key])/dataCount
    shannonEntropy-=prob*log(prob,2)
  return shannonEntropy 

def splitDataSet(dataSet,axis,value):
  '''''
  此方法功能是:对样本集数据按照某一特征进行分割,使得分割后的数据集中该特征的值全部等于同一个值,并且将分割后的数据中该特征列去除 

    参数:
      dataSet:待分割的样本集数据,二维数组
      axis:特征所在样本集数据列中的位置
      value:样本集数据分割后该特征的值 

    返回值:
      splitedDataSet:按照所在位置为axis的特征进行分割,并且该特征值为value的样本集数据的子集
  '''
  splitedDataSet=[]
  for data in dataSet:
    if data[axis]==value:
      splitedData=data[:axis]
      splitedData.extend(data[axis+1:])
      splitedDataSet.append(splitedData)
  return splitedDataSet 

def chooseBestFeatureToSlipt(dataSet):
  '''''
  此方法功能是:分别计算整个样本集数据的信息熵与按照各个特征分割后的数据集的信息熵之差,得到使差值最大的分割方案,得到该分割方案的特征 

    参数:
      dataSet:待分割的样本集数据,二维数组 

    返回值:
      bestFeature:按照分割前后信息熵差值最大的分割方案得到的特征,返回此特征所在样本集数据列中的位置
  '''
  bestFeature=-1
  dataSetShannonEntropy=calculateShannonEntropy(dataSet)
  infoGain=0
  featureCount=len(dataSet[0])-1
  for i in range(featureCount):
    featureList=[example[i] for example in dataSet]
    featureSet=set(featureList)
    splitedDataSetShannonEntropy=0
    for feature in featureSet:
      splitedDataSet=splitDataSet(dataSet,i,feature)
      splitedDataSetShannonEntropy+=float(len(splitedDataSet))/len(dataSet)*calculateShannonEntropy(splitedDataSet)
    if dataSetShannonEntropy-splitedDataSetShannonEntropy>infoGain:
      infoGain=dataSetShannonEntropy-splitedDataSetShannonEntropy
      bestFeature=i
  return bestFeature 

def majorityClass(classList):
  '''''
  此方法功能是:从类别列表中得到个数最多的类别 

    参数:
      classList:类别列表,一维数组 

    返回值:
      类别列表中个数最多的类别
  '''
  classCountDic={}
  for label in classList:
    if label not in classCountDic.keys():
      classCountDic[label]=0
    classCountDic[label]+=1
  classCountDic=sorted(classCountDic.item(),key=operator.itemgetter(1),reverse=True)
  return classCountDic[0][0] 

def createTree(dataSet,features):
  '''''
  此方法功能是:根据训练样本集数据创建对分类最有效的决策树 

    参数:
      dataSet:训练样本集数据,二维数组
      features:与训练样本集数据中各列的特征值相对应的特征名称集合,一维数组 

    返回值:
      tree:根据训练样本集数据所创建的,对分类最有效的决策树
  '''
  subFeatures=features[:]
  classList=[example[-1] for example in dataSet]
  if classList.count(classList[0])==len(classList):
    return classList[0]
  if len(dataSet[0])==1:
    return majorityClass(classList)
  bestFeature=chooseBestFeatureToSlipt(dataSet)
  label=subFeatures[bestFeature]
  tree={label:{}}
  del(subFeatures[bestFeature])
  featureList=[example[bestFeature] for example in dataSet]
  featureSet=set(featureList)
  for feature in featureSet:
    splitedDataSet=splitDataSet(dataSet,bestFeature,feature)
    tree[label][feature]=createTree(splitedDataSet, subFeatures)
  return tree 

def classify(inX,tree,features):
  '''''
  此方法功能是:根据创建好的决策树,对特定的数据进行分类 

    参数:
      inX:待分类的数据,特征值向量,一维数组
      tree:根据决策树算法创建好的最有效的决策树
      features:与训练样本集数据中各列的特征值相对应的特征名称集合,一维数组 

    返回值:
      label:待分类的数据通过决策树分类之后的类别
  '''
  feature=list(tree.keys())[0]
  featureIndex=features.index(feature)
  secondTree=tree[feature][inX[featureIndex]]
  if type(secondTree).__name__=="dict":
    label=classify(inX,secondTree,features)
  else:
    label=secondTree
  return label 

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

时间: 2017-12-17

机器学习python实战之决策树

决策树原理:从数据集中找出决定性的特征对数据集进行迭代划分,直到某个分支下的数据都属于同一类型,或者已经遍历了所有划分数据集的特征,停止决策树算法. 每次划分数据集的特征都有很多,那么我们怎么来选择到底根据哪一个特征划分数据集呢?这里我们需要引入信息增益和信息熵的概念. 一.信息增益 划分数据集的原则是:将无序的数据变的有序.在划分数据集之前之后信息发生的变化称为信息增益.知道如何计算信息增益,我们就可以计算根据每个特征划分数据集获得的信息增益,选择信息增益最高的特征就是最好的选择.首先我们先来

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

决策树的python实现方法

本文实例讲述了决策树的python实现方法.分享给大家供大家参考.具体实现方法如下: 决策树算法优缺点: 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关的特征数据 缺点:可能会产生过度匹配的问题 适用数据类型:数值型和标称型 算法思想: 1.决策树构造的整体思想: 决策树说白了就好像是if-else结构一样,它的结果就是你要生成这个一个可以从根开始不断判断选择到叶子节点的树,但是呢这里的if-else必然不会是让我们认为去设置的,我们要做的是提供一种方法,计算机可以根

python决策树之CART分类回归树详解

决策树之CART(分类回归树)详解,具体内容如下 1.CART分类回归树简介   CART分类回归树是一种典型的二叉决策树,可以处理连续型变量和离散型变量.如果待预测分类是离散型数据,则CART生成分类决策树:如果待预测分类是连续型数据,则CART生成回归决策树.数据对象的条件属性为离散型或连续型,并不是区别分类树与回归树的标准,例如表1中,数据对象xi的属性A.B为离散型或连续型,并是不区别分类树与回归树的标准. 表1 2.CART分类回归树分裂属性的选择   2.1 CART分类树--待预测

python编写分类决策树的代码

决策树通常在机器学习中用于分类. 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关特征数据. 缺点:可能会产生过度匹配问题. 适用数据类型:数值型和标称型. 1.信息增益 划分数据集的目的是:将无序的数据变得更加有序.组织杂乱无章数据的一种方法就是使用信息论度量信息.通常采用信息增益,信息增益是指数据划分前后信息熵的减少值.信息越无序信息熵越大,获得信息增益最高的特征就是最好的选择. 熵定义为信息的期望,符号xi的信息定义为: 其中p(xi)为该分类的概率. 熵,即信息

python机器学习之决策树分类详解

决策树分类与上一篇博客k近邻分类的最大的区别就在于,k近邻是没有训练过程的,而决策树是通过对训练数据进行分析,从而构造决策树,通过决策树来对测试数据进行分类,同样是属于监督学习的范畴.决策树的结果类似如下图: 图中方形方框代表叶节点,带圆边的方框代表决策节点,决策节点与叶节点的不同之处就是决策节点还需要通过判断该节点的状态来进一步分类. 那么如何通过训练数据来得到这样的决策树呢? 这里涉及要信息论中一个很重要的信息度量方式,香农熵.通过香农熵可以计算信息增益. 香农熵的计算公式如下: p(xi)

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

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

基于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 决策树算法的实现

''' 数据集:Mnist 训练集数量:60000 测试集数量:10000 ------------------------------ 运行结果:ID3(未剪枝) 正确率:85.9% 运行时长:356s ''' import time import numpy as np def loadData(fileName): ''' 加载文件 :param fileName:要加载的文件路径 :return: 数据集和标签集 ''' # 存放数据及标记 dataArr = []; labelArr

基于Python实现的ID3决策树功能示例

本文实例讲述了基于Python实现的ID3决策树功能.分享给大家供大家参考,具体如下: ID3算法是决策树的一种,它是基于奥卡姆剃刀原理的,即用尽量用较少的东西做更多的事.ID3算法,即Iterative Dichotomiser 3,迭代二叉树3代,是Ross Quinlan发明的一种决策树算法,这个算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总是生成最小的树型结构,而是一个启发式算法. 如下示例是一个判断海洋生物数据是否是鱼类而构建的基于ID3思想

python基于ID3思想的决策树

这是一个判断海洋生物数据是否是鱼类而构建的基于ID3思想的决策树,供大家参考,具体内容如下 # coding=utf-8 import operator from math import log import time def createDataSet(): dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no'], [0,0,'maybe']] labels = ['no surface

python 基于卡方值分箱算法的实现示例

原理很简单,初始分20箱或更多,先确保每箱中都含有0,1标签,对不包含0,1标签的箱向前合并,计算各箱卡方值,对卡方值最小的箱向后合并,代码如下 import pandas as pd import numpy as np import scipy from scipy import stats def chi_bin(DF,var,target,binnum=5,maxcut=20): ''' DF:data var:variable target:target / label binnum:

应用OpenCV和Python进行SIFT算法的实现详解

应用OpenCV和Python进行SIFT算法的实现 如下图为进行测试的gakki101和gakki102,分别验证基于BFmatcher.FlannBasedMatcher等的SIFT算法,对比其优劣.为体现出匹配效果对于旋转特性的优势,将图gakki101做成具有旋转特性的效果. 基于BFmatcher的SIFT实现 BFmatcher(Brute-Force Matching)暴力匹配,应用BFMatcher.knnMatch( )函数来进行核心的匹配,knnMatch(k-nearest

python Canny边缘检测算法的实现

图像边缘信息主要集中在高频段,通常说图像锐化或检测边缘,实质就是高频滤波.我们知道微分运算是求信号的变化率,具有加强高频分量的作用.在空域运算中来说,对图像的锐化就是计算微分.对于数字图像的离散信号,微分运算就变成计算差分或梯度.图像处理中有多种边缘检测(梯度)算子,常用的包括普通一阶差分,Robert算子(交叉差分),Sobel算子等等,是基于寻找梯度强度.拉普拉斯算子(二阶差分)是基于过零点检测.通过计算梯度,设置阀值,得到边缘图像. Canny边缘检测算子是一种多级检测算法.1986年由J

python常用排序算法的实现代码

这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升. 1.插入排序 插入排序默认当前被插入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序. def insertion_sort(old_list): n=len(old_list) k=0 for i in range(1,n): temp=old_lis

python 贪心算法的实现

贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 基本思路 思想 贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解.每一步只考虑一个数据,他的选取应该满足局部优化的条件.若

python em算法的实现

''' 数据集:伪造数据集(两个高斯分布混合) 数据集长度:1000 ------------------------------ 运行结果: ---------------------------- the Parameters set is: alpha0:0.3, mu0:0.7, sigmod0:-2.0, alpha1:0.5, mu1:0.5, sigmod1:1.0 ---------------------------- the Parameters predict is: al