使用Python实现决策树

# -*- coding: utf-8 -*-
import operator
from math import log


‘‘‘创建数据集   ‘‘‘
def createData（）:  
    dataSet=[[11‘yes‘][11‘yes‘][10‘no‘][01‘no‘][01‘no‘]]
    label=[‘no surfacing‘‘flippers‘]
    return dataSetlabel


‘‘‘计算数据集的信息熵 （信息熵即指类别标签的混乱程度，值越小越好）‘‘‘
def calcshan（dataSet）:   
    lenDataSet=len（dataSet）
    p={}
    H=0.0
    for data in dataSet:
        currentLabel=data[-1]  #获取类别标签
        if currentLabel not in p.keys（）:  #若字典中不存在该类别标签，即创建
            p[currentLabel]=0
        p[currentLabel]+=1    #递增类别标签的值
    for key in p:
        px=float（p[key]）/float（lenDataSet）  #计算某个标签的概率
        H-=px*log（px2）  #计算信息熵
    return H
        
            
‘‘‘根据某一特征分类数据集‘‘‘
def spiltData（dataSetaxisvalue）:    #dataSet为要划分的数据集axis为给定的特征，value为给定特征的具体值
    subDataSet=[]
    for data in dataSet:
        subData=[]
        if data[axis]==value:
            subData=data[:axis]  #取出data中第0到axis-1个数进subData;
            subData.extend（data[axis+1:]）  #取出data中第axis+1到最后一个数进subData;这两行代码相当于把第axis个数从数据集中剔除掉
            subDataSet.append（subData） #此处要注意expend和append的区别
    return subDataSet


‘‘‘遍历所有特征，选择信息熵最小的特征，即为最好的分类特征‘‘‘      
def chooseBestFeature（dataSet）:  
    lenFeature=len（dataSet[0]）-1    #计算特征维度时要把类别标签那一列去掉
    shanInit=calcshan（dataSet）      #计算原始数据集的信息熵
    feature=[]
    inValue=0.0
    bestFeature=0
    for i in range（lenFeature）:
        shanCarry=0.0
        feature=[example[i] for example in dataSet]  #提取第i个特征的所有数据
        feature=set（feature）  #得到第i个特征所有的分类值，如‘0‘和‘1‘
        for feat in feature:  
            subData=spiltData（dataSetifeat）  #先对数据集按照分类值分类
            prob=float（len（subData））/float（len（dataSet））
            shanCarry+=prob*calcshan（subData）  #计算第i个特征的信息熵
        outValue=shanInit-shanCarry  #原始数据信息熵与循环中的信息熵的差
        if （outValue>inValue）:
            inValue=outValue  #将信息熵与原始熵相减后的值赋给inValue，方便下一个循环的信息熵差值与其比较
            bestFeature=i
    return bestFeature

  
‘‘‘ 如果数据集已经处理了所有属性，但是类标签依然不是唯一时使用，采用多数表决的方法定义该节点的分类‘‘‘
def majorCount（classList）:
    classCount={}
    for vote in classList:
        if vote not in classCount.keys（）:  #若字典中不存在该类别标签，即创建
            classCount[vote]=0
        classCount[vote]+=1                #递增类别标签的值
    sortedClassCount=sorted（classCount.iterit