在飞机上发现非常接近点 - 近似聚类算法需要

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

距离的平直（或甚至更高阶）应通过提高维帮助。然而，这种算法将偏向城市中心附近的点。它将很难在城市的边缘找到群集。

如何避免这个问题有什么建议？和任何其他建议，以提高该算法

来源

2013-07-10 arahant

也许这一个可以帮助你：http://stackoverflow.com/questions/17112719/how-can-i-find-the-center-of-a-cluster-of-data-points – Regenschein

是否需要群集1成为一个连通的空间？在街道的感觉（没有第2组点）或点类似的东西（没有第2类的点）？ – Galigator

@fordprefect哇，我希望它会比答案中提供的描述更简单。由于我不是数学家，因此需要一些时间才能掌握所说的内容。 – arahant

我建议沿着以下的说法：在距离小于给定值

关键概念相邻点的

计数。

在距离小于每个点P一个给定值d_cutoff半正式描述

计数数nc(P)相邻点的。
将所有点P_i与nc(P_i)集群大于阈值thres_count集群＃1。
对于集群＃1中的每个P_i将其近邻邻居（即，将Q与d(Q, P_i) < d_cutoff一起的点）添加到完全相同的集群＃1。
将集群＃2设置为集群＃1的补集。

算法角度

构建的无向图G=(V, E)与您的点为顶点设定V和在彼此的距离小于d_cutoff每对点之间的边缘。
从图中删除所有边缘e=(v,w)，其中deg(v) < thres_count和deg(w) < thres_count。
G的孤立顶点形式簇＃2中，补体是簇1＃。

如何选择你的点集的d_cutoff

构建一个最小生成树（MST）启发。边缘长度的频率分布应暗示适当的截止值。短成对距离将首先被并入mst。因此在具有自然聚类的点集的边缘长度的有序序列中应该至少存在一个明显的间隙。因此将一组mst边缘长度划分为少量相邻区间，以自然的方式对这些区间进行排序。计算每个间隔有多少实际距离值。考虑一个区间的序数和距离值的计数之间的映射。对于连续参数的函数值之间的大三角形将建议将较低区间中的距离的上界作为d_cutoff。

来源

2013-07-10 12:49:09 collapsar

感谢您的回答。算法肯定会摆脱我的算法偏向中心点的问题。该算法看起来像一个很好的近似值。只是麻烦的是选择d_cutoff和thres_count。具体选择d_cutoff将会很困难。太低，我们可能得不到足够的积分。太高，我们可能会在步骤3（您的半正式描述）中链接太多点。 – arahant

@arahant：我在回答问题的答案中添加了一节。 – collapsar

由于簇1中的点彼此接近，我认为基于密度的聚类算法可能有所帮助。您可以尝试OPTICS algorithm，它与DBSCAN类似，但知道密度不同，用户可以指定群集的数量。

来源

2013-07-11 04:03:10 fuch

在飞机上发现非常接近点 - 近似聚类算法需要

回答

相关问题