文档章节

python决策树 math库ID3算法

悲喜世界
 悲喜世界
发布于 01/30 14:49
字数 1143
阅读 84
收藏 0

每周一搏,提升自我。

python开发人工智能如火如荼,公司又安排任务,抱着无知者无畏的态度,开始学。

搭建环境:

    python:2.7.14

    编辑器:sublime text3

安装步骤和方法:https://my.oschina.net/wangzonghui/blog/1603104

安装学习库:

    pip install numpy

    pip install scipy

    pip install matplotlib

    pip install scikit-learn

 

决策树是人工智能的入门级监督式算法,从程序角度相对好理解,主要过程是根据训练数据的特征和结果,生成一套相应算法,评定测试数据,生成结论。

决策树的数学理论支持有香农熵(信息熵)基尼不纯度,本人对高等数学不怎么感冒,不是太懂,感兴趣的可以百度。

主流算法如下:

ID3:第一代,有缺陷,基础的一代,入门最好。选择最大增益的特征划分数据。

C45:ID3的扩展板增加了IDC功能。选择最大增益比的特征划分数据。

C50:C45的优化版,准确效率更高。是一个商业软件,公众是不可能得到的。

CART:分类回归树,使用基尼不纯度来决定划分,它和C45区别是 1、叶节点不是具体分类,而是一个函数,该函数定义了在该条件下的回归函数 2、CART是二叉树,不是多叉树。

除了CART其他都是基于香农熵实现。

下面是ID3代码:

#!/usr/bin/python
#coding:utf-8

from math import log
import operator

#计算给定数据集的香农熵
def calcShannonEnt(dataSet):
    numEntries=len(dataSet)  #数据集长度
    lableCounts={}
    for featVec in dataSet:
        currentLable=featVec[-1]  #数据集最后一个标签,特征数量-1
        if currentLable not in lableCounts.keys():
            lableCounts[currentLable]=0
        lableCounts[currentLable]+=1 #判断标签是否在当前字典的键值中,是键值为1
    shannonEnt=0
    for key in lableCounts:
        prob=float(lableCounts[key])/numEntries  #计算响应标签概率
        shannonEnt -=prob* log(prob,2)            #计算香农熵并且返回
    return shannonEnt

#创建简单的数据集   武器类型(0 步枪 1机枪),子弹(0 少 1多),血量(0 少,1多)  fight战斗 1逃跑 
def createDataSet():
    dataSet =[[1,1,0,'fight'],[1,0,1,'fight'],[1,0,1,'fight'],[1,0,1,'fight'],[0,0,1,'run'],[0,1,0,'fight'],[0,1,1,'run']]
    lables=['weapon','bullet','blood']
    return dataSet,lables

#按行打印数据集
def printData(myData):
    for item in myData:
        print '%s' %(item)

#给定特征划分数据集  dataSet(数据)  axis(数据下标)  value(数据值)
def splitDataSet(dataSet,axis,value):
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

#选择最好的数据集划分方式 
#用这个方法必须满足条件:1、数据必须是一种由列元素组成的列表   2、所有列表元素都要具有相同的数据长度 
#3、数据的最后一列是当前数据的类别标签
def chooseBestFeatureToSplit(dataSet):
    numFeatures=len(dataSet[0])-1  #数据集最后一个标签,特征数量-1
    baseEntropy=calcShannonEnt(dataSet)
    bestInfoGain=0
    bestFeature=-1
    for i in range(numFeatures):
        featList=[example[i] for example in dataSet]
        uniqueVals =set(featList)
        newEntropy=0
        for value in uniqueVals:
            subDataSet =splitDataSet(dataSet,i,value)
            prob=len(subDataSet)/float(len(dataSet))
            newEntropy+=prob * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if(infoGain > bestInfoGain):
            bestInfoGain=infoGain
            bestFeature=i
    return bestFeature


#构建决策树
def createTree(dataSet,lables):
    classList=[example[-1] for example in dataSet]
    if classList.count(classList[0])==len(classList):
        return classList[0]
    if len(dataSet[0] )== 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLable = lables[bestFeat]
    myTree={bestFeatLable:{}}
    del(lables[bestFeat])
    featValues=[example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLables = lables[:]
        myTree[bestFeatLable][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLables)
    return myTree


#挑选出现次数最多的分类名称
def majorityCnt(classList):
    classCount=[]
    for vote in classList:
        if vote not in classCount.keys():classCount[vote]=0
        classCount[vote] +=1
    sortedClassCount = sorted(ClassCount.iteritems(),key=operator.itemgetter(1),reverse=true)
    return sortedClassCount[0][0]

#使用决策树分类
def classify(inputTree,featLabels,testVec):
    firstStr=inputTree.keys()[0]
    secondDict=inputTree[firstStr]
    featIndex=featLabels.index(firstStr)
    for key in secondDict.keys():
        if testVec[featIndex] ==key:
            if type(secondDict[key]).__name__=='dict':
                classLabel=classify(secondDict[key],featLabels,testVec)
            else:classLabel=secondDict[key]
    return classLabel

#存储决策树
def storeTree(inputTree,filename):
    import pickle
    fw=open(filename,'w')
    pickle.dump(inputTree,fw)
    fw.close()


#获取决策树
def grabTree(filename):
    import pickle
    fr=open(filename)
    return pickle.load(fr)


######################运行测试######################
myDat,lables=createDataSet()
# printData(myDat)    #打印数据
#result=calcShannonEnt(myDat) #计算香农熵值
#print(result)

#根据传入特征拆分数据
# jiqiang=splitDataSet(myDat,0,1)
# printData(jiqiang)
# buqiang=splitDataSet(myDat,0,0)
# printData(buqiang)

# 比较所有特征的信息增益,返回最好特征划分的索引值
#chooseBestFeatureToSplit(myDat) #根据结果显示 武器类型值最大,是最好的用于划分数据集的特征

#构建决策树  {'weapon': {0: {'blood': {0: 'fight', 1: 'run'}}, 1: 'fight'}}
#该例子中包含了3个叶子节点和2个判断节点
tree=createTree(myDat,lables)
print(tree)

#根据决策树,预测结果
# dat,lab=createDataSet()
# result=classify(tree,lab,[1,0,0])
# print "结果是",result

直接运行出结果。天天学习,快乐无限。

 

© 著作权归作者所有

共有 人打赏支持
悲喜世界
粉丝 3
博文 23
码字总数 14227
作品 0
大兴
程序员
私信 提问
决策树 学习笔记

基本概念 算法杂货铺的这篇介绍说的比较生动详细 决策树算法原理(上) 对ID3、C4.5 的算法思想做了总结。介绍了两种算法的过程,以及优缺点。 ID3 构造决策树是基于信息增益最大的情况进行。...

喵_十八
2017/12/04
0
0
机器学习之决策树(Decision Tree)及其Python代码实现

  决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经...

大黄有故事
2017/02/10
0
0
机器学习笔记之信息熵、信息增益和决策树(ID3算法)

决策树算法: 优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关的特征数据。 缺点:可能会产生过度匹配问题。 适用数据类型:数值型和标称型。 算法原理: 决...

SilenceYaung
06/30
0
0
decisionTree填坑记

定义 其实决策树的定义用一个邮件分类系统去诠释一下。 if 我们收到一个来自邮件域为funny.com的邮件 : 我们将这份邮件甩到无聊的时候才会去读的栏目中 elif 收到的邮件中包含字眼“爱人” ...

Uncle_OJ
2017/12/05
0
2
机器学习实战---ID3决策树

今天给大家带来一个很好用的分类和预测方法—决策树 决策树是一种监督算法,以树状图为基础,输出结果为一系列简单实用的规则,有点像if-then语句,这里偷一个图: 我们看到,决策树就是把数据按照...

qq_39525832
05/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

程序中设置MySQL的默认值

import com.alibaba.fastjson.JSON;import java.beans.PropertyDescriptor;import java.lang.annotation.*;import java.lang.reflect.Field;import java.lang.reflect.Method;impo......

laolin23
18分钟前
1
0
WordPress没有上级目录的写权限

sudo chmod -R 777 wordpress/wp-content

临江仙卜算子
25分钟前
2
0
大数据学习之大数据技术笔记—spring入门

篇一 spring介绍 spring.io 官网 快速开始 Aop 面向切面编程,可以任何位置,并且可以细致到方法上 连接框架与框架 Spring 就是 IOC AOP 思想 有效的组织中间层对象一般都是切入 service 层 ...

董黎明
26分钟前
5
0
ASP.NET Core MVC 静态文件配置

在启动文件中添加以下配置 public class Startup{ public IServiceProvider ConfigureServices(IServiceCollection services) { services.AddDirectoryBrowser(); ......

whltian
54分钟前
1
0
linux之自定义命令

本人使用的是ubuntu系统,不喜欢建各种桌面快捷链接,但是每次启动个软件,去查找又麻烦,所以自定义了命令,来快捷的启动应用: 1、修改/etc/bash.bashrc,在文件末尾,加上如下List-1中的内...

克虏伯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部