Entfernen von Duplikaten (innerhalb einer gegebenen Toleranz) von einem Numpy-Vektorfeld

Question

Ich habe ein Nx5-Array mit N Vektoren der Form 'id', 'x', 'y', 'z' und 'Energie'. Ich muss doppelte Punkte entfernen (d. H. Wo x, y, z alle übereinstimmen) innerhalb einer Toleranz von etwa 0,1. Idealerweise könnte ich eine Funktion erstellen, in der ich das Array übergebe, Spalten, die übereinstimmen müssen, und eine Toleranz für die Übereinstimmung.

Nach this thread on Scipy-user kann ich Duplikate basierend auf einem vollständigen Array mit Record-Arrays entfernen, aber ich muss nur einen Teil eines Arrays übereinstimmen. Außerdem wird dies innerhalb einer bestimmten Toleranz nicht übereinstimmen.

Ich könnte mühsam durchlaufen mit einer for Schleife in Python, aber gibt es eine bessere Numponic Weg?

Answer 1

Sie könnten sich scipy.spatial.KDTree ansehen. Wie groß ist N?
Hinzugefügt: oops, tree.query_pairs ist nicht in scipy 0.7.1.

Im Zweifelsfall verwenden Brute-Force: spaltete den Raum (hier Seite^3) in kleine Zellen, einen Punkt pro Zelle:

""" scatter points to little cells, 1 per cell """ 
from __future__ import division   
import sys        
import numpy as np      

side = 100        
npercell = 1 # 1: ~ 1/e empty   
exec "\n".join(sys.argv[1:]) # side= ... 
N = side**3 * npercell     
print "side: %d npercell: %d N: %d" % (side, npercell, N) 
np.random.seed(1)      
points = np.random.uniform(0, side, size=(N,3)) 

cells = np.zeros((side,side,side), dtype=np.uint) 
id = 1 
for p in points.astype(int): 
    cells[tuple(p)] = id     
    id += 1        

cells = cells.flatten() 
    # A C, an E-flat, and a G walk into a bar. 
    # The bartender says, "Sorry, but we don't serve minors." 
nz = np.nonzero(cells)[0]    
print "%d cells have points" % len(nz) 
print "first few ids:", cells[nz][:10] 

Answer 2

nicht getestet, aber wenn Sie Ihre Array sortieren entlang x dann y dann z das sollte dir die Liste der Duplikate bringen. Sie müssen dann auswählen, was Sie behalten möchten.

def find_dup_xyz(anarray, x, y, z): #for example in an data = array([id,x,y,z,energy]) x=1 y=2 z=3 
    dup_xyz=[] 
    for i, row in enumerated(sortedArray): 
     nx=1 
     while (abs(row[x] - sortedArray[i+nx[x])<0.1) and (abs(row[z] and sortedArray[i+nx[y])<0.1) and (abs(row[z] - sortedArray[i+nx[z])<0.1): 
       nx=+1 
       dup_xyz.append(row) 
return dup_xyz 

Auch fand gerade diese http://mail.scipy.org/pipermail/scipy-user/2008-April/016504.html

Answer 3

Ich habe endlich eine Lösung, die ich mit glücklich bin, das ist ein Schnitt leicht gereinigt ist, und fügen Sie aus meinem eigenen Code. Es kann noch einige Fehler geben.

Hinweis: dass es immer noch eine 'for' Schleife verwendet. Ich könnte Denis 'Idee von KDTree oben zusammen mit der Rundung verwenden, um die vollständige Lösung zu erhalten.

import numpy as np 

def remove_duplicates(data, dp_tol=None, cols=None, sort_by=None): 
    ''' 
    Removes duplicate vectors from a list of data points 
    Parameters: 
     data  An MxN array of N vectors of dimension M 
     cols  An iterable of the columns that must match 
        in order to constitute a duplicate 
        (default: [1,2,3] for typical Klist data array) 
     dp_tol  An iterable of three tolerances or a single 
        tolerance for all dimensions. Uses this to round 
        the values to specified number of decimal places 
        before performing the removal. 
        (default: None) 
     sort_by  An iterable of columns to sort by (default: [0]) 

    Returns: 
     MxI Array An array of I vectors (minus the 
        duplicates) 

    EXAMPLES: 

    Remove a duplicate 

    >>> import wien2k.utils 
    >>> import numpy as np 
    >>> vecs1 = np.array([[1, 0, 0, 0], 
    ...  [2, 0, 0, 0], 
    ...  [3, 0, 0, 1]]) 
    >>> remove_duplicates(vecs1) 
    array([[1, 0, 0, 0], 
      [3, 0, 0, 1]]) 

    Remove duplicates with a tolerance 

    >>> vecs2 = np.array([[1, 0, 0, 0 ], 
    ...  [2, 0, 0, 0.001 ], 
    ...  [3, 0, 0, 0.02 ], 
    ...  [4, 0, 0, 1  ]]) 
    >>> remove_duplicates(vecs2, dp_tol=2) 
    array([[ 1. , 0. , 0. , 0. ], 
      [ 3. , 0. , 0. , 0.02], 
      [ 4. , 0. , 0. , 1. ]]) 

    Remove duplicates and sort by k values 

    >>> vecs3 = np.array([[1, 0, 0, 0], 
    ...  [2, 0, 0, 2], 
    ...  [3, 0, 0, 0], 
    ...  [4, 0, 0, 1]]) 
    >>> remove_duplicates(vecs3, sort_by=[3]) 
    array([[1, 0, 0, 0], 
      [4, 0, 0, 1], 
      [2, 0, 0, 2]]) 

    Change the columns that constitute a duplicate 

    >>> vecs4 = np.array([[1, 0, 0, 0], 
    ...  [2, 0, 0, 2], 
    ...  [1, 0, 0, 0], 
    ...  [4, 0, 0, 1]]) 
    >>> remove_duplicates(vecs4, cols=[0]) 
    array([[1, 0, 0, 0], 
      [2, 0, 0, 2], 
      [4, 0, 0, 1]]) 

    ''' 
    # Deal with the parameters 
    if sort_by is None: 
     sort_by = [0] 
    if cols is None: 
     cols = [1,2,3] 
    if dp_tol is not None: 
     # test to see if already an iterable 
     try: 
      null = iter(dp_tol) 
      tols = np.array(dp_tol) 
     except TypeError: 
      tols = np.ones_like(cols) * dp_tol 
     # Convert to numbers of decimal places 
     # Find the 'order' of the axes 
    else: 
     tols = None 

    rnd_data = data.copy() 
    # set the tolerances 
    if tols is not None: 
     for col,tol in zip(cols, tols): 
      rnd_data[:,col] = np.around(rnd_data[:,col], decimals=tol) 

    # TODO: For now, use a slow Python 'for' loop, try to find a more 
    # numponic way later - see: http://stackoverflow.com/questions/2433882/ 
    sorted_indexes = np.lexsort(tuple([rnd_data[:,col] for col in cols])) 
    rnd_data = rnd_data[sorted_indexes] 
    unique_kpts = [] 
    for i in xrange(len(rnd_data)): 
     if i == 0: 
      unique_kpts.append(i)  
     else: 
      if (rnd_data[i, cols] == rnd_data[i-1, cols]).all(): 
       continue 
      else: 
       unique_kpts.append(i)  

    rnd_data = rnd_data[unique_kpts] 
    # Now sort 
    sorted_indexes = np.lexsort(tuple([rnd_data[:,col] for col in sort_by])) 
    rnd_data = rnd_data[sorted_indexes] 
    return rnd_data 



if __name__ == '__main__': 
    import doctest 
    doctest.testmod()