Come calcolare o approssimare la mediana di una lista senza memorizzare la lista

Sto cercando di calcolare la mediana di un insieme di valori, ma non voglio memorizzare tutti i valori che potrebbero far saltare i requisiti di memoria. Esiste un modo per calcolare o approssimare la mediana senza memorizzare e ordinare tutti i singoli valori?

Idealmente mi piacerebbe scrivere il mio codice un po ‘come il seguente

var medianCalculator = new MedianCalculator(); foreach (var value in SourceData) { medianCalculator.Add(value); } Console.WriteLine("The median is: {0}", medianCalculator.Median); 

Tutto ciò di cui ho bisogno è il vero codice MedianCalculator!

Aggiornamento: alcune persone hanno chiesto se i valori che sto cercando di calcolare la mediana abbiano proprietà conosciute. La risposta è si. Un valore è in incrementi di 0,5 da circa -25 a -0,5. L’altro è anche in incrementi di 0,5 da -120 a -60. Immagino che questo significhi che posso usare qualche forma di istogramma per ogni valore.

Grazie

tacca

Se i valori sono discreti e il numero di valori distinti non è troppo alto, puoi semplicemente accumulare il numero di volte in cui ogni valore si verifica in un istogramma, quindi trovare la mediana dai conteggi degli istogrammi (basta contare i conteggi dall’alto e dal basso dell’istogramma fino a raggiungere la metà). Oppure, se sono valori continui, puoi distribuirli in contenitori: non ti direbbero la mediana esatta ma ti darebbero un intervallo, e se hai bisogno di sapere con più precisione potresti ripetere l’elenco nuovamente, esaminando solo gli elementi nel cestino centrale.

C’è la statistica “remedian”. Funziona impostando prima k array, ciascuno di lunghezza b. I valori dei dati vengono inviati al primo array e, quando questo è pieno, la mediana viene calcasting e memorizzata nella prima posizione dell’array successivo, dopo il quale viene riutilizzato il primo array. Quando il secondo array è pieno, la mediana dei suoi valori viene memorizzata nella prima posizione del terzo array, ecc. Ecc. Si ottiene l’idea 🙂

È semplice e abbastanza robusto. Il riferimento è qui …

http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/Remedian.pdf

Spero che questo ti aiuti

Michael

Io uso questi stimatori medi e medi incrementali / ricorsivi, che usano entrambi una memoria costante:

 mean += eta * (sample - mean) median += eta * sgn(sample - median) 

dove eta è un piccolo parametro di velocità di apprendimento (es. 0.001) e sgn () è la funzione signum che restituisce uno tra {-1, 0, 1}.

Questo tipo di stimatore medio incrementale sembra essere usato dappertutto, ad esempio nelle regole di apprendimento della rete neurale non supervisionate, ma la versione mediana sembra molto meno comune, nonostante i suoi benefici (robustezza rispetto ai valori anomali). Sembra che la versione mediana potrebbe essere utilizzata come sostituto dello stimatore medio in molte applicazioni.

Mi piacerebbe vedere uno stimatore in modalità incrementale di una forma simile …

(Nota: ho anche postato questo argomento ad un argomento simile qui: algoritmi “on-line” (iteratore) per stimare la mediana statistica, la modalità, l’asimmetria, la curtosi? )

Ecco un approccio pazzo che potresti provare. Questo è un problema classico negli algoritmi di streaming. Le regole sono

  1. Hai una memoria limitata, ad esempio O(log n) dove n è il numero di elementi che desideri
  2. Puoi guardare ogni object una volta sola e prendere una decisione e lì cosa fare con esso, se lo immagazzini, costa della memoria, se lo butti via è sparito per sempre.

L’idea per trovare una mediana è semplice. Esempio O(1 / a^2 * log(1 / p)) * log(n) elementi dalla lista a caso, è ansible farlo tramite campionamento del serbatoio (vedere una domanda precedente ). Ora semplicemente restituisci la mediana dai tuoi elementi campionati, usando un metodo classico.

La garanzia è che l’indice dell’articolo restituito sarà (1 +/- a) / 2 con probabilità almeno 1-p . Quindi c’è una probabilità p di fallire, puoi sceglierlo campionando più elementi. E non restituirà la mediana o garantirà che il valore dell’object restituito è ovunque vicino alla mediana, solo che quando si ordina l’elenco l’object restituito sarà vicino alla metà della lista.

Questo algoritmo utilizza O(log n) spazio aggiuntivo e viene eseguito in tempo lineare.

Ciò è difficile da ottenere in generale, in particolare per gestire serie degenerate già ordinate o con un gruppo di valori all’inizio della lista, ma la fine dell’elenco ha valori in un intervallo diverso.

L’idea di base di creare un istogramma è molto promettente. Ciò consente di accumulare informazioni sulla distribuzione e rispondere a domande (come mediana) da esso. La mediana sarà approssimativa poiché ovviamente non si memorizzano tutti i valori. Lo spazio di archiviazione è fisso in modo che funzioni con qualsiasi sequenza di lunghezza.

Ma non puoi semplicemente build un istogramma da dire i primi 100 valori e usare continuamente quell’istogramma .. i dati che cambiano potrebbero invalidare quell’istogramma. Quindi hai bisogno di un istogramma dinamico in grado di cambiare la sua gamma e i cestini al volo.

Crea una struttura che abbia N bidoni. Memorizzerete il valore X di ogni transizione di slot (N + 1 valori totali) e la popolazione del bin.

Trasmetti i tuoi dati. Registra i primi valori N + 1. Se il stream termina prima di questo, ottimo, hai caricato tutti i valori e puoi trovare la mediana esatta e restituirla. Altrimenti usa i valori per definire il tuo primo istogramma. Basta ordinare i valori e usarli come definizioni bin, ogni bin con una popolazione di 1. Va bene avere dupes (0 width bid).

Ora streaming in nuovi valori. Per ognuno, ricerca binaria per trovare il cestino a cui appartiene. Nel caso comune, basta incrementare la popolazione di quel bin e continuare. Se il tuo campione è oltre i bordi dell’istogramma (più alto o più basso), estendi semplicemente l’intervallo del contenitore finale per includerlo. Quando il stream è terminato, si trova il valore del campione medio trovando il contenitore che ha uguale popolazione su entrambi i lati e interpolando linearmente la larghezza del contenitore rimanente.

Ma non è abbastanza .. devi ancora ADAPT l’istogramma per i dati mentre viene trasmesso in streaming. Quando un raccoglitore diventa troppo pieno, stai perdendo informazioni sulla distribuzione secondaria di quel bin. Puoi sistemarlo adattandoti in base ad un certo euristico … Il più semplice e robusto è se un bin raggiunge una determinata soglia di popolazione (qualcosa come 10 * v / N dove v = # di valori visti finora nello stream, e N è il numero di contenitori), SPLIT quello scomparto troppo pieno. Aggiungi un nuovo valore nel punto medio del contenitore, dai a ogni lato metà della popolazione del contenitore originale. Ma ora hai troppi contenitori, quindi devi CANCELLARE un cestino. Una buona euristica è quella di trovare il cestino con il più piccolo prodotto di popolazione e larghezza. Eliminalo e uniscilo con il suo vicino di sinistra o di destra (qualunque dei due vicini abbia il più piccolo prodotto di larghezza e popolazione). Fatto! Tieni presente che la fusione o la suddivisione dei raccoglitori perde informazioni, ma ciò è inevitabile .. hai solo una memoria fissa.

Questo algoritmo è bello in quanto si occuperà di tutti i tipi di flussi di input e darà buoni risultati. Se hai il lusso di scegliere l’ordine del campione, un campione casuale è il migliore, dal momento che riduce al minimo le divisioni e le fusioni.

L’algoritmo ti consente anche di interrogare qualsiasi percentile, non solo la mediana, dato che hai una stima di distribuzione completa.

Io uso questo metodo nel mio codice in molti posti, principalmente per il debug dei log … dove alcune statistiche che stai registrando hanno una distribuzione sconosciuta. Con questo algoritmo non è necessario indovinare in anticipo.

Lo svantaggio è che le larghezze bin non uguali significano che devi fare una ricerca binaria per ogni campione, quindi il tuo algoritmo netto è O (NlogN).

Il suggerimento di David sembra l’approccio più sensato per approssimare la mediana.

Una media in esecuzione per lo stesso problema è molto più facile da calcolare:

M n = M n-1 + ((V n – M n-1 ) / n)

Dove M n è la media di n valori, M n-1 è la media precedente, e V n è il nuovo valore.

In altre parole, la nuova media è la media esistente più la differenza tra il nuovo valore e la media, diviso per il numero di valori.

Nel codice questo sembrerebbe qualcosa di simile:

 new_mean = prev_mean + ((value - prev_mean) / count) 

anche se ovviamente potresti voler considerare cose specifiche della lingua come errori di arrotondamento a virgola mobile, ecc.

Non penso che sia ansible fare a meno di avere la lista in memoria. Ovviamente puoi approssimarti con

  • medio se si sa che i dati sono distribuiti simmetricamente
  • o calcola una mediana corretta di un piccolo sottoinsieme di dati (che si adatta alla memoria) – se sai che i tuoi dati hanno la stessa distribuzione nel campione (ad esempio che il primo elemento ha la stessa distribuzione dell’ultimo)

Trova Min e Max dell’elenco contenente N elementi attraverso la ricerca lineare e assegna loro il nome di Valore alto e Valore minimo Lascia MedianIndex = (N + 1) / 2

Ricerca binaria del 1 ° ordine:

Ripetere i seguenti 4 passaggi fino a LowValue

  1. Ottieni MedianValue circa = (Valore alto + Valore minimo) / 2

  2. Ottieni NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  3. è K = MedianIndex, quindi restituire MedianValue

  4. è K> MedianIndex? then HighValue = MedianValue Else LowValue = MedianValue

Sarà più veloce senza consumare memoria

Ricerca binaria di secondo ordine:

LowIndex = 1 HighIndex = N

Ripeti dopo 5 passaggi fino a (LowIndex

  1. Get Approximate DistrbutionPerUnit = (HighValue-LowValue) / (HighIndex-LowIndex)

  2. Ottieni approssimativo MedianValue = LowValue + (MedianIndex-LowIndex) * DistributionPerUnit

  3. Ottieni NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  4. è (K = MedianIndex)? restituire MedianValue

  5. è (K> MedianIndex)? quindi HighIndex = K e HighValue = MedianValue Else LowIndex = K e LowValue = MedianValue

Sarà più veloce del primo ordine senza consumare memoria

Possiamo anche pensare di montare HighValue, LowValue e MedianValue con HighIndex, LowIndex e MedianIndex su una parabola, e possiamo ottenere la ricerca binaria ThirdOrder che sarà più veloce del 2 ° ordine senza consumare memoria e così via …

Di solito se l’input è all’interno di un certo intervallo, diciamo da 1 a 1 milione, è facile creare una serie di conteggi: leggi il codice per “quantile” e “ibucket” qui: http://code.google.com/p/ EA-utils / source / browse / trunk / clipper / sam-stats.cpp

Questa soluzione può essere generalizzata come un’approssimazione forzando l’input in un intero all’interno di un intervallo utilizzando una funzione che si inverte all’uscita: IE: foo.push ((int) input / 1000000) e quantile (foo) * 1000000 .

Se il tuo input è un numero arbitrario di doppia precisione, devi eseguire la scalabilità automatica dell’istogramma non appena i valori entrano fuori range (vedi sopra).

Oppure puoi utilizzare il metodo delle mediane-triplette descritto in questo documento: http://web.cs.wpi.edu/~hofri/medsel.pdf