(1) 收集数据：可以使用任何方法。
(2) 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。(离散跟随记)
(3) 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
(4) 训练算法：构造树的数据结构。
(5) 测试算法：使用经验树计算错误率。
(6) 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据
的内在含义。
构造数据
def create_dataset():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing', 'flippers']#这两个代表是特征名称的集合，也就是特征1，特征2
return dataSet, labels
计算信息期望
def calc_shannon_ent(dataSet):
num_entries = len(dataSet)
label_counts = {}
# 为所有可能分类创建字典
for featVec in dataSet:#统计是鱼的次数，统计不是鱼的次数
current_label = featVec[-1]#拿到分类的值，是否鱼类
if current_label not in label_counts.keys():
label_counts[current_label] = 0
label_counts[current_label] += 1
shannoent = 0.0#信息期望值
# 以二为底求对数
for key in label_counts:
prob = float(label_counts[key])/num_entries
shannoent -= prob * math.log(prob, 2)#所有可能性的信息增益就是得到信息期望值
return shannoent
切割数据急的函数
def split_dataset(dataSet, axis, value):#选择当前特征属性分类的情况，不懂的可以debug看一下
# 创建新的list对象
retdataSet = []
for featVec in dataSet:
if featVec[axis] == value:#如果第一行的三维数组第一个特征等于1的话
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retdataSet.append(reducedFeatVec)
return retdataSet
依次计算特征1跟特征2的信息增益，得出信息增益最大的特征
def choose_best(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calc_shannon_ent(dataSet)#最开始的信息期望值
bestInfoGain = 0.0#最佳信息增益
bestFeature = -1#最佳特征
# 创建唯一分类标签
for i in range(numFeatures):
featList = [example[i] for example in dataSet]#每个特征属性组成的列表
uniqueValis = set(featList)#看特征1区分成几种
newEntropy = 0.0#最初的信息期望值
# 计划每种划分的信息墒
for value in uniqueValis:
subDataSet = split_dataset(dataSet, i ,value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calc_shannon_ent(subDataSet)
infoGain = baseEntropy - newEntropy
# 计算最好的增益墒
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.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount
def create_tree(dataSet, labels):
classList = [example[-1] for example in dataSet]#[yes,yes,no,no,no]
if classList.count(classList[0]) == len(classList):#如果所有的数据只有一种类别，就直接停止分类了
# 停止分类直至所有类别相等
return classList[0]
if len(dataSet[0]) == 1:#代表此时数据里只剩下最后一列，也就是我们的类别列，没有特征给我们继续往下分了，所以就采取投票法
# 停止分割直至没有更多特征
return majoritycnt(classList)
bestfaet = choose_best(dataSet)#首先通过计算得根结点特征
bestfaetlabel = labels[bestfaet]#拿到根结点的特征名称
mytree = {bestfaetlabel:{}}
del(labels[bestfaet])
print(labels)
# 得到包含所有属性的列表
featvalues = [example[bestfaet] for example in dataSet]#拿到特征1的所有取值情况[1,1,1,0,0]
uniquevalues = set(featvalues)#发现no surfacing特征只有两种选择，1,0
for value in uniquevalues:#遍历这两种特征，其实也就是把这两种特征切割成两个子树出来，俗称递归
sublables = labels[:]#剩下的就去切分第二个特征了
mytree[bestfaetlabel][value] = create_tree(split_dataset(dataSet, bestfaet, value), sublables)
return mytree
决策树的分类
def classify(inputtree, featlabels, testvec):#参数分别代表决策树，特征名称，特征向量[mytree,labels,[1,0]]
firststr = list(inputtree.keys())[0]
print(firststr)
seconddict = inputtree[firststr]#看它下面还有没有字典可以分
print(seconddict)
featindex = featlabels.index(firststr)
key = testvec[featindex]
valueoffeat = seconddict[key]
if isinstance(valueoffeat, dict):#isinstance() 函数来判断一个对象是否是一个已知的类型，类似 type()。
classlabel = classify(valueoffeat, featlabels, testvec)
else:
classlabel = valueoffeat
return classlabel
决策树模型的加载跟存储
def store_tree(inputtree, filename):#把模型存储起来
fw = open(filename, 'w')
pickle.dump(inputtree, fw)
fw.close()
def grab_tree(filename):#加载模型
import pickle
fr = open(filename)
return pickle.load(fr)
