改进的K-means算法：基于Kruskal生成初值

本文主要探讨了"基于Kruskal算法进行初值选取的改进的K-means算法"这一主题，由任倩和卓新建两位作者共同研究。K-means算法是数据科学领域中广泛应用的聚类算法，其核心原理是将数据集划分为K个互相不相交的簇，每个簇内的数据点与簇中心的距离之和最小。然而，K-means算法的一个显著缺点是其对初始聚类中心的敏感性，不同的初始中心可能导致不同的聚类结果，这在实际应用中可能会带来不确定性。 作者针对这一问题，提出了一个创新的方法，利用图论中的Kruskal算法来改进K-means算法。Kruskal算法是一种用于寻找无向图中最小生成树（Minimum Spanning Tree, MST）的经典算法，通过合并节点连接权重最小的边，构建出一棵包含所有节点的树，而没有形成环路。在此基础上，作者设计的改进版K-means流程如下： 1. 首先，通过对输入的数据对象构建一个无向图，计算所有对象之间的距离或相似度，构建出所有对象的邻接矩阵。 2. 应用Kruskal算法找到该图的最小生成树，即一条边连接所有对象的树结构，确保每两个对象之间都有一条最短路径。 3. 在最小生成树中，保留K-1条边，其余的边则被删除，使得剩下的K个连通子图分别代表K个潜在的初始聚类。 4. 对于每个连通子图，计算其中对象的均值作为对应的初始聚类中心。 5. 使用这些新的初始中心执行K-means算法的迭代过程，直到收敛，即簇不再发生变化或者达到预设的最大迭代次数。 通过这种方法，改进的K-means算法降低了对随机初始化的依赖，因为初始聚类中心是根据对象间的关系和结构自然产生的。实验结果显示，相比于传统的K-means算法，这种改进方法在聚类效果和准确性上有所提升，尤其在处理复杂、高维或噪声数据集时，优势更为明显。 总结来说，这篇论文的核心贡献在于将Kruskal算法巧妙地融入K-means算法，以减少对初始聚类中心选择的敏感性，并通过实验证明了其在提高聚类性能方面的有效性。这对于那些对聚类算法稳定性有较高要求的应用场景具有重要的实践价值。