Trova una linea più vicina ai punti sparsi

3

Mi sono imbattuto nella seguente domanda dell'intervista su Glassdoor:

Un grafico a dispersione di punti su una pagina, traccia una linea orizzontale sulla pagina in modo tale che la distanza perpendicolare alla linea da tutti i punti in aggregato sia ridotta al minimo. Descrivi un algoritmo per posizionare questa linea in modo ottimale

Il mio approccio:

Penso che possiamo calcolare la media delle distanze y e posizionare la linea lì.

Tuttavia, non sono sicuro che sia corretto o se esiste un approccio migliore per risolvere questo problema.

    
posta Chander Shivdasani 09.06.2015 - 14:02
fonte

3 risposte

1

Innanzitutto, poiché ci interessa solo la distanza y e disegneremo una linea orizzontale, basti pensare alle coordinate y dei punti e alla coordinata y che definisce la linea. La distanza tra un punto e la nostra linea sarà la differenza assoluta tra la coordinata y del punto e la coordinata y che definisce la linea.

Quindi, riformulando il problema, abbiamo un insieme di numeri, da y_1 a y_n, e abbiamo bisogno di un numero, z, che minimizzi l'aggregazione delle differenze assolute tra z e i punti da y_1 a y_n. Invece di minimizzare l'aggregato, possiamo semplicemente minimizzare la somma e ottenere il risultato corretto (aggregato = somma / numero_di_points).

Si scopre che è la mediana a fare questo, non il mezzo.

link

Per intuizione, avere punti alle coordinate y 10, 10, 10 e 110. La mediana è 10, la distanza aggregata è (0 + 0 + 0 + 100) / 4 = 25. La media è 140/4 = 35, la distanza aggregata è (25 + 25 + 25 + 75) / 4 = 37,5. In effetti spostando la linea a qualsiasi distanza, d, lontano dalla coordinata y 10 verso 100, si aumenta la distanza di 3 punti (con d) mentre si riduce solo la distanza a 1 punto (con d) e quindi si aumenta l'aggregato.

(Se prendessimo quadrati di distanza, la media sarebbe la risposta corretta)

    
risposta data 09.06.2015 - 17:23
fonte
0

Il metodo che usi per calcolare la linea dipende dalla funzione di costo che minimizzi. Puoi usare il valore y medio che imposta la somma delle distanze (misurate come positive quando un punto è sopra la linea e negativo quando il punto è al di sotto della linea) a zero.

Potresti usare una "somma minima dei quadrati della funzione di costo delle distanze", che fornirebbe una risposta diversa.

Entrambi sono semplici da calcolare. Potresti usare una "somma minima delle distanze assolute"; è più difficile da calcolare, e in generale dà una risposta diversa dagli altri due metodi.

Puoi anche ideare la tua funzione di costo per minimizzare. Buon divertimento!

Per i tuoi scopi, penso che la media sia una scelta sensata.

    
risposta data 09.06.2015 - 15:38
fonte
0

Come sottolinea Jonathan, ci sono un certo numero di diverse funzioni di costo che puoi minimizzare ma da the perpendicular y distance to the line from all points in aggregate is minimized suppongo che stessimo cercando la "somma minima della distanza assoluta".

Questo non è male da calcolare se ti capita di sapere che questo è lo stesso della mediana, proof (ho il sospetto che ciò lo rende una domanda scarsa per una posizione di sviluppo generale e uno più adatto per la scienza dei dati)

per trovare la mediana si possono ordinare i punti per co-ord, quindi prendere il punto medio dalla lista o la media dei due punti mediani.

    
risposta data 09.06.2015 - 17:23
fonte

Leggi altre domande sui tag