0%

机器学习常见算法个人总结

原载于 机器学习常见算法个人总结(面试用),经本人整理并加入别的资料,仅供参考。

参数模型VS变参模型

机器学习算法可以被分为两大类:参数模型和变参模型。对于参数模型,在训练过程中我们要学习一个函数,重点是估计函数的参数,然后对于新数据集,我们直接 用学习到的函数对齐分类。典型的参数模型包括感知机、逻辑斯蒂回归和线性SVM。与之相对的,变参模型中的参数个数不是固定的,它的参数个数随着训练集增 大而增多!很多书中变参(nonparametric)被翻译为无参模型,一定要记住,不是没有参数,而是参数个数是变量!变参模型的两个典型示例是决策树/随机森林和核SVM。

朴素贝叶斯

参考[1]

事件A和B同时发生的概率为在A发生的情况下发生B或者在B发生的情况下发生A
$P(A \cap B) = P(A)*P(B|A) = P(B)*P(A|B)$
所以有:

对于给出的待分类项,求解在此项出现的条件下各个目标类别出现的概率,哪个最大,就认为此待分类项属于哪个类别

工作原理

  1. 假设现在有样本$x=(a_1,a_2,a_3,…a_n)$这个待分类项(并认为$x$里面的特征独立)
  2. 再假设现在有分类目标$Y={y_1,y_2,y_3,y_4..y_n}$
  3. 那么$max(P(y_1|x),P(y_2|x),P(y_3|x)..P(y_n|x))$就是最终的分类类别
  4. 而$P(y_i|x)=\frac{p(x|y_i)*P(yi)}{P(x)}$
  5. 因为$x$对于每个分类目标来说都一样,所以就是求$max(P(x|y_i)*p(y_i))$
  6. $P(x|y_i)*p(y_i)=p(y_i)*\prod_i(P(a_i|y_i))$
  7. 而具体的$p(a_i|y_i)$和$p(y_i)$都是能从训练样本中统计出来
    $p(a_i|y_i)$表示该类别下该特征出现的概率
    $p(y_i)$表示全部类别中这个这个类别出现的概率
  8. 好的,就是这么工作的^_^

工作流程

  1. 准备阶段
    确定特征属性,并对每个特征属性进行适当划分,然后由人工对一部分待分类项进行分类,形成训练样本。
  2. 训练阶段
    计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计
  3. 应用阶段
    使用分类器进行分类,输入是分类器和待分类样本,输出是样本属于的分类类别

属性特征

  1. 特征为离散值时直接统计即可(表示统计概率)
  2. 特征为连续值的时候假定特征符合高斯分布:$g(x,n,u)$
    那么$p(a_k|y_i)=g(x_k,n_i,u_i)$

Laplace校准(拉普拉斯校验)

当某个类别下某个特征划分没有出现时,会有$P(a|y)=0$,就是导致分类器质量降低,所以此时引入Laplace校验,就是对没类别下所有划分的计数加1。

遇到特征之间不独立问题

参考改进的贝叶斯网络,使用DAG来进行概率图的描述

优缺点

朴素贝叶斯的优点:

  1. 对小规模的数据表现很好,适合多分类任务,适合增量式训练。

缺点:

  1. 对输入数据的表达形式很敏感(离散、连续,值极大极小之类的)。

Liner Regression 线性回归

用Tensorflow实现的一个线性回归例子

Logistic Regression 逻辑回归

参考[2,3,4]

LR回归是一个线性的二分类模型,主要是计算在某个样本特征下事件发生的概率,比如根据用户的浏览购买情况作为特征来计算它是否会购买这个商品,抑或是它是否会点击这个商品。然后LR的最终值是根据一个线性和函数再通过一个sigmoid函数来求得,这个线性和函数权重与特征值的累加以及加上偏置求出来的,所以在训练LR时也就是在训练线性和函数的各个权重值w。

关于这个权重值w一般使用最大似然法来估计,假设现在有样本${x_i,y_i}$, 其中$x_i$表示样本的特征,$y_i \in {0,1}$表示样本的分类真实值,$y_i=1$的概率是$p_i$,则$y_i=0$的概率是$1-p_i$,那么观测概率为:

则最大似然函数为:

对这个似然函数取对数之后就会得到的表达式

$$\begin{aligned} L(w) & = \sum_i \left( y_i*logh_w(x_i)+(1-y_i)*log(1-h_w(x_i)) \right) \\ & = \sum_i \left(y_i*(w^Tx_i)+log(1+e^{w^Tx_i})\right) \end{aligned}$$

估计这个$L(w)$的极大值就可以得到$w$的估计值。

实际操作中一般会加个负号 改为求最小

所以求解问题就变成了这个最大似然函数的最优化问题,这里通常会采样随机梯度下降法和拟牛顿迭代法来进行优化

梯度下降法

LR的损失函数为交叉熵代价函数(cross-entropy cost function):
$J(w)=-\frac{1}{N} \sum_{i=1}^N{\left(y_i*log(h_w(x_i))+(1-y_i)*log(1-h_w(x_i))\right)}$
这样就变成了求$min(J(w))$其更新w的过程为

$$\begin{aligned} w:&=w- \alpha * \triangledown J(w) \\ w:&=w- \alpha * \frac{1}{N}*\sum_{i=1}^N\left( (h_w(x_i)-y_i) *x_i\right) \end{aligned}$$

其中$\alpha为步长$,直到$J(w)$不能再小时停止

梯度下降法的最大问题就是会陷入局部最优,并且每次在对当前样本计算cost的时候都需要去遍历全部样本才能得到cost值,这样计算速度就会慢很多(虽然在计算的时候可以转为矩阵乘法去更新整个w值)
所以现在好多框架(mahout)中一般使用随机梯度下降法,它在计算cost的时候只计算当前的代价,最终cost是在全部样本迭代一遍之求和得出,还有他在更新当前的参数w的时候并不是依次遍历样本,而是从所有的样本中随机选择一条进行计算,它方法收敛速度快(一般是使用最大迭代次数),并且还可以避免局部最优,并且还很容易并行(使用参数服务器的方式进行并行)
$w:=w-\alpha * \left( (h_w(x_j)-y_j) *x_i\right);j \in 1 \ldots N \quad and \quad randomly$

这里SGD可以改进的地方就是使用动态的步长

其他优化方法

  • 拟牛顿法(记得是需要使用Hessian矩阵和cholesky分解)
  • BFGS
  • L-BFGS

优缺点:无需选择学习率α,更快,但是更复杂

关于LR的过拟合问题

如果我们有很多的特性,在训练集上拟合得很好,但是在预测集上却达不到这种效果

  1. 减少feature个数(人工定义留多少个feature、算法选取这些feature)
  2. 正则化(为了方便求解,L2使用较多)
    添加正则化之后的损失函数为:

    $J(w)=-\frac{1}{N} \sum_{i=1}^N{\left(y_i*log(h_w(x_i))+(1-y_i)*log(1-h_w(x_i))\right)} + \frac{\lambda}{2} ||w||_2$

    同时w的更新变为

    $w:=w-\alpha * \left(h_w(x_j)-y_j) *x_i\right) -2\alpha*w_j$

    注意:这里的$w_0$不受正则化影响

p范数的求解:
$$||X||_p=\left\{ \begin{aligned} Count(x_i \neq 0) & \quad if \quad p = 0 \\ (\sum_i^n |x_i|^p)^{\frac{1}{p}} & \quad if \quad p \neq 0 \\ \end{aligned} \right.$$

关于LR的多分类:softmax

假设离散型随机变量Y的取值集合是{1,2,..,k},则多分类的LR为
$P(Y=a|x)=\frac{exp(w_a*x)}{(\sum_{i=1}^k(w_i*x))} ; 1<a<k$

这里会输出当前样本下属于哪一类的概率,并且满足全部概率加起来=1

关于softmax和k个LR的选择

如果类别之间是否互斥(比如音乐只能属于古典音乐、乡村音乐、摇滚月的一种)就用softmax
否则类别之前有联系(比如一首歌曲可能有影视原声,也可能包含人声,或者是舞曲),这个时候使用k个LR更为合适

优缺点:
Logistic回归优点:

  1. 实现简单;
  2. 分类时计算量非常小,速度很快,存储资源低;

缺点:

  1. 容易欠拟合,一般准确度不太高
  2. 只能处理两分类问题(在此基础上衍生出来的softmax可以用于多分类),且必须线性可分;

ps 另外LR还可以参考这篇以及多分类可以看这篇,softmax可以看这篇

示例代码

这是用TensorFlow 实现的实例代码, 损失函数是基于Softmax的交叉熵函数

感知机

将逻辑回归修改一下,现在强制它的输出不是0就是1,则此时的$g$就是一个临界函数(threshold function)
$$g(z)=\left\{ \begin{aligned} 1 & \quad if \quad z \geq 0 \\ 0 & \quad if \quad z < 0 \\ \end{aligned} \right.$$

$h_\theta(x)=g(\theta^T x)$ 则我们得到更新规则如下: $\theta_j:=\theta_j+\alpha(y^i-h_\theta(x^i))x_j^i$

这就是感知机算法。

KNN算法

给一个训练数据集和一个新的实例,在训练数据集中找出与这个新实例最近的k个训练实例,然后统计最近的k个训练实例中所属类别计数最多的那个类,就是新实例的类。
虽然我们在逻辑回归中讨论了正则项来防止过拟合,但是正则项却不适用于KNN和决策树模型,我们只能通过特征选择和降维手段来避免维度诅咒。

三要素:

  1. k值的选择
  2. 距离的度量(常见的距离度量有欧式距离,马氏距离等)
  3. 分类决策规则 (多数表决规则)

k值的选择

  1. k值越小表明模型越复杂,更加容易过拟合
  2. 但是k值越大,模型越简单,如果k=N的时候就表明无论什么点都是训练集中类别最多的那个类

所以一般k会取一个较小的值,然后用过交叉验证来确定
这里所谓的交叉验证就是将样本划分一部分出来为预测样本,比如95%训练,5%预测,然后k分别取1,2,3,4,5之类的,进行预测,计算最后的分类误差,选择误差最小的k

KNN的回归

在找到最近的k个实例之后,可以计算这k个实例的平均值作为预测值。或者还可以给这k个实例添加一个权重再求平均值,这个权重与度量距离成反比(越近权重越大)。

优缺点:

KNN算法的优点:

  1. 思想简单,理论成熟,既可以用来做分类也可以用来做回归;
  2. 可用于非线性分类;
  3. 训练时间复杂度为O(n);
  4. 准确度高,对数据没有假设,对outlier不敏感;

缺点:

  1. 计算量大;
  2. 样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少);
  3. 需要大量的内存;

KD树

KD树是一个二叉树,表示对K维空间的一个划分,可以进行快速检索(那KNN计算的时候不需要对全样本进行距离的计算了)

构造KD树

在k维的空间上循环找子区域的中位数进行划分的过程。
假设现在有K维空间的数据集$T={x_1,x_2,x_3,…x_n}$,$xi={a_1,a_2,a_3..a_k}$

  1. 首先构造根节点,以坐标$a_1$的中位数b为切分点,将根结点对应的矩形局域划分为两个区域,区域1中$a_1 < b$,区域2中$a_1 > b$
  2. 构造叶子节点,分别以上面两个区域中$a_2$
    的中位数作为切分点,再次将他们两两划分,作为深度1的叶子节点,(如果a2=中位数,则a2的实例落在切分面)
  3. 不断重复2的操作,深度为j的叶子节点划分的时候,索取的$a_i$的$i=j\%k+1$,直到两个子区域没有实例时停止

KD树的搜索

  1. 首先从根节点开始递归往下找到包含x的叶子节点,每一层都是找对应的xi
  2. 将这个叶子节点认为是当前的“近似最近点”
  3. 递归向上回退,如果以x圆心,以“近似最近点”为半径的球与根节点的另一半子区域边界相交,则说明另一半子区域中存在与x更近的点,则进入另一个子区域中查找该点并且更新”近似最近点“
  4. 重复3的步骤,直到另一子区域与球体不相交或者退回根节点
  5. 最后更新的”近似最近点“与x真正的最近点

KD树进行KNN查找

通过KD树的搜索找到与搜索目标最近的点,这样KNN的搜索就可以被限制在空间的局部区域上了,可以大大增加效率。

KD树搜索的复杂度

当实例随机分布的时候,搜索的复杂度为log(N),N为实例的个数,KD树更加适用于实例数量远大于空间维度的KNN搜索,如果实例的空间维度与实例个数差不多时,它的效率基于等于线性扫描。

后来自己有实现过KD树,可以看KNN算法中KD树的应用

SVM、SMO

对于样本点$(x_i,y_i)$以及svm的超平面:$w^Tx_i+b=0$

  • 函数间隔:$y_i(w^Tx_i+b)$
  • 几何间隔:$\frac{y_i(w^Tx_i+b)}{||w||}$,其中$||w||$为$w$的L2范数,几何间隔不会因为参数比例的改变而改变

svm的基本想法就是求解能正确划分训练样本并且其几何间隔最大化的超平面。

线性SVM问题

先来看svm的问题:
$$\underset{w,b}{argmax} \quad \gamma \\ st. \quad \frac{y_i(w^Tx_i+b)}{||w||} \geq \gamma$$

那么假设$\hat{\gamma}=\gamma *||w||$
则将问题转为:
$$\underset{w,b}{argmax} \quad \frac{\hat{\gamma}}{||w||} \\ st. \quad y_i(w^Tx_i+b) \geq 1$$

由于$\hat{\gamma}$的成比例增减不会影响实际间距,所以这里的取$\hat{\gamma}=1$,又因为$max(\frac{1}{||w||})=min(\frac{1}{2}*||w||^2)$ 所以最终的问题就变为了
$$\underset{w,b}{argmin} \quad \frac{1}{2}*||w||^2 \\ st. \quad y_i(w^Tx_i+b) \geq 1$$

这样就变成了一个凸的二次规划化,可以将其转换为拉格朗日函数,然后使用对偶算法来求解

对偶求解

引进拉格朗日乘子$\alpha={\alpha_1,\alpha_2..\alpha_n}$, 定义拉格朗日函数:
$L(w,b,a)=\frac{1}{2}*||w||^2-\sum_{i=1}^{N}(\alpha_i*y_i(w^Tx_i+b))+\sum(\alpha_i)$

根据对偶性质 原始问题就是求对偶问题的极大极小

先求L对$w,b$的极小,再求对$\alpha$的极大。
求$\underset{w,b}{min}L(w,b,\alpha)$,也就是相当于对$w,b$求偏导并且另其等于0
$$\begin{aligned} \triangledown_wL(w,b,\alpha)&=w-\sum_{i=1}^{N}(\alpha_iy_ix_i)=0 \\ \triangledown_bL(w,b,\alpha)&=\sum_{i=1}^{N}(a_iy_i)=0 \end{aligned}$$
代入后可得
$\underset{w,b}{min}L(w,b,\alpha)=-\frac{1}{2}*\sum_{i=1}^{N}\sum_{j=1}^{N}\left(\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)\right)+\sum_{i=1}^{N}\alpha_i$
求$\underset{w,b}{min}L(w,b,\alpha)$对$\alpha$的极大,即是对偶问题:
$$\underset{\alpha}{max} -\frac{1}{2}*\sum_{i=1}^{N}\sum_{j=1}^{N}\left(\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)\right)+\sum_{i=1}^{N}\alpha_i \\ st. \quad \sum_{i=1}^{N}(a_iy_i)=0 \\ \alpha \geq 0,i=1,2,3…N$$
将求最大转为求最小,得到等价的式子为:
$$\underset{\alpha}{min} \frac{1}{2}*\sum_{i=1}^{N}\sum_{j=1}^{N}\left(\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)\right)-\sum_{i=1}^{N}\alpha_i \\ st. \quad \sum_{i=1}^{N}(a_iy_i)=0 \\ \alpha \geq 0,i=1,2,3…N$$

假如求解出来的$\alpha$$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},…\alpha_n^{*})$
则得到最优的$w,b$分别为
$$w^{*}=\sum_{i=1}^{N}(\alpha_i^{*}y_ix_i)\\ b^{*}=y_j-\sum_{i=1}^{N}(\alpha_i^{*}y_i(x_i \cdot x_j))$$
所以,最终的决策分类面为
$f(x)=sign\left( \sum_{i=1}^{N}(\alpha_i^{*}y_i(x \cdot x_i) +b^{*} \right)$
也就是说,分类决策函数只依赖于输入$x$与训练样本的输入的内积

ps:上面介绍的是SVM的硬间距最大化,还有一种是软间距最大化,引用了松弛变量$\zeta$,则次svm问题变为:

其余解决是与硬间距的一致~

还有:与分离超平面最近的样本点称为支持向量

损失函数

损失函数为(优化目标):
$\sum_{i=1}^{N}[1-y_i(w^Tx_i+b)]_+ + \lambda||w||^2$

其中$[1-y_i(w^Tx_i+b)]_+$称为折页损失函数,因为:
$$[1-y_i(w^Tx_i+b)]_+=\left\{ \begin{aligned} 0 & \quad if \quad 1-y_i(w^Tx_i+b) \le 0 \\ 1-y_i(w^Tx_i+b) & \quad otherwise\\ \end{aligned} \right.$$

为什么要引入对偶算法

  1. 对偶问题往往更加容易求解(结合拉格朗日和kkt条件)
  2. 可以很自然的引用核函数(拉格朗日表达式里面有内积,而核函数也是通过内积进行映射的)

核函数

将输入特征x(线性不可分)映射到高维特征R空间,可以在R空间上让SVM进行线性可以变,这就是核函数的作用

  • 多项式核函数:$K(x,z)=(x*z+1)^p$
  • 高斯核函数:$K(x,z)=exp(\frac{-(x-z)^2}{\sigma^2})$
  • 字符串核函数:貌似用于字符串处理等

SVM优缺点

优点:

  1. 使用核函数可以向高维空间进行映射
  2. 使用核函数可以解决非线性的分类
  3. 分类思想很简单,就是将样本与决策面的间隔最大化
  4. 分类效果较好

缺点:

  1. 对大规模数据训练比较困难
  2. 无法直接支持多分类,但是可以使用间接的方法来做

SMO

SMO是用于快速求解SVM的
它选择凸二次规划的两个变量,其他的变量保持不变,然后根据这两个变量构建一个二次规划问题,这个二次规划关于这两个变量解会更加的接近原始二次规划的解,通过这样的子问题划分可以大大增加整个算法的计算速度,关于这两个变量:

  1. 其中一个是严重违反KKT条件的一个变量
  2. 另一个变量是根据自由约束确定,好像是求剩余变量的最大化来确定的。

SVM多分类问题

  1. 直接法
    直接在目标函数上进行修改,将多个分类面的参数求解合并到一个最优化问题中,通过求解该优化就可以实现多分类(计算复杂度很高,实现起来较为困难)
  2. 间接法
    1. 一对多
      其中某个类为一类,其余n-1个类为另一个类,比如A,B,C,D四个类,第一次A为一个类,{B,C,D}为一个类训练一个分类器,第二次B为一个类,{A,C,D}为另一个类,按这方式共需要训练4个分类器,最后在测试的时候将测试样本经过这4个分类器$f_1(x)$,$f_2(x)$,$f_3(x)$和$f_4(x)$,取其最大值为分类器(这种方式由于是1对M分类,会存在偏置,很不实用)
    2. 一对一(libsvm实现的方式)
      任意两个类都训练一个分类器,那么n个类就需要n(n-1)/2个svm分类器。
      还是以A,B,C,D为例,那么需要{A,B},{A,C},{A,D},{B,C},{B,D},{C,D}为目标共6个分类器,然后在预测的将测试样本通过这6个分类器之后进行投票选择最终结果。(这种方法虽好,但是需要n
      (n-1)/2个分类器代价太大,不过有好像使用循环图来进行改进)

逻辑斯蒂回归 VS SVM

在解决现实的分类问题时,线性逻辑斯蒂回归和线性SVM通常效果近似。逻辑回归目标是最大化训练集的条件似然,使得她更易受奇异值影响。SVM 只关心那些离决策界最近的点(即,支持向量)。另一方面,逻辑斯蒂回归的优点是易于实现,特别是并行化实现。此外,面对流式数据,逻辑斯蒂回归的易于更新的特点也很明显。

决策树

决策树是一颗依托决策而建立起来的树。对于决策树算法来说,特征缩放并不是必须的。

ID3

  1. 首先是针对当前的集合,计算每个特征的信息增益
  2. 然后选择信息增益最大的特征作为当前节点的决策决策特征
  3. 根据特征不同的类别划分到不同的子节点(比如年龄特征有青年,中年,老年,则划分到3颗子树)
  4. 然后继续对子节点进行递归,直到所有特征都被划分

一个属性中某个类别的熵 $p_i=P(y_i|a_i)$, $p_i$表示$a_i$情况下发生$y_i$的概率,也即是统计概率。

增益表示分类目标的熵减去当前属性的熵,增益越大,分类能力越强
(这里前者叫做经验熵,表示数据集分类C的不确定性,后者就是经验条件熵,表示在给定A的条件下对数据集分类C的不确定性,两者相减叫做互信息,决策树的增益等价于互信息)。
比如说当前属性是是否拥有房产,分类是是否能偿还债务
现在:

  • 有用房产为7个,4个能偿还债务,3个无法偿还债务
  • 然后无房产为3个,其中1个能偿还债务,2个无法偿还债务

然后
有房子的熵:$S(have\_house)=-(\frac{4}{7}*log\frac{4}{7}+\frac{3}{7}*log\frac{3}{7})$
无房子的熵:$S(no\_house)=-(\frac{1}{3}*log\frac{1}{3}+\frac{2}{3}*log\frac{2}{3})$
分类的熵:$S(classifier)=-(\frac{5}{10}*log\frac{5}{10}+\frac{5}{10}*log\frac{5}{10})$
最终的增益=$S(classifier)-(\frac{7}{10}*S(have\_house)+\frac{3}{10}*S(no\_house))$最大越好

关于损失函数

设树的叶子节点个数为$T$,$t$ 为其中一个叶子节点,该叶子节点有 $N_t$ 个样本,其中 $k$类的样本有$N_{tk}$个,$H(t)$为叶子节点上的经验熵,则损失函数定义为
$C_t(T)=\sum(N_t*H(t))+ \lambda|T|$
其中
$H(t)=\sum(\frac{N_{tk}}{N_t}*log(\frac{N_{tk}}{Nt}))$
代入可以得到
$C_t(T)=\sum(\sum(N_{tk}*log(N_{tk}/N_t)))+\lambda|T|$

$\lambda|T|$为正则化项,$\lambda$是用于调节比率
决策树的生成只考虑了信息增益

C4.5

它是ID3的一个改进算法,使用信息增益率来进行属性的选择
$$splitInformation(S,A)=-\sum_i(\frac{|S_i|}{|S|}*log2(\frac{|Si|}{|S|})) \\ GainRatio(S,A)=\frac{Gain(S,A)}{splitInformation(S,A)}$$

优缺点:
准确率高,但是子构造树的过程中需要进行多次的扫描和排序,所以它的运算效率较低

Cart

分类回归树(Classification And Regression Tree)是一个决策二叉树,在通过递归的方式建立,每个节点在分裂的时候都是希望通过最好的方式将剩余的样本划分成两类,这里的分类指标:

  1. 分类树:基尼指数最小化(gini_index)
  2. 回归树:平方误差最小化

分类树:

  1. 首先是根据当前特征计算他们的基尼增益
  2. 选择基尼增益最小的特征作为划分特征
  3. 从该特征中查找基尼指数最小的分类类别作为最优划分点
  4. 将当前样本划分成两类,一类是划分特征的类别等于最优划分点,另一类就是不等于
  5. 针对这两类递归进行上述的划分工作,直达所有叶子指向同一样本目标或者叶子个数小于一定的阈值

gini用来度量分布不均匀性(或者说不纯),总体的类别越杂乱,GINI指数就越大(跟熵的概念很相似)

$p_i$当前数据集中第i类样本的比例
gini越小,表示样本分布越均匀(0的时候就表示只有一类了),越大越不均匀
基尼增益
$gini\_gain=\sum_i(\frac{N_i}{N}*gini(a_i))$ 表示当前属性的一个混乱 $\frac{N_i}{N}$

表示当前类别占所有类别的概率
最终Cart选择GiniGain最小的特征作为划分特征

以ID3中的贷款的那棵树为样例:
基尼指数有房产:$gini(have\_house)=1-\left((\frac{3}{7})^2+(\frac{4}{7})^2\right)$
基尼指数无房产:$gini(no\_house)=1-\left((\frac{1}{3})^2+(\frac{2}{3})^2\right)$
基尼增益为:$gini\_gain=\frac{7}{10}*gini(have\_house)+\frac{3}{10}*gini(no\_house)$

回归树:

回归树是以平方误差最小化的准则划分为两块区域

  1. 遍历特征计算最优的划分点s,使其最小化的平方误差是:$min{min(\sum_i^{R1}((y_i-c_1)^2))+min(\sum_i^{R2}((y_i-c_2)^2))}$计算根据s划分到左侧和右侧子树的目标值与预测值之差的平方和最小,这里的预测值是两个子树上输入xi样本对应$y_i$的均值
  2. 找到最小的划分特征j以及其最优的划分点s,根据特征j以及划分点s将现有的样本划分为两个区域,一个是在特征j上小于等于s,另一个在在特征j上大于s $$R1(j)=\{x|x(j) \leq s\} \\ R2(j)=\{x|x(j) > s\}$$
  3. 进入两个子区域按上述方法继续划分,直到到达停止条件
    这里面的最小化我记得可以使用最小二乘法来求

关于剪枝:用独立的验证数据集对训练集生长的树进行剪枝(事后剪枝)。

停止条件

  1. 直到每个叶子节点都只有一种类型的记录时停止,(这种方式很容易过拟合)
  2. 另一种时当叶子节点的记录树小于一定的阈值或者节点的信息增益小于一定的阈值时停止

关于特征与目标值

  1. 特征离散 目标值离散:可以使用ID3,cart
  2. 特征连续 目标值离散:将连续的特征离散化 可以使用ID3,cart
  3. 特征离散 目标值连续

决策树的分类与回归

  • 分类树
    输出叶子节点中所属类别最多的那一类
  • 回归树
    输出叶子节点中各个样本值的平均值

理想的决策树

  1. 叶子节点数尽量少
  2. 叶子节点的深度尽量小(太深可能会过拟合)

解决决策树的过拟合

  1. 剪枝
    1. 前置剪枝:在分裂节点的时候设计比较苛刻的条件,如不满足则直接停止分裂(这样干决策树无法到最优,也无法得到比较好的效果)
    2. 后置剪枝:在树建立完之后,用单个节点代替子树,节点的分类采用子树中主要的分类(这种方法比较浪费前面的建立过程)
  2. 交叉验证
  3. 随机森林

优缺点

优点:

  1. 计算量简单,可解释性强,比较适合处理有缺失属性值的样本,能够处理不相关的特征;

缺点:

  1. 单颗决策树分类能力弱,并且对连续值变量难以处理;
  2. 容易过拟合(后续出现了随机森林,减小了过拟合现象);

随机森林 RF

随机森林是有很多随机得决策树构成,它们之间没有关联。得到RF以后,在预测时分别对每一个决策树进行判断,最后使用Bagging的思想进行结果的输出(也就是投票的思想)。

随机森林一直是广受欢迎的模型,优点很多:优秀的分类表现、扩展性和使用简单。随机森林的思想也不复杂,一个随机森林模型就是多颗决策树的集成。集成学习(ensemble learning)的观点是将多个弱分类器结合来构建一个强分类器,它的泛化误差小且不易过拟合。

随机森林中构建决策树的做法和原始决策树的区别是,在每次分割节点时,不是从所有特征中选择而是在一个小特征集中选择特征。

虽然随机森林模型的可解释性不如决策树,但是它的一大优点是受超参数的影响波动不是很大(译者注:几个主要参数还是需要好好调参的)。我们也不需要对随机森林进行剪枝因为集成模型的鲁棒性很强,不会过多受单棵决策树噪音的影响。

随机森林能够度量每个特征的重要性,我们可以依据这个重要性指标进而选择最重要的特征。

学习过程

  1. 现在有N个训练样本,每个样本的特征为M个,需要建K颗树
  2. 从N个训练样本中有放回的取N个样本作为一组训练集(其余未取到的样本作为预测分类,评估其误差)
  3. 从M个特征中取m个特征左右子集特征(m<<M)
  4. 对采样的数据使用完全分裂的方式来建立决策树,这样的决策树每个节点要么无法分裂,要么所有的样本都指向同一个分类
  5. 重复2的过程K次,即可建立森林

预测过程

  1. 将预测样本输入到K颗树分别进行预测
  2. 如果是分类问题,直接使用投票的方式选择分类频次最高的类别
  3. 如果是回归问题,使用分类之后的均值作为结果

参数问题

  1. 这里的一般取m=sqrt(M)
  2. 关于树的个数K,一般都需要成百上千,但是也有具体的样本有关(比如特征数量)
  3. 树的最大深度,(太深可能可能导致过拟合??)
  4. 节点上的最小样本数、最小信息增益

泛化误差估计

使用oob(out-of-bag)进行泛化误差的估计,将各个树的未采样样本作为预测样本(大约有36.8%),使用已经建立好的森林对各个预测样本进行预测,预测完之后最后统计误分得个数占总预测样本的比率作为RF的oob误分率。

学习算法

  1. ID3算法:处理离散值的量
  2. C45算法:处理连续值的量
  3. Cart算法:离散和连续 两者都合适?

关于CART

Cart可以通过特征的选择迭代建立一颗分类树,使得每次的分类平面能最好的将剩余数据分为两类

$gini=1-\sum(p_i^2)$,表示每个类别出现的概率和与1的差值,
分类问题:$argmax(Gini-GiniLeft-GiniRight)$
回归问题:$argmax(Var-VarLeft-VarRight)$

查找最佳特征f已经最佳属性阈值th 小于th的在左边,大于th的在右边子树

优缺点

  1. 能够处理大量特征的分类,并且还不用做特征选择
  2. 在训练完成之后能给出哪些feature的比较重要
  3. 训练速度很快
  4. 很容易并行
  5. 实现相对来说较为简单

GBDT, GBRT

首先说明一下,GBRT这个算法有很多名字,但都是同一个算法: GBRT (Gradient BoostRegression Tree) 渐进梯度回归树 GBDT (Gradient BoostDecision Tree) 渐进梯度决策树 MART (MultipleAdditive Regression Tree) 多决策回归树 Tree Net决策树网络

GBDT的精髓在于训练的时候都是以上一颗树的残差为目标,这个残差就是上一个树的预测值与真实值的差值。

比如,当前样本年龄是18岁,那么第一颗会去按18岁来训练,但是训练完之后预测的年龄为12岁,差值为6,
所以第二颗树的会以6岁来进行训练,假如训练完之后预测出来的结果为6,那么两棵树累加起来就是真实年龄了,
但是假如第二颗树预测出来的结果是5,那么剩余的残差1就会交给第三个树去训练。

单决策树C4.5由于功能太简单,并且非常容易出现过拟合的现象,于是引申出了许多变种决策树,就是将单决策树进行模型组合,形成多决策树,比较典型的就是迭代决策树GBRT和随机森林RF。

GBRT是回归树,不是分类树。其核心就在于,每一棵树是从之前所有树的残差中来学习的。为了防止过拟合,和Adaboosting一样,也加入了boosting这一项。

提起决策树(DT, DecisionTree)不要只想到C4.5单分类决策树,GBRT不是分类树而是回归树! 决策树分为回归树和分类树:

  • 回归树用于预测实数值,如明天温度、用户年龄
  • 分类树用于分类标签值,如晴天/阴天/雾/雨、用户性别

Boosting的好处就是每一步的参加就是变相了增加了分错instance的权重,而对已经对的instance趋向于0,这样后面的树就可以更加关注错分的instance的训练了

偏差(bias)和方差(variance)

其实就机器学习算法来说,其泛化误差可以分解为两部分,偏差(bias)和方差(variance)。
这个可由下图的式子导出(这里用到了概率论公式$D(X)=E(X^2)-[E(X)]^2$)。
偏差指的是算法的期望预测与真实预测之间的偏差程度,反应了模型本身的拟合能力;方差度量了同等大小的训练集的变动导致学习性能的变化,刻画了数据扰动所导致的影响。

Shrinkage

Shrinkage认为,每次走一小步逐步逼近的结果要比每次迈一大步逼近结果更加容易避免过拟合。

就像我们做互联网,总是先解决60%用户的需求凑合着,再解决35%用户的需求,最后才关注那5%人的需求,这样就能逐渐把产品做好.

调参

  1. 树的个数 100~10000
  2. 叶子的深度 3~8
  3. 学习速率 0.01~1
  4. 叶子上最大节点树 20
  5. 训练采样比例 0.5~1
  6. 训练特征采样比例 sqrt(num)

优缺点:

优点:

  1. 精度高
  2. 能处理非线性数据
  3. 能处理多特征类型
  4. 适合低维稠密数据

缺点:

  1. 并行麻烦(因为上下两颗树有联系)
  2. 多分类的时候 复杂度很大

BP

最小二乘法

最小二乘法是一种数学的优化技术,通过求最小化平方误差来寻找最佳的函数匹配
假设现在有二维的观测数据$(x_1,y_1),(x_2,y_2)…(x_n,y_n)$,求$y=a+bx$的拟合。

现设 $yi=a+b*x_i+k_i$ 如果有 $a,b$ 能得到$\sum_{i=1}^{N}(|ki|)$最小,则该线比较理想
所以先变为求$min(\sum_{i=1}^{N}(k_i))$ ,这个与$min(\sum_{i=1}^{N}(k_i^2))$等价
而$k_i=y_i-(a+b*x_i)$
那么现设$f=\sum_{i=1}{N}\left((y_i-(a+b*x_i))^2\right)$
求其最小即可

上述就是最小二乘原则,估计$a,b$的方法称为最小二乘法

先求$f$
对$a,b$的偏导:
$$\triangledown_af=-2*\sum_{i=1}^{N}\left(y_i-(a+b*x_i)\right)=0 \\ \triangledown_bf=-2*xi*\sum_{i=1}^{N}\left(y_i-(a+b*x_i)\right)=0$$
现设:
$$X=\frac{\sum_{i=1}^{N}x_i}{N} \\ Y=\frac{\sum_{i=1}^{N}y_i}{N}$$
则代入上述偏导:
$$a*N+b*N*X=N*Y \\ a*N*X+b*\sum_{i=1}^{N}(x_i^2)=\sum_{i=1}^{N}(x_i*y_i)$$
求该行列式:
$$\begin{vmatrix} N&N*X \\ N*X& \sum_{i=1}^{N}x_i^2 \end{vmatrix} =N*\sum_{i=1}^N((x_i-X))!=0$$
所以有唯一解

最后记:
$$l(xx) = \sum_{i=1}^N(x_i-X)^2 \\ l(yy) = \sum_{i=1}^N(y_i-Y)^2 \\ l(xy) = \sum_{i=1}^N((x_i-X)(y_i-Y))$$

百度文库-最小二乘法

EM

EM用于隐含变量的概率模型的极大似然估计,它一般分为两步:第一步求期望(E),第二步求极大(M),如果概率模型的变量都是观测变量,那么给定数据之后就可以直接使用极大似然法或者贝叶斯估计模型参数。但是当模型含有隐含变量的时候就不能简单的用这些方法来估计,EM就是一种含有隐含变量的概率模型参数的极大似然估计法。

应用到的地方:混合高斯模型、混合朴素贝叶斯模型、因子分析模型

Bagging

  1. 从N样本中有放回的采样N个样本
  2. 对这N个样本在全属性上建立分类器(CART,SVM)
  3. 重复上面的步骤,建立m个分类器
  4. 预测的时候使用投票的方法得到结果

Boosting

boosting在训练的时候会给样本加一个权重,然后使loss function尽量去考虑那些分错类的样本(比如给分错类的样本的权重值加大)

凸优化

在机器学习中往往是最终要求解某个函数的最优值,但是一般情况下,任意一个函数的最优值求解比较困难,但是对于凸函数来说就可以有效的求解出全局最优值。

凸集

一个集合C是,当前仅当任意x,y属于C且$0 \leq \Theta \leq 1$,都有$\Theta*x+(1-\Theta)*y$属于C
用通俗的话来说C集合线段上的任意两点也在C集合中

凸函数

一个函数f其定义域(D(f))是凸集,并且对任意x,y属于D(f)和$0 \leq \Theta \leq 1$都有$f(\Theta*x+(1-\Theta)*y) \leq \Theta*f(x)+(1-\Theta)*f(y)$

用通俗的话来说就是曲线上任意两点的割线都在曲线的上方

常见的凸函数有:

  • 指数函数$f(x)=a^x ; a>1$
  • 负对数函数$-logax ;a>1,x>0$
  • 开口向上的二次函数等

凸函数的判定:

  1. 如果f是一阶可导,对于任意数据域内的x,y满足$f(y) \geq f(x)+f’(x)(y-x)$
  2. 如果f是二阶可导,

凸优化应用举例

  • SVM:其中由$max|w|$转向$min(\frac{1}{2}*|w|^2)$
  • 最小二乘法?
  • LR的损失函数$\sum\left(y_i*log(h_w(x_i))+(1-y_i)*(log(1-h_w(x_i)))\right)$

过拟合

模型过拟合的一个原因是对于给定的训练集数据,模型过于复杂,常用的减小泛化误差的做法包括:

  1. 收集更多的训练集数据
  2. 正则化,即引入模型复杂度的惩罚项
  3. 选择一个简单点的模型,参数少一点的
  4. 降低数据的维度

怎样找到bias-variance之间的平衡,常用的方法是正则化(regularization)。正则化是解决特征共线性、过滤数据中噪音和防止过 拟合的有用方法。正则化背后的原理是引入额外的信息(偏差)来惩罚过大的权重参数。最常见的形式就是所谓的L2正则(L2 regularization,有时也被称为权重衰减,L2收缩)

如果我们减小C的值,也就是增大正则系数的值,正则化项的威力也增强。

正则化的两种方法

参考[6]

由于模型的参数个数一般是由人为指定和调节的,所以正则化常常是用来限制模型参数值不要过大,也被称为惩罚项。一般是在目标函数(经验风险)中加上一个正则化项$\Phi(w)$。在LR中即

$J(w)=-\frac{1}{N} \sum_{i=1}^N{\left(y_i*log(h_w(x_i))+(1-y_i)*log(1-h_w(x_i))\right)} + \lambda \Phi(w)$

而这个正则化项一般会采用L1范数或者L2范数。其形式分别为$\Phi(w)=||w||_1$和$\Phi(w)=||w||_2$。

首先针对L1范数$\Phi(w)=||w||_1$,当采用梯度下降方式来优化目标函数时,对目标函数进行求导,正则化项导致的梯度变化当$w_j>0$是取1,当$w_j<0$时取-1.

因此当$w_j$大于0的时候,$w_j$会减去一个正数,导致$w_j$减小,而当$w_j$小于0的时候,$w_j$会减去一个负数,导致$w_j$又变大,因此这个正则项会导致参数$w_j$取值趋近于0,也就是为什么L1正则能够使权重稀疏,这样参数值就受到控制会趋近于0。L1正则还被称为 Lasso regularization。

然后针对L2范数$\Phi(w)=||w||_2=\sum_j w_j^2$,同样对它求导,得到梯度变化为$\frac{\partial \Phi(w)}{\partial w_j}=2w_j$(一般会用$\frac{\lambda}{2}$来把这个系数2给消掉)。同样的更新之后使得$w_j$的值不会变得特别大。在机器学习中也将L2正则称为weight decay,在回归问题中,关于L2正则的回归还被称为Ridge Regression岭回归。weight decay还有一个好处,它使得目标函数变为凸函数,梯度下降法和L-BFGS都能收敛到全局最优解。

需要注意的是,L1正则化会导致参数值变为0,但是L2却只会使得参数值减小,这是因为L1的导数是固定的,参数值每次的改变量是固定的,而L2会由于自己变小改变量也变小。而(12)式中的λ
也有着很重要的作用,它在权衡拟合能力和泛化能力对整个模型的影响,$\lambda$越大,对参数值惩罚越大,泛化能力越好。

此外,从贝叶斯的角度而言,正则化项实际上是给了模型一个先验知识,L2正则相当于添加了一个均值为0协方差为$\frac{1}{\lambda}$的高斯分布先验(将L2正则表示为$\frac{\lambda}{2}w^Tw$),当$\lambda$为0,即不添加正则项,那么可以看成协方差是无穷大,w可以不受控制变成任意大。当$\lambda$越大,即协方差越小,那么参数值的取值方差会变小,模型会趋向于稳定

统一特征取值范围

特征缩放(feature scaling)是预处理阶段的关键步骤,但常常被遗忘。虽然存在决策树和随机森林这种是少数不需要特征缩放的机器学习算法,但对于大部分机器学习算法和优化算法来说,如果特征都在同一范围内,会获得更好的结果。比如梯度下降法。

特征缩放的重要性可以通过一个简单的示例解释。假设我们有两个特征,一个特征的取值范围是 [1,10],另一个特征的取值范围是[1,100000]。我们使用Adaline中的平方误差函数,很明显,权重更新时会主要根据第二维度特征,这就 使得在权重更新过程中第一个特征的话语权很小。另一个例子是如果kNN算法用欧氏距离作为距离度量,第二维度特征也占据了主要的话语权。

有两种方法能使不同的特征有相同的取值范围:归一化(normalization)和标准化 (standardization)。两种方法还是有必要区分一下的。归一化指的是将特征范围缩放到[0,1],是最小-最大缩放(min-max scaling)的特例。为了得到归一化结果,我们对每一个特征应用最小-最大缩放

虽然归一化方法简单,但相对来说,标准化对于大部分机器学习算法更实用。原因是大部分线性模型比如逻辑斯蒂回归和线性SVM在初始化权重参数时,要么选择0要么选择一个接近0的随机数。实用标准化,我们能将特征值缩放到以0为中心,标准差为1,换句话说,标准化后的特征形式服从正态分布,这样学习权重参数更容易。此外,标准化后的数据保持了异常值中的有用信息,使得算法对异常值不太敏感,这一点归一化就无法保证。

选择有意义的特征

L2正则项是权重参数的平方和,而L1正则项是权重参数的绝对值和。相对于L2, L1正则项趋向于得到稀疏特征向量,即很多特征权重参数为0.如果数据集的特征维度很高且特征不相干(极端情况是 不相干的特征维度数目比训练样本数还大),特征稀疏性是非常有用的。 由于很多特征权重为0,所以,很多人也把L1正则看做特征选择的一种方式。

L1正则将不相干特征变为0,使用SBS算法进行特征选择

PCA进行无监督降维

PCA(principal component analysis, 主成分分析)是一种被广泛使用的无监督的线性转换技术,主要用于降维。其他领域的应用还包括探索数据分析和股票交易的信号去噪,基因数据分析和基因表达。

PCA根据特征之间的相关性帮助我们确定数据中存在的模式。简而言之,PCA的目标是找到高维数据中最大方差的方向,并且将高维数据映射到一个新的子空间,这个子空间的方向不大于原始特征空间。新子空间的正交轴(主成分)可以被解释为原始空间的最大方差方向。

PCA的步骤:

  1. 将d维度原始数据标准化。
  2. 构建协方差矩阵。
  3. 求解协方差矩阵的特征向量和特征值。
  4. 选择值最大的k个特征值对应的特征向量,k就是新特征空间的维度,k<<d。
  5. 利用k特征向量构建映射矩阵$W$。
  6. 将原始d维度的数据集X,通过映射矩阵W转换到k维度的特征子空间。

LDA进行监督数据压缩

LDA(linear discriminant analysis, 线性判别分析)是另一种用于特征抽取的技术,它可以提高计算效率,对于非正则模型也能减小过拟合。

虽然LDA的很多概念和PCA很像,但他俩的目标不同,PCA目标是找到正交的主成分同时保持 数据集的最大方差,LDA的目标是为每个类单独优化,得到各个类的最优特征子集。PCA和LDA都是线性转换技术,用于数据压缩,前者是无监算法,后者是 监督算法。看到监督两个字,可能你会认为对于分类任务,LDA要比PCA效果更好,但实际却不是这样,在某些分类任务情境下,用PCA预处理数据得到的结 果要比LDA号,比如,如果每个类含有的样本比较少。

LDA 的一个假设是数据服从正态分布。同时,我们也假设各个类含有相同的协方差矩阵,每个特征都统计独立。即使真实数据可能不服从上面的某几个假设,但LDA依然具有很好的表现。

我们在应用LDA时做出的假设是:特征服从正态分布并且彼此独立,每个类的协方差矩阵都相同。现实中的数据当然不可能真的全部服从这些假设,但是不用担心,即使某一个甚至多个假设不成立,LDA也有不俗的表现.

学习LDA内部原理前,我们先将它的几大步骤列出来:

  1. 将d维度原始数据进行标准化.
  2. 对每一个类,计算d维度的平均向量.
  3. 构建类间(between-class)散点矩阵$S_B$和类内(within-class)散点矩阵$S_W$.
  4. 计算矩阵$S^{-1}_W S_B$的特征向量和特征值.
  5. 选择值最大的前k个特征值对应的特征向量,构建d*d维度的转换矩阵$W$,每一个特征向量$W$是的一列.
  6. 使用矩阵$W$将原始数据集映射到新的特征子空间.

验证评估模型性能

两种交叉验证计数,holdout交叉验证和k折交叉验证, 来评估模型的泛化能力。

评估模型泛化能力的典型方法是holdout交叉验证(holdout cross validation)。holdout方法很简单,我们只需要将原始数据集分割为训练集和测试集,前者用于训练模型,后者用于评估模型的性能。

更好的holdout方法是将原始训练集分为三部分:训练集、验证集和测试集。训练机用于训练不同的模型,验证集用于模型选择。而测试集由于在训练模型和模型选择这两步都没有用到,对于模型来说是未知数据,因此可以用于评估模型的泛化能力。

当然holdout方法也有明显的缺点,它对数据分割的方式很敏感,如果原始数据集分割不当,这包括训练集、验证集和测试集的样本数比例,以及分割后数据的分布情况是否和原始数据集分布情况相同等等。所以,不同的分割方式可能得到不同的最优模型参数。

k折交叉验证,即重复k次holdout方法提高鲁棒性。

  1. k折交叉验证的过程,第一步我们使用不重复抽样将原始数据随机分为k份,第二步 k-1份数据用于模型训练,剩下那一份数据用于测试模型。然后重复第二步k次,我们就得到了k个模型和他的评估结果(译者注:为了减小由于数据分割引入的 误差,通常k折交叉验证要随机使用不同的划分方法重复p次,常见的有10次10折交叉验证)。
  2. 然后我们计算k折交叉验证结果的平均值作为参数/模型的性能评估。使用k折交叉验证来寻找最优参数要比holdout方法更稳定。一旦我们找到最优参数,要使用这组参数在原始数据集上训练模型作为最终的模型。
  3. k折交叉验证使用不重复采样,优点是每个样本只会在训练集或测试中出现一次,这样得到的模型评估结果有更低的方法。

频率派与贝叶斯派各自不同的思考方式

  • 频率派把需要推断的参数θ看做是固定的未知常数,即概率虽然是未知的,但最起码是确定的一个值,同时,样本$X$ 是随机的,所以频率派重点研究样本空间,大部分的概率计算都是针对样本$X$ 的分布;

  • 而贝叶斯派的观点则截然相反,他们认为待估计的参数$\theta $ 是随机变量,服从一定的分布,而样本$X$ 是固定的,由于样本是固定的,所以他们重点研究的是参数$\theta $的分布。

参考

[1]. 算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)
[2]. Logistic Regression—逻辑回归算法汇总**
[3]. Stanford机器学习—-第三讲. 逻辑回归和过拟合问题的解决 logistic Regression & Regularization
[4]. Softmax回归
[5]. 《统计学习方法》.李航
[6]. 【机器学习算法系列之二】浅析Logistic Regression