数据挖掘西安电子科技大学软件学院课件

1数据挖掘与商务智能

DataMining&BusinessIntelligence西安电子科技大学软件学院主讲人：黄健斌

第八章异常检测

1数据挖掘与商务智能

DataMining&Busin内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献内容提纲异常挖掘及其应用内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献内容提纲异常挖掘及其应用什么是异常(Outlier)？Hawkins的定义：异常是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。Weisberg的定义：异常是与数据集中其余部分不服从相同统计模型的数据。Samuels的定义：异常是足够地不同于数据集中其余部分的数据。Porkess的定义：异常是远离数据集中其余部分的数据什么是异常(Outlier)？Hawkins的定义：异常是在异常数据具有特殊的意义和很高的实用价值

现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，异常数据通常作为噪音而忽略，许多数据挖掘算法试图降低或消除异常数据的影响。而在有些应用领域识别异常数据是许多工作的基础和前提，异常数据会带给我们新的视角。如在欺诈检测中，异常数据可能意味欺诈行为的发生，在入侵检测中异常数据可能意味入侵行为的发生。异常数据具有特殊的意义和很高的实用价值现有数据挖掘研究大异常检测的应用领域电信、保险、银行中的欺诈检测与风险分析发现电子商务中的犯罪行为灾害气象预报税务局分析不同团体交所得税的记录，发现异常模型和趋势海关、民航等安检部门推断哪些人可能有嫌疑海关报关中的价格隐瞒营销定制：分析花费较小和较高顾客的消费行为医学研究中发现医疗方案或药品所产生的异常反应计算机中的入侵检测运动员的成绩分析应用异常检测到文本编辑器，可有效减少文字输入的错误

……异常检测的应用领域电信、保险、银行中的欺诈检测与风险分析

什么是异常挖掘？

异常挖掘可以描述为：给定N个数据对象和所期望的异常数据个数，发现明显不同、意外，或与其它数据不一致的前k个对象。异常挖掘问题由两个子问题构成：(1)如何度量异常；(2)如何有效发现异常。什么是异常挖掘？

异常挖掘可以描述为：给定N个数据对象为什么会出现异常数据？测量、输入错误或系统运行错误所致数据内在特性所决定客体的异常行为所致由于异常产生的机制是不确定的，异常挖掘算法检测出的“异常数据”是否真正对应实际的异常行为，不是由异常挖掘算法来说明、解释的，只能由领域专家来解释，异常挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。为什么会出现异常数据？测量、输入错误或系统运行错误所致异常数据实例一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的；一个公司的高层管理人员的工资明显高于普通员工的工资可能成为异常数据但却是合理的数据(如平安保险公司2007年5位高管税后收入超过了1000万元)；一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致；一张信用卡出现明显的高额消费也许是因为是盗用的卡。异常数据实例一个人的年龄为-999就可能是由于程序处理缺省数异常数据与众不同但具有相对性：

高与矮，疯子与常人。类似术语：

Outliermining，Exceptionmining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘。异常数据与众不同但具有相对性：11内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献11内容提纲异常挖掘及其应用MainProblems主要问题典型正常区域的定义不易正常对象和离群点之间的界线不明确离群点的确切概念随应用领域而异训练/验证已标记数据的可用性数据可能包含噪声恶意对手的存在，反检测正常行为不断演变12MainProblems主要问题典型正常区域的定义不易113内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献13内容提纲异常挖掘及其应用14AnomalyDetectionSchemes异常检测方法一般步骤构建“正常”行为的资料集资料集可以是针对数据整体的图案或者汇总统计通过使用“正常”资料集检测异常行为异常行为是特征与“正常”资料有显著差别的观察对象异常检测方法的类型分类和聚类基于统计的方法基于距离和基于密度的方法基于图形的方法14AnomalyDetectionSchemes异异常检测上下文异常检测集体异常检测在线异常检测分布异常检测异常点检测基于分类基于规则基于神经网络基于支持向量机基于最近邻基于密度基于距离统计有参数的无参数的基于聚类其他基于信息理论基于谱分解基于可视化AnomalyDetectionSchemes异常检测方法15异常检测上下文异常检测集体异常检测在线异常检测分布异常检测异主要思想基于已标记的训练数据，对正常事件(和(极少)异常事件)构建一个分类模型，以此对每一个新的未知事件进行分类分类模型必须能够处理倾斜(不均衡)的类分布分类监督分类技术

需要了解正常类和异常类建立分类，以区分正常事件和已知的异常事件半监督分类技术

只需要了解正常类使用改进的分类模型学习正常行为，然后将检测到的偏离正常行为的对象作为异常行为Ⅰ.Classification-BasedTechniques分类16主要思想Ⅰ.Classification-BasedTeⅠ.Classification-BasedTechniques分类优点监督分类技术

模型很容易理解在多种已知异常对象的检测中具有高精度半监督分类技术

模型很容易理解正常行为可以被准确学习缺点监督分类技术

需要正常类的标记和异常类的标记不能检测未知的和新兴的异常对象半监督分类技术

需要正常类的标记可能存在高误报率：先前未知(但合法)的数据记录可能被认为是异常的17Ⅰ.Classification-BasedTechniⅡ.Clustering-BasedTechniques聚类关键假设正常数据记录属于大型的、密集的集群，而异常数据记录不属于任何集群或者形成极小的集群按照标签分类半监督：

聚集正常数据，以创建正常行为模式。如果一个新实例不属于或者不靠近任何集群，那么就是异常无监督：

在聚类过程所需步骤之后，需要进行后处理来决定集群的大小，集群间的距离用来判别数据点是否异常应用基于聚类的方法进行异常检测不适合任何集群的数据记录(集群残差)

小集群低密度集群或局部异常(远离属于同一聚类的其他点)18Ⅱ.Clustering-BasedTechniques19基本思想将数据聚类划分为不同密度的簇选择小簇中的点作为候选离群点计算非候选点形成的簇和候选点间的距离如果候选点距离非候选点形成的簇较远，那么他们是离群点

Ⅱ.Clustering-BasedTechniques聚类19基本思想Ⅱ.Clustering-BasedTec优点不需要监督易适应在线/增量模式，适用于时空数据的异常检测缺点代价极大使用索引结构(k-d树，R*树)可能能够减轻该问题如果正常点不能创建任何簇，那么该方法可能会失败在高维空间中，数据是稀疏的，任意两个数据记录间的距离可能会非常相似聚类算法可能不会得到有意义的簇Ⅱ.Clustering-BasedTechniques聚类20优点Ⅱ.Clustering-BasedTechniqu

Ⅲ.NN-BasedTechniques最近邻方法关键假设正常点有近邻，而离群点远离其他节点一般为二步法计算每个数据记录和其邻居间的关系分析邻居关系，以确定该数据记录异常与否分类基于距离的方法离群点是远离其他节点的数据点基于密度的方法离群点是低密度区域的数据点21Ⅲ.NN-BasedTechniques最近邻方法关键优点可以应用于无监督或半监督环境中(对数据分布不作出任何假设)

缺点如果正常点没有足够数量的邻居，该方法可能会失败代价极大在高维空间中，数据是稀疏的，相似度的概念不能起到很大作用两个数据记录间的距离会由于稀疏而变得十分相似，以至于每个数据记录都可能被视为潜在的离群点

Ⅲ.NN-BasedTechniques最近邻方法22优点Ⅲ.NN-BasedTechniques最近邻方法

Ⅲ.NN-BasedTechniques最近邻方法基于距离的方法对于数据集中的点O，如果数据集中至少有p(百分比)的节点到点O的距离超过d，那么就认为O是数据集中的离群点，记为DB(p,d)*基于密度的方法计算特定区域的局部密度，将低密度区域的实例报为潜在离群点方法局部离群因子(LocalOutlierFactor,LOF)连接离群因子(ConnectivityOutlierFactor,COF‏）多粒度偏差因子(Multi-GranularityDeviationFactor,MDEF)*Knorr,Ng,AlgorithmsforMiningDistance-BasedOutliersinLargeDatasets,VLDB9823Ⅲ.NN-BasedTechniques最近邻方法基于(1)基于距离的NN方法基于距离的方法有两种不同的策略第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少来判定异常；如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为异常，也就是将没有足够邻居的对象看成是基于距离的异常。利用k最近邻距离的大小来判定异常。使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的异常程度由到它的k-最近邻的距离给定。这种方法对k的取值比较敏感。如果k太小(例如1)，则少量的邻近异常点可能导致较低的异常程度。如果k太大，则点数少于k的簇中所有的对象可能都成了异常点。(1)基于距离的NN方法基于距离的方法有两种不同的策略到k-最近邻的距离的计算k-最近邻的距离：一个对象的异常点得分由到它的k-最近邻的距离给定。异常点得分的最低值为0，最高值是距离函数的可能最大值----如无穷大到k-最近邻的距离的计算k-最近邻的距离：基于距离的异常点检测例1请问该二维数据集中，当k=5时，哪个点具有最高的异常点得分？基于距离的异常点检测例1请问该二维数据集中，当k=5时，基于距离的异常点检测例2请问该二维数据集中，当k=5时，哪个点具有最高的异常点得分？基于距离的异常点检测例2请问该二维数据集中，当k=5时，基于距离的异常检测的优缺点优点：基于距离的异常点检测方案简单缺点：时间复杂度O(m2)，不适用于大数据集不能处理不同密度区域的数据集，因为它使用全局阈值，不能考虑这种密度的变化基于距离的异常检测的优缺点优点：不能处理不同密度区域的数据集CDAB当k=5时，哪个点具有最高的异常点得分,B的异常点得分和D的异常点得分哪个低？例：不能处理不同密度区域的数据集CDAB当k=5时，哪个点具有最局部离群因子法(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方法不会局部离群因子法(LocalOutlierFactor,31(2)LocalOutlierFactor(LOF)基于密度的NN方法对每一个数据点q，计算到第k个近邻的距离(k-distance)对任意两个数据，计算可达距离(reach-dist)

reach-dist(p,o)=max{k-distance(o),d(p,o)}31(2)LocalOutlierFactor(L32(2)LocalOutlierFactor(LOF)基于密度的NN方法计算局部可达密度(localreachabilitydensity,lrd)基于数据p的MinPts-NN的平均可达距离的逆

lrd(p)

=

计算

LOF(p)作为p的k近邻平均局部可达密度比率数据记录p的局部可达密度为

LOF(p)=

*-Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.32(2)LocalOutlierFactor(LO(2)LocalOutlierFactor(LOF)基于密度的NN方法*-Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.对象p的离群因子不为空，则称p为离群点平均局部可达密度比率

p

的MinPts-NN邻居很容易看出：

p的LOF值越高，则p的局部可达密度越低，

p的MinPts-NN的局部可达密度越高.33(2)LocalOutlierFactor(LOF内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献内容提纲异常挖掘及其应用应用案例1

IntrusionDetection入侵检测35应用案例1

IntrusionDetectionCaseStudy:DataMininginIntrusionDetection随着互联网的不断发展，越来越多的组织易受到网络攻击网络攻击的复杂性和严重性都在增长安全机制总有不可避免的漏洞防火墙不足以确保计算机网络的安全性内线攻击36

19901991199219931994199519961997199819992000200120022003计算机应急反应协调中心的事故报告攻击复杂性vs.入侵技术知识源：/archive/ppt/cyberterror.pptSapphire/SlammerWorm攻击30分钟后的地理分布源：CaseStudy:DataMininginIntr

WhatareIntrusions?入侵37扫描活动攻击者计算机网络易损机器入侵活动试图绕过计算机系统的安全机制通常的行为有攻击者从因特网访问系统内线攻击已授权用户试图获取或误用未被授权的权限典型的入侵场景

受损机器WhatareIntrusions?入侵37扫描活动攻

IDS-AnalysisStrategy入侵检测系统策略分析误用检测(Misusedetection)是基于与专家提供的已知攻击相关的外部知识模式现有的方法：(签字)模式匹配，专家系统，状态转换分析，数据挖掘主要的限制：不能检测异常的或者意料之外的攻击签名数据库要为每一个新发现的攻击进行修改异常检测(Anomalydetection)

是基于代表用户、主机或网络的正常行为的配置文件，检测这个文件中有显著偏差的攻击主要好处：潜在地对不可预见攻击的识别能力主要限制因素：可能有较高的误报率，因为检测偏差不一定代表真实攻击主要方法：统计方法，专家系统，聚类，神经网络，支持向量机，异常检测计划38IDS-AnalysisStrategy入侵检测系统

IntrusionDetection入侵检测39入侵检测系统

将可能执行入侵检测的软硬件结合当可能有入侵发生时拉响警报

传统入侵检测系统(IDS)工具(例如:SNORT)是基于已知签名攻击SNORT规则实例(MS-SQL“Slammer”worm)‏any->udpport1434(content:"|81F10301049B81F101|";

content:"sock";content:"send")限制当出现新的入侵类型时，签名数据库必须手动修改无法检测新兴的网络威胁部署新创建的签名会造成整个计算机系统的重大延迟数据挖掘可以缓解这些限制IntrusionDetection入侵检测www.sn

DataMiningforIntrusionDetection入侵检测数据挖掘对基于数据挖掘的入侵检测兴趣日增攻击造成签名难以建立攻击具有隐蔽性不可预见的/未知的/新出现的攻击分布式/协调的攻击针对入侵检测的数据挖掘方法误用检测(Misusedetection)

基于已标记的数据集(数据标记为”正常”或”异常”)建立预测模型，判别已知入侵在检测多种已知攻击中具有高精度不能检测未知的和新兴的攻击异常检测(Anomalydetection)

从”正常”行为检测异常攻击作为偏差潜在高误报率：以前不可见(但合法)系统行为也可能被认为是异常网络流量综述(Summarizationofnetworktraffic)40DataMiningforIntrusionDetDataMiningforIntrusionDetection误用检测：建立预测模型41绝对的当时的持续的分类测试集训练集模型学习分类器绝对的异常检测发现的规则:{SrcIP=5,

DestPort=139,

Bytes[150,200]}-->{ATTACK}使用关联规则对攻击进行综述DataMiningforIntrusionDete

AnomalyDetectiononRealNetworkData

真实网络数据的入侵检测

在明尼苏达州和美国陆军研究实验室，使用异常检测来检测各种侵扰活动或可以活动其中许多入侵不能被广泛应用的异常检测工具检测到，如SNORT异常/攻击被MINDS发现扫描活动不规范的行为违反策略蠕虫42MINDS–MinnesotaIntrusionDetectionSystem明尼苏达异常检测系统MINDS网络数据捕获装置异常检测……获取异常Human

analyst检测

新的攻击Summaryandcharacterization

ofattacks已知攻击检测Detected

knownattacks标记特征抽取相关模式分析MINDSAT过滤NetflowtoolstcpdumpAnomalyDetectiononRealNet三组特征TCP连接个体的基本特征源&目的地IPFeatures1&2源&目的端口

Features

3

&4协议

Feature5持续时间

Feature6每包字节Feature7字节数Feature8基于时间的特征网络中对于相同的源(目的地)IP地址,最后T秒钟唯一目的地(源)IP地址数目–Features9(13)最后T秒钟从源(目的地)IP到同一个目的地(源)端口的连接数目–Features11(15)基于连接的特征网络中对于相同的源(目的地)IP地址,最后N个连接中唯一目的地(源)IP地址数目-Features10(14)最后N个连接中从源(目的地)IP到同一个目的地(源)端口的连接数目-Features12(16)43FeatureExtraction特征抽取三组特征43FeatureExtraction特征抽取

TypicalAnomalyDetectionOutput典型异常检测输出

“slammer”蠕虫病毒爆发48小时后44连接到“half-life”游戏服务器

的机器所对应的连接“slammer”蠕虫病毒对应的异常连接进行ping扫描异常连接TypicalAnomalyDetectionOutDetectionofAnomaliesonRealNetworkData

真实网络数据中的异常检测MINDS检测出的异常/攻击，包括扫描活动、蠕虫病毒以及像违反规则行为、内部攻击行为等不正常的行为。这些攻击中的大部分均可被MINDS检测出来，并被放在当前计算机应急反应协调中心(CERT/CC)的咨询列表中。下面是MINDS检测出的入侵行为的一些说明例子。ScansAugust13,2004,

DetectedscanningforMicrosoftDSserviceonport445/TCP(Ranked#1)ReportedbyCERTasrecentDoSattacksthatneedsfurtheranalysis(CERTAugust9,2004)UndetectedbySNORTsincethescanningwasnon-sequential(veryslow).RuleaddedtoSNORTinSeptember2004August13,2004,DetectedscanningforOracleserver(Ranked#2),ReportedbyCERT,June13,2004UndetectedbySNORTbecausethescanningwashiddenwithinanotherWebscanningOctober10,2005,Detectedadistributedwindowsnetworkingscanfrommultiplesourcelocations(Ranked#1)PolicyViolationsAugust8,2005,IdentifiedmachinerunningMicrosoftPPTPVPNserveronnon-standardports(Ranked#1)UndetectedbySNORTsincethecollectedGREtrafficwaspartofthenormaltraffic

August102005&October30,2005,IdentifiedcompromisedmachinesrunningFTPserversonnon-standardports,whichisapolicyviolation(Ranked#1)ExampleofanomalousbehaviorfollowingasuccessfulTrojanhorseattackFebruary6,2006,TheIPaddress128.101.X.0(notarealcomputer,butanetworkitself)hasbeentargetedwithIPProtocol0trafficfromKorea(61.84.X.97)(badsinceIPProtocol0isnotlegitimate)February6,2006,DetectedacomputeronthenetworkapparentlycommunicatingwithacomputerinCaliforniaoveraVPNoronIPv6WormsOctober10,2005,DetectedseveralinstancesofslapperwormthatwerenotidentifiedbySNORTsincetheywerevariationsofexistingwormcodeFebruary6,2006,DetectedunsolicitedICMPECHOREPLYmessagestoacomputerpreviouslyinfectedwithStacheldractworm(aDDosagent)45DetectionofAnomaliesonReal46应用案例2

FraudDetection欺骗检测46应用案例2OnlineAuctions:GrowingFroud欺诈日增#1网上犯罪2006年，投诉超过40,000件平均损失>$602.5047Source:/media/annualreport/2006_IC3Report.pdfOnlineAuctions:GrowingFroud48PotentialBuyerCPotentialBuyerBPotentialBuyerA$$$Seller$$$BuyerATransactionWhatifsomethinggoesBAD?未交付欺诈OnlineAuctions:HowTheyWork48PotentialBuyerCPotentialBProblemDescription问题描述通过观察Byobserving拍卖者的行为模式与其他用户相互交流一些关于已暴露的欺诈者的知识预测在未来，谁可能犯欺诈接下来是更具体的说明……49ProblemDescription问题描述通过观察ByModelingFraudulentBehavior欺诈行为建模捕捉用户之间的关系，而不是个人行为模式关系图模型节点——每个用户边——两个用户成交潜在希望：全球性的图属性更难操纵50ModelingFraudulentBehavior欺ModelingFraudulentBehavior(contd.)欺诈者的行为如何反应在图中？与其他欺诈者间密切互动愚弄基于信誉的系统这是一种极好的检测方法，可以很容易地发现诈骗群体不太符合实际一个真实的eBay数据集的实验表明，他们很少拉帮结派510924530112149信誉ModelingFraudulentBehavior(ModelingFraudulentBehavior(contd.)那么，诈骗者是如何操作的?52=诈骗者=同谋=诚实者二部图核心ModelingFraudulentBehavior(ModelingFraudulentBehavior(contd.)3个角色诚实者Honest普通人，如：你、我诈骗者Fraudsters那些真正犯诈骗罪的人同谋Accomplices往日的行为像诚实的用户通过低成本的交易积累反馈的人偷偷提高信誉的诈骗者(例如：偶尔购买贵重物品的人)53ModelingFraudulentBehavior(ModelingFraudulentBehavior(contd.)为什么寻找二部图核心，而不是小集体？诈骗者之间不会之间联系一旦一次诈骗交易被曝光，相关的账目会被eBay扫描，并立即作废“架构重用”一次欺诈后同谋不比丢弃长时间积累信誉分数54ModelingFraudulentBehavior(ProblemDescription(Concrete)已知在线拍卖用户图关于一些已经暴露的诈骗者的知识检测二部图核心Bipartitecores55ProblemDescription(Concrete)Solution解决方案大量的方法可以用来检测二部图核心，

要使用哪一个？这是一个军备竞赛诈骗者势必会形成新的模式，试图突破你的系统适应他们千变万化的行为对诈骗者的行为建模，而不是生成图形模式56NONE!Solution解决方案大量的方法可以用来检测二部图核心，TheNetProbeAlgorithmNetProbe对拍卖图建模——马尔可夫随机域(MarkovRandomField)用预期诈骗者的行为对模型进行训练通过“置信传播”来推断节点最可能的标签

它不依赖于任何特定的图形模型，甚至是诈骗者与其他人相互交流的模式57TheNetProbeAlgorithmNetProbeMarkovRandomFields马尔可夫随机域图形模型推理问题节点可能的状态属于固定集合两个不同状态的节点间的连接似然性状态集={F,A,H

}连接似然性F

非常可能连接到AF

不大可能连接到F58MarkovRandomFields马尔可夫随机域图形MarkovRandomFields(contd.)训练模型连接似然性通过传播矩阵表达59FAHFЄ1-2ЄЄA0.52Є0.5-2ЄHЄ(1–

Є)/2(1–

Є)/2[i,j]=已知节点在状态i、有一个在状态

j的邻居节点，则它们之间的似然性F,F=Є~0F,A=1-2Є~1MarkovRandomFields(contd.)训MarkovRandomFields(contd.)重申马尔可夫随机域模型下的问题已知传播矩阵一些节点的初始状态推断其余节点最可能的状态60MarkovRandomFields(contd.)重BeliefPropagation置信传播通过迭代消息传播计划来解决推理问题用有限的理论担保来进行启发式计划在很多领域的问题中实践都得到了很好的结果(尤其是物理方面!)61BeliefPropagation置信传播通过迭代消息传BeliefPropagation:Algorithm算法消息mij

从节点

i传播到节点j针对节点

i考虑节点

j

在哪个状态？每次迭代每个节点与它所接收到的消息相结合，计算它自己的置信度每个节点基于自己最新计算出的置信度，将消息传递给自己的邻居继续传递，直到置信度收敛62BeliefPropagation:AlgorithmBeliefPropagation:Details细节63Messagecomputation消息计算Beliefcomputation置信度计算使用传播矩阵进行变换将邻居处得到的消息结合在一起BeliefPropagation:Details细节

BeliefPropagation:Example举例64ACBEDBeliefPropagation:Example举TheNetProbeAlgorithm已知的诈骗者的初始状态为F初始化其它节点，无刻意偏向每次迭代对于每个节点通过结合前次达到收到的消息，计算自身置信度通过传播矩阵，将自身置信度转化为消息传递给每一个邻居继续迭代，直到收敛用最可能的状态对每个节点进行标记65TheNetProbeAlgorithm已知的诈骗者的初

Evaluation:RealDatasets评价：真实数据来自eBay的真实数据66,130

用户和795,320交易对数据形象为期2个月的爬行多层并行履带式架构Java+MySQL一直进行，直到我们不能在eBay发现黑名单为止66Evaluation:RealDatasets评价：Evaluation:eBayDataset评价度量：精密/二次行动?完全正确的结果并不知道诈骗者没有完全暴露未来进行诈骗行为的可能性不能确定eBay不公开提供超过6个月的信息很无奈，我们不得不做出一个主观评价67Evaluation:eBayDataset评价度量：精Evaluation:eBayDataset(contd.)68通过NetProbe方法检测二部图核心确认欺诈=Evaluation:eBayDataset(contPracticalConsiderations实际考虑如果图形发生变化，会怎样?新的用户出现，新的交易发生如果小范围图形发生变化，则从新开始计算置信度拓扑结构上的改变带来的影响本质上应当局部化69PracticalConsiderations实际考虑如PracticalConsiderations(contd.)增量式的NetProbe新节点或边的

k近邻的传播置信度初步试验表明：在精确度近乎零损失的情况下，执行时间降低80%进一步切实改进并行爬行的基础架构用户界面显示可疑的图模式70PracticalConsiderations(contSystemOverview系统综述71SystemOverview系统综述71内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献72内容提纲异常挖掘及其应用72参考文献[P4]J.Naisbitt,Megatrends:TenNewDirectionsTransformingOurLives.NewYork:WarnerBooks,1982.[P7]XiuyaoSong,MingxiWu,ChristopherJermaine,SanjayRanka,ConditionalAnomalyDetection,IEEETransactionsonDataandKnowledgeEngineering,2006.[P21.22]Knorr,Ng,AlgorithmsforMiningDistance-BasedOutliersinLargeDatasets,VLDB98.[P22]S.Ramaswamy,R.Rastogi,S.Kyuseok:EfficientAlgorithmsforMiningOutliersfromLargeDataSets,ACMSIGMODConf.OnManagementofData,2000.[P23.25.26]Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.73参考文献[P4]J.Naisbitt,Megatren利用SPSS软件进行异常检测利用SPSS软件进行异常检测

异常检测建模

方法具体如下所示：在回归模型诊断里面，一般称预测值与实际值的偏差为"残差",残差有几种表示方法:标准化残差,学生化残差等等，按照需要取一种残差，再按照某种标准取一个阀值来限定异常点，只要那个点的残差大于阀值，就可以认为它是异常点。75

异常检测建模

方法具体如下所示：75SPSS在异常检测中应用Step01：选定对话框打开SPSS软件，选择菜单栏中的【File(文件)】→【Open(打开)】→【Data(数据)】命令，弹出【OpenData(打开数据)】对话框。Step02：选定打开文件类型在数据表格中填写如下图所示的数据。接着，点击【File(文件)】→【Save

(保存)】。填写保存数据的位置，完成数据的保存操作。76SPSS在异常检测中应用Step01：选定对话框76SPSS在异常检测中应用77SPSS在异常检测中应用77SPSS在异常检测中应用Step03：打开对话框选择菜单栏中的【Analyze(分析)】→【Regression（回归）】→【Linear（线性）】命令，弹出【LinearRegression（线性回归）】对话框，这是线性回归分析的主操作窗口。78SPSS在异常检测中应用Step03：打开对话框78SPSS在异常检测中应用Step04：选择因变量在【LinearRegression（线性回归）】对话框左侧的候选变量列表框中选择一个变量，将其添加至【Dependent（因变量）】列表框中，即选择该变量作为多元线性回归的因变量。Step05：选择自变量在【LinearRegression（线性回归）】对话框左侧的候选变量列表框中选择一个变量，将其添加至【Independent(s)（自变量）】列表框中，即选择该变量作为一元线性回归的自变量。79SPSS在异常检测中应用Step04：选择因变量79SPSS在异常检测中应用如下图所示：80SPSS在异常检测中应用如下图所示：80SPSS在异常检测中应用Step06：样本的筛选从主对话框的候选变量列表框中选择一个变量，将其移至【SelectionVariable（选择变量）】列表框中，这表示要按照这个变量的标准来筛选样本进行回归分析。具体操作可以在Rule窗口中实现。Step07：选择个案标签从候选变量列表框中选择一个变量进入【CaseLabels（个案诊断）】列表框中，它的取值将作为每条记录的标签。这表示在指定作图时，以哪个变量作为各样本数据点的标志变量。设置离群值为381SPSS在异常检测中应用Step06：样本的筛选81SPSS在异常检测中应用如下图所示：82SPSS在异常检测中应用如下图所示：82SPSS在异常检测中应用Step08：单击【OK】按钮，结束操作，SPSS软件自动输出结果。83由上表可知复相关系数R=0.898，决定系数R方=0.806，均小于1，由决定系数看出回归方程的显著性不高，接下来看方差分析表3SPSS在异常检测中应用Step08：单击【OK】按钮，结束SPSS在异常检测中应用由表3知F值为8.283较小，说明x1、x2、x3整体上对y的影响不太显著。84SPSS在异常检测中应用84SPSS在异常检测中应用回归方程为

85SPSS在异常检测中应用85SPSS在异常检测中应用86对数据用spss进行分析得：从表中可以看出,绝对值最大的学生化残差SRE=2.11566,小于3,因而根据学生化残差诊断认为数据不存在异常值.绝对值最大的删除学生化残差为SDR=3.83214,因而根据学生化删除残差诊断认为第6个数据为异常值.其中中心化杠杆值0.64187,cook距离为3.21601位于第一大.因此第6个数据为异常值.SPSS在异常检测中应用86对数据用spss进行分析得：从表数据挖掘西安电子科技大学软件学院课件88数据挖掘与商务智能

DataMining&BusinessIntelligence西安电子科技大学软件学院主讲人：黄健斌

第八章异常检测

1数据挖掘与商务智能

DataMining&Busin内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献内容提纲异常挖掘及其应用内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献内容提纲异常挖掘及其应用什么是异常(Outlier)？Hawkins的定义：异常是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。Weisberg的定义：异常是与数据集中其余部分不服从相同统计模型的数据。Samuels的定义：异常是足够地不同于数据集中其余部分的数据。Porkess的定义：异常是远离数据集中其余部分的数据什么是异常(Outlier)？Hawkins的定义：异常是在异常数据具有特殊的意义和很高的实用价值

现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，异常数据通常作为噪音而忽略，许多数据挖掘算法试图降低或消除异常数据的影响。而在有些应用领域识别异常数据是许多工作的基础和前提，异常数据会带给我们新的视角。如在欺诈检测中，异常数据可能意味欺诈行为的发生，在入侵检测中异常数据可能意味入侵行为的发生。异常数据具有特殊的意义和很高的实用价值现有数据挖掘研究大异常检测的应用领域电信、保险、银行中的欺诈检测与风险分析发现电子商务中的犯罪行为灾害气象预报税务局分析不同团体交所得税的记录，发现异常模型和趋势海关、民航等安检部门推断哪些人可能有嫌疑海关报关中的价格隐瞒营销定制：分析花费较小和较高顾客的消费行为医学研究中发现医疗方案或药品所产生的异常反应计算机中的入侵检测运动员的成绩分析应用异常检测到文本编辑器，可有效减少文字输入的错误

……异常检测的应用领域电信、保险、银行中的欺诈检测与风险分析

什么是异常挖掘？

异常挖掘可以描述为：给定N个数据对象和所期望的异常数据个数，发现明显不同、意外，或与其它数据不一致的前k个对象。异常挖掘问题由两个子问题构成：(1)如何度量异常；(2)如何有效发现异常。什么是异常挖掘？

异常挖掘可以描述为：给定N个数据对象为什么会出现异常数据？测量、输入错误或系统运行错误所致数据内在特性所决定客体的异常行为所致由于异常产生的机制是不确定的，异常挖掘算法检测出的“异常数据”是否真正对应实际的异常行为，不是由异常挖掘算法来说明、解释的，只能由领域专家来解释，异常挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。为什么会出现异常数据？测量、输入错误或系统运行错误所致异常数据实例一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的；一个公司的高层管理人员的工资明显高于普通员工的工资可能成为异常数据但却是合理的数据(如平安保险公司2007年5位高管税后收入超过了1000万元)；一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致；一张信用卡出现明显的高额消费也许是因为是盗用的卡。异常数据实例一个人的年龄为-999就可能是由于程序处理缺省数异常数据与众不同但具有相对性：

高与矮，疯子与常人。类似术语：

Outliermining，Exceptionmining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘。异常数据与众不同但具有相对性：98内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献11内容提纲异常挖掘及其应用MainProblems主要问题典型正常区域的定义不易正常对象和离群点之间的界线不明确离群点的确切概念随应用领域而异训练/验证已标记数据的可用性数据可能包含噪声恶意对手的存在，反检测正常行为不断演变99MainProblems主要问题典型正常区域的定义不易1100内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献13内容提纲异常挖掘及其应用101AnomalyDetectionSchemes异常检测方法一般步骤构建“正常”行为的资料集资料集可以是针对数据整体的图案或者汇总统计通过使用“正常”资料集检测异常行为异常行为是特征与“正常”资料有显著差别的观察对象异常检测方法的类型分类和聚类基于统计的方法基于距离和基于密度的方法基于图形的方法14AnomalyDetectionSchemes异异常检测上下文异常检测集体异常检测在线异常检测分布异常检测异常点检测基于分类基于规则基于神经网络基于支持向量机基于最近邻基于密度基于距离统计有参数的无参数的基于聚类其他基于信息理论基于谱分解基于可视化AnomalyDetectionSchemes异常检测方法102异常检测上下文异常检测集体异常检测在线异常检测分布异常检测异主要思想基于已标记的训练数据，对正常事件(和(极少)异常事件)构建一个分类模型，以此对每一个新的未知事件进行分类分类模型必须能够处理倾斜(不均衡)的类分布分类监督分类技术

需要了解正常类和异常类建立分类，以区分正常事件和已知的异常事件半监督分类技术

只需要了解正常类使用改进的分类模型学习正常行为，然后将检测到的偏离正常行为的对象作为异常行为Ⅰ.Classification-BasedTechniques分类103主要思想Ⅰ.Classification-BasedTeⅠ.Classification-BasedTechniques分类优点监督分类技术

模型很容易理解在多种已知异常对象的检测中具有高精度半监督分类技术

模型很容易理解正常行为可以被准确学习缺点监督分类技术

需要正常类的标记和异常类的标记不能检测未知的和新兴的异常对象半监督分类技术

需要正常类的标记可能存在高误报率：先前未知(但合法)的数据记录可能被认为是异常的104Ⅰ.Classification-BasedTechniⅡ.Clustering-BasedTechniques聚类关键假设正常数据记录属于大型的、密集的集群，而异常数据记录不属于任何集群或者形成极小的集群按照标签分类半监督：

聚集正常数据，以创建正常行为模式。如果一个新实例不属于或者不靠近任何集群，那么就是异常无监督：

在聚类过程所需步骤之后，需要进行后处理来决定集群的大小，集群间的距离用来判别数据点是否异常应用基于聚类的方法进行异常检测不适合任何集群的数据记录(集群残差)

小集群低密度集群或局部异常(远离属于同一聚类的其他点)105Ⅱ.Clustering-BasedTechniques106基本思想将数据聚类划分为不同密度的簇选择小簇中的点作为候选离群点计算非候选点形成的簇和候选点间的距离如果候选点距离非候选点形成的簇较远，那么他们是离群点

Ⅱ.Clustering-BasedTechniques聚类19基本思想Ⅱ.Clustering-BasedTec优点不需要监督易适应在线/增量模式，适用于时空数据的异常检测缺点代价极大使用索引结构(k-d树，R*树)可能能够减轻该问题如果正常点不能创建任何簇，那么该方法可能会失败在高维空间中，数据是稀疏的，任意两个数据记录间的距离可能会非常相似聚类算法可能不会得到有意义的簇Ⅱ.Clustering-BasedTechniques聚类107优点Ⅱ.Clustering-BasedTechniqu

Ⅲ.NN-BasedTechniques最近邻方法关键假设正常点有近邻，而离群点远离其他节点一般为二步法计算每个数据记录和其邻居间的关系分析邻居关系，以确定该数据记录异常与否分类基于距离的方法离群点是远离其他节点的数据点基于密度的方法离群点是低密度区域的数据点108Ⅲ.NN-BasedTechniques最近邻方法关键优点可以应用于无监督或半监督环境中(对数据分布不作出任何假设)

缺点如果正常点没有足够数量的邻居，该方法可能会失败代价极大在高维空间中，数据是稀疏的，相似度的概念不能起到很大作用两个数据记录间的距离会由于稀疏而变得十分相似，以至于每个数据记录都可能被视为潜在的离群点

Ⅲ.NN-BasedTechniques最近邻方法109优点Ⅲ.NN-BasedTechniques最近邻方法

Ⅲ.NN-BasedTechniques最近邻方法基于距离的方法对于数据集中的点O，如果数据集中至少有p(百分比)的节点到点O的距离超过d，那么就认为O是数据集中的离群点，记为DB(p,d)*基于密度的方法计算特定区域的局部密度，将低密度区域的实例报为潜在离群点方法局部离群因子(LocalOutlierFactor,LOF)连接离群因子(ConnectivityOutlierFactor,COF‏）多粒度偏差因子(Multi-GranularityDeviationFactor,MDEF)*Knorr,Ng,AlgorithmsforMiningDistance-BasedOutliersinLargeDatasets,VLDB98110Ⅲ.NN-BasedTechniques最近邻方法基于(1)基于距离的NN方法基于距离的方法有两种不同的策略第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少来判定异常；如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为异常，也就是将没有足够邻居的对象看成是基于距离的异常。利用k最近邻距离的大小来判定异常。使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的异常程度由到它的k-最近邻的距离给定。这种方法对k的取值比较敏感。如果k太小(例如1)，则少量的邻近异常点可能导致较低的异常程度。如果k太大，则点数少于k的簇中所有的对象可能都成了异常点。(1)基于距离的NN方法基于距离的方法有两种不同的策略到k-最近邻的距离的计算k-最近邻的距离：一个对象的异常点得分由到它的k-最近邻的距离给定。异常点得分的最低值为0，最高值是距离函数的可能最大值----如无穷大到k-最近邻的距离的计算k-最近邻的距离：基于距离的异常点检测例1请问该二维数据集中，当k=5时，哪个点具有最高的异常点得分？基于距离的异常点检测例1请问该二维数据集中，当k=5时，基于距离的异常点检测例2请问该二维数据集中，当k=5时，哪个点具有最高的异常点得分？基于距离的异常点检测例2请问该二维数据集中，当k=5时，基于距离的异常检测的优缺点优点：基于距离的异常点检测方案简单缺点：时间复杂度O(m2)，不适用于大数据集不能处理不同密度区域的数据集，因为它使用全局阈值，不能考虑这种密度的变化基于距离的异常检测的优缺点优点：不能处理不同密度区域的数据集CDAB当k=5时，哪个点具有最高的异常点得分,B的异常点得分和D的异常点得分哪个低？例：不能处理不同密度区域的数据集CDAB当k=5时，哪个点具有最局部离群因子法(LocalOutlierFactor,LOF)Example:

p2

p1

p3Distancefromp3tonearestneighborDistancefromp2tonearestneighbor(2)LocalOutlierFactor(LOF)基于密度的NN方法*-Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.117在NN方法中，p2

并没有被认为是离群点,而在LOF

方法中发现

p1

和

p2

都是离群点NN方法可能认为p3

是离群点,但LOF方法不会局部离群因子法(LocalOutlierFactor,118(2)LocalOutlierFactor(LOF)基于密度的NN方法对每一个数据点q，计算到第k个近邻的距离(k-distance)对任意两个数据，计算可达距离(reach-dist)

reach-dist(p,o)=max{k-distance(o),d(p,o)}31(2)LocalOutlierFactor(L119(2)LocalOutlierFactor(LOF)基于密度的NN方法计算局部可达密度(localreachabilitydensity,lrd)基于数据p的MinPts-NN的平均可达距离的逆

lrd(p)

=

计算

LOF(p)作为p的k近邻平均局部可达密度比率数据记录p的局部可达密度为

LOF(p)=

*-Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.32(2)LocalOutlierFactor(LO(2)LocalOutlierFactor(LOF)基于密度的NN方法*-Breunig,etal,LOF:IdentifyingDensity-BasedLocalOutliers,KDD2000.对象p的离群因子不为空，则称p为离群点平均局部可达密度比率

p

的MinPts-NN邻居很容易看出：

p的LOF值越高，则p的局部可达密度越低，

p的MinPts-NN的局部可达密度越高.120(2)LocalOutlierFactor(LOF内容提纲异常挖掘及其应用异常检测面临的主要问题异常数据挖掘方法简介异常检测的应用案例参考文献内容提纲异常挖掘及其应用应用案例1

IntrusionDetection入侵检测122应用案例1

IntrusionDetectionCaseStudy:DataMininginIntrusionDetection随着互联网的不断发展，越来越多的组织易受到网络攻击网络攻击的复杂性和严重性都在增长安全机制总有不可避免的漏洞防火墙不足以确保计算机网络的安全性内线攻击123

19901991199219931994199519961997199819992000200120022003计算机应急反应协调中心的事故报告攻击复杂性vs.入侵技术知识源：/archive/ppt/cyberterror.pptSapphire/SlammerWorm攻击30分钟后的地理分布源：CaseStudy:DataMininginIntr

WhatareIntrusions?入侵124扫描活动攻击者计算机网络易损机器入侵活动试图绕过计算机系统的安全机制通常的行为有攻击者从因特网访问系统内线攻击已授权用户试图获取或误用未被授权的权限典型的入侵场景

受损机器WhatareIntrusions?入侵37扫描活动攻

IDS-AnalysisStrategy入侵检测系统策略分析误用检测(Misusedetection)是基于与专家提供的已知攻击相关的外部知识模式现有的方法：(签字)模式匹配，专家系统，状态转换分析，数据挖掘主要的限制：不能检测异常的或者意料之外的攻击签名数据库要为每一个新发现的攻击进行修改异常检测(Anomalydetection)

是基于代表用户、主机或网络的正常行为的配置文件，检测这个文件中有显著偏差的攻击主要好处：潜在地对不可预见攻击的识别能力主要限制因素：可能有较高的误报率，因为检测偏差不一定代表真实攻击主要方法：统计方法，专家系统，聚类，神经网络，支持向量机，异常检测计划125IDS-AnalysisStrategy入侵检测系统

IntrusionDetection入侵检测126入侵检测系统

将可能执行入侵检测的软硬件结合当可能有入侵发生时拉响警报

传统入侵检测系统(IDS)工具(例如:SNORT)是基于已知签名攻击SNORT规则实例(MS-SQL“Slammer”worm)‏any->udpport1434(content:"|81F10301049B81F101|";

content:"sock";content:"send")限制当出现新的入侵类型时，签名数据库必须手动修改无法检测新兴的网络威胁部署新创建的签名会造成整个计算机系统的重大延迟数据挖掘可以缓解这些限制IntrusionDetection入侵检测www.sn

DataMiningforIntrusionDetection入侵检测数据挖掘对基于数据挖掘的入侵检测兴趣日增攻击造成签名难以建立攻击具有隐蔽性不可预见的/未知的/新出现的攻击分布式/协调的攻击针对入侵检测的数据挖掘方法误用检测(Misusedetection)

基于已标记的数据集(数据标记为”正常”或”异常”)建立预测模型，判别已知入侵在检测多种已知攻击中具有高精度不能检测未知的和新兴的攻击异常检测(Anomalydetection)

从”正常”行为检测异常攻击作为偏差潜在高误报率：以前不可见(但合法)系统行为也可能被认为是异常网络流量综述(Summarizationofnetworktraffic)127DataMiningforIntrusionDetDataMiningforIntrusionDetection误用检测：建立预测模型128绝对的当时的持续的分类测试集训练集模型学习分类器绝对的异常检测发现的规则:{SrcIP=5,

DestPort=139,

Bytes[150,200]}-->{ATTACK}使用关联规则对攻击进行综述DataMiningforIntrusionDete

AnomalyDetectiononRealNetworkData

真实网络数据的入侵检测

在明尼苏达州和美国陆军研究实验室，使用异常检测来检测各种侵扰活动或可以活动其中许多入侵不能被广泛应用的异常检测工具检测到，如SNORT异常/攻击被MINDS发现扫描活动不规范的行为违反策略蠕虫129MINDS–MinnesotaIntrusionDetectionSystem明尼苏达异常检测系统MINDS网络数据捕获装置异常检测……获取异常Human

analyst检测

新的攻击Summaryandcharacterization

ofattacks已知攻击检测Detected

knownattacks标记特征抽取相关模式分析MINDSAT过滤NetflowtoolstcpdumpAnomalyDetectiononRealNet三组特征TCP连接个体的基本特征源&目的地IPFeatures1&2源&目的端口

Features

3

&4协议

Feature5持续时间

Feature6每包字节Feature7字节数Feature8基于时间的特征网络中对于相同的源(目的地)IP地址,最后T秒钟唯一目的地(源)IP地址数目–Feat