离群点检测课件.ppt

1、数据挖掘天津大学计算机科学与技术学院喻梅目录 CONTENTS1.52 9.19.2离群点的定义与类型离群点检测Chapter 9.1离群点定义与类型 离群点：是一个数据对象，它显著不同于其他数据对，好像它是被不同的机制产生的一样。例如:不同寻常的信用卡交易 离群点不同于噪声数据噪声数据是被观测变量的随机误差或方差噪声数据应在离群点检测前被删除 离群点产生原因：计算的误差或者操作的错误所致数据本身的可变性或弹性所致什么是离群点：9.1 离群点定义与类型4 图9-1区域O中的对象为离群点5 三类:全局离群点,条件离群点和集体离群点。全局离群点(或点异常)如果一个数据对象显著的偏离数据集的其余部分

2、，则这个数据对象为全局离群点。条件离群点 一个数据对象，如果关于对象的特定情境，它显著偏离其他对象。例如：多伦多的温度为28。C，这是离群点吗？(取决于冬天还是夏天）数据对象的属性划分为两组。情境属性:定义对象的情境，例如，时间和地点。行为属性:定义对象的特征,并用来评估对象关于它所处的情境是否为离群点。例如，温度。离群点的类型：9.1 离群点定义与类型6 集体离群点给定一个数据集，数据对象的一个子集作为整体显著偏离整个数据集，数据对象的这个子集称为集体离群点。应用：在入侵检测时，多台计算机不断地相互发送拒绝服务包，则它们可以视为集体离群点，所涉及的计算机可能受到攻击。数据集可能有多种类型的离

3、群点。一个对象可能属于多种类型的离群点。9.1 离群点定义与类型图9-2黑色对象形成集体离群点Chapter 9.2离群点检测 离群点的检测方法有很多，每种方法在检测时，都会对正常数据对象或离群点做出假设。从这个假设的角度考虑，离群点检测方法可以分为:基于统计学的离群点检测；基于近邻的离群点检测；基于聚类的离群点检测;基于分类的局部离群点检测。8 9.2离群点检测1.统计学方法:9 9.2离群点检测基于统计分布的检测方法是为数据集构建一个概率统计模型（例如正态、泊松、二项式分布等，其中的参数由数据求得），然后根据模型采用不和谐检验识别离群点。图9.1给出了基于统计分布的检测流程。图9.1 基于

4、统计的离群点检测流程 不和谐检验需要检查两个假设：工作假设和备择假设。工作假设指的是如果某样本点的某个统计量相对于数据分布的是显著性概率充分小，则认为该样本点是不和谐的，工作假设被拒绝，此时备择假设被采用，它声明该样本点来自于另一个分布模型。如果某个样本点不符合工作假设，那么认为它是离群点。如果它符合备择假设，认为它是符合某一备择假设分布的离群点。工作假设H为，假设n个对象的整个数据集来自一个初始的分布模型F，即：H:oiF，其中i=1，2，n不和谐检验就是检查对象oi关于分布F是否显著地大（或小）。10 9.2离群点检测不和谐检验:11 9.2离群点检测基于正态分布的一元离群点基于正态分布的

5、一元离群点检测检测 正态分布曲线特点：N（，2）变量值落在（-，+）区间的概率是68.27%变量值落在（-2，+2）区间的概率是95.44%变量值落在（-3，+3）区间的概率是99.73%12 9.2离群点检测基于正态分布的一元离群点基于正态分布的一元离群点检测检测一般的，设属性X取自具有期望值，方差2的正态分布N（，2），如果属性X满足：P(|X|C)=,其中C是一个选定的常量，则X以概率1-为离群点。例9.1 基于统计方法检测年龄离群点设儿童上学的具体年龄总体服从正态分布，所给的数据集是某地区随机选取的开始上学的20名儿童的年龄。具体的年龄特征如下：年龄=6，7，6，8，9，10，8，11

6、，7，9，12，7，11，8，13，7，8，14，9，12相应的统计参数是：均值m=9.1；标准差s=2.3。如果选择数据分布的阈值q按如下公式计算：q=m2s，则阈值下限与上限分别为4.5和13.7。如果将工作假设描述为：儿童上学的年龄分布在阈值设定区间内，则依据不和谐检验，不符合工作假设的，即在4.5，13.7区间以外的年龄数据都是潜在的离群点，将最大值取整为13，所以年龄为14的孩子可能是个例外。13 9.2离群点检测统计方法的离群点检测的优缺点:优点 建立在非常标准的统计学原理之上，当数据和检验的类型十分充分时，检验十分有效。缺点 多数情况下，数据的分布是未知的或数据几乎不可能用标准的

7、分布来拟合，虽然可以使用混合分布对数据建模，基于这种模型开发功能更强的离群挖掘方案，但这种模型更复杂，难以理解和使用。当观察到的分布不能恰当地用任何标准的分布建模时，基于统计方法的挖掘不能确保所有的离群点被发现，而且要确定哪种分布最好的拟合数据集的代价也非常大。即使这类方法在低维（一维或二维）时的数据分布己知，但在高维情况下，估计数据对象的分布是极其困难的，对每个点进行分布测试，需要花费更大的代价。14 9.2离群点检测2.基于近邻的离群点检测:假定：离群点对象与它最近邻的邻近性显著偏离数据集中其它对象与它们邻近之间的邻近性。两种方法：基于距离的离群点检测。基于密度的离群点检测。15 9.2离

8、群点检测基于距离的离群点检测:如果数据对象集D中大多数对象都远离d，即都不在d的r-邻域内，d可视为一个离群点。r 是距离阈值，是分数阈值，如果有则d是一个DB(r,)离群点。16 9.2离群点检测|(,)ddist d drD基于距离的离群点检测:如何计算DB(r,)-离群点：嵌套循环对每个对象 (),计算 与其它对象之间的距离，统计 r-邻域中其它对象的个数，一旦找到n *个，内循环可以中止。ni 1idid17 9.2离群点检测基于密度的离群点检测:图9.2 基于密度的局部离群点检测的必要性 聚类簇C1属于低密度区域，聚类簇C2属于高密度区域。依据传统的基于密度的离群点检测算法，C1中任

9、何一个数据点q与其近邻的距离大于数据点p2与其在C2中的近邻的距离，数据点p2会被看作是正常点，当然能检测出数据点p1是离群点。18 9.2离群点检测 基于密度的离群点检测能够检测出基于距离的异常算法所不能识别的一类异常数据局部离群点 局部离群点:是指一个对象相对于它的局部邻域，特别是关于邻域密度，它是远离的。图9.2中，p1相当于C2的密度来说是一个局部离群点，这就形成了基于密度的局部离群点检测的基础。此时，评估的是一个对象是离群点的程度，这种“离群”程度就是作为对象的局部离群点因子（LOF），然后计算。19 9.2离群点检测_(,)max(),(,)kikiireachdistx xdis

10、txdist x x 局部可达密度 对象p的局部可达密度定义为p的k最近邻点的平均可达密度的倒数 局部离群点因子 表征了称p是离群点的程度，定义如下：20 9.2离群点检测()()_(,)ikkixKNN xklrdxreachdistx x()()()()ikixKNN xkklrdxlrdxLOF xk 结论 LOF算法计算的离群度不在一个通常便于理解的范围0,1，而是一个大于1的数，并且没有固定的范围。而且数据集通常数量比较大，内部结构复杂，LOF极有可能因为取到的近邻点属于不同数据密度的聚类簇，使得计算数据点的近邻平均数据密度产生偏差，而得出与实际差别较大甚至相反的结果。优点 通过基于

11、密度的局部离群点检测就能在样本空间数据分布不均匀的情况下也可以准确发现离群点。21 9.2离群点检测3.基于聚类的方法:22 9.2离群点检测 该对象属于某个簇吗？如果不，则它被识别为离群点。该对象与最近的簇之间的距离很远吗？如果是，则它是离群点。该对象是小簇或稀疏簇的一部分吗？如果是，则该簇中的所有对象都是离群点。基与聚类的离群点检测挖掘方法如下：23 9.2离群点检测基与聚类的离群点检测挖掘方法如下：两阶段离群点挖掘方法如下：对数据集D采用一趟聚类算法进行聚类，得到聚类结果C=C1，C2，Ck 计算数据集D中所有对象p的离群因子OF1(p)，及其平均值Ave_OF和标准差Dev_OF，满足

12、条件：24 9.2离群点检测基与聚类的离群点检测挖掘方法如下：例9.2基于对象的离群因子法 对于图9-5所示的二维数据集，比较点p1(6，8)，p2(5，2)，哪个更有可能成为离群点。假设数据集经过聚类后得到聚类结果为C=C1，C2，C3，图中红色圆圈标注，三个簇的质心分别为：C1(5.5，7.5)、C2(5，2)、C3(1.75，2.25)，试计算所有对象的离群因子。25 9.2离群点检测图9-5 基于聚类的离群点检测二维数据集基与聚类的离群点检测挖掘方法如下：26 9.2离群点检测基与聚类的离群点检测挖掘方法如下：27 9.2离群点检测XYOF1122.2132.3112.9212.622

13、1.7231.9685.9242.5322.2574.8523.4表9-1 离群因子表基与聚类的离群点检测挖掘方法如下：28 9.2离群点检测基与聚类的离群点检测挖掘方法如下：29 9.2离群点检测基与聚类的离群点检测挖掘方法如下：30 9.2离群点检测图9-5 基于聚类的离群点检测二维数据集基与聚类的离群点检测挖掘方法如下：31 9.2离群点检测3.基于聚类的方法:32 9.2离群点检测 基于聚类的离群点检测方法具如下优点。首先，它们可以检测离群点，而不要求数据是有标号的，即它们以无监督方式检测。它们对许多类型的数据都有效。簇可以看做数据的概括。一旦得到簇，基于聚类的方法只需要把对象与簇进行

14、比较，以确定该对象是否是离群点。这一过程通常很快，因为与对象总数相比，簇的个数通常很小。基于聚类的方法的缺点是，它的有效性高度依赖于所使用的聚类方法。这些方法对于离群点检测而言可能不是最优的。对于大型数据集，聚类方法通常开销很大，这可能成为一个瓶颈。4.基于分类的方法33 9.2离群点检测 使用基于分类检测离群点的时候，分类器可以使用前面介绍的常用的分类器，如SVM、KNN、决策树等。为解决正常数据和离群点数据分布的不均衡，可以使用一类模型进行分类。简单来说就是构建一个描述正常数据的分离器，不属于正常的数据就是离群点。例9.2 使用SVM检测离群点。在图9.3中，三个圆圈内的样本是正常数据，圆圈外的数据是离群点。可以使用圆圈内的正常数据训练一个决策边界，通过这个边界就可以区分数据是正常数据还是非正常数据离群点。即，如果给定的新对象在正常类的决策边界内，则被视为正常的；如果新对象在边界外，则被视为离群点。这样就不需要训练离群点数据模型，避免了由于数据分布不均衡造成的分类器准确率低的现象。34 9.2离群点检测图9.3 使用SVM检测离群点数据样本THANKS FOR YOUR ATTENTION感谢指导！