论文部分内容阅读
离群检测是数据挖掘的重要分支,离群数据对象隐藏着非常重要的信息和知识，发掘并运用这些财富推动着离群检测的研究。在理论上，研究者们对离群检测的研究取得了巨大的成功。在实际应用中，离群点检测也应用非常广泛，如信用卡欺诈、传感器数据检测、气象分析以及图像处理等等。离群数据可以分为点离群点和簇离群点。由于现实生活中数据集的复杂性以及多样性，有些离群点的相似性非常大，数量小，可认为是由特殊机制产生的离群簇。不能检测出这些离群小簇意味着丢失极其重要的隐秘信息。因此，检测簇离群点极其重要。传统的研究都集中于检测点离群点而忽视簇离群点，有些算法能检测出离群簇，但是效果不够理想。除此之外，传统的离群检测算法对参数、数据集密度、数据集分布敏感。针对这些问题，本文提出了基于k近邻树的离群检测算法。具体的研究成果包括如下：①对离群检测技术的背景以及意义进行了介绍，考察调研了离群检测技术的国内外现状。②对离群点产生的原因、分类及检测技术应用进行了简单介绍，系统全面地表述了当前的离群点检测算法，重点分析比较了各类离群点检测算法的优点以及局限性，最后简单阐述了离群点检测技术的当前热点和趋势。③提出基于k近邻的不相似性度量方法，该度量方法首次提出数据对象间的不相似性具有方向性，并且结合密度因素使得最终算法更适应数据集密度变化。④针对现有离群检测算法对簇离群点的检测欠佳问题提出了基于k近邻树的离群检测算法（Outlier Detection based on K-nearest Neighborhood MST.，KNMOD），算法通过采用Fibonacci堆等高级数据结构，大大提高了算法的检测效率，并且利用树的特性使得该算法能够克服数据集流形问题。通过人造具有明显局部离群点和离群簇的数据集，将算法和其他传统算法（LOF、KNN以及INFLO）进行对比实验，验证算法的有关特性；同时，将算法和其他传统算法(LOF、KNN、INFLO、COF)运行在UCI的五组真实数据集上，提出类ROC评估方法,比较他们的有效性，最终验证了算法的有效性以及合理性。