2012-03-03 11 views
6

Sto scrivendo del codice di Machine Learning in MATLAB e sto rappresentando un grafico con una matrice di adiacenza A e un raggruppamento del grafico con una matrice Z definita nei modi seguenti.Ottimizzazione del codice vettoriale per la adiacenza del grafico

A: a_ij è 1 se c'è uno spigolo tra il nodo i e il nodo j. 0 altrimenti. Z: z_ij è 1 se il nodo j è nel cluster i. 0 altrimenti.

sto calcolo di una matrice N, che è il numero di spigoli tra cluster, definito nel modo seguente:

N: n_ij è il numero di archi tra i nodi del cluster i e j nodi del cluster. n_ii è il numero di spigoli all'interno del cluster i.

N può essere calcolato:

N = zAz' 

dove z' è z-recepita.

Se ho molti nodi, il calcolo richiede un po 'di tempo, ma non è questo il problema. Il problema è che sposto un sacco di volte i nodi da cluster a cluster, e ogni volta voglio calcolare N.

Quindi il problema è il seguente: Dato che conosco N, e che quindi spostare nodo dal cluster c_1 al cluster c_2, come posso aggiornare N in modo efficiente?

risposta

2

Per passare da Z a Z + U, aggiornare

N ← N + 'Z (UA) + Z (AU)' + UAU'
Z ← Z + U.

Z e U (e A, se ha senso per il grafico) dovrebbero avere rappresentazioni sparse. In teoria, almeno, questo fa più o meno nel codice compilato cosa farei in C: scansionare i vicini di i, decrementare i conteggi degli edge da e verso il vecchio cluster di i e incrementare i conteggi degli edge da e verso il nuovo cluster di i . In pratica, potrebbe essere necessario trasporre Z per farlo allineare con la rappresentazione di matrice sparse di Matlab e eseguire l'aggiornamento Z ← Z + U sostituendo due intere righe in modo che le voci appena azzerate non vengano trattate come non nerali.

+0

Immagino di aver dimenticato di specificare che a volte ho bisogno di creare un nuovo cluster e che a volte devo rimuovere i cluster. Come dovrei creare U durante la costruzione di un nuovo o la rimozione di un cluster? – utdiscant

+0

Aggiungere un cluster vuoto: aggiungere una riga zero a Z e riga/colonna a N. Eliminare un cluster vuoto: invertire questa procedura. Se in realtà intendi unire due cluster, c'è un modo migliore per aggiornare N che spostare un vertice alla volta (sostituisci le due righe di Z con la loro somma, quindi sostituisci le due righe e poi le colonne di N con la loro somma). – foobar