modo incrementale di conteggio quantili per grande insieme di dati
-
26-09-2019 - |
Domanda
Devo contare i quantili per un grande insieme di dati.
Supponiamo possiamo ottenere i dati solo attraverso alcune porzioni (cioè fila uno di una grande matrice). Per contare il Q3 quantile una necessità di ottenere tutte le porzioni di dati e archiviare da qualche parte, quindi ordinare e contare il quantile:
List<double> allData = new List<double>();
// This is only an example; the portions of data are not really rows of some matrix
foreach(var row in matrix)
{
allData.AddRange(row);
}
allData.Sort();
double p = 0.75 * allData.Count;
int idQ3 = (int)Math.Ceiling(p) - 1;
double Q3 = allData[idQ3];
Vorrei trovare il modo di ottenere il quantile senza memorizzare i dati in una variabile intermedia. La soluzione migliore sarebbe contare alcuni parametri di metà risultati prima riga e quindi regolare passo a passo per righe successive.
Nota:
- Questi insiemi di dati sono molto grandi (circa 5000 elementi in ogni riga)
- Il Q3 può essere stimato, non deve essere un valore esatto.
- I chiamare le porzioni di dati "righe", ma possono avere diverse leghts! Di solito non varia così tanto (+/- poche centinaia di campioni) ma varia!
Questa domanda è simile a “on-line ”(iterator_traits) algoritmi per la stima mediana statistica, modo, asimmetria, curtosi , ma devo contare quantili.
Inoltre ci sono alcuni articoli in questo argomento, cioè .:
- Un ef fi ciente per l'approssimativa mediana Selezione problema
- incrementale quantile stima per il monitoraggio massiccia
Prima di provare a implementare questi approcci, mi sono chiesto se ci sono forse altri modi più rapidi di contare i quantili 0,25 / 0,75?
Soluzione 5
questa risposta ho creato un metodo che stima i quantili abbastanza buono. E 'approssimazione abbastanza vicino per i miei scopi.
L'idea è la seguente: il quantile 0,75 è in realtà una mediana di tutti i valori che si trova sopra la mediana globale. E, rispettivamente, 0,25 quantile è una mediana di tutti i valori al di sotto della mediana globale.
Quindi, se siamo in grado di approssimare la mediana, possiamo in modo simile, sul ravvicinamento delle quantili.
double median = 0;
double q1 = 0;
double q3 = 0;
double eta = 0.005;
foreach( var value in listOfValues) // or stream, or any other large set of data...
{
median += eta * Math.Sign(p.Int - median);
}
// Second pass. We know the median, so we can count the quantiles.
foreach(var value in listOfValues)
{
if(p.Int < median)
q1 += eta*Math.Sign(p.Int - q1);
else
q3 += eta*Math.Sign(p.Int - q3);
}
Commento:
- Se la distribuzione dei dati è strano, si avrà bisogno di avere grande
eta
in modo da adattarsi ai dati strano. Ma la precisione sarà peggio. - Se la distribuzione è strano, ma si sa la dimensione totale della vostra collezione (cioè N) è possibile regolare il parametro
eta
in questo modo: al beggining impostare ileta
essere quasi uguale un po 'di valore elevato (vale a dire 0,2). Come il ciclo passa, abbassare il valore dieta
in modo che quando si arriva quasi alla fine della collezione, ileta
sarà quasi uguale a 0 (ad esempio, nel ciclo di elaborazione in quel modo:eta = 0.2 - 0.2*(i/N);
Altri suggerimenti
I secondi l'idea di utilizzare secchi. Non ti limitare a 100 secchi - potrebbe anche usare 1 milione. La parte difficile è quello di scegliere gli intervalli di secchio in modo che tutto non finisca in un solo secchio. Probabilmente il modo migliore per stimare gli intervalli di secchio è quello di prendere un campione casuale ragionevole di dati, calcolare i quantili 10% e il 90% utilizzando l'algoritmo di ordinamento semplice, quindi generare secchi di uguali dimensioni per riempire tale intervallo. Non è perfetto, ma se i dati non è da una distribuzione super-strano, dovrebbe funzionare.
Se non si può fare a campione, sei nei guai. È possibile scegliere una congettura bucket iniziale basata sulla distribuzione dei dati previsto, quindi mentre si lavora attraverso i vostri dati se ogni secchio (in genere il primo o l'ultimo secchio) diventa troppo pieno, ricominciare da capo con una nuova gamma secchio.
C'è un più recente e molto più semplice algoritmo per questo che fornisce ottime stime dei quantili estremi.
L'idea di base è che bidoni piccoli sono utilizzati agli estremi in modo che entrambi delimita la dimensione della struttura di dati e garantisce una maggiore precisione per piccole o grandi q. L'algoritmo è disponibile in diverse lingue e molti pacchetti. La versione MergingDigest non richiede l'allocazione dinamica ... una volta che il MergingDigest viene creata un'istanza, non è necessaria alcuna ulteriore stanziamento mucchio.
- recuperare solo i dati che si ha realmente bisogno -. Vale a dire, qualsiasi valore (s) è / sono in uso come la chiave per l'ordinamento, non tutto il resto ad esso associato
- È possibile utilizzare probabilmente Selezionare l'algoritmo di Tony Hoare per trovare il tuo quantile più velocemente di quanto ordina tutti i dati.
Se i dati ha una distribuzione gaussiana, è possibile stimare i quantili dalla deviazione standard. Presumo i dati non siano gaussiana distribuito o si era appena utilizzare la deviazione standard in ogni caso.
Se si riesce a passare attraverso i dati due volte, farei il seguente:
- In primo passaggio, calcolare il massimo, minimo, SD e media.
- Secondo passaggio, divide l'intervallo [min, max] in qualche numero di segmenti (ad esempio 100); fare lo stesso per (media - 2 * SD, media + 2 * SD) (con secchi extra per valori anomali). Quindi eseguire attraverso i dati ancora una volta, i numeri che getta in queste secchi.
- Conte secchi finché non si è al 25% e il 75% dei dati. Se si desidera ottenere extra-fantasia, è possibile interpolare tra i valori della benna. (Cioè se avete bisogno di 10% di un secchio per colpire il 25 quantile, assume il valore è del 10% della strada dal basso legato al limite superiore.)
Questo dovrebbe dare un buon algoritmo di tempo lineare che funziona bene per la maggior parte dei set di dati non-tutto-perverso.
q-digest è un algoritmo in linea approssimativa che consente di calcolare quantile: http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf
Ecco un'implementazione: