パレトフロンティアインデックスnumpyを使って

Question

私は数多くのnumpyベクトル（行列M）にラベルを付けると、ラベルにパレートフロンティアインデックスが表示されます。

例えば、ベクター（v0）の非支配集合がパレートフロンティア指数0、V1（V1 = M - V0）が非支配ベクトルのセットで標識される指標で標識されます非支配ベクトルの1、次のセット/フロンティアV2（V2 = M - V0 - V1）2など行列Mの全てのベクトルが標識されるまで。

私はいくつかのテストケースをまとめましたが、それが非常に非効率的である（現時点ではあまり気にしない）か、あるいはうまく動作しません。

mat1 = np.asarray([ 
    [1, 2, 3, 4, 5, 7], 
    [1, 2, 3, 4, 5, 6], 
    [1, 2, 3, 4, 5, 6], 
]) 

calc_fronts(mat1) == [0, 1, 1] 

mat2 = np.asarray([ 
    [1, 2, 3, 4, 5, 7], 
    [1, 2, 3, 4, 5, 6], 
    [1, 22, 3, 4, 5, 6], 
]) 

calc_fronts(mat2) == [0, 1, 0] 


mat3 = np.asarray([ 
    [1, 2, 3, 4, 5, 7], 
    [1, 2, 3, 4, 5, 5], 
    [1, 2, 2, 4, 5, 4], 
]) 

calc_fronts(mat3) == [0, 1, 2] 


mat4 = np.asarray([ 
    [0, 2, 3, 4, 5, 7], 
    [1, 2, 3, 4, 5, 6], 
    [1, 22, 2, 4, 5, 6], 
]) 

calc_fronts(mat4) == [0, 0, 0] 

ベクトルXは、xでのforeach A場合、Yを支配yのB：A> = B AND > BためXに少なくとも1つのが存在します。

これは私の試みです：

def calc_fronts_2(vecs): 
    n = vecs.shape[0] 
    # find the most dominating 
    m = np.zeros(vecs.shape, dtype=bool) 
    dominates = [] 
    for i, vec in enumerate(vecs): 
     for x in xrange(n): 
      m[x] = i != x 
     mvecs = np.ma.masked_array(vecs, mask=~m) 
     # print 'i=', i 
     # print 'all better \n', np.all(vec >= mvecs, axis=1) 
     # print 'at least one\n', np.any(np.all(vec > vecs[m], axis=0)) 
     # print 'at least one\n', vec > mvecs 
     # print 'at least one\n', np.any(vec > mvecs, axis=1) 

     dom = np.where(np.all(vec >= mvecs, axis=1) & np.any(vec > mvecs, axis=1)) 
     dom = dom[0] 
     dominates.append(dom.tolist()) 
    # print dominates 

    dominated_by = [[j for j in xrange(n) if i in dominates[j]] for i in xrange(n)] 

    print 'domin:\n', dominates 
    print 'dom by\n', dominated_by 
    ranks = np.empty(n, dtype=int) 
    ranks.fill(-1) 
    for r in xrange(n): 
     remove = set() 
     for i in xrange(n): 
      if ranks[i] == -1 and len(dominated_by[i]) == 0: 
       ranks[i] = r 
       remove.add(i) 
     for ranked in remove: 
      for domby in dominated_by: 
       if ranked in domby: 
        domby.remove(ranked) 
     if np.all(ranks == -1): 
      break 
    return ranks 

Answer 1

ここでうまくいけば、いくつかの新しいアイデアを与えるために、私は非常に配列-重い試みは、です。ただし、（m、m、n）のテンポラリ配列が作成されることに注意してください（Mが（m、n）の場合）。

import numpy as np 

def calc_fronts(M): 
    i_dominates_j = np.all(M[:,None] >= M, axis=-1) & np.any(M[:,None] > M, axis=-1) 
    remaining = np.arange(len(M)) 
    fronts = np.empty(len(M), int) 
    frontier_index = 0 
    while remaining.size > 0: 
     dominated = np.any(i_dominates_j[remaining[:,None], remaining], axis=0) 
     fronts[remaining[~dominated]] = frontier_index 

     remaining = remaining[dominated] 
     frontier_index += 1 
    return fronts 

デモ：私が正しく理解していれば

In [217]: M = np.array([[ 0, 18, 1], 
    ...:    [ 4, 8, 11], 
    ...:    [ 3, 19, 3], 
    ...:    [18, 1, 19], 
    ...:    [16, 7, 13], 
    ...:    [ 3, 18, 3], 
    ...:    [15, 13, 19], 
    ...:    [13, 5, 13], 
    ...:    [ 2, 16, 16], 
    ...:    [ 9, 14, 17]]) 

In [218]: calc_fronts(M) 
Out[218]: array([2, 1, 0, 0, 0, 1, 0, 1, 0, 0])