异常检测(Anomaly Detection)

机器学习初学者，原本是写来自己看的，写的比较随意。难免有错误，还请大家批评指正！对其中不清楚的地方可以留言，我会及时更正修改

[参考请点击这里]

异常检测是机器学习算法的常见应用，它主要用于非监督学习问题，但从某些角度看，又十分类似一些监督学习问题。
假设我们有m个样本x(1)…x(m)都是正常的，我们需要一个算法告诉我们，新样本xtest是不是正常的，即这个新样本是否异常。这里使用的方式是对已有的无标签样本数据进行建模p(x)，也可以理解成是对x的分布概率进行建模。模型建立之后，对于新样本xtest，如果它的概率p小于某个阈值ϵ，它就被标记为异常。
异常检测可以应用在欺诈检测，飞机引擎参数检测，数据中心的计算机监控等。

高斯分布Gaussian Distribution

又常称作正太分布Normal Distribution，其分布函数可以描述为x∼N(μ,σ2)，其中μ称作均值，是曲线的中心，σ2称作方差，亦即σ是标准差。完整的分布函数描述为：

算法

给定训练集{x(1),…,x(m)}，每个样本是一个向量，即x∈Rn。则异常检测算法的模型表示为：

其中，μj=1m∑i=1mx(i)j,σ2j=1m∑i=1m(x(i)j−μj)2。因此，p(x)也可以写作

当计算出的p(x)<ϵ时，标记为异常。这种估计p(x)分布的问题，通常被称作密度估计问题。

开发和评估异常检测系统

评估我们的学习算法，首先要获得一些标记好的数据，将其分成异常样本（y=1）和非异常样本（y=0）。在进行训练时，使用大量的正常样本，剩余的正常样本和异常样本供交叉验证集和测试集使用。通常，将正常样本按照6:2:2的比例进行分配，异常样本按照1:1的比例分到交叉验证机和训练集中。如下图：

由于我们的样本是偏斜的（如单独预测y=0就可以得到很高的准确率），因此，这里常使用精确率、召回率、F1值等方法进行算法评估（详见“机器学习系统设计”章节）。
注：我们使用交叉验证集来选择阈值ϵ

异常检测VS监督学习

使用异常检测
- 样本中有很少的正样本即异常样本（0-20），和大量的负样本。
- 异常类型比较多样，对于任何机器学习算法，都很难从正样本中学习得到出现异常的规律，亦即很难预测异常的产生。未来的样本参数规律可能跟训练样本的任何一个都不相似。

使用监督学习
- 有大量的正负样本，训练集可以被均匀的分成两类
- 有足够的正样本可以帮助我们对正样本的产生和规律有一定了解。未来的样本可能跟训练样本的某一个非常相似。

选择合适的特征

特征的选择对异常检测算法的影响很大，由于我们的算法使用的是高斯分布模型，因此我们希望选取的特征也能够满足高斯分布。可以通过绘制特征的直方图来判断特征的分布情况，对于不满足高斯分布的特征，可以进行log(x+c),x1/2等方式进行变换，使其满足高斯分布。
通常，我们希望p(x)对异常样本给出一个较低的概率，对正常样本给出一个较高的概率，但当p(x)对这两种样本给出的概率差不多时，就需要仔细检查那些给出较高概率的异常样本，找出一些新的特征能够区分两种数据。
在选择特征的过程中，通常选择那些值不太大，也不太小的特征。

多元高斯分布

与之前分别建模p(x1),p(x2)…不同，我们直接对p(x)进行建模：

其中μ∈Rn,Σ∈Rn×n，这个模型可以建模椭圆形高斯曲线轮廓。μ决定了图形的中心，Σ决定了图形的形状，宽度，及轴线的方向等参数。
之前的模型只是该模型的一个特例，它的轴线方向与坐标轴平行。
多元高斯分布可以自动捕捉不同特征之间的相互关系。

推荐系统(Recommender System)

[参考请点击这里]

推荐是机器学习的一个很流行的应用，我们考虑用户给电影进行评分的案例，每个用户都会对一部分电影进行评分，我们根据已评的分数来推测该用户对其他电影的评分，进而给用户进行电影推荐。

先定义以下参数：
nu= 用户总数
nm= 电影总数
r(i,j)=1 如果用户j对电影i进行了评分
y(i,j)= 用户j对电影i评的分数（r(i,j)=1时）

基于文本的推荐Content Based Recommendations

我们引入两个特征x1,x2，分别代表电影是爱情片或动作片的程度，取值0-1。一个方法就是我们对每个没用进行线性回归，得到参数θ(j)∈R3，预测用户j对电影i的评分(θ(j))Tx(i)。
学习θ(j)，与线性回归类似，有下式：
minθ(j)=12∑i:r(i,j)=1((θ(j))T(x(i))−y(i,j))2+λ2∑k=1n(θ(j)k)2
得到所有用户的参数，参考下式：
minθ(1),…,θ(nu)=12∑j=1nu∑i:r(i,j)=1((θ(j))T(x(i))−y(i,j))2+λ2∑j=1nu∑k=1n(θ(j)k)2
我们可以使用之前学过的梯度下降算法优化上式。

协同过滤Collaborative Filtering

很多时候，我们很难对一部电影给出一个爱情程度或动作程度的参数。为解决这个问题，我们可以让用户告诉我们他们喜欢那些种类的电影，直接提供参数向量。从给定的参数中推测特征，我们对所有用户使用正则化的平方误差函数：
minx(1),…,x(nm)12∑i=1nm∑j:r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2∑i=1nm∑k=1n(x(i)k)2
也可以随机猜测用户的特征参数，对该参数进行迭代优化，最终收敛到一组很好的特征。

算法实现

根据前两节的内容，我们知道，如果给定电影特征，我们可以使用这个资料去获得用户参数；相反，如果给定用户参数数据，我们也可以使用这些资料获得电影特征。将这些概念合并，就形成了我们的协同过滤算法。其模型如下：
J(x,θ)=12∑(i,j):r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2∑i=1nm∑k=1n(x(i)k)2+λ2∑j=1nu∑k=1n(θ(j)k)2
通过比较可以明显看出，这个模型只是上两节模型的组合。这个模型可以自己学习。在该模型中，偏差单元x0=1这一项被移除，因此有x∈Rn,θ∈Rn
算法执行步骤如下：
1 将x(i),...,x(nm),θ(1),...,θ(nu)初始化成较小的随机值。随机初始化可以打破对称，保证算法学习到彼此不同的特征。
2 使用梯度下降（或其他优化算法）最小化代价函数J(x(i),...,x(nm),θ(1),...,θ(nu))，即前述的j(x,θ)，对每个j=1,...,nu,i=1,...nm
x(i)k:=x(i)k−α⎛⎝∑j:r(i,j)=1((θ(j))Tx(i)−y(i,j))θ(j)k+λx(i)k⎞⎠
θ(j)k:=θ(j)k−α⎛⎝∑i:r(i,j)=1((θ(j))Tx(i)−y(i,j))x(i)k+λθ(j)k⎞⎠
3 对参数为θ的用户，和特征为x的电影，预测评分θTx。

向量化：低秩矩阵分解Low Rank Matrix Factorization

给定矩阵X（每行包含电影特征）和Θ（每行包含用户特征），则预测矩阵Y可以表示成Y=XΘT，如下图

预测产品i和j的相似程度，可以使用它们之间的欧式距离来衡量，亦即我们要寻找||x(i)−x(j)||的较小值。

均值归一化Mean Normalization

我们考虑一个用户没有给任何电影评分的例子，回头看我们的协同过滤算法，为了使正则项最小化，它会使这个用户的参数θ变成一个零向量，显然，这不是我们想要的结果。使用均值归一化可以帮助解决类似的问题。
首先，我们使用矩阵Y表示先前的评分矩阵，定义向量μ=[μ1,μ2,…,μnm]，其中μi=∑j:r(i,j)=1Yi,j∑jr(i,j)
其实就是对每行的评分进行了均值，如下例：
Y=⎡⎣⎢⎢⎢54005?000?550040⎤⎦⎥⎥⎥
μ=⎡⎣⎢⎢⎢2.522.251.25⎤⎦⎥⎥⎥
Y′=Y−μ=⎡⎣⎢⎢⎢2.52−.2.25−1.252.5?−2.25−1.25−2.5?3.753.75−2.5−21.25−1.25⎤⎦⎥⎥⎥
上述预处理过称完毕后，我们新的预测函数变成：(θ(j))Tx(i)+μi。回到我们之前说的没有打分的例子，通过新的预测函数处理后，预测出来的评分就等于向量μ。相当于使用已有数据的均值对未知用户进行了预测。