ID3算法(Iterative Dichotomiser 3 迭代二叉树3代)，是一个由Ross Quinlan发明的用于决策树的算法；简单理论是越是小型的决策树越优于大的决策树。
算法归纳：
1、使用所有没有使用的属性并计算与之相关的样本熵值；
2、选取其中熵值最小的属性
3、生成包含该属性的节点
4、使用新的分支表继续前面步骤
ID3算法以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类；所以归根结底，是为了从一堆数据中生成决策树而采取的一种归纳方式；
具体介绍：
1、信息熵：熵的概念主要指信息的混乱程度，变量的不确定性越大，熵的值越大；
或者这样理解：假如事件A的全概率划分是(A1, A2, A3, … , An)，每部分发生的概率是(P1, P2, P3, … , Pn)，那么信息熵计算公式可如下表示
Info(A) = Entropy(p1, p2, … , pn) = -p1 * log2(p1) - p2 * log2(p2) - … - pn * log2(pn);
2、信息增益：信息增益指划分前后熵的变化；
或者这样理解：在某个案例中，类S的属性值A的信息增益 = 类的信息熵Info(S) - 该属性的信息熵Info(A);
3、一个案例中总会有一个类导向，也可以理解为结果，而产生结果统计来的信息可能会有多个相关属性，当我们使用一次信息增益计算，并在这多个属性的信息增益中得到了某个属性X的信息增益为最大值时，实际上也是选择了决策树中从根节点出发的第一层分支的依据；找到第一个分类节点后，如果这时X有三个分支x1，x2，x3，我们下一次的计算，其实就是把原表，根据X的三种情况分为了三张表，再重复计算信息增益，就可以得到整个决策树；
示例：http://www.cnblogs.com/zhangchaoyang/articles/2196631.html
优缺点：
优点：理论清晰，方法简单；
缺点：支队比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变；
我的理解：
整个计算其实并不复杂，有一点需要注意的是在一算整体表的某个属性A的熵时，如果A有三个取值，a1、a2、a3；A的熵其实 等于 a1出现的概率 乘 a1为独立表时该类的熵 加上 同理a2 加上 同理a3 这个计算的才是A的熵
相关：
奥卡姆剃刀：“切勿浪费较多东西，去做’用较少的东西，同样可以做好的事情’。”，即，如果同一个问题有许多种理论，每一种都能够做出同样准确的预言，那么应该挑选其中使用的嘉定最少的那一个。尽管越复杂的方法通常能做出越好的语言，但是在不考虑语言能力的情况下，前提假设越少越好。所罗门诺夫的归纳推理理论是奥卡姆剃刀的数学公式化：在所有能够完美描述已有观测的可计算理论中，较短的可计算理论在孤寂下一次观测结果的概率时具有较大权重。
课外：ID3也是一种metadata容器的简称，多用于MP3格式的音频文件中，他可以将相关的曲名、演唱者、转机、音轨数等信息存储在MP3文件中。ID3一般位于一个mp3文件的开头或末尾的若干字节内，附加了关于该mp3的歌手，标题，专辑名称，年代，风格等信息，该信息被称为ID3信息，ID3信息又分为两个版本。v1版的ID3在mp3文件的末尾128字节，以TAG三个字符开头，后面跟上个区信息。v2版一般位于mp3开头，可以存储歌词，该专辑的图片等大容量的信息；