第7章-聚类分析(孤立点分析)

1第7章.聚类分析什么是聚类（Clustering）分析?聚类分析中的数据类型主要聚类方法分类划分方法（PartitioningMethods）层次方法（HierarchicalMethods）基于密度的方法（Density-BasedMethods）基于网格的方法（Grid-BasedMethods）基于模型的聚类方法（Model-BasedClusteringMethods）孤立点分析（OutlierAnalysis）小结2孤立点分析什么是孤立点?对象的集合,它们与数据的其它部分不一致孤立点可能是度量或执行错误所导致的孤立点也可能是固有的数据变异性的结果问题给定一个n个数据点或对象的集合,及预期的孤立点的数目k,发现与剩余的数据相比是相异的,例外的,或不一致的前k个对象两个子问题：定义在给定的数据集合中什么样的数据可以被认为是不一致的找到一个有效的方法来挖掘这样的孤立点3孤立点分析应用:信用卡欺诈检测电信欺诈检测顾客分割:确定极低或极高收入的客户的消费行为医疗分析:发现对多种治疗方式的不寻常的反应孤立点的定义是非平凡的如果采用一个回归模型,余量的分析可以给出对数据“极端”的很好的估计当在时间序列数据中寻找孤立点时,它们可能隐藏在趋势的,周期性的,或者其他循环变化中,这项任务非常棘手当分析多维数据时,不是任何特别的一个,而是维值的组合可能是极端的.对于非数值型的数据（如分类数据）,孤立点的定义要求特殊的考虑4孤立点分析采用数据可视化方法来进行孤立点探测如何？不适用于包含周期性曲线的数据对于探测有很多分类属性的数据,或高维数据中的孤立点效率很低方法统计学方法基于距离的方法基于密度的方法5基于统计学的孤立点检测对给定的数据集合假设了一个分布或概率模型(例如,正态分布),然后根据模型采用不一致性检验(discordancytest)来确定孤立点检验要求的参数数据集参数:例如,假设的数据分布分布参数:例如平均值和方差和预期的孤立点的数目统计学的不一致性检验需要检查的两个假设工作假设(workinghypothesis)替代假设(alternativehypothesis)6基于统计学的孤立点检测工作假设H是一个命题：n个对象的整个数据集合来自一个初始的分布模型F,即H：Oi∈F，i=1,2,…,n不一致性检验验证一个对象Oi关于分布F是否显著地大(或者小)依据关于数据的可用知识,已提出不同的统计量用于不一致性检验假设某个统计量被选择用于不一致性检验,对象Oi的该统计量的值为Vi,则构建分布T估算显著性概率SP(Vi)=Prob(TVi)如果某个SP(Vi)是足够的小,那么Oi是不一致的,工作假设被拒绝.替代假设被采用,它声明Oi来自于另一个分布模型G7检测一元正态分布中的离群点2221xey8检测一元正态分布中的离群点若考察的属性服从正态分布,可以用属性的出现概率确定是否离群点.出现概率低于一个阈值,就可以认为该属性是一个离群点.确定的方法由下面定义:9检测一元正态分布中的离群点出现概率在2.5%左边或者右边的属性都可以作为离群点,因为概率小于给定的阈.10检测二元正态分布中的离群点);;;;(~),(2211rmmNyx11用mahalanobis距离来衡量是否离群点,距离超过一个阈值就是离群点.),(21xxXyxyxyxssssS12检测二元正态分布中的离群点13检测二元正态分布中的离群点若A、B的距离超过一个阈值，它们就是离群点。A的Mahalanobis距离比B大,证明A离中心点更远.14基于统计学的孤立点检测结果非常依赖于模型F的选择Oi可能在一个模型下是孤立点,在另一个模型下是非常有效的值替代分布在决定检验的能力上是非常重要的不同的替代分布固有的替代分布(inherentalternativedistribution):所有对象来自分布F的工作假设被拒绝,而所有对象来自另一个分布G的替代假设被接受混合替代分布(mixturealternativedistribution)：不一致的值不是F分布中的孤立点,而是来自其他分布的污染物滑动替代分布(slippagealternativedistribution)：所有的对象(除了少量外)根据给定的参数,独立地来自初始的模型F，而剩余的对象是来自修改过的F的独立的观察15基于统计学的孤立点检测检测孤立点有两类基本的过程批(block)过程:或者所有被怀疑的对象都被作为孤立点对待,或者都被作为一致数据而接受连续的过程：该过程的一个例子是内部出局(inside-out)过程主要思想首先检验最不可能是孤立点的对象.如果它是孤立点,那么所有更极端的值都被认为是孤立点;否则,检验下一个极端的对象,依次类推该过程往往比批过程更为有效16基于统计学的孤立点检测缺点绝大多数检验是针对单个属性的,而许多数据挖掘问题要求在多维空间中发现孤立点统计学方法要求关于数据集合参数的知识(如,数据分布),但是在许多情况下,数据分布可能是未知的当没有特定的检验时,统计学方法不能确保所有的孤立点被发现;或者观察到的分布不能恰当地被任何标准的分布来模拟17基于距离的孤立点检测为了解决统计学方法带来的一些限制，引入了基于距离的孤立点的概念基于距离的孤立点:DB(p,d)-孤立点是数据集T中的一个对象o,使得T中的对象至少有p部分与o的距离大于d将基于距离的孤立点看作是那些没有“足够多”邻居的对象.这里的邻居是基于距给定对象的距离来定义的对许多不一致性检验来说,如果一个对象o根据给定的检验是一个孤立点,那么对恰当定义的p和d，o也是一个DB(p,d)孤立点例如，如果离平均值偏差3或更大的对象被认为是孤立点，假设一个正态分布，那么这个定义能够被一个DB(0.9988,0.13σ)孤立点所概括18基于距离的异常检测指定参数pct和dmin，如果数据集合D中的对象至少有pct部分与对象o的距离大于dmin，则称对象o是以pct和dmin为参数的基于距离的异常，记为DB(pct,dmin)。19算法：寻找基于距离的异常检测（D，dmin，M）输入：数据对象集合D，邻域半径dmin，一个异常的dmin邻域内最多对象数目M输出：D中的异常对象步骤：（1）forD中每个数据对象ti，do（1.1）counti=0（1.2）forD中除ti的每个对象tj（1.2.1）ifdist(ti,tj)dmin，thencounti+1//dist（）是距离函数（1.2.2）ifcountiM，then标记ti不是一个异常，处理下一个ti（1.3）ifcountiM，then标记ti是一个异常，处理下一个ti基于距离的异常检测20基于偏离的孤立点检测通过检查一组对象的主要特征来确定孤立点与给出的描述偏离的对象被认为是孤立点序列异常技术(sequentialexceptiontechnique)模仿人类从一系列推测类似的对象中识别异常对象的方式术语异常集(exceptionset):它是偏离或孤立点的集合,被定义为某类对象的最小子集,这些对象的去除会导致剩余集合的相异度的最大减少相异度函数(dissimilarityfunction)：是满足如下条件的任意函数：当给定一组对象时，如果对象间相似，返值就较小。对象间的相异度越大，函数返回的值就越大21基于密度的异常检测相关概念基于密度的异常检测算法22相关概念(1)1）k距离对象p的k距离k-distance(p)是p到它的k最近邻的最大距离。它定义为p与对象oD之间的距离d(p，o)，满足：（1）D中至少存在k个对象到p的距离小于或等于p到o的距离。（2）D中最多有k-1个对象到p的距离比p到o的距离小。k与聚类算法DBSCAN中的MinPts相同，用于定义对象p的局部邻域。2）k距离邻域对象p的k距离邻域Nk_distance(p)(p)包含所有与p的距离不超过k_distance(p)的对象，即：Nk-distance(p)(p)={qD﹨{p}|d(p，q)k-distance(p)}23op1p2reach-distk(p2,o)reach-distk(p1,o)=k-distance(o)3）可达距离给定自然数k，对象p关于对象o的可达距离reach_distk(p，o)为：reach_distk(p，o)=max{k_distance(o)，d(p，o)}。reach_distk(p，o)的含义是，如果对象p远离o，则两者间的可达距离就是它们间的实际距离。但是，如果p在o的k距离邻域内，则实际距离用o的k距离取代。k距离越大，在相同邻域中对象的可达距离越相似。图9.5所示的是ｋ=4时对象p1和p2关于对象o的可达距离。图9.7k=4时对象p1和p2的可达距离相关概念(2)244）局部可达密度用MinPts表示p的邻域中最小的对象个数，那么对象p的局部可达密度为对象p与它的MinPts-邻域的平均可达距离的倒数：5）局部异常因子LOF对象p的局部异常因子定义为：LOF是对象p和它的最近邻的局部可达密度的比率的平均值。p的局部可达密度越小，p的MinPts最近邻的局部可达密度越大，LOFMinPts(p)越高。LOF表征了p的异常程度：如果p不是局部异常，则LOFMinPts(p)接近于1；p是局部异常的程度越大，LOFMinPts(p)越高。|)(|),(_1)()(pNopdistreachplrdMinPtspNoMinPtsMinPtsMinPts|)(|)()()()(pNplrdolrdpLOFMinPtspNoMinPtsMinPtsMinPtsMinPts相关概念(3)25基于密度的异常检测算法(1)LOF表征了对象p的异常程度，因此，可以通过计算LOF(p)来判断对象p是否是局部异常。基于密度的异常检测算法的核心是对于指定的近邻个数k，基于对象的最近邻计算对象的LOF。算法：基于密度的异常检测算法（D，MinPts，k）输入：数据对象集合D，近邻个数MinPts，异常对象数目k输出：k个异常步骤：（1）forD中每个数据对象p（1.1）确定p的MinPts距离邻域NMinpts_distance(p)(p)26基于密度的异常检测算法(2)（1.2）使用p的最近邻（即NMinPts_distance(p)(p)中的对象），计算p的局部可达密度lrdMinPts(p)（1.3）计算NMinPts_distance(p)(p)中每个对象o的局部可达密度lrdMinPts(o)（1.4）计算p的局部异常因子LOFMinPts(p)（2）输出D中LOF值最大的k个对象基于密度的异常检测算法的时间复杂度为O(n2)（其中n是D中对象个数）。算法给出了对象异常程度的定量度量，并且在数据具有不同密度的区域也能够很好地识别局部异常。27基于偏离的孤立点检测例:给定n个对象的子集合{x1,…,xn},一个可能的相异度函数是集合中对象的方差基数函数(cardinalityfunction)：一般是给定的集合中对象的数目平滑因子(smoothingfactor)：一个为序列中的每个子集计算的函数.它估算从原始的数据集合中移走子集合可以带来的相异度的降低程度.平滑因子值最大的子集是异常集一般的寻找异常集的任务可以是NP完全的(即,难处理的).28基于偏离的孤立点检测一个顺序的方法在计算上是可行的,能够用一个线性的算法实现不考虑估算当前子集关于其补集的相异度,该算法从集合中选择了一个子集合的序列来分析对每个子集合,它确定其与序列中前一个子集合的相异度差异为了减轻输入顺序对结果的任何可能的影响,以上的处理过程可以被重复若干次,每一次采用子集合的一个不同的随机