数据挖掘导论-ch10

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