Anomaly Detection

异常检测算法经常用于非监督学习问题中，有点类似于logistic regression.

examples

Aircraft engine
如上图所示,红色的样本都是经过测试被证明是质量合格的引擎,如果有一个新的引擎称作与质量合格的样本位置接近那么大概率也质量合格,反之此样本可能需要作更进一步的安全测试.

量化来说就是如果就被认为是异常样本,反之正常.调节的值类似调节logistic regression中的Threshold值.

Density estimation

Anomaly Detection还用于欺诈行为识别和manufacturing

more examples

Gaussian((Normal) distribution

正态分布
如果随机变量X服从正态分布,记作X~,则其密度函数为:

Density
其中

被称为数学期望/期望值,被称为方差,被称为标准差 Parameter estimation

Anomaly detection algorithm

Anomaly detection algorithm
1.选择你认为可能会表明样本是一个异常样本的特征,用来筛选异常样本候选者.
2.构造{}样本集合用来训练,上图中的公式向量化可以写作,类似
3.给定新样本x,计算p(x)
符号表示乘积.,即

如果则x被认为是异常样本,值的选取下文会提到.
example
p(x)的函数图类似于上图中的3D图片(特征值n=2).

Developing and evaluating an anomaly detection system

数据准备阶段,如下图,需要
1.Training Set, unlabeled,由正常样本构成
2.Cross validation set, labeled,由正常样本和异常样本混合而成.
3.Test set, labeled,由正常样本和异常样本混合而成.

Data set

举个例子,如下图,不推荐粉色的样本分组方法.一般来说Training/CV/Test分组的样本最好不要重合,避免影响对算法的性能评估.

example Algorithm evaluation
评估一个Anomaly detection algorithm算法的步骤如下:
1.使用training set的样本数据训练出
2.对CV set的样本进行预测,选择Fscore最高时对应的
3.将以及用于Test set观察算法表现.

Anomaly detection vs. supervised learning

Anomaly detection算法实际上也是预测样本的分类,飞机引擎是好的还是坏的;这笔交易是否有欺诈嫌疑等等.那既然如此为什么不使用logistic regression呢?
因为这两个算法针对的场景有细微的差别,如下图所示:

Anomaly detection vs. supervised learning

• Anomaly detection算法适用于异常样本很少的情况下(通常是0-20),并且有大量的正常样本(因为训练p(x)需要的是正常样本).换句话说就是异常样本太少以至于使用监督学习算法无法很好的识别异常样本的特征,但是因为有大量的正常样本反而能很好的训练p(x),所以这种场景使用Anomaly detection更好.

• Supervised learning适用于无论正常样本还是异常样本都很多的情况.

  
  example

Choosing what features to use

如何为Anomaly Detection 算法选择特征使得算法的性能更好呢?
需要思考以下两个方面:
1.选择的特征尽量满足Gaussian distribution.

Non-Gaussian features -> Gaussian features
在octave中我们可以使用hist函数打印特征值的图形,如果特征值的图形不符合Gaussian distribution我们可以使用如下手段:
Tranforms
注意:我们可以对每个特征使用不同的方式变形.

2.选择的特征需要尽可能可以区分正常/异常样本.

Error analysis
一般来说我们会选择特征值要么非常大要么非常小的特征去用于Anomaly Detection算法,更通常的做法是,选择一些特征看看能不能很好的区分,如果不行,观察本该是异常的样本,在挑选新的特征加入算法.但是有时候根据现有的特征无法还是不能够区分出异常样本.
举个例子,如下图所示,你想找出在数据中心中出现特定错误的机器(cpu空转,死循环导致),依靠现有的4个特征值很难将异常机器和正常机器区分开(有可能真的是在执行很耗cpu的任务),此时我们创建一个新特征值,这样就能很明显区分出正常机器和异常机器了. example

Multivariate Gaussian Distribution

Motivating example

之前p(x)的计算方式(分别计算)没法很好的区分CPU低Memory Use高,CPU高Memory Use高两个样本,所以这里需要使用Multivariate Gaussian Distribution,新的p(x)如下:

Multivariate Gaussian Distribution

以下是一些例子:

example1 example2 example3 example4 example5 example6

如果使用example4中间的例子可以区分CPU低Memory Use高,CPU高Memory Use高两种情况.

Anomaly detection using the multivariate Gaussian distribution

Parameter fitting Anomaly detection with multivariate Gaussian Relationship to original model
Gaussian distribution的p(x)是multivariate Gaussian distribution 的特例(是一个n*n的矩阵当满足除对角线之外的元素都为0的时候).
另一个发现是original model的轮廓图始终是与坐标轴对齐的. Original model vs. Multivariate Gaussian

• Original model
  需要创建新的特征(现有特征值的组合)来更好的识别异常值.
  计算成本低(适用于大规模输入,like n=10000)
  training size很小也ok
• Multivariate Gaussian
  无需考虑新建特征值
  计算成本高,求的inverse
  必须满足m>n,否则不可逆(推荐m>=10*n时才使用)

Recommender System

Recommender System Example

Content-based recommender systems

基于内容的推荐系统,以推荐电影为例,根据用户的打分数据和这些分数对应的电影特征去构造hypothesis去预测该用户对没打过分数的电影的打分,然后可以根据分高的推荐.

terms
上图中的可以理解为用户的对不同类型电影的喜好. cost function for user j
,这其实是一个linear regression,带入linear regression的cost function可得recommender system用户j的cost function如上.
cost function for all users
Gradient descent

Collaborative filtering

协同过滤的动机在于(还是拿预测电影评分举例子):电影太多了,如果需要工作人员一个一个去看完然后给出每个电影的特征值太慢而且不现实.所以我们这样想,如果我们已知用户对于电影的喜好(),并且知道用户对于电影的评分(y(i,j)),那么我们可以根据这些来倒推电影的特征().

cost function for X
如上图所示求出最优的X.
Collaborative filtering
Collaborative filtering的思想就是随机初始化用户的偏好,根据用户评分去估算电影特征X,再根据X和评分去优化,如此往复,虽然没给出证明,但是这样做最后和X都会收敛.

Collaborative filtering algorithm

cost function(simultaneously)
前一节中的先优化再优化X的反复的过程可以合并在一起同时进行,cost fucntion 如上.
Collaborative filtering algorithm
完整的Collaborative filtering algorithm步骤如上.
注意,这里不需要了

Vectorization:Low rank matrix factorization

Y
Predicted ratings

X是的矩阵,可以看成是影片的样本,每一行代表一部电影,每一列代表电影的特征,是的矩阵,可以看作用户的样本,每一行代表一个用户,每一列代表用户对电影特征的爱好程度. Finding similar movies
有时候我们要根据用户喜爱的电影类型推荐相似的电影给他,当计算出用户喜欢的电影的特征值时,遍历所有电影,当最小时对应的电影j就是和i最类似的电影.

Implementational detail:Mean normalization

Users who have not rated any movies
对于从来没有打对电影打过分的用户,在使用Collaborative filtering algorithm时,cost function的第一项永远为0,那么在梯度下降算法执行的过程中对于上图中的Eve用户来说,倾向于把偏好都设置为0,如果使用去预测Eve的评分那将全部是0,我们没法给Eve做推荐,为了解决这种问题,我们需要使用Mean normalization,如下图所示,对于Y的每一行求平均值构成向量,再做类似于的操作,此时对于用户j在电影i上的打分则是 ,换句话说就是对于没有做过任何评分的用户,将他对电影的评分设置为该电影的平均分.
Mean normalization