异常检测

1数据挖掘与商务智能DataMining&BusinessIntelligence西安电子科技大学软件学院主讲人：黄健斌第八章异常检测内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献什么是异常(Outlier)？Hawkins的定义：异常是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。Weisberg的定义：异常是与数据集中其余部分不服从相同统计模型的数据。Samuels的定义：异常是足够地不同于数据集中其余部分的数据。Porkess的定义：异常是远离数据集中其余部分的数据异常数据具有特殊的意义和很高的实用价值现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，异常数据通常作为噪音而忽略，许多数据挖掘算法试图降低或消除异常数据的影响。而在有些应用领域识别异常数据是许多工作的基础和前提，异常数据会带给我们新的视角。如在欺诈检测中，异常数据可能意味欺诈行为的发生，在入侵检测中异常数据可能意味入侵行为的发生。异常检测的应用领域电信、保险、银行中的欺诈检测与风险分析发现电子商务中的犯罪行为灾害气象预报税务局分析不同团体交所得税的记录，发现异常模型和趋势海关、民航等安检部门推断哪些人可能有嫌疑海关报关中的价格隐瞒营销定制：分析花费较小和较高顾客的消费行为医学研究中发现医疗方案或药品所产生的异常反应计算机中的入侵检测运动员的成绩分析应用异常检测到文本编辑器，可有效减少文字输入的错误……什么是异常挖掘？异常挖掘可以描述为：给定N个数据对象和所期望的异常数据个数，发现明显不同、意外，或与其它数据不一致的前k个对象。异常挖掘问题由两个子问题构成：(1)如何度量异常；(2)如何有效发现异常。为什么会出现异常数据？测量、输入错误或系统运行错误所致数据内在特性所决定客体的异常行为所致由于异常产生的机制是不确定的，异常挖掘算法检测出的“异常数据”是否真正对应实际的异常行为，不是由异常挖掘算法来说明、解释的，只能由领域专家来解释，异常挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。异常数据实例一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的；一个公司的高层管理人员的工资明显高于普通员工的工资可能成为异常数据但却是合理的数据(如平安保险公司2007年5位高管税后收入超过了1000万元)；一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致；一张信用卡出现明显的高额消费也许是因为是盗用的卡。异常数据与众不同但具有相对性：高与矮，疯子与常人。类似术语：Outliermining，Exceptionmining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘。11内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献MainProblems主要问题典型正常区域的定义不易正常对象和离群点之间的界线不明确离群点的确切概念随应用领域而异训练/验证已标记数据的可用性数据可能包含噪声恶意对手的存在，反检测正常行为不断演变1213内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献14AnomalyDetectionSchemes异常检测方法一般步骤构建“正常”行为的资料集资料集可以是针对数据整体的图案或者汇总统计通过使用“正常”资料集检测异常行为异常行为是特征与“正常”资料有显著差别的观察对象异常检测方法的类型分类和聚类基于统计的方法基于距离和基于密度的方法基于图形的方法异常检测上下文异常检测集体异常检测在线异常检测分布异常检测异常点检测基于分类基于规则基于神经网络基于支持向量机基于最近邻基于密度基于距离统计有参数的无参数的基于聚类其他基于信息理论基于谱分解基于可视化AnomalyDetectionSchemes异常检测方法15主要思想基于已标记的训练数据，对正常事件(和(极少)异常事件)构建一个分类模型，以此对每一个新的未知事件进行分类分类模型必须能够处理倾斜(不均衡)的类分布分类监督分类技术需要了解正常类和异常类建立分类，以区分正常事件和已知的异常事件半监督分类技术只需要了解正常类使用改进的分类模型学习正常行为，然后将检测到的偏离正常行为的对象作为异常行为Ⅰ.Classification-BasedTechniques分类16Ⅰ.Classification-BasedTechniques分类优点监督分类技术模型很容易理解在多种已知异常对象的检测中具有高精度半监督分类技术模型很容易理解正常行为可以被准确学习缺点监督分类技术需要正常类的标记和异常类的标记不能检测未知的和新兴的异常对象半监督分类技术需要正常类的标记可能存在高误报率：先前未知(但合法)的数据记录可能被认为是异常的17Ⅱ.Clustering-BasedTechniques聚类关键假设正常数据记录属于大型的、密集的集群，而异常数据记录不属于任何集群或者形成极小的集群按照标签分类半监督：聚集正常数据，以创建正常行为模式。如果一个新实例不属于或者不靠近任何集群，那么就是异常无监督：在聚类过程所需步骤之后，需要进行后处理来决定集群的大小，集群间的距离用来判别数据点是否异常应用基于聚类的方法进行异常检测不适合任何集群的数据记录(集群残差)小集群低密度集群或局部异常(远离属于同一聚类的其他点)1819基本思想将数据聚类划分为不同密度的簇选择小簇中的点作为候选离群点计算非候选点形成的簇和候选点间的距离如果候选点距离非候选点形成的簇较远，那么他们是离群点Ⅱ.Clustering-BasedTechniques聚类优点不需要监督易适应在线/增量模式，适用于时空数据的异常检测缺点代价极大使用索引结构(k-d树，R*树)可能能够减轻该问题如果正常点不能创建任何簇，那么该方法可能会失败在高维空间中，数据是稀疏的，任意两个数据记录间的距离可能会非常相似聚类算法可能不会得到有意义的簇Ⅱ.Clustering-BasedTechniques聚类20Ⅲ.NN-BasedTechniques最近邻方法关键假设正常点有近邻，而离群点远离其他节点一般为二步法1.计算每个数据记录和其邻居间的关系2.分析邻居关系，以确定该数据记录异常与否分类基于距离的方法离群点是远离其他节点的数据点基于密度的方法离群点是低密度区域的数据点21优点可以应用于无监督或半监督环境中(对数据分布不作出任何假设)缺点如果正常点没有足够数量的邻居，该方法可能会失败代价极大在高维空间中，数据是稀疏的，相似度的概念不能起到很大作用两个数据记录间的距离会由于稀疏而变得十分相似，以至于每个数据记录都可能被视为潜在的离群点Ⅲ.NN-BasedTechniques最近邻方法22Ⅲ.NN-BasedTechniques最近邻方法基于距离的方法对于数据集中的点O，如果数据集中至少有p(百分比)的节点到点O的距离超过d，那么就认为O是数据集中的离群点，记为DB(p,d)*基于密度的方法计算特定区域的局部密度，将低密度区域的实例报为潜在离群点方法局部离群因子(LocalOutlierFactor,LOF)连接离群因子(ConnectivityOutlierFactor,COF‏）多粒度偏差因子(Multi-GranularityDeviationFactor,MDEF)*Knorr,Ng,AlgorithmsforMiningDistance-BasedOutliersinLargeDatasets,VLDB9823(1)基于距离的NN方法基于距离的方法有两种不同的策略第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少来判定异常；如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为异常，也就是将没有足够邻居的对象看成是基于距离的异常。利用k最近邻距离的大小来判定异常。使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的异常程度由到它的k-最近邻的距离给定。这种方法对k的取值比较敏感。如果k太小(例如1)，则少量的邻近异常点可能导致较低的异常程度。如果k太大，则点数少于k的簇中所有的对象可能都成了异常点。到k-最近邻的距离的计算k-最近邻的距离：一个对象的异常点得分由到它的k-最近邻的距离给定。异常点得分的最低值为0，最高值是距离函数的可能最大值----如无穷大基于距离的异常点检测例1请问该二维数据集中，当k=5时，哪个点具有最高的异常点得分？基于距离的异常点检测例2请问该二维数据集中，当k=5时，哪个点具有最高的异常点得分？基于距离的异常检测的优缺点优点：基于距离的异常点检测方案简单缺点：时间复杂度O(m2)，不适用于大数据集不能处理不同密度区域的数据集，因为它使用全局阈值，不能考虑这种密度的变化不能处理不同密度区域的数据集CDAB当k=5时，哪个点具有最高的异常点得分,B的异常点得分和D的异常点得分哪个低？例：局部离群因子法(LocalOutlierFactor,LOF)Example:p2p1p3Distancefromp3tonearestneighborDistancefromp2tonearestneighbor(2)LocalOutlierFactor(LOF)基于密度的NN方法*-Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.30在NN方法中，p2并没有被认为是离群点,而在LOF方法中发现p1和p2都是离群点NN方法可能认为p3是离群点,但LOF方法不会31(2)LocalOutlierFactor(LOF)基于密度的NN方法对每一个数据点q，计算到第k个近邻的距离(k-distance)对任意两个数据，计算可达距离(reach-dist)reach-dist(p,o)=max{k-distance(o),d(p,o)}32(2)LocalOutlierFactor(LOF)基于密度的NN方法计算局部可达密度(localreachabilitydensity,lrd)基于数据p的MinPts-NN的平均可达距离的逆lrd(p)=计算LOF(p)作为p的k近邻平均局部可达密度比率数据记录p的局部可达密度为LOF(p)=MinPtsMinPts()()_(,)MinPtsoNpNpreachdistpoMinPts()MinPts1()|()|()oNplrdoNplrdp*-Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.(2)LocalOutlierFactor(LOF)基于密度的NN方法*-Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.对象p的离群因子不为空，则称p为离群点平均局部可达密度比率p的MinPts-NN邻居很容易看出：p的LOF值越高，则p的局部可达密度越低，p的MinPts-NN的局部可达密度越高.33内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献应用案例1IntrusionDetection入侵检测35CaseStudy:DataMininginIntrusionDetection