论文部分内容阅读
聚类问题一直是模式识别领域的热点课题,其应用领域广泛,包括统计学、图像处理、医疗诊断、信息检索、生物学以及机器学习等。近年来,很多聚类方法纷纷涌现。这些方法大多受到自身算法的伸缩性限制,在特定数据规模的数据集上表现出优良的性能,但在超出其规定规模的数据集上往往收效甚微,甚至无法运行。随着信息采集与存储技术的飞速发展,数据的多样性越发突出,因此,对于高伸缩性的聚类方法的探索越发成为关注的焦点。本文主要针对聚类算法的伸缩性以及一些聚类算法存在的高昂计算复杂度和巨大内存需求而难以应用于大规模数据集的处理中的问题展开研究和讨论。在此过程中,本文的主要创新体现在以下几方面:(1)许多经典的聚类算法在小数据规模的数据聚类任务中取得了非常优秀的效果,但由于其伸缩能力不强,使得大多数算法在大规模数据的聚类任务中很难胜任或无法完成聚类分析的任务。针对探索高伸缩性聚类方法的问题,使得算法能够适应大幅度的数据规模变化,本文以化整为零的处理思想为基础,对于数据集先进行切分后划分的处理方式进行了深入的研究。提出一种基于这种处理方式的聚类方法—基于数据切分与划分的聚类方法。该方法处理数据不须将数据一次读入主存,可以大幅度的降低了算法对硬件资源的需求,相比于传统迭代产生的质心不易陷入局部最优。(2)DP是一种伸缩性较强的聚类方法,在小数据集合和大数据集合的聚类任务中都表现出了优异的聚类性能,但对于数据规模过大的情况下,其局部特征样本集过大,超出主存要求,仍然存在不足。针对这种情况,本文对于DP理论进行深入分析后提出了逐级压缩的思想,并对DP方法进行了改进,提出了一种基于均值径向压缩的聚类方法(Means Radial Compression,MRC),相比于DP方法,均值径向压缩方法MRC具有更好的伸缩性能,并且其优良的时间复杂度O(n)也使得其应用范围更广。(3)提出一种基于最小距离谱的数据特征聚类特性的可视化分析方法(MinDS)。通常情况下,用于参与聚类分析的数据是经过数据表示后产生的数据特征,应具有内在的联系,使其呈现出分组特性,聚类分析则指按照某种相似性测度找出这种数据分组。因此,数据表示过程、数据特征的选择将直接影响最终聚类结果。MinDS首先定义了最小距离谱模型,通过对最小距离谱特征分析,可以将多维数据间数据关系映射到二维数据空间中,对于直观的评价数据特征聚类特性,聚类方法失效原因等都获得了很好的效果。同时MinDS方法也可用于处理噪声,识别孤立点,寻求数据类别等方面。