论文部分内容阅读
随着计算机软硬件的发展,计算机存储设备能够存储的信息越来越多,人们要从海量的数据中寻找有用的信息却越来越难,数据挖掘作为处理海量数据的一种技术应运而生,它能够从杂乱的海量数据中,发现隐藏的潜在有用的模式与规律。聚类分析作为数据挖掘的重要组成部分,成为国内外学者的重要研究领域,聚类分析是非监督学习的一种数据挖掘技术,它基于“物以类聚”的思想,使得同类的数据对象具有较高的相似度,而不同类簇的数据对象具有较高的分离度。聚类分析根据聚类的具体方式可分为六种聚类方法:即为基于划分的聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于层次的聚类算法和基于模型的聚类算法。本文主要研究的是基于划分的聚类算法,通过研究国内外有关划分聚类算法的文献,根据其存在的一些问题,提出改进的算法。本文主要工作如下:1.基于最小方差优化的K-means算法。传统K-means算法随机选择初始聚类中心,聚类结果受数据输入顺序影响,即使数据输入顺序一定,其随机选择的初始聚类中心也会导致聚类结果不稳定。现有的一些改进K-means算法能够选出符合原始分布的较优初始聚类中心,但在选取中心点时需要一定的参数值,这些参数值没有规律可循,往往需要一定的经验值。本文算法根据数据对象的最小方差和所有数据对象的距离均值选取初始聚类中心,在选取初始聚类中心时不需要参数输入。改进算法很好解决了K-means随机选择初始聚类中心的问题,能够客观地选择出符合数据集原始分布的初始聚类中心。2.基于最小方差优化的K-medoid算法。传统K-medoid算法能够克服K-means算法对噪声点敏感的缺点,但仍然存在初始聚类中随机选择带来的缺陷,并增加了更新聚类中心时采用对所有非中心点进行评估的原则,致使K-medoids算法时间复杂度很大,无法处理大数据集的问题。本文提出最小方差优化的K-medoids算法,选取方差最小的数据对象同时结合所有数据对象的距离均值来选择初始聚类中心,使得选择的初始聚类中心尽可能的符合数据集的原始分布状态,尽可能位于不同的簇,并尽可能接近簇中心。为了降低K-medoids的时间复杂度,更新聚类中心时,选择同类簇中方差最小的数据对象进行更替,并运用聚类误差平方和进行判断是否更新类簇中心,从而加快算法的收敛速度,增强了原始K-medoids算法的伸缩性,使之能够处理大规模的数据集,提高了算法的执行效率。3.聚类有效性评价准则。聚类算法作为一种数据分析工具,聚类结果能否揭示数据集的原始分布或者能够达到人们的期望,是评价聚类算法性能的重要依据。构造一定的标准去评价聚类算法的结果,判定聚类算法是否揭示了数据集的原始分布或达到预期的期望,是聚类有效性评价研究的重点。正确合理的标准能有效分辨聚类算法的优劣,能对整个聚类过程进行客观分析。聚类有效性评价指标研究可以分为内部评价指标和外部评价指标两大类。本文总结了常用的几种内部有效性评价准则和外部有效性评价准则,对内部有效性准则进行了对比,分析这几种内部有效性评价准则的特点。同时介绍了几种常用的外部有效性评价准则,在对现有外部评价准则优缺点进行分析的基础上,提出新的外部有效性评价指标。新指标更能揭示聚类算法的结果是否反映了数据集的原始分布,并避免了现有外部评价指标对于类偏斜问题无法正确判断的缺陷。