决策树(Decision Tree)
决策树是一种分类回归算法,决策树采用的是树形结构。每一个内部节点表示对于特征属性的判断,每一个分支就代表对这个特征属性判断的输出,每一个叶节点就是对决策结果的分类。 举个例子:在贷款买房、买车时,为了防止不良贷款,银行一般会看借款人的银行流水是否合格,如:月收入是否达标、时间是否合规、流水是否是造假。
决策树是一种常用的分类方法,是监督学习的一种,需要给出一些数据集样本,这些样本中包括了特征属性、决策分类的结果。通过这些数据集样本能够得到一个决策树,通过决策树得出新样本的分类结果。
决策树的优点是计算的复杂度不高、输出结果容易理解、对中间值的缺省不敏感。缺点是可能产生过度匹配的问题。
特征属性
在构造决策树时,需要解决的第一个问题就是,在数据集样本中,每个样本都有许多特征属性,每个特征属性对决策结果的影响都有大有小。为了找到那些决定性的特征,必须对每个特征进行评估、选择。对每个特征属性进行评估、选择就是对数据集的划分,一个数据集将被分为多个数据子集。
在选择特征属性时通常使用的方法为:信息增益。
信息增益
在选择特征属性之前和之后数据集发生的变化称之为信息增益。只要知道如何计算信息增益,就可以知道哪个特征属性就是最好的选择。
集合信息的度量方式被称为:香浓熵或者简称为熵。熵:信息的期望值,集合的无序程度,熵越大表示集合越无序,熵越小表示集合越有序。
如果待分类的数据集中可能会划分出多个分类,则符号 x~i~ 的信息定义为
\[l(x{_i}) = - log{_2}p(x{_i})\]其中 p(x~i~) 是这个分类的概率。
通过下面的公式可以得到所有类别的信息期望值,n 是分类的数目:
\[H = - \sum{^n_{i=1}}p(x{_i})log{_2}p(x{_i})\]ID3.5 算法
ID3.5 算法的核心思想是在决策树各个结点上选择最优的信息增益得出特征属性,递归地构建决策树,直到没有特征选择为止。最后得到一个决策树。
举个例子使用 ID3.5 算法计算熵与信息增益,下表是简单的银行流水是否达标
申请人序号 | 月收入是否达标 | 时间是否合规 | 流水是否造假 | 银行流水是否达标 |
---|---|---|---|---|
1 | 是 | 是 | 否 | 是 |
2 | 是 | 是 | 否 | 是 |
3 | 是 | 否 | 否 | 否 |
4 | 否 | 是 | 否 | 否 |
5 | 否 | 否 | 是 | 否 |
6 | 是 | 否 | 是 | 否 |
7 | 是 | 是 | 是 | 否 |
使用 ID3.5 算法计算上表中熵的值,把【是】用 1 表示,【否】用 0 表示,最后是否达标用 y/n 表示
1 |
|
示例结果
1 |
|
熵值越大表示集合越无序,熵越小表示集合越有序。
下面使用 Python 代码计算出示例中的最优特征
1 |
|
示例结果
1 |
|
在计算出第二个最优特征属性后,可以继续使用递归方式计算第二个最优特征属性,直至得出所有可能的决策类别。
下面构建决策树
1 |
|
示例结果
1 |
|
总结
简单的介绍了决策树和 ID3.5 算法,用了一个示例构造了一个简单的决策树,希望对大家有所帮助。
参考资料
《机器学习实战》