基于密度划分的离群点检测算法

目前,大部分离群点检测算法需要人工输入参数,不能同时检测出全局和局部离群点,不能有效处理密度不均匀数据。针对这些问题,提出一种基于密度划分的离群点检测算法DD-DBSCAN。主要创新包括:1)运用最小生成树的方法,新定义簇密度概念,将数据录入后划分成密度不等的簇,使算法能够处理密度分布不均匀的数据;2)采用"分而治之"的思想,对经过划分的数据集分别进行离群点检测,使得算法能够同时处理全局和局部离群点;3)通过在各个簇中自适应地计算所需参数值,算法不再需要人工输入参数(聚类半径(Eps)等)。通过在2D模拟数据集和Iris真实数据集上的实验表明,与DBSCAN算法比较,本文算法具有更高的覆盖率和正确率。     

一种基于邻域系统密度差异度量的离群点检测算法

针对离群点检测算法LOF在高维离散分布数据集中检测精度较低及参数敏感性较高的问题,提出了基于邻域系统密度差异度量的离群点检测NSD（neighborhood system density difference）算法。相较于传统基于密度的离群点检测方法,NSD算法引入了截取距离的概念。首先计算数据集中对象在截取距离内的邻居点个数;其次计算对象的邻域系统密度;然后将对象的密度与它邻居的密度进行比较,判定目标对象与其邻居趋向于同一簇的程度;最后输出最可能是离群点的对象。将NSD算法与LOF、LDOF、CBOF算法在真实数据集与合成数据集中对比实验发现,NSD算法具有较高的检测准确率和执行效率以及较低的参数敏感性,证明了NSD算法是有效可行的。     

加速大规模数据集的离群点检测

针对现有基于距离的离群点检测算法在处理大规模数据时效率低的问题,提出一种基于聚类和索引的分布式离群点检测(DODCI) 算法。首先利用聚类方法将大数据集划分成簇;然后在分布式环境中的各节点处并行创建各个簇的索引;最后使用两个优化策略和两条剪枝规则以循环的方式在各节点处进行离群点检测。在合成数据集和整理后的KDD CUP数据集上的实验结果显示,在数据量较大时该算法比Orca和iDOoR算法快近一个数量级。理论和实验分析表明,该算法可以有效提高大规模数据中离群点的检测效率。     

基于共享反K近邻的局部离群点检测算法

离群点检测和分析离群模式隐含的特征是离群点挖掘的重要研究内容.现有离群点检测算法存在两个明显的不足:根据离群度检测离群点,难以确定离群点的数量;忽略了与离群点邻接的聚类信息,不能提供解析离群模式的有效证据.为此,提出一种基于共享反K近邻的离群点检测算法,首先定义了一种对密度和维数变化不敏感的共享反K近邻相似度,然后应用聚类方法将数据集划分为聚类簇和包含离群点的离群簇,从而获取数据集中的离群点及解析离群点的聚类结构.仿真结果表明,反K近邻算法比现有方法更能精确地检测数据集中的局部离群点,具有很好的控制性能.     

基于图上随机游走的离群点检测算法

离群点检测算法在网络入侵检测、医疗辅助诊断等领域具有十分广泛的应用。针对LDOF、CBOF及LOF算法在大规模数据集和高维数据集的检测过程中存在的执行时间长及检测率较低的问题,提出了基于图上随机游走(BGRW)的离群点检测算法。首先初始化迭代次数、阻尼因子以及数据集中每个对象的离群值;其次根据对象之间的欧氏距离推导出漫步者在各对象之间的转移概率;然后通过迭代计算得到数据集中每个对象的离群值;最后将数据集中离群值最高的对象判定为离群点并输出。在UCI真实数据集与复杂分布的合成数据集上进行实验,将BGRW算法与LDOF、CBOF和LOF算法在执行时间、检测率和误报率指标上进行对比。实验结果表明,BGRW算法能够有效降低执行时间并在检测率及误报率指标上优于对比算法。     

基于密度峰值和近邻优化的聚类算法

针对密度峰值算法在选取聚类中心时的时间复杂度过高,需要人工选择截断距离并且处理流形数据时有可能出现多个密度峰值,导致聚类准确率下降等问题,提出一种新的密度峰值聚类算法,从聚类中心选择、离群点筛选、数据点分配三方面进行讨论和分析,并给出相应的聚类算法。在聚类中心的选择上采取KNN的思想计算数据点的密度,离群点的筛选和剪枝以及数据点分配则利用Voronoi图的性质,结合数据点的分布特征进行处理,并在最后应用层次聚类的思想以合并相似类簇,提高聚类准确率。实验结果表明:所提算法与实验对比算法相比较,具有较好的聚类效果和准确性。     

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

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

工业过程数据异常检测的改进局部离群因子法

局部离群因子(LOF)是对过程数据的局部离群程度的定义,然而工业过程对数据异常检测的实时性要求高,要求出所有采样点的离群因子计算量较大。故本文对LOF算法进行相应的改进,采用k-近邻计算对象的局部可达密度,同时利用1种预处理采样点的方法CDC(Closest Distance to Center),通过计算每个点到中心点的距离先对采样点进行修剪,剔除大部分不可能是离群点的采样点,只需要计算剩余点改进的LOF值,从而提高离群点检测的效率。最终通过对TE过程数据仿真,说明在保证离群点检测准确性的情况下,相比于LOF缩短了算法运行的时间。     

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

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

基于K-近邻树的离群检测算法

为适应数据集分布形状多样性以及克服数据集密度问题,针对已有算法对离群簇检测效果欠佳的现状,提出了一种基于K-近邻树的离群检测算法KNMOD(outlier detection based on K-nearest neighborhood MST).算法结合密度与方向因素,提出一种基于K-近邻的不相似性度量,然后带约束切割基于此度量构建的最小生成树从而获得离群点.算法可以有效地检测出局部离群点以及局部离群簇,与LOF、COF、KNN及INFLO算法的对比结果也证实了算法的优越性能.     

基于聚类的两段式孤立点检测算法

现有的大多数孤立点检测算法都需要预先设定孤立点个数,并且还缺乏对不均匀数据集的检测能力。针对以上问题,提出了基于聚类的两段式孤立点检测算法,该算法首先用DBSCAN聚类算法产生可疑孤立点集合,然后利用剪枝策略对数据集进行剪枝,并用基于改进距离的孤立点检测算法产生最可能孤立点排序集合,最终由两个集合的交集确定孤立点集合。该算法不必预先设定孤立点个数,具有较高的准确率与检测效率,并且对数据集的分布状况不敏感。数据集上的实验结果表明,该算法能够高效、准确地识别孤立点。     

基于幂图的离群子空间搜索算法*

通过分析子空间搜索算法的研究现状以及存在的问题,提出基于幂图的离群子空间搜索算法。该方法主要讨论离群点产生的原因,能够找出单个对象的离群子空间,并根据离群子空间对离群点进行分类。在对幂图扩展的基础上进行剪枝,减少了存储量和计算量,算法性能得到很大的提高。采用实例说明了该算法,并通过实验证明了该算法的可行性和高效性。     

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

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

基于聚类划分的两阶段离群点检测算法

针对基于距离的离群点检测算法受全局阈值的限制, 只能检测全局离群点, 提出了基于聚类划分的两阶段离群点检测算法挖掘局部离群点。首先基于凝聚层次聚类迭代出K-means所需的k值, 然后再利用K-means的方法将数据集划分成若干个微聚类; 其次为了提高挖掘效率, 提出基于信息熵的聚类过滤机制, 判定微聚类中是否包含离群点; 最后从包含离群点的微聚类中利用基于距离的方法挖掘出相应的局部离群点。实验结果表明, 该算法效率高、检测精度高、时间复杂度低。     

一种基于多示例学习的局部离群点检测算法

提出了一种基于多示例学习（multi-instance learning,MIL）的局部离群点检测算法,称之为MIL-LOF（a local outlier factor based on multi-instance learning）．算法采用MIL框架,首先将真实对象提取为多示例形式,然后运用退化策略和权重调整方法,计算综合离群点因子,最后检测离群点．在实际企业监控数据以及公共数据集上将MIL-LOF与经典局部离群点检测算法及其优化算法进行了对比实验,结果表明本文提出的MIL-LOF算法在准确性、全面性及高效性上相对其他算法均可获得较为明显的提高．     

基于小波密度估计的数据流离群点检测

为能及时发现数据流上的局部离群点,分析数据流已有的离群点挖掘算法,提出基于小波密度估计的离群点检测算法。利用小波密度估计多尺度和多粒度的特点,通过小波概率阈值判断数据流中当前滑动窗口内的数据点是否为离群点,并对数据流中离群点检测过程进行讨论。仿真结果表明,与核密度估计算法相比,该算法的检测效率与精度较高。     

一种基于概率的孤立点检测方法

现有孤立点检测方法大多数都需要预先设定孤立点个数,若设定不准确将降低孤立点检测的准确性。针对该问题,提出一种基于概率的孤立点检测方法。结合基于密度的DBSCAN算法与中位数求方差的方法,对待检测数据集进行聚类,提取出不包含在任何聚类中的可疑孤立点并进行分析,从而确定最终孤立点。该方法所检测的数据与时间因素线性无关,不必预先设定孤立点个数及聚类数,并且对噪声数据具有较强的抗干扰能力。IRIS测试数据集上的实验结果表明,该方法能够有效地识别孤立点。