一种基于密度的局部离群点检测算法DLOF

离群点可分为全局离群点和局部离群点.在很多情况下,局部离群点的挖掘比全局离群点的挖掘更有意义.提出了一种基于密度的局部离群点检测算法DLOF.该方法通过引入信息熵用于确定各对象的离群属性,在计算各对象之间的距离时采用加权距离,并给离群属性较大的权重,从而提高离群点检测的准确度.另外,该算法在计算离群因子时,采用了两步优化技术,并对采用这两步优化技术后算法的时间复杂度进行了详细分析.理论分析和实验结果表明了该方法是有效可行的.     

基于全息熵的空间离群点挖掘算法研究

基于距离和基于密度的离群点检测算法受到维度和数据量伸缩性的挑战, 而空间数据的自相关性和异质性决定了以属性相互独立和分类属性的基于信息理论的离群点检测算法也难以适应空间离群点检测, 因此提出了基于全息熵的混合属性空间离群点检测算法。算法利用区域标志属性进行区域划分, 在区域内利用空间关系确定空间邻域, 并用R*-树进行检索。在此基础上提出了基于全息熵的空间离群度的度量方法和空间离群点挖掘算法, 有效解决了混合属性的离群度的度量和离群点的挖掘问题。由于实现区域划分有利于并行计算, 从而可适应大数据量的计算。理论和实验证明, 所提算法在计算效率和实验结果的可解释性方面均具有优势。     

基于空间约束的离群点挖掘

由于现有的空间离群点检测算法没有很好地解决空间数据的自相关性和异质性约束问题,提出用计算邻域距离的方法解决空间自相关性约束问题,用计算空间局部离群系数的方法解决空间异质性约束问题。用离群系数表示对象的离群程度,并将离群系数按降序排列,取离群系数最大的前m个对象为离群点,据此提出基于空间约束的离群点挖掘算法。实验结果表明,所提算法比已有算法具有更高的检测精度、更低的用户依赖性和更高的效率。     

基于相对密度的军事高维数据噪声点检测方法

军事训练领域的特殊性造成其相关数据存在大量的噪声点,同时也为噪声检测算法提出了相应的要求。分析现有数据噪声点检测算法,提出将数据属性分为空间属性、环境属性、特征属性,利用空间属性确定数据对象的分类,利用环境属性确定具有不同特征的数据对象邻域,利用特征属性计算离群度。改进了基于相对密度的离群度计算方法,提出LRDF算法,实验结果表明,该方法有效地提高了噪声点检测的精度和效率,增强算法可用性。     

基于Voronoi和空间自相关的离群点检测

为了提高空间数据挖掘的效率和准确度,在分析传统的离群点检测算法优、缺点的基础上,提出一种空间离群点检测算法。用Voronoi来确定空间对象间的邻近关系,在空间邻域内利用空间自相关性来计算局部Moran指数,并将其作为离群因子进而判断离群点。实验结果表明,该算法能够高效、准确地检测出空间离群点,具有对用户依赖性少和可伸缩性强等优点。     

基于Voronoi和空间自相关的离群点检测

为了提高空间数据挖掘的效率和准确度,在分析传统的离群点检测算法优、缺点的基础上,提出一种空间离群点检测算法。用Voronoi来确定空间对象间的邻近关系,在空间邻域内利用空间自相关性来计算局部Moran指数,并将其作为离群因子进而判断离群点。实验结果表明,该算法能够高效、准确地检测出空间离群点,具有对用户依赖性少和可伸缩性强等优点。     

NLOF:一种新的基于密度的局部离群点检测算法

基于密度的局部离群点检测算法(LOF)的时间复杂度较高且不适用于大规模数据集和高维数据集的离群点检测。通过对LOF算法的分析,提出了一种新的局部离群点检测算法NLOF,该算法的主要思想如下:在数据对象邻域查询过程中,尽可能地利用已知信息优化邻近对象的邻域查询操作,有关邻域的计算查找都采用这种思想。首先通过聚类算法DBSCAN对数据集进行预处理,得到初步的异常数据集。然后利用LOF算法中计算局部异常因子的方法计算初步异常数据集中对象的局部异常程度。在计算数据对象的局部异常因子的过程中,引入去一划分信息熵增量,用去一划分信息熵差确定属性的权重,対属性的权值做具体的量化,在计算各对象之间的距离时采用加权距离。 在真实数据集上 对NLOF算法进行了充分的验证。结果显示,该算法能够提高离群点检测的精度,降低时间复杂度,实现有效的局部离群点的检测。     

基于邻域密度的异构数据局部离群点挖掘算法

由于数据集规模、维数,以及复杂程度的不断提高,导致对其离群点的挖掘难度越来越大,提出了基于邻域密度的局部离群点挖掘算法.首先依据节点计算性能对高维数据进行区域分割,通过各个维度的数据分布来评价区域分割的效果.然后采取核密度来描述局部密度,根据高斯分布得到数据出现次数,进一步计算出数据邻域密度.再由邻域及密度关系计算得到各数据离群度,从而判断异构数据中的离群点.最后针对可能存在的离群误判情况,采取离群分数计算,为增强此过程的检测性能,利用权重进行剪枝处理.人工与UCI数据集上的仿真结果表明,当数据量和数据维数改变时,算法对离群点挖掘的准确度几乎不受影响,挖掘时间和覆盖率指标也显著优于其它方法;同时对于不同类型和复杂度的异构数据,算法仍然保持良好的挖掘准确度和效率.     

基于Voronoi和信息熵的空间离群样点检测

为了提高离群点挖掘的效率和准确度,在分析了传统离群点挖掘算法优、缺点的基础上,提出一种离群点检测算法.该算法利用Voronoi确定样点之间的邻近关系,通过参照邻域范围内其它样点的非空间属性值的信息熵作为离群因子,并根据离群因子标识出样点集中的离群点.以北京市大兴区土壤养分为例,实验结果表明,该检测算法能够高效,准确地检测出土壤样点中的离群点.     

基于重叠模块度的社区离群点检测

社区离群点是结合数据的社区特性和自身属性挖掘得到的一种特殊离群点。针对现有社区离群点检测算法忽略社区间的重叠现象而导致社区划分不准确的问题,提出一种将对象的特征属性引入到相似度和重叠模块度的计算中的社区离群点检测方法。首先根据节点间的相似度对节点进行聚类,然后根据重叠模块度的变化进行迭代聚类,多次聚类后选取重叠模块度最大的作为划分结果,最终根据特征属性的偏离程度来确定社区离群点,从而解决重叠社区中社区离群点的检测问题。实验结果表明,提出的算法不仅能准确地发现重叠社区而且能有效地检测社区离群点。     

On Detecting Spatial Outliers

The ever-increasing volume of spatial data has greatly challenged our ability to extract useful but implicit knowledge from them. As an important branch of spatial data mining, spatial outlier detection aims to discover the objects whose non-spatial attribute values are significantly different from the values of their spatial neighbors. These objects, called spatial outliers, may reveal important phenomena in a number of applications including traffic control, satellite image analysis, weather forecast, and medical diagnosis. Most of the existing spatial outlier detection algorithms mainly focus on identifying single attribute outliers and could potentially misclassify normal objects as outliers when their neighborhoods contain real spatial outliers with very large or small attribute values. In addition, many spatial applications contain multiple non-spatial attributes which should be processed altogether to identify outliers. To address these two issues, we formulate the spatial outlier detection problem in a general way, design two robust detection algorithms, one for single attribute and the other for multiple attributes, and analyze their computational complexities. Experiments were conducted on a real-world data set, West Nile virus data, to validate the effectiveness of the proposed algorithms.

空间离群点的检测算法

空间离群点是指与其邻居具有明显区别的属性值的空间对象。已有的空间离散点检测算法一个主要的缺陷就是这些方法导致一些真正的离群点被忽略而把一些非离群点当成了空间离群点。提出了一种迭代算法,该算法通过多次迭代检测离群点,取得较好效果。实验表明该算法具有较好的实用性。     

基于熵度量的空间邻域离群点查找

离群点的查找算法主要有两类：第一类是面向统计数据,把各种数据都看成是多维空间,没有区分空间维与非空间维,这类算法可能产生错误的判断或找到的是无意义的离群点;第二类算法面向空间数据,区分空间维与非空间维,但该类算法查找效率太低或不能查找邻域离群点。引入熵权的概念,提出了一种新的基于熵权的空间邻域离群点度量算法。算法面向空间数据,区分空间维与非空间维,利用空间索引划分空间邻域,用非空间属性计算空间偏离因子,由此度量空间邻域的离群点。理论分析表明,该算法是合理的。实验结果表明,算法具有对用户依赖性小、检测精度和计算效率高的优点。     

局部空间离群点算法的改进及其实现

LOF算法是一个著名的局部离群点查找方法,该方法赋予了表征每一个空间点偏离程度的数值。但LOF算法存在效率低和性能差的问题,为此对该算法进行了以下两个方面的改进：第一,提出了降低该算法时间复杂度的两步改进方法,并对这两步改进方法的时间复杂度也进行详细分析,第二,使得该算法在查找局部离群点时,不仅考虑了空间属性,也考虑了非空间属性。另外还通过实验测试了LOF算法及其改进方法的时间效率,以及在模拟数据和真实数据情况下的查找离群点的效果。实验结果表明,改进方法具有更好的时间效率和性能。     

空间离群点的模型与跳跃取样查找算法

目前无论是查找一般的离群点，还是空间离群点，都强调非空间属性的偏离，但在图像处理、基于位置的服务等许多应用领域，空间与非空间属性要综合考虑。为此，首先提出了一个综合考虑两者的空间离群点定义，然后提出了一种新的基于密度的空间离群点查找方法——基于密度的跳跃取样空间离群点查找算法DBSODLS。由于已有的基于密度的离群点查找方法对每一点都要求进行邻域查询计算，故查找效率低，而该算法由于可充分利用已知的邻居信息，即不必计算所有点的邻域，从而能快速找到空间离群点。分析与试验结果表明，该算法时间性能明显优于目前已有的基于密度的算法。     

无线传感器网络中异常读数检测算法研究*

针对无线传感器网络的离群点检测算法由于没有充分考虑数据的时空关联性和网络的分布特性,导致检测精度低、通信量大和计算复杂度高等局限,提出了基于时空关联的分布计算与过滤的在线离群点检测算法。该算法在各传感器节点上利用传感器读数的时间关联性生成候选离群点,并利用空间关联性对候选离群点进行过滤得到局部离群点,最终将所有传感器节点上的局部离群点集中到sink节点上获得全局离群点。利用时空关联性提高了检测精度,利用分布计算与过滤减少了通信量和计算量,理论分析和实验结果均表明该算法优于现有算法。     

空间离群点的检测算法

空间离群点是指与其邻居具有明显区别的属性值的空间对象。已有的空间离散点检测算法一个主要的缺陷就是这些方法导致一些真正的离群点被忽略而把一些非离群点当成了空间离群点。本文提出了一种迭代算法,该算法通过多次迭代检测离群点,取得较好效果。实验表明该算法具有较好的实用性。