心跳

决 策 树
引言
决策树对比神经元网络的优点在于可以生成一些规则。

当我们进行一些决策，同时需要相应的理由的时候，使用神经元网络就不行了。

本章介绍三个算法 CART,CHAID,C4.5。

决策树是如何工作的
决策树一般都是自上而下的来生成的。

选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。

从根到叶子节点都有一条路径，这条路径就是一条“规则”。

决策树可以是二叉的，也可以是多叉的。

对每个节点的衡量：

1)     通过该节点的记录数

2)     如果是叶子节点的话，分类的路径

3)     对叶子节点正确分类的比例。

有些规则的效果可以比其他的一些规则要好。

决策树对于常规统计方法的优点。

CART
Diversity(整体)-diversity(左节点)-diversity(右节点)，值越大，分割就越好。

三种diversity的指标：

1.       min(P(c1),P(c2))

2.       2P(c1)P(c2)

3.       [P(c1)logP(c1)]+[P(c2)logP(c2)]

这几个参数有相同的性质：当其中的类是均匀分布的时候，值最大；当有一个类的个数为0的时候，值为0。

选择分割的时候，对每个字段都考虑；对每个字段中的值先排序，然后再一一计算。最后选出最佳的分割。

树的生成：

错误率的衡量：最初生成的树中也是有错误率的！因为有些叶子节点并不是“Pure”的。

树的修剪：是不是当所以的叶子都很纯是，这棵树就能工作的很好呢?

修剪的要点是：应该回溯多少、如何从众多的子树总寻找最佳的。

1)       鉴别生成候选子树     ：使用一个调整的错误率。AE(T)=E(T)+aleaf_count(T)。一步步的生成一些候选子树。

2)       对子树的评估：通过test set找到最佳子树

3)       对最佳子树进行评估：使用evaluation set。

4)       考虑代价(cost)的问题。

C4.5
C4.5是从ID3演变而来的。

C4.5和CART的区别:

1)   树的生成方面。

C4.5不一定使用两分法。C4.5处理种类变量的时候，缺省的情况是每个值作为一个分支。

Gain 和gain ratio。

2)     树的修剪

C4.5使用原来的数据进行测试。(学院派)

规则的生成

CHAID
1975年

和CART和C4.5的区别：

1.       在overfitting之前就停止树的生长。

2.       必须都是种类变量。数值变量必须分成范围。

树的生长

1.       选择分割。X2检验



实际中使用决策树的一些问题
主要是一些数据准备和数据表示方面的问题。

案例：银行信用卡部门

1.       对数据细节的不熟悉。

2.       数据翻译问题。COBOL

3.       对时间元素的处理：OCCURS语句的处理。可以根据需要来增加一些字段：delta_balance，delta_interest_rate等等。

4.       CART算法不考虑字段之间的关系。

5.       定义类别。使用的工具在类别字段只可以有两个值。我们对原始数据进行一些映射处理。“silent attrition”。

6.       数据表示的问题。需要额外的数据。

7.       消除杂音。

8.       欺骗性的字段。有些字段其实和要预测的字段并不是独立的。可以通过决策树来进行这些字段的判断。

9.       过于总结性的数据。

10.     经验和教训。

将决策树运用于事件序列：
PV Future View，一个工具。

Case,某一时刻的快照。

Attribute,组成Case的字段

Feature,布尔变量，用于形成决策树的内部节点。

Interpretations，由Attribute组成用于体现领域知识和关系的衍生字段。Interpretations字段常常是由用户提供的。

从历史推出未来：

案例学习：咖啡烘烤的流程控制

其他的决策树的变种

1)     一次使用超过一个字段用于分类

2)     使用倾斜的超平面切分

3)     神经元树

决策树的优缺点：
优点：

1)     可以生成可以理解的规则。

2)     计算量相对来说不是很大。

3)     可以处理连续和种类字段。

4)     决策树可以清晰的显示哪些字段比较重要

缺点：

1)     对连续性的字段比较难预测。

2)     对有时间顺序的数据，需要很多预处理的工作。

3)     当类别太多时，错误可能就会增加的比较快。

4)     一般的算法分类的时候，只是根据一个字段来分类。


SLIQ ：一种 快 速 的 分 类 器

分类器的定义：输入的数据含有千万个记录，每个记录又有很多个属性，其中有一个特别的属性叫做类（例如信用程度的高，中，低）。分类器的目的就是分析输入的数据，并建立一个模型，并用这个模型对未来的数据进行分类，应用于信用确认，医疗诊断等。

运用在决策树上的分类器��SLIQ。

一：树的建立。


预分类：为训练集中的每个属性建立一个属性表，每个属性表包含属性值和索引，每个索引对应一个记录，而特殊的属性��类中还包含枝节点。


节点的分割过程：a,选取哪个属性来分割。b,对于选取的属性，确定分割标准。在SLIQ里采用的是gini分割系数的方法。具体到每个node的分割又包括矩形类图的的更新和类表的更新。


以上介绍的是连续值的属性的分割方法，对于分类属性的值（例如地区属性）：S代表A所有可能的值的集合（有2的n次方个），S’是S的子集。如果n小于某个门限时，就对每个S’都估算一遍，否则就采用一种叫做greedy algorithrm的方法。

二：树的修剪。SLIQ采用了MDL（最小叙述长度）的方法来修剪树。

COST(M,D)=COST(D|M)+COST(M);

COST(D|M)是指对于Data的编码的“费用”，定义为分类器错误个数的总和。

COST(M)包含两部分：

a,树的编码的“费用”，有code1，code2和code3三种。　

b,分割方法的编码的“费用”。有连续值属性的（每一个判断定为L(test)=1）和分类属性（L(test)=lnAi,其中树中所有采用类属性分割的方法的总和）的两种。

上述公式又可分成四种情况：

如果该节点是一个叶子， Cleaf(t)= L(t)+Errorst;

如果该节点有两个孩子， Cboth(t)=L(t)+Ltest+C(t1)+C(t2);

如果该节点只有左边有一个孩子， Cleft(t)=L(t)+Ltest+C(t1)+C’(t2);

如果该节点只有右边有一个孩子， Cright(t)=L(t)+Ltest+C’(t1)+C(t2);

这里C’（ti）指的是：被修剪了的那个枝里的记录用母节点里的统计方法来编码所用的“费 用”。

根据上面的叙述，可以采用三种策略来进行修剪。


Full:采用这种方法，只是考虑第一和第二种情况，也就是如果Cleaf计算下来比Cboth小的话就将这个节点变为一片叶子。这样树的编码“费用”里就只用了一个比特。


Partial:这种方法将四种情况都考虑了进去，比较四种计算“费用”的大小，选择“费用”最小的那种作为修剪的方法。

3, Hybrid（混合的）:这种方法包含两个过程，第一步先用Full的策略来得到一个比较小的 树，然后再考虑后三种的计算方法来修剪树。

三：综述：SLIQ采用了Pre-sorting,breadth-first和MDL的方法来建立和修剪决策树，它能够对大量的数据进行处理，突破了传统分类器的只能处理700KB数据的瓶颈。


贝叶斯用于分类的方法


为阐述单个变量的分布函数的求法，首先讲一个掷图钉的例子：设掷为头的可能性是t,那么t的可能性概率分布函数P(t|ξ)。那么下一次掷为头的概率是P(x=heads|ξ)=∫p(x=heads|t,ξ)p(t|ξ)dt=∫t*p(t|ξ)dt=E(t|ξ)。而且，进一步地如果掷为头后的t的分布概率就为p(t| x=heads,ξ)=c* p(x=heads|t,ξ)* p(t|ξ)=c*t* p(t|ξ).这样的话p(t|m heads ,n tails ,ξ)=c*t(m)*(1-t)(n)* p(t|ξ) [其中t(m)表示t的m次方]，也就求得m次掷为“头”，n次掷为尾后的t的概率分布情况。上面的是对于两个结果的情况的分析，那么对于离散的多种结果的情况，我们可以用同样的方法进行分析。下面讲怎么样用贝叶斯方法来进行分类。

定义：如果K为属性的个数，D定义为含有K个值的向量。表示为D=(x1=v1,x2=v2,….xk=vk),其中x为属性，v为属性值。一个Concept定义为相似记录的集合，Concept C定义为K个可能的属性值的分布函数的向量。表示为C=(f1,f2,…fk)。这里fk是一个分布函数，它由在这个Concept里第k个属性的所有属性值决定。例如，vk1,vk2,….vkN是N个记录D1,D2…DN的第k个属性值,那么fk可能的分布函数是fk(xk|D1…DN)=Mk*exp{-(xk-ak)*(xk-ak)/2бk*бk}.

定义H=(C1,C2…,CJ)为所有各种分类集合的集合。对于新的一个记录D,如果Cj为那个接受D的那一类，Hj为接受了以后变化了的H,那么衡量Cj接受D的好坏就由P(Hj|DH)=P(Hj|H)P(D|HjH)/P(D|H)来决定，它的最大值也就对应哪个最适合的Cj。假定P(Hj|H)对于每一个j都是相等的，那么我们只需要比较P(D|HjH)。而P(D|HjH) =P(Cj|HjH)*

P(D|CjHjH)=|Cj|/|C|*P(D|Cj),P(D|Cj)表示D属于Cj的程度。这里|C|表示C中记录的个数。，P(D|C)=П P(vk|fk) 对于连续变量，P(vk|fk)=fk(vk)?xk,这儿?xk是vk周围很小的一个常量范围。对于离散变量，P(vk|fk)=C中第k个属性值是vk的个数/C中记录的个数。