ID3算法是1986年由Quilan提出的，它是一个从上到下、分而治之的归纳过程。ID3算法的核心是：在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。
有关信息增益的定义以及具体的计算方法和实例，可以参考马瑜和王有刚的论文《ID3算法应用研究》的第1、2两节。
ID3算法思想描述如下：
(1)初始化决策树T为只含一个树根(X,Q)，其中X是全体样本集，Q为全体属性集。
(2)if(T中所有叶节点(X’,Q’)都满足X属于同一类或Q’为空)then算法停止；
(3)else
{任取一个不具有(2)中所述状态的叶节点(X’,Q’)；
(4)foreachQ’中的属性Ado计算信息增益gain(A,X’)；
(5)选择具有最高信息增益的属性B作为节点(X’,Q’)的测试属性；
(6)foreachB的取值bido
{从该节点(X’,Q’)伸出分支，代表测试输出B=bi；
求得X中B值等于bi的子集Xi，并生成相应的叶节点(Xi’,Q’-{B})；}
(7)转(2)；}
ID3算法是决策树的一个经典的构造算法，在一段时期内曾是同类研究工作的比较对象，但通过近些年国内外学者的研究，ID3算法也暴露出一些问题，具体如下：
(1)信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属性并不一定最优。
(2)ID3是非递增算法。
(3)ID3是单变量决策树(在分枝节点上只考虑单个属性)，许多复杂概念的表达困难，属性相互关系强调不够，容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次。
(4)抗噪性差，训练例子中正例和反例的比例较难控制。
决策树的经典构造算法（二）——C4.5
由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；有关信息增益率的定义可以参考栾丽华和吉根林的论文《决策树分类技术研究》1.2节。
2)在树构造过程中进行剪枝；
3)能够完成对连续属性的离散化处理；
4)能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。