机器学习算法之决策树
rushuang3818
8年前
<h2><strong>前言</strong></h2> <p>决策树是一种简单高效并且具有强解释性的模型，广泛应用于数据分析领域。其本质是一颗由多个判断节点组成的树，如：</p> <p><img src="https://simg.open-open.com/show/57827ac7dece3c8f4102d7e39804fc5a.png"></p> <p>决策树</p> <p>在使用模型进行预测时，根据输入参数依次在各个判断节点进行判断游走，最后到叶子节点即为预测结果。</p> <h2><strong>如何构造决策树</strong></h2> <p>决策树算法的核心是通过对数据的学习，选定判断节点，构造一颗合适的决策树。</p> <p>假设我们从用户行为日志中整理出如下数据：</p> <p><img src="https://simg.open-open.com/show/081d022b5dceba8e3a09e9943716a76b.png"></p> <p style="text-align:center">原始数据</p> <p>我们的目的是要利用这些数据，训练决策树模型，模型训练好后，我们就可以通过任意给定的用户来源网站、位置、是否阅读过 FAQ、浏览网页数信息，预测该用户是否会进行付费以及付费类型，供运营使用。</p> <h3><strong>选择合适的拆分条件</strong></h3> <p>我们知道决策树是由一个个判断节点组成，每经过一个判断节点数据就会被拆分一次。上面数据中有4种属性，每种属性下面有多种值，我们可以按位置是否来自「浙江」进行拆分，拆分结果为：</p> <p><img src="https://simg.open-open.com/show/23842e1e9fdf8464a58ae13ed5ed7e4a.png"></p> <p style="text-align:center">按是否来自「浙江」拆分结果</p> <p>我们「拍脑袋」进行了一次拆分，到底这么拆分合不合适，是不是最佳，我们需要量化指标来进行评价，在决策树算法中，我们通过 <strong>基尼不纯度</strong> 或者 <strong>熵</strong> 来对一个集合进行的有序程度进行量化，然后引入 <strong>信息增益</strong> 概念对一次拆分进行量化评价。下面依次介绍。</p> <p><strong>基尼不纯度</strong></p> <p>基尼不纯度是指将来自集合中的某种结果随机应用于集合中某一数据项的预期误差率。如何集合中的每一个数据项都属于同一分类，那么推测的结果总会是正确的，因此误差率是 0；如果有 4 种可能的结果均匀分布在集合内，出错可能性是75%，基尼不纯度为 0.75。该值越高，说明拆分的越不理想，如果该值为 0，说明完美拆分。java 实现代码如下：</p> <pre> <code class="language-java">public static float getCiniimpurity(String[] rows){ float total = rows.length; //将[a,a,b,c]转化成[2,1,1] Integer[] uniqueRows = getUniqueRows(rows); float score = 0.0f; for(int k1=0;k1<uniqueRows.length;k1++){ float p1 = uniqueRows[k1]/total; for(int k2=0;k2<uniqueRows.length;k2++){ if(k2 == k1) continue; float p2 = uniqueRows[k2]/total; score += p1 * p2; } } return score; }</code></pre> <p><strong>熵</strong></p> <p>熵是信息论中的概念，用来表示集合的无序程度，熵越大表示集合越混乱，反之则表示集合越有序。熵的计算公式为：</p> <p>E = -P * log <sub>2</sub> P</p> <p>java 代码实现如下：</p> <pre> <code class="language-java">public static double getEntropy(String[] rows){ float total = rows.length; //将[a,a,b,c]转化成[2,1,1] Integer[] uniqueRows = getUniqueRows(rows); double ent = 0.0; for(int i=0;i<uniqueRows.length;i++){ float p = uniqueRows[i]/total; ent = ent - p * (Math.log(p)/Math.log(2)); } return ent; }</code></pre> <p><strong>基尼不纯度与熵对比</strong></p> <p>两者主要区别在于，熵到达峰值的过程相对慢一些。因此熵对混乱集合的「判罚」往往更重一些。通常情况下，熵的使用更加频繁。</p> <p><strong>信息增益</strong></p> <p>假设集合 U，一次拆分后变为了两个集合 u <sub>1</sub> 和 u <sub>2</sub> ，则有：</p> <p>信息增益 = E(U) - (P <sub>u1</sub> x E(u <sub>1</sub> ) + P <sub>u2</sub> x E(u <sub>2</sub> ))</p> <p>E 可以是基尼不纯度或熵。</p> <p>使用 P <sub>u1</sub> 和 P <sub>u2</sub> 是为了得到拆分后两个集合基尼不纯度或熵的加权平均，其中 :</p> <ul> <li>P <sub>u1</sub> = Size(u1) / Size(U)</li> <li>P <sub>u2</sub> = Size(u2) / Size(U)</li> </ul> <p>信息增益越大，说明整个集合从无序到有序的速度越快，本次拆分越有效。</p> <h3><strong>构造决策树</strong></h3> <p>我们已经可以通过信息增益量化一次拆分的结果好坏，下一步就是构造决策树，主要步骤如下：</p> <ol> <li>遍历每个决策条件（如：位置、来源网站），对结果集进行拆分</li> <li>计算该决策条件下，所有可能的拆分情况的信息增益，信息增益最大的拆分为本次最优拆分</li> <li>递归执行1、2两步，直至信息增益<=0</li> </ol> <p>执行完上述步骤后，就构造出了一颗决策树，如图：</p> <p><img src="https://simg.open-open.com/show/837c3459385a011f5da7196e0f77c3ab.png"></p> <p>决策树</p> <h3><strong>决策树剪枝</strong></h3> <p>为什么要剪枝</p> <p>训练出得决策树存在过度拟合现象——决策树过于针对训练的数据，专门针对训练集创建出来的分支，其熵值可能会比真实情况有所降低。</p> <p>如何剪枝</p> <p>人工设置一个信息增益的阀值，自下而上遍历决策树，将信息增益低于该阀值的拆分进行合并</p> <h3><strong>处理缺失数据</strong></h3> <p>决策树模型还有一个很大的优势，就是可以容忍缺失数据。如果决策树中某个条件缺失，可以按一定的权重分配继续往以后的分支走，最终的结果可能有多个，每个结果又一定的概率，即：</p> <p>最终结果=某个分支的结果 x 该分支的权重(该分支下的结果数/总结果数)</p> <h3><strong>处理数值型数据</strong></h3> <p>决策树主要解决分类问题（结果是离散数据），如果结果是数字，不会考虑这样的事实：有些数字相差很近，有些数字相差很远。为了解决这个问题，可以用方差来代替熵或基尼不纯度。</p> <h2><strong>结语</strong></h2> <p>本文简单介绍了决策树算法，该算法虽然简单，但是在很多场景能取得非常好的效果，值得读者一试。另外，从决策树发展出了更为高级复杂的 <strong>随机森林</strong> ，如果有兴趣读者可以去深入了解。</p> <p> </p> <p>来自：http://www.jianshu.com/p/6eecdeee5012</p> <p> </p>