0

我在飞机（一个城市）上有很多点（纬度和经度），我想找到两个集群。簇 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

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

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

4

2 回答 2

1

我会提出以下几点建议：

关键概念

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

半正式的描述

  1. 为每个点nc(P)计算距离小于给定值的相邻点的数量。d_cutoffP
  2. 将所有大于阈值的P_i点聚类到聚类 #1。nc(P_i)thres_count
  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.

于 2013-07-10T12:49:09.513 回答
1

由于集群 1 中的点彼此靠近，我认为基于密度的聚类算法可能会有所帮助。您可以尝试OPTICS 算法，该算法类似于 DBSCAN，但可以感知不同的密度，并且可以由用户指定集群的数量。

于 2013-07-11T04:03:10.710 回答