<p style="text-align: center;"><img src="https://simg.open-open.com/show/b170edc5955f03200739b701ae19d195.png"></p>    <p> </p>    <h3>1. 决策树是什么?</h3>    <p>简单地理解，就是根据一些 feature 进行分类，每个节点提一个问题，通过判断，将数据分为几类，再继续提问。这些问题是根据已有数据学习出来的，再投入新数据的时候，就可以根据这棵树上的问题，将数据划分到合适的叶子上。</p>    <p><img src="https://simg.open-open.com/show/3edf669ee74e5603f3bcee31bdec1e85.png"></p>    <h3>2. 决策树有什么算法?</h3>    <p>常用的几种决策树算法有ID3、C4.5、CART：</p>    <p>ID3：选择信息熵增益最大的feature作为node，实现对数据的归纳分类。</p>    <p>C4.5：是ID3的一个改进，比ID3准确率高且快，可以处理连续值和有缺失值的feature。</p>    <p>CART：使用基尼指数的划分准则，通过在每个步骤最大限度降低不纯洁度，CART能够处理孤立点以及能够对空缺值进行处理。</p>    <h3>3. 数学原理?</h3>    <p>ID3: Iterative Dichotomiser 3</p>    <p><a href="/misc/goto?guid=4959726600730955008" rel="nofollow,noindex">参考</a></p>    <p><img src="https://simg.open-open.com/show/8c4e9fd057f7eca23cfc864396ecc338.png"></p>    <p>下面这个数据集，可以同时被上面两颗树表示，结果是一样的，而我们更倾向于选择简单的树。</p>    <p>那么怎样做才能使得学习到的树是最简单的呢?</p>    <p><img src="https://simg.open-open.com/show/8459fecff08dd088b86453a1a1a7f002.png"></p>    <p>下面是 ID3( Iterative Dichotomiser 3 )的算法：</p>    <p><img src="https://simg.open-open.com/show/eac15bcb0efa6ee6f8a1549280466c58.png"></p>    <p>例如下面数据集，哪个是最好的 Attribute?</p>    <p><img src="https://simg.open-open.com/show/d57b347a1f1c1b452f913b71039e8c5b.png"></p>    <p>用熵Entropy来衡量：</p>    <p>E(S) 是数据集S的熵</p>    <p>i 指每个结果，即 No，Yes的概率</p>    <p><img src="https://simg.open-open.com/show/4365615836224836c34abbe37c10e285.png"></p>    <p>E越大意味着信息越混乱，我们的目标是要让E最小。</p>    <p>E在0-1之间，如果P+的概率在0.5， 此时E最大，这时候说明信息对我们没有明确的意义，对分类没有帮助。</p>    <p><img src="https://simg.open-open.com/show/13ce18f78c51d44e02818699f1e373b7.png"></p>    <p>但是我们不仅仅想要变量的E最小，还想要这棵树是 well organized。</p>    <p>所以用到 Gain：信息增益</p>    <p><img src="https://simg.open-open.com/show/fdbc49449d72690d530d537f153ff5c9.png"></p>    <p>意思是如果我后面要用这个变量的话，它的E会减少多少。</p>    <p><img src="https://simg.open-open.com/show/67b7db57d8477dc9c81b44cc16fbdaa0.png"></p>    <p>例如下面的数据集：</p>    <p><img src="https://simg.open-open.com/show/779309e0c0ff4705648ecc21d5084479.png"></p>    <p>先计算四个feature的熵E，及其分支的熵，然后用Gain的公式计算信息增益。</p>    <p><img src="https://simg.open-open.com/show/26cd95750a124cd4b355c39d7a8ddbcb.png"></p>    <p>再选择Gain最大的特征是 outlook。</p>    <p>第一层选择出来后，各个分支再继续选择下一层，计算Gain最大的，例如分支 sunny 的下一层节点是 humidity。</p>    <p><img src="https://simg.open-open.com/show/7ef2ddba1bcb56356e0911f6391ce418.png"></p>    <p>详细的计算步骤可以参考这篇博文 <a href="/misc/goto?guid=4959726600822113829" rel="nofollow,noindex">分类算法——决策树</a> 。</p>    <p>C4.5</p>    <p><a href="/misc/goto?guid=4959726600905056008" rel="nofollow,noindex">参考</a></p>    <p>ID3有个局限是对于有大量数据的feature过于敏感，C4.5是它的一个改进，通过选择最大的信息增益率 gain ratio 来选择节点。而且它可以处理连续的和有缺失值的数据。</p>    <p><img src="https://simg.open-open.com/show/5f10c49d443b21f9a720a81bb8b5c20f.png"></p>    <p>例如 outlook 作为第一层节点后，它有 3 个分支，分别有 5，4，5 条数据，则 SplitInfo(5,4,5) = -5/14log(5,14)-4/14log(4,14)-5/14(5,14) ，其中 log(5,14) 即为 log2(5/14)。</p>    <p>下面是一个有连续值和缺失值的例子：</p>    <p><img src="https://simg.open-open.com/show/8abfec9b2c36ff1fa64a9ecae33108d0.png"></p>    <p>连续值</p>    <p>第一步计算 Gain，除了连续值的 humudity，其他步骤和前文一样。</p>    <p>要计算 humudity 的 Gain 的话，先把所有值升序排列：</p>    <p>{65, 70, 70, 70, 75, 78, 80, 80, 80, 85, 90, 90, 95, 96}</p>    <p>然后把重复的去掉：</p>    <p>{65, 70, 75, 78, 80, 85, 90, 95, 96}</p>    <p>如下图所示，按区间计算 Gain，然后选择最大的 Gain (S, Humidity) = 0.102</p>    <p><img src="https://simg.open-open.com/show/39fbdc189b8862cbfb7a6fa9b8b13dfb.png"></p>    <p>因为 Gain(S, Outlook) = 0 .246，所以root还是outlook：</p>    <p><img src="https://simg.open-open.com/show/ed79a10b67763da0f373010d69f259de.png"></p>    <p>缺失值</p>    <p>处理有缺失值的数据时候，用下图的公式：</p>    <p><img src="https://simg.open-open.com/show/6e5975c5735fdb4d570c3230427a753a.png"></p>    <p>例如 D12 是不知道的。</p>    <p>计算全集和 outlook 的 info，</p>    <p><img src="https://simg.open-open.com/show/a0907235eb740dca483bfaf3b049b14c.png"></p>    <p>其中几个分支的熵如下，再计算出 outlook 的 Gain：</p>    <p><img src="https://simg.open-open.com/show/dc2bb341ad42f9bbbef2ff643840f3d2.png"></p>    <p>比较一下 ID3 和 C4.5 的准确率和时间：</p>    <p>accuracy ：</p>    <p><img src="https://simg.open-open.com/show/a23ded3cbaae81abd22cbaccbc2b4824.png"></p>    <p>execution time：</p>    <p><img src="https://simg.open-open.com/show/a50d8e538726bd18beff0a844a28b9fb.png"></p>    <h3>4. 编码实现算法?</h3>    <p>代码可以看《机器学习实战》这本书和这篇博客 <a href="/misc/goto?guid=4959726600994605190" rel="nofollow,noindex">Python实现C4.5</a> 。</p>    <p>完整代码可以在 <a href="/misc/goto?guid=4959726601077525568" rel="nofollow,noindex">github</a> 上查看。</p>    <p>接下来以 C4.5 的代码为例：</p>    <p>1. 定义数据：</p>    <p><img src="https://simg.open-open.com/show/3664e409889aa7070903d325506e4b81.png"></p>    <p>2. 计算熵：</p>    <p><img src="https://simg.open-open.com/show/a3f79507c5e83729331f09f94be43587.png"></p>    <p>3. 选择最大的gain ratio对应的feature：</p>    <p><img src="https://simg.open-open.com/show/bec83704d7864f9fd331bdff65171fe8.png"></p>    <p>4. 划分数据，为下一层计算准备:</p>    <p><img src="https://simg.open-open.com/show/22bf4e138b322003ec23e184a8753fa6.png"></p>    <p>5. 多重字典构建树：</p>    <p><img src="https://simg.open-open.com/show/a2bd30b842bece90bac1952c715ce443.png"></p>    <p>6. 可视化决策树的结果:</p>    <p><img src="https://simg.open-open.com/show/56f43b9cf0fd1d14bbf72d72cc744644.png"></p>    <p>End.</p>    <p> </p>    <p>来自：http://www.36dsj.com/archives/69663</p>    <p> </p>