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

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

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

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

基于网格查询的局部离群点检测算法

针对基于密度的局部离群因子算法（LOF），需要计算距离矩阵来进行[k]近邻查寻，算法时间复杂度高，不适合大规模数据集检测的问题，提出基于网格查询的局部离群点检测算法。算法利用距离目标网格中的数据点最近的[k]个其他数据点，一定在该目标网格或在该目标网格的最近邻接网格中这一特性，来改进LOF算法的邻域查询操作，以此减少LOF算法在邻域查询时的计算量。实验结果证明，提出的LOGD算法在与原LOF算法具有基本相同的检测准确率的情况下，能够有效地降低离群点检测的时间。     

基于聚类分析局部离群点挖掘改进算法的研究与实现

对于犯罪检测、网络入侵检测等应用,离群点检测是数据挖掘的一种重要算法.局部离群因子是对数据对象离群点的程度定义,计算所有数据对象局部离群因子需要大量计算. 一种基于聚类分析局部离群点挖掘改进算法得以实现,此改进算法以聚类分析为预处理,只对聚类之外的数据对象计算局部离群因子,避免了大量计算,并改进了对数据对象k距离邻域的求解.通过仿真数据和轨道交通AFC(automatic fare collecting system)客流数据的实验,证实此改进算法不仅能更高效地挖掘出值得关注的离群点,而且还能更好地达到解析目的.     

基于局部离群点的低压台区线损异常检测

为提高低压台区线损异常检测方法的数据采集成功率与检测准确率,提出基于局部离群点的低压台区线损异常检测方法研究。分析低压台区基本结构,获取线损数据集,依据基于密度的局部离群算法完成离群数据点的定义。对数据集进行预处理,通过计算信息熵来判断其是否具有离群属性,通过计算其加权距离,计算各对象间的局部可达密度,继而通过计算各对象的离群因子,通过与离群因子阈值比较完成离群属性的判断,完成低压台区线损异常的检测。对比实验结果显示：该方法可大幅提高低压台区的线损异常检测的数据采集成功率与检测准确率,经过适当治理后其异常情况骤减,改善了该台区的线损情况,提高供电质量和供电效率。     

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

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

基于局部信息熵的加权子空间离群点检测算法

离群点检测作为数据挖掘的一个重要研究方向,可以从大量数据中发现少量与多数数据有明显区别的数据对象.“维度灾殃”现象的存在使得很多已有的离群点检测算法对高维数据不再有效.针对这一问题,提出基于局部信息熵的加权子空间离群点检测算法SPOD.通过对数据对象在各维进行邻域信息熵分析,生成数据对象相应的离群子空间和属性权向量,对离群子空间中的属性赋以较高的权值,进一步提出子空间加权距离等概念.采用基于密度离群点检测的思想,分析计算数据对象的子空间离群影响因子,判断是否为离群点.算法能够有效地适应于高维数据离群点检测,理论分析和实验结果表明算法是有效可行的.     

基于前向查找和均值漂移的点模型鲁棒降噪算法

针对点模型提出了基于前向查找和均值漂移两种鲁棒统计方法的滤波算法。前向查找算法根据残差图自动检测离群点,并将输入的点云数据划分为多个不带离群点的最优局部降噪邻域。对局部邻域进行加权协方差分析,估计出该邻域的最小二乘拟合平面。在局部邻域内估计采样点的核密度函数并通过均值漂移算法计算它的局部最大值点,核密度函数的局部最大值点确定了点云数据的聚类中心并能准确逼近采样点曲面,将每一个采样点漂移到密度函数的局部最大值点,使点云曲面收敛为一个稳定的三维数字模型。实验结果表明,本文的算法是鲁棒的,能在有效剔除点模型表面噪声的同时较好地保持模型表面的尖锐特征。     

局部离群点挖掘算法研究

离群点可分为全局离群点和局部离群点.在很多情况下,局部离群点的挖掘比全局离群点的挖掘更有意义.现有的基于局部离群度的离群点挖掘算法存在检测精度依赖于用户给定的参数、计算复杂度高等局限.文中提出将对象属性分为固有属性和环境属性,用环境属性确定对象邻域、固有属性计算离群度的方法克服上述局限;并以空间数据为例,将空间属性与非空间属性分开,用空间属性确定空间邻域,用非空间属性计算空间离群度,设计了空间离群点挖掘算法.实验结果表明,所提算法具有对用户依赖性少、检测精度高、可伸缩性强和运算效率高的优点.     

相关子空间中的局部离群数据挖掘算法研究

针对高维数据集,采用局部稀疏差异和局部密度差异的度量因子,给出一种相关子空间中的局部离群数据挖掘算法.该算法根据K最近邻(K-NN),确定数据集中各数据对象的局部数据集,并依据属性值的稀疏因子生成全局的稀疏因子矩阵和局部稀疏因子矩阵,从而有效地反映了数据对象的局部稀疏程度;根据局部稀疏因子矩阵,计算属性维对应的局部稀疏差异因子,并确定数据对象对应的子空间定义向量,从而体现了具有任意性相关的相关子空间;如果数据对象存在相关子空间,则采用高斯误差函数体现相关子空间中各数据对象的局部密度差异,有效地降低了"维灾"的影响,使得离群数据的度量与相关子空间的维度无关,并能够度量相关子空间的数据对象,否则设置数据对象的局部密度差异为0,表明其为正常数据;选取局部密度差异(离群程度)最大的若干数据对象作为局部离群数据;最后采用UCI和恒星光谱数据集,实验验证了该算法的有效性.     

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

基于统计学和基于距离的离群点检测都依赖与给定数据点集的全局分布,然而数据通常并非都是均匀分布的。当分析分布密度相差很大的数据时,基于密度的局部离群点检测方法有着很好的识别局部离群点的能力。但存在时间复杂度较大,文章提出了一种改进的算法,能降低时间复杂度,实现有效的局部离群点的检测。     

基于相关子空间的高维离群数据检测算法

为了提高离群数据检测精度和效率,提出了一种基于相关子空间的离群数据检测算法。该算法首先根据数据局部密度分布特征得出稀疏度矩阵,通过高斯相似核函数放大稀疏度特征;然后计算各属性维中数据稀疏度相似因子,确定子空间向量及相关子空间,结合数据稀疏度和维度权值得出数据对象的离群因子,选取最大的若干个对象为离群数据;最后采用人工数...     

基于动态多向局部离群因子的在线故障检测*

针对化工间歇生产过程的多模态问题,为了提高故障检测性能,将滑动窗口技术与局部离群因子(LOF)算法相结合,提出了一种新的动态多向局部离群因子(Dynamic Multiway Local Outlier Factor,DMLOF)用于工业过程在线故障检测的方法。首先将间歇过程数据展开成二维数据,利用滑动窗口技术分别在时间片内运用局部离群因子算法计算LOF统计量,并利用核密度估计(KDF)确定控制限。其次,对于新来数据标准化处理后分别在相应窗口内投影,确定新数据的LOF统计量并与控制限比较进行故障检测。最后通过青霉素发酵过程的仿真实验结果验证了该算法的有效性。     

基于MapReduce与相关子空间的局部离群数据挖掘算法

针对高维海量数据,在MapReduce编程模型下,提出了一种基于相关子空间的局部离群数据挖掘算法.该算法首先利用属性维上的局部稀疏程度,重新定义了相关子空间,从而能够有效地刻画各种局部数据集上的分布特征;其次,利用局部数据集的概率密度,给出了相关子空间中的局部离群因子计算公式,有效地体现了相关子空间中数据对象不服从局部数据集分布特征的程度,并选取离群程度最大的N个数据对象定义为局部离群数据;在此基础上,采用LSH分布式策略,提出了一种MapReduce编程模型下的局部离群数据挖掘算法;最后,采用人工数据集和恒星光谱数据集,实验验证了该算法的有效性、可扩展性和可伸缩性.     

Top-k outlier detection from uncertain data

Uncertain data are common due to the increasing usage of sensors, radio frequency identification(RFID), GPS and similar devices for data collection. The causes of uncertainty include limitations of measurements, inclusion of noise, inconsistent supply voltage and delay or loss of data in transfer. In order to manage, query or mine such data, data uncertainty needs to be considered. Hence,this paper studies the problem of top-k distance-based outlier detection from uncertain data objects. In this work, an uncertain object is modelled by a probability density function of a Gaussian distribution. The naive approach of distance-based outlier detection makes use of nested loop. This approach is very costly due to the expensive distance function between two uncertain objects. Therefore,a populated-cells list(PC-list) approach of outlier detection is proposed. Using the PC-list, the proposed top-k outlier detection algorithm needs to consider only a fraction of dataset objects and hence quickly identifies candidate objects for top-k outliers. Two approximate top-k outlier detection algorithms are presented to further increase the efficiency of the top-k outlier detection algorithm.An extensive empirical study on synthetic and real datasets is also presented to prove the accuracy, efficiency and scalability of the proposed algorithms.     

IncLOF:动态环境下局部异常的增量挖掘算法

异常检测是数据挖掘领域研究的最基本的问题之一，它在欺诈甄别、贷款审批、气象预报、客户分类等方面有广泛的应用，以前的异常检测算法只适应于静态环境，在数据更新时需要进行重新计算，在基于密度的局部异常检测算法LOF的基础上，提出一种在动态环境下局部异常挖掘的增量算法IncLOF，当数据库中的数据更新时，只对受到影响的点进行重新计算，这样可以大大提高异常的挖掘速度,实验表明，在动态环境下IncLOF的运行时间远远小于LOF的运行时间，并且用户定义的邻域中的最小对象个数与记录数之比越小，效果越明显.     

NLOF：基于网格过滤的两阶段离群点检测算法

现有的离群度检测算法因没有对原数据进行处理导致计算时间复杂度过高,检测效果不理想。提出一种基于网格过滤的两阶段离群点检测算法NLOF。首先使用网格过滤对原数据进行初步筛选,将密度小于特定阈值的数据放入候选异常子集中;然后为了进一步优化基于密度的算法,基于k邻域,根据邻域中数据点的个数与邻域所组成圆的面积之比,作为数据点密度计算的依据,进行离群点检测以获得更准确的离群点集。在多种公开数据集上进行实验,实验表明,该方法可以在异常检测中取得良好的性能,同时降低了算法的时间复杂度。     

演化数据流上的连续异常检测

基于滑动窗口的异常检测是数据流挖掘研究的一个重要课题,在许多应用中数据流通常在一个分布网络上传输,解决这类问题时常采用分布计算技术,以便获得实时高质量的计算结果。对分布演化数据流上连续异常检测问题,进行形式化地阐述,提出了两个基于核密度估计的异常检测定义和算法,并通过大量真实数据集的实验,表明该算法具有良好的高效性和可扩展性,完全适应数据流应用的需求。