模式识别笔记5-决策树

1. 决策树概览对于一个具有多个属性的数据集，决策树根据某种划分决策，依据某个离散属性对数据集进行划分，形成子集，之后递归地对子集进行划分，直到子集均属于某一类别，或是在某个容忍度下属于某种类比。假设有样本集合 \(D\)，它有如下属性：\(m\) 个样本属性集合 \(A\) 具有 \(n\) 个离散属性 \(\{a_1,a_2,\cdots,a_n\}\)\(|\gamma|\) 种...

weixin_30455023

236人浏览 · 2018-05-31 21:12:00

weixin_30455023 · 2018-05-31 21:12:00 发布

1. 决策树概览

对于一个具有多个属性的数据集，决策树根据某种划分决策，依据某个离散属性对数据集进行划分，形成子集，之后递归地对子集进行划分，直到子集均属于某一类别，或是在某个容忍度下属于某种类比。

假设有样本集合 \(D\)，它有如下属性：

\(m\) 个样本
属性集合 \(A\) 具有 \(n\) 个离散属性 \(\{a_1,a_2,\cdots,a_n\}\)
\(|\gamma|\) 种类别

对于决策树的建立，首先要解决的是划分。

2. 划分依据

假设对于样本集合的某个离散属性 \(a\)，有 \(V\) 种可能的取值，那么我们使用这个属性对样本集合进行划分后，可以获得 \(V\) 个子集，即 \(V\) 个分支节点。有3种常见的划分依据可以选择：

基尼指数（Gini index)
信息增益（information gain)
错分误差（Misclassification error）

2.1 基尼指数(Gini Index)

CART决策树使用基尼指数来选择划分属性。

基尼指数使用基尼值来衡量一个集合的纯度：
\[ \begin{align} \text{Gini}(D) &= \sum_{k=1}^{|\gamma|}\sum_{k'\neq k}p_kp_{k'}\\ &=1-\sum_{k=1}^{|\gamma|}p_k^2 \end{align} \]
直观的来看，基尼值反映了从数据集中任意抽取两个样本，其类别标记不一样的概率。
显然，基尼值越小，则数据集的纯度越高。

据此，基尼指数定义为：
\[ \begin{align} \text{Gini_index}(D,a)=\sum_{v=1}^V\frac{|D_v|}{|D|}\text{Gini}(D_v) \end{align} \]
考虑到划分的不同子集的个数不一样，引入权重因子 \(\frac{|D_v|}{|D|}\), 样本越多分支节点影响越大。

划分决策：
在候选属性集合 \(A\) 种，选择那个使得划分后基尼指数最小的属性作为划分属性

2.2 信息增益(Information Gain)

ID3决策树使用信息增益来作为划分依据。

信息增益使用信息熵来衡量一个样本集合的纯度：
\[ \begin{align} \text{Entropy}(D) =\text{Ent}(D)=-\sum_{k=1}^{|\gamma|}p_k\log_2p_k \end{align} \]
当集合只有一个类别 \(k'\) 的时候 \(p_{k\neq k'}=0, p_{k'}=1\)，则
\[ \begin{align} \min \text{Ent}(D)=0 \end{align} \]
当集合中所有类别同概率分布的时候，\(p_1=p_2=\cdots=p_{|\gamma|}=\frac{1}{|\gamma|}\)
\[ \begin{align} \max \text{Ent}(D)=-|\gamma|\frac{1}{|\gamma|}\log_2{\frac{1}{|\gamma|}}=\log_2{|\gamma|} \end{align} \]
可以看到，\(\text{Ent}(D)\) 的值越小，则数据集的纯度越高。

同样，根据划分子集进行加权，获得信息增益：
\[ \begin{align} \text{Gain}(D,a)=\text{Ent}(D)-\sum_{v=1}^{V}\frac{|D_v|}{|D|}\text{Ent}(D_v) \end{align} \]
一般来说，信息增益越大，则意味着使用属性 \(a\) 来划分所获得的 纯度提升 越大。