algorithm - 在平面上找到非常接近的点 - 需要近似聚类算法

Question

我在一个平面(一个城市)上有很多点(纬度和经度)，我想找到两个集群。集群 1 是杂乱的点，集群 2 是其他一切。

我知道问题的定义不准确。唯一定义的是我正好需要 2 个集群。在 N 个点中，有多少点最终属于聚类 1 或聚类 2 未定义。

主要目的是识别彼此非常接近的点并将它们与其余点分开(分布更均匀)

我能想到的最好的是以下算法:

1. For each point, Calculate the sum of the square distances to all other points.
2. Run the k-means with k=2 on these square distances

距离的平方(或更高阶)应该有助于提高维度。然而，该算法将偏向于城市中心附近的点。很难在城市边缘找到集群。

关于如何避免这个问题有什么建议吗？以及任何其他改进此算法的建议

Answer 1

我建议按照以下几行:

关键概念

计算距离小于给定值的相邻点数。

半正式的描述

1. 计数 nc(P)距离小于给定值的相邻点 d_cutoff对于每个点 P .
2. 聚类所有点P_i与 nc(P_i)大于阈值 thres_count进入集群 #1。
3. 每个 P_i在集群 #1 中添加它的近邻，即点 Q与 d(Q, P_i) < d_cutoff到同一个集群 #1。
4. 将簇 #2 设置为簇 #1 的补集。

算法角度

1. 构建一个无向图 G=(V, E)你的点是顶点集 V以及距离小于 d_cutoff 的每对点之间的边从彼此。
2. 删除所有边e=(v,w)从图中 deg(v) < thres_count和 deg(w) < thres_count .
3. G的孤立顶点形成簇 #2，补集是簇 #1。

关于如何选择的启发式 d_cutoff

构建点集的最小生成树 (mst)。边长的频率分布应该暗示合适的截止值。短的成对距离将首先合并到 mst 中。因此，对于具有自然聚类的点集，在边长的有序序列中应该至少有一个明显的间隙。因此将 mst 边长度集划分为少量相邻间隔，以自然方式对这些间隔进行排序。计算每个区间有多少实际距离值。考虑间隔的序数与其距离值计数之间的映射。连续参数的函数值之间的大增量建议将下区间的距离上限取为 d_cutoff .