Erstellen Sie ein ungefähr gleichmäßiges Gitter aus Zufallsstichprobe (Python)

Question

Ich möchte ein Raster aus Stichproben erstellen. Ich könnte einen maschinellen Lern-Clustering-Algorithmus, wie k-means, verwenden, aber ich möchte die Zentren auf ungefähr gleichförmige Verteilung beschränken.

Ich habe einen Ansatz mit der scikit-learn Suche nächste Nachbarn gefunden: Wählen Sie einen Punkt nach dem Zufallsprinzip, löschen Sie alle Punkte innerhalb Radius r dann wiederholen. Das funktioniert gut, aber ich frage mich, ob jemand einen besseren (schnelleren) Weg hat, dies zu tun.

Als Reaktion auf die Kommentare, die ich zwei alternative Methoden versucht haben, wendet man sich als viel langsamer die andere ist etwa die gleiche ...

Methode 0 (mein erster Versuch):

def get_centers0(X, r): 

    N = X.shape[0] 
    D = X.shape[1] 
    grid = np.zeros([0,D]) 
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') 

    while N > 0: 
     nearest.fit(X) 
     x = X[int(random()*N), :] 
     _, del_x = nearest.radius_neighbors(x) 
     X = np.delete(X, del_x[0], axis = 0) 
     grid = np.vstack([grid, x]) 
     N = X.shape[0] 

    return grid 

Methode 1 (unter Verwendung der vorberechneten graph):

def get_centers1(X, r): 

    N = X.shape[0] 
    D = X.shape[1] 
    grid = np.zeros([0,D]) 
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') 
    nearest.fit(X) 
    graph = nearest.radius_neighbors_graph(X) 

    #This method is very slow even before doing any 'pruning' 

Methode 2:

def get_centers2(X, r, k): 

    N = X.shape[0] 
    D = X.shape[1] 
    k = k 
    grid = np.zeros([0,D]) 
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') 

    while N > 0: 
     nearest.fit(X) 
     x = X[np.random.randint(0,N,k), :] 

     #min_dist = near.NearestNeighbors().fit(x).kneighbors(x, n_neighbors = 1, return_distance = True) 
     min_dist = dist(x, k, 2, np.ones(k)) # where dist is a cython compiled function 
     x = x[min_dist < 0.1,:] 

     _, del_x = nearest.radius_neighbors(x) 
     X = np.delete(X, del_x[0], axis = 0) 
     grid = np.vstack([grid, x]) 
     N = X.shape[0] 

    return grid 

diese Rennen wie folgt:

N = 50000 
r = 0.1 
x1 = np.random.rand(N) 
x2 = np.random.rand(N) 
X = np.vstack([x1, x2]).T 

tic = time.time() 
grid0 = get_centers0(X, r) 
toc = time.time() 
print 'Method 0: ' + str(toc - tic) 

tic = time.time() 
get_centers1(X, r) 
toc = time.time() 
print 'Method 1: ' + str(toc - tic) 

tic = time.time() 
grid2 = get_centers2(X, r) 
toc = time.time() 
print 'Method 1: ' + str(toc - tic) 

Methode 0 und 2 etwa gleich sind ...

Method 0: 0.840130090714 
Method 1: 2.23365592957 
Method 2: 0.774812936783 

Answer 1

Ich habe eine sehr einfache Methode entwickelt, die viel effizienter ist als meine früheren Versuche.

Diese Schleife wird einfach über den Datensatz gelegt und fügt den aktuellen Punkt nur dann zur Liste der Gitterpunkte hinzu, wenn er größer als der Abstand zu allen vorhandenen Zentren ist. Diese Methode ist ungefähr 20 Mal schneller als meine vorherigen Versuche. Da es keine externen Bibliotheken beteiligt sind, kann ich das alles in cython laufen ...

@cython.boundscheck(False) 
@cython.wraparound(False) 
@cython.nonecheck(False) 
def get_centers_fast(np.ndarray[DTYPE_t, ndim = 2] x, double radius): 

    cdef int N = x.shape[0] 
    cdef int D = x.shape[1] 
    cdef int m = 1 
    cdef np.ndarray[DTYPE_t, ndim = 2] xc = np.zeros([10000, D]) 
    cdef double r = 0 
    cdef double r_min = 10 
    cdef int i, j, k 

    for k in range(D): 
     xc[0,k] = x[0,k] 

    for i in range(1, N): 
     r_min = 10 
     for j in range(m): 
      r = 0 
      for k in range(D): 
       r += (x[i, k] - xc[j, k])**2 
      r = r**0.5 
      if r < r_min: 
       r_min = r 
     if r_min > radius: 
      m = m + 1 
      for k in range(D): 
       xc[m - 1,k] = x[i,k] 

    nonzero = np.nonzero(xc[:,0])[0] 
    xc = xc[nonzero,:] 

    return xc 

diese Methoden laufen wie folgt:

N = 40000 
r = 0.1 
x1 = np.random.normal(size = N) 
x1 = (x1 - min(x1))/(max(x1)-min(x1)) 
x2 = np.random.normal(size = N) 
x2 = (x2 - min(x2))/(max(x2)-min(x2)) 
X = np.vstack([x1, x2]).T 

tic = time.time() 
grid0 = gt.get_centers0(X, r) 
toc = time.time() 
print 'Method 0: ' + str(toc - tic) 

tic = time.time() 
grid2 = gt.get_centers2(X, r, 10) 
toc = time.time() 
print 'Method 2: ' + str(toc - tic) 

tic = time.time() 
grid3 = gt.get_centers_fast(X, r) 
toc = time.time() 
print 'Method 3: ' + str(toc - tic) 

Die neue Methode um 20 Mal schneller ist. Es könnte sogar noch schneller gemacht werden, wenn ich die Schleife früher aufhalte (z. B. wenn k aufeinanderfolgende Iterationen nicht in der Lage sind, ein neues Zentrum zu erzeugen).

Method 0: 0.219595909119 
Method 2: 0.191949129105 
Method 3: 0.0127329826355 

Answer 2

Vielleicht könnten Sie nur wieder passen die nearest Objekt jedes k < < N Löschungen beschleunige den Prozess. Meistens sollte sich die Nachbarschaftsstruktur nicht viel ändern.

Answer 3

Ich bin nicht sicher von der Frage genau, was Sie versuchen zu tun. Sie erwähnen, dass Sie ein "ungefähres Gitter" oder eine "einheitliche Verteilung" erstellen möchten, während der von Ihnen bereitgestellte Code eine Teilmenge von Punkten auswählt, sodass keine paarweise Entfernung größer als r ist.

Ein paar mögliche Vorschläge:

• wenn das, was Sie wollen, ist ein ungefähren Gitter, würde ich konstruieren, um das Raster Sie annähern wollen, und dann für die nächsten Nachbarn von jedem Gitterpunkt abzufragen. Abhängig von Ihrer Anwendung können Sie diese Ergebnisse zu Ausschnitten weiter schneiden, deren Abstand vom Gitterpunkt größer ist als für Sie nützlich.

• wenn das, was Sie wollen, ist eine annähernd gleichmäßige Verteilung aus den Punkten gezogen, würde ich an jedem Punkt eine Kerndichteschätzung (sklearn.neighbors.KernelDensity) tun, und tue eine randomisierte Unterauswahl aus dem Datensatz durch die inverse gewichtet der lokalen Dichte an jedem Punkt.

• wenn das, was Sie wollen, ist ein Teilmenge von Punkten, so dass keine paarweise Abstand größer alsr, ich würde zunächst eine radius_neighbors_graph mit Radius konstruieren r, das wird in einem Rutsch, geben Sie eine Liste aller Punkte, die zu nah beieinander liegen. Sie können dann einen Bereinigungsalgorithmus verwenden, der dem oben beschriebenen ähnlich ist, um Punkte auf der Grundlage dieser geringen Abstände zu entfernen.

Ich hoffe, dass hilft!

Answer 4

Klingt wie Sie versuchen, eine der folgenden neu zu erfinden:

• Clusterfunktionen (siehe BIRKEN)
• Daten Blasen (siehe „Datenblasen: Qualität Erhaltung Leistung für hierarchisches Clustering Boosten“)
• Baldachin vor dem Clustering

dh dieses Konzept wurde bereits mindestens dreimal mit kleinen Variationen erfunden.

Technisch ist es nicht Clustering. K-Means gruppiert sich auch nicht wirklich.

Es ist viel angemessener als Vektorquantisierung beschrieben.