这个实验的主要目标是构建一个决策树。

决策树,实际上是用来分类的。树,体现了这个数据结构是逐层分叉的。那么怎么找到分叉点呢?

ID3 算法

在谈ID3算法前,首先介绍一下熵的概念。

训练元组D有若干个属性,每个属性有一些值。则D的信息熵(entropy)表示为

$$ info(D) = - \sum_{i-1}^{m} p_i \log_2 (p_i) $$

其中$p_i$表示第i个类别在整个训练元组中出现的概率,可以用此类别元素的数量除以训练元组总数量作为估计。熵的实际意义表示的是D中元组的类标号所需要的平均信息量。现在我们假设将训练元组按属性A进行划分,则A对D划分的期望信息为:

$$infoA(D)=\sum{j=1}^v \frac{D_j} {D}info(D_j)$$

而信息增益即为两者的差值:

$$gain(A)=info(D)-info_A(D)$$

ID3算法就是在每次需要分裂时,计算每个属性的增益率,然后选择增益率最大的属性进行分裂。

对于特征属性为连续值,可以将D中的元素按照特征属性排序,则每两个相邻元素的中间点可以看作潜在分裂点,从第一个潜在分裂点开始,分裂D并计算两个集合的期望信息,选择具有最小期望信息的点作为这个属性的最佳分裂点,此期望信息作为此属性的信息期望。

施工中ing