ottimizzazione combinatoria di una metrica di distanza

voti
1

Ho una serie di traiettorie, composta di punti lungo la traiettoria, e con le coordinate associate a ciascun punto. I memorizzare questi in una matrice 3d (traiettoria, punto, param). Voglio trovare l'insieme di traiettorie r che hanno la massima distanza accumulata tra le possibili combinazioni a coppie di queste traiettorie. Il mio primo tentativo, che credo sia sguardi come questo funziona:

max_dist = 0
for h in itertools.combinations ( xrange(num_traj), r):
    for (m,l) in itertools.combinations (h, 2):
        accum = 0.
        for ( i, j ) in itertools.izip ( range(k), range(k) ):
            A = [ (my_mat[m, i, z] - my_mat[l, j, z])**2 \
                    for z in xrange(k) ]
            A = numpy.array( numpy.sqrt (A) ).sum()
            accum += A
    if max_dist < accum:
        selected_trajectories = h

Questo richiede sempre, come num_traj può essere intorno 500-1000, e R può essere intorno 5-20. k è arbitraria, ma in genere può essere fino a 50.

Cercando di essere super-intelligente, ho messo tutto in due list comprehension annidati, facendo uso pesante di itertools:

chunk = [[ numpy.sqrt((my_mat[m, i, :] - my_mat[l, j, :])**2).sum() \
        for ((m,l),i,j) in \
        itertools.product ( itertools.combinations(h,2), range(k), range(k)) ]\
        for h in itertools.combinations(range(num_traj), r) ]

Oltre ad essere del tutto illeggibile (!!!), si è tenuto anche un lungo periodo di tempo. Qualcuno può suggerire dei modi per migliorare su questo?

È pubblicato 13/05/2010 alle 18:41
dall'utente
In altre lingue...                            


5 risposte

voti
3

Invece di ricalcolare la distanza tra ogni coppia di traiettorie su richiesta, è possibile avviare calcolando la distanza tra tutte le coppie di traiettorie. È possibile memorizzare quelli in un dizionario e di guardare in alto, se necessario.

In questo modo il vostro di anello interno for (i,j) ...sarà sostituita con una ricerca costante di tempo.

Risposto il 13/05/2010 a 18:53
fonte dall'utente

voti
2

È possibile abbandonare il calcolo della radice quadrata sul calcolo della distanza ... la somma massima avrà anche la massima quadrato somma, anche se che cede solo un aumento di velocità costante.

Risposto il 13/05/2010 a 18:59
fonte dall'utente

voti
1

E 'probabile che prendere per sempre in ogni caso, come l'algoritmo richiede circa ~ O( C( N, r ) * r^2 ), dove C( N, r )è N scegliere r. Per i più piccoli R (o N) questo potrebbe essere a posto, ma se assolutamente bisogno di trovare il massimo, invece di utilizzare un euristica approssimazione, si dovrebbe provare branch and bound con strategie diverse. Questo potrebbe funzionare per i più piccoli di r, e consente di risparmiare un bel po 'su nuovi calcoli inutili.

Risposto il 13/05/2010 a 19:42
fonte dall'utente

voti
2

Qui ci sono alcuni punti di interesse e suggerimenti, oltre a ciò che è già stato detto. (A proposito, il suggerimento di mathmike di generare un elenco di look-up tutte le distanze coppia è quello che si dovrebbe mettere in atto immediatamente. E si libera di un O (r ^ 2) dalla complessità dell'algoritmo.)

In primo luogo, le linee

for ( i, j ) in itertools.izip ( range(k), range(k) ):
    A = [ (my_mat[m, i, z] - my_mat[l, j, z])**2 \
        for z in xrange(k) ]

può essere sostituito con

for i in xrange(k):
    A = [ (my_mat[m, i, z] - my_mat[l, i, z])**2 \
        for z in xrange(k) ]

perché i e j sono sempre lo stesso in ogni ciclo. Non c'è alcuna necessità di utilizzare izip affatto qui.

In secondo luogo, per quanto riguarda la linea

A = numpy.array( numpy.sqrt (A) ).sum()

Sei sicuro che questo è come si desidera calcolare esso? Forse è così, ma appena mi ha colpito come strano, perché se questo è stato più di una distanza euclidea tra vettori allora la linea sarebbe:

A = numpy.sqrt (numpy.array( A ).sum())

o semplicemente

A = numpy.sqrt(sum(A))

perché penserei che la conversione di un a un array NumPy utilizzare la funzione somma di NumPy sarebbe più lento di un semplice utilizzando la funzione di somma built-in Python, ma potrei sbagliarmi. Inoltre, se è veramente una distanza euclidea che si desidera, allora si farà meno sqrt di questo modo.

In terzo luogo, ti rendi conto quante combinazioni potenziale si può tentare di iterare? Per il caso peggiore con num_traj = 1000 e R = 20, cioè circa 6.79E42 combinazioni della mia stima. Questo è abbastanza intrattabile con il metodo corrente. Anche per il miglior caso di num_traj = 500 e R = 5, che è 1.28E12 combinazioni che è un bel po ', ma non impossibile. Questo è il vero problema che stai avendo qui perché prendendo il consiglio di mathmike, i primi due punti che ho citato non sono molto importanti.

Cosa si può fare allora? Bene, avrete bisogno di essere un po 'più intelligente. Non mi è chiaro ancora quale sarebbe un grande uso metodo per questo. Sto indovinando che sarà necessario per rendere l'algoritmo di euristica in qualche modo. Un pensiero che ho avuto è stato quello di provare una programmazione dinamica tipo di approccio con un'euristica. Per ogni traiettoria si potrebbe trovare la somma o media delle distanze per ogni abbinamento di esso con un altro traiettoria e utilizzare questo come una misura di fitness. Alcune delle traiettorie con i più bassi misure di fitness potrebbe essere eliminato prima di passare a trii. Si potrebbe poi fare la stessa cosa con trii: trovare la somma o media delle distanze accumulate per tutti i trii (tra le rimanenti possibili traiettorie) che ogni traiettoria è coinvolto con e utilizzarlo come la misura di fitness per decidere quali far cadere prima di passare a foursome. E doesn'

Risposto il 13/05/2010 a 20:14
fonte dall'utente

voti
1

Questo suona come un problema "ponderato cricca": trovare ad esempio r = 5 persone in una rete con maximim compatibilità / somma massima di C (5,2) coppia pesi.
Google algoritmo "ponderato cricca" - "percolazione cricca" → 3K colpi.
Ma vorrei andare con il metodo di Justin Peel perché è comprensibile e controllabile
(prendere le migliori coppie n2, da loro i migliori triple n3 ... regolare n3 n2 ... al compromesso facilmente runtime / qualità dei risultati.)

18may aggiunta, un taglio ad un'implementazione segue.
@Jose, sarebbe interessante vedere cosa nCordiali [] sequenza funziona per voi.

#!/usr/bin/env python
""" cliq.py: grow high-weight 2 3 4 5-cliques, taking nbest at each stage
    weight ab = dist[a,b] -- a symmetric numpy array, diag << 0
    weight abc, abcd ... = sum weight all pairs
    C[2] = [ (dist[j,k], (j,k)) ... ]  nbest[2] pairs
    C[3] = [ (cliqwt(j,k,l), (j,k,l)) ... ]  nbest[3] triples
    ...
    run time ~ N * (N + nbest[2] + nbest[3] ...)

keywords: weighted-clique heuristic python
"""
# cf "graph clustering algorithm"

from __future__ import division
import numpy as np

__version__ = "denis 18may 2010"
me = __file__.split('/') [-1]

def cliqdistances( cliq, dist ):
    return sorted( [dist[j,k] for j in cliq  for k in cliq if j < k], reverse=True )

def maxarray2( a, n ):
    """ -> max n [ (a[j,k], (j,k)) ...]  j <= k, a symmetric """
    jkflat = np.argsort( a, axis=None )[:-2*n:-1]
    jks = [np.unravel_index( jk, a.shape ) for jk in jkflat]
    return [(a[j,k], (j,k)) for j,k in jks if j <= k] [:n]

def _str( iter, fmt="%.2g" ):
    return " ".join( fmt % x  for x in iter )

#...............................................................................

def maxweightcliques( dist, nbest, r, verbose=10 ):

    def cliqwt( cliq, p ):
        return sum( dist[c,p] for c in cliq )  # << 0 if p in c

    def growcliqs( cliqs, nbest ):
        """ [(cliqweight, n-cliq) ...] -> nbest [(cliqweight, n+1 cliq) ...] """
            # heapq the nbest ? here just gen all N * |cliqs|, sort
        all = []
        dups = set()
        for w, c in cliqs:
            for p in xrange(N):
                    # fast gen [sorted c+p ...] with small sorted c ?
                cp = c + [p]
                cp.sort()
                tup = tuple(cp)
                if tup in dups:  continue
                dups.add( tup )
                all.append( (w + cliqwt(c, p), cp ))
        all.sort( reverse=True )
        if verbose:
            print "growcliqs: %s" % _str( w for w,c in all[:verbose] ) ,
            print " best: %s" % _str( cliqdistances( all[0][1], dist )[:10])
        return all[:nbest]

    np.fill_diagonal( dist, -1e10 )  # so cliqwt( c, p in c ) << 0
    C = (r+1) * [(0, None)]  # [(cliqweight, cliq-tuple) ...]
        # C[1] = [(0, (p,)) for p in xrange(N)]
    C[2] = [(w, list(pair)) for w, pair in maxarray2( dist, nbest[2] )]
    for j in range( 3, r+1 ):
        C[j] = growcliqs( C[j-1], nbest[j] )
    return C

#...............................................................................
if __name__ == "__main__":
    import sys

    N = 100
    r = 5  # max clique size
    nbest = 10
    verbose = 0
    seed = 1
    exec "\n".join( sys.argv[1:] )  # N= ...
    np.random.seed(seed)
    nbest = [0, 0, N//2] + (r - 2) * [nbest]  # ?

    print "%s  N=%d  r=%d  nbest=%s"  % (me, N, r, nbest)

        # random graphs w cluster parameters ?
    dist = np.random.exponential( 1, (N,N) )
    dist = (dist + dist.T) / 2
    for j in range( 0, N, r ):
        dist[j:j+r, j:j+r] += 2  # see if we get r in a row
    # dist = np.ones( (N,N) )

    cliqs = maxweightcliques( dist, nbest, r, verbose )[-1]  # [ (wt, cliq) ... ]

    print "Clique weight,  clique,  distances within clique"
    print 50 * "-"
    for w,c in cliqs:
        print "%5.3g  %s  %s" % (
            w, _str( c, fmt="%d" ), _str( cliqdistances( c, dist )[:10]))
Risposto il 15/05/2010 a 17:00
fonte dall'utente

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more