这部分内容来源于Andrew NG老师讲解的 machine learning课程,包括异常检测算法以及推荐系统设计。异常检测是一个非监督学习算法,用于发现系统中的异常数据。推荐系统在生活中也是随处可见,如购物推荐、影视推荐等。课程链接为: https://www.coursera.org/course/ml。
(一)异常检测(Anomaly Detection)
举个例子:
我们有一些飞机发动机特征的sample: {x (1) ,x (2) ,...,x (m) } ,对于一个新的样本x test ,那么它是异常数据么(这个数据不属于该组的几率怎样)?我们可以构建一个模型 p(x) ,来计算测试数据是否为异常数据.从图中可见,若数据落在蓝色圈内,则属于该组的可能性较高,若落于蓝色圈外,则属于该组的几率较低。
这种方法为密度估计,表达式如下:
if p(x test ) ≤ ε → anomaly
if p(x test ) > ε → normal
异常检测应用:
可以用来识别欺骗。例如在online采集的数据中,特征向量可能包括:用户多久登陆一次,点击过的页面,发帖数量,打字速度等。我们可以根据这些特征来构建模型,用来识别不符合该模式的用户;再者在数据中心里,特征向量可能包括:内存使用情况、CPU负载、被访问的磁盘数、网络通信量等。构建模型从而判断计算机是否出错。
下面是几个高斯分布的例子:
例如,若训练集又两维特征 x 1 ,x 2 组成,其中 x 1 和 x 2 的 μ 和 σ 2 分别为:μ1=5,σ 1 =2;μ2=3,σ 2 =1。分布情况如下所示。
则模型 p(x) 函数如下图的三围图像所示, z 轴为估计的 p(x) 值:
异常检测系统评价:
和我们之前学习的监督学习一样,我们需要评估该异常检测系统,但是异常检测算法是 unsupervised ,即我们无法根据y值来评估预测数据。那么我们就从带标记的(异常或正常)数据入手,假设给定一些有label的数据(若是正常数据则y=0,异常数据则y=1),从中选择一部分正常数据来构成 Training set ,用剩余的正常数据和异常数据来构成 Cross validation set 和 test set 。
例如:在飞机引擎的问题中,我们有10000台正常引擎和20台异常引擎。我们这样分配:
评价方法:
1.根据 Training set ,估计特征的 μ 和 σ 2 ,构建 p(x) 函数;
2.在 CV/Test set 上面使用不同的 ε 作为阈值,预测数据,并根据 F1 值(或查准率与查全率比值)来选择合适的 ε 。
异常检测 vs 监督学习
特征选择
对于异常检测,特征选择至关重要。之前我们假
误差分析:
而一个常见的问题是 p(x) 对于 normal 或者 anomalous 都比较大,那么如何解决呢?
我们可以增加一些特征,或者将一些相关的特征进行组合,这些新的他正可以帮助我们进行更好的异常检测。例如,在数据中心检测计算机状况的问题中,我们可以使用cpu负载与网络通信量之比作为新的特征,若该值特别大则可能说明计算机出现了异常。
多元高斯分布(Mul-variate Gaussian distribution)
在使用高斯分布模型进行异常检测时,可能会出现这样的情况:假设我们有两个特征 x 1 和 x 2 ,这两个特征的值域范围较大,而一般的高斯分布模型会尝试同时抓住两个特征,从而创造出一个更大的边界,如图中紫色所示边界,可以看出绿色的样本点可能是异常数据,但是它却处于正常的范围内。那么多元高斯分布会构建蓝色所示的边界。
在多元高斯分布中,我们将构建特征协方差矩阵,即所有特征放在一起计算 p(x)
原高斯分布模型与多元高斯分布模型的关系:
显而易见,当协方差矩阵只在对角线上有非零的值时,即为原高斯分布模型,所以原高斯分布模型是多元高斯分布模型的一个子集。
PS:
(二)推荐系统(Recommender Systems)
问题描述
基于内容的推荐系统(Content-based recommendations)
现在我们假设每部电影有两个特征: x 1 代表浪漫程度, x 2 代表动作程度。
假设我们现在有 5 部电影和 4 个用户,以及这四个用户对看过电影的评分。前三部是爱情片,后两部是动作片。从表格中我们可以看出 Alice 和 Bob 似乎喜欢看爱情片,而 Carol 和 Dave 似乎喜欢动作片。我们可以根据一些算法来预测他们会给没看过的电影打多少份,作为推荐的依据。
基于内容的推荐系统(Content-based recommendations)
现在我们假设每部电影有两个特征: x 1 代表浪漫程度, x 2 代表动作程度。
我们预测用户j对电影i的评分为: (θ (j) ) T (x (i) )
其中 i:r(i,j)=1 表示我们只计算那些用户j评分过的电影,在一般的 linear regression 模型中,误差项和归一项都应乘以 1/2m ,这里我们统一将 m 去掉,并且不对 θ 0 进行归一化。
协同过滤算法(Collaborative filtering algorithm)
对协同过滤,这里有一个比较全面的说明,可供参考:
http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy2/index.html
在之前的基于内容的推荐系统中我们知道,如果我们掌握电影的可用特征,则可以训练出每个用户的参数;相反如果我们掌握了用户参数,则可以训练出电影的特征。
那么如果我们既没有用户参数也没有电影特征,可以使用协同过滤算法来同时学习两者。我们的优化目标同时针对 x 和 θ 进行。
PS :在协同过滤中,通常不加 bias 项 x 0 和 θ 0 ,如果需要,算法会自动获得。
协同过滤算法步骤:
PS: 协同过滤算法获得的特征矩阵包含了电影的相关数据,这些数据不总是人能读懂的,但我们可以用这些数据作为给用户推荐电影的依据,如一位用户看了电影 x (i),如果对于另一部电影 x (j) , ||x (i) -x (j) || 很小,我们可以为他推荐电影 x (j) 。
均值归一化(Mean normalization)
现在我们新增一个用户 Eve , Eve 没有为电影做出任何评分,那么如何为 Eve 推荐电影呢