Skip to main content
 首页 » 编程设计

python之K均值聚类,使质心不与节点重叠

2025年05月04日14thcjp

我按照 http://datasciencelab.wordpress.com/2014/01/15/improved-seeding-for-clustering-with-k-means/ 中给出的方法,使用 Python 2.7 完成了 K-mean++ 聚类并获得了聚类的质心。

在我的问题中,还有一个进一步的限制,即任何质心到任何节点之间的距离应该大于常数。实现的最佳方式是什么?

一个质心可能离几个节点太近。

关于如何稍微移动质心有什么建议吗?

非常感谢。

比如要集群的节点有 MyNodes = [[469500, 5802610], [468764, 5803422], [467991, 5804202], [470260, 5799949], [469486, 5800730], [468713, 5801510], [467939, 58022916], [467939, 58022916], [46] , [467966, 5800204], [467193, 5800985], [466420, 5801766], [466457, 5799700], [465678, 5800488], [464950, 5799229], [470615, 57966002,7], [4594] 470320,5794955],[469547,5795735],[468773,5796516],[467990,5797297],[470062,5793215] 5796338], [466195, 5797119], [469976, 5791334], [469202, 5792115], [468429, 5792896], [467656, 5793676], [466882, 5794457], [466109, 5790538], [466109, 5796538] ] , [464600, 5796840], [470160, 5789250], [469354, 5789972], [468581, 5790753], [467808, 5791534], [467034, 5792315], [466261, 5793096], [466261, 5793096], [4793096], [4793096], [4678], [467808, 5791534] 464714​​, 5794658], [463941, 5795499], [463150, 5796210], [469500, 5787920], [468698, 5788614], [467925, 5789395], [467152, 5790176]]

质心 = [[ 467839.6, 5793224.1], [ 467617.22222222, 5800489.94444444]] 质心 [0] 离节点 [29] 太近了,质心 1会太靠近节点 [8]。

请您参考如下方法:

如果我正确理解你的问题,但我不确定我是否正确理解,那么从你的图纸中已经可以看出解决方案:

您想要最接近给定质心点的点;并且与一组节点有最小距离。

  • 围绕每个节点画一个圆,以你的最小距离为半径
  • 将每个圆与其他圆相交,记下交点
  • 丢弃任何距离节点小于最小距离的交点。
  • 从剩余的交点中,取最接近质心点的一个。那是你新的置换质心。

原始实现的运行时间应该是 O(number_of_nodes^2),尽管您可以在相交时通过使用一些快速最近邻查找数据结构(例如 kd 树)来优化它圆圈并丢弃太近的交点。

这应该是最优解;无论使用哪种算法,都无法找到更接近原始质心的点来满足最小距离约束;并且该算法应该总能找到最佳点。

虽然质心通常被节点包围,但如果节点密集,新点可能会相距很远。