
基本概念
决策树是分类算法。
数据类型:数值型和标称型。因为构造算法只适用于标称型,所以数值型数据必须离散化。
工作原理
利用香浓熵找到信息增益最大的特征,按照信息增益最大的特征划分数据,如此反复,让无序的数据变的更加有序。使用ID3算法构建树结构。当传入一个新数据时,按照数据找到对应树节点,直到最后没有叶子节点时,完成分类。
样例
不浮出水面是否可以生存? 是否有脚蹼? 是否是鱼类?
通过“不浮出水面是否可以生存”和“是否有脚蹼”这两个特征来判断是否是鱼类。构建一个简单决策树,如果得到一个新的生物,可以用此来判断是否是鱼类。
样例代码
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing','flippers'] return dataSet, labels
香农熵公式
如果待分类的事务可能划分在多个分类之中,则符号Xi的信息定义为:
其中P(Xi)是选择该分类的概率
为了计算熵,需要计算所有类别所有可能值包含的信息期望值总和,公式为:
其中n是分类的数目
香农熵算法
def calcShannonEnt(dataSet):
# 选择该分类的概率 就是每个类型/总个数
# 总数,多少行数据
numEntries = len(dataSet)
labelCounts = {} # 取到的每个类型个数
for featVec in dataSet:
currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts: # 得到选择该分类的概率
prob = float(labelCounts[key])/numEntries # 按照公式
shannonEnt -= prob * log(prob,2) #log base 2
return shannonEnt
按照香农熵划分数据
除了需要测量信息熵,还需要划分数据集,度量花费数据集的熵,以便判断当前是否正确划分。 循环计算香浓熵和splitDataSet(),找到最好的特征划分方式。
def splitDataSet(dataSet, axis, value):
# 这个算法返回axis下标之外的列
retDataSet = [] for featVec in dataSet: if featVec[axis] == value:
reducedFeatVec = featVec[:axis] #chop out axis used for splitting
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec) return retDataSetdef chooseBestFeatureToSplit(dataSet):
# 先取最后一列,用在标签结果:是鱼或不是鱼。
numFeatures = len(dataSet[0]) - 1
# 原始香浓熵
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
# 遍历所有的特征
for i in range(numFeatures): # 创建一个列表包含这个特征的所有值
featList = [example[i] for example in dataSet] # 利用set去重
uniqueVals = set(featList)
newEntropy = 0.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
数据集需要满足一定的要求:
数据必须是一种有列表元素组成的列表。(二维数组)
所有列表元素必须有相同长度。
最后一列必须是当前实例的标签。
递归构建决策树
多数表决算法
如果数据集已经处理了所有属性,但是类标签依然不是唯一的,此时需要决定如何定义该叶子节点,在这种情况下,我们通常会采用多数表决决定该叶子节点。
import operator 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 createTree(dataSet,labels):
# 取出结果
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) # 根据下标取出标签
bestFeatLabel = labels[bestFeat] # 构建树
myTree = {bestFeatLabel:{}} # 删除取出过的标签,避免重复计算
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet] # 利用set去重
uniqueVals = set(featValues) for value in uniqueVals: # 复制所有的子标签,因为是引用类型,以避免改变原始标签数据
subLabels = labels[:] # 递归的构建树
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) return myTree
使用决策树分类
def classify(inputTree,featLabels,testVec):
firstStr = inputTree.keys()[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr) # print 'featIndex %s' % (featIndex)
key = testVec[featIndex] # print 'key %s' % (key)
valueOfFeat = secondDict[key] if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLabels, testVec) else: classLabel = valueOfFeat return classLabel
dataSet, labels = createDataSet()
mytree = createTree(dataSet, labels[:]) #因为内部会删除labels里的值所以用这样copy一份 print mytree # {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}print classify(mytree, labels, [0,1])
no
决策树的存储
构造决策树是耗时的任务,即使处理很小的数据集。所以我们可以使用构造好的决策树。
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)
优点
计算复杂度不高
输出结果易于理解
对中间值缺失不敏感
可以处理不相关特侦
缺点
可能产生过度匹配问题
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
用 Power BI 制作地图热力图:基于经纬度数据的实践指南 在数据可视化领域,地图热力图凭借直观呈现地理数据分布密度的优势,成 ...
2025-07-24解析 insert into select 是否会锁表:原理、场景与应对策略 在数据库操作中,insert into select 是一种常用的批量数据插入语句 ...
2025-07-24CDA 数据分析师的工作范围解析 在数字化时代的浪潮下,数据已成为企业发展的核心资产之一。CDA(Certified Data Analyst)数据分 ...
2025-07-24从 CDA LEVEL II 考试题型看 Python 数据分析要点 在数据科学领域蓬勃发展的当下,CDA(Certified Data Analyst)认证成为众多从 ...
2025-07-23用 Python 开启数据分析之旅:从基础到实践的完整指南 在数据驱动决策的时代,数据分析已成为各行业不可或缺的核心能力。而 Pyt ...
2025-07-23鸢尾花判别分析:机器学习中的经典实践案例 在机器学习的世界里,有一个经典的数据集如同引路明灯,为无数初学者打开了模式识别 ...
2025-07-23解析 response.text 与 response.content 的核心区别 在网络数据请求与处理的场景中,开发者经常需要从服务器返回的响应中提取数 ...
2025-07-22解析神经网络中 Softmax 函数的核心作用 在神经网络的发展历程中,激活函数扮演着至关重要的角色,它们为网络赋予了非线性能力, ...
2025-07-22CDA数据分析师证书考取全攻略 一、了解 CDA 数据分析师认证 CDA 数据分析师认证是一套科学化、专业化、国际化的人才考核标准, ...
2025-07-22左偏态分布转正态分布:方法、原理与实践 左偏态分布转正态分布:方法、原理与实践 在统计分析、数据建模和科学研究中,正态分 ...
2025-07-22你是不是也经常刷到别人涨粉百万、带货千万,心里痒痒的,想着“我也试试”,结果三个月过去,粉丝不到1000,播放量惨不忍睹? ...
2025-07-21我是陈辉,一个创业十多年的企业主,前半段人生和“文字”紧紧绑在一起。从广告公司文案到品牌策划,再到自己开策划机构,我靠 ...
2025-07-21CDA 数据分析师的职业生涯规划:从入门到卓越的成长之路 在数字经济蓬勃发展的当下,数据已成为企业核心竞争力的重要来源,而 CD ...
2025-07-21MySQL执行计划中rows的计算逻辑:从原理到实践 MySQL 执行计划中 rows 的计算逻辑:从原理到实践 在 MySQL 数据库的查询优化中 ...
2025-07-21在AI渗透率超85%的2025年,企业生存之战就是数据之战,CDA认证已成为决定企业存续的生死线!据麦肯锡全球研究院数据显示,AI驱 ...
2025-07-2035岁焦虑像一把高悬的利刃,裁员潮、晋升无望、技能过时……当职场中年危机与数字化浪潮正面交锋,你是否发现: 简历投了10 ...
2025-07-20CDA 数据分析师报考条件详解与准备指南 在数据驱动决策的时代浪潮下,CDA 数据分析师认证愈发受到瞩目,成为众多有志投身数 ...
2025-07-18刚入职场或是在职场正面临岗位替代、技能更新、人机协作等焦虑的打工人,想要找到一条破解职场焦虑和升职瓶颈的系统化学习提升 ...
2025-07-182025被称为“AI元年”,而AI,与数据密不可分。网易公司创始人丁磊在《AI思维:从数据中创造价值的炼金术 ...
2025-07-18CDA 数据分析师:数据时代的价值挖掘者 在大数据席卷全球的今天,数据已成为企业核心竞争力的重要组成部分。从海量数据中提取有 ...
2025-07-18