#本算法前提，要熟悉决策树的理论知识，如:ID3算法流程，香农熵的计算公式和信息论原理
#数据集解释 是否属于鱼类是目标标量
#把数据离散化，变成标量型 是--》1 否 --》0
#变成
#在设定2个标签
#不浮出水面的鱼类 no surfacing
#有脚蹼的鱼类 flippers
#计算香农熵的方法 以二为底的对数 这里面的函数都是通用的
from math import log
import operator #operator模块输出一系列对应Python内部操作符的函数
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 #记录目标变量次数，出现一次就加1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries #计算概率
shannonEnt -= prob*log(prob,2) #求熵，通过循环
return shannonEnt #返回熵值
#创建数据集
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
#划分数据集 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:]) #extend()方法和append的区别
retDataSet.append(reducedFeatVec)
return retDataSet #返回按axis列上的value值划分的数据集
#选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet) - 1 #特征数
baseEntropy = calcShannonEnt(dataSet) #整个数据集的原始香农熵，用于后面比较
bestInfoGain = 0.0
bestFeature = -1 #用来存储特征值最好的那一列的列序号
for i in range(numFeatures): #i的作用控制列号，表示到底几个特征变量了
#重复工作为了求出唯一的元素序列 采用set方法，最快
featList = [example[i] for example in dataSet] #列表推导式
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 > bestFeature):
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=opetator.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(dataSet): #如果所有的类标签都一样，递归结束
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[:] #因为列表在函数传参时是引用传递的，所以要保存副本
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
return myTree #返回决策树
if __name__ == '__main__':
myDat,labels = createDataSet()
# myDat[0][-1] = 'maybe' #熵越高，混合的数据越多
# print(myDat)
# t=splitDataSet(myDat,1,1) #划分数据集
# x=calcShannonEnt(myDat) #求得的香农熵
# print("香农熵是:",x)
# print(t)
# bestFeature=chooseBestFeatureToSplit(myDat)
# print(bestFeature)
myTree = createTree(myDat,labels)
print(myTree) #打印ID3的分类决策树，字典形式
#结果分析(决策树如下)：no surfacing ->0->'no'
->1->flippers->0->'no'
->1->'yes'