数据挖掘——决策树
(v1,v2,……, vn;c)。这里的vn表示字段值，c表示类别。
分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每个类找到一种准确的描述或者模型。由此生成的类用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意，是预测而不是肯定。我们也可以由此对数据中的每一个类有更好的理解，或者说我们获得了这个类的知识。
分类器评价或比较尺度主要有三种：
预测准确度 预测准确度是用的最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法的分层交叉验证法。
计算复杂度 计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库因此空间和时间的复杂度问题将是非常重要的一个环节。
模型描述的简洁度 对于描述型的分类任务，模型描述越简洁越受欢迎;例如采用规则表示的分类器构造法就比较简单，而神经网络方法产生的结果就难以理解。
(四)决策树学习算法
决策树学习算法是以实例为基础的归纳学习算法，通常用来形成分类器和预测模型，可以对未知数据进行分类或预测、数据预处理、数据挖掘等。它通常包括两部分：树的生成和树的剪枝。
1、决策树描述
一颗决策树的内部结点是属性或属性的集合，叶节点是所要学习划分的类，内部结点的属性称为测试属性。当经过一批训练实例集的训练产生一颗决策树，决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树对实例进行分类的时候，有树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。
决策树是一个可以自动对数据进行分类的树型结构，是树形结构的知识表示，可以直接转换为决策规则，它能被看作一棵树的预测模型，树的根节点是整个数据集合空间，每个分节点是一个分裂问题，它是对一个单一变量的测试，给测试将数据集合空间分割成两个或更多块，每个叶结点是带有分类的数据分割。决策树也可以解释成一种特殊形式的规则集，其特征是规则的层次组织关系。决策树算法主要是用来学习以离散型变量作为属性类型的学习方法。连续型变量必须被离散化才能被学习。表1给出了决策树与自然树的对应关系以及在分类问题中的代表含义。
表1 自然树 树根 杈 树枝 叶子 对应决策树中的意义 根节点 内部（非叶）结点、决策结点 分支 叶结点、状态结点 分类问题中的表示意义 训练实例整个数据集空间 待分类对象的属性（集合） 属性的一个可能取值 数据分割（分类结果） 2、决策树的类型
决策树的内节点的测试属性可能是单变量的，即每个内节点只包含一个属性。也可能是多变量的，即存在包含多个属性的内节点。
根据测试属性的不同属性值的个数，可能使得每个内节点有两个或多个分支。如果每个内节点只有两个分支则称之为二叉决策树。
每个属性可能是值类型，也可能是枚举类型。
分类结果既可能是两类又可能是多类，如果二叉决策树的结果只能有两类则称之为布尔决策树。布尔决策树可以很容易以析取范式的方法表示，并且在决策树学习的最自然的情况就是学习
4
数据挖掘——决策树
析取概念。
3、递归方式
决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。决策树生成算法分成两个步骤：一是树的生成，开始时所有数据都在根节点，然后递归的进行数据分片。二是树的修剪，就是去掉一些可能是噪音或异常的数据决策树停止分割的条件有：一个结点上的数据都是属于同一个类别；没有属性可以在用于对数据进行分割。
4、决策树的构造算法
决策树的构造算法可通过训练集T完成，其中T={ cj>},而x=(a1,a2,…, an)为一个训 练实例，它有n个属性，分别列于属性表（A1,A2,…，An），其中ai表示属性Ai的取值。Cj∈C={C1, C2,..., Cm}为X的分类结果。算法分以下几步： 从属性表中选择属性Ai作为分类属性； 若属性Ai的取值有Ki个，则将T划分为Ki个子集T1，…, TKi,其中 Tij ={ 从属性表中删除属性Ai； 对于每一个Tij（1≤j≤K1），令T=Tij； 如果属性表非空，返回（1），否则输出。 目前比较成熟的决策树方法有ID3、C4.5、CART、SLIQ等。 5、决策树的简化方法 在决策树学习过程中，如果决策树过于复杂，则存储所要花费的代价也就越大；而如果结点个数过多，则每个节点所包含的实例个数就越小，支持每个叶结点假设的实例个数也越小，学习后的错误率就随之增加；同时对用户来说难于理解，使得很大程度上分类器的构造没有意义，实践表明简单的假设更能反映事物之间的关系，所以在决策树学习中应该对决策树进行简化。 简化决策树的方法有控制树的规模、修改测试空间、修改测试属性、数据库约束、改变数据结构等。 控制树的规模可以采用预剪枝、后剪枝算法及增量树方法来实现，预剪枝算法不要求决策树的每一个叶结点都属于同一个类，而是在这之前就停止决策树的扩张，具体何时停止是其研究的主要内容，例如可以规定决策树的高度，达到一定高度即停止扩张；或计算扩张对系统性能的增益，如小于某个规定的值则停止扩张。后剪枝算法则首先利用增长集生成一颗未经剪枝的决策树T并进行可能的修剪，把T作为输入，再利用修剪集进行选择，输出选择最好的规则。 6、决策树算法的讨论 5 数据挖掘——决策树 基于决策树的学习算法具有建立速度快、精度高、可以生成可理解的规则、计算量相对来说不是很大、可以处理连续值和离散值属性、可以清晰的显示哪些属性比较重要等优点，另外在学习过程中不需要使用者了解很多背景知识，只要训练例子能够用属性——结论式的方式表达出来，就能使用该算法来学习。 决策树算法的缺点：对连续性的字段比较难预测；对有时间顺序的数据，需要很多预处理工作；当类别太多时，错误可能就会增加的比较快；算法分类时只是根据一个字段来分类。 决策树技术是一种“贪心”搜索，使用了贪心算法，它把每个属性值依次试探加入左子树，如果能够找到更大的信息增益那么就把这个属性值加入左子树，否则把它退回右子树。这样试探下去，直到左子树不能再变大为止，就能求到最大的属性值。贪心算法总是做出在当前看来最好的选择，并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。 四、决策树算法分类 决策树的生成算法主要有ID3、C4.5、CART、CHAID等方法。ID3算法在1979年由J.R.Quinlan提出，是机器学习中广为人知的一个算法，在归纳学习中，它代表着基于决策树方法的一大类，ID3及后来的C4.5均是Quinlan在Hunt的概念学习系统(Concept Learning System CLS)上发展起来的一种自顶向下的学习算法，而C4.5算法又是Quinlan本人针对ID3算法提出的一种改进算法，他在1993年出版了专著《机器学习规划》对C4.5算法进行了详细的描述。CHAID(即Chi-Square Automatic Interacion Detector的缩写，卡方自动互动侦测器)算法是Gordon B.Kass博士在1976年提出的，可用来对于分类性数据进行挖掘。CART (即Classification And Regression Tree的缩写，分类回归树)算法从1984年开始得到普及推广，可对连续型因变量进行处理。针对这些算法的缺点，很多研究人员尝试在控制树的大小和简化决策树等方面作出努力，通过研究各种预剪枝算法和后剪枝算法来控制树的规模，同时在修改测试属性空间、改进测试属性选择方法、限制数据集、改变数据结构等方面提出了许多新的算法和标准。 五、ID3学习算法 1、基本原理 信息熵在信息论中称为平均信息量，是对被传送的信息进行度量所采用的一种平均值。信源中被传送的信息包括有限数目的互斥并联合完备的事件，它们都以一定的概率出现，用数学式子来表示就是:一组事件X1,… ,Xr，以既定概率p(X1),…,p(Xr)出现，其平均值H(X)就是信息熵，它的值等于每个事件的(自)信息量I(X)的数学期望，即: H(X)???p(Xi)I(Xi)???p(Xi)logp(Xi) r?1r?1rr传统ID3学习算是以信息熵(也称信息不确定性)的下降速度作为选取测试属性的标准。该算法根据属性集的取值选择实例的类别。它的核心是在决策树中各级结点上选择属性，用信息增益作为属性选择标准，使得在每一非叶结点进行测试时，能获得关于被测试例子最大的类别信息。使用该属性将例子集分成子集后，系统的熵值最小，期望该非叶结点到达各后代叶节点的平均路径最短，使生成的决策树平均深度较小。可以看出训练例集在目标分类方面越模糊越杂乱无序， 6 数据挖掘——决策树 它的熵就越高；训练例集在目标分类方面越清晰则越有序，它的熵越低，ID3算法就是根据“信息赢取(增益)越大的属性对训练例的分类越有利”的原则在算法的每一步选取“属性表中可对训练例集进行最佳分类的属性”。一个属性的信息增益就是由于使用这个属性分割样例而导致系统熵的降低，计算各个属性的信息赢取并加以比较是ID3算法的关键操作。 ID3算法的步骤如下： (1)选出整个训练实例集X的规模为W的随机子集Xl (W称为窗口规模，子集称为窗口)； (2)以使得信息熵的值最小为标准，选取每次的测试属性，形成当前窗口的决策树； (3)顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外则训练结束； (4)组合当前窗口的一些训练实例与某些在(3)中找到的例外形成新的窗口，转(2)。 2、ID3算法的形式化模型 ID3基本原理是基于两类分类问题，其数学模型可描述如下:设E= F1*F2*…*Fn是n维有穷向量空间，其中Fj是有穷离散符号集，E中的元素e= Fj, J=1,2, …, n。设P和N是E和F的两个实例集，分别叫正例集和反例集。假设向量空间E中 的正例集PE和反例集NE的大小分别为P和N, ID3基于下列两个假设： (1)在向量空间E上的一棵正确决策树，对任意例子的分类概率同E中的正、反例的概率一致。 (2)一棵决策树能对一实例作出正确类别判断所需的信息量(原集合E的熵)为: PPNNE(E)??log?logP?NP?NP?NP?N 如果以属性A作为决策树的根，A具有v个值（V1、V2…Vv），它将E分为v个子集（E1,E2…Ev），假设Ei中含有Pi个正例和Ni个反例，子集Ei的信息熵为E(Ei)： PiPiNiNiE(Ei)??log?log Pi?NiPi?NiPi?NiPi?Ni以属性A为根分类后的信息熵（用A分类后上的期望值）为E(A): Pi?NiE(A)??E(Ei) r?1P?N因此，以属性为根的信息增益I（A）是： vI(A)?E(E)?E(A) ID3选择使I(A)最大(即E(A)最小)的属性A作为根结点。对A的不同的取值对应的E的v个子集Ei递归调用上述过程，生成A的子结点B1，B2，…，Bv。 ID3的基本原理是基于两类分类问题，但很容易扩展到多类。设样本集S共有C类样本，每类样本数为Pi,(i=1, 2, 3,…,c)。若以属性A作为决策树的根，A具有v个值V1， V2，…，Vv， 7 数据挖掘——决策树 它将E分成v个子集[E1，E2，…，Ev]，假设Ei中含有j类样本的个数为Pij=1，2，…，c，那么子集Ei的信息量是E(Ei)为： PijPijE(Ei)???log|Ei| j?1|Ei|以A为根分类的信息熵为： c|Ei|E(A)??E(Ei) i?1|E|选择属性A使公式6中E(A)最小，信息增益也将增大。 v3. ID3算法的流程 ID3算法是一个从上到下、分而治之的归纳过程。 ID3算法的核心是：在决策树各级节点上选择分裂属性时，通过计算信息增益来选择属性，以使得在每一个非叶节点进行测试时，能获得关于被测试样本最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树节点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树节点的分支，直到所有子集仅包括同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。 4.ID3算法的性能分析 ID3算法是一种典型的决策树分析算法，后来发展的许多决策树算法都是以ID3算法为基础发展而来的。 ID3算法的优点在于它构建决策树的速度比较快，它的计算时间随问题的难度只是线性地增加，适合处理大批量数据集。 同时，ID3算法的缺点也是突出的，包括以下几点。 （1）ID3算法对训练样本的质量的依赖性很强，训练样本的质量主要是指是否存在噪声和是 8