解析名单和检测continious地区

Question

我有x的名单，y坐标

我需要做的是独立的那些成连续区域

所有组列表中的x，y坐标将最终属于特定的组。

我目前有一个简单的算法，只是通过每个点，并找到所有的相邻点（所以在x和+ -1上坐标为+ 1的点） 但是，它太慢时它涉及到使用大的x，y列表。

PS请记住，组中间可能存在漏洞。

Answer 1

您可以使用的一种简单方法是k-means clustering。 k -means将观察列表划分为k集群，其中每个点属于具有最近平均值的集群。如果你知道有一组点，那么这种方法应该工作得很好，假设你的点集合相当分离（即使它们有空洞）。 SciPy has an implementation of k-means应该很容易应用。

下面是您可以执行的分析类型的示例。

# import required modules 
import numpy as np 
from scipy.cluster.vq import kmeans2 

# generate clouds of 2D normally distributed points 
N = 6000000 # number of points in each cluster 

# cloud 1: mean (0, 0) 
mean1 = [0, 0] 
cov1 = [[1, 0], [0, 1]] 
x1,y1 = np.random.multivariate_normal(mean1, cov1, N).T 

# cloud 2: mean (5, 5) 
mean2 = [5, 5] 
cov2 = [[1, 0], [0, 1]] 
x2,y2 = np.random.multivariate_normal(mean2, cov2, N).T 

# merge the clouds and arrange into data points 
xs, ys = np.concatenate((x1, x2)), np.concatenate((y1, y2)) 
points = np.array([xs, ys]).T 

# cluster the points using k-means 
centroids, clusters = kmeans2(points, k=2) 

我2012工商管理硕士，1200万个数据点运行，这是相当快的：

>>> time python test.py 

real 0m20.957s 
user 0m18.128s 
sys  0m2.732s 

这也是100％准确的（并不奇怪，因为在点云完全不重叠） 。以下是计算群集分配准确性的一些快速代码。唯一棘手的部分是我首先使用欧几里德距离来确定哪个聚类的质心与原始数据云的均值匹配。

# determine which centroid belongs to which cluster 
# using Euclidean distance 
dist1 = np.linalg.norm(centroids[0]-mean1) 
dist2 = np.linalg.norm(centroids[1]-mean1) 
if dist1 <= dist2: 
    FIRST, SECOND = 0, 1 
else: 
    FIRST, SECOND = 1, 0 

# compute accuracy by iterating through all 2N points 
# note: first N points are from cloud1, second N points are from cloud2 
correct = 0 
for i in range(len(clusters)): 
    if clusters[i] == FIRST and i < N: 
     correct += 1  
    elif clusters[i] == SECOND and i >= N: 
     correct += 1 

# output accuracy 
print 'Accuracy: %.2f' % (correct*100./len(clusters)) 

Answer 2

首先，你可以用相应的图表G(V, E)识别问题：

点是顶点，有边e点A和点B之间，当且仅当A是“关闭”到B，您可以在其中自行定义“关闭”。

由于每个点只属于一个组，因此组会形成不相交的组，您可以使用简单的DFS将点分配给组。在图论中，潜在的问题被称为Connected Components。

DFS的复杂性是线性的，即O(V + E)。

Answer 3

你想要做的是在图像处理中调用连接组件。您有一个二进制图像，其中列表中的所有（x，y）像素都是1，而不是0的像素。

您可以使用numpy/scipy将数据转换为2D二进制图像，然后调用ndimage.label来查找连接的组件。

假设所有的x和y是> = 0，你知道MAX_X和MAX_Y，并将得到的图像能够装入内存，则是这样的：

import numpy as np 
from scipy import ndimage 

image = np.zeros(max_x, max_y) 
for x, y in huge_list_of_xy_points: 
    image[x, y] = 1 

labelled = ndimage.label(image) 

应该给你一个阵列，其中在组中的所有像素1具有值1，组2中的所有像素具有值2等等。未经测试。