神经决策树算法代码

‘壹’ 决策树算法的典型算法

决策树的典型算法有ID3，C4.5，CART等。
国际权威的学术组织，数据挖掘国际会议ICDM （the IEEE International Conference on Data Mining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解，准确率较高。不过在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，在实际应用中因而会导致算法的低效。
决策树算法的优点如下：
（1）分类精度高；
（2）生成的模式简单；
（3）对噪声数据有很好的健壮性。
因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。

‘贰’ 决策树(decisionTree)

决策树(decisionTree)是一种基本的分类和回归方法。此文仅讨论用于分类方法的决策树。

决策树的学习通常分为3步：

决策树的学习的思想主要源于

定义决策树 ：

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点又分为内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。
形如：

其中，圆表示内部结点，方框表示叶结点。

if-then规则，简单来说就是 ：

举例：对于一个苹果，外表是红色的是红苹果，外表是绿色的是青苹果。可以表示为：

if-then规则集合具有一个重要的性质：

这就是说每一个实例都被一条路径或规则覆盖，并且只被一条路径或规则覆盖。这里所谓的覆盖是指实例的特征与路径上的特征一致，或实例满足规则的条件。

给定数据集：

其中， 为输入实例（特征向量），含有 个特征， 为类标记， , 为样本容量。

目标 ：
根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确分类。

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。

如果我们利用某一个特征进行分类的结果与随机分类的结果没什么很大的差别的话，则称这个特征没有分类能力。

那么问题来了，怎么选择特征呢？

通常特征选择的准则是

下面通过例子来说明一下。

目标 ：
希望通过所给的训练集数据，学习一个贷款申请的决策树。当新的客户提出贷款申请的时候，根据申请人的特征利用决策树决定是否批准贷款申请。

可见这里共有4个特征可供选择。用特征选择的准则是 。接下来介绍 。

：
熵是表示随机变量不确定性的度量。

设 是一个取有限个值的随机变量，其概率分布为

则随机变量 的熵定义为

若 ，则定义 。通常对数取以2为底，或是以 为底，熵的单位分布为比特（bit）或是纳特（nat）。
由上式可知，熵只依赖 的分布，而已 的值无关，则 的熵还可记作 ，即

则从定义可知

当随机变量只取2个值的时候，例如 时， 的分布为

熵为

熵随概率变化的曲线为

当 或 时 ，随机变量完全没有不确定性，当 时 ，熵取值最大，随机变量不确定性最大。

设随机变量 ，其联合概率分布

条件熵 表示在已知随机变量 的条件下随机变量 的不确定性。随机变量 给定条件下随机变量 的条件熵(conditional entropy)，定义为 给定条件下 的条件概率分布的熵对 的数学期望

信息增益
特征 对训练集 的信息增益

根据信息增益准则的特征选择方法：对训练集 ，计算其每个特征的信息增益，并比较大小，选择信息增益最大的特征。

前期定义各个量：

信息增益的算法
输入：训练集 和特征 ；
输出：特征 对训练集 的信息增益

回看刚才的例子，

解 ：

这一次我很无聊的想用一下.csv文件类型。

所以训练数据集部分如下，我存在一个loan.csv文件里了。对.csv文件的各种处理一般由python的pandas模块完成。

第一步，导入相关模块

第二步，读入数据

若是使用jupyter，可以即刻查看一下数据，和数据标签。

可以看出，除了'ID'之外前4个标签 'age', 'work', 'own house', 'Credit conditions'为我们一直在说的特征 ，而最后一个标签'label'是我们所说的类 ，所以要处理一下这些标签，

第三步，计算训练集 的熵 ：

这里会用到pandas的一个统计数据的功能， groupby(by = [列]).groups ，将数据统计成字典的形式，这么说比较抽象，看下图，将我们用pandas读入的data，分为2类， ， Index 表示索引，即第0，1，4，5，6，14（python计数从0开始）个数据的 ，第2，3，7，8，9，10，11，12，13个数据的 .

那么计算训练集 的熵

第四步，计算特征 对数据集 的条件熵

第五步 ，计算信息增益

输入：训练集 和特征 和阈值 ；
输出：决策树
(1) 中所有实例都属于同一类 ，则 为单结点树，并将类 作为该结点的类标记，返回 ；
(2) 若 ，则 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ；
(3)否则，按照上述信息增益的算法，计算 中各个特征对 的信息增益，选择信息增益最大的特征 ；
(4)如果特征 的信息增益小于阈值 ，将置 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ；
(5)否则，对 的每一个可能值 ，依 将 分割为若干非空子集 ，将 中实例数最大的类 作为该结点的类标记，构建子结点，由结点及其子结点构成树 ，返回 ；
(6)对第 个子结点，以 为训练集，以 为特征集，递归的调用步骤(1)~步骤(5)，得到子树 ，返回 。

对上述表的训练集数据，利用ID3算法建立决策树。

解 ：

第一次迭代 ：

【特征：有自己的房子】将数据集 划分为2个子集 （有自己的房子）和 （没有自己的房子），观察一下 和 ：

：

由于 所有实例都属于同一类 ，所以它是一个叶结点，结点的类标记为“是”。

：

对于 则需从特征 中选择新的特征。

第二次迭代 ：

将 看作新的数据集 。【特征：有工作】有2个可能值，划分为2个子集 （有工作）和 （没有工作），观察一下 和 ：

：

由于 所有实例都属于同一类 ，所以它是一个叶结点，结点的类标记为“是”。

：

‘叁’ 决策树算法基础 ID3与C4.5

决策树算法基础：ID3与C4.5
设X是一个取有限个值得离散随机变量，其概率分布为P(X=xi)=pi, i=1,2,…,n。则随机变量X的信息熵为
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。H(Y|X)的计算公式为
所以决策树分支后信息总熵H(D|A)=P1*H1+P2*H2+...+Pn*Hn,(特征A条件下D的经验条件熵)
所以信息增益ΔH=H(D)-H(D|A)
H(D|A)越小，ΔH越大，该特征A越适合作为当前的决策节点。
选取最佳特征伪代码：
计算信息总熵H(D)
遍历每一个特征下的关于D的经验条件熵H(D|A)
计算每一个特征的信息增益ΔH
将信息增益ΔH最大的特征作为最佳特征选为当前决策节点
ID3算法伪代码：
如果第一个标签的数量等于所有的标签数量，说明这是一个单节点树，返回这个标签作为该节点类
如果特征只有一个，说明这是一个单节点树，用多数表决法投票选出标签返回作为该节点类
否则，按信息增益最大的特征A作为当前决策节点，即决策树父节点
如果该特征的信息增益ΔH小于阈值，则用多数表决法投票选出标签返回作为该节点类
否则，对于该特征A的每一个可能值ai，将原空间D分割为若干个子空间Di
对于若干个非空子集Di，将每个Di中实例数最大的类作为标记，构建子节点
以Di为训练空间，递归调用上述步骤
由于信息增益存在偏向于选择取值较多的特征的问题，而C4.5算法中，将ID3算法里的信息增益换成信息增益比，较好地解决了这个问题。
决策树的优点在于计算量简单，适合有缺失属性值的样本，适合处理不相关的特征。而缺点是容易过拟合，可以通过剪枝来简化模型，另外随机森林也解决了这个问题。

‘肆’ 决策树算法如何将连续值转化为离散值处理，我要Python实现的代码，希望完整一点

切断就行了。。。比如某个特征的值，预期会在1-100之间。。。那么你可以人为的切片，1-10的，就算1。。。

‘伍’ 常见决策树分类算法都有哪些

在机器学习中，有一个体系叫做决策树，决策树能够解决很多问题。在决策树中，也有很多需要我们去学习的算法，要知道，在决策树中，每一个算法都是实用的算法，所以了解决策树中的算法对我们是有很大的帮助的。在这篇文章中我们就给大家介绍一下关于决策树分类的算法，希望能够帮助大家更好地去理解决策树。
1.C4.5算法
C4.5算法就是基于ID3算法的改进，这种算法主要包括的内容就是使用信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性等内容，这种算法是一个十分使用的算法。
2.CLS算法
CLS算法就是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。
3.ID3算法
ID3算法就是对CLS算法的最大改进是摒弃了属性选择的随机性，利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗干扰能力差。
3.1.ID3算法的优缺点
ID3算法的优点就是方法简单、计算量小、理论清晰、学习能力较强、比较适用于处理规模较大的学习问题。缺点就是倾向于选择那些属性取值比较多的属性，在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。
3.2.ID3算法的核心思想
根据样本子集属性取值的信息增益值的大小来选择决策属性，并根据该属性的不同取值生成决策树的分支，再对子集进行递归调用该方法，当所有子集的数据都只包含于同一个类别时结束。最后，根据生成的决策树模型，对新的、未知类别的数据对象进行分类。
在这篇文章中我们给大家介绍了决策树分类算法的具体内容，包括有很多种算法。从中我们不难发现决策树的算法都是经过不不断的改造趋于成熟的。所以说，机器学习的发展在某种程度上就是由于这些算法的进步而来的。

‘陆’ 决策树（Decision Tree）

  决策树（Decision Tree）是一种基本的分类与回归方法，其模型呈树状结构，在分类问题中，表示基于特征对实例进行分类的过程。本质上，决策树模型就是一个定义在特征空间与类空间上的条件概率分布。决策树学习通常包括三个步骤： 特征选择 、 决策树的生成 和 决策树的修剪 。

  分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）和叶节点（leaf node）。内部节点表示一个特征或属性，叶节点表示一个类。

  利用决策树进行分类，从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点；这时，每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点。最后将实例分到叶节点的类中。

  决策树是给定特征条件下类的条件概率分布，这一条件概率分布定义在特征区间的一个划分（partiton）上。将特征空间划分为互不相交的单元（cell）或区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示成P(Y|X)。X取值于给定划分下单元的集合，Y取值于类的集合，各叶节点（单元）上的条件概率往往偏向于某一个类，即属于某一类的概率较大，决策树分类时将该节点的实例分到条件概率大的那一类去。也就以为着决策树学习的过程其实也就是由数据集估计条件概率模型的过程，这些基于特征区间划分的类的条件概率模型由无穷多个，在进行选择时，不仅要考虑模型的拟合能力还要考虑其泛化能力。

  为了使模型兼顾模型的拟合和泛化能力，决策树学习使用正则化的极大似然函数来作为损失函数，以最小化损失函数为目标，寻找最优的模型。显然从所有可能的决策树中选取最优决策树是NP完全问题，所以在实际中通常采用启发式的方法，近似求解这一最优化问题： 通过递归的选择最优特征，根据该特征对训练数据进行划分直到使得各个子数据集有一个最好的分类，最终生成特征树 。当然，这样得到的决策树实际上是次最优（sub-optimal）的。进一步的，由于决策树的算法特性，为了防止模型过拟合，需要对已生成的决策树自下而上进行剪枝，将树变得更简单，提升模型的泛化能力。具体来说，就是去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，然后将父节点或更高的节点改为新的叶节点。如果数据集的特征较多，也可以在进行决策树学习之前，对数据集进行特征筛选。

  由于决策树是一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型，决策树的生成对应模型的局部选择，决策树的剪枝对应着模型的全局选择。

   熵（Entropy） 的概念最早起源于物理学，最初物理学家用这个概念度量一个热力学系统的无序程度。在1948年， 克劳德·艾尔伍德·香农 将热力学的熵，引入到 信息论 ，因此它又被称为 香农熵 。在信息论中，熵是对不确定性的量度，在一条信息的熵越高则能传输越多的信息，反之，则意味着传输的信息越少。

  如果有一枚理想的硬币，其出现正面和反面的机会相等，则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么，因此每一次抛硬币都是不可预测的。因此，使用一枚正常硬币进行若干次抛掷，这个事件的熵是一 比特 ，因为结果不外乎两个——正面或者反面，可以表示为 0, 1 编码，而且两个结果彼此之间相互独立。若进行 n 次 独立实验 ，则熵为 n ，因为可以用长度为 n 的比特流表示。但是如果一枚硬币的两面完全相同，那个这个系列抛硬币事件的熵等于零，因为 结果能被准确预测 。现实世界里，我们收集到的数据的熵介于上面两种情况之间。

  另一个稍微复杂的例子是假设一个 随机变量 X ，取三种可能值 ，概率分别为 ，那么编码平均比特长度是： 。其熵为 。因此<u>熵实际是对随机变量的比特量和顺次发生概率相乘再总和的</u> 数学期望 。

  依据玻尔兹曼H定理，香农把随机变量X的熵 定义为：

  其中 是随机变量X的信息量，当随机变量取自有限样本时，熵可以表示为：

  若 ，则定义 。

  同理可以定义条件熵 :

  很容易看出，条件熵（conditional entropy） 就是X给定条件下Y的条件概率分布的熵对X的数学期望。当熵和条件熵中的概率有极大似然估计得到时，所对应的熵和条件熵分别称为检验熵（empirical entropy）和经验条件熵（empirical conditional entropy）.

  熵越大，随机变量的不确定性就越大，从定义可以验证:

  当底数 时，熵的单位是 ；当 时，熵的单位是 ;而当 时，熵的单位是 .

  如英语有26个字母，假如每个字母在文章中出现的次数平均的话，每个字母的信息量 为：

  同理常用汉字2500有个，假设每个汉字在文章中出现的次数平均的话，每个汉字的信息量 为：

  事实上每个字母和汉字在文章中出现的次数并不平均，少见字母和罕见汉字具有相对较高的信息量，显然，由期望的定义，熵是整个消息系统的平均消息量。

  熵可以用来表示数据集的不确定性，熵越大，则数据集的不确定性越大。因此使用 划分前后数据集熵的差值 量度使用当前特征对于数据集进行划分的效果（类似于深度学习的代价函数）。对于待划分的数据集 ，其划分前的数据集的熵 是一定的，但是划分之后的熵 是不定的， 越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高）。因此 越大，说明使用当前特征划分数据集 时，纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的数据子集，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集 。

  显然这种划分方式是存在弊端的，按信息增益准则的划分方式，当数据集的某个特征B取值较多时，依此特征进行划分更容易得到纯度更高的数据子集，使得 偏小，信息增益会偏大，最终导致信息增益偏向取值较多的特征。

  设 是 个数据样本的集合，假定类别属性具有 个不同的值： ,设 是类 中的样本数。对于一个给定样本，它的信息熵为：

  其中， 是任意样本属于 的概率，一般可以用 估计。

  设一个属性A具有 个不同的值 ，利用属性A将集合 划分为 个子集 ，其中 包含了集合 中属性 取 值的样本。若选择属性A为测试属性，则这些子集就是从集合 的节点生长出来的新的叶节点。设 是子集 中类别为 的样本数，则根据属性A划分样本的信息熵为：

  其中 , 是子集 中类别为 的样本的概率。最后，用属性A划分样本子集 后所得的 信息增益(Gain) 为：

  即，<u>属性A的信息增益=划分前数据的熵-按属性A划分后数据子集的熵</u>。 信息增益（information gain）又称为互信息（matual information）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 。信息增益显然 越小， 的值越大，说明选择测试属性A对于分类提供的信息越多，选择A之后对分类的不确定程度越小。

  经典算法 ID3 使用的信息增益特征选择准则会使得划分更偏相遇取值更多的特征，为了避免这种情况。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基础上将特征选择准则由 信息增益 改为了 信息增益率 。在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大（类似于正则化）。这个惩罚参数就是 分裂信息度量 的倒数 。

  不同于 ID3 和 C4.5 , CART 使用基尼不纯度来作为特征选择准则。基尼不纯度也叫基尼指数 , 表示在样本集合中一个随机选中的样本被分错的概率 则<u>基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率</u>。Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

样本集合的基尼指数：
样本集合 有m个类别， 表示第 个类别的样本数量,则 的Gini指数为：

基于某个特征划分样本集合S之后的基尼指数：
  CART是一个二叉树，也就是当使用某个特征划分样本集合后，得到两个集合：a.等于给定的特征值的样本集合 ；b.不等于给定特征值的样本集合 。实质上是对拥有多个取值的特征的二值处理。

对于上述的每一种划分，都可以计算出基于划分特=某个特征值将样本集合划分为两个子集的纯度：

因而对于一个具有多个取值（超过2个）的特征，需要计算以每个取值为划分点，对样本集合划分后子集的纯度 ( 表示特征 的可能取值)然后从所有的划分可能 中找出Gini指数最小的划分，这个划分的划分点，就是使用特征 对样本集合 进行划分的最佳划分点。

参考文献 ：

决策树--信息增益，信息增益比，Geni指数的理解

【机器学习】深入理解--信息熵（Information Entropy）

统计学习方法 （李航）

  为了便于理解，利用以下数据集分别使用三种方法进行分类：

  在进行具体分析之前，考虑到收入是数值类型，要使用决策树算法，需要先对该属性进行离散化。
  在机器学习算法中，一些分类算法（ID3、Apriori等）要求数据是分类属性形式，因此在处理分类问题时经常需要将一些连续属性变换为分类属性。一般来说，连续属性的离散化都是通过在数据集的值域内设定若干个离散的划分点，将值域划分为若干区间，然后用不同的符号或整数数值代表落在每个子区间中的数据值。所以，离散化最核心的两个问题是：如何确定分类数以及如何将连续属性映射到这些分类值。常用的离散化方法有 等宽法 ， 等频法 以及 一维聚类法 等。

在实际使用时往往使用Pandas的 cut() 函数实现等宽离散化:

  可以看到与手工计算的离散化结果相同，需要注意的是，<u> 等宽法对于离群点比较敏感，倾向于不均匀地把属性值分布到各个区间，导致某些区间数据较多，某些区间数据很少，这显然不利用决策模型的建立。 </u>

使用四个分位数作为边界点，对区间进行划分：

<u> 等频率离散化虽然避免了等宽离散化的数据分布不均匀的问题,却可能将相同的数据值分到不同的区间以满足每个区间具有相同数量的属性取值的要求。 </u>

使用一维聚类的离散化方法后得到数据集为：

  在本次实例中选择使用基于聚类的离散化方法后得到的数据集进行指标计算。为了预测客户能否偿还债务，使用A（拥有房产）、B（婚姻情况）、C（年收入）等属性来进行数据集的划分最终构建决策树。

单身 ：

离婚 ：

已婚 ：

显然，由B属性取值'已婚'划分得到的子数据集属于同一个叶节点，无法再进行分类。
接下来，对由B属性取值'单身'划分得到的子数据集 再进行最优特征选择：

1）计算数据集 总的信息熵，其中4个数据中，能否偿还债务为'是'数据有3，'否'数据有1,则总的信息熵：

2）对于A(拥有房产)属性，其属性值有'是'和'否'两种。其中，在A为'是'的前提下，能否偿还债务为'是'的有1、'否'的有0；在A为'否'的前提下，能否偿还债务为'是'的有2、为'否'的有1，则A属性的信息熵为：

3)对于B（婚姻情况）属性，由于已被确定，在这个数据子集信息熵为0

4)对于C（年收入）属性，其属性值有'中等输入'、'低收入'两种。在C为'中等收入'的前提下，能否偿还作为为'是'的有1,为'否'的有0；在C为'低收入'的前提下，能否偿还作为为'是'的有2,为'否'的有1;则C属性的信息熵为：

5）最后分别计算两个属性的信息增益值：


信息增益值相同，说明以两个属性对数据子集进行划分后决策树的纯度上升是相同的，此时任选其一成为叶节点即可。
同理，对数据子集 进行最优特征选择，发现信息熵为0：
整理得到最终的决策树：

‘柒’ 决策树的算法

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
具体算法步骤如下；
1创建节点N
2如果训练集为空，在返回节点N标记为Failure
3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N
4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；
5for each 候选属性 attribute_list
6if 候选属性是连续的then
7对该属性进行离散化
8选择候选属性attribute_list中具有最高信息增益率的属性D
9标记节点N为属性D
10for each 属性D的一致值d
11由节点N长出一个条件为D=d的分支
12设s是训练集中D=d的训练样本的集合
13if s为空
14加上一个树叶，标记为训练集中最普通的类
15else加上一个有C4.5（R - {D},C，s）返回的点 背景：
分类与回归树(CART——Classification And Regression Tree)) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。
分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显着。模型的关键是预测准则的构建，准确的。
定义：
分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。

‘捌’ 如何利用matlab建立决策树模型，对原始数据（excel表格）有什么要求最好有代码，C4.5算法的~

C4.5的好像没看到人实现过，不过ID3是很好用的，用treefit函数，excel函数只要主体部分，属性矩阵和分类向量要分开存放，不要第一行和第一列的注释内容（如果没有就不用删），用xlsread函数获取Excel数据得到输入矩阵。目标向量可以另外在建立一个excel一样的使用。可以继续交流

‘玖’ 实现ID3决策树学习算法

http://www.rulequest.com/download.html
http://www.rulequest.com/See5-demo.zip
这里有些。
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)的问题

‘拾’ 求决策树源代码。最好使用matlab实现。

function [Tree RulesMatrix]=DecisionTree(DataSet,AttributName)
%输入为训练集，为离散后的数字，如记录1：1 1 3 2 1；
%前面为属性列，最后一列为类标
if nargin<1
error('请输入数据集');
else
if isstr(DataSet)
[DataSet AttributValue]=readdata2(DataSet);
else
AttributValue=[];
end
end
if nargin<2
AttributName=[];
end
Attributs=[1:size(DataSet,2)-1];
Tree=CreatTree(DataSet,Attributs);
disp([char(13) 'The Decision Tree:']);
showTree(Tree,0,0,1,AttributValue,AttributName);
Rules=getRule(Tree);
RulesMatrix=zeros(size(Rules,1),size(DataSet,2));
for i=1:size(Rules,1)
rule=cell2struct(Rules(i,1),{'str'});
rule=str2num([rule.str([1:(find(rule.str=='C')-1)]) rule.str((find(rule.str=='C')+1):length(rule.str))]);
for j=1:(length(rule)-1)/2
RulesMatrix(i,rule((j-1)*2+1))=rule(j*2);
end
RulesMatrix(i,size(DataSet,2))=rule(length(rule));
end
end
function Tree=CreatTree(DataSet,Attributs) %决策树程序 输入为：数据集，属性名列表
%disp(Attributs);
[S ValRecords]=ComputEntropy(DataSet,0);
if(S==0) %当样例全为一类时退出，返回叶子节点类标
for i=1:length(ValRecords)
if(length(ValRecords(i).matrix)==size(DataSet,1))
break;
end
end
Tree.Attribut=i;
Tree.Child=[];
return;
end
if(length(Attributs)==0) %当条件属性个数为0时返回占多数的类标
mostlabelnum=0;
mostlabel=0;
for i=1:length(ValRecords)
if(length(ValRecords(i).matrix)>mostlabelnum)
mostlabelnum=length(ValRecords(i).matrix);
mostlabel=i;
end
end
Tree.Attribut=mostlabel;
Tree.Child=[];
return;
end
for i=1:length(Attributs)
[Sa(i) ValRecord]=ComputEntropy(DataSet,i);
Gains(i)=S-Sa(i);
AtrributMatric(i).val=ValRecord;
end
[maxval maxindex]=max(Gains);
Tree.Attribut=Attributs(maxindex);
Attributs2=[Attributs(1:maxindex-1) Attributs(maxindex+1:length(Attributs))];
for j=1:length(AtrributMatric(maxindex).val)
DataSet2=[DataSet(AtrributMatric(maxindex).val(j).matrix',1:maxindex-1) DataSet(AtrributMatric(maxindex).val(j).matrix',maxindex+1:size(DataSet,2))];
if(size(DataSet2,1)==0)
mostlabelnum=0;
mostlabel=0;
for i=1:length(ValRecords)
if(length(ValRecords(i).matrix)>mostlabelnum)
mostlabelnum=length(ValRecords(i).matrix);
mostlabel=i;
end
end
Tree.Child(j).root.Attribut=mostlabel;
Tree.Child(j).root.Child=[];
else
Tree.Child(j).root=CreatTree(DataSet2,Attributs2);
end
end
end
function [Entropy RecordVal]=ComputEntropy(DataSet,attribut) %计算信息熵
if(attribut==0)
clnum=0;
for i=1:size(DataSet,1)
if(DataSet(i,size(DataSet,2))>clnum) %防止下标越界
classnum(DataSet(i,size(DataSet,2)))=0;
clnum=DataSet(i,size(DataSet,2));
RecordVal(DataSet(i,size(DataSet,2))).matrix=[];
end
classnum(DataSet(i,size(DataSet,2)))=classnum(DataSet(i,size(DataSet,2)))+1;
RecordVal(DataSet(i,size(DataSet,2))).matrix=[RecordVal(DataSet(i,size(DataSet,2))).matrix i];
end

Entropy=0;
for j=1:length(classnum)
P=classnum(j)/size(DataSet,1);
if(P~=0)
Entropy=Entropy+(-P)*log2(P);
end
end
else
valnum=0;
for i=1:size(DataSet,1)
if(DataSet(i,attribut)>valnum) %防止参数下标越界
clnum(DataSet(i,attribut))=0;
valnum=DataSet(i,attribut);
Valueexamnum(DataSet(i,attribut))=0;
RecordVal(DataSet(i,attribut)).matrix=[]; %将编号保留下来，以方便后面按值分割数据集
end
if(DataSet(i,size(DataSet,2))>clnum(DataSet(i,attribut))) %防止下标越界
Value(DataSet(i,attribut)).classnum(DataSet(i,size(DataSet,2)))=0;
clnum(DataSet(i,attribut))=DataSet(i,size(DataSet,2));
end
Value(DataSet(i,attribut)).classnum(DataSet(i,size(DataSet,2)))= Value(DataSet(i,attribut)).classnum(DataSet(i,size(DataSet,2)))+1;
Valueexamnum(DataSet(i,attribut))= Valueexamnum(DataSet(i,attribut))+1;
RecordVal(DataSet(i,attribut)).matrix=[RecordVal(DataSet(i,attribut)).matrix i];
end
Entropy=0;
for j=1:valnum
Entropys=0;
for k=1:length(Value(j).classnum)
P=Value(j).classnum(k)/Valueexamnum(j);
if(P~=0)
Entropys=Entropys+(-P)*log2(P);
end
end
Entropy=Entropy+(Valueexamnum(j)/size(DataSet,1))*Entropys;
end
end
end
function showTree(Tree,level,value,branch,AttributValue,AttributName)
blank=[];
for i=1:level-1
if(branch(i)==1)
blank=[blank ' |'];
else
blank=[blank ' '];
end
end
blank=[blank ' '];
if(level==0)
blank=[' (The Root):'];
else
if isempty(AttributValue)
blank=[blank '|_____' int2str(value) '______'];
else
blank=[blank '|_____' value '______'];
end
end
if(length(Tree.Child)~=0) %非叶子节点
if isempty(AttributName)
disp([blank 'Attribut ' int2str(Tree.Attribut)]);
else
disp([blank 'Attribut ' AttributName{Tree.Attribut}]);
end
if isempty(AttributValue)
for j=1:length(Tree.Child)-1
showTree(Tree.Child(j).root,level+1,j,[branch 1],AttributValue,AttributName);
end
showTree(Tree.Child(length(Tree.Child)).root,level+1,length(Tree.Child),[branch(1:length(branch)-1) 0 1],AttributValue,AttributName);
else
for j=1:length(Tree.Child)-1
showTree(Tree.Child(j).root,level+1,AttributValue{Tree.Attribut}{j},[branch 1],AttributValue,AttributName);
end
showTree(Tree.Child(length(Tree.Child)).root,level+1,AttributValue{Tree.Attribut}{length(Tree.Child)},[branch(1:length(branch)-1) 0 1],AttributValue,AttributName);
end
else
if isempty(AttributValue)
disp([blank 'leaf ' int2str(Tree.Attribut)]);
else
disp([blank 'leaf ' AttributValue{length(AttributValue)}{Tree.Attribut}]);
end
end
end
function Rules=getRule(Tree)
if(length(Tree.Child)~=0)
Rules={};
for i=1:length(Tree.Child)
content=getRule(Tree.Child(i).root);
%disp(content);
%disp([num2str(Tree.Attribut) ',' num2str(i) ',']);
for j=1:size(content,1)
rule=cell2struct(content(j,1),{'str'});
content(j,1)={[num2str(Tree.Attribut) ',' num2str(i) ',' rule.str]};
end
Rules=[Rules;content];
end
else
Rules={['C' num2str(Tree.Attribut)]};
end
end