2

x、y座標のリストがあります

私がする必要があるのは、それらを連続した領域のグループに分けることです

ここに画像の説明を入力

リスト内のすべての x、y 座標は、特定のグループに属することになります。

私は現在、各ポイントを通過し、隣接するすべてのポイントを見つける単純なアルゴリズムを持っています(つまり、x で +-1 の座標と y で +-1 の座標を持つポイント)。 x、y リスト。

PS グループの途中に穴がある可能性があることに注意してください。

4

3 に答える 3

2

使用できる簡単な方法の 1 つは、k-means クラスタリングです。k -means は、観測値のリストをkクラスターに分割します。各点は、最も近い平均を持つクラスターに属します。ポイントのグループがあることがわかっている場合k=2、ポイントのクラスターが適切に分離されていると仮定すると (穴があっても)、この方法は非常にうまく機能するはずです。SciPy には、簡単に適用できる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 年の MBA で 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))
于 2013-10-25T17:57:09.570 に答える
2

やりたいことは、画像処理で連結成分を見つけることと呼ばれます。リストにあるすべての (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 などを持つ配列を与える必要があります。未検証。

于 2013-10-25T18:57:58.800 に答える
0

まず、対応するグラフで問題を特定できますG(V, E)。

ポイントは頂点であり、が に「近い」場合にのみ、ポイントとポイントeの間にエッジが存在します。ここで、独自に「閉じる」を定義できます。ABAB

各ポイントは正確に 1 つのグループに属しているため、グループはばらばらのセットを形成し、単純なDFSを使用してポイントをグループに割り当てることができます。グラフ理論では、根底にある問題はConnected Componentsと呼ばれます。

DFS の複雑さは直線的O(V + E)です。

于 2013-10-25T18:06:10.807 に答える