• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

学习日志-2021.10.11

开发技术 开发技术 4小时前 2次浏览

学习日志-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)
        ]

        在选择基尼指数最小的属性作为最优化分。

  • 剪枝处理

    防止决策树学习算法“过拟合”

    基本策略分为 预剪枝 和 后剪枝

    • 预剪枝:指在决策树生成过程中,对每个结点在划分前先进行评估,若当前结点的划分不能带来决策树泛化性能的提升,则停止划分并将当前节点标记为叶结点。
    • 后剪枝:先从训练集生成一颗完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化能力的提升,则将该子树替换为叶结点。
  • 连续与缺失值

    • 连续值处理
      • 上述决策树处理过程是基于离散属性的,在现实问题中常遇到连续值,对此需要将连续属性离散化
      • 最简单的方法是采用二分法对连续属性进行处理
    • 缺失值处理
      • 现实中侦测到的样本数据信息可能存在不完整的情况,为了能够尽量使得样本信息能够尽量被使用,需要对缺失值进行处理

程序员灯塔
转载请注明原文链接:学习日志-2021.10.11
喜欢 (0)