深度学习:知识回收(Lecture3+4PLA+DecisionTree)

序

晚上开始继续写啦&＃xff0c;这篇主要将PLA 和 决策树 DecisionTree

主要篇章应该是在决策树上&＃xff0c;依稀记得决策树自己实现的代码写的比较久&＃xff08;也可能是偷懒哈&＃xff09;

哼~

Lecture 3 PLA

PLA主要是用来解决二元分类问题

首先我们有样本x&＃61;{x1,x2,x3,…,xn} 、权重向量w&＃61;{w1,w2,w3,…,wn}、以及阈值θ

其中w0&＃61;θ

那么PLA的步骤应该是

• Step1 给样本前都加上常数字1
  

• Step 2 初始化权重&＃xff0c;w0&＃61;0或其他值

• Step 3 遍历所有样本

  发现预测是错误的时候&＃xff0c;即更新权重wt&＃43;1 &＃61; wt&＃43;yn*xn

  重复遍历所有样本直到所有的样本都预测正确

  此时的权重w就可以用来预测测试集的label

PLA的核心思想非常简单&＃xff0c;就是要尽量满足所有样本的预测正确

但是PLA不适用于非线性问题&＃xff0c;并且并非所有时候的权重w能满足所有样本预测正确

对于权重无法满足的情况有两种解决方法

1、 设置迭代次数&＃xff0c;在达到次数时直接停止继续遍历&＃xff0c;无论满不满足所有样本
2、用最优解的w作为 初始化的权重进行遍历和更新&＃xff0c;找到最优的w放入口袋
即口袋pocket算法

对于二元分类的验证集评测来说分为四个评测指标

准确率表示被正确分类的样本占总样本的比例

召回率是覆盖率的度量&＃xff0c;表示有多少正例被正确分类

精度表示被分为正例的示例中实际为正例的比例

精度P和召回率R有时候会出现的矛盾的情况&＃xff0c; F-Measure是Precision和Recall加权调和平均
α&＃61;1即F1

Lecture 4 Decision Tree

决策树&＃xff0c;看了下似乎不难哈&＃xff0c;就是分类方法多&＃xff08;所以才写的慢&＃xff0c;嗯肯定是这样&＃xff09;

处理离散和连续特征

剪枝&＃xff1a;预剪枝、后剪枝等

对于决策树来说&＃xff0c;就是要先建树。

• Step 1 初始化 &＃xff1a; 创建根结点&＃xff0c;该根结点拥有所有的数据集以及所有的特征
• Step 2 选择特征 &＃xff1a; 遍历当前所有结点的数据集和特征&＃xff0c;根据某种原则&＃xff0c;选择其中一个特征
• Step 3 划分数据 &＃xff1a; 根据这个特征的取值&＃xff0c;将当前数据集划分成为若干个子数据集
• Step 4 创建结点 &＃xff1a; 为每一个子数据集创建一个结点&＃xff0c;并且删除刚刚选中的特征
• Step 5 递归建树 &＃xff1a; 对于每个子结点&＃xff0c;返回到Step 2 &＃xff0c;直到达到边界条件&＃xff0c;则回溯
• Step 6 完成建树 &＃xff1a; 叶子结点采用多数投票的方式判定自身的类别

那么对于其中Step 5 来说&＃xff0c;边界条件是什么呢&＃xff0c;假设当前结点的数据集为D&＃xff0c;特征集为F

1. D中样本属于同一个类别 1 &＃xff0c;则将当前结点标记为类别1 的叶结点
2. F为空集或者D中所有样本在F中的所有特征值相同&＃xff0c;则此时已经达到边界&＃xff0c;将当前结点标记为叶结点&＃xff0c;类别为D中出现最多的类
3. D为空集&＃xff0c;则将当前结点标记为叶结点&＃xff0c;类别为父结点中出现最多的类

那么&＃xff0c;举个栗子

接下来我们对左边<&＃61;30 的age进行继续的划分

那么假设我们通过student这个类别来进行划分

子结点可以被分成yes 和 no

此时我们可以选择的特征划分的方法有3种

特征划分

ID3 信息增益

对于ID3&＃xff0c;信息增益&＃xff08;information gain&＃xff09;

步骤如下&＃xff1a;

那么举个计算的例子

C4.5 信息增益率

同样以上面的例子计算

CART GINI指数

以上面的例子进行计算

连续特征

上面举的例子都是关于离散特征的处理&＃xff0c;对于连续特征来说&＃xff0c;应该如何处理呢

连续特征我们首先可以将数据看作一个范围

譬如(0,1), [-20,20] 等等

对于这些连续的特征&＃xff0c;只需要分区对应即可

譬如0-0.5记作1&＃xff0c;0.5-1记作2&＃xff0c;那么(0,1)就被划分成两个离散的特征了

剪枝

剪枝可以帮助提升泛化性能&＃xff0c;简单的两种

预剪枝和后剪枝

1. 预剪枝&＃xff0c;是在决策树构造的时候进行的&＃xff0c;对于当前的结点未达到作为子结点的终止条件之前就进行停止&＃xff0c;并将该结点作为叶子结点。
   可以基于某个划分方式来确认对某个特征不再进行划分
   若划分后验证集的正确率无法提高则无需划分

2. 后剪枝&＃xff0c;在决策树形成后&＃xff0c;通过后续遍历进行尝试&＃xff0c;若发现某个非叶子结点变为叶子结点后&＃xff0c;在验证集上的正确率不下降&＃xff0c;则将其变成叶子结点

额外说一下

决策树一般用在一些流程、营销等市场战略分类上

对于决策树来说&＃xff0c;剪枝和设定上限高度可以有效解决过拟合问题

最后&＃xff0c;这篇文章过了几天才出来真不是我偷懒&＃xff0c;昨天电脑坏了&＃xff0c;先用ipad把bpnn的推导写出来就先写那篇了&＃xff0c;今天先修好了电脑才开始写的

哼&＃xff5e;