一组含n个实例的数据集,每一个实例长为m,其中包括m-1个特征(属性),最后一个为该特征的类别标签。
在此种数据集的基础上,有一棵树,这棵树上的非叶子节点均为某特征,叶子节点均为其父节点特征的特征值。
那么这棵树是怎么来的?
我们 1.首先要在当前数据集中找到最适合分组的一个特征,2. 然后根据这个特征值的不同将数据分为几组,3.接着在分组完成后的子数据集中,判断当前实例的是否都属于同一类,若是,则结束,若不是,那么在当前数据集中从第一步循环。4.数据集的所有特征都遍历完了,结束。
容易知道建树时会用到递归,递归结束的两种情况:1.所有分支下的叶子节点均有同一标签 2.数据集的所有特征都遍历完了。
其中,寻找划分数据集的最好特征
为了确定哪一个特征是划分数据的最好特征,我们需要判断用哪个特征划分后的子数据集信息增益最高,也就是说划分后更加有序了,划分后的子数据集越有序,越说明我们用这个特征划分是合理的。
因此,我们要对当前数据集中的每个特征计算依据其划分后的信息增益。
1.取数据集的前m-1列,每列为一个特征下的一组值,去重后长为N,
2.依据此N个特征值将数据分为N组,计算每一组的熵,并对该N组的熵求和,
3.将2所得结果与划分前初始数据的熵比较得出信息增益,
4.对m-1个特征下的一组值均作以上操作,
5.最后求m-1个特征中信息增益最高的,此时特征变为当前的最好划分特征。
网友评论