决策树是一种描述对实例进行分类的树形结构。决策树由点和有向边组成。节点有两种类型：内部节点和叶节点。内部节点表示一种特征或者属性，叶节点表示一个分类。构建决策树时通常采用自上而下的方法，在每一步选择一个最好的属性来分裂。每次都找不同的切分点，将样本空间逐渐进行细分，最后把属于同一类的空间进行合并，就形成了决策边界，树的层次越深，决策边界的切分就越细，区分越准确，同时也越有可能产生过拟合。
决策树的建立开始，构建根节点，将所有训练数据放在根节点，选择一个最优特征，按照这一特征的取值将训练数据分割为子集，使各个子集有一个当前条件下最好的分类。如果这些子集能被基本正确分类，那么构造叶节点，将对应子集集中到叶节点。如果有子集不能被正确分类，那么就这些子集选择新的最优特征，继续对其进行分割，构建相应的节点。递归进行上述的操作，直到所有训练数据子集均能被正确分类。
信息熵(entropy) 熵是接收的每条消息中包含的信息的平均量，熵是对不确定性的测量。但是在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。简单来说，熵表示随机变量的不确定性。
条件熵(conditional entropy) 在一个条件下，随机变量的不确定性。
信息增益(information gain) 信息增益=熵－条件熵。表示在一个条件下，信息不确定性减少的程度。
信息增益率(information gain ratio) 节点信息增益与节点分裂信息度量的比值。

CART算法 CART中用于选择变量的不纯性度量是Gini指数； 如果目标变量是标称的，并且是具有两个以上的类别，则CART可能考虑将目标类别合并成两个超类别（双化）； 如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量。CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。

以C4.5决策树算法为例：
步骤一将西瓜数据集划分为训练集和测试集，并将数据集中的每个属性值转换为唯一标签

步骤二将数据集中的属性和属性值进行划分，核心代码如下所示：
def read_dataset(filename):
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

步骤三使用C4.5算法来构造决策树，核心代码如下所示：
defC45_createTree(dataset, labels, test_dataset):
classList = [example[-1] for examplein dataset]
if classList.count(classList[0]) ==len(classList):
# 类别完全相同，停止划分
return classList[0]
if len(dataset[0]) == 1:
# 遍历完所有特征时返回出现次数最多的
return majorityCnt(classList)
bestFeat = C45_chooseBestFeatureToSplit(dataset)
bestFeatLabel = labels[bestFeat]
print(u"此时最优索引为：" + (bestFeatLabel))
print(u"最优索引对应的子典为：", {bestFeatLabel:cds.ids2lables[bestFeatLabel]})
C45Tree = {bestFeatLabel: {}}
del (labels[bestFeat])
# 得到列表包括节点所有的属性值
featValues = [example[bestFeat] forexample in dataset]
uniqueVals = set(featValues)
if pre_pruning:
ans = []
for index inrange(len(test_dataset)):
ans.append(test_dataset[index][-1])
result_counter = Counter()
for vec in dataset:
result_counter[vec[-1]] += 1
leaf_output =result_counter.most_common(1)[0][0]
root_acc =cal_acc(test_output=[leaf_output] * len(test_dataset), label=ans)
outputs = []
ans = []
for value in uniqueVals:
cut_testset =splitdataset(test_dataset, bestFeat, value)
cut_dataset =splitdataset(dataset, bestFeat, value)
for vec in cut_testset:
ans.append(vec[-1])
result_counter = Counter()
for vec in cut_dataset:
result_counter[vec[-1]]+= 1
leaf_output =result_counter.most_common(1)[0][0]
outputs += [leaf_output] *len(cut_testset)
cut_acc = cal_acc(test_output=outputs,label=ans)
if cut_acc <= root_acc:
return leaf_output
for value in uniqueVals:
subLabels = labels[:]
C45Tree[bestFeatLabel][value] =C45_createTree(
splitdataset(dataset, bestFeat,value),
subLabels,
splitdataset(test_dataset,bestFeat, value))
if post_pruning:
tree_output =classifytest(C45Tree,
featLabels=['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖率'],
testDataSet=test_dataset)
ans = []
for vec in test_dataset:
ans.append(vec[-1])
root_acc = cal_acc(tree_output,ans)
result_counter = Counter()
for vec in dataset:
result_counter[vec[-1]] += 1
leaf_output =result_counter.most_common(1)[0][0]
cut_acc = cal_acc([leaf_output] *len(test_dataset), ans)
if cut_acc >= root_acc:
return leaf_output
return C45Tree
defC45_chooseBestFeatureToSplit(dataset):
numFeatures = len(dataset[0]) - 1
baseEnt = cal_entropy(dataset)
bestInfoGain_ratio = 0.0
bestFeature = -1
for i in range(numFeatures): # 遍历所有特征
featList = [example[i] forexample in dataset]
uniqueVals = set(featList) # 将特征列表创建成为set集合，元素不可重复。创建唯一的分类标签列表
newEnt = 0.0
IV = 0.0
for value in uniqueVals: # 计算每种划分方式的信息熵
subdataset =splitdataset(dataset, i, value)
p = len(subdataset) /float(len(dataset))
newEnt += p *cal_entropy(subdataset)
IV = IV - p * log(p, 2)
infoGain = baseEnt - newEnt
if (IV == 0): # fix the overflow bug
continue
infoGain_ratio = infoGain /IV # 这个feature的infoGain_ratio
print(u"C4.5中第%d个特征的信息增益率为：%.3f" % (i,infoGain_ratio))
if (infoGain_ratio >bestInfoGain_ratio): # 选择最大的gain ratio
bestInfoGain_ratio =infoGain_ratio
bestFeature = i # 选择最大的gain ratio对应的feature
return bestFeature

不剪枝？不剪枝？