第9章-离群点检测

数据挖掘天津大学计算机科学与技术学院喻梅目录CONTENTS1.529.19.2离群点的定义与类型离群点检测Chapter9.1离群点定义与类型‒离群点：是一个数据对象，它显著不同于其他数据对，好像它是被不同的机制产生的一样。•例如:不同寻常的信用卡交易‒离群点不同于噪声数据•噪声数据是被观测变量的随机误差或方差•噪声数据应在离群点检测前被删除‒离群点产生原因：•计算的误差或者操作的错误所致•数据本身的可变性或弹性所致什么是离群点：9.1离群点定义与类型4图9-1区域O中的对象为离群点5三类:全局离群点,条件离群点和集体离群点。全局离群点(或点异常)‒如果一个数据对象显著的偏离数据集的其余部分，则这个数据对象为全局离群点。条件离群点‒一个数据对象，如果关于对象的特定情境，它显著偏离其他对象。–例如：多伦多的温度为28。C，这是离群点吗？(取决于冬天还是夏天）–数据对象的属性划分为两组。•情境属性:定义对象的情境，例如，时间和地点。•行为属性:定义对象的特征,并用来评估对象关于它所处的情境是否为离群点。例如，温度。离群点的类型：9.1离群点定义与类型6‒集体离群点•给定一个数据集，数据对象的一个子集作为整体显著偏离整个数据集，数据对象的这个子集称为集体离群点。•应用：在入侵检测时，多台计算机不断地相互发送拒绝服务包，则它们可以视为集体离群点，所涉及的计算机可能受到攻击。•数据集可能有多种类型的离群点。•一个对象可能属于多种类型的离群点。9.1离群点定义与类型图9-2黑色对象形成集体离群点Chapter9.2离群点检测–离群点的检测方法有很多，每种方法在检测时，都会对正常数据对象或离群点做出假设。从这个假设的角度考虑，离群点检测方法可以分为:•基于统计学的离群点检测；•基于近邻的离群点检测；•基于聚类的离群点检测;•基于分类的局部离群点检测。89.2离群点检测1.统计学方法:99.2离群点检测基于统计分布的检测方法是为数据集构建一个概率统计模型（例如正态、泊松、二项式分布等，其中的参数由数据求得），然后根据模型采用不和谐检验识别离群点。图9.1给出了基于统计分布的检测流程。设定数据集的分布模型不和谐检验发现离群点图9.1基于统计的离群点检测流程不和谐检验需要检查两个假设：工作假设和备择假设。工作假设指的是如果某样本点的某个统计量相对于数据分布的是显著性概率充分小，则认为该样本点是不和谐的，工作假设被拒绝，此时备择假设被采用，它声明该样本点来自于另一个分布模型。如果某个样本点不符合工作假设，那么认为它是离群点。如果它符合备择假设，认为它是符合某一备择假设分布的离群点。工作假设H为，假设n个对象的整个数据集来自一个初始的分布模型F，即：H:oi∈F，其中i=1，2，…，n不和谐检验就是检查对象oi关于分布F是否显著地大（或小）。109.2离群点检测不和谐检验:119.2离群点检测基于正态分布的一元离群点检测•正态分布曲线特点：N（μ，σ2）•变量值落在（μ-σ，μ+σ）区间的概率是68.27%•变量值落在（μ-2σ，μ+2σ）区间的概率是95.44%•变量值落在（μ-3σ，μ+3σ）区间的概率是99.73%129.2离群点检测基于正态分布的一元离群点检测一般的，设属性X取自具有期望值μ，方差σ2的正态分布N（μ，σ2），如果属性X满足：P(|X|≥C)=α,其中C是一个选定的常量，则X以概率1-α为离群点。例9.1基于统计方法检测年龄离群点设儿童上学的具体年龄总体服从正态分布，所给的数据集是某地区随机选取的开始上学的20名儿童的年龄。具体的年龄特征如下：年龄={6，7，6，8，9，10，8，11，7，9，12，7，11，8，13，7，8，14，9，12}相应的统计参数是：均值m=9.1；标准差s=2.3。如果选择数据分布的阈值q按如下公式计算：q=m±2×s，则阈值下限与上限分别为4.5和13.7。如果将工作假设描述为：儿童上学的年龄分布在阈值设定区间内，则依据不和谐检验，不符合工作假设的，即在[4.5，13.7]区间以外的年龄数据都是潜在的离群点，将最大值取整为13，所以年龄为14的孩子可能是个例外。139.2离群点检测统计方法的离群点检测的优缺点:‒优点•建立在非常标准的统计学原理之上，当数据和检验的类型十分充分时，检验十分有效。‒缺点①多数情况下，数据的分布是未知的或数据几乎不可能用标准的分布来拟合，虽然可以使用混合分布对数据建模，基于这种模型开发功能更强的离群挖掘方案，但这种模型更复杂，难以理解和使用。②当观察到的分布不能恰当地用任何标准的分布建模时，基于统计方法的挖掘不能确保所有的离群点被发现，而且要确定哪种分布最好的拟合数据集的代价也非常大。③即使这类方法在低维（一维或二维）时的数据分布己知，但在高维情况下，估计数据对象的分布是极其困难的，对每个点进行分布测试，需要花费更大的代价。149.2离群点检测2.基于近邻的离群点检测:‒假定：离群点对象与它最近邻的邻近性显著偏离数据集中其它对象与它们邻近之间的邻近性。‒两种方法：•基于距离的离群点检测。•基于密度的离群点检测。159.2离群点检测基于距离的离群点检测:•如果数据对象集D中大多数对象都远离d，即都不在d的r-邻域内，d可视为一个离群点。•r是距离阈值，α是分数阈值，如果有则d是一个DB(r,α)离群点。169.2离群点检测'|(,')ddistddrD基于距离的离群点检测:•如何计算DB(r,α)-离群点：嵌套循环对每个对象(),计算与其它对象之间的距离，统计r-邻域中其它对象的个数，一旦找到n*α个，内循环可以中止。ni1idid179.2离群点检测基于密度的离群点检测:图9.2基于密度的局部离群点检测的必要性聚类簇C1属于低密度区域，聚类簇C2属于高密度区域。依据传统的基于密度的离群点检测算法，C1中任何一个数据点q与其近邻的距离大于数据点p2与其在C2中的近邻的距离，数据点p2会被看作是正常点，当然能检测出数据点p1是离群点。189.2离群点检测•基于密度的离群点检测能够检测出基于距离的异常算法所不能识别的一类异常数据——局部离群点•局部离群点:是指一个对象相对于它的局部邻域，特别是关于邻域密度，它是远离的。C2C1p1p2图9.2中，p1相当于C2的密度来说是一个局部离群点，这就形成了基于密度的局部离群点检测的基础。此时，评估的是一个对象是离群点的程度，这种“离群”程度就是作为对象的局部离群点因子（LOF），然后计算。199.2离群点检测数据集中的数据点𝑥和𝑥𝑖，𝑥到𝑥𝑖的可达距离reach_distk(𝑥，𝑥𝑖)定义为_(,)max{(),(,)}kikiireachdistxxdistxdistxx其中，distk(𝑥𝑖)指数据点𝑥𝑖到其第k个近邻的距离，dist(𝑥，𝑥𝑖)指数据点𝑥和𝑥𝑖的距离。通常，距离度量选用欧式距离，而且𝑥到𝑥𝑖的可达距离reach_distk(𝑥，𝑥𝑖)与𝑥𝑖到𝑥的可达距离reach_distk(𝑥𝑖，𝑥)一般并不相同。•局部可达密度对象p的局部可达密度定义为p的k最近邻点的平均可达密度的倒数•局部离群点因子表征了称p是离群点的程度，定义如下：209.2离群点检测()()_(,)ikkixKNNxklrdxreachdistxx()()()()ikixKNNxkklrdxlrdxLOFxk‒结论•LOF算法计算的离群度不在一个通常便于理解的范围[0,1]，而是一个大于1的数，并且没有固定的范围。而且数据集通常数量比较大，内部结构复杂，LOF极有可能因为取到的近邻点属于不同数据密度的聚类簇，使得计算数据点的近邻平均数据密度产生偏差，而得出与实际差别较大甚至相反的结果。‒优点•通过基于密度的局部离群点检测就能在样本空间数据分布不均匀的情况下也可以准确发现离群点。219.2离群点检测3.基于聚类的方法:229.2离群点检测•该对象属于某个簇吗？如果不，则它被识别为离群点。•该对象与最近的簇之间的距离很远吗？如果是，则它是离群点。•该对象是小簇或稀疏簇的一部分吗？如果是，则该簇中的所有对象都是离群点。基与聚类的离群点检测挖掘方法如下：•基于对象离群因子法•假设数据集D被聚类算法划分为k个簇C={C1，C2，…，Ck}，对象p的离群因子（OutlierFactor）OF1(p)定义为p与所有簇间距离的加权平均值：•𝑂𝐹1𝑝=|𝐶𝑗||𝐷|∙𝑑(𝑝，𝐶𝑗)𝑘𝑗=1(9-6)•其中，𝑑(𝑝，𝐶𝑗)表示对象p与第j个簇Cj之间的距离。239.2离群点检测基与聚类的离群点检测挖掘方法如下：•两阶段离群点挖掘方法如下：①对数据集D采用一趟聚类算法进行聚类，得到聚类结果C={C1，C2，…，Ck}②计算数据集D中所有对象p的离群因子OF1(p)，及其平均值Ave_OF和标准差Dev_OF，满足条件：249.2离群点检测OF1(p)≥Ave_OF+β∗Dev_OF(1≤β≤2)的对象判定为离群点。通常取β=1或1.285。基与聚类的离群点检测挖掘方法如下：•例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)，试计算所有对象的离群因子。259.2离群点检测图9-5基于聚类的离群点检测二维数据集基与聚类的离群点检测挖掘方法如下：•解：根据对象p的离群因子（OutlierFactor）OF1(p)的定义，对于𝑝1点有：𝑂𝐹1𝑝1=𝐶𝑗𝐷∙𝑑𝑝1，𝐶𝑗=811𝑘𝑗=16−1.752+8−2.252+111(6−5)2+(8−2)2+311(6−5.5)2+(8−7.5)2=5.9•对于𝑝2有：𝑂𝐹1𝑝2=𝐶𝑗𝐷∙𝑑𝑝2，𝐶𝑗=811𝑘𝑗=15−1.752+2−2.252+111(5−5)2+(2−2)2+311(5−5.5)2+(2−7.5)2=3.4•可见，点𝑝1较𝑝2更可能成为离群点。269.2离群点检测基与聚类的离群点检测挖掘方法如下：•同理可求得所有对象的离群因子，结果如表9-1所示。。•进一步求得所有点的离群因子平均值•Ave_OF=2.95，•标准差Dev_OF=1.3，•假设𝛽=1，则阈值𝐸=𝐴𝑣𝑒_𝑂𝐹+𝛽∗𝐷𝑒𝑣_𝑂𝐹=2.95+1.3=4.25，•离群因子大于4.25的对象可视为离群点，𝑝1和𝑝2都是离群点，但相对而言，𝑝1更有可能成为离群点。279.2离群点检测XYOF1122.2132.3112.9212.6221.7231.9685.9242.5322.2574.8523.4表9-1离群因子表基与聚类的离群点检测挖掘方法如下：•基于簇的离群因子法•假设数据集D被聚类算法划分为k个簇C={C1，C2，…，Ck}，簇Ci离群因子（OutlierFactor）OF2(Ci)定义为簇Ci与其他所有簇间距离的加权平均值：𝑂𝐹2𝐶𝑖=|𝐶𝑗||𝐷|∙𝑑(𝐶𝑖，𝐶𝑗)𝑘𝑗=1(9-7)•如果一个簇离几个大簇的距离都比较远，则表明该簇偏离整体比较远，其离群因子也较大。OF2(Ci)度量了Ci偏离整个数据集的程度，其值越大，说明Ci偏离整体越远。289.2离群点检测基与聚类的离群点检测挖掘方法如下：•基于簇的离群因子离群点检测算法描述如下：①聚类：对数据集D进行聚类，得到聚类结果C={C1，C2，…，Ck};②确定离群簇：计算每个簇Ci(1≤𝑖≤𝑘)的离群因子OF2(Ci)，按OF2(Ci)递减的顺序重新排列Ci(1≤𝑖≤𝑘)，求满足：|𝐶𝑗||𝐷|≥𝜀（0𝜀1）𝑘𝑗=1(9-8)的最小下标b，将簇C1，C2，…，Cb标识为“outlier”类