基于最近邻相似度的孤立点检测及半监督聚类算法

摘要

聚类分析是数据挖掘领域的一种重要方法,聚类结果的好坏不仅依赖于相似度或者距离的定义,而且数据集中的孤立点也会影响聚类的效果。传统聚类分析是一种无监督的学习,没有先验知识的指导。在实际应用中,人们往往可以利用样本空间的一些先验知识或背景信息来解决类标号难的问题,因此产生了半监督聚类。
　　 本文首先介绍了聚类分析的相关知识,对数据挖掘中最基本的相似性度量进行了总结。对传统聚类算法进行了分析,给出了传统聚类算法的分类以及主要算法的性能比较;并详细论述了半监督聚类算法的框架以及它与传统聚类算法的不同之处。
　　 其次提出了基于最近邻的孤立点检测算法。首先分析了孤立点检测的重要性,给出了最近邻集的确定方法,并详细介绍了检测算法的具体步骤,并使用人工数据集和真实数据集验证了算法的准确性与高效性。
　　 本文还提出了基于共享最近邻的半监督聚类算法。首先研究了半监督算法中先验知识的相关情况,介绍了先验知识的获取方式以及表现形式,并提出对约束集扩展的两种方法:根据约束集本身的传递性以及数据集的特点对约束进行扩展。算法结合了扩展后的最近邻集,根据数据点间的SNN相似度构建SNN相似度图,使用图形分割方法得到聚类结果,并通过真实数据集验证了约束扩展方式的有效性以及聚类算法的高性能。
　　 最后,本文结合孤立点检测算法和半监督聚类算法,在一个含有孤立点的数据集上进行实验,先对数据集进行“去噪”处理,然后对其进行半监督聚类,通过实验验证了算法在孤立点检测以及半监督聚类方面,比其他算法具有更高的准确性。