机器学习 --- 重点回顾（一）1. Logistic Regression2. KNN（K-Nearest Neighbor）3. SVM (Support Vector Machine) 总结对比4. 决策树

93 阅读 0 评论 62 点赞

我是靠谱客的博主淡然灯泡，最近开发中收集的这篇文章主要介绍机器学习 --- 重点回顾（一）1. Logistic Regression2. KNN（K-Nearest Neighbor）3. SVM (Support Vector Machine) 总结对比4. 决策树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

近期实习及秋招岗竞争颇为激烈~ 整理了一些机器学习的相关知识，加以复习和巩固。以下所有图，侵删。

1. Logistic Regression

1.1 是什么： logistic 回归，是分类模型，主要用于二分类，使用了sigmoid非线性映射。

1.2 损失函数：

1.3 公式推导： 从贝叶斯开始推，将高斯分布带入似然函数。

1.4 如何多分类： Softmax。贝叶斯也可以推到Softmax。

1.5 具体< 贝叶斯->LR > <贝叶斯->Softmax>过程见下图：

2. KNN（K-Nearest Neighbor）

2.1 三要素：

K值选取：选太大，训练误差低，但泛化误差高，容易过拟合，模型复杂；选太小，泛化误差低，但训练误差高（很远的点也会有作用），模型简单
距离度量方式：欧式距离（常用），曼哈顿距离等
分类决策规则：多数表决法

2.2 和K-means的异同：

方法	KNN	K-means
属性	有监督分类	无监督聚类
目的	确定一个点的类别	将一堆点分成K类
训练	无明显训练过程，memory-based learning	有明显训练迭代过程
K值影响	K确定后，结果确定	K确定后，结果仍可能会变动

3. SVM (Support Vector Machine)

3.1 是什么： SVM是分类算法，目的是找到一个最佳分类面使得分类面两侧（正负样本）的样本中离分类面最近的正负样本距分类面距离（间隔）最大。距离表示为 $d = frac{1}{left |w right |}$

3.2 目标： 用数学语言描述： $max(d)==min(left | w right |)$ $s.t. y_{i}(w^{T}x_{i}+b)geq 1(i=1,2,3...n)$ 其中n为样本数。

SVM的基本型，在运筹学中属于二次规划问题，且是凸二次规划问题。二次规划问题主要用于求最优化问题，确实SVM问题如此，且问题中有限制。

根据优化理论，如果要达到最优，就要符合KKT（Karush-Kuhn-Tucker）条件。

KKT是一个（满足规则条件下）非线性规则问题能有最优解的充分必要条件。将约束条件按KKT列出，且符合KKT条件，就可以有最优解。

https://blog.csdn.net/on2way/article/details/47729419（关于SVM, 拉格朗日、KKT的详解）

普通优化问题 $f(x)=w^{T}x+b$ ， $max f(x)$ , 等式约束 $g(x)=0$ , 引入拉格朗日乘子 $lambda$ ，优化问题转化为： $max L(x,lambda )=f(x)+lambda g(x)$ （凸二次规划问题，能直接使用现代计算包求解，但可以使用更高效的拉格朗日乘子法）

构造目标函数： $L(w,b,lambda )=frac{1}{2}left | w right |^{2}+sum lambda_{i}(1-y_{i}(w^{T}x_{i}+b))$

对 $x$ 求偏导，得 $w=sum_{i=1}^{m}lambda_{i}y_{i}x_{i}$

对 $lambda$ 求偏导，得 $0=sum_{i=1}^{m}lambda_{i}y_{i}$

3.3 对偶问题？ 在求解最优化问题时，常把原问题转化为对偶问题求解。

然而，一般情况下，常规方法的计算规模正比于训练样本，且训练样本不能太小，因此为了控制计算规模，需要一种适合数据量大且计算小的方法 ------> SMO (Sequential Minimal Optimization)

SMO : 基本思路是先固定 $lambda_{i}$ 外得所有参数，然后求 $lambda_{i}$ 上的极值，每次选择两个变量 $lambda_{i}$ 和 $lambda_{j}$ ,并固定其他参数，不断执行如下步骤直至收敛。

选取一堆需要更新的变量 $lambda_{i}$ 和 $lambda_{j}$
固定 $lambda_{i}$ 和 $lambda_{j}$ 以外的参数，求解得到更新后的 $lambda_{i}$ 和 $lambda_{j}$

3.4 核函数? SVM的目的是通过样本找到最大间隔的分类面，但在现实任务中，原始的样本空间可能不存在可分离样本的超平面；因此，可以将样本从原始空间映射到更高维的特征空间，使得样本在高维空间中，可被线性划分。高位映射直接输入核函数，得到映射结果。运算简单。

常用核函数：

线性核函数 $k(x_{1},x_{2})=<x_{1},x_{2}>$
多项式核函数 $k(x_{1},x_{2})=(gamma <x_{1},x_{2}>+c)^{n}$
高斯核函数 $k(x_{1},x_{2})=exp(-frac{left | x_{1}-x_{2} right | ^{2}}{2delta^{2}})$
指数核函数（L2变L1） $k(x_{1},x_{2})=exp(-frac{left | x_{1}-x_{2} right |}{2delta^{2}})$ 只有分子变了
拉普拉斯核函数 $k(x_{1},x_{2})=exp(-frac{left | x_{1}-x_{2} right |}{delta})$ 分母变

总结对比

LR & SVM：

		Logistic Regression	SVM
同		(1) 都是分类算法 (2) SVM不考虑核时，都是线性分类算法	(3) 都是监督学习算法 (4) 都是判别模型
异	loss不同	————	————
	分类面-受影响数据不同	分类面-受所有数据影响	分类面-只受支持向量的影响
	非线性问题的处理不同	无法处理	用核函数
	是否依赖距离度量	不依赖	依赖数据距离表达度量

LR & 线性回归：

Logistic Regression

线性回归

是否线性

有sigmoid，是非线性模型

（除去该映射函数，是线性模型）

线性模型

损失函数

对数误差

平方误差

LR的评估？

有pair的AUC，使用不同阈值，看有几个错误的pair，计算比例。网上可以找到详细的例子。

4. 决策树

4.1 什么是决策树？ 决策树是一种通过对已知数据（实例）的描述来构建树形模型的方法，由结点和有向边组成。其中结点又分为内部结点和叶结点。由于构建树时样本的label已知，因此是一种监督学习方法。目前常用的算法有ID3, C4.5, CART等。

决策树学习算法：(1) 特征选择 (2) 决策树生成 (3) 决策树剪枝
优点： a) 决策树按规则建立的过程简单，易理解，直观；b) 应用范围广，可分类与回归，可多分类； c)可处理数值型和连续的样本特征。
缺点：a) 容易在训练数据中生产复杂的树结构，造成过拟合; 【可用“剪枝”操作缓解】 b)学习一棵最优的决策树被认为是NP-complete的，实际中决策树是基于启发式的贪心算法建立的，该算法不能保证建立全局最优的决策树。【“随机森林”可缓解】

4.2 ID3算法（Ross Quinlan, 1986年提出）

核心：在决策树各级节点上选择属性时，用信息增益(大) 作为属性选择的标准。
步骤：

优点：理论清晰，方法简单，学习能力较强。
缺点：a) 信息增益的计算依赖于特征数目多的特征(如“头发颜色”，有各种颜色头发的分类，所以用该属性分类后混乱度大幅度降低，信息增益大，但此特征数目多，极端情况下不公平)； b) 无法处理特征值为连续的情况 c) 抗噪性差

4.3 C4.5算法（仍是Ross Quinlan, 1993提出，为改进ID3）

改进思路：

ID3使用信息增益(gain) 作为属性选择标准，存在缺点，它一般会优先选择有较多属性值的特征（如“头发”，有红橙黄绿青蓝紫7种属性），因为这种特征有相对较大的信息增益(属性值多，分得越细，数据集确定性更高，混乱度大幅度降低，信息增益越大)，我们不希望有这种偏见。

（1）为了改进这个不足， C4.5中使用信息增益率(gain ratio) 作为分支标准，它通过引入一个被称作分裂信息(Split information)的项，惩罚取值较多的特征。

（2）ID3不能解决特征属性值连续的问题，C4.5可以。

步骤：

4.4 CART算法（Classification And Regression Tree, 分类回归树，1984年由L.Breiman, J.Friedman, R.Olshen, C.Stone提出）

改进思路：

ID3中根据属性分割数据，之后该特征不会再起作用，这种分割过于快速，会影响算法的准确率。而CART树是一棵二叉树,采用二元切分法, 每次把数据切成两份并分别送进左子树右子树,且每个非叶子节点有两个孩子(二叉树性质),因此CART叶子节点比非叶子节点多1.

核心：CART可用于分类，可用于回归。

分类时，使用基尼指数(Gini) 作为属性选择标准，它描述的是纯度，与信息熵含义相似。CART中每一次迭代都会降低Gini指数。

回归时，使用均方差作为 loss function。

4.5 分类树 vs 回归树

分类树：分类树模型用于分类，根据最大增益/增益率选择分支处特征。样本依次从上到下经历每个特征，根据样本属性值进行分支，直到被分到叶子节点或达到预设条件。若最终叶子节点的类别不唯一，则以多数投票法作为最后类别。

回归树：回归树总体流程类似，区别在于回归树的每个节点都会得到一个预测值，该预测值等于属于这个节点的所有样本属性值的平均值。分支选特征时，遍历每个特征每个阈值找最好的分割点，但标准不再是“最大增益/增益率”，而是最小化均方差。（被预测错的样本越多，错的越离谱，均方差就越大。因此通过最小化均方差，来找最可靠的分支依据。）若叶子节点上的值不唯一，则以该节点上所有样本的平均值作为该节点的预测值。