浅谈C5.0与CART算法的较量–理论领略
###二、C5.0与CART的较量
####C5.0算法
1、C5.0是一种多叉树（即假如根节点或中间节点存在持续型的自变量，则该变量会一分为二的展开两个分支；假如根节点或中间节点存在离散的自变量，则该变量会按照离散变量的程度数分隔多个分支），就会导致某个变量一旦被利用，后头的节点将不会再启用该变量。
2、C5.0决定树的发展进程回收的是最大信息增益率原则举办节点选择和破裂点的选择，详细可从下方的理论中领略：
信息熵回响的是信息混乱水平，信息越混乱（越不纯），则信息熵越大；反之，信息熵越小。其数学公式为：
个中-log2(pj)回响的是信息量，即某随机事件产生的概率越小，则信息量越大；反之概率越大，则信息量越小。所以信息熵就是指事件产生的概率（pj）乘以其对应的信息量（-log2(pj)），然后再加总。
信息增益的计较为：
个中，Info为Y变量的信息熵，InfoA为自变量A对Y变量支解的信息熵，
接下来举个例子，也许你就可以或许大白。
Y变量为是否相亲，不妨我们计较学历这个变量对Y变量的支解信息增益值。
Y变量的信息熵：
学历对Y变量的支解信息熵：
学历对Y变量的支解信息增益：
在非叶节点的特征选择时，我们要求信息增益最大化，但思量信息增益最大化会带来一个问题，就是特征的选择会倾向于那些离散程度多的变量。譬喻两种极度环境：一种是ID变量（看成离散变量处理惩罚），该变量对Y变量的支解信息增益就便是Y变量的信息熵，到达最大；另一种是单一值变量，如国籍，该变量对Y变量的支解信息增益就便是0，到达最小，所以节点变量很大概会选择ID变量。但这样做其实是对那些程度较量少的离散变量的一种不公正处理惩罚。于是就提出了信息增益率的观念，即：
SI为支解信息，说白了就是计较自变量A的信息熵；信息增益率就是在信息增益的基本上除以自变量A的信息熵。仍然接着上面的学历例子：
学历变量的信息熵：
学历对Y变量的支解信息增益率：
通过这样的一个调动就可以办理信息增益存在的左袒漏洞。
3、剪枝回收“淘汰-误差”法和“淘汰-损失”法技能
“淘汰-误差”法：其焦点思想是比拟剪枝前后的误差率，假如剪枝后的误差率比剪枝前的误差率要低，则剪枝，不然不剪枝。关于误差率的计较：假如第i个节点中包括N个样本，个中预测错误的样本量为M，则该节点的错误率为f=M/N，按照正态漫衍假设，该视察错误率的置信区间为：
所以获得灰心的真实错误率为：
该剪枝要领所设定的默认alpha值为0.25，所以，alpha（置信程度）越小，则1-alpha（置信度）就越大，就越大概执行剪枝，使得真实错误率越小，模子的泛化本领越大。
“淘汰-损失”法：该要领团结损失矩阵对树举办剪枝，焦点思想是较量剪枝前后损失量，假如剪枝后的损失要小于剪枝前的损失，则剪枝，不然不剪枝。有关损失的计较如下：
个中，k为待剪子树中叶节点的个数，pi为第i个叶节点所含样本量占子树所含样本量的比例，ei为第i个叶节点的预计误差，oi为第i个叶节点的错判损失，e为父节点的预计误差，o为父节点的错判损失。
4、C5.0算法只能办理分类问题。
####CART算法
1、是一个二叉树，即每一个非叶节点只能引伸出两个分支，所以当某个非叶节点是多程度(2个以上)的离散变量时，该变量就有大概被多次利用。举个例子也许可以或许大白：假如年数段可分为{青年，中年，暮年}，则其子集可以是{青年，中年，暮年}、{青年，中年}、{青年，暮年}、{中年，暮年}、{青年}、{中年}、{暮年}、{}。个中{青年，中年，暮年}和空集{}为无意义的支解，所以最终有2^3-2=6种组合，形成3对对立的组合，如{青年，中年}与{暮年}可以分出两个分支。
2、CART决定树的发展进程回收的是最大基尼增益指数原则举办节点选择和破裂点的选择，详细可从下方的理论中领略：
对付分类问题
Y变量的基尼指数：
自变量A对Y变量的支解基尼增益指数：
我们仍然拿上面的相亲数据为例，计较学历的各个程度对Y变量的支解基尼增益指数：
Y变量的基尼指数：
{大专}与{本科、硕士}二叉树的基尼指数：
所以，大专与非大专的支解基尼增益指数为0.486-0.483=0.003。
{本科}与{大专、硕士}二叉树的基尼指数：
所以，本科与非本科的支解基尼增益指数为0.486-0.438=0.048。
{硕士}与{大专、本科}二叉树的基尼指数：
所以，硕士与非硕士的支解基尼增益指数为0.486-0.419=0.067。
对付回归问题
非叶结点的特征选择及支解点选择利用最小二乘毛病：
Y变量的最小二乘毛病：
个中，yi为实际的持续值，ri为预测的持续值；ri的是由某个叶节点中样本均值来权衡。
自变量A对Y变量的支解最小二乘毛病增益：
个中，beta为持续变量的某个支解点，基于这个支解点可以将数据分成两组。
3、剪枝回收“最小价钱巨大度”法和“损失矩阵”法技能
最小价钱巨大度说白了就是某其中间节点中往叶节点成长的进程中，其大错误率是否下降的明明，假如不明明，则剪枝，不然不减枝。详细数学公式如下：
举个例子也许你就大白了：
上图回响了一个简朴的树，根节点有100个样本，两其中间节点T1，T2和4个叶节点。则中间节点T1，T2误差率增益值α别离为：
可通过配置一个阈值，当误差率增益值α低于阈值时可以思量剪枝。
损失矩阵的思想与C5.0的雷同，这里就不在赘述。
4、CART算法既可以办理分类问题（Y变量为离散变量），也可以或许很好的处理惩罚预测问题（Y变量为持续变量）。
关于两个算法的理论较量我们本日就讲到这里，主要是从算法的几叉树？如何选择节点特征、支解点？树的剪枝技能？和各自办理的问题做了梳理。在下一期我们将针对这两个算法如何通过R语言实现落地，并通过案例完成两个算法的较劲。
####天天进步一点点2015
####进修与分享，取长补短，存眷小号！
####长按识别二维码 顿时存眷
网作者：刘顺祥
数据阐明师，热爱数据阐明与挖掘事情，擅长利用Ｒ语言，今朝自学Python语言。
