基于K-距离的孤立点和聚类算法研究

作     者：贾晨科 

作者单位：郑州大学 

学位级别：硕士

导师姓名：邱保志

授予年度：2006年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：数据挖掘 聚类算法 孤立点检测 p的k-距离 k-距离邻居 

摘      要：从大型数据集中发现有趣的，有用的且预先未知的知识的过程被称为数据挖掘。数据挖掘又称数据库中的知识发现，是数据库研究最活跃的领域之一。通过数据挖掘可以从大型数据集中提取可信、新颖、有效并易于理解的知识、规律或高层信息。这给人们在信息时代所积累的海量数据赋予了新的意义。随着数据挖掘技术的迅速发展，作为其重要组成部分，聚类分析和孤立点检测技术已经广泛应用于模式识别、数据分析、图象处理、市场研究等许多领域。聚类及孤立点检测算法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。 本文介绍了数据挖掘理论，对聚类及孤立点检测算法进行了深入地分析研究。在分析了基于密度的聚类算法和基于密度的孤立点算法的基础上，提出了基于局部孤立系数的孤立点检测和基于局部孤立系数的聚类算法;基于K-距离因子和增强的K-距离因子的孤立点检测算法。 本文使用Visual C++6.0实现了基于局部孤立系数的聚类算法、基于局部孤立系数的孤立点算法、基于K-距离因子的孤立点算法、增强的K-距离因子的孤立点算法、LOF算法、RDBKNN算法。在综合数据集上和真实数据集上做了大量的对比实验来验证孤立点算法的正确性，在综合数据集上验证孤立点算法的效率;在综合数据集上、真实数据集上和多密度数据集上验证基于局部孤立系数的聚类算法的正确性，在综合数据集上验证聚类算法的效率。 实验结果表明，基于局部孤立系数的聚类、基于局部孤立系数的孤立点、基于K-距离因子的孤立点、增强的K-距离因子的孤立点算法能够准确、有效的发现聚类和孤立点。聚类和孤立点检测算法在执行效率、聚类及孤立点检测效果等方面有一定的优越性。 总之，基于局部孤立系数的聚类算法不仅适合于均匀密度的数据集，而且对多密度数据集上也适合。该算法能有效的识别出各种形状的聚类，而且也能有效的识别出孤立点或噪声，在和RDBKNN算法对比中显示出了一定的优越性。最后，实验结果表明，无论是聚类算法还是孤立点检测算法都比原来的算法效率高。