第10章聚类方法(续)ppt课件.ppt

《第10章聚类方法(续)ppt课件.ppt》由会员分享，可在线阅读，更多相关《第10章聚类方法(续)ppt课件.ppt（87页珍藏版）》请在三一办公上搜索。

1、第10章 聚类方法,10.4 基于密度的聚类算法,很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。,10.4.1 DBSCAN算法,DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法是一种性能优越的基于密度的空间聚类算法。它的基本思想是，如果一个点p和另一个点q是密度相连的，则p和q属于同一个簇。,1. 相关概念,定义10.6 以数据集

2、D中一个点p为圆心，以为半径的圆形区域内的数据点的集合称为p的-邻域，用N(p)表示，即：N(p)=q | qD dist(p，q),点p的-邻域,定义10.7 给定一个参数MinPts，如果数据集D中的一个点p的-邻域至少包含MinPts个点（含点p自身），则称p为核心点。在图10.36中，如果MinPts=7，则p为核心点（核心点用实心圆点表示）。,为核心点,定义10.8 给定数据集D中的两个点p、q，如果q在p的-邻域内，而p是一个核心点，则称点q是从p出发直接密度可达的。在图10.36中，qN(p)，如果p是一个核心点，则q是从p出发直接密度可达。,为核心点， q是从p出发直接密度可达

3、,定义10.9 对于给定的和MinPts，如果数据集D中存在一个点链p1、p2、pn，p1=q，pn=p，对于piD（1in），pi+1是从pi出发直接密度可达的，则点p是从点q出发密度可达的。,点p是从点q密度可达的,定义10.10 对于给定的和MinPts，如果数据集D中存在如果存在点oD，使点p和q都是从o出发密度可达的，那么点p到q是密度相连的。密度相连关系是对称的。如图10.38所示，p到q是密度相连的，则q到p是密度相连的。,到q是密度相连的,定义10.12 数据集D中不是核心点，但落在某个核心点的邻域内的点称为边界点。边界点可能落在多个核心点的邻域内，边界点为稠密区域边缘上的点。

4、数据集D中不是核心点也不是边界点的点称为噪声点，噪声点不属于任何簇，它属于稀疏区域中的点。例如，如图10.39所示，MinPts=4，用实心圆点表示核心点，用空心圆点表示边界点，用方形点表示噪声点。,核心点、边界点和噪声点,2. DBSCAN算法,DBSCAN算法基本思想是：首先选取一个未标记类别的核心点，并创建一个新簇；然后，寻找所有从该核心点出发关于和MinPts密度可达的点，并标记为该簇。重复这个过程，直至处理完所有点，即没有未标记簇的核心点。,输入：数据集D，邻域半径，最小点数MinPts输出：关于（，MinPts）的所有簇的集合方法：其过程描述如下：,do 从数据集D中抽取一个未处理

5、过的点p; if (p是核心点) 找出所有从p出发关于（，MinPts）密度可达的点，形成一个簇; else p是边界点或噪声点（非核心点），跳出本次循环，寻找下一点； until (所有点都被处理);,【例10.11】有如表10.14所示的数据集，其在二维空间中的分布情况如图10.40所示。用户输入=1，MinPts=4，采用DBSCAN算法进行聚类的过程如下。,散点图,DBSCAN算法的优点是基于密度定义，相对抗噪音，能处理任意形状和大小的簇。其缺点是对参数（，MinPts）敏感，当簇的密度变化太大时，会产生较大误差。,10.4.2 OPTICS算法,OPTICS并不显示的产生结果簇，而是

6、为聚类分析生成一个增广的簇排序（比如以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类，换句话说，从这个排序中可以得到基于任何参数和MinPts的DBSCAN算法的聚类结果。,定义10.13 设o是数据集D中一个点，为距离，MinPts是一个自然数，MinPts-dist(o)是o到其最邻近的MinPts个邻接点的最大距离，则o的核心距离为：,也就是说，对于点o，它的核心距离为使o成为核点的最小。如果o不是核心对象，则o的核心距离没有定义。,定义10.14 设点p、o为数据集D中的点，为距离，

7、MinPts是一个自然数，点p关于点o的可达距离定义为：,也就是说，点p关于点o的可达距离是指o的核心距离和o与p之间欧几里得距离之间的较大值。如果o不是核心对象，o和p之间的可达距离没有意义。,例如，如图10.41所示，设=6，MinPts=5。显然o为核心点，点o到最邻近的5个点（含自身）的最大距离为=3，所以核心点o的核心距离为3。点p关于o的可达距离=MAX3，dist(o，p)=3（点p属于o的最邻近的MinPts个点之一）。点q关于o的可达距离=MAX3，dist(o，q)=dist(o，q)（点q属于o的邻域内的点，但不属于最邻近的MinPts个点之一）。,OPTICS算法产生了

8、数据集的排序，并为每个点存储了核心距离和相应的可达距离。也就是说，OPTICS的结果是将所有点按照其直接密度可达的最近的核心点的可达距离进行排序，称为簇排序。然后可以基于OPTICS产生的排序信息来提取簇，对于从该排序中提取小于的每个距离值的聚类已经足够。,基于数据集的簇排序可以图形化的描述，有助于理解。例如，图10.42是一个简单的二维数据集的可达性图，它给出了如何对数据结构化和聚类的一般观察。数据点连同它们各自的可达距离按簇顺序绘出。从中看到，核心距离比会生成更好的聚类结果。,【例10.12】有如表10.16所示的数据集，在二维空间中的分布情况如图10.43所示。当设置=2，MinPts=

9、4时，采用OPTICS算法进行聚类的过程如下：,散点图,（1）求各个点的可达距离，其结果如表10.17所示，表中序号指出输出次序，对于未输出的点，表示该点的可达距离没有定义，用OPTICS簇次序图表示，其结果如图10.44所示，其中横坐标对应点的簇次序，纵坐标对应点的可达距离。,OPTICS中的簇次序图,（2）从图中看到，根据可达距离的大小可以分成3个簇，即a，e，b，d，c，f，g，j，k，i，h，n，q，o，m。这和DBSCAN算法设置=1.0，MinPts=4时的聚类结果是相同的。,OPTICS中的簇次序图,（3）通过分析簇次序图还能直接得到这样的结果：当参数=1.5，MinPts=4时

10、的聚类结果只有两个簇，即a，e，b，d，c，f，g，j，k，i，h，也就是说，在OPTICS簇次序图中所有可达距离Y值小于1.5的样本点都不加区分地划入一个簇中这和DBSCAN算法设置=1.5，MinPts=4时的聚类结果是相同的。不在这两个簇中的其他点被认为是离群点。,OPTICS中的簇次序图,OPTICS算法的特点如下：,对于真实的，高维的数据集合而言，绝大多数算法对参数值是非常敏感的，参数的设置通常是依靠经验，难以确定。而OPTICS算法可以帮助找出合适的参数。OPTICS算法通过对象排序识别聚类结构。OPTICS没有显式地产生一个数据类簇，它为自动和交互的聚类分析计算一个簇排序。这个次

11、序代表了数据的基于密度的聚类结构。,10.5 基于网格的聚类算法,基于网格的聚类方法使用一种多分辨率的网格数据结构，将对象空间量化为有限数目的单元，形成网格结构，所有的聚类操作都在网格上进行。其处理速度独立于数据对象的个数，仅依赖于量化空间中每一维的单元个数，因此处理速度快。,10.5.1 STING算法,STING（Statistaical INformation Grid）算法是基于空间数据挖掘的算法，将数据空间区域划分为矩形单元，并且对应于不同级别的分辨率，存在着不同层次的矩形单元，高层的每个单元被分为多个低一层的单元。每个网络单元的统计信息被预先计算和存储，供处理和查询使用。,STIN

12、G结构中的结点,通常每个单元具有以下统计信息方面的参数：,单元内的对象数目count； 单元内所有对象的均值mean； 单元内对象属性的标准差stdev； 单元内对象属性的最小值min； 单元内对象属性的最大值max； 单元内对象属性值遵循的分布类型distr，可以是正态的、均匀的、指数的或NONE（分布未知）。,较高层单元的参数可以很容易地从低层单元的参数计算得到。设count、mean、stdev、min、max和distr分别表示当前单元的参数，与该单元相对应的低层单元的参数分别用counti、meani、stdevi、mini、maxi和distri表示，则count、mean、std

13、ev、min、max和distr可以按如下方式计算：,在完成一个有关空间信息的查询时，先将查询转化为统计信息，然后使用STING算法在层次结构中查找相关的统计参数。STING算法如下：,输入：层次网格结构T，查询要求Q输出：满足查询要求的相关单元的区域方法：其过程描述如下：,（1）从层次结构T的一个层次开始;（2）对于这一层次的每个单元，计算查询Q相关的属性值;（3）从计算的属性值及其约束条件中，将每一个单元标注成相关或者不相关;（4）如果这一层是底层，则转到（6），否则就转（5）;（5）由层次结构转到下一层依照（2）进行计算;（6）若查询结果满足，转到（8），否则转到（7）;（7）恢复数据到

14、相关的单元格进一步处理以得到满意结果，转到（8）;（8）算法结束。,【例10.13】有如图10.46所示的层次网格结构，共3层，第3层中每个单元的面积为10m2，第2层和第3层中每个单元的count=4。采用STING算法查询某个房屋的占地面积的过程如下。,从第一层开始，假设找到该房屋的相关单元有3个，所有相并单元用阴影表示，再在第2层中找到相关单元共10个，继续在第3层中找到相关单元共28个，最后求出面积为2810共280m2。,STING算法具有如下优点： 存储在每个单元的统计信息是不依赖于具体的查询的，所以基于网格的计算独立于查询。 网格层次结构有利于增量更新和并行处理。 执行效率高，扫

15、描一遍数据集计算出每个单元的统计信息，产生聚类的时间复杂度是O(n)，n是数据集中对象的个数。层次结构建成后，查询处理时间是O(k)，k是最低层网格单元的数目，通常kn。,STING算法的缺点如下： 如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量。 在构建一个父单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的边界或者是水平的，或者是竖直的，没有斜的分界线。 尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。,10.5.2 WaveCluster算法,WaveCluster算法利用小波变换聚类，既是基于网格的，也是基于密度的。其

16、主要思想是：首先量化特征空间，形成一个多维网格结构，然后用小波变换来变换原特征空间，在小波变换中，用一个合适的内核函数进行旋转，产生一个变形后的空间，使数据中的簇易于区分。在变换后的空间中发现密集区域。可以在不同分辨率的下产生基于用户需求的聚类。,小波变换是一种有效的数学分析方法，广泛应用于边界的处理与滤波、时频分析、信噪分离与提取弱信号以及多尺度边缘侦测等。就聚类而言，小波变换具有提供无监督聚类、有效地消除离群点、有利于在不同精度（分辨率）上发现簇和高效率的优点。,样例及其多种分辨率结果,WaveCluster算法如下：,输入：多维数据集的特征向量输出：聚类对象方法：其过程描述如下：,对特征

17、空间进行量化，把每个维度分成若干段，这样，整个空间分成单元，然后把对象分配到相应的单元；对量化后的特征空间进行离散小波变换；在变化后的特征空间的子波段中找出相连的部分，就是簇；为每个簇所包含的单元分配相应的标记；建立查找表，用于把变换后特征空间中的单元映射到原特征空间中的单元；把每个单元的标记分配给该单元内的所有对象，将对象映射成簇。,WaveCluster算法的优点如下： 它提供无监督聚类；采用了加强点簇区域，而抵制簇边界之外的较弱信息的帽形（hat-shape）过滤器。这样在原特征空间中的密集区域成为附近点的吸引点（attractor）和较远点的抵制点（inhibitor）。这意味着数据的

18、聚类自动地突显出来，并清洗”周围的区域。这样小波变换的另一个优点是能够自动地排除离群点。 小波变换的多分辨率特征有助于发现不同精度的聚类。 基于小波的聚类速度很快。 对输入顺序不敏感，不需要事先知道簇的数目，并且能够快速处理大型数据集，能够发现任意复杂形状的聚类。,WaveCluster算法的不足是：量化特征空间形成多维网格结构时，需要消耗较大的存储空间，仅适合于特征空间可以明显量化的数据集进行聚类。所以WaveCluster算法主要用于空间数据聚类。,10.5.3 CLIQUE算法,CLIQUE（Clustering In Quest）算法是基于网格和密度的空间聚类算法。该算法的基本思想是：

19、给定一个多维数据点的数据空间，数据点在数据空间中通常是分布不平衡的。该算法区分空间中稀疏的和“拥挤的”区域，找出数据集合的全局分布模式。,在CLIQUE算法中，由若干相邻的密集单元合并构成密集。所谓密集单元，是指包含的数据点数超过了某个输入阈值的单元。最后把相连的密集区域的最大集合成为簇。,CLIQUE通过以下两个步骤进行多维聚类：第一步，将n维空间划分为互不相交的矩形单元，识别其中的密集单元。在识别密集单元时该算法采用如下Apriori性质：如果一个k维单元是密集的，那么它在k-1维空间是的投影也是密集的。因此，可以从k-1维空间中发现的密集单元来推断k维空间中潜在的或候选的密集单元。代表密

20、集单元的子空间取交集形成了一个候选搜索空间，这样的候选搜索空间比初始空间要小很多，最后依次检查密集单元确定最终的聚类。第二步，CLIQUE为每个簇生成最小的描述。对每个簇，它确定覆盖相连的密集单元的最大区域，然后再为每一个簇确定最小的覆盖。,示例,CLIQUE算法的优点是：对高维数据有良好的伸缩性，对数据输入顺序不敏感，具有处理噪声的能力。 CLIQUE算法的局限性：若允许簇重叠会大大增加簇的个数，使解释变得困难，由于基于Apriori性质，和Apriori算法一样具有指数复杂度。,10.6 基于模型的聚类算法,基于模型的方法假设数据集是由一系列的概率分布所决定的，给每一个聚簇假定了一个模型，

21、然后在数据集中寻找能够很好满足这个模型的簇。这个模型可以是数据点在空间中的密度分布函数，它由一系列的概率分布决定，也可以是通过基于标准的统计来自动求出聚类的数目。,10.6.1 EM算法,EM（Expectation-maximization，期望最大化）算法。属k-均值算法的一种扩展。与k-均值算法将每个对象指派到一个簇中不同，在EM算法中，每个对象按照代表对象隶属概率的权重指派到每个簇中，新的均值基于加权的度量来计算。在EM算法中，簇间没有严格的边界。,1. 期望最大化方法,每个簇都可以用参数概率分布即高斯分布进行数学描述，元素x属于第i个簇Ci的概率表示为：,记为N(i，i2),其中，k

22、、k分别为均值和协方差。Ni为簇Ci的元素个数。,高斯分布概率示意图,一般地，k个概率分布的混合高斯分布函数如下：,其中，i0，。,采用期望最大化的EM过程如下：,（1）用随机函数初始化k个高斯分布的参数，同时保证。,（2）E步：依次取观察数据x，比较x在k个高斯函数中概率的大小，把x归类到这k个高斯中概率最大的一个即第i个类中。（3）M步：用最大似然估计，使观察数据是x的概率最大，因为已经在第（2）步中分好类了，所以，只需重新执行以下各式：,（4）返回第（2）步用第（3）步新得到的参数来对观察数据x重新分类。直到概率（最大似然函数）达到最大。上述E步称为期望步，M步称为最大化步，EM算法就是

23、使期望最大化的算法。,2. EM算法,输入：数据集D=o1，o2，on，簇数目k输出：k个簇的参数方法：其过程描述如下：,对混合模型的参数作初始估计：从D中随机选取k个不同的数据对象作为k个簇C1、C2、Ck的中心1、2、k，估计k个簇的方差1、2、k;do E步：计算p(oiCj)，根据 将对象oi指派到簇Cj。其中： p(Cj)为先验概率。在无先验知识时，通常取所有p(Cj)相同，在这种情况下，只需求 。 M步：利用E步计算的概率重新估计j和j; until (参数如或不再发生变化或变化小于指定的阈值);,【例10.14】随机产生20个1100的整数（数据对象），采用上述EM算法将其分为3

24、个簇。假设随机生成的20个整数为62，98，91，6，30，72，22，4，22，80，99，9，87，44，4，76，38，58，21，95，编号分别为019。设定迭代结束的条件是两次迭代之间的均值小于等于0.1。,（1）先取前3个整数放入3个簇C0、C1和C2中。求出所有簇的均值和方差如下：C0的均值=62，方差=2.0（此时每个簇中只有一个对象，方差应为0，为了便于下一次迭代，将所有簇的方差随机地取为2）；C1的均值=98，方差=2.0；C2的均值=91，方差=2.0。,（2）第1次迭代，迭代完毕的分配结果如下：C0（对象个数=15）：62，62，6，30，72，22，4，22，9，44

25、，4，76，38，58，21C1（对象个数=4）：98，98，99，95C2（对象个数=4）；91，91，80，87重新计算均值和方差如下：C0的均值=35.3，方差=24.662C1的均值=97.5，方差=1.500C2的均值=87.3，方差=4.493,（3）第5次迭代，其过程与第1次迭代相似，迭代完毕的分配结果如下：C0（对象个数=12）：62，6，30，22，4，22，9，44，4，38，58，21C1（对象个数=3）：98，99，95C2（对象个数=5）：91，72，80，87，76重新计算均值和方差如下：C0的均值=26.7，方差=19.392C1的均值=97.3，方差=1.700

26、C2的均值=81.2，方差=6.969此时迭代条件满足，算法结束，共进行5次迭代。显然聚类结果是合理的。,3. SQL Server中EM算法聚类示例,对于表10.1的学生成绩数据集，本示例介绍采用SQL Server提供的EM算法进行聚类分析的过程。,设置算法参数,EM算法的分类关系图,EM算法的预测结果,10.6.2 COBWEB算法,COBWEB算法是一个通用且简单的增量式的概念聚类算法。概念聚类是一种机器学习聚类方法，给定一组未标记的对象，产生对象的分类模式。与传统的聚类不同，概念聚类除了确定相似的对象分组外，还找出每组对象的特征描述，其中每组对象代表一个概念或类。因此，概念聚类通常分

27、为两步，首先进行聚类，然后给出特征描述。这里，聚类质量不再只是个体对象的函数，而且加入了如导出的概念描述的一般性和简单性等因素。,如图10.53所示是一棵关于花类植物的分类树，共有3个二元属性，即male（是否有雄蕊）、wings（是否有翼瓣）和nocturnal（是否夜间开花），每个对象用二元属性值列表来表示，每个概念（结点）表示一个对象集，每个结点旁的虚线方框表示各属性的计数。,一棵分类树,例如，计数为1，3，3的结点表示该概念中有1个对象是雄蕊，3个对象有翼瓣，3个对象是夜间开花的。概念描述就是对应结点的分类条件概率，例如，若一个对象属于结点C1，它有雄蕊的可能性是1/4即0.25，它有

28、翼瓣和夜间开花的可能性都是3/4=0.75，因此，结点C1的概念描述简写成0.25,0.75,0.75，对应C1的条件特征的可能性，也就是：p(x|C1)=0.25,0.75,0.75。,一棵分类树,为了利用分类树来对一个对象进行分类，需要利用一个匹配函数来寻找“最佳的路径”，COBWEB算法用了一种启发式的评估衡量标准。类内的相似性用p(Ai=vij|Ck)来衡量，它表示Ck类内Ai属性为vij的条件概率，该条件概率越大，同一类中具有相同属性值对（Ai，vij）的对象就越多。因此，该（Ai，vij）对Ck类的内部对象的预测能力就越强。,类间的相异性用p(Ck|Ai=vij)来衡量，它表示（A

29、i，vij）对象属于Ck类的条件概率，该概率越大，在其他类中同样具有该属性值对（Ai，vij）的对象就越少。因此，该（Ai，vij）对Ck类的预测能力就越强。定义划分效用（Partition Utility，PU）如下：,PU表示了给定的划分能够正确猜测出属性值的期望数目。,所以，,COBWEB采用以下启发式估算度量即分类效用（Category Utility，CU）来指导树的建立过程。,其中，n是树的某个层次上形成一个划分C1，C2，Cn的结点、概念或“种类”的数目。换句话说，分类效用是指PU相对于未知划分情况下正确猜测的期望数目（对应上式中分子的第二项）的增量。分类效用表达了簇内的相似性和

30、簇间的相异性。,COBWEB算法的优点是：可以自动修正划分中类的数目；不需要用户提供输入参数。其缺点是：COBWEB基于这样一个假设：在每个属性上的概率分布是彼此独立的。但这个假设并不总是成立。且对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化，不适用于聚类大型数据库的数据。,【例10.15】有如表10.19所示的数据集，不考虑Play属性部分，采用COBWEB算法建立分类树的过程如下。,（1）插入对象a，将对象a放在一个新类（结点）中，如图10.55（a）所示。（2）插入对象b，将对象b放在一个新类中，如图10.55（b）所示。,（3）插入对象c，有3种情况，如图10.

31、56所示，其中第3种情况CU值最高，则插入对象c作为根结点的孩子结点。,（4）插入对象d、e，其结果是建立d、e的结点并均作为根结点的孩子结点。（5）插入对象f，由于对象f与对象e很相似（前3个属性值相同），求CU值后将对象f和对象e放在相同的类下，如图10.57所示。,（6）依次插入所有余下的对象，得到最终的分类树如图10.58所示。,将分类树的聚类结果与表中Play属性值进行对比，发现很多分类错误，如将对象b、k划在同一类中，而它们的Play属性值正好相反。这是因为COBWEB算法基于Outlook、Temp、Humidity和Windy各属性相互独立来进行聚类的，而表10.19中列出的经

32、验知识中各属性之间是有关联关系的，如天气的好坏肯定影响温度和湿度。这是为什么本例的聚类结果出现错误的原因。,10.7 离群点分析,10.7.1 离群点概述,1. 什么是离群点,所谓离群点，是指那些与数据的一般行为或模型不一致的数据对象，它们与数据的其他部分非常不同或不一致。离群点挖掘可以描述为，给定n个数据点或对象的集合，及预期的离群点的数目k，发现与剩余的数据相比显著相异的、异常的或不一致的头k个对象。,2. 离群点产生的原因,（1）计算的误差或者操作的错误所致，例如，某人的年龄-999岁，这就是明显由误操作所导致的离群点。（2）数据本身的可变性或弹性所致，例如，一个公司中CEO的工资肯定是

33、明显高于其他普通员工的工资，于是CEO变成为了由于数据本身可变性所导致的离群点。,3. 为什么要对离群点进行检测,一方面，离群点作为噪声会影响数据挖掘的有效性和可靠性。另一方面，这些离群点也许正是用户感兴趣的，例如在欺诈检测领域，那些与正常数据行为不一致的离群点，往往预示着欺诈行为，因此成为执法者所关注的。,4. 离群点检测遇到的困难,（1）在时序样本中发现离群点一般比较困难，因为这些离群点可能会隐藏在趋势、季节性或者其他变化中。（2）对于属性为非数值型的样本，如何表现出异常，一般难以准确的量化。（3）针对高维数据，离群点的异常特征可能是多维度的组合，而不是单一维度就能体现的。,10.7.2

34、常见的离群点检测方法,1. 基于统计分布的离群点检测方法,基于统计分布的离群点检测方法是对给定的数据集假设了一个分布或概率模型（例如正态分布），然后根据模型采用不和谐检验识别离群点。应用该检验需要数据集参数知识，分布参数知识和期望的离群点数目。例如，设属性x取自标准正态分布N(0，1)，如果属性值x满足p(|x|c)=，其中c是给定的常量，则x以概率1-为离群点。,2. 基于距离的离群点检测方法,为了解决统计学方法带来的限制，引入了基于距离的离群点的概念。如果数据集合D中对象至少有pct部分与对象o的距离大于dmin，则称对象o是以pct和dmin为参数的基于距离的离群点，记为DB(pct，d

35、min)。其中，dmin是邻域半径，pct是一个异常的dmin邻域外的最少对象比例。换句话说，不依赖于统计检验，可以将基于距离的离群点看作是没有“足够多”紧邻的对象，其中紧邻基于到给定对象的距离定义。基于距离的离群点检测避免了与观测分布拟合到某个标准分布和选择不和谐检验相关联的过多计算。挖掘基于距离的离群点的高效算法有基于索引的算法、嵌套-循环算法和基于单元的算法等。,3. 基于密度的离群点检测方法,基于密度的离群点概念由Breunig等人提出，引入局部离群点这一新的概念，一个对象如果是局部离群点，那么相对于它的局部邻域是远离的。通过比较每个点与附近邻域点的密度来考察它们的离群程度，用局部离群

36、因子（LOF）表示。在基于密度的离群点检测中，借用了DBSCAN算法的一些概念。,对象p的k距离k-dist(p)是指，对于正整数k，是指对象p到它的k最邻近点的最大距离。对象p的k距离邻域Nk-dist(p)(p)是指与对象p之间距离小于等于k-dist(p)的对象集合，该邻域其实是以p为中心，k-dist(p)为半径的区域内所有对象的集合。,可以想象，对于离群点p，其Nk-dist(p)(p)范围往往比较大，对于非离群点p，其Nk-dist(p)(p)范围往往比较小。对于同一个类簇中的对象来说，它们涵盖的区域面积大致相当。对象p关于对象o（其中o在p的k最近邻中）的可达距离定义为：reac

37、hdistk(p，o)=MAXk-dist(o)，dist(p，o)即k-dist(o)和dist(p，o)值较大的那个。,对象p的局部可达密度lrdk(p)是基于p的k最近邻点的平均可达密度的倒数，即：,对象p的局部离群点因子（LOF）定义如下：,可以通过LOF(p)来判断对象p是否是局部离群点。,4. 基于偏差的离群点检测方法,基于偏差的离群点检测的技术主要有两种：（1）顺序异常技术：模仿人类从一系列推测类似的对象中识别异常对象的方式。（2）OLAP数据立方体方法：在大规模的多维数据中采用数据立方体来确定异常区域。如果一个立方体的单元值显著的不同于根据统计模型得到的期望值，则该单元值被认为是一个异常，并用可视化技术表示。,本章完,