3d配列の "スライス"内の行を互いに一致させるために

Question

私はいくつかのスペースで行がポイントである一連の2次元配列を持っています。多くの類似点は、すべての配列で異なる行順で発生します。 最も類似した順序になるように行を並べ替える必要があります。また、K-meansまたはDBSCANを使用したクラスタリングでは、ポイントが大きく異なります。問題は、このようにキャストすることもできます。配列を3次元配列に積み重ねると、2番目の軸に沿った平均標準偏差（SD）を最小にするために行をどのように並べ替えるのですか？ この問題の良いソートアルゴリズムは何ですか？

私は以下のアプローチを試みました。

1. リファレンス2dアレイへの平均ユークリッド距離を最小限にするために、リファレンス2dアレイとソート行を各アレイに作成します。 私はこれが偏った結果をもたらすのではないかと心配しています。

2. 行をペアで並べ替え、ペアの中央値のペア、そのペアなどを並べ替えます。これは実際には機能しません。理由はわかりません。

第三のアプローチは、単にブルートフォース最適化をすることができますが、私は配列の複数のセットを持っているので、上の手順を実行することを避けるようにしてください。

これが第二のアプローチ（パイソン）のために私のコードです：

def reorder_to(A, B): 
    """Reorder rows in A to best match rows in B. 

    Input 
    ----- 
    A : N x M numpy.array 
    B : N x M numpy.array 

    Output 
    ------ 
    perm_order : permutation order 
    """ 

    if A.shape != B.shape: 
     print "A and B must have the same shape" 
     return None 

    N = A.shape[0] 

    # Create a distance matrix of distance between rows in A and B 
    distance_matrix = np.ones((N, N))*np.inf 
    for i, a in enumerate(A): 
     for ii, b in enumerate(B): 
      ba = (b-a) 
      distance_matrix[i, ii] = np.sqrt(np.dot(ba, ba)) 

    # Choose permutation order by smallest distances first 
    perm_order = [[] for _ in range(N)] 
    for _ in range(N): 
     ind = np.argmin(distance_matrix) 
     i, ii = ind/N, ind%N 
     perm_order[ii] = i 
     distance_matrix[i, :] = np.inf 
     distance_matrix[:, ii] = np.inf 

    return perm_order 


def permute_tensor_rows(A): 
    """Permute 1d rows in 3d array along the 0th axis to minimize average SD along 2nd axis. 

    Input 
    ----- 
    A : numpy.3darray 
     Each "slice" in the 2nd direction is an independent array whose rows can be permuted 
     to decrease the average SD in the 2nd direction. 

    Output 
    ------ 
    A : numpy.3darray 
     A with sorted rows in each "slice". 
    """ 
    step = 2 
    while step <= A.shape[2]: 
     for k in range(0, A.shape[2], step): 

      # If last, reorder to previous 
      if k + step > A.shape[2]: 
       A_kk = A[:, :, k:(k+step)] 
       kk_order = reorder_to(np.median(A_kk, axis=2), np.median(A_k, axis=2)) 
       A[:, :, k:(k+step)] = A[kk_order, :, k:(k+step)] 
       continue 

      k_0, k_1 = k, k+step/2 
      kk_0, kk_1 = k+step/2, k+step 

      A_k = A[:, :, k_0:k_1] 
      A_kk = A[:, :, kk_0:kk_1] 

      order = reorder_to(np.median(A_k, axis=2), np.median(A_kk, axis=2)) 
      A[:, :, k_0:k_1] = A[order, :, k_0:k_1] 

     print "Step:", step, "\t ... Average SD:", np.mean(np.std(A, axis=2)) 
     step *= 2 

    return A 

Answer 1

私はあなたのコードサンプルを見ている必要があります申し訳ありません。それは非常に有益でした。

は、ここではこのように思える問題へのアウトオブボックスソリューションを提供します：数百ポイントのだけは本当に実現可能な

http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html#scipy.optimize.linear_sum_assignment

を高々しかし、私の経験で。