① 数据挖掘十大算法-
整理里一晚上的数据挖掘算法，其中主要引自wiki和一些论坛。发布到上作为知识共享，但是发现Latex的公式转码到网页的时候出现了丢失，暂时没找到解决方法，有空再回来填坑了。
——编者按
一、 C4.5
C4.5算法是由Ross Quinlan开发的用于产生决策树的算法[1]，该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法主要应用于统计分类中，主要是通过分析数据的信息熵建立和修剪决策树。
1.1 决策树的建立规则
在树的每个节点处，C4.5选择最有效地方式对样本集进行分裂，分裂规则是分析所有属性的归一化的信息增益率，选择其中增益率最高的属性作为分裂依据，然后在各个分裂出的子集上进行递归操作。
依据属性A对数据集D进行分类的信息熵可以定义如下：
划分前后的信息增益可以表示为：
那么，归一化的信息增益率可以表示为：
1.2 决策树的修剪方法
C4.5采用的剪枝方法是悲观剪枝法(Pessimistic Error Pruning，PEP)，根据样本集计算子树与叶子的经验错误率，在满足替换标准时，使用叶子节点替换子树。
不妨用K表示训练数据集D中分类到某一个叶子节点的样本数，其中其中错误分类的个数为J，由于用估计该节点的样本错误率存在一定的样本误差，因此用表示修正后的样本错误率。那么，对于决策树的一个子树S而言，设其叶子数目为L(S)，则子树S的错误分类数为：
设数据集的样本总数为Num，则标准错误可以表示为：
那么，用表示新叶子的错误分类数，则选择使用新叶子节点替换子树S的判据可以表示为：
二、KNN
最近邻域算法(k-nearest neighbor classification, KNN)[2]是一种用于分类和回归的非参数统计方法。KNN算法采用向量空间模型来分类，主要思路是相同类别的案例彼此之间的相似度高，从而可以借由计算未知样本与已知类别案例之间的相似度，来实现分类目标。KNN是一种基于局部近似和的实例的学习方法，是目前最简单的机器学习算法之一。
在分类问题中，KNN的输出是一个分类族群，它的对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。在回归问题中，KNN的输出是其周围k个邻居的平均值。无论是分类还是回归，衡量邻居的权重都非常重要，目标是要使较近邻居的权重比较远邻居的权重大，例如，一种常见的加权方案是给每个邻居权重赋值为1/d，其中d是到邻居的距离。这也就自然地导致了KNN算法对于数据的局部结构过于敏感。
三、Naive Bayes
在机器学习的众多分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive Bayesian Model，NBC)[3]。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。
在假设各个属性相互独立的条件下，NBC模型的分类公式可以简单地表示为：
但是实际上问题模型的属性之间往往是非独立的，这给NBC模型的分类准确度带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型；而在属性相关性较小时，NBC模型的性能最为良好。
四、CART
CART算法(Classification And Regression Tree)[4]是一种二分递归的决策树，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。在CART算法中主要分为两个步骤：将样本递归划分进行建树过程；用验证数据进行剪枝。
五、K-means
k-平均算法(k-means clustering)[5]是源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-means的聚类目标是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类。
5.1 k-means的初始化方法
通常使用的初始化方法有Forgy和随机划分(Random Partition)方法。Forgy方法随机地从数据集中选择k个观测作为初始的均值点；而随机划分方法则随机地为每一观测指定聚类，然后执行“更新”步骤,即计算随机分配的各聚类的图心，作为初始的均值点。Forgy方法易于使得初始均值点散开，随机划分方法则把均值点都放到靠近数据集中心的地方；随机划分方法一般更适用于k-调和均值和模糊k-均值算法。对于期望-最大化(EM)算法和标准k-means算法，Forgy方法作为初始化方法的表现会更好一些。
5.2 k-means的标准算法
k-means的标准算法主要包括分配(Assignment)和更新(Update)，在初始化得出k个均值点后，算法将会在这两个步骤中交替执行。
分配(Assignment)：将每个观测分配到聚类中，使得组内平方和达到最小。
更新(Update)：对于上一步得到的每一个聚类，以聚类中观测值的图心，作为新的均值点。
六、Apriori
Apriori算法[6]是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。Apriori采用自底向上的处理方法，每次只扩展一个对象加入候选集，并且使用数据集对候选集进行检验，当不再产生匹配条件的扩展对象时，算法终止。
Apriori的缺点在于生成候选集的过程中，算法总是尝试扫描整个数据集并尽可能多地添加扩展对象，导致计算效率较低；其本质上采用的是宽度优先的遍历方式，理论上需要遍历次才可以确定任意的最大子集S。
七、SVM
支持向量机(Support Vector Machine, SVM)[7]是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。
除了进行线性分类之外，SVM还可以使用所谓的核技巧有效地进行非线性分类，将其输入隐式映射到高维特征空间中，即支持向量机在高维或无限维空间中构造超平面或超平面集合，用于分类、回归或其他任务。直观来说，分类边界距离最近的训练数据点越远越好，因为这样可以缩小分类器的泛化误差。
八、EM
最大期望算法(Expectation–Maximization Algorithm, EM)[7]是从概率模型中寻找参数最大似然估计的一种算法。其中概率模型依赖于无法观测的隐性变量。最大期望算法经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望(E)，利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化(M)，最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。
九、PageRank
PageRank算法设计初衷是根据网站的外部链接和内部链接的数量和质量对网站的价值进行衡量。PageRank将每个到网页的链接作为对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。
算法假设上网者将会不断点网页上的链接，当遇到了一个没有任何链接出页面的网页，这时候上网者会随机转到另外的网页开始浏览。设置在任意时刻，用户到达某页面后并继续向后浏览的概率，该数值是根据上网者使用浏览器书签的平均频率估算而得。PageRank值可以表示为：
其中，是被研究的页面集合，N表示页面总数，是链接入页面的集合，是从页面链接处的集合。
PageRank算法的主要缺点是的主要缺点是旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多外链，除非它是某个站点的子站点。
十、AdaBoost
AdaBoost方法[10]是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器Ck。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器Ck[，并且如此迭代地进行下去。
AdaBoost方法的自适应在于：前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中，AdaBoost方法相对于大多数其它学习算法而言，不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱（比如出现很大错误率），但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，同样也能提升分类效果。
引用
[1] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
[2] Altman, N. S. An introction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879
[3] Webb, G. I.; Boughton, J.; Wang, Z. Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning (Springer). 2005, 58 (1): 5–24. doi:10.1007/s10994-005-4258-6
[4] decisiontrees.net Interactive Tutorial
[5] Hamerly, G. and Elkan, C. Alternatives to the k-means algorithm that find better clusterings (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 2002
[6] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.
[7] Cortes, C.; Vapnik, V. Support-vector networks. Machine Learning. 1995, 20 (3): 273–297. doi:10.1007/BF00994018
[8] Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39 (1):1–38, 1977
[9] Susan Moskwa. PageRank Distribution Removed From WMT. [October 16, 2009]
[10] Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855
② R语言-17决策树
是一个预测模型，分为回归决策树和分类决策树，根据已知样本训练出一个树模型，从而根据该模型对新样本因变量进行预测，得到预测值或预测的分类
从根节点到叶节点的一条路径就对应着一条规则．整棵决策树就对应着一组表达式规则。叶节点就代表该规则下得到的预测值。如下图决策树模型则是根据房产、结婚、月收入三个属性得到是否可以偿还贷款的规则。
核心是如何从众多属性中挑选出具有代表性的属性作为决策树的分支节点。
最基本的有三种度量方法来选择属性
1. 信息增益（ID3算法）
信息熵
一个信源发送出什么符号是不确定的，衡量它可以根据其出现的概率来度量。概率大，出现机会多，不确定性小；反之不确定性就大。不确定性函数f是概率P的 减函数 。两个独立符号所产生的不确定性应等于各自不确定性之和，即f(P1,P2)=f(P1)+f(P2)，这称为可加性。同时满足这两个条件的函数f是对数函数，即
在信源中，考虑的不是某一单个符号发生的不确定性，而是要考虑这个信源所有可能发生情况的平均不确定性。因此，信息熵被定义为
决策树分类过程
2、增益率（C4.5算法）
由于信息增益的缺点是：倾向于选择具有大量值的属性，因为具有大量值的属性每个属性对应数据量少，倾向于具有较高的信息纯度。因此增益率使用【信息增益/以该属性代替的系统熵（类似于前面第一步将play换为该属性计算的系统熵】这个比率，试图克服这种缺点。
g(D,A)代表D数据集A属性的信息增益，
3. 基尼指数（CART算法）
基尼指数：
表示在样本集合中一个随机选中的样本被分错的概率。越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高。
假设集合中有K个类别，则：
说明:
1. pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)
2. 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和
3. 当为二分类是，Gini(P) = 2p(1-p)
基尼指数是将属性A做二元划分，所以得到的是二叉树。当为离散属性时，则会将离散属性的类别两两组合，计算基尼指数。
举个例子：
如上面的特征Temperature，此特征有三个特征取值： “Hot”，“Mild”， “Cool”，
当使用“学历”这个特征对样本集合D进行划分时，划分值分别有三个，因而有三种划分的可能集合，划分后的子集如下：
对于上述的每一种划分，都可以计算出基于 划分特征= 某个特征值 将样本集合D划分为两个子集的纯度：
决策数分类过程
先剪枝 ：提前停止树的构建对树剪枝，构造树时，利用信息增益、统计显着性等，当一个节点的划分导致低于上述度量的预定义阈值时，则停止进一步划分。但阈值的确定比较困难。
后剪枝 ：更为常用，先得到完全生长的树，再自底向上，用最下面的节点的树叶代替该节点
CART使用代价复杂度剪枝算法 ：计算每个节点剪枝后与剪枝前的代价复杂度，如果剪去该节点，代价复杂度较小（复杂度是树的结点与树的错误率也就是误分类比率的函数），则剪去。
C4.5采用悲观剪枝 ：类似代价复杂度，但CART是利用剪枝集评估代价复杂度，C4.5是采用训练集加上一个惩罚评估错误率
决策树的可伸缩性
ID3C4.5CART都是为较小的数据集设计，都限制训练元祖停留再内存中，为了解决可伸缩性，提出了其它算法如
RainForest(雨林）：对每个属性维护一个AVC集，描述该结点的训练元组，所以只要将AVC集放在内存即可
BOAT自助乐观算法：利用统计学，创造给定训练数据的较小样本，每个样本构造一个树，导致多颗树，再利用它们构造1颗新树。优点是可以增量的更新，当插入或删除数据，只需决策树更新，而不用重新构造。
决策树的可视化挖掘
PBC系统可允许用户指定多个分裂点，导致多个分支，传统决策树算法数值属性都是二元划分。并且可以实现交互地构建树。
rpart是采用cart算法，连续型“anova”;离散型“class”;
2）进行剪枝的函数：prune()
3）计算MAE评估回归树模型误差，这里将样本划分成了训练集和测试集，testdata为测试集
rt.mae为根据训练集得到的决策树模型对测试集因变量预测的结果与测试集因变量实际值得到平均绝对误差
③ 决策树算法 CART和C4.5决策树有什么区别各用于什么领域
1、C4.5算法是在ID3算法的基础上采用信息增益率的方法选择测试属性。CART算法采用一种二分递归分割的技术，与基于信息熵的算法不同，CART算法对每次样本集的划分计算GINI系数，GINI系数，GINI系数越小则划分越合理。
2、决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
3、决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数据集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。
④ 数据挖掘weka软件里有没有cart算法
有，名称是
weka.classifiers.trees.SimpleCart
它只是CART的基本用法，而且剪枝比较电脑时空复杂度较高。
⑤ 决策树算法
决策树算法的算法理论和应用场景
算法理论：
我了解的决策树算法，主要有三种，最早期的ID3，再到后来的C4.5和CART这三种算法。
这三种算法的大致框架近似。
决策树的学习过程
1.特征选择
在训练数据中 众多X中选择一个特征作为当前节点分裂的标准。如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。
2.决策树生成
根据选择的特征评估标准，从上至下递归生成子节点，直到数据集不可分或者最小节点满足阈值，此时决策树停止生长。
3.剪枝
决策树极其容易过拟合，一般需要通过剪枝，缩小树结构规模、缓解过拟合。剪枝技术有前剪枝和后剪枝两种。
有些算法用剪枝过程，有些没有，如ID3。
预剪枝：对每个结点划分前先进行估计，若当前结点的划分不能带来决策树的泛化性能的提升，则停止划分，并标记为叶结点。
后剪枝：现从训练集生成一棵完整的决策树，然后自底向上对非叶子结点进行考察，若该结点对应的子树用叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
但不管是预剪枝还是后剪枝都是用验证集的数据进行评估。
ID3算法是最早成型的决策树算法。ID3的算法核心是在决策树各个节点上应用信息增益准则来选择特征，递归构建决策树。缺点是，在选择分裂变量时容易选择分类多的特征，如ID值【值越多、分叉越多，子节点的不纯度就越小，信息增益就越大】。
ID3之所以无法 处理缺失值、无法处理连续值、不剪纸等情况，主要是当时的重点并不是这些。
C4.5算法与ID3近似，只是分裂标准从 信息增益 转变成 信息增益率。可以处理连续值，含剪枝，可以处理缺失值，这里的做法多是 概率权重。
CART：1.可以处理连续值 2.可以进行缺失值处理 3.支持剪枝 4.可以分类可以回归。
缺失值的处理是 作为一个单独的类别进行分类。
建立CART树
我们的算法从根节点开始，用训练集递归的建立CART树。
1) 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
2) 计算样本集D的基尼系数， 如果基尼系数小于阈值 （说明已经很纯了！！不需要再分了！！），则返回决策树子树，当前节点停止递归。
3) 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数。
4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择 基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。 (注：注意是二叉树，故这里的D1和D2是有集合关系的，D2=D-D1)
5) 对左右的子节点递归的调用1-4步，生成决策树。
CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。
应用场景
比如欺诈问题中，通过决策树算法简单分类，默认是CART的分类树，默认不剪枝。然后在出图后，自行选择合适的叶节点进行拒绝操作。
这个不剪枝是因为欺诈问题的特殊性，欺诈问题一般而言较少，如数据的万几水平，即正样本少，而整个欺诈问题需要解决的速度较快。此时只能根据业务要求，迅速针对已有的正样本情况，在控制准确率的前提下，尽可能提高召回率。这种情况下，可以使用决策树来简单应用，这个可以替代原本手工选择特征及特征阈值的情况。
⑥ 决策树是什么东东
小白自学路上的备忘记录。。。
参考：
决策树(分类树、回归树)
决策树 :这个博客的图真好看，通俗易懂。哈哈
决策树详解
决策树（Decision Tree）是一种有监督学习算法，常用于分类和回归。本文仅讨论分类问题。
决策树模型是运用于分类以及回归的一种树结构。决策树由节点和有向边组成，一般一棵决策树包含一个根节点、若干内部节点和若干叶节点。决策树的决策过程需要从决策树的根节点开始，待测数据与决策树中的特征节点进行比较，并按照比较结果选择选择下一比较分支，直到叶子节点作为最终的决策结果。
简而言之，决策树是一个利用树的模型进行决策的多分类模型
为了找到最优的划分特征，我们需要先了解一些信息论的知识：
纯度 ：
你可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上，我们可以用纯度来表示，纯度换一种方式来解释就是让目标变量的分歧最小
信息熵 ：表示信息的不确定度
在信息论中，随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性，信息学之父香农引入了信息熵的概念.
当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高 。
信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低
经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）
信息增益 ：
信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。
信息增益率
信息增益率 = 信息增益 / 属性熵
基尼指数
基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。
即 基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
基尼系数的性质与信息熵一样：度量随机变量的不确定度的大小；
G 越大，数据的不确定性越高；
G 越小，数据的不确定性越低；
G = 0，数据集中的所有样本都是同一类别
详细参考： 机器学习——基尼指数
ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树
ID3算法的核心是在决策树各个节点上根据信息增益来选择进行划分的特征，然后递归地构建决策树。算法采用自顶向下的贪婪搜索遍历可能的决策树空间。
具体方法 ：
ID3的局限 ：
C4.5与ID3相似，但大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。
C4.5的实现基于ID3的改进 ：
信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个 启发式方法 ：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。
C4.5的局限 ：
ID3 和 C4.5 生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。
CART(),分类回归树算法，既可用于分类也可用于回归，在这一部分我们先主要将其分类树的生成。区别于ID3和C4.5,CART假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支为取值为“是”的分支，右分支为取值为”否“的分支。这样的决策树等价于递归地二分每个特征，将输入空间(即特征空间)划分为有限个单元。
CART的分类树用基尼指数来选择最优特征的最优划分点，具体过程如下
剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。
过拟合：指的是模型的训练结果“太好了”，以至于在实际应用的过程中，会存在“死板”的情况，导致分类错误。
欠拟合：指的是模型的训练结果不理想.
剪枝的方法 ：
参考： 【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）
更多模型不断更新中。。。。
⑦ 用python实现红酒数据集的ID3,C4.5和CART算法
ID3算法介绍
ID3算法全称为迭代二叉树3代算法（Iterative Dichotomiser 3）
该算法要先进行特征选择，再生成决策树，其中特征选择是基于“信息增益”最大的原则进行的。
但由于决策树完全基于训练集生成的，有可能对训练集过于“依赖”，即产生过拟合现象。因此在生成决策树后，需要对决策树进行剪枝。剪枝有两种形式，分别为前剪枝（Pre-Pruning）和后剪枝（Post-Pruning），一般采用后剪枝。
信息熵、条件熵和信息增益
信息熵：来自于香农定理，表示信息集合所含信息的平均不确定性。信息熵越大，表示不确定性越大，所含的信息量也就越大。
设x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x
1
,x
2
,x
3
,...x
n
为信息集合X的n个取值，则x i x_ix
i
的概率：
P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n
P(X=i)=p
i
,i=1,2,3,...,n
信息集合X的信息熵为：
H ( X ) = − ∑ i = 1 n p i log p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}
H(X)=−
i=1
∑
n
p
i
logp
i
条件熵：指已知某个随机变量的情况下，信息集合的信息熵。
设信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y
1
,y
2
,y
3
,...y
m
组成的随机变量集合Y，则随机变量（X，Y）的联合概率分布为
P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}
P(x=i,y=j)=p
ij
条件熵：
H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}
H(X∣Y)=
j=1
∑
m
p(y
j
)H(X∣y
j
)
由
H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}
H(X∣y
j
)=−
j=1
∑
m
p(y
j
)
i=1
∑
n
p(x
i
∣y
j
)logp(x
i
∣y
j
)
和贝叶斯公式：
p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)
p(x
i
y
j
)=p(x
i
∣y
j
)p(y
j
)
可以化简条件熵的计算公式为:
H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}
H(X∣Y)=
j=1
∑
m
i=1
∑
n
p(x
i
,y
j
)log
p(x
i
,y
j
)
p(x
i
)
信息增益：信息熵-条件熵，用于衡量在知道已知随机变量后，信息不确定性减小越大。
d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)
d(X,Y)=H(X)−H(X∣Y)
python代码实现
import numpy as np
import math
def calShannonEnt(dataSet):
""" 计算信息熵 """
labelCountDict = {}
for d in dataSet:
label = d[-1]
if label not in labelCountDict.keys():
labelCountDict[label] = 1
else:
labelCountDict[label] += 1
entropy = 0.0
for l, c in labelCountDict.items():
p = 1.0 * c / len(dataSet)
entropy -= p * math.log(p, 2)
return entropy
def filterSubDataSet(dataSet, colIndex, value):
"""返回colIndex特征列label等于value，并且过滤掉改特征列的数据集"""
subDataSetList = []
for r in dataSet:
if r[colIndex] == value:
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
subDataSetList.append(newR)
return np.array(subDataSetList)
def chooseFeature(dataSet):
""" 通过计算信息增益选择最合适的特征"""
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatureIndex = -1
for i in range(featureNum):
uniqueValues = np.unique(dataSet[:, i])
condition_entropy = 0.0
for v in uniqueValues: #计算条件熵
subDataSet = filterSubDataSet(dataSet, i, v)
p = 1.0 * len(subDataSet) / len(dataSet)
condition_entropy += p * calShannonEnt(subDataSet)
infoGain = entropy - condition_entropy #计算信息增益
if infoGain >= bestInfoGain: #选择最大信息增益
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex
def creatDecisionTree(dataSet, featNames):
""" 通过训练集生成决策树 """
featureName = featNames[:] # 拷贝featNames，此处不能直接用赋值操作，否则新变量会指向旧变量的地址
classList = list(dataSet[:, -1])
if len(set(classList)) == 1: # 只有一个类别
return classList[0]
if dataSet.shape[1] == 1: #当所有特征属性都利用完仍然无法判断样本属于哪一类，此时归为该数据集中数量最多的那一类
return max(set(classList), key=classList.count)
bestFeatureIndex = chooseFeature(dataSet) #选择特征
bestFeatureName = featNames[bestFeatureIndex]
del featureName[bestFeatureIndex] #移除已选特征列
decisionTree = {bestFeatureName: {}}
featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已选特征列所包含的类别， 通过递归生成决策树
for v in featureValueUnique:
FeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, FeatureName)
return decisionTree
def classify(decisionTree, featnames, featList):
""" 使用训练所得的决策树进行分类 """
classLabel = None
root = decisionTree.keys()[0]
firstGenDict = decisionTree[root]
featIndex = featnames.index(root)
for k in firstGenDict.keys():
if featList[featIndex] == k:
if isinstance(firstGenDict[k], dict): #若子节点仍是树，则递归查找
classLabel = classify(firstGenDict[k], featnames, featList)
else:
classLabel = firstGenDict[k]
return classLabel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
下面用鸢尾花数据集对该算法进行测试。由于ID3算法只能用于标称型数据，因此用在对连续型的数值数据上时，还需要对数据进行离散化，离散化的方法稍后说明，此处为了简化，先使用每一种特征所有连续性数值的中值作为分界点，小于中值的标记为1，大于中值的标记为0。训练1000次，统计准确率均值。
from sklearn import datasets
from sklearn.model_selection import train_test_split
iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]
scoreL = []
for i in range(1000): #对该过程进行10000次
trainData, testData = train_test_split(data) #区分测试集和训练集
featNames = iris.feature_names[:]
for i in range(trainData.shape[1] - 1): #对训练集每个特征，以中值为分界点进行离散化
splitPoint = np.mean(trainData[:, i])
featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
trainData[:, i] = [1 if x <= splitPoint else 0 for x in trainData[:, i]]
testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输出结果为：score: 0.7335，即准确率有73%。每次训练和预测的准确率分布如下：
数据离散化
然而，在上例中对特征值离散化的划分点实际上过于“野蛮”，此处介绍一种通过信息增益最大的标准来对数据进行离散化。原理很简单，当信息增益最大时，说明用该点划分能最大程度降低数据集的不确定性。
具体步骤如下：
对每个特征所包含的数值型特征值排序
对相邻两个特征值取均值，这些均值就是待选的划分点
用每一个待选点把该特征的特征值划分成两类，小于该特征点置为1， 大于该特征点置为0，计算此时的条件熵，并计算出信息增益
选择信息使信息增益最大的划分点进行特征离散化
实现代码如下：
def filterRawData(dataSet, colIndex, value, tag):
""" 用于把每个特征的连续值按照区分点分成两类，加入tag参数，可用于标记筛选的是哪一部分数据"""
filterDataList = []
for r in dataSet:
if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
filterDataList.append(newR)
return np.array(filterDataList)
def dataDiscretization(dataSet, featName):
""" 对数据每个特征的数值型特征值进行离散化 """
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
for featIndex in range(featureNum): #对于每一个特征
uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
meanPoint = []
for i in range(len(uniqueValues) - 1): # 求出相邻两个值的平均值
meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
bestInfoGain = 0.0
bestMeanPoint = -1
for mp in meanPoint: #对于每个划分点
subEntropy = 0.0 #计算该划分点的信息熵
for tag in range(2): #分别划分为两类
subDataSet = filterRawData(dataSet, featIndex, mp, tag)
p = 1.0 * len(subDataSet) / len(dataSet)
subEntropy += p * calShannonEnt(subDataSet)
## 计算信息增益
infoGain = entropy - subEntropy
## 选择最大信息增益
if infoGain >= bestInfoGain:
bestInfoGain = infoGain
bestMeanPoint = mp
featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
return dataSet, featName
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
重新对数据进行离散化，并重复该步骤1000次，同时用sklearn中的DecisionTreeClassifier对相同数据进行分类，分别统计平均准确率。运行代码如下:
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000): #对该过程进行1000次
featNames = iris.feature_names[:]
trainData, testData = train_test_split(data) #区分测试集和训练集
trainData_tmp = .(trainData)
testData_tmp = .(testData)
discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根据信息增益离散化
for i in range(testData.shape[1]-1): #根据测试集的区分点离散化训练集
splitPoint = float(discritizationFeatName[i].split('<=')[-1])
testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
clf = DecisionTreeClassifier('entropy')
clf.fit(trainData[:, :-1], trainData[:, -1])
clf.predict(testData[:, :-1])
scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))
print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
两者准确率分别为：
score: 0.7037894736842105
score-sk: 0.7044736842105263
准确率分布如下：
两者的结果非常一样。
（但是。。为什么根据信息熵离散化得到的准确率比直接用均值离散化的准确率还要低啊？？哇的哭出声。。）
最后一次决策树图形如下：
决策树剪枝
由于决策树是完全依照训练集生成的，有可能会有过拟合现象，因此一般会对生成的决策树进行剪枝。常用的是通过决策树损失函数剪枝，决策树损失函数表示为:
C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|
C
a
(T)=
t=1
∑
T
N
t
H
t
(T)+α∣T∣
其中，H t ( T ) H_t(T)H
t
(T)表示叶子节点t的熵值，T表示决策树的深度。前项∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑
t=1
T
N
t
H
t
(T)是决策树的经验损失函数当随着T的增加，该节点被不停的划分的时候，熵值可以达到最小，然而T的增加会使后项的值增大。决策树损失函数要做的就是在两者之间进行平衡，使得该值最小。
对于决策树损失函数的理解，如何理解决策树的损失函数? - 陶轻松的回答 - 知乎这个回答写得挺好，可以按照答主的思路理解一下
C4.5算法
ID3算法通过信息增益来进行特征选择会有一个比较明显的缺点：即在选择的过程中该算法会优先选择类别较多的属性（这些属性的不确定性小，条件熵小，因此信息增益会大），另外，ID3算法无法解决当每个特征属性中每个分类都只有一个样本的情况（此时每个属性的条件熵都为0）。
C4.5算法ID3算法的改进，它不是依据信息增益进行特征选择，而是依据信息增益率，它添加了特征分裂信息作为惩罚项。定义分裂信息：
S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}
SplitInfo(X,Y)=−
i
∑
n
∣X∣
∣X
i
∣
log
∣X∣
∣X
i
∣
则信息增益率为：
G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}
GainRatio(X,Y)=
SplitInfo(X,Y)
d(X,Y)
关于ID3和C4.5算法
在学习分类回归决策树算法时，看了不少的资料和博客。关于这两个算法，ID3算法是最早的分类算法，这个算法刚出生的时候其实带有很多缺陷：
无法处理连续性特征数据
特征选取会倾向于分类较多的特征
没有解决过拟合的问题
没有解决缺失值的问题
即该算法出生时是没有带有连续特征离散化、剪枝等步骤的。C4.5作为ID3的改进版本弥补列ID3算法不少的缺陷：
通过信息最大增益的标准离散化连续的特征数据
在选择特征是标准从“最大信息增益”改为“最大信息增益率”
通过加入正则项系数对决策树进行剪枝
对缺失值的处理体现在两个方面：特征选择和生成决策树。初始条件下对每个样本的权重置为1。
特征选择：在选取最优特征时，计算出每个特征的信息增益后，需要乘以一个**“非缺失值样本权重占总样本权重的比例”**作为系数来对比每个特征信息增益的大小
生成决策树：在生成决策树时，对于缺失的样本我们按照一定比例把它归属到每个特征值中，比例为该特征每一个特征值占非缺失数据的比重
关于C4.5和CART回归树
作为ID3的改进版本，C4.5克服了许多缺陷，但是它自身还是存在不少问题：
C4.5的熵运算中涉及了对数运算，在数据量大的时候效率非常低。
C4.5的剪枝过于简单
C4.5只能用于分类运算不能用于回归
当特征有多个特征值是C4.5生成多叉树会使树的深度加深
————————————————
版权声明：本文为CSDN博主“Sarah Huang”的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_44794704/article/details/89406612
⑧ 如何对决策树进行剪枝
决策树洞橡衡的剪枝通常有两种方法，预剪枝(Pre-Pruning)和后剪枝(Post- Pruning)。那么这两种方法是如何进行的呢如渣?它们又各有什么优缺点?
■ 预剪枝
预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能带 来模型泛化能力的提升，如果不能，则不再继续生长子树。此时可能存在不同类 别的样本同时存于结点中，按照多数投票的原则判断该结点所属类别。预剪枝对 于何时纳做停止决策树的生长有以下几种方法。
(1)当树到达一定深度的时候，停止树的生长。
(2)当到达当前结点的样本数量小于某个阈值的时候，停止树的生长。
(3)计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继 续扩展。
预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题。但 如何准确地估计何时停止树的生长(即上述方法中的深度或阈值)，针对不同问 题会有很大差别，需要一定经验判断。且预剪枝存在一定局限性，有欠拟合的风 险，虽然当前的划分会导致测试集准确率降低，但在之后的划分中，准确率可能 会有显着上升。
■ 后剪枝
后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后从最底层向上
计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样 按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率 进行判断，如果剪枝过后准确率有所提升，则进行剪枝。相比于预剪枝，后剪枝 方法通常可以得到泛化能力更强的决策树，但时间开销会更大。
常见的后剪枝方法包括错误率降低剪枝(Reced Error Pruning，REP)、悲 观剪枝(Pessimistic Error Pruning，PEP)、代价复杂度剪枝(Cost Complexity Pruning，CCP)、最小误差剪枝(Minimum Error Pruning，MEP)、CVP(Critical Value Pruning)、OPP(Optimal Pruning)等方法，这些剪枝方法各有利弊，关注 不同的优化角度，本文选取着名的CART剪枝方法CCP进行介绍。
代价复杂剪枝主要包含以下两个步骤。
⑨ 决策树ID3，C4.5，CART算法中某一属性分类后，是否能运用该属性继续分类
决策树主要有ID3，C4.5，CART等形式。ID3选取信息增益的属性递归进行分类，C4.5改进为使用信息增益率来选取分类属性。CART是Classfication and Regression Tree的缩写。表明CART不仅可以进行分类，也可以进行回归。其中使用基尼系数选取分类属性。以下主要介绍ID3和CART算法。
ID3算法：
信息熵： H(X)=-sigma（对每一个x）（plogp） H(Y|X)=sigma(对每一个x)（pH(Y|X=xi)）
信息增益：H（D）-H(D|X) H(D)是整个数据集的熵
信息增益率：（H(D)-H(D|X)）/H(X)
算法流程：（1）对每一个属性计算信息增益，若信息增益小于阈值，则将该支置为叶节点，选择其中个数最多的类标签作为该类的类标签。否则，选择其中最大的作为分类属 性。
（2）若各个分支中都只含有同一类数据，则将这支置为叶子节点。
否则 继续进行（1）。
CART算法：
基尼系数：Gini（p）=sigma（每一个类）p(1-p)
回归树：属性值为连续实数。将整个输入空间划分为m块，每一块以其平均值作为输出。f(x)=sigma(每一块)Cm*I(x属于Rm)
回归树生成：（1）选取切分变量和切分点，将输入空间分为两份。
（2）每一份分别进行第一步，直到满足停止条件。
切分变量和切分点选取：对于每一个变量进行遍历，从中选择切分点。选择一个切分点满足分类均方误差最小。然后在选出所有变量中最小分类误差最小的变量作为切分 变量。
分类树：属性值为离散值。
分类树生成：（1）根据每一个属性的每一个取值，是否取该值将样本分成两类，计算基尼系数。选择基尼系数最小的特征和属性值，将样本分成两份。
（2）递归调用（1）直到无法分割。完成CART树生成。
决策树剪枝策略：
预剪枝（树提前停止生长）和后剪枝（完全生成以后减去一些子树提高预测准确率）
降低错误率剪枝：自下而上对每一个内部节点比较减去以其为叶节点和子树的准确率。如果减去准确率提高，则减去，依次类推知道准确率不在提高。
代价复杂度剪枝：从原始决策树T0开始生成一个子树序列{T0、T1、T2、...、Tn},其中Ti+1是从Ti总产生，Tn为根节点。每次均从Ti中 减去具有最小误差增长率的子树。然后通过 交叉验证比较序列中各子树的效果选择最优决策树。