利用id3算法建立决策树（基于ID3决策树算法的理解）
利用id3算法建立决策树（基于ID3决策树算法的理解）小白曾在信息的度量"熵"和香农定理一文中提到"熵"的概念，熵可用来衡量一个随机系统确定性。试想，我们在预测和判断一个事件（是否健身）会出现的时候，其本质其实就是在试图得到这个事件所关联的随机系统的确定性的度量。这个度量就是"熵"，熵为0，说明事件完全确定，我们就能准确的判断和预测。可以比喻成有一把尺子度量随机系统的熵，而"周ｘ维度"和"上/下午"维度就是尺子。另外，小白理解，在度量时，不管谁先谁后都可以得到相同的度量结果。但是，如果把度量结果大的尺子首先度量，那么度量的工作量就会增大。或者这样理解，随机系统的一部分确定性如果通过一把尺子度量后得到了确认，那么就不需要第二把尺子再测量了。因此，如果一部分确认性本可以通过尺子A度量得到确认，但现在却先通过尺子B度量，但B不能完全确认，就需要A再次度量，这就导致了重复的工作了。图4图2图3这里有一个问题，如果用上午/下午维度作为根结点难道不可以吗
引出话题我们知道决策树算法是一种机器学习算法。机器学习近年来甚是火热，小白以为机器学习关键在"学习"二字，学习是人区别于其他生物的核心特征。那么学习的本质是什么？小白理解，学习有两个前提：一是，宇宙是一整体，它投影在时空维度里的万事万物互相关联，可以说任何事物都有关联和联系；二是，人作为其中一个系统，通过感官，工具获取消息和数据并通过逻辑梳理消化数据，形成人的知识系统（这个知识系统就是信息，就是万物的关联和联系），进而指导人的行为。小白理解，机器学习，就是人通过计算机输入数据，根据逻辑（即算法）把数据转换为知识系统，这个知识系统通过学习不断迭代完善，进而更好指导机器的行为，因此也就实现了机器智能的目的。
进一步思考，以上第二个前提有两个关键点，第一个是数据，第二个是算法。本篇的标题"决策树"就是这里的算法。另外，小白理解数据和算法是对应的。比如，对待图片，音乐等数据，人通常以艺术的算法加以处理；对待商品交易，金融数据，人通常以逻辑数学的算法加以处理。因此，再描述决策树算法之前，先对决策树算法所分析和处理的对象，即数据，进行一些思考和理解。
第十七篇 数据的本质形态－维度阅读过小白关于随机世界系列小文章的朋友们应该知道，小白反复诉说着一个臆想的观点，这个宇宙的本质是一个随机系统。我们人所感知的世界是时空世界，即时间和空间四个维度。时空中的一切事物是随机系统在时空世界的投影，准确的说是人在时空的维度下对随机系统的采样。因此，万事万物都是样本，甚至时空本身也是样本。数据是人类对这些样本进行描述的符号，也可以说，数据就是样本。
决策树把维度作为结点形成一棵树，这棵树从根结点到叶子结点的每条路径可以理解为一条决策的步骤路径，也可以理解成对随机空间的分割路径（通过属性值进行分割，形成子结点）。举个例子，假如一个健身房对A过去30天去健身的情况进行统计，发现A去了12次。想预测今天A还来健身吗？首先健身房对A的统计按照周日进行分割，然后，再按照上午下午进行分割，就得到了图2（黑点表示A去了健身房）。同时，图3是对应的决策树。
图2
图3
这里有一个问题，如果用上午/下午维度作为根结点难道不可以吗？当然可以，如图4。但我们发现，如果选用上/下午维度做根结点的话，那么决策树的路径多了，叶子结点多了。直观上看，图2似乎更优。如何理解这里的更优，难道"上午/下午无维度"和"周x维度"有何不同吗？好了下面咱们开始进入ID3算法的理解。
图4
ID3算法小白曾在信息的度量"熵"和香农定理一文中提到"熵"的概念，熵可用来衡量一个随机系统确定性。试想，我们在预测和判断一个事件（是否健身）会出现的时候，其本质其实就是在试图得到这个事件所关联的随机系统的确定性的度量。这个度量就是"熵"，熵为0，说明事件完全确定，我们就能准确的判断和预测。可以比喻成有一把尺子度量随机系统的熵，而"周ｘ维度"和"上/下午"维度就是尺子。另外，小白理解，在度量时，不管谁先谁后都可以得到相同的度量结果。但是，如果把度量结果大的尺子首先度量，那么度量的工作量就会增大。或者这样理解，随机系统的一部分确定性如果通过一把尺子度量后得到了确认，那么就不需要第二把尺子再测量了。因此，如果一部分确认性本可以通过尺子A度量得到确认，但现在却先通过尺子B度量，但B不能完全确认，就需要A再次度量，这就导致了重复的工作了。
这里的尺子度量的是不确定性，度量的结果是熵，熵越小说明被度量的系统越确定。小白这样理解，被度量的随机系统有一个总的熵，被尺子度量后，和尺子相关的那些不确定性因素就变成确定的了，和尺子不相关的那些不确性因素就成为了尺子度量得到的熵。或者说这把尺子的信息量很大，从ID3算法的角度看，这里的信息量就是"互信息"的概念。也就是说，我们应该先用"互信息"最大的尺子先度量，形成父决策结点，然后通过父决策节点的属性值将样本空间进行分割；接着再分别计算各分割后的子空间中"互信息"量最大的维度作为父节点，然后迭代继续分割计算。
回到我们的决策树，我们也可以说，根结点和中间结点就是"尺子"，结点的父子关系表示父尺子先于子尺子进行测量，最后我们得到叶子结点，即得到我们想要的确定性度量。想到这里，小白豁然开朗，我们可以通过计算各个维度下随机系统的熵，然后再比较这些熵的大小。熵小的作为父结点，熵大的作为子结点，这样不断的计算，形成一个"尺子树"，这个尺子树就是决策树。这个计算并形成"尺子树"的过程就是ID3算法。
阅读关于ID3算法的一些资料，我们发现，有熵，条件熵和互信息 几个概念。其实这里的条件熵就是刚才谈到尺子度量的熵，尺子就是条件。而互信息的计算方法是"互信息＝熵－条件熵"。互信息表示两个维度的相关性，互信息越大，说明两者相关性越大。这一点很容易理解。从公式可看出，互信息越大，条件熵越小，条件熵越小说事件越确定。事件越确定说明被度量的事件（维度）和度量的尺子（维度）是紧密相关的，也就是相关性。
决策有了决策树，我们就可以决策了。把数据和决策树进行比对，就能得到决策的结果。这个行为体现了智能。但小白理解，事物的关联是客观存在的，智能仅是学以致用而已。
