Trasformando i punti n-dim in m-dim dove mn e dove la deviazione della distanza punto-punto è minimizzata

2

Voglio applicare k-means clustering a un grafico di adiacenza (sparse). Per questo ho bisogno di assegnare i nodi ad una posizione in uno spazio euclideo. Trivialmente posso farlo avendo uno spazio con tante dimensioni quanti sono i nodi in cui ogni componente corrisponde ad un altro nodo.

Ora, per rendere il clustering un po 'più comprensibile, o forse solo diverso, sto pensando se ci sono modi per "piegare" lo spazio n-dimensionale dei punti in uno spazio più gestibile, forse 3- debole o forse solo m-dim dove m < n. Mentre faccio questo voglio mantenere le relazioni di distanza tra i nodi - quindi voglio minimizzare la deviazione tra la linea retta tra due punti qualsiasi prima della piega rispetto a dopo la piega, o in altre parole, la somma di tutte le deviazioni.

Quindi non riesco a trovare alcuna informazione al momento su questo aspetto. Forse mi manca la terminologia. Quali sono i metodi buoni / efficaci per questo? Algoritmi? Sembra un problema di ottimizzazione quadrata in qualche modo archetipico / medio.

Un semplice caso base:

P1 = (1,1,1)
P2 = (1,1,0)
p3 = (1,0,1)
newPoints = spacefold(2,[P1,P2,P3])

// example output:
// newPoints = [(1,1),
//              (1,0),
//              (0,1)]

Per questo esempio sono stati posizionati convenientemente su un piano: rimuovere il componente x fornisce una soluzione ottimale.

    
posta worldsayshi 23.01.2013 - 15:25
fonte

1 risposta

1

Il ridimensionamento multidimensionale è probabilmente quello che stai cercando. Prende come input una matrice di distanze e assegna a ciascun oggetto un vettore della dimensione di destinazione.

    
risposta data 01.03.2013 - 21:18
fonte

Leggi altre domande sui tag