概述
决策树这个算法比较接地气，就算你根本不懂机器学习算法也可以很好的理解决策树，决策树之前的算法就已经解释过了。主要思想就算通过条件进行分类即可。决策树主要的优点就在于数据形式非常好理解。decision tree的算法可以读取数据集合，可以得到数据中所隐含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取一系列规则。优点很明显，计算复杂度不高，输出结果也很容易理解，就算是中间有缺失值也影响不大，特征不相关也可以处理。由于决策树是按照条件划分，如果划分的条件过多了，可能导致overfitting。 首先要做的就是要找到数据的决定性特征是什么，把它作为划分的依据。当划分完成，如果当前的叶子都是同一个类别，那么当前叶子的划分就完成了。
决策树一般的划分流程 收集数据 准备数据，不同的判别条件方法可能会导致有不同的结果 分析数据，归一化预处理等等 训练数据，最后树的结构 测试数据，做validation 使用算法解决问题，基本步骤和KNN的差不多一样。
信息增益
划分数据的原则的，划分完了，数据一定要更加有序。组织杂乱无章数据的一种方法就是使用信息熵，也就是信息论的度量方法，在划分了数据时候信息发生的变化称为信息增益，信息增益最高的特征就是最好的选择。
其中
为是该分类的概率，为了计算熵，我们需要计算所有类别所有可能包含是信息期望值：
def calculateShan(self, dataSet):
labelFraction = {}
if len(dataSet) == 0:
return 0
for data in dataSet:
label = data[-1]
if label not in labelFraction.keys():
labelFraction[label] = 1
else:
labelFraction[label] = 1
Ent = 0.0
alldata = len(dataSet)
for key in labelFraction:
prob = float(labelFraction[key]) / alldata
Ent -= prob * math.log(prob, 2)
return Ent找到最好的区分特征：
代码语言：javascript复制 def choosetheBestFeature(self, dataset):
feature_num = dataset.shape[1] - 1
bestEntDiff = 0.0
BestFeature = -1
Bestvalue = -1
baseEnt = self.calculateShan(dataset)
aSet = None
bSet = None
for i in range(feature_num):
for value in dataset[:, i]:
A, B = self.split_data(dataset, i, value)
proA = len(A) / len(dataset)
proB = 1 - proA
infoEnt = proA * self.calculateShan(A) proB * self.calculateShan(B)
if baseEnt - infoEnt > bestEntDiff:
bestEntDiff = baseEnt - infoEnt
BestFeature = i
Bestvalue = value
aSet = A
bSet = B
return BestFeature, Bestvalue, np.array(aSet), np.array(bSet)递归构建一颗树
代码语言：javascript复制 def __build_tree(self, dataSet):
if dataSet is None:
return None
elif len(dataSet) < 3:
label_class = {}
for data in dataSet:
label = data[-1]
if label not in label_class:
label_class[label] = 1
else:
label_class[label] = 1
sorted(label_class.items(), key=lambda label_class: label_class[1], reverse=True)
key = list(label_class)[0]
return nodes(result=key)
node = nodes()
nodes.result = None
feature, value, A, B = self.choosetheBestFeature(dataSet)
if value != -1 and feature != -1:
node.value = value
node.fea = feature
node.left = self.__build_tree(A)
node.right = self.__build_tree(B)
else:
label_class = {}
for data in dataSet:
label = data[-1]
if label not in label_class:
label_class[label] = 1
else:
label_class[label] = 1
sorted(label_class.items(), key=lambda label_class: label_class[1], reverse=True)
key = list(label_class)[0]
node.result = key
return node在构建算法中也发现了，构建一棵树是需要很长时间的，这里还好，是寻找存在的特征，如果是寻找一些连续型的特征，比如用gini系数，那么是要找到当前特征的最大最小值，然后按照步长加上去一个一个找，类似addboost一样，所以时间复杂度不低的。即使是处理很小的数据集，也是很耗时的任务。为了节省时间，可以用Python模块pickle序列化对象，序列化可以在磁盘上保存，需要就读出来，任何对象都可以序列化，字典也不例外。 开始处理数据的时候，先要测量数据的不一致性，然后用最优的方案划分数据集，直到数据集里面所有的数据都属于同一类。 这只是其中一种决策树，比较流行的还有C4.5和CART。
所有代码https://github.com/GreenArrow2017/MachineLeariningnAction/tree/master/DecisionTree
