modo incrementale di conteggio quantili per grande insieme di dati

StackOverflow https://stackoverflow.com/questions/2837311

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è .:

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?

È stato utile?

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 il eta essere quasi uguale un po 'di valore elevato (vale a dire 0,2). Come il ciclo passa, abbassare il valore di eta in modo che quando si arriva quasi alla fine della collezione, il eta 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.

https://github.com/tdunning/t-digest

  1. 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
  2. È 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.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top