- 1. 数据挖掘在高维数据中的应用 ——决策树
- 2. 决策树决策树的一个突出特点是其再现了人类做决策的过程。我们先看一个例子。
这是关于鸢尾花的品种辨别的数据。总共150个案例（样品），4个变量：花萼长，花萼宽，花瓣长，花瓣宽，都是连续性变量。花的品种有三种： SETOSA ，VERSICOL，VIRGINIC。
- 3. 根据这4个自变量，我们建立了下面的一个决策树
- 4. 决策树的构造方法最先源自所谓Hunt方法(Hunt 1966)，
后来的一些方法，比如ID3、C4.5和CART等都是基于
Hunt方法而构造的。以分类为例，一开始的数据可能包
含有若干类，Hunt方法的要点是（假定在某一个节点）
如果数据已经只有一类了，则该节点为叶节点。否则进行下一步。
寻找一个变量使得依照该变量的某个条件把数据分成纯度较大的两个或几个数据子集。而用其它变量所划分的子集不如该变量划分得那样纯。也就是说，根据某种局部最优性来选择变量。然后对于其子节点回到步骤1。
- 5. 第T个节点的不纯度的度量熵(entropy)：
Gini指数(Gini index)：
误分率(misclassification rate或classification error)：
- 6. 熵以两分类问题为例
如果有个节点中1类和0类样品比例分别为0.5，0.5
那么该节点的
如果有个节点中1类和0类样品比例分别为0.67，0.33
可见，节点的样品越杂，熵越大，节点越纯，熵越小
- 7. 信息增益如果以属性A来对节点T进行分割，分割后生成的新的节点的熵为：
分割之前节点T的熵为：
那么，以属性A来对节点T进行分割的信息增益为：
可见，信息增益越大，说明以属性A作为分割带来
越纯的节点
- 8. ID3算法（函数的参数为在当前节点的数据集、变量集和变量等）function ID3 (R :尚未用过的变量集, T :在该节点训练数据集)
If T 为空集, 返回失败信息;
If T包含所有同样的分类变量的值，返回一个具有该值的单独节点;
If R为空，那么返回一个具有最大频率的当前变量的值;
Let 具有最大Gain(D,T)的变量;
Let {dj| j=1,2, .., m} 为D的值;
Let {Sj| j=1,2, .., m} 相应于D的值的T的子集;
Return 以D为标签的节点及标为d1, d2,...,dm的树枝;
#这时ID3的函数和参数为ID3(R-{D}, T1), ID3(R-{D}, T2),..., ID3(R-{D}, Tm);
end ID3;它只能处理定性变量，而且一个变量用过之后就不再使用了。
- 9. C4.5算法为ID3的延伸，它可以处理缺失值、连续变量及剪枝等。为了弥补信息增益的一些缺点，比如当 时，增益为最大，这就会产生小而纯的子集，例如企业代码、日期等等，Quinlan(1993)为C4.5提出了信息增益比(gain ratio)的概念。
- 10. 信息增益比(gain ratio)分离信息定义为
信息增益比为
可见， 接近于1，则分离信息接近于0，信息
增益比将比较大；而 比较均匀，则分离信息
越大，信息增益也越小。
- 11. CART(Classification and Regression Trees)算法CART算法包含了分类树和回归树，是由Breiman et al.(1984)提出的。CART的方法是AID和THAID算法的发展和提高，而且克服了经典统计中判别分析、核密度估计、K最近邻方法、Logistic回归等方法中的一些固有问题。
- 12. Breiman et al.(1984)以及Steinberg & Colla (1995)提供了使用CART的一些理由，部分理由如下(其中一些是前面提到的其它基于树的模型所共有的)：
CART对于自变量和因变量不做任何形式的分布假定。
CART中的自变量可以是分类变量和连续变量的混合。
CART具有对付一个观测中具有缺失值的功能，但用变量的线性组合来分割节点时除外。
CART不受离群点、共线性、异方差性或者（如在经典回归中的）误差结构的影响。在一个节点处的离群点是孤立的，不会影响分割。
- 13. CART能够探测和揭示数据中的交互作用。
CART的结果不受自变量的单调变换的影响。
在一些背景知识不清楚的研究中，CART能够作为探索和分析的工具，其结果能够揭示关于问题背景结构的许多重要线索。
CART的主要优点在于它有效地处理大数据集和高维问题，也就是说，它能够利用大量变量中的最重要的部分变量来得到有用的结论。
CART分析所产生的树的结构很容易被任何领域的人所理解。.
- 14. CART的构建过程在根节点，数据是不纯的，所有的变量都是候选变量。我们进行下面的步骤来构造一棵分类树：
对于每一个变量，都对其所有可能产生的分割计算
这样，对每个变量都选出一个最优的分割点，对于连续变量X，要找出d，而由是否“ ”来确定分割，而对离散变量，要找出w，使得由是否“ ”来确定分割。
- 15. 对所有变量，比较它们在其最优分割点的 ，选择相应于最大 的变量作为根节点的分割变量，并由此产生两个子节点。再对这两个子节点根据使误分损失最小的原则确定节点的类型。
对每个非叶节点，重复上面1－2步。最终CART构造一个有很多叶节点的大树，它的每个叶节点或者纯粹的只有一类，或者只有很少的几个观测值。
- 16. 大的树有两个问题。首先，虽然大的树对于训练集精确度很高，误分率也很低，甚至为零，但是对于新的数据集会产生很糟糕的结果。其次，理解和解释一个大的树是一个复杂的过程。一个大的树也称为复杂树(complex tree)。树的复杂性由其叶节点的个数来度量。我们必需要在精确性和复杂性中找到平衡。它们之间的关系由复杂性损失(cost complexity)来度量，它等于代回误分损失(resubstitution misclassification cost)加上叶节点数目乘以惩罚常数b：
复杂性损失＝代回误分损失＋b×叶节点数目
- 17. (本页无文本内容)
- 18. CHAID(chi-square automatic interaction detector)算法CHAID是一个研究因变量和大量自变量之间关系的探索性数据方法。最初的CHAID方法是Kass (1980)为名义因变量而引入的。后来它又被Magidson (1993)推广到有序变量的情况。自变量可以是定性变量，诸如名义变量或有序变量，也可以是定量变量，因变量也是一样，可以是各种变量。
- 19. 步骤对于定性变量，其各个水平也称为（最初始的）范畴(category)，由各个水平事先分组，形成一些范畴
通过统计检验：卡方检验或是F检验来确定分割变量，合并范畴，得到新的子节点
对新的子节点实施重复1,2步，直到最后得到两个范畴 CHAID不是一个二分树，在树的任何水平，它可以产生的子节点可多于两个。因此它的树要比二分树要宽。
- 20. (本页无文本内容)
- 21. (本页无文本内容)
- 22.
Thank you
