本代码来源自：https://github.com/Erikfather/Decision_tree-python
1.数据集描述
共分为四个属性特征：年龄段，有工作，有自己的房子，信贷情况; 现根据这四种属性特征来决定是否给予贷款
为了方便，我对数据集进行如下处理：
在编写代码之前，我们先对数据集进行属性标注。
（0）年龄：0代表青年，1代表中年，2代表老年；
（1）有工作：0代表否，1代表是；
（2）有自己的房子：0代表否，1代表是；
（3）信贷情况：0代表一般，1代表好，2代表非常好；
（4）类别(是否给贷款)：no代表否，yes代表是。
存入txt文件中:
然后分别利用ID3，C4.5，CART三种算法对数据集进行决策树分类；
数据集的读取：
def read_dataset(filename):
"""
年龄段：0代表青年，1代表中年，2代表老年；
有工作：0代表否，1代表是；
有自己的房子：0代表否，1代表是；
信贷情况：0代表一般，1代表好，2代表非常好；
类别(是否给贷款)：0代表否，1代表是
"""
fr = open(filename,'r')
all_lines = fr.readlines() ## list形式,每行为1个str
#print(all_lines)
labels = ['年龄段','有工作','有自己的房子','信贷情况']
dataset = []
for line in all_lines[0:]:
line = line.strip().split(',') #以逗号为分割符拆分列表
dataset.append(line)
return dataset,labels
运行一下，看看有什么效果：
dataset,labels = read_dataset('./data/dataset.txt')
print(dataset,labels)
[['0', '0', '0', '0', '0'], ['0', '0', '0', '1', '0'], ['0', '1', '0', '1', '1'], ['0', '1', '1', '0', '1'], ['0', '0', '0', '0', '0'],
['1', '0', '0', '0', '0'], ['1', '0', '0', '1', '0'], ['1', '1', '1', '1', '1'], ['1', '0', '1', '2', '1'], ['1', '0', '1', '2', '1'],
['2', '0', '1', '2', '1'], ['2', '0', '1', '1', '1'], ['2', '1', '0', '1', '1'], ['2', '1', '0', '2', '1'], ['2', '0', '0', '0', '0'],
['2', '0', '0', '2', '0']] ['年龄段', '有工作', '有自己的房子', '信贷情况']
2. 计算信息熵
def inforEntropy(dataset):
m = len(dataset) #数据集的长度
labelCounts = {} #给所有可能分类创建字典
for featvec in dataset:
currentlabel = featvec[-1] #获取当前样本的label
if currentlabel not in labelCounts.keys():
labelCounts[currentlabel] = 0
labelCounts[currentlabel] += 1 # 统计每类标签的样本个数
Ent=0.0
for key in labelCounts:
p = float(labelCounts[key]) / m
Ent = Ent - p*log(p,2)
return Ent
3. ID3算法的实现
def ID3(dataset):
numFeatures = len(dataset[0])-1 #特征的个数
baseEnt = inforEntropy(dataset) #没划分之前的信息熵
bestInfoGain = 0.0 #信息增益先定义一下
bestFeature = -1 # 最优的特征先定义一下
for i in range(numFeatures): #遍历所有的特征
featList = [example[i] for example in dataset] #只取出每个样本的第i个特征 创建一个列表
uniqueVals = set(featList) #将特征列表创建成为set集合，元素不可重复。创建唯一的分类标签列表
newEnt = 0.0
for value in uniqueVals: #计算每种划分方式的信息熵
subdataset = splitdataset(dataset,i,value) #根据某一属性i取出样本集中这一属性值等于value的样本
p = len(subdataset) / float(len(dataset)) #计算|D(v)| / |D|
newEnt += p*inforEntropy(subdataset) #计算划分后的信息熵
inforGain = baseEnt - newEnt #计算信息增益
print(u"ID3中第%d个特征的信息增益为：%.3f"%(i,inforGain))
if inforGain > bestInfoGain:
bestInfoGain = inforGain
bestFeature = i
return bestFeature
3.1 利用ID3算法创建决策树
首先明白树停止生长的条件：
1. 当前节点包含的样本全属于同一类别，无需划分
2. 当前属性集为空，或者所有样本在所有属性上的取值相同，但所属的类别不同，无法划分
3. 当前节点包含的样本集为空，不能划分
def majorityCnt(classList):
classCont = {}
for vote in classList:
if vote not in classList.keys():
classCont[vote] = 0
classCont[vote] += 1 #每个类别统计一下个数
sortedClassCont = sorted(classCont.items(),key=operator.itemgetter(1),reverse=True) #此处要注意sorted的用法和其中的key参数
return sortedClassCont[0][0]
def ID3_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 = ID3(dataset) #选择最好的属性
bestFeatLabel = labels[bestFeat]
print(u"此时最优索引为："+(bestFeatLabel))
ID3Tree = {bestFeatLabel:{}}
del(labels[bestFeat]) #既然选出了最佳属性，那就把它删了吧，以后不再用这个属性了
featValues = [example[bestFeat] for example in dataset] #统计一下在此最佳划分属性下所有样本的取值，构成一个列表
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] #递归一下，找出当前最优属性下的生长的树，用字典存储。
ID3Tree[bestFeatLabel][value] = ID3_createTree(splitdataset(dataset,bestFeat,value),subLabels)
return ID3Tree
4 .创建完决策树后进行分类
def classify(inputTree,featLables,testdataset):
"""
输入：决策树，分类标签，测试数据
输出：决策结果
描述：跑决策树
"""
firstStr = list(inputTree.keys())[0]
secondDict = inputTree[firstStr]
featIndex = featLables.index(firstStr)
classlabel = '0'
for key in secondDict.keys():
if testdataset[featIndex] == key:
if type(secondDict[key]).__name__=='dict':
classlabel = classify(secondDict[key],featLables,testdataset)
else:
classlabel = secondDict[key]
return classlabel
def classifytest(inputTree, featLabels, testDataSet):
"""
输入：决策树，分类标签，测试数据集
输出：决策结果
描述：跑决策树
"""
classLabelAll = []
for testVec in testDataSet:
classLabelAll.append(classify(inputTree, featLabels, testVec))
return classLabelAll
5.主程序：
if __name__ == "__main__":
filename='./data/dataset.txt'
testfile='./data/testset.txt'
dataset, labels = read_dataset(filename)
#dataset,features=createDataSet()
print ('dataset',dataset)
print("---------------------------------------------")
print(u"数据集长度",len(dataset))
print ("Ent(D):",inforEntropy(dataset))
print("---------------------------------------------")
print(u"以下为首次寻找最优索引:
")
print(u"ID3算法的最优特征索引为:"+str(ID3(dataset)))
print ("--------------------------------------------------")
print(u"首次寻找最优索引结束！")
print("---------------------------------------------")
print(u"下面开始创建相应的决策树-------")
while(True):
dec_tree=str(input("请选择决策树:->(1:ID3; 2:C4.5; 3:CART)|('enter q to quit!')|："))
#ID3决策树
if dec_tree=='1':
labels_tmp = labels[:] # 拷贝，createTree会改变labels
ID3desicionTree = ID3_createTree(dataset,labels_tmp)
print('ID3desicionTree:
', ID3desicionTree)
#treePlotter.createPlot(ID3desicionTree)
treePlotter.ID3_Tree(ID3desicionTree)
testSet = read_testset(testfile)
print("下面为测试数据集结果：")
print('ID3_TestSet_classifyResult:
', classifytest(ID3desicionTree, labels, testSet))
print("---------------------------------------------")
if dec_tree=='q':
break
6. 运行结果
