背景介绍：根据患者眼部状况的观察条件，利用决策树来向患者推荐隐形眼镜的类型。
1. 收集数据
数据集来自于UCI数据库的隐形眼镜数据集。
2. 准备数据
解析tab键分割的数据行。
def read2DataSet(filename):
fr= open(filename,'r')
dataSet= [example.strip().split('\t') for example in fr.readlines()]
lenseLabels= ['age','prescript','astigmatric','tearRate']#特征名称
return dataSet, lenseLabels
3. 分析数据
快速检查数据，确保正确地解析数据内容，绘制最后的决策树型图。
4. 训练算法-生成决策树
思想（伪代码）：
检测数据集中的每个子项是否属于同一分类：
If so return 类标签
Else
寻找划分数据集的最好特征（--基于信息增益）
划分数据集
创建分支结点
for 每个划分的子集
调用自己，并增加返回结果到分支结点中
return 分支结点
4.1 划分数据
def splitDataSet(dataSet, axis, value):
"""
对数据集进行划分
:param dataSet:数据集
:param axis: 选择的特征，在该特征上对数据集进行划分;
:param value: 特征的取值；划分依据（这种划分是多分支划分，依赖于每个标称属性的取值个数）
:return: 划分后的子集（删除特征axis后的数据集）；；方便进行下一次划分；；递归执行"""
retDataSet= []
for featVecin dataSet:
if featVec[axis] == value:
reducedFeatVec= featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
4.2 选取最佳的划分方式
标准是 信息增益（Information Gain）：
香农熵：
香农熵计算实现：
def calcShannonEnt(dataSet):
numEntries= len(dataSet)
labelCounts= {}
for featVecin dataSet:
currentLabel= featVec[-1]
labelCounts[currentLabel] = labelCounts.get(currentLabel,0) + 1
shannonEnt= 0.0
for key in labelCounts:
prob= labelCounts[key]/float(numEntries)
shannonEnt-= prob*log(prob,2)
return shannonEnt
以信息增益为评价指标，选出最佳的划分方式（穷举）：
def chooseBestFeatureToSplit(dataSet):
numFeatures= len(dataSet[0]) - 1#dataSet 数据格式：每一行最后为类标签
baseEntropy= calcShannonEnt(dataSet)
bestInfoGain= 0.0; bestFeature= -1
for i in range(numFeatures):
featList= [example[i] for examplein 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 > bestInfoGain):#选信息增益最大的特征
bestInfoGain= infoGain
bestFeature= i
return bestFeature
4.3 生成决策树
决策树的生成过程是一个递归的过程。那么，必须有终止条件，才能结束运行。
终止条件：
（1）结点中所有实例都是一个类别；
（2）结点中没有可供选择的特征（即，属性已经遍历完）；此时，依据多数表决原则，返回该节点的分类标签。
针对情况二，多数表决函数：
def majorityCnt(classList):
classCnt= {}
for vote in classList:
classCnt[vote] = classCnt.get(vote,0) + 1
sortedClassCount= sorted(classCnt.items(),key=lambda a:a[1],reverse=True)
return sortedClassCount[0][0]
千呼万唤始出来，重头戏---生成决策树：
def createTree(dataSet, labels):
classList= [example[-1] for examplein dataSet]
if classList.count(classList[0]) == len(classList):#结束条件1：结点中所有实例都是一个类别；
return classList[0]
if len(dataSet[0]) == 1:#结束条件2：结点中没有特征，只剩下类别标签---多数表决
return majorityCnt(classList)
bestFeat= chooseBestFeatureToSplit(dataSet)
bestFeatLabel= labels[bestFeat]#特征的名称，eg：工资、性别等等----中间结点，进行判断
myTree= {bestFeatLabel:{}}#对子节点进行划分
del labels[bestFeat]#针对选定的特征--取不同的值，进行划分
featValues= [example[bestFeat] for example in dataSet]
uniqueValues= set(featValues)
for value in uniqueValues:
subLabels= labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
return myTree
生成的决策树，结果如下：
为了更加形象直观，使用matplotlib工具画图。决策树的形状如下：
5. 测试算法
编写测试函数可以验证决策树可以正确分类给定的数据实例。
6. 使用算法
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 is instance(secondDict[key],dict):
classLabel= classify(secondDict[key],featLabels,testVec)
else:
classLabel= secondDict[key]
return classLabel
比如：一个测试用例：pre + myope + no + normal = soft
输出结果为：
7. 后续
为了方便下次使用，而不必重新生成决策树，我们使用pickle来进行保存。
def storeTree(inputTree, filename):
import pickle
fw= open(filename,'w')
pickle.dump(inputTree,fw)
fw.close()
下次读取时，使用：
def grabTree(filename):
import pickle
fr= open(filename)
return pickle.load(fr)
其中：
pickle：
The pickle module implements a fundamental, but powerful algorithm for serializing and de-serializing a Python object structure. 该模块实现对python 数据对象的序列化和反序列化（保存和读取）。
pickle.dump(obj, file[, protocol])
Write a pickled representation of obj to the open file object file. 将python数据对象写到文件中；即保存。
pickle.load(file)
Read a string from the open file object file and interpret it as a pickle data stream, reconstructing and returning the original object hierarchy.从文件中读取信息，反序列化形成原来的数据对象，并返回。
8. 小结
决策树
优点：计算复杂度不高。输出结果易于理解，对中间值缺失不敏感；能方便理解数据中所蕴含的知识信息。
缺点：可能会过度匹配（overfitting）--剪枝；提前停止
适用数据类型：数值型和标称型。
