python实现ID3决策树算法
决策树之ID3算法及其Python实现，具体内容如下
主要内容
决策树背景知识
决策树⼀般构建过程
ID3算法分裂属性的选择
ID3算法流程及其优缺点分析
ID3算法Python代码实现
1. 决策树背景知识
  决策树是数据挖掘中最重要且最常⽤的⽅法之⼀，主要应⽤于数据挖掘中的分类和预测。决策树是知识的⼀种呈现⽅式，决策树中从顶点到每个结点的路径都是⼀条分类规则。决策树算法最先基于信息论发展起来，经过⼏⼗年发展，⽬前常⽤的算法有：ID3、
C4.5、CART算法等。
2. 决策树⼀般构建过程
  构建决策树是⼀个⾃顶向下的过程。树的⽣长过程是⼀个不断把数据进⾏切分细分的过程，每⼀次切分都会产⽣⼀个数据⼦集对应的节点。从包含所有数据的根节点开始，根据选取分裂属性的属性值把训练集划分成不同的数据⼦集，⽣成由每个训练数据⼦集对应新的⾮叶⼦节点。对⽣成的⾮叶⼦节点再重复以上过程，直到满⾜特定的终⽌条件，停⽌对数据⼦集划分，⽣成数据⼦集对应的叶⼦节点，即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标，我们需要对决策树算法进⾏改善，直到达到预期的性能指标。
  注：分裂属性的选取是决策树⽣产过程中的关键，它决定了⽣成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。
3. ID3算法分裂属性的选择——信息增益
  属性的选择是决策树算法中的核⼼。是对决策树的结构、性能起到决定性的作⽤。ID3算法基于信息增益的分裂属性选择。基于信息增益的属性选择是指以信息熵的下降速度作为选择属性的⽅法。它以的信息论为基础，选择具有最⾼信息增益的属性作为当前节点的分裂属性。选择该属性作为分裂属性后，使得分裂后的样本的信息量最⼤，不确定性最⼩，即熵最⼩。
  信息增益的定义为变化前后熵的差值，⽽熵的定义为信息的期望值，因此在了解熵和信息增益之前，我们需要了解信息的定义。  信息：分类标签xi 在样本集 S 中出现的频率记为 p(xi)，则 xi 的信息定义为：−log2p(xi) 。
  分裂之前样本集的熵：E(S)=−∑Ni=1p(xi)log2p(xi)，其中 N 为分类标签的个数。
  通过属性A分裂之后样本集的熵：EA(S)=−∑mj=1|Sj||S|E(Sj)，其中 m 代表原始样本集通过属性A的属性值划分为 m 个⼦样本
集，|Sj| 表⽰第j个⼦样本集中样本数量，|S| 表⽰分裂之前数据集中样本总数量。
  通过属性A分裂之后样本集的信息增益：InfoGain(S,A)=E(S)−EA(S)
  注：分裂属性的选择标准为：分裂前后信息增益越⼤越好，即分裂后的熵越⼩越好。
4. ID3算法
  ID3算法是⼀种基于信息增益属性选择的决策树学习⽅法。核⼼思想是：通过计算属性的信息增益来选择决策树各级节点上的分裂属性，使得在每⼀个⾮叶⼦节点进⾏测试时，获得关于被测试样本最⼤的类别信息。基本⽅法是：计算所有的属性，选择信息增益最⼤的属性分裂产⽣决策树节点，基于该属性的
不同属性值建⽴各分⽀，再对各分⽀的⼦集递归调⽤该⽅法建⽴⼦节点的分⽀，直到所有⼦集仅包括同⼀类别或没有可分裂的属性为⽌。由此得到⼀棵决策树，可⽤来对新样本数据进⾏分类。
ID3算法流程：
(1) 创建⼀个初始节点。如果该节点中的样本都在同⼀类别，则算法终⽌，把该节点标记为叶节点，并⽤该类别标记。
(2) 否则，依据算法选取信息增益最⼤的属性，该属性作为该节点的分裂属性。
(3) 对该分裂属性中的每⼀个值，延伸相应的⼀个分⽀，并依据属性值划分样本。
(4) 使⽤同样的过程，⾃顶向下的递归，直到满⾜下⾯三个条件中的⼀个时就停⽌递归。
  A、待分裂节点的所有样本同属于⼀类。
  B、训练样本集中所有样本均完成分类。
  C、所有属性均被作为分裂属性执⾏⼀次。若此时，叶⼦结点中仍有属于不同类别的样本时，选取叶⼦结点中包含样本最多的类别，作为该叶⼦结点的分类。
ID3算法优缺点分析
优点：构建决策树的速度⽐较快，算法实现简单，⽣成的规则容易理解。
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，⽽这些属性不⼀定是最佳分裂属性；不能处理属性值连续的属性；⽆修剪过程，⽆法对决策树进⾏优化，⽣成的决策树可能存在过度拟合的情况。
5. ID3算法Python代码实现
# -*- coding: utf-8 -*-
__author__ = 'zhihua_oba'
import operator
from numpy import *
from math import log
#⽂件读取
def file2matrix(filename, attribute_num): #传⼊参数：⽂件名，属性个数
fr = open(filename)
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines) #统计数据集⾏数（样本个数）
dataMat = zeros((numberOfLines, attribute_num))
classLabelVector = [] #分类标签
index = 0
for line in arrayOLines:
line = line.strip() #strip() 删除字符串中的'\n'
listFromLine = line.split() #将⼀个字符串分裂成多个字符串组成的列表，不带参数时以空格进⾏分割，当代参数时，以该参数进⾏分割
dataMat[index, : ] = listFromLine[0:attribute_num] #读取数据对象属性值
classLabelVector.append(listFromLine[-1]) #读取分类信息
index += 1
dataSet = [] #数组转化成列表
index = 0
for index in range(0, numberOfLines):
temp = list(dataMat[index, :])
temp.append(classLabelVector[index])
dataSet.append(temp)
return dataSet
#划分数据集
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featvec in dataSet: #每⾏
if featvec[axis] == value: #每⾏中第axis个元素和value相等 #删除对应的元素，并将此⾏，加⼊到rerDataSet
reducedFeatVec = featvec[:axis]
retDataSet.append(reducedFeatVec)
return retDataSet
#计算⾹农熵 #计算数据集的⾹农熵 == 计算数据集类标签的⾹农熵
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)
return shannonEnt
#根据⾹农熵，选择最优的划分⽅式 #根据某⼀属性划分后，类标签⾹农熵越低，效果越好
def chooseBestFeatureToSplit(dataSet):
baseEntropy = calcShannonEnt(dataSet) #计算数据集的⾹农熵
numFeatures = len(dataSet[0])-1
bestInfoGain = 0.0 #最⼤信息增益
bestFeature = 0 #最优特征
for i in range(0, numFeatures):
featList = [example[i] for example in dataSet] #所有⼦列表（每⾏）的第i个元素，组成⼀个新的列表
uniqueVals = set(featList)
newEntorpy = 0.0
for value in uniqueVals: #数据集根据第i个属性进⾏划分，计算划分后数据集的⾹农熵
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntorpy += prob*calcShannonEnt(subDataSet)
infoGain = baseEntropy-newEntorpy #划分后的数据集，⾹农熵越⼩越好，即信息增益越⼤越好
if(infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
#如果数据集已经处理了所有属性，但叶⼦结点中类标签依然不是唯⼀的，此时需要决定如何定义该叶⼦结点。这种情况下，采⽤多数表决⽅法，对该叶⼦结点进⾏分类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] #数据集样本的类标签
unt(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]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
subDataSet = splitDataSet(dataSet, bestFeat, value)
myTree[bestFeatLabel][value] = createTree(subDataSet, subLabels)
return myTree
#测试算法：使⽤决策树，对待分类样本进⾏分类
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 main():
dataSet = file2matrix('', 4)
labels = ['attr01', 'attr02', 'attr03', 'attr04']
labelsForCreateTree = labels[:]
Tree = createTree(dataSet, labelsForCreateTree )
testvec = [2, 3, 2, 3]
print classify(Tree, labels, testvec)
if __name__ == '__main__':sortedlist
main()
以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。