设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci（i＝1，2，…，m），ci是类Ci中的样本数，是任意样本属于Ci的概率。

假设属性A具有v个不同值｛a1，a2，…，av｝，可以用属性A将S划分为v个子集｛S1，S2，…Sv｝，其中Sj（j＝1，2，…，v）中的样本在属性A上具有相同的值aj，sj为子集Sj的样本数，sij是子集Sj中类Ci的样本数，即属性A将S分成m×v个子集，每个子集所含的样本个数为sij，是Sj中样本属于类Ci的概率。则

为属性A的一个划分矩阵。且

引入几个概念。

（1）个体类信息量：

（2）信息期望或熵：(www.daowen.com)

（3）属性A将集合S分裂后（划分成子集）信息期望或熵：

这里

（4）属性A将集合S分裂后获得的信息增益

ID3算法的核心是：在决策树各级结点上选择属性时，用信息增益（Gain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：假设具有p个属性，即属性集为A＝｛A1，A2，…，Ap｝。检测所有的属性，选择信息增益最大的属性产生决策树结点，取使Grain（Ak，S）（k＝1，2，…，p）中最大的Ap，由Ak属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到的一棵决策树，它可以用来对新的样本进行分类。

ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：只对比较小的数据集有效且对噪声比较敏感，由于每次产生决策树结点时都要对备选属性的信息增益进行计算并判断信息增益最大的属性，所以运算量大。当训练数据集加大时，决策树可能会随之改变。