关键词:
决策树
概述:通过分析每个数据特征项在分类过程中所起到的所用比重,将数据划分为几个数据子集,如果某个数据子集数据同一类型,则无需再继续划分数据分类,如果不属于同一分类,则需要在对数据子集进行分割。
优点:计算复杂度不高。
缺点:可能会出现由于样本特征值对应的样本数量不统一导致结果偏向于数量多的样本对应的分类。
具体分类算法 ID3算法
在每次划分数据集时我们会取一个特征属性来进行划分,那么这里有一个问题,例如训练样本里面有20个特征值,我们如何从这些特征中选择当前用于划分的最适合的特征项呢?我们需要找到一个有效的量化方法来划分数据。
信息熵
样本id | 是否需要浮出水面 | 是否有脚蹼 | 属于鱼 |
---|---|---|---|
1 | 是 | 是 | 是 |
2 | 是 | 是 | 是 |
3 | 是 | 否 | 是 |
4 | 否 | 是 | 否 |
5 | 否 | 是 | 否 |
我们划分数据的原则是将无须的数据变得更加有序,这里有一个信息增益的概念:即数据在划分前后的信息发生的变化成为信息增益。因此我们需要计算每个特征值的数据划分之后的信息增益值,选取最大的信息增益特征值作为当前数据划分特征。集合信息的度量方式成为熵,我们需要计算我们的信息集合熵值。
熵的计算公式:
H=−log2p(xi)
对于集合的熵计算公式:
H=−∑ni=1p(xi)log2p(xi)
计算信息熵算法
#-*- coding=utf-8 -*-
from numpy import *
from math import log
import operator
def calcShannonEnt(dataSet):
labelCounts = #统计每个标签的次数
for line in dataSet:
label = line[-1]
labelCounts[label] = labelCounts.get(label, 0) + 1
shannonEnt = 0.0
#统计信息熵
for key in labelCounts:
prob = float(labelCounts[key])/len(dataSet)
shannonEnt -= prob * log(prob, 2)
return shannonEnt
数据划分code
由于是决策树因此我们需要将集合划分为不同的子集
#例如上面的通过是否浮出水面划分数据就能得到两个子集
#子集1
#是否有脚蹼|属于鱼类
#是 | 是
#是 | 是
#否 | 是
#子集2
#是 | 否
#是 | 否
#axis表示特征项,value表示需要匹配的特征值
def splitDataSet(dataSet, axis, value):
resultDataSet = []
for line in dataSet:
if line[axis] == value:
reduceValue = line[:axis]
reduceValue.extend(line[axis+1 : ])
resultDataSet.append(reduceValue)
return resultDataSet
选择最优的划分属性
由于有上面两个方法作为基础,我们可以通过下面的代码来寻找最适合划分的特征值
def chooseBestSplitFeature(dataSet):
featureCount = len(dataSet[0]) - 1
#计算当前的熵值
currentShannonEnt = calcShannonEnt(dataSet)
#定义信息增益
bestInfoGain = 0.0
#定义返回值
bestAxis = -1
#遍历每个特征项
for i in range(featureCount):
featureValues = set([value[i] for value in dataSet])
subShannonEnt = 0.0
for featureValue in featureValues:
subDataSet = splitDataSet(dataSet, i, featureValues)
subDataSetProb = float(subDataSet)/len(dataSet)
subShannonEnt += subDataSetProb * calcShannonEnt(subDataSet)
subInfoGain = currentShannonEnt - subShannonEnt
#判断当先最优的划分特征
if subInfoGain > bestInfoGain :
bestInfoGain = subInfoGain
bestAxis = i
return bestAxis
构建决策树
我们可以通过一个map来表示我们的决策树
def createTree(dataSet):
classList = [value[-1] for value in dataSet]
#如果所有的classList一致则直接返回
if classList.count(classList[0]) == len(classList):
return classList[0]
if len(dataSet[0]) == 1:
##这里的case场景是,已经没有可用的特征项时,针对剩余的分类如何决定目标分类
#return dataSet[0]
#这里采用取占比最多的值
return major(dataSet)
#选择分类属性
axis = chooseBestSplitFeature(dataSet)
#定义tree树 属性 index->Map
myTree = axis:
featureList = set([value[axis] for value in dataSet])
for feature in featureList :
mytree[axis][feature] = createTree(splitDateSet(dataSet, axis, feature))
return mytree
#去占比最多的分类值
def major(dataSet):
labelCount=
for line in dataSet:
labelCount[line[-1] = labelCount.get(line[-1], 0) + 1
#排序
return sorted(labelCount.iteritems(), key = operator.itemgetter(1), reverse=True)[0][0]
关于python的序列化
决策树构建完成之后,我们可以将决策树序列化到一个文件中,以便以后直接使用,这里就涉及到python的序列化模块pickle
import pickle
def storeTree(myTree, fileName):
fw = open(fileName, 'w')
pickle.dumps(myTree, fw)
fw.close()
def readTree(fileName):
fr = open(fileName)
return pickle.load(fr)
机器学习:决策树(decisiontree)--id3算法(代码片段)
决策树的主要算法构建决策树的关键:按照什么样的次序来选择变量(属性/特征)作为分类依据。根据不同的目标函数,建立决策树主要有以下三种算法ID3(J.RossQuinlan-1975)核心:信息熵,信息增益C4.5——ID... 查看详情
机器学习总结决策树id3,c4.5算法,cart算法
本文主要总结决策树中的ID3,C4.5和CART算法,各种算法的特点,并对比了各种算法的不同点。决策树:是一种基本的分类和回归方法。在分类问题中,是基于特征对实例进行分类。既可以认为是if-then规则的集合,也可以认为是定... 查看详情
机器学习实战精读--------决策树
感觉自己像个学走路的孩子,每一步都很吃力和认真!机器根据数据集创建规则,就是机器学习。决策树:从数据集合中提取一系列规则,适用于探索式的知识发现。决策树本质:通过一系列规则对数据进行分类的过程。决策树... 查看详情
鹅厂优文|决策树及id3算法学习
...决策树是一种用树形结构来辅助行为研究、决策分析以及机器学习的方式,是机器学习中的一种基本的分类方法。决策树(DecisionTree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概... 查看详情
机器学习——决策树(下)算法实现
Decisiontree在机器学习(5)——决策树(上)原理中介绍了决策树的生成和剪枝原理。介绍了CART,ID3,C4.5等算法的算法流程,其中CART算法可以实现回归和分类,是基于基尼不纯度实现的,这里并未实... 查看详情
pyhon3实现机器学习经典算法id3决策树(代码片段)
一、ID3决策树概述 ID3决策树是另一种非常重要的用来处理分类问题的结构,它形似一个嵌套N层的IF…ELSE结构,但是它的判断标准不再是一个关系表达式,而是对应的模块的信息增益。它通过信息增益的大小,从根节点开始... 查看详情
决策树算法
决策树算法在机器学习中算是很经典的一个算法系列了。它既可以作为分类算法,也可以作为回归算法,同时也特别适合集成学习比如随机森林。本文就对决策树算法原理做一个总结,上篇对ID3,C4.5的算法思想做了总结,下... 查看详情
机器学习-决策树算法(id3c4.5和cart)
文章目录简介划分依据ID3算法C4.5算法CART算法处理连续值剪枝应用示例前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。简介决策树(DecisionTree)是... 查看详情
机器学习---算法---决策树
.../blog.csdn.net/qq_43208303/article/details/84837412 决策树是一种机器学习的方法。决策树的生成算法有ID3,C4.5和CART等。决策树是一种树形结构,其中每个内部节点表示一个属性上的判断,每个分支代表一个判断结果的输出,最后每个叶... 查看详情
机器学习_02_决策树
决策树也是一种基础的机器学习模型比如预测今天小明是否出去打球,那么我们知道一些特征,通过对特征的划分,我们可以做出一颗树,就是决策树,其实决策树在管理学也用的很多,主要是对每种情况给出一个概率,然后判断情况的... 查看详情
机器学习算法学习02:决策树的学习以及应用决策树解决cora数据集论文分类问题(代码片段)
机器学习算法学习02:决策树的学习以及应用决策树解决Cora数据集论文分类问题文章目录机器学习算法学习02:决策树的学习以及应用决策树解决Cora数据集论文分类问题1.前言2.算法分析2.1算法概述2.2算法优化3.算法代码3.... 查看详情
机器学习02-决策树id3算法
决策树概述:通过分析每个数据特征项在分类过程中所起到的所用比重,将数据划分为几个数据子集,如果某个数据子集数据同一类型,则无需再继续划分数据分类,如果不属于同一分类,则需要在对数据... 查看详情
人工智能机器学习之用python使用id3算法实例及使用sklearn的决策树算法对葡萄酒数据集进行分类
02-24决策树总结
...算法比较二、决策树优缺点2.1优点2.2缺点更新、更全的《机器学习》的更新网站,更有python、go、数据结构与算法、爬虫、人工智能教学等着你:https://www.cnblogs.com/nickchen121/决策树总结一、ID3算法、C4.5算法和CART算法比较算法树... 查看详情
机器学习(数据挖掘十个重要算法)
...据挖掘中常用的十个重要算法 一、C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的长处。并在下面几方面对ID3算法进行了改进: 1)用信息增益率来选择属性,克... 查看详情
决策树分类算法(id3)
...结点代表类或类分布。树的最顶层是根结点。 2. 机器学习中分类方法中的一个重要算法 3. 构造决策树的基本算法 查看详情
机器学习——决策树(上)原理
Decisiontree决策树是机器学习中一种基本的分类和回归算法,是依托于策略抉择而建立起来的树。其主要优点是模型具有可读性,分类速度快,易于理解。决策树的思想主要来源于Quinlan在1986年提出的ID3算法和1993年提出... 查看详情
开始学习机器学习时你必须要了解的模型有哪些?机器学习系列之决策树进阶篇(代码片段)
前言在上一篇文章中我们已经详细介绍了决策树模型,并且提到了ID3算法及其局限性,那么在本篇文章中,我们将会介绍基于ID3算法进行改良的C4.5算法以及决策树拟合度的优化问题。目录前言1C4.5算法1.1修改局部最优... 查看详情