聚类分析中的改进K--means算法和新聚类有效性指标的研究

摘要

聚类分析是自主的发现数据集中的自然结构，并根据数据间的规律将数据集划分成若干个聚簇的重要工具。作为“无监督学习”的方法，聚类分析已经被广泛应用在数据挖掘，模式识别，图像处理等领域。聚类分析主要分为对聚类算法和聚类有效性指标(CVI)的研究。但是，面对大数据时代，现有的聚类算法和聚类有效性指标都存在若干问题，包括:算法的效率较低、聚类结果的准确性较差、对噪声点较为敏感和无法高效正确地处理大规模数据集等问题。针对上述问题，本文聚焦于对K-means算法的改进，同时提出了新的适用于大数据的聚类有效性指标(BCVI)。 本文的主要工作如下: (1)针对传统的K-means算法应对大规模数据集时效率较低的问题，本文将网格算法中划分网格的思想引入K-means算法提高算法效率，提出了改进算法Grid-K-means;同时，本文利用网格算法中的网格密度解决了K-means算法无法确定初始聚类中心的问题;为了规避网格算法划分网格需要设置过多参数的问题，本文利用动态网格的操作代替数据点的操作来提高改进的Grid-K-means算法的效率和准确率，并减少聚类算法需要手动设置初始参数的数量。改进的Grid-K-means算法具有更好的稳定性、准确性和鲁棒性。 (2)本文提出新的适用于大规模数据集的聚类有效性指标BCVI。BCVI指标利用加权网格作为多个代表点来处理各种形状的聚簇，避免了所有样本点参与计算带来的计算量过大的问题。同时，多个代表点较单个代表点可以更好地评估聚类结果的质量。最后，利用各个聚类中心构建的最小生成树和最大生成树的组合确定聚簇之间的分离性。各个聚类中心之间的最大生成树的加入可以更好的评估聚簇间的分离程度，同时可以平衡聚簇内部紧致性数据上的差异，保证BCVI指标有更稳定的评估效果。 (3)BCVI指标由簇内紧致性和簇间分离性的线性组合构成，通过分析BCVI指标特性可以发现BCVI指标具有的单调性特性可以快速地确定最佳聚类数(Kopt)。BCVI在寻找最佳聚类数(Kopt)方面花费的时间成本远低于利用经验规则2≤K≤√n的常用方法。通过该方法，BCVI可以快速确定最佳聚类数Kopt，特别是对于大规模数据集。 (4)利用模拟数据集和真实数据集对本文提出的改进算法Grid-K-means和新的聚类有效性指标BCVI进行测试。实验证明，Grid-K-means算法比传统的K-means算法、K-medoids算法、K-means++算法和改进的K-means算法更快，更准确。同时，BCVI指标与其他7种现有指标(DI指标、DBI指标、I指标、CH指标、COP指标、STR指标、VCVI指标)的对比实验结果表明，新的BCVI指标在数据处理速度和稳定性方面优于传统指标。