Delaunay三角剖分、K-means聚类、数据点密度、聚类性能、初始化方法、时间复杂度。
在当前的机器学习和数据分析领域，聚类作为无监督学习的一个重要分支，已经被广泛应用于各类数据的分组和模式识别中。K-means聚类算法由于其简单高效而广受欢迎，但其对初始聚类中心的选择十分敏感，很容易导致局部最小问题，从而影响最终的聚类性能。为了解决这一问题，研究者们提出了各种改进方法。
K-means聚类算法是一种基于划分的非层次聚类方法，其核心思想是将n个数据点划分到k个聚类中，使得每个数据点属于离它最近的均值（即聚类中心）对应的聚类，以达到降低聚类内部差异的目的。算法通常使用欧氏距离作为衡量数据点间相似性的标准，并通过迭代寻找最优的聚类中心，从而最小化聚类内部的平方误差之和。
Delaunay三角剖分是一种在二维或三维空间中对一组点进行三角剖分的方法，它满足Delaunay准则，即任何一个三角形的外接圆内不包含其他的点。该方法能够产生一种具有“最优化”性质的三角剖分，在处理空间点集时能较好地反映其分布特性。在聚类算法中引入Delaunay三角剖分，有助于克服传统K-means算法对初始中心选择的敏感性，提高聚类效果。
在聚类性能的评估上，通常会考察以下几个方面：聚类结果是否使同一聚类内的数据点相似度高，不同聚类间的数据点相似度低；是否能够适应数据集的分布特征；以及聚类算法的计算效率。而上述提到的改进方法，如KKZ算法，虽然能够确保初始聚类中心间有一定的间隔，却未考虑到数据点的密度问题，可能会忽略掉数据集中的关键特征。
本文提出了一种新的基于Delaunay三角剖分的K-means聚类算法的初始聚类中心选择方法。该方法首先定义了代表数据点及其对应的密度，然后提出了一种新的距离度量方法，它综合了数据点密度和欧氏距离。通过使用Delaunay三角剖分，该算法能够在初始化阶段就考虑到数据点的分布特征，并结合数据点密度信息来挑选初始聚类中心。这能够有效提升算法的性能，特别是在高维数据集上的应用效果更为显著。
算法的时间复杂度也是研究中需要考虑的因素。本文对所提出的初始化方法的时间复杂度进行了分析，并将该算法应用于不同维度的数据集上，用于计算K-means算法的初始聚类中心。与CCIA算法、kd-tree算法和k-means++算法相比，本文提出的算法在获取K-means算法的初始聚类中心方面展示了优越的性能。
总结来说，本文的贡献主要在于提出了一种新的选择K-means聚类初始中心的方法，该方法基于Delaunay三角剖分，并且考虑了数据点的密度特性，从而有效提升了聚类性能，并通过实验证明了其有效性。该研究对于优化K-means算法及提高聚类分析的实际应用价值具有重要意义。
