数据挖掘导论-ch10

1、数据挖掘数据挖掘 异常检测异常检测第十章第十章数据挖掘简介数据挖掘简介 数据挖掘导论 3/23/2022 1 数据挖掘导论 3/23/2022 2 不规则不规则/异常检测异常检测l什么是异常/离群值？ 与其余数据相差很大的数据点集l异常/异常值检测问题的变体 给定数据库D，找到具有大于某个阈值t的异常分数的所有数据点x D 给定数据库D，找到具有前n个最大异常分数f(x)的所有数据点x D 给定包含大部分正常（但未标记）数据点的数据库D和测试点x，计算x相对于D的异常分数l应用： 信用卡欺诈检测，电信欺诈检测，网络入侵检测，故障检测 数据挖掘导论 3/23/2022 3 异常检测的重要性异常检

2、测的重要性臭氧消耗历史l1985年，三个研究人员（Farman，Gardinar和Shanklin）对英国南极调查收集的数据感到困惑，表明南极洲的臭氧水平比正常水平下降了10l为什么Nimbus 7卫星（其上有用于记录臭氧水平的仪器）不记录类似的低臭氧浓度？ l由卫星记录的臭氧浓度如此之低，他们被计算机程序作为异常值处理并丢弃！Sources: .au/ozone.html /ozone/science/hole/size.html 数据挖掘导论 3/23/2022 4 异常检测异常检测l挑战 数据中有多少

3、离群值？ 方法是无人监督的u验证可能相当具有挑战性（就像聚类） 在大海里捞针查找l工作假设： 与数据中的“异常”观察（异常值/异常）相比，存在显着更多的“正常”观察结果 数据挖掘导论 3/23/2022 5 异常检测方案异常检测方案l一般步骤 构建“正常”行为的配置文件u配置文件可以是总体人口的模式或摘要统计 使用“正常”配置文件检测异常u异常是其特征与正常特征明显不同的观察结果l异常检测？方案的类型 图形和统计 基于距离 基于模型 数据挖掘导论 3/23/2022 6 图形方法图形方法l箱形图(1-D),散点图(2-D),自旋图(3-D)l缺点 耗时的 主观 数据挖掘导论 3/23/2022

4、 7 凸体船体法凸体船体法l极值点被假定为异常值l使用凸包方法来检测极值l如果异常值出现在数据的中间怎么办？ 数据挖掘导论 3/23/2022 8 统计方法统计方法l假设描述数据分布的参数模型（例如，正态分布） l应用取决于的统计测试 数据分布 分布参数（例如，平均值，方差） 预期异常值的数量（置信限制） 数据挖掘导论 3/23/2022 9 格鲁布斯测试格鲁布斯测试l检测单变量数据中的异常值l假设数据来自正态分布l一次检测一个异常值，删除异常值，然后重复 H0: 数据中没有异常值 HA: 至少有一个离群值lGrubbs 检验统计量：l拒绝H0如果：sXXGmax22)2,/()2,/(2)

5、1(NNNNtNtNNG 数据挖掘导论 3/23/2022 10 基于统计的似然方法基于统计的似然方法l假定数据集D包含来自两个概率分布的混合的样本： M (多数分布) A (异常分布)l一般方法： 最初，假设所有数据点属于M 令Lt(D)是D在时间t的对数似然性 对于属于M的每个点xt ，将其移动到Au 令Lt+1 (D)为新的对数似然。u 计算差值， = Lt(D) Lt+1 (D) u 如果 c （某些阈值），则xt被声明为异常，并从M永久移动到A 数据挖掘导论 3/23/2022 11 基于统计的似然方法基于统计的似然方法l数据分布，D = (1 ) M + AlM 是从数据估计的概率

6、分布 可以基于任何建模方法（朴素贝叶斯，最大熵等）l最初假设A是均匀分布l在时间t的似然性：tittittitttittAxiAtMxiMttAxiAAMxiMMNiiDtxPAxPMDLLxPxPxPDL)(loglog)(log)1log()()()()1 ()()(|1 数据挖掘导论 3/23/2022 12 统计方法的局限性统计方法的局限性l大多数测试是针对单个属性的l在许多情况下，数据分布可能不是已知的l对于高维数据，可能难以估计真实分布 数据挖掘导论 3/23/2022 13 基于距离的方法基于距离的方法l数据表示为特征向量l三大方法 基于最近邻 基于密度 基于集群 数据挖掘导论

7、3/23/2022 14 最近邻法最近邻法l方法： 计算每对数据点之间的距离 有各种方法来定义异常值：u在距离D内具有少于p个相邻点的数据点u距第k个最近邻的距离最大的前n个数据点u与k个最近邻居的平均距离最大的前n个数据点 数据挖掘导论 3/23/2022 15 低维投影中的离群值低维投影中的离群值l在高维空间中，数据稀疏，接近度概念变得无意义 从基于接近度的定义的角度来看，每一点都是一个几乎同样好的异常值l低维投影方法 如果在一些较低维投影中，点是异常值，则其存在于异常低密度的局部区域中 数据挖掘导论 3/23/2022 16 低维投影中的离群值低维投影中的离群值l将每个属性划分为个等深度

8、区间 每个区间包含记录的分数f = 1/ l考虑通过从k个不同维度中选择网格范围创建的k维多维数据集 如果属性是独立的，我们期望区域包含记录的分数 fk 如果有N个点，我们可以测量立方体D的稀疏度： 负稀疏性表示立方体包含的点数比预期的少 数据挖掘导论 3/23/2022 17 示例示例lN=100, = 5, f = 1/5 = 0.2, N f2 = 4 数据挖掘导论 3/23/2022 18 基于密度：基于密度： LOF方法方法l对于每个点，计算其局部邻域的密度l计算样本p的局部离群值因子(LOF) ，作为样本p的密度与其最近邻的密度的比率的平均值l异常值是具有最大LOF值的点 p2 p

9、1 在NN方法中， p2不被认为是异常值，而LOF方法发现p1和p2都是异常值 数据挖掘导论 3/23/2022 19 基于聚类基于聚类l基本思路： 将数据聚集成不同密度的组 在小集群中选择点作为候选离群值 计算候选点和非候选聚类之间的距离。u如果候选点远离所有其他非候选点，则它们是离群值 数据挖掘导论 3/23/2022 20 基本利率下跌基本利率下跌l贝叶斯定理：l推广： 数据挖掘导论 3/23/2022 21 基本利率下跌基本利率下跌(Axelsson, 1999) 数据挖掘导论 3/23/2022 22 基本利率下跌基本利率下跌l即使测试是99肯定，你的疾病的几率是1/100，因为健康的人口比病人大得多 数据挖掘导论 3/23/2022 23 入侵检测中的基本速率下降入侵检测中的基本速率下降l I: 侵入行为 I: 非侵入行为 A: 报警 A: 无报警l检测率（真阳性率）: P(A|I)l假报警率: P(A|I)l目标是最大化两者 贝叶斯检测率, P(