机器学习之决策树（一）

演示一个简单的决策树：

关键词：

classification 分类

training set 训练集

decision tree 决策树

predicton tree 预测树

input variable 输入变量

test point 测试点

branch 分支

categorical 分类的

continuous 连续的

leaf node 叶子节点

probability score 概率得分

internal node 内部节点

root 根节点

split 分裂

LHS 左手边

RHS 右手边

pruning 剪枝

流行的决策树算法：

ID3：Iterative Dichotomiser(迭代二分) 最早的决策树算法之一

C4.5：改良ID3，支持分类属性和连续属性，连续变量的值会进行排序和分区

CART：Classification And Regression Tree

两类决策树：

分类树 classification tree:

应用于分类的输出变量，通常是二元，比如：是或否，购买或不购买

回归树 regression tree：

应用到数值输出变量或连续输出变量，比如：消费品的预测价格和消费的概率可能性

应用案例：

动物分类

输出：冷血、温血、是哺乳、非哺乳

医生评估病人

输入：症状检测列表

视频游戏的人工智能引擎

输出：控制游戏角色的自主行为

零售商

输出：划分客户、预测市场对促销活动的反应率

response rate

金融机构

输入：批准贷款申请、拒绝贷款申请

属性能够提供信息的程度使用以下概念来度量：

熵 entropy

信息增益 information gain

节点属性的purity纯净度，如果结果分类有两种可能（是，否），那么节点属性有两个纯净度，对于‘是’的纯净度，和对于‘后’的纯净度，一般偏向于注重其主要方面，也就是较大的值

熵：衡量信息的混乱程度，约混乱约接近1，约清晰约易琢磨则越接近0

基础熵：

输出变量的熵

H-subscribed = 0.482

综合衡量(yes,no)的概率

表征：结果类的混乱程度

(属性A的)条件熵：

输入属性的熵

H-subscribedcontact = 0.466

表征：有了一个属性的参照后，再看结果类的混乱程度，应该会起到一定的拨云见雾的作用，用来衡量该属性对判断结果的帮助作用

(属性A的)信息增益：

输入属性的信息增益

基础熵与条件熵的差值

InfoGain-contact = (H-subscribed) - (H-subscribedcontact)

信息增益最大的属性被认为是最能提供信息的属性，信息增益表明一个属性的纯净度。每次取信息增益最大的属性作为分裂点。

(属性A的某个分裂点的)信息增益

分裂点的显著性

K值越大，表示在该分裂点上进行分裂是显著的

构建决策树的过程：

1，选择信息增益最大的属性A进行第一次分裂

2，属性A具有的可能是离散值或者可能是连续值，对于离散值，进行所有可能的组合对进行二分的分裂，对于连续值也进行所有可能的二分的分裂

3，对于属性A，计算所有可能的分裂点的信息增益，信息增益K值

3，第一次分裂后，把训练集分为两部分，然后再分别对两个子训练集进行分裂

4，直到分裂节点足够纯净（使用信息增益表征），或属性分裂没有产生足够的信息增益

示例：

Contact：cellular,telephone,unknown

对于属性Contact有3种分裂方式：

(cellular),(telephone,unknown)

(telephone),(cellular,known)

(unknown),(cellular,telephone)