这个实验的主要目标是构建一个决策树。
决策树，实际上是用来分类的。树，体现了这个数据结构是逐层分叉的。那么怎么找到分叉点呢？
ID3 算法
在谈ID3算法前，首先介绍一下熵的概念。
训练元组D有若干个属性，每个属性有一些值。则D的信息熵(entropy)表示为
$$ info(D) = - \sum_{i-1}^{m} p_i \log_2 (p_i) $$
其中$p_i$表示第i个类别在整个训练元组中出现的概率，可以用此类别元素的数量除以训练元组总数量作为估计。熵的实际意义表示的是D中元组的类标号所需要的平均信息量。现在我们假设将训练元组按属性A进行划分，则A对D划分的期望信息为：
$$info_A(D)=\sum_{j=1}^v \frac{D_j} {D}info(D_j)$$
而信息增益即为两者的差值：
$$gain(A)=info(D)-info_A(D)$$
ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。
对于特征属性为连续值，可以将D中的元素按照特征属性排序，则每两个相邻元素的中间点可以看作潜在分裂点，从第一个潜在分裂点开始，分裂D并计算两个集合的期望信息，选择具有最小期望信息的点作为这个属性的最佳分裂点，此期望信息作为此属性的信息期望。
施工中ing