Chp10 Anomaly Detection

数据挖掘导论 笔记

examples: fraud detection, invader detection, habitate maladjustment, public health, medical secure.

1 Introductory Information

1 Reasons

来源不同
outlier：和其他的差别相当大，以至于怀疑不是相同机制产生的
自然变异
数据测量和收集误差

2 Detection Approach

Based on model, 如利用分类器，利用模型拟合好正常点，其他的就是异常点。
Based on Distance
Based on Density

supervised:注意异常类特别稀少(提供了标号)
unsupervised:给出评分或标号，然后判断。不过，若出现许多相似的异常值，就没法识别了。(没提供标号)
semisupervised:训练集中不含异常信息。

3 Questions

1. 那些属性确定了不正常，e.g. 身高1m，正常，小孩，体重100kg，正常，大个，加在一起就很不正常了。
2. 全局与局部观点，有的放在局部看就不异常了，如运动员
3. 异常程度
4. 识别一个，或者多个
5. 评估，用recall比precision好一些
6. 有效性，计算开销

2 Statistical Approach

离群点，即出现概率很低的点
1. 识别具体分布
2. 使用的属性个数，有些是单个的，有的是多个的
3. 混合分布

基于正太的方法：。。。略
基于混合分布的办法，即假设异常点也有一个分布，通常设为均匀分布。然后可以看看怎么分，可以最大化极大似然。

3 Based on Distance

使用k距离，k的选择也是玄学，当然也可以用平均的来

O(m^2)太慢了，不能处理密度不同的时候的情况

4 Based on Density

得分为密度的逆
一个常用的密度定义为k个最近邻的平均距离的倒数or给定半径内的点的个数，参数选择是个玄学

基于相对平均密度
$average relative density(x,k)=\frac{density(x,k)}{avg_{y \in N(x,k)}(density(y,k))}$

对于具有不同密度的情况也有较好的结果
复杂度较高$O(m^2)$,k的选择是个玄学

5 Based on Clustering

丢弃远离其他簇的小簇，需要设定距离和大小的阈值。
也可以看对目标函数的改进。
可以定义离群点为不强属于任何一个簇的点。(如密度太低，太远，etc.)

算法效率高。不过聚类的效果很影响他的效果。