一、决策树是什么
决策树(decision tree)是一种基本的分类与回归方法。在分类问题中,它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。在学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型;在预测时,对新的数据,利用决策树模型进行分类。
决策树学习主要包括三个步骤:特征选择、决策树生成和决策树的修剪。
二、决策树模型
圆代表内部结点也就是特征/属性,而矩形则代表叶结点也就是具体的类别。
三、特征选择
通常特征选择的准则是信息增益或信息增益比,要记住下面的概念与公式:
熵(entropy):是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量,其概率分布为
则随机变量X的熵定义为
在上式中的对数通常以2为底或以e为底又或者以10为底,这时熵的单位分别是bit,nat,hart.
熵越大,不确定性就越大。
依据琴生不等式推出熵的范围为:[0,logn]。
条件熵(conditional entropy)
H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。定义为X给定条件下随机变量Y的条件概率分布的熵对X的数学期望:
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵和条件熵分别成为经验熵和经验条件熵。
信息增益(information gain)
表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。 定义:特征A对训练数据集D的信息增益g(D,A),定义集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:
一般地,熵与条件熵之差成为互信息(mutual information),决策树学习中的信息增益等价于训练数据集中类与特征的互信息。 根据信息增益准则的特征选择方法是:对训练数据集(或子集)D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。
信息增益比(information gain ratio)
信息增益的大小是相对于训练数据集而言的,并没有绝对意义。在训练数据集的经验熵大的时候,信息增益值会偏大。反之,信息增益值会偏小。使用信息增益比可以对这一问题进行校正。 定义:特征A对训练数据集D的信息增益比gR(D,A)定义为信息增益g(D,A)与训练集D的经验熵H(D)之比:
四、决策树生成-ID3算法
ID3算法依据信息增益来自顶向下建立决策树。
假设有以下数据:
上面的训练集有4个属性,即属性集合A={OUTLOOK, TEMPERATURE, HUMIDITY, WINDY};而类标签有2个,即类标签集合C={Yes, No},分别表示适合户外运动和不适合户外运动,其实是一个二分类问题。 数据集D包含14个训练样本,其中属于类别“Yes”的有9个,属于类别“No”的有5个,则计算其信息熵:
Info(D) = -9/14 * log2(9/14) - 5/14 * log2(5/14) = 0.940
下面对属性集中每个属性分别计算信息熵,如下所示:
OUTLOOK属性:
OUTLOOK属性中,有3个取值:Sunny、Overcast和Rainy,样本分布情况如下: 类别为Yes时,Sunny有2个样本;类别为No时,Sunny有3个样本。 类别为Yes时,Overcast有4个样本;类别为No时,Overcast有0个样本。 类别为Yes时,Rainy有3个样本;类别为No时,Rainy有2个样本。 从而可以计算OUTLOOK属性的信息熵:
Info(OUTLOOK) = 5/14 * [- 2/5 * log2(2/5) – 3/5 * log2(3/5)]
+ 4/14 * [ - 4/4 * log2(4/4) - 0/4 * log2(0/4)]
+ 5/14 * [ - 3/5 * log2(3/5) – 2/5 * log2(2/5)] = 0.694
TEMPERATURE属性:
TEMPERATURE属性中,有3个取值:Hot、Mild和Cool,样本分布情况如下: 类别为Yes时,Hot有2个样本;类别为No时,Hot有2个样本。 类别为Yes时,Mild有4个样本;类别为No时,Mild有2个样本。 类别为Yes时,Cool有3个样本;类别为No时,Cool有1个样本。
Info(TEMPERATURE) = 4/14 * [- 2/4 * log2(2/4) – 2/4 * log2(2/4)]
+ 6/14 * [ - 4/6 * log2(4/6) - 2/6 * log2(2/6)]
+ 4/14 * [ - 3/4 * log2(3/4) – 1/4 * log2(1/4)] = 0.911
HUMIDITY属性:
TEMPERATURE属性中,有2个取值:High和Normal,样本分布情况如下: 类别为Yes时,High有3个样本;类别为No时,High有4个样本。 类别为Yes时,Normal有6个样本;类别为No时,Normal有1个样本。
Info(HUMIDITY) = 7/14 * [- 3/7 * log2(3/7) – 4/7 * log2(4/7)]
+ 7/14 * [ - 6/7 * log2(6/7) - 1/7 * log2(1/7)] = 0.789
WINDY属性:
WINDY属性中,有2个取值:True和False,样本分布情况如下: 类别为Yes时,True有3个样本;类别为No时,True有3个样本。 类别为Yes时,False有6个样本;类别为No时,False有2个样本。
Info(WINDY) = 6/14 * [- 3/6 * log2(3/6) – 3/6 * log2(3/6)]
+ 8/14 * [ - 6/8 * log2(6/8) - 2/8 * log2(2/8)] = 0.892
根据上面的数据,我们可以计算选择第一个根结点所依赖的信息增益值,计算如下所示:
Gain(OUTLOOK) = Info(D) - Info(OUTLOOK) = 0.940 - 0.694 = 0.246
Gain(TEMPERATURE) = Info(D) - Info(TEMPERATURE) = 0.940 - 0.911 = 0.029
Gain(HUMIDITY) = Info(D) - Info(HUMIDITY) = 0.940 - 0.789 = 0.151
Gain(WINDY) = Info(D) - Info(WINDY) = 0.940 - 0.892 = 0.048
根据上面对各个属性的信息增益值进行比较,选出信息增益值最大的属性:
Max(Gain(OUTLOOK), Gain(TEMPERATURE), Gain(HUMIDITY), Gain(WINDY)) = Gain(OUTLOOK)
所以,第一个根结点我们选择属性OUTLOOK。
继续执行上述信息熵和信息增益的计算,最终能够选出其他的决策结点,从而建立一棵决策树,这就是我们训练出来的分类模型。基于此模型,可以使用一组测试数据及进行模型的验证,最后能够对新数据进行预测。
五、决策树生成-C4.5算法
它与ID3算法的区别在于,它使用信息增益比来进行判断。