机器学习之回归算法&异常检测算法
机器学习的定义
（Arthur Samuel）在进行特定编程的情况下，给予计算机学习能力的领域。
（Tom Mitchell）一个程序被认为能从经验（Experience，E)中学习，解决任务(Task,T)，达到性能度量值(preference，P），有了经验E后，经过P评判，程序在处理T时的性能有所提升。
监督学习：监督学习指的就是我们给学习算法一个数据集。这个数据集由“正确答案”组成。
无监督学习：数据集中没有任何的标签，没有提前告知算法一些信息。
单变量线性回归
相关符号:
m代表训练集中实例的数量
x代表特征/输入变量
y代表目标变量/输出变量
(x,y)代表训练集中的实例
$(x^{(i)},y^{(i)})$代表第$i$个观察实例
h为hypothesis（假设）,假设函数，在这一节记为$h_{\theta \ }(x)=\theta \ _0+\theta \ _1x$
为了找到最好的回归直线，我们要使得代价函数
$$
J(\theta \ _0,\theta \ _1)=\frac{1}{2m}\sum {i=1}^{\ m}(h{\theta \ }(x^{(i)})-y^{(i)}\ )^2
$$
最小。（这是回归中常用的代价函数，故又被称为平方误差代价函数，square error function）
梯度下降法是一个比较常用的方法。
多变量线性回归
我们引入一系列新的注释：
$n$ 代表特征的数量
$x^{( i )}$代表第 $i$ 个训练实例，是特征矩阵中的第$i$行，是一个向量（vector）。
在多变量线性回归中，
$$
h_{\theta}( x )=\theta^TX={\theta_{0}}+{\theta_{1}}{x_{1}}+{\theta_{2}}{x_{2}}+…+{\theta_{n}}{x_{n}}
$$
代价函数：
$$
J( {\theta_{0}},{\theta_{1}}…{\theta_{n}} )=\frac{1}{2m}\sum\limits_{i=1}^{m}{( h_\theta (X^{( i )})-{y}^{( i )} )}^{2}
$$
当使用梯度下降法时：
在我们面对多维特征问题的时候，我们要保证这些特征都具有相近的尺度，这将帮助梯度下降算法更快地收敛。
最简单的方法是令：${x_n}=\frac{x_n-\mu_n}{s_n}$，其中 ${\mu_n}$是平均值，${s_n}$是标准差(极差也行)。
使用正规方程：
假设我们的训练集特征矩阵为 $X$（包含了 ${X_{0}}=1$）并且我们的训练集结果为向量 $y$，则利用正规方程解出向量:
$$
\theta =( X^T X )^{-1}{X^T}y
$$
梯度下降与正规方程的比较：
| 梯度下降 | 正规方程 |
|---|---|
| 需要选择学习率$\alpha$ | 不需要 |
| 需要多次迭代 | 一次运算得出 |
| 当特征数量$n$大时也能较好适用 | 需要计算$(X^TX )^{-1}$ 如果特征数量n较大则运算代价大，因为矩阵逆的计算时间复杂度为$O( n^{3} )$，通常来说当$n$小于10000 时还是可以接受的 |
| 适用于各种类型的模型 | 只适用于线性模型，不适合逻辑回归模型等其他模型梯度下降与正规方程的比较： |
若$(X^T X)^-1$不可逆的情况:
(1)首先，看特征值里是否有一些多余的特征，像这些${x_1}$和${x_2}$是线性相关的，互为线性函数。同时，当有一些多余的特征时，可以删除这两个重复特征里的其中一个，无须两个特征同时保留，将解决不可逆性的问题。
(2)正规化方法
(3)直接使用伪逆(pseudoinverse）,有时被称为广义逆（Generalized inverse）。定义：A* B* A=A，则B是A的广义逆矩阵。所有的矩阵都存在逆矩阵。若一矩阵存在逆矩阵，则其逆矩阵即为其唯一的广义逆矩阵。Matlab的伪逆函数是pinv(逆矩阵函数为inv），可以证明：使用伪逆，以下式子任成立
$$
\theta =( X^T X )^{-1}{X^T}y
$$
逻辑回归 (Logistic Regression)
简单而言，即将数据分类划分为离散的值{0,1}。
我们将因变量(dependent variable)可能属于的两个类分别称为负向类（negative class）和正向类（positive class），则因变量y∈ {0,1}，其中 0 表示负向类，1 表示正向类。
我们引入一个新的模型，逻辑回归，该模型的输出变量范围始终在0和1之间。
逻辑回归模型的假设是： $h_\theta ( x )=g(\theta^{T}X )$
其中：
$X$ 代表特征向量
$g$ 代表逻辑函数（logistic function)是一个常用的逻辑函数为S形函数（Sigmoid function），公式为： $g( z )=\frac{1}{1+e^{-z}}$。
该函数的图像为：
$h_\theta ( x )$的作用是，对于给定的输入变量，根据选择的参数计算输出变量=1的可能性（estimated probablity）即$h_\theta ( x )=P( y=1|x;\theta )$
例如，如果对于给定的$x$，通过已经确定的参数计算得出$h_\theta ( x )=0.7$，则表示有70%的几率$y$为正向类，相应地$y$为负向类的几率为1-0.7=0.3。
代价函数：
若按照原来的公式，我们得到的代价函数将是一个非凸函数（non-convexfunction）。
这意味着我们的代价函数有许多局部最小值，这将影响梯度下降算法寻找全局最小值。
故我们重新定义逻辑回归的代价函数为:
$$
J(\theta )=\frac{1}{m}\sum \limits_{i=1}^m Cost(h _\theta( {x}^{( i )} ),y^{( i )})
$$
其中
${h_\theta}( x )$与 $Cost( {h_\theta}( x ),y )$之间的关系如下图所示：
将构建的 $Cost( {h_\theta}( x ),y )$简化如下：
$Cost( {h_\theta}( x ),y )=-y\times log( {h_\theta}( x ) )-(1-y)\times log( 1-{h_\theta}( x ) )$
带入代价函数得到：
$J( \theta )=\frac{1}{m}\sum\limits_{i=1}^{m}{[-y^{(i)}\log ( {h_\theta}( x^{(i)} ) )-( 1-y^{(i)} )\log ( 1-{h_\theta}( x^{(i)} ) )]}$
即：$J( \theta )=-\frac{1}{m}\sum\limits_{i=1}^{m}{[y^{(i)}\log ( {h_\theta}( x^{(i)} ) )+( 1-y^{(i)} )\log ( 1-{h_\theta}( x^{(i)} ) )]}$
一对多的情况：
我们只需分别多次如右上角的操作，可化归为分成两类的逻辑回归。
正规化
我们已经学了几种算法，如最小二乘法（Ordinary Least Squares,OLS)。我们所学的算法不足之处是随着特征维度的增加会出现线性模型的过度拟合。
过拟合解决方案：
-
丢弃一些不能帮助我们正确预测的特征。可以是手工选择保留哪些特征，或者使用一些模型选择的算法来帮忙（例如PCA）
-
正则化。 保留所有的特征，但是减少参数的大小（magnitude）。
正则化：
我们可以修改代价函数，增加几个惩罚项。比如将代价函数写成：
$$
J\left( \theta \right)=\frac{1}{2m}[\sum\limits_{i=1}^{m}({h_\theta}(x^{(i)})-y^{(i)})^{2}+\lambda \sum\limits_{j=1}^{n}{\theta_j^2}]
$$
其中$\lambda $又称为正则化参数（Regularization Parameter）。 注：根据惯例，我们不对${\theta_{0}}$ 进行惩罚。事实上其也被称为岭回归：（Ridge Regression），由俄罗斯科学家Tikhonov 提出的对OLS的改进。$\lambda \sum\limits_{j=1}^{n}{\theta_j^2}$被称为L2惩罚项（L2 Penalty）。
附：Lasso回归：
与岭回归类似：
$$
\lambda \sum\limits_{j=1}^{n}{\theta_j^2}改为\lambda \sum\limits_{j=1}^{n}{|\theta_j|}
$$
相应地，$\lambda \sum\limits_{j=1}^{n}{|\theta_j|}$被称为L1惩罚项。
在这里，我们展示只讨论岭回归。
我们也利用正规方程来求解正则化线性回归模型：
图中的矩阵尺寸为 （n+1）*(n+1)。
同样对于逻辑回归，我们也给代价函数增加一个正则化的表达式，得到代价函数：
$$
J(\theta)=\frac{1}{m}\sum\limits_{i=1}^{m}{[-y^{(i)}\log (h_\theta( x^{(i)}) )-( 1-y^{(i)} )\log ( 1-{h_\theta}( x^{(i)}) )]}+\frac{\lambda }{2m}\sum\limits_{j=1}^{n}\theta _j ^2
$$
异常检测算法
异常检测算法(Anomaly detection)主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题。
正如其名，异常检测算法根据一堆无标签数据中的样本点检测另一个数据点是否异常。
异常检测算法用到了高斯分布。
算法流程：
我们可以利用已有的数据来预测总体中的$μ$和$σ^2$的计算方法如下：
$$
\mu=\frac{1}{m}\sum\limits_{i=1}^mx^{(i)}\
\sigma^2=\frac{1}{m}\sum\limits_{i=1}^m(x^{(i)}-\mu)^2
$$
一旦我们获得了平均值和方差的估计值，给定新的一个训练实例，根据模型计算 $p(x)$：
$$
p(x)=\prod\limits_{j=1}^np(x_j;\mu_j,\sigma_j^2)=\prod\limits_{j=1}^1\frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2})
$$
当$p(x) < \varepsilon$时，为异常。
下图是一个由两个特征的训练集，以及特征的分布情况：
下面的三维图表表示的是密度估计函数，$z$轴为根据两个特征的值所估计$p(x)$值：
接下来的具体评价方法如下：
- 根据测试集数据，我们估计特征的平均值和方差并构建$p(x)$函数
- 对交叉检验集，我们尝试使用不同的$\varepsilon$值作为阀值，并预测数据是否异常，根据$F1$值或者查准率与查全率的比例来选择 $\varepsilon$
- 选出 $\varepsilon$ 后，针对测试集进行预测，计算异常检验系统的$F1$值，或者查准率与查全率之比
F1值：
为了能够评价不同算法的优劣，在Precision和Recall的基础上提出了F1值的概念，来对Precision和Recall进行整体评价。F1的定义如下：
F1值 = 正确率 * 召回率 * 2 / (正确率 + 召回率)
$F_1={(\frac{recall^{-1}+precision^{-1}}{2})}^{-1}=2* \frac{precision * recall}{precision+recall}$
除此，还可以利用多元高斯分布
**多元高斯分布:
假使我们有两个相关的特征，而且这两个特征的值域范围比较宽，这种情况下，一般的高斯分布模型可能不能很好地识别异常数据。其原因在于，一般的高斯分布模型尝试的是去同时抓住两个特征的偏差，因此创造出一个比较大的判定边界。
下图中是两个相关特征，洋红色的线（根据ε的不同其范围可大可小）是一般的高斯分布模型获得的判定边界，很明显绿色的X所代表的数据点很可能是异常值，但是其$p(x)$值却仍然在正常范围内。多元高斯分布将创建像图中蓝色曲线所示的判定边界。
在多元高斯分布模型中，我们将协方差矩阵形式的高斯分布函数，用所有的特征一起来计算 $p(x)$。
我们首先计算所有特征的平均值，然后再计算协方差矩阵：
$p(x)=\prod_{j=1}^np(x_j;\mu,\sigma_j^2)=\prod_{j=1}^n\frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2})$
$\mu=\frac{1}{m}\sum_{i=1}^mx^{(i)}$
$\Sigma = \frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu)(x^{(i)}-\mu)^T=\frac{1}{m}(X-\mu)^T(X-\mu)$
注:其中$\mu $ 是一个向量，其每一个单元都是原特征矩阵中一行数据的均值。最后我们计算多元高斯分布的$p\left( x \right)$:
$p(x)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp\left(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\right)$
其中：
$|\Sigma|$是定矩阵，在 Octave 中用 det(sigma)计算
$\Sigma^{-1}$ 是逆矩阵，下面我们来看看协方差矩阵是如何影响模型的：
上图是5个不同的模型，从左往右依次分析：
- 是一个一般的高斯分布模型
- 通过协方差矩阵，令特征1拥有较小的偏差，同时保持特征2的偏差
- 通过协方差矩阵，令特征2拥有较大的偏差，同时保持特征1的偏差
- 通过协方差矩阵，在不改变两个特征的原有偏差的基础上，增加两者之间的正相关性
- 通过协方差矩阵，在不改变两个特征的原有偏差的基础上，增加两者之间的负相关性
多元高斯分布模型与原高斯分布模型的关系：
可以证明的是，原本的高斯分布模型是多元高斯分布模型的一个子集，即像上图中的第1、2、3，3个例子所示，如果协方差矩阵只在对角线的单位上有非零的值时，即为原本的高斯分布模型了。
原高斯分布模型和多元高斯分布模型的比较：
| 原高斯分布模型 | 多元高斯分布模型 |
|---|---|
| 不能捕捉特征之间的相关性 但可以通过将特征进行组合的方法来解决 | 自动捕捉特征之间的相关性 |
| 计算代价低，能适应大规模的特征 | 计算代价较高 训练集较小时也同样适用 |
| 必须要有 ，不然的话协方差矩阵 不可逆的，通常需要 另外特征冗余也会导致协方差矩阵不可逆 |
原高斯分布模型被广泛使用着，如果特征之间在某种程度上存在相互关联的情况，我们可以通过构造新新特征的方法来捕捉这些相关性。
如果训练集不是太大，并且没有太多的特征，我们可以使用多元高斯分布模型。
异常检测与监督学习对比
两者比较：
| 异常检测 | 监督学习 |
|---|---|
| 非常少量的正向类（异常数据 $y=1$）, 大量的负向类（$y=0$） | 同时有大量的正向类和负向类 |
| 许多不同种类的异常，非常难。根据非常 少量的正向类数据来训练算法。 | 有足够多的正向类实例，足够用于训练 算法，未来遇到的正向类实例可能与训练集中的非常近似。 |
| 未来遇到的异常可能与已掌握的异常、非常的不同。 | |
| 例如： 欺诈行为检测 生产（例如飞机引擎）检测数据中心的计算机运行状况 | 例如：邮件过滤器 天气预报 肿瘤分类 |