机器学习 | 决策树

标签：结点 机器 text sum 学习 增益 Ent quad 决策树

Def

信息熵

\[\text{Ent}(D)=\sum p_k\log p_k \]

条件熵

\[\text{Ent}(D|A)=\sum\frac{|D^v|}{|D|}\text{Ent}(D^v) \]

信息增益

\[\text{Gain}(D,A)=\text{Ent}(D)-\text{Ent}(D|A) \]

信息增益率

\[\text{Gain}_r (D,A)=\frac{\text{Gain}(D,A)}{\text{IV}(A)} \]

固有值

\[\text{IV(A)}=\sum\frac{|D^v|}{|D|}\log\frac{|D^v|}{|D|} \]

基尼系数

\[\text{Gini}(D)=1-\sum p_k^2 \]

条件基尼系数

\[\text{Gini}(D|A)=\sum \frac{|D^v|}{|D|}\text{Gini}(D^v) \]

信息熵反映的是数据的混乱程度, 熵值高则意为纯度低, 反之熵值低则意为纯度高即分类效果好. 信息熵的概念由香农提出, 沿袭了热力学中由玻尔兹曼发现的熵的定义式.

信息增益指的是以某一属性对数据集进行分类, 使熵下降的量的多少. 显然信息增益越高, 越适合作为分类标准.

信息增益率概念的提出是为了防止递归到后期只判定信息增益, 出现的过拟合现象.

基尼系数的直观意义是在数据集中任取两个样本, 它们属于不同类的概率. 可知其值越低, 纯度越高, 分类效果越好.

ID3 算法

以信息增益作为分类标准.

C4.5 算法

以信息增益率作为分类标准.

CART 算法

以基尼系数作为分类标准.

三个算法的流程都是:

1. 输入训练集 \(D\), 属性集 \(A\).
2. 生成决策树 \(\text{TreeGenerate(D,A)}\):
   生成结点 \(\text{node}\);
   \(\text{if}\) \(D\) 中样本属于同一类别 \(\text{then}\)
   \(\quad\) 标记 \(\text{node}\) 为该类叶结点; \(\text{return}\)
   \(\text{end if}\)
   \(\text{if}\) \(A=\emptyset\ \text{OR}\ D\) 中所有样本所有属性值相同 \(\text{then}\)
   \(\quad\) 标记 \(\text{node}\) 为叶结点, 类别为 \(D\) 中样本最多的类; \(\text{return}\)
   \(\text{end if}\)
   从 \(A\) 中选择最优划分属性 \(a\);
   \(\text{for}\) \(a\) 中每一个值 \(a^v\) \(\text{do}\)
   \(\quad\) 为 \(\text{node}\) 生成一个分支, 令 \(D^v\) 为该属性值的样本子集;
   \(\quad \text{if}\) \(D^v\) 为空 \(\text{then}\)
   \(\quad\quad\) 该分支结点标记为叶结点, 类别为 \(D\) 中样本最多的类; \(\text{return}\)
   \(\quad \text{else}\)
   \(\quad\quad \text{TreeGenerate}(D^v,A- \{a\})\)
   \(\quad \text{end if}\)
   \(\text{end for}\)
3. 输出以 \(\text{node}\) 为根结点的决策树.

Code

标签：结点,机器,text,sum,学习,增益,Ent,quad,决策树
From： https://www.cnblogs.com/Arcticus/p/16838755.html