机器学习(2)--决策树

决策树

决策树是根据数据属性采用树状结构建立的一种决策模型,可以解决分类/回归问题。树的内部节点为属性,叶节点为类别结果

基本算法流程: 训练集D{x,y}, 属性集A{a}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeGenerater(D,A): 
建立新节点node
if D中的样本属于同一个类别:
不需要划分,将类别赋值给node,作为叶节点
return
if A为空 or D的属性值都一样:
没办法划分,选择样本比较多的类别作为叶节点结果
return
选出最优划分的属性a
for i in a.value():
node建立分支,按照属性值给样本D分类划分
if Di是空的:
分支为叶节点,样本多的类别作为结果
else:
TreeGenerater(Di,A/a)


重要的:如何找到最佳属性

ID3决策树算法使用的信息增益Gain(D,a)

C4.5决策树算法使用的增益率Gain_ratio(D,a)

CART决策树算法使用的基尼指数Gini(D)