数据挖掘导论-ch10.ppt

数据挖掘异常检测 第十章数据挖掘简介 不规则 异常检测 什么是异常 离群值 与其余数据相差很大的数据点集异常 异常值检测问题的变体给定数据库D 找到具有大于某个阈值t的异常分数的所有数据点x D给定数据库D 找到具有前n个最大异常分数f x 的所有数据点x D给定包含大部分正常 但未标记 数据点的数据库D和测试点x 计算x相对于D的异常分数应用 信用卡欺诈检测 电信欺诈检测 网络入侵检测 故障检测 异常检测的重要性 臭氧消耗历史1985年 三个研究人员 Farman Gardinar和Shanklin 对英国南极调查收集的数据感到困惑 表明南极洲的臭氧水平比正常水平下降了10 为什么Nimbus7卫星 其上有用于记录臭氧水平的仪器 不记录类似的低臭氧浓度 由卫星记录的臭氧浓度如此之低 他们被计算机程序作为异常值处理并丢弃 Sources 异常检测 挑战数据中有多少离群值 方法是无人监督的验证可能相当具有挑战性 就像聚类 在大海里捞针查找工作假设 与数据中的 异常 观察 异常值 异常 相比 存在显着更多的 正常 观察结果 异常检测方案 一般步骤构建 正常 行为的配置文件配置文件可以是总体人口的模式或摘要统计使用 正常 配置文件检测异常异常是其特征与正常特征明显不同的观察结果异常检测 方案的类型图形和统计基于距离基于模型 图形方法 箱形图 1 D 散点图 2 D 自旋图 3 D 缺点耗时的主观 凸体船体法 极值点被假定为异常值使用凸包方法来检测极值如果异常值出现在数据的中间怎么办 统计方法 假设描述数据分布的参数模型 例如 正态分布 应用取决于的统计测试数据分布分布参数 例如 平均值 方差 预期异常值的数量 置信限制 格鲁布斯测试 检测单变量数据中的异常值假设数据来自正态分布一次检测一个异常值 删除异常值 然后重复H0 数据中没有异常值HA 至少有一个离群值Grubbs 检验统计量 拒绝H0如果 基于统计的似然方法 假定数据集D包含来自两个概率分布的混合的样本 M 多数分布 A 异常分布 一般方法 最初 假设所有数据点属于M令Lt D 是D在时间t的对数似然性对于属于M的每个点xt 将其移动到A令Lt 1 D 为新的对数似然 计算差值 Lt D Lt 1 D 如果 c 某些阈值 则xt被声明为异常 并从M永久移动到A 基于统计的似然方法 数据分布 D 1 M AM是从数据估计的概率分布可以基于任何建模方法 朴素贝叶斯 最大熵等 最初假设A是均匀分布在时间t的似然性 统计方法的局限性 大多数测试是针对单个属性的在许多情况下 数据分布可能不是已知的对于高维数据 可能难以估计真实分布 基于距离的方法 数据表示为特征向量三大方法基于最近邻基于密度基于集群 最近邻法 方法 计算每对数据点之间的距离有各种方法来定义异常值 在距离D内具有少于p个相邻点的数据点距第k个最近邻的距离最大的前n个数据点与k个最近邻居的平均距离最大的前n个数据点 低维投影中的离群值 在高维空间中 数据稀疏 接近度概念变得无意义从基于接近度的定义的角度来看 每一点都是一个几乎同样好的异常值低维投影方法如果在一些较低维投影中 点是异常值 则其存在于异常低密度的局部区域中 低维投影中的离群值 将每个属性划分为 个等深度区间每个区间包含记录的分数f 1 考虑通过从k个不同维度中选择网格范围创建的k维多维数据集如果属性是独立的 我们期望区域包含记录的分数fk如果有N个点 我们可以测量立方体D的稀疏度 负稀疏性表示立方体包含的点数比预期的少 示例 N 100 5 f 1 5 0 2 N f2 4 基于密度 LOF方法 对于每个点 计算其局部邻域的密度计算样本p的局部离群值因子 LOF 作为样本p的密度与其最近邻的密度的比率的平均值异常值是具有最大LOF值的点 在NN方法中 p2不被认为是异常值 而LOF方法发现p1和p2都是异常值 基于聚类 基本思路 将数据聚集成不同密度的组在小集群中选择点作为候选离群值计算候选点和非候选聚类之间的距离 如果候选点远离所有其他非候选点 则它们是离群值 基本利率下跌 贝叶斯定理 推广 基本利率下跌 Axelsson 1999 基本利率下跌 即使测试是99 肯定 你的疾病的几率是1 100 因为健康的人口比病人大得多 入侵检测中的基本速率下降 I 侵入行为 I 非侵入行为A 报警 A 无报警检测率 真阳性率 P A I 假报警率 P A I 目标是最大化两者贝叶斯检测率 P I A P I A 检测率与假报警率 假设 然后 如果P I