基于邻域和密度的异常点检测算法

为了减少基于密度的异常点检测算法邻域查询操作的次数,同时避免ODBSN(Outlier Detection Based onSquare Neighborhood)中有意义异常点的丢失和稀疏聚类中的对象靠近稠密聚类时导致错误的异常点判断,提出了一种基于邻域和密度的异常点检测算法NDOD(Neighborhood and Density based Outlier Detection)。NDOD吸收基于网格方法的思想,以广度优先扩张方形邻域,成倍地减少了邻域查询的次数,从而快速排除聚类点并克服基于网格方法中的"维灾"。新引入的基于邻域的局部异常因子代表候选异常点的异常程度,用于对候选异常点的精选,可避免ODBSN的缺陷,发现更多有意义的异常点。大规模和任意形状的二维空间数据的测试结果表明,该算法是可行有效的。

屏蔽输入参数敏感的异常点检测新方法

大多数基于密度的异常点检测算法需要设置两个输入参数,并对输入参数很敏感,用户设置不正确会导致算法不能发现所有有意义的异常点,甚至是发现错误的异常点,这使得评价一个数据挖掘算法的"3-E"标准中"易于使用"这一点不能得到满足。为此,首先根据对象的邻域、反邻域和局部密度构造基于邻域的局部密度因子NLDF,NLDF可指示异常点的异常程度,然后提出一种屏蔽输入参数敏感的异常点检测算法ODINP。ODINP的一个非常显著的优点就是只需要一个参数k并且对k不敏感。该算法在保持已有基于密度的异常点检测算法高效性的同时,具有很高的异常点检测精度。大规模、任意形状和高维数据集的测试结果表明该算法是有效的、可行的。

一种快速移动对象轨道聚类算法

针对已有轨道聚类(TRACLUS)算法的线段聚类模块需要对划分后的每条线段进行邻域查询的问题,将取样技术引入轨道聚类,提出一种快速移动对象轨道聚类(FTCS)算法。FTCS算法根据基于极大连通子图的合并原理,对核心线段的Eps邻域以及与该Eps邻域相重叠的所有轨道聚类进行合并,避免了TRACLUS算法中核心线段Eps邻域内线段的不必要邻域查询操作。在真实和合成轨道数据集上的大量实验结果表明,FTCS算法显著降低了邻域查询操作次数,在保持TRACLUS算法轨道聚类质量的同时,成倍提高了轨道聚类的时间效率。