关于 anomaly detection

现在开始思考一些基本的处理 anomaly detection 问题的 machine learning 的策略。这方面现在文献看得少,只是一些 general idea。后面会慢慢深入,实验一些想法。其实什么是 anomaly 本身是一个比较难以澄清的概念,看起来这是一个“相对”的东西,就是有一个 background information,这个特定的样本偏离了这个 background “太多”。那怎样的才算太多呢?什么样的 information 用来做 background 参照呢?其实这是一个 application-oriented 的东西,有的 background 是一群人体现出来的,有的 background 是一个人长时间体现出来的,还有的 background 是一些复杂的东西,可能需要 learning 出来。

数据的表示

一个很重要的问题是我们应该为样本提供能区分 outlier 与 normality 的表示,或者足够多的 feature 能够推导出某个/些性质让我们区分出两者。这部分总觉得是 feature engineering,比如我们考虑线上交易行为,如果需要发现一些异常行为我们可以用哪些信息呢?

  • 交易时间,比如用户长期早上购买,突然变成了晚上购买(类似有对 working day 偏好)
  • 交易频率,可能得去掉每个月的 bias
  • 交易金额,类似
  • IP 地址的变化
  • delivery address 的变化
  • 购买产品范围的变化(天天买书的人突然买贵重首饰)

尽管一个因素可能不能完全说明问题,但是一旦多个因素都出现了问题,那么就会越发值得怀疑。

模型与方法

搞 modeling 的人比较喜欢的就是在确定了以上东西后开始折腾各种诡异的方法了(参考 wiki):

  • 基于距离的,如 kNN,local outlier factor(比较当前点的邻域的密度和邻居点的密度)
  • one-class SVM,这是当作 supervised learning 问题来做了
  • replicator neural network,其实和距离的概念类似,即使用多层神经网络来 generate 数据,reconstruction error 大的就可能是 outlier,一个 cheap 的做法就是使用 PCA
  • cluster analysis,clustering 很多情况下等价于 winner-gets-all style EM,因此本质上聚类和密度估计是类似的手法,出现在低密度区域的数据很可能是 anomaly
  • association rules,将不符合 accociation rules 的样本拿出来
  • conditional anomaly detection,并不直接使用 generative model 来生成数据,而使用 indicator attributes conditioned on environmental attributes 上作为拟合的目标,此时如 mixture model 的隐变量 z 将会依赖于 environmental attributes。
  • control charts,例如 real-time contrast control charts,使用近期数据与长期数据作为两类(不见得有意义),训练一个 random forests 来做 prediction,得到一些统计量,当统计量发生了较大的 shift 时候

其实很多情况下 detection 很重要,explanation 也很重要,因为 detection 之后就是人工审查,当我们有非常多的 feature 的时候指出什么导致系统觉得存在异常可能是非常重要的。从某种角度来说,我们做的逻辑系统还非常简单,即如果某些 feature on 了,那么会导致 anomaly。很自然的想法是通过某个 Markov logic net 来做这个事情,将更复杂的 rule 能够加入到 inference 过程里面。hmm… 看起来用的方法基本比较清楚了,不晓得怎么搞点数据开始玩玩…

实验

其实如果有 groundtruth,实验无非就是看 precision/recall 了。线上的情况可能稍微有点不大一样,一方面需要做 online inference,另一方面数据并不是一开始全部都有的,对新用户,我们必须积累一定的数据之后才可能打开对应的防范措施。这个界限大概可以用 inference 的 confidence interval 来判断。

其他

其实很多 anomaly detection 是很难维持很久的。如果是简单的 rule,产生 anomaly 的人自然会设法获得这些 rule 并加以利用,比如如果设置一次支付大于 500$ 就会人工干预,那么很可能会出现大批 499$ 的支付从而逃避 hard rule。因此 anomaly detection 本质也是一个制造 anomaly 的人与 detector 之间的博弈问题。如果希望 detection 能够 handle 这种变化,大致有两种思路:

  • 使用最坏情况的界来做,这可能增加很多假阳性
  • 使用随机算法以及统计结果作为判断依据,这样并不存在一个简单的 rule,每个 detector 自身都是随机的(hmm… 类似前面那个 random forest 的 idea)

——————
She said moreover to him, We have both straw and provender enough, and room to lodge in.

Advertisements
关于 anomaly detection

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s