基于聚类的离群点检测讲述.docxVIP

DBSCAN密度算法： 1、DBSCAN算法介绍 DBSCAN算法是将密度足够大的数据组成类。DBSCAN需要由用户主观来选择参数从而影响了最终的聚类结果，对于数据量为凡的样本集合，DBSCAN的计算复杂度为D(n2)。一般采用空间索引的方法降低时间复杂度，复杂度为D(nlogn)。 2、DBSCAN算法用到的定义如下 定义l(数据点的Eps邻域)以数据样本中任意一点为圆心，Eps为半径的球形区域内包含的点的集合，叫做该数据点的Eps邻域。 定义2(数据点的密度)数据样本中任意一点的Eps邻域内包含的点数，叫做该数据点的密度。 定义3(核心数据点)核心数据点是指在Eps半径范围之内包含等于Minpts或大于Minpts个点的数据样本中任意一点。 定义4(边界数据点)边界数据点是指在某个核心数据点的邻域内，但自身不是核心数据点的数据样本中任意一点。 定义5(直接密度可达)已知Eps，Minpts，对于点x和点y，如果y是核心点，而且x属于y的Eps邻域，则点x从点y直接密度可达。 定义6(密度可达)如果对于给定的Eps，Minpts存在点链x1，x2，x3? xn，其中x1=x，xn=Q，而且xi从xi+l直接密度可达，那么点x从点Q密度可达。 定义7(密度相连)如果在给定Eps，Minpts的情况下，存在点p，使得点x和点y都从p密度可达，则点x和y是密度相连的。 定义8事先给定Eps和Minpts，基于密度聚类中的一个聚类就是可以密度连接所能包含的最多数据点的集合。不属于任何聚类的数据点的集合称为噪声。 假定输入参数为Eps和Minpts，DBSCAN的算法 3、描述如下 (1)输入聚类数据，然后任意选取一个数据点茗，检查数据点菇的Eps邻域。 (2)如果戈是核心点而且没有被划分到某一个类，则找出所有从戈密度可达的点，最终形成一个包含菇的类。 (3)如果z不是核心点，则被当做噪声处理。 (4)转到第一步，重复执行算法；如果数据集合中所有的点都被处理，则算法结束。 基于多重聚类的局部离群点检测算法 1、局部离群点检测算法 LDOF 该算法定义了一个基于距离的局部离群因子ldof，利用该离群因子可以评估某个数据点p与其自身最近邻邻域集合的偏离程度。ldof(p)的值越大，表示数据点p相对于其邻域的偏离程度越大，p的离群度就越大。 设Np为数据对象p的k最近邻点的集合（不包括对象p）。 定义3.1 点p的KNN距离所有Np内的数据到p的平均距离，记作p 的平均距离，记作dp ,计算公式如下： dp=1kq∈Npdisp,q 3.1 其中，disp,q表示点p与点q之间的距离，而且disp,q≥0。 定义3.2 点p的KNN内部距离Np内所有数据对象间的平均距离，记作Dp ，计算公式如下： Dp=1k(k-1)q,r∈N,q≠rdist(q,r) (3.2) 定义3.3 点p 的局部距离离群因子 点p 的k 最近邻距离与k 最近邻内部距离的之比，记作ldof ( p)，计算公式如下： ldofp=dpDp (3.3) LDOF采用了top-n离群检测方式，首先计算所有数据的ldop值，然后根据ldof值对所有数据进行排序，将ldof值最大的n个数据点作为检测结果。这种top-n离群检测方式使得LDOF算 不需要再设置局部离群度阈值。 LDOP不足 LDOF不但可以有效地检测数据集中的全局离群点，还可以很好地检测数据集中包含的局部离群点。但是LDOF仍然存在明显的不足： (1)LDOF算法中，由于需要计算所有数据点的ldof值，导致其时间复杂度很高。然而，数据集中的绝大多数数据是正常点，离群点只占很小一部分。这意味着对LDOF算法中存在大量的无效（或无价值）ldof值计算。这种无效的计算直接导致了算法较高的时间复杂度。 (2)LDOF对最近邻参数k比较敏感，其离群检测精度受k值影响大。 2、基于DBSCAN聚类剪枝的局部离群点检测算法 PLDOF 稠密区域内的数据聚集为簇，并不聚集稀疏区域的数据。总之，将DBSCAN算法作为剪枝手段，既可以适应复杂多变的数据集，又可以满足降低局部离群因子计算量的要求。 PLDOF算法分剪枝初选阶段和离群点精选阶段进行，其主要思想和执行步骤如下： ①首先采用DBSCAN算法对数据集进行聚类以找到簇数据，然后将不可能是离群点的簇数据剪枝，保留剩余数据作为候选离群点集。 ②对于候选离群点集中的所有数据对象，计算它们的局部离群因子ldof。 ③若某数据的局部离群度属于top-n，则将该数据对象视为离群点。 PLDOP不足 PLDOF算法利用DBSCAN算法作为剪枝手段，虽然既可以适应复杂多变的数据集，又可以改进LDOF的缺点，但是其却带来了错剪离群点的问题。 3、基于多重聚类的局部离群点检测算法 PM