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

1、1数据挖掘与商务智能Data Mining&Business Intelligence西安电子科技大学软件学院主讲人：黄健斌 第八章第八章 异常检测异常检测 内容提纲n异常挖掘及其应用n异常检测面临的主要问题n异常数据挖掘方法简介n异常检测的应用案例n参考文献内容提纲n异常挖掘及其应用n异常检测面临的主要问题n异常数据挖掘方法简介n异常检测的应用案例n参考文献什么是异常(Outlier)？nHawkins的定义的定义：异常是在数据集中偏离大部分数偏离大部分数据的数据据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。nWeisberg的定义：异常是与数据集中其余部分不

2、服从相同统计模型的数据。nSamuels的定义：异常是足够地不同于数据集中其余部分的数据。nPorkess的定义：异常是远离数据集中其余部分的数据异常数据具有特殊的意义和很高的实用价值 n 现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，异常数据通常作为噪音而忽略，许多数据挖掘算法试图降低或消除异常数据的影响。而在有些应用领域识别异常数据是许多工作的基础和前提，异常数据会带给我们新的视角。n如在欺诈检测中，异常数据可能意味欺诈行为的发生，在入侵检测中异常数据可能意味入侵行为的发生。异常检测的应用领域n电信、保险、银行中的欺诈检测与风险分析 n发现电子商务中的犯罪行为

3、n灾害气象预报n税务局分析不同团体交所得税的记录，发现异常模型和趋势 n海关、民航等安检部门推断哪些人可能有嫌疑 n海关报关中的价格隐瞒n营销定制：分析花费较小和较高顾客的消费行为n医学研究中发现医疗方案或药品所产生的异常反应n计算机中的入侵检测n运动员的成绩分析n应用异常检测到文本编辑器，可有效减少文字输入的错误 n 什么是异常挖掘？n异常挖掘可以描述为：给定N个数据对象和所期望的异常数据个数，发现明显不同、意外，或与其它数据不一致的前k个对象。n异常挖掘问题由两个子问题构成：(1)如何度量异常；(2)如何有效发现异常。为什么会出现异常数据？n测量、输入错误或系统运行错误所致n数据内在特性所

4、决定n客体的异常行为所致由于异常产生的机制是不确定的，异常挖掘算法检测出的“异常数据”是否真正对应实际的异常行为，不是由异常挖掘算法来说明、解释的，只能由领域专家来解释，异常挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。异常数据实例n一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的；n一个公司的高层管理人员的工资明显高于普通员工的工资可能成为异常数据但却是合理的数据(如平安保险公司2007年 5位高管税后收入超过了1000万元)；n一部住宅电话的话费由每月200元以内增加到数千元可能就

5、因为被盗打或其它特殊原因所致；n一张信用卡出现明显的高额消费也许是因为是盗用的卡。n异常数据与众不同但具有异常数据与众不同但具有相对性：相对性：高与矮，疯子与常人。n类似术语：类似术语：Outlier mining，Exception mining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘。11内容提纲n异常挖掘及其应用n异常检测面临的主要问题n异常数据挖掘方法简介n异常检测的应用案例n参考文献Main Problems 主要问题n典型正常区域的定义不易n正常对象和离群点之间的界线不明确n离群点的确切概念随应用领域而异n训练/验证已标记数据的可用性n数据可能包含噪声n恶意对手的存在，反检测n

6、正常行为不断演变1213 内容提纲n异常挖掘及其应用n异常检测面临的主要问题n异常数据挖掘方法简介n异常检测的应用案例n参考文献14 Anomaly Detection Schemes 异常检测方法 o 一般步骤n构建“正常”行为的资料集 资料集可以是针对数据整体的图案或者汇总统计n通过使用“正常”资料集检测异常行为 异常行为是特征与“正常”资料有显著差别的观察对象o 异常检测方法的类型n分类和聚类n基于统计的方法n基于距离和基于密度的方法n基于图形的方法异常检测异常检测上下文异常检测上下文异常检测集体异常检测集体异常检测在线异常检测在线异常检测分布异常检测分布异常检测异常点检测异常点检测基于

7、分类基于分类基于规则基于规则基于神经网络基于神经网络基于支持向量机基于支持向量机基于最近邻基于最近邻基于密度基于密度基于距离基于距离统计统计有参数的有参数的无参数的无参数的基于聚类基于聚类其他其他基于信息理论基于信息理论基于谱分解基于谱分解基于可视化基于可视化Anomaly Detection Schemes异常检测方法 15n主要思想基于已标记的训练数据，对正常事件(和(极少)异常事件)构建一个分类模型，以此对每一个新的未知事件进行分类n分类模型必须能够处理倾斜(不均衡)的类分布n分类监督分类技术 需要了解正常正常类和异常异常类建立分类，以区分正常事件和已知的异常事件半监督分类技术 只需要了

8、解正常正常类使用改进的分类模型学习正常行为，然后将检测到的偏离正常行为的对象作为异常行为.Classification-Based Techniques分类16.Classification-Based Techniques分类n优点监督分类技术 模型很容易理解在多种已知异常对象的检测中具有高精度半监督分类技术 模型很容易理解正常行为可以被准确学习n缺点监督分类技术 需要正常类的标记和异常类的标记不能检测未知的和新兴的异常对象半监督分类技术 需要正常类的标记可能存在高误报率：先前未知(但合法)的数据记录可能被认为是异常的17.Clustering-Based Techniques 聚类n关键假

9、设正常数据记录属于大型的、密集的集群，而异常数据记录不属于任何集群或者形成极小的集群n按照标签分类半监督：聚集正常数据，以创建正常行为模式。如果一个新实例不属于或者不靠近任何集群，那么就是异常无监督：在聚类过程所需步骤之后，需要进行后处理来决定集群的大小，集群间的距离用来判别数据点是否异常n应用基于聚类的方法进行异常检测不适合任何集群的数据记录(集群残差)小集群低密度集群或局部异常(远离属于同一聚类的其他点)1819n基本思想将数据聚类划分为不同密度的簇选择小簇中的点作为候选离群点计算非候选点形成的簇和候选点间的距离如果候选点距离非候选点形成的簇较远，那么他们是离群点.Clustering-B

10、ased Techniques 聚类n优点不需要监督易适应在线/增量模式，适用于时空数据的异常检测n缺点代价极大使用索引结构(k-d树，R*树)可能能够减轻该问题如果正常点不能创建任何簇，那么该方法可能会失败在高维空间中，数据是稀疏的，任意两个数据记录间的距离可能会非常相似聚类算法可能不会得到有意义的簇.Clustering-Based Techniques 聚类20.NN-Based Techniques 最近邻方法n关键假设正常点有近邻，而离群点远离其他节点n一般为二步法1.计算每个数据记录和其邻居间的关系2.分析邻居关系，以确定该数据记录异常与否n分类基于距离的方法离群点是远离其他节点的

11、数据点基于密度的方法离群点是低密度区域的数据点21n优点可以应用于无监督或半监督环境中(对数据分布不作出任何假设)n缺点如果正常点没有足够数量的邻居，该方法可能会失败代价极大在高维空间中，数据是稀疏的，相似度的概念不能起到很大作用两个数据记录间的距离会由于稀疏而变得十分相似，以至于每个数据记录都可能被视为潜在的离群点.NN-Based Techniques 最近邻方法22.NN-Based Techniques 最近邻方法n基于距离的方法对于数据集中的点O，如果数据集中至少有p(百分比)的节点到点O的距离超过d，那么就认为O是数据集中的离群点，记为DB(p,d)*n基于密度的方法计算特定区域的

12、局部密度，将低密度区域的实例报为潜在离群点方法n局部离群因子(Local Outlier Factor,LOF)n连接离群因子(Connectivity Outlier Factor,COF）n多粒度偏差因子(Multi-Granularity Deviation Factor,MDEF)*Knorr,Ng,Algorithms for Mining Distance-Based Outliers in Large Datasets,VLDB9823(1)基于距离的NN方法n基于距离的方法有两种不同的策略u第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少来判定异常；如果一个点的邻域内

13、包含的对象少于整个数据集的一定 比例则标识它为异常，也就是将没有足够邻居的对象看成是基于距离的异常。u利用k最近邻距离的大小来判定异常。使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的异常程度由到它的k-最近邻的距离给定。这种方法对k的取值比较敏感。如果k太小(例如1)，则少量的邻近异常点可能导致较低的异常程度。如果k太大，则点数少于k的簇中所有的对象可能都成了异常点。到k-最近邻的距离的计算nk-最近邻的距离：一个对象的异常点得分由到它的k-最近邻的距离给定。异常点得分的最低值为0，最高值是距离函数的可能最大值-如无穷大基于距离的异常点检测 例1请问该二维数据集中，当k=5时，哪

14、个点具有最高的异常点得分？基于距离的异常点检测 例2请问该二维数据集中，当k=5时，哪个点具有最高的异常点得分？基于距离的异常检测的优缺点n优点：基于距离的异常点检测方案简单 n缺点：时间复杂度O(m2)，不适用于大数据集不能处理不同密度区域的数据集，因为它使用全局阈值，不能考虑这种密度的变化不能处理不同密度区域的数据集CDAB当k=5时，哪个点具有最高的异常点得分,B的异常点得分和D的异常点得分哪个低？例：n局部离群因子法(Local Outlier Factor,LOF)Example:p2 p1 p3Distance from p3 to nearest neighborDistance

15、 from p2 to nearest neighbor (2)Local Outlier Factor(LOF)基于密度的NN方法*-Breunig,et al,LOF:Identifying Density-Based Local Outliers,KDD 2000.30 在NN方法中，p2 并没有被认为是离群点,而在LOF 方法中发现 p1 和 p2 都是离群点 NN方法可能认为 p3 是离群点,但 LOF 方法不会31 (2)Local Outlier Factor(LOF)基于密度的NN方法n对每一个数据点q，计算到第到第k k个近邻的距离个近邻的距离(k-distance)n对任意

16、两个数据，计算可达距离可达距离(reach-dist)reach-dist(p,o)=maxk-distance(o),d(p,o)32(2)Local Outlier Factor(LOF)基于密度的NN方法n计算局部可达密度局部可达密度(local reachability density,lrd)基于数据p的MinPts-NN的平均可达距离的逆 lrd(p)=n计算 LOF(p)作为p的k近邻平均局部可达密度比率数据记录p的局部可达密度为 LOF(p)=MinPtsMinPts()()_(,)MinPtso NpNpreachdistp oMinPts()MinPts1()|()|()o

17、 Nplrd oNplrd p*-Breunig,et al,LOF:Identifying Density-Based Local Outliers,KDD 2000.(2)Local Outlier Factor(LOF)基于密度的NN方法*-Breunig,et al,LOF:Identifying Density-Based Local Outliers,KDD 2000.对象p的离群因子不为空，则称p为离群点平均局部可达密度比率 p 的MinPts-NN邻居很容易看出：p的LOF 值越高，则p的局部可达密度越低，p 的MinPts-NN的局部可达密度越高.33内容提纲n异常挖掘及其应

18、用n异常检测面临的主要问题n异常数据挖掘方法简介n异常检测的应用案例n参考文献应用案例应用案例 1 1 Intrusion Detection 入侵检测入侵检测35Case Study:Data Mining in Intrusion Detectionn随着互联网的不断发展，越来越多的组织易受到网络攻击n网络攻击的复杂性和严重性都在增长n安全机制总有不可避免的漏洞防火墙不足以确保计算机网络的安全性内线攻击360200004000060000800001000001200001234567891011121314 1990 1991 1992 1993 1994 1995 1996 1997

19、1998 1999 2000 2001 2002 2003计算机应急反应协调中心的事故报告计算机应急反应协调中心的事故报告攻击复杂性攻击复杂性 vs.入侵技术知识入侵技术知识源：源：www.cert.org/archive/ppt/cyberterror.pptSapphire/Slammer Worm攻击攻击30分钟后的地理分分钟后的地理分布布源：源：www.caida.org What are Intrusions?入侵37扫描活动扫描活动攻击者攻击者 计算机网络计算机网络易损机器易损机器 p 入侵活动试图绕过计算机系统的安全机制p 通常的行为有n攻击者从因特网访问系统n内线攻击已授权用户

20、试图获取或误用未被授权的权限p典型的入侵场景 受损机器受损机器 IDS-Analysis Strategy入侵检测系统策略分析n误用检测误用检测(Misuse detection)是基于与专家提供的已知攻击相关的外部知识模式现有的方法：(签字)模式匹配，专家系统，状态转换分析，数据挖掘主要的限制：不能检测异常的或者意料之外的攻击签名数据库要为每一个新发现的攻击进行修改n异常检测异常检测(Anomaly detection)是基于代表用户、主机或网络的正常行为的配置文件，检测这个文件中有显著偏差的攻击主要好处：潜在地对不可预见攻击的识别能力主要限制因素：可能有较高的误报率，因为检测偏差不一定代表

21、真实攻击主要方法：统计方法，专家系统，聚类，神经网络，支持向量机，异常检测计划38 Intrusion Detection入侵检测www.snort.org39p 入侵检测系统 n将可能执行入侵检测的软硬件结合n当可能有入侵发生时拉响警报 p 传统入侵检测系统(IDS)工具(例如:SNORT)是基于已知签名攻击已知签名攻击nSNORT 规则实例(MS-SQL“Slammer”worm)any-udp port 1434(content:|81 F1 03 01 04 9B 81 F1 01|;content:sock;content:send)p 限制n当出现新的入侵类型时，签名数据库必须手动

22、修改n无法检测新兴的网络威胁无法检测新兴的网络威胁n部署新创建的签名会造成整个计算机系统的重大延迟o 数据挖掘可以缓解这些限制 Data Mining for Intrusion Detection 入侵检测数据挖掘p对基于数据挖掘的入侵检测兴趣日增攻击造成签名难以建立攻击具有隐蔽性不可预见的/未知的/新出现的攻击分布式/协调的攻击p针对入侵检测的数据挖掘方法误用检测误用检测(Misuse detection)基于已标记的数据集(数据标记为”正常”或”异常”)建立预测模型，判别已知入侵在检测多种已知攻击中具有高精度不能检测未知的和新兴的攻击异常检测异常检测(Anomaly detection)

23、从”正常”行为检测异常攻击作为偏差潜在高误报率：以前不可见(但合法)系统行为也可能被认为是异常网络流量综述网络流量综述(Summarization of network traffic)40Data Mining for Intrusion Detection误用检测：建立预测模型41绝对的绝对的当时的当时的持续的持续的分类分类测试集测试集训练集训练集模型模型学习学习分类器分类器TidSrcIPStarttimeDest IPDestPortNumberof bytesAttack1206.135.38.95 11:07:20 160.94.179.223139192No2206.163.37

24、.95 11:13:56 160.94.179.219139195No3206.163.37.95 11:14:29 160.94.179.217139180No4206.163.37.95 11:14:30 160.94.179.255139199No5206.163.37.95 11:14:32 160.94.179.25413919Yes6206.163.37.95 11:14:35 160.94.179.253139177No7206.163.37.95 11:14:36 160.94.179.252139172No8206.163.37.95 11:14:38 160.94.179.

25、251139285Yes9206.163.37.95 11:14:41 160.94.179.250139195No10 206.163.37.95 11:14:44 160.94.179.249139163Yes1 0TidSrcIPStarttimeDest PortNumberof bytesAttack1206.163.37.81 11:17:51 160.94.179.208150?2206.163.37.99 11:18:10 160.94.179.235208?3206.163.37.55 11:34:35 160.94.179.221195?4206.163.37.37 11:

26、41:37 160.94.179.253199?5206.163.37.41 11:55:19 160.94.179.244181?绝对的绝对的异常检测异常检测发现的规则发现的规则:Src IP=206.163.37.95,Dest Port=139,Bytes 150,200-ATTACK使用关联规则使用关联规则对攻击进行综述对攻击进行综述TidSrcIPStarttimeDest IPNumberof bytesAttack1206.163.37.81 11:17:51 160.94.179.208150No2206.163.37.99 11:18:10 160.94.179.235208

27、No3206.163.37.55 11:34:35 160.94.179.221195Yes4206.163.37.37 11:41:37 160.94.179.253199No5206.163.37.41 11:55:19 160.94.179.244181Yes Anomaly Detection on Real Network Data真实网络数据的入侵检测n在明尼苏达州和美国陆军研究实验室，使用异常检测来检测各种侵扰活动或可以活动n其中许多入侵不能被广泛应用的异常检测工具检测到，如SNORTn异常/攻击被MINDS发现扫描活动不规范的行为违反策略蠕虫42MINDS Minnesota

28、Intrusion Detection System明尼苏达异常检测系统明尼苏达异常检测系统MINDS网络网络数据捕获装置数据捕获装置异常检测异常检测获取异常获取异常Humananalyst检测检测 新的攻击新的攻击Summary and characterizationof attacks已知攻击检测已知攻击检测Detected known attacks 标记标记特征抽取特征抽取相关模式相关模式分析分析MINDSAT过滤过滤uNet flow toolsutcpdumpn三组特征TCP 连接个体的基本特征源&目的地IP Features 1&2源&目的端口 Features 3&4协议 F

29、eature 5持续时间 Feature 6每包字节 Feature 7字节数 Feature 8基于时间的特征基于时间的特征网络中对于相同的源(目的地)IP地址,最后最后T T秒钟秒钟唯一目的地(源)IP地址数目 Features 9(13)最后最后T T秒钟秒钟从源(目的地)IP 到同一个目的地(源)端口的连接数目 Features 11(15)基于连接的特征基于连接的特征网络中对于相同的源(目的地)IP地址,最后最后N个连接中个连接中唯一目的地(源)IP地址数目-Features 10(14)最后最后N N个连接中个连接中从源(目的地)IP 到同一个目的地(源)端口的连接数目-Featu

30、res 12(16)43flagdst service h1 http S0h1 http S0h1 http S0h2 http S0h4 http S0h2 ftp S0syn floodnormalexisting features existing features uselessuselessflagdst service h1 http S0h1 http S0h1 http S0h2 http S0h4 http S0h2 ftp S0syn floodnormalflagdst service h1 http S0h1 http S0h1 http S0h2 http S0h4

31、 http S0h2 ftp S0syn floodnormalexisting features existing features uselessuselessdst service h1 http S0h1 http S0h1 http S0h2 http S0h4 http S0h2 ftp S0flag%S0707275000construct features with construct features with high information gainhigh information gaindst service h1 http S0h1 http S0h1 http S

32、0h2 http S0h4 http S0h2 ftp S0flag%S0707275000dst service h1 http S0h1 http S0h1 http S0h2 http S0h4 http S0h2 ftp S0flag%S0707275000construct features with construct features with high information gainhigh information gainFeature Extraction 特征抽取 Typical Anomaly Detection Output 典型异常检测输出p“slammer”蠕虫

33、病毒爆发48小时后44score srcIPsPort dstIPdPort protocol flagspackets bytes1234567891011121314151637674.6963.150.X.2531161128.101.X.29143417160,2)0,1829)000000000.8100.590000026676.6263.150.X.2531161160.94.X.134143417160,2)0,1829)000000000.8100.590000024323.5563.150.X.2531161128.101.X.185143417160,2)0,1829)0

34、00000000.8100.580000021169.4963.150.X.2531161160.94.X.71143417160,2)0,1829)000000000.8100.580000019525.3163.150.X.2531161160.94.X.19143417160,2)0,1829)000000000.8100.580000019235.3963.150.X.2531161160.94.X.80143417160,2)0,1829)000000000.8100.580000017679.163.150.X.2531161160.94.X.220143417160,2)0,18

35、29)000000000.8100.58000008183.5863.150.X.2531161128.101.X.108143417160,2)0,1829)000000000.8200.58000007142.9863.150.X.2531161128.101.X.223143417160,2)0,1829)000000000.8200.57000005139.0163.150.X.2531161128.101.X.142143417160,2)0,1829)000000000.8200.57000004048.49142.150.Y.1010128.101.X.12720481162,4

36、)0,1829)000000000.8300.56000004008.35200.250.Z.2027016 128.101.X.116462917162,4)0,1829)00000000000000103657.23202.175.Z.23727016 128.101.X.116414817162,4)0,1829)00000000000000103450.963.150.X.2531161128.101.X.62143417160,2)0,1829)000000000.8200.57000003327.9863.150.X.2531161160.94.X.223143417160,2)0

37、,1829)000000000.8200.57000002796.1363.150.X.2531161128.101.X.241143417160,2)0,1829)000000000.8200.57000002693.88142.150.Y.1010128.101.X.16820481162,4)0,1829)000000000.8300.56000002683.0563.150.X.2531161160.94.X.43143417160,2)0,1829)000000000.8200.57000002444.16142.150.Y.2360128.101.X.24020481162,4)0

38、,1829)000000000.8300.56000002385.42142.150.Y.1010128.101.X.4520481160,2)0,1829)000000000.8300.56000002114.4163.150.X.2531161160.94.X.183143417160,2)0,1829)000000000.8200.57000002057.15142.150.Y.1010128.101.X.16120481160,2)0,1829)000000000.8300.56000001919.54142.150.Y.1010128.101.X.9920481162,4)0,182

39、9)000000000.8300.56000001634.38142.150.Y.1010128.101.X.21920481162,4)0,1829)000000000.8300.56000001596.2663.150.X.2531161128.101.X.160143417160,2)0,1829)000000000.8200.57000001513.96142.150.Y.1070128.101.X.220481160,2)0,1829)000000000.8300.56000001389.0963.150.X.2531161128.101.X.30143417160,2)0,1829

40、)000000000.8200.57000001315.8863.150.X.2531161128.101.X.40143417160,2)0,1829)000000000.8200.57000001279.75142.150.Y.1030128.101.X.20220481160,2)0,1829)000000000.8300.56000001237.9763.150.X.2531161160.94.X.32143417160,2)0,1829)000000000.8300.56000001180.8263.150.X.2531161128.101.X.61143417160,2)0,182

41、9)000000000.8300.5600000连接到连接到“half-life”游戏服务器游戏服务器 的机器所对应的连接的机器所对应的连接“slammer”蠕虫病毒对应的异常连接蠕虫病毒对应的异常连接 进行进行ping扫描异常连接扫描异常连接Detection of Anomalies on Real Network Data真实网络数据中的异常检测uMINDS检测出的异常/攻击，包括扫描活动、蠕虫病毒以及像违反规则行为、内部攻击行为等不正常的行为。这些攻击中的大部分均可被MINDS检测出来，并被放在当前计算机应急反应协调中心(CERT/CC)的咨询列表中。u下面是MINDS检测出的入侵行为

42、的一些说明例子。nScansAugust 13,2004,Detected scanning for Microsoft DS service on port 445/TCP(Ranked#1)nReported by CERT as recent DoS attacks that needs further analysis(CERT August 9,2004)nUndetected by SNORT since the scanning was non-sequential(very slow).Rule added to SNORT in September 2004August 13

43、,2004,Detected scanning for Oracle server(Ranked#2),Reported by CERT,June 13,2004nUndetected by SNORT because the scanning was hidden within another Web scanningOctober 10,2005,Detected a distributed windows networking scan from multiple source locations(Ranked#1)nPolicy ViolationsAugust 8,2005,Iden

44、tified machine running Microsoft PPTP VPN server on non-standard ports(Ranked#1)nUndetected by SNORT since the collected GRE traffic was part of the normal traffic August 10 2005&October 30,2005,Identified compromised machines running FTP servers on non-standard ports,which is a policy violation(Ran

45、ked#1)nExample of anomalous behavior following a successful Trojan horse attackFebruary 6,2006,The IP address 128.101.X.0(not a real computer,but a network itself)has been targeted with IP Protocol 0 traffic from Korea(61.84.X.97)(bad since IP Protocol 0 is not legitimate)February 6,2006,Detected a

46、computer on the network apparently communicating with a computer in California over a VPN or on IPv6nWormsOctober 10,2005,Detected several instances of slapper worm that were not identified by SNORT since they were variations of existing worm codeFebruary 6,2006,Detected unsolicited ICMP ECHOREPLY m

47、essages to a computer previously infected with Stacheldract worm(a DDos agent)4546应用案例应用案例 2 2 Fraud Detection 欺骗检测欺骗检测Online Auctions:Growing Froud 欺诈日增n#1 网上犯罪2006年，投诉超过40,000件平均损失$602.5047Source:http:/www.ic3.gov/media/annualreport/2006_IC3Report.pdf48Potential Buyer CPotential Buyer BPotential B

48、uyer A$Seller$BuyerA TransactionWhat if something goes BAD?未交付欺诈未交付欺诈Online Auctions:How They WorkProblem Description 问题描述n通过观察By observing拍卖者的行为模式与其他用户相互交流一些关于已暴露的欺诈者的知识n预测在未来，谁可能犯欺诈n接下来是更具体的说明49Modeling Fraudulent Behavior 欺诈行为建模n捕捉用户之间的关系，而不是个人行为模式关系n图模型节点每个用户边两个用户成交n潜在希望：全球性的图属性更难操纵50Modeling Fr

49、audulent Behavior(contd.)n欺诈者的行为如何反应在图中？与其他欺诈者间密切互动愚弄基于信誉的系统这是一种极好的检测方法，可以很容易地发现诈骗群体n不太符合实际一个真实的eBay数据集的实验表明，他们很少拉帮结派510 924530112149信誉信誉Modeling Fraudulent Behavior(contd.)n那么，诈骗者是如何操作的?52=诈骗者诈骗者=同谋同谋=诚实者诚实者二部图核心二部图核心Modeling Fraudulent Behavior(contd.)n3个角色诚实者 Honest普通人，如：你、我诈骗者 Fraudsters那些真正犯诈骗罪

50、的人同谋 Accomplices往日的行为像诚实的用户通过低成本的交易积累反馈的人偷偷提高信誉的诈骗者(例如：偶尔购买贵重物品的人)53Modeling Fraudulent Behavior(contd.)n为什么寻找二部图核心，而不是小集体？诈骗者之间不会之间联系一旦一次诈骗交易被曝光，相关的账目会被eBay扫描，并立即作废“架构重用”一次欺诈后同谋不比丢弃长时间积累信誉分数54Problem Description(Concrete)n已知在线拍卖用户图关于一些已经暴露的诈骗者的知识n检测二部图核心 Bipartite cores55Solution 解决方案n大量的方法可以用来检测二部