1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| from numpy import *
import math
import copy
import cPickle as pickle
class ID3DTree(object):
def __init__(self): #构造方法
self.tree={} #生成的树
self.dataSet=[] #数据集
self.lables=[] #标签集
#数据导入函数
def loadDataSet(self,path,lables):
recordlist=[]
fp=open(path,"rb") #读取文件内容
content=fp.read()
fp.close()
rowlist=content.splitlines() #按行转换为一维表
recordlist=[row.split("\t") for row in rowlist if row.strip()]
self.dataSet=recordlist
self.lables=lables
#执行决策函数
def train(self):
lables=copy.deepcopy(self.lables)
self.tree=self.buildTree(self.dataSet,lables)
#构建决策树，创建决策树主程序
def buildTree(self,dataSet,lables):
cateList=[data[-1] for data in dataSet] #抽取源数据集中的决策标签列
#程序终止条件1：如果classList只有一种决策标签，停止划分，返回这个决策标签
if cateList.count(cateList[0])==len(cateList):
return cateList[0]
#程序终止条件2：如果数据集的第一个决策标签只有一个，返回这个标签
if len(dataSet[0])==1:
return self.maxCate(cateList)
#核心部分
bestFeat=self.getBestFeat(dataSet) #返回数据集的最优特征轴
bestFeatLabel=lables[bestFeat]
tree={bestFeatLabel:{}}
del(lables[bestFeat])
#抽取最优特征轴的列向量
uniqueVals=set([data[bestFeat] for data in dataSet]) #去重
for value in uniqueVals: #决策树递归生长
subLables=lables[:] #将删除后的特征类别集建立子类别集
#按最优特征列和值分隔数据集
splitDataset=self.splitDataset(dataSet,bestFeat,value)
subTree=self.buildTree(splitDataset,subLables) #构建子树
tree[bestFeatLabel][value]=subTree
return tree
#计算出现次数最多的类别标签
def maxCate(self,cateList):
items=dict([(cateList.count(i),i) for i in cateList])
return items[max(items.keys())]
#计算最优特征
def getBestFeat(self,dataSet):
#计算特征向量维，其中最后一列用于类别标签
numFeatures=len(dataSet[0])-1 #特征向量维数=行向量维数-1
baseEntropy=self.computeEntropy(dataSet) #基础熵
bestInfoGain=0.0 #初始化最优的信息增益
bestFeature=-1 #初始化最优的特征轴
#外循环：遍历数据集各列，计算最优特征轴
#i为数据集列索引：取值范围0~(numFeatures-1)
for i in xrange(numFeatures):
uniqueVals=set([data[i] for data in dataSet]) #去重
newEntropy=0.0
for value in uniqueVals:
subDataSet=self.splitDataSet(dataSet,i,value)
prob=len(subDataSet)/float(len(dataSet))
newEntropy+=prob*self.computeEntropy(subDataSet)
infoGain=baseEntropy-newEntropy
if(infoGain>bestInfoGain): #信息增益大于0
bestInfoGain=infoGain #用当前信息增益值替代之前的最优增益值
bestFeature=i #重置最优特征为当前列
return bestFeature
#计算信息熵
def computeEntropy(self,dataSet):
datalen=float(len(dataSet))
cateList=[data[-1] for data in dataSet]
#得到类别为key、出现次数value的字典
items=dict([(i,cateList.count(i)) for i in cateList])
infoEntropy=0.0
for key in items:
prob=float(items[key])/datalen
infoEntropy-=prob*math.log(prob,2)
return infoEntropy
#划分数据集；分隔数据集；删除特征轴所在的数据列，返回剩余的数据集
#dataSet:数据集；axis:特征轴；value:特征轴的取值
def splitDataSet(self,dataSet,axis,value):
rtnList=[]
for featVec in dataSet:
if featVec[axis]==value:
rFeatVec=featVec[:axis] #list操作：提取0~（axis-1）的元素
rFeatVec.extend(featVec[axis+1:])
rtnList.append(rFeatVec)
return rtnList
|