学习日志-2021.10.11
复习一下机器学习书本第四章内容
决策树
-
基本算法
这是一个递归的过程,有三种情况会导致递归返回:
- 当前节点包含的样本全属于同一类别,无需划分
- 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分
- 当前结点包含的样本集合为空,不能划分
输入:训练集 (D = {(x_1 , y_1),(x_2 , y_2),...,(x_m , y_m)})
属性集 (A = {a_1 , a_2 , ... , a_d})
过程:函数 TreeGenerate( (D) , (A) )
- 生成结点 node :
- if (D) 中样本全属于同一类别 (C) then
- 将 node 标记为 (C) 类叶结点;return
- end if
- if (A = Φ) OR (D) 中样本在 (A) 上取值相同 then
- 将 node 标记为叶结点,其类别标记为 (D) 中样本数最多的类;return
- end if
- 从 (A) 中选择最优划分属性 (a_*) ;
- for (a_*) 的每一个值 (a_*^v) do
- 为 node 生成一个分支;令 (D_v) 表示 (D) 中在 (a_*) 上取值为 (a_*^v) 的样本子集;
- if (D_v) 为空 then
- 将分支节点标记为叶结点,其类别标记为 (D) 中样本最多的类;return
- else
- 以 TreeGenerate( (D) , (A) ({a_*}) )为分支点
- end if
- end for
输出:以 node 为根节点的一棵决策树
-
划分选择
-
信息增益
信息熵:(Ent(D) = - sum_{k = 1}^{| gamma |} p_k log_2 p_k)
- (p_k) 为当前样本集合 (D) 中第 (k) 类样本所占的比例 ((k = 1,2,...,|gamma|))
(Ent(D)) 的值越小,则 (D) 的纯度越高
信息增益: (Gain (D,a) = Ent(D) - sum_{v=1}^{V} frac{|D_v|}{|D|} Ent(D^v))
假定离散值 (a) 有可能的取值为 ({ a^1,a^2,...,a^V }) ,使用 (a) 来对样本集进行划分,则会产生V个分支结点。
- (D^v) 表示第 (v) 个分支包含了 (D) 中所有在属性 (a) 上取值为 (a^v) 的样本
- $ frac{|D_v|}{|D|} $ 表示分支结点的权重
一般而言,信息增益越大,意味着使用属性 (a) 来进行划分所获得的“纯度提升”越大。
-
增益率
[Grain_ratio (D,a) = frac{Gain(D,a)}{IV(a)} ]其中
[IV(a) = - sum_{v=1}^{V} frac{|D_v|}{|D|} log_2 frac{|D_v|}{|D|} ]- (IV(a)) 成为属性 (a) 的“固有值”。属性 (a) 的可能取值数目越多,则 (IV(a)) 的值通常越大。
-
基尼指数
-
基尼值
[Gini(D) = sum_{k=1}^{|gamma|} sum_{k'≠k} p_k p_{k'}=1-sum_{k=1}^{|gamma|}p^2_k ]直观来说,(Gini(D)) 反映了从数据集 (D) 中随机抽取两个样本,其类别标记不一致的概率。即,(Gini(D)) 越小,则数据集 (D) 的纯度越高。
-
基尼指数
[Gini \_ index (D,a) = sum_{v=1}^{V} frac{|D^v|}{|D|} Gini(D) ]在选择基尼指数最小的属性作为最优化分。
-
-
-
剪枝处理
防止决策树学习算法“过拟合”
基本策略分为 预剪枝 和 后剪枝
- 预剪枝:指在决策树生成过程中,对每个结点在划分前先进行评估,若当前结点的划分不能带来决策树泛化性能的提升,则停止划分并将当前节点标记为叶结点。
- 后剪枝:先从训练集生成一颗完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化能力的提升,则将该子树替换为叶结点。
-
连续与缺失值
- 连续值处理
- 上述决策树处理过程是基于离散属性的,在现实问题中常遇到连续值,对此需要将连续属性离散化
- 最简单的方法是采用二分法对连续属性进行处理
- 缺失值处理
- 现实中侦测到的样本数据信息可能存在不完整的情况,为了能够尽量使得样本信息能够尽量被使用,需要对缺失值进行处理
- 连续值处理