机器学习算法之决策树

1、机器学习算法之决策树4一刖s决策树是一种简单高效并且具有强解释性的模型，广泛应用于数据分析领 域。其本质是一颗曲多个判断节点组成的树，如：满足条件a?满足条件b?结果a结果c结果d在使用模型进行预测吋，根据输入参数依次在各个判断节点进行判断游走， 最后到叶子节点即为预测结果。如何构造决策树决策树算法的核心是通过对数据的学习，选定判断节点，构造一颗合适的决 策树。假设我们从用户行为日志中整理出如下数据:来源网站；位置阅读过faq |浏览网页数付费类型百度西安yes18none谷歌上海no23premium叟浙江yes24basic匚百度二浙江no11nonel谷歌_西安no18basic匚搜狗二

2、上海yes22none百度西安no12none浙江no19basic搜狗；西安no20none匚谷歌口西安yes16none我们的目的是要利用这些数据，训练决策树模型，模型训练好后，我们就可 以通过任意给定的用户來源网站、位置、是否阅读过faq、浏览网页数信息，预 测该用户是否会进行付费以及付费类型，供运营使用。选择合适的拆分条件我们知道决策树是由一个个判断节点组成，每经过一个判断节点数据就会被 拆分一次。上而数据中冇4种屈性，每种屈性下而有多种值，我们可以按位置是 否来自浙江进行拆分，拆分结果为：来自浙江其他地方basicnonenonepremiumbasicbasicnonenoneno

3、nenone我们拍脑袋进行了一次拆分，到底这么拆分合不合适，是不是最佳，我 们需要量化指标來进行评价，在决策树算法中，我们通过基尼不纯度或者爛來对一个集合进行的有序程度进行量化，然后引入信息增益概念对一次拆分进行量化 评价。下而依次介绍。基尼不纯度基尼不纯度是指将来自集合屮的某种结果随机应用于集合屮某一数据项的 预期误差率。如何集合中的每一个数据项都属于同一分类，那么推测的结果总会 是止确的，因此误羌率是0;如杲有4种可能的结杲均匀分布在集合内，出错可 能性是75%,基尼不纯度为0.75。该值越高，说明拆分的越不理想，如果该值 为0,说明完美拆分。java实现代码如下：public stati

4、c float getcini impurity(string rows) float total 二 rows, length;/将a, a, b, c转化成2, 1, 1integer uniquerows = getuniquerows (rows); float score = 0. of;for(int kl=o;kl<uniquerows. length;kl+) float pl 二 uniquerowskl/total;for (int k2=0;k2<uniqucrows. length;k2+)if(k2 =float p2score +二 kl) contin

5、ue;二 uniquerowsk2/total; pl * p2;1jreturn score;爛是信息论中的概念，用來表示集合的无序程度，爛越大表示集合越混乱, 反z则表示集合越有序。爛的计算公式为：e 二-p * log2pjava代码实现如下：public static double getentropy(string rows)float total 二 rows, length; /将a, a, b, c转化成2, 1, 1integer uniquerows = getuniquerows(rows);double ent = 0. 0;for(int i=0;i<uniqu

6、erows. length;i+) float p 二 uniquerowsi/total;ent = ent - p * (math, log (p)/math, log (2);基尼不纯度与炳对比两者主要区别在于，爛到达峰值的过程相对慢一些。因此爛对混乱集合的判 罚往往更重一些。通常情况下，爛的使用更加频繁。信息增益假设集合u, 一次拆分后变为了两个集合u1和u2 ,则有：信息增益=e(u) - (pul x e(ul) + pu2 x e(u2)e可以是基尼不纯度或爛。使用pul和pu2是为了得到拆分后两个集合基尼不纯度或爛的加权平均， 其屮：pul = size(ul) / size(

7、u)pu2 = size(u2) / size(u)信息增益越大，说明整个集合从无序到有序的速度越快，木次拆分越有效。构造决策树我们已经可以通过信息增益量化一次拆分的结果好坏，下一步就是构造决策 树，主要步骤如下：遍丿力每个决策条件(如：位置、來源网站)，对结果集进行拆分计算该决策条件下，所有可能的拆分情况的信息增益，信息增益最大的拆分 为本次最优拆分递归执行1、2两步，直至信息增益二0执行完上述步骤后，就构造岀了一颗决策树，如图:浏网页数x23来自谷歌?true/true/falsebasic: 1premium: 1basic:2none:1决策树剪枝为什么要剪枝训练出得决策树存在过度拟合现象决策树过于针对训练的数据，专门针 对训练集创建出來的分支，其爛值可能会比真实情况有所降低。如何剪枝人工设置一个信息增益的阀值，自下而上遍丿力决策树，将信息增益低于该阀 值的拆分进行合并处理缺失数据决策树模型还有一个很大的优势，就是町以容忍缺失数据。如果决策树中某 个条件缺失，可以按一定的权重分配继续往以后的分支走，最终的结果可能有多 个，每个结果乂一定的概率，w：最终结果二某个分支的结果x该分支的权重（该分支下的结果数/总结果数）处理数值型数据决策树主要解决分类问题（结果是离散数据），如果结果是数字，不会考虑这 样的事实：有些数字相差很