c# - Algoritmo rápido para calcular percentiles para eliminar valores atípicos
c++ algorithm (10)
Tengo un programa que necesita computar repetidamente el percentil aproximado (orden estadístico) de un conjunto de datos para eliminar los valores atípicos antes de continuar con el procesamiento. Actualmente lo estoy haciendo ordenando la matriz de valores y seleccionando el elemento apropiado; esto es factible, pero es un problema notable en los perfiles a pesar de ser una parte bastante menor del programa.
Más información:
- El conjunto de datos contiene un orden de hasta 100000 números de punto flotante, y se supone que están "razonablemente" distribuidos; es poco probable que haya duplicados ni grandes picos en la densidad cerca de valores particulares; y si por alguna extraña razón la distribución es impar, está bien que una aproximación sea menos precisa, ya que los datos probablemente estén desordenados de todos modos y el procesamiento aún más dudoso. Sin embargo, los datos no están necesariamente distribuidos uniformemente o normalmente; es muy poco probable que sea degenerado.
- Una solución aproximada estaría bien, pero necesito entender cómo la aproximación introduce el error para garantizar que sea válida.
- Dado que el objetivo es eliminar los valores atípicos, estoy calculando dos percentiles sobre los mismos datos en todo momento: por ejemplo, uno al 95% y otro al 5%.
- La aplicación está en C # con bits de trabajo pesado en C ++; pseudocódigo o una biblioteca preexistente en cualquiera de los dos estaría bien.
- Una forma completamente diferente de eliminar los valores atípicos también estaría bien, siempre que sea razonable.
- Actualización: Parece que estoy buscando un algoritmo de selección aproximado.
Aunque todo esto se hace en un bucle, los datos son (ligeramente) diferentes cada vez, por lo que no es fácil reutilizar una estructura de datos como se hizo para esta pregunta .
Solución implementada
El uso del algoritmo de selección de wikipedia como lo sugiere Gronim redujo esta parte del tiempo de ejecución en aproximadamente un factor 20.
Como no pude encontrar una implementación de C #, esto es lo que se me ocurrió. Es más rápido incluso para entradas pequeñas que Array.Sort; y con 1000 elementos es 25 veces más rápido.
public static double QuickSelect(double[] list, int k) {
return QuickSelect(list, k, 0, list.Length);
}
public static double QuickSelect(double[] list, int k, int startI, int endI) {
while (true) {
// Assume startI <= k < endI
int pivotI = (startI + endI) / 2; //arbitrary, but good if sorted
int splitI = partition(list, startI, endI, pivotI);
if (k < splitI)
endI = splitI;
else if (k > splitI)
startI = splitI + 1;
else //if (k == splitI)
return list[k];
}
//when this returns, all elements of list[i] <= list[k] iif i <= k
}
static int partition(double[] list, int startI, int endI, int pivotI) {
double pivotValue = list[pivotI];
list[pivotI] = list[startI];
list[startI] = pivotValue;
int storeI = startI + 1;//no need to store @ pivot item, it''s good already.
//Invariant: startI < storeI <= endI
while (storeI < endI && list[storeI] <= pivotValue) ++storeI; //fast if sorted
//now storeI == endI || list[storeI] > pivotValue
//so elem @storeI is either irrelevant or too large.
for (int i = storeI + 1; i < endI; ++i)
if (list[i] <= pivotValue) {
list.swap_elems(i, storeI);
++storeI;
}
int newPivotI = storeI - 1;
list[startI] = list[newPivotI];
list[newPivotI] = pivotValue;
//now [startI, newPivotI] are <= to pivotValue && list[newPivotI] == pivotValue.
return newPivotI;
}
static void swap_elems(this double[] list, int i, int j) {
double tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
Gracias, Gronim, por señalarme en la dirección correcta!
Divida el intervalo entre el mínimo y el máximo de sus datos en (por ejemplo) 1000 contenedores y calcule un histograma. Luego construye sumas parciales y observa dónde primero exceden 5000 o 95000.
Hay un par de enfoques básicos que se me ocurren. Lo primero es calcular el rango (al encontrar los valores más altos y más bajos), proyectar cada elemento a un percentil ((x - min) / rango) y descartar cualquiera que se evalúe a un valor inferior a .05 o superior a .95.
El segundo es calcular la media y la desviación estándar. Un intervalo de 2 desviaciones estándar de la media (en ambas direcciones) encerrará el 95% de un espacio muestral normalmente distribuido, lo que significa que sus valores atípicos estarán en los percentiles <2.5 y> 97.5. El cálculo de la media de una serie es lineal, al igual que la dev estándar (raíz cuadrada de la suma de la diferencia de cada elemento y la media). Luego, reste 2 sigmas de la media, y agregue 2 sigmas a la media, y tendrá sus límites de valores atípicos.
Ambos de estos calcularán en un tiempo aproximadamente lineal; el primero requiere dos pases, el segundo toma tres (una vez que tiene sus límites, todavía tiene que descartar los valores atípicos). Como se trata de una operación basada en listas, no creo que encuentre nada con complejidad logarítmica o constante; cualquier ganancia adicional de rendimiento requeriría la optimización de la iteración y el cálculo, o la introducción de errores al realizar los cálculos en una submuestra (como cada tercer elemento).
La solución de histograma de Henrik funcionará. También puede usar un algoritmo de selección para encontrar de manera eficiente los k elementos más grandes o más pequeños en una matriz de n elementos en O (n). Para usar esto para el percentil 95, establezca k = 0.05n y encuentre los k elementos más grandes.
Referencia:
http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements
No soy un experto, pero mi memoria sugiere:
- para determinar los puntos de percentil exactamente lo que necesita para ordenar y contar
- tomar una muestra de los datos y calcular los valores de percentiles suena como un buen plan para una aproximación decente si puede obtener una buena muestra
- Si no, como lo sugiere Henrik, puedes evitar la clasificación completa si haces los cubos y los cuentas
Puede estimar sus percentiles a partir de solo una parte de su conjunto de datos, como los primeros miles de puntos.
El teorema de Glivenko-Cantelli asegura que esta sería una estimación bastante buena, si puede asumir que sus puntos de datos son independientes.
Puede filtrar 2 o 3 desviaciones estándar incluso si los datos no están distribuidos normalmente; Al menos, se hará de manera consistente, eso debería ser importante.
A medida que elimine los valores atípicos, el desarrollo estándar cambiará, puede hacer esto en un bucle hasta que el cambio en el desarrollo estándar sea mínimo. Si desea o no hacer esto depende de por qué manipula los datos de esta manera. Hay algunas reservas importantes de algunos estadísticos para eliminar los valores atípicos. Pero algunos eliminan los valores atípicos para demostrar que los datos se distribuyen de manera bastante normal.
Solía identificar valores atípicos calculando la desviación estándar . Todo lo que tiene una distancia más de 2 (o 3) veces la desviación estándar del promedio es un valor atípico. 2 veces = alrededor del 95%.
Ya que está calculando el promedio, también es muy fácil calcular la desviación estándar es muy rápido.
También puede usar solo un subconjunto de sus datos para calcular los números.
Un conjunto de datos de 100k elementos lleva casi nada de tiempo en ordenarse, por lo que asumo que debe hacerlo repetidamente. Si el conjunto de datos es el mismo que se acaba de actualizar, lo mejor es construir un árbol ( O(N log N) ) y luego eliminar y agregar nuevos puntos a medida que ingresan ( O(K log N) donde K es el número de puntos cambiados). De lo contrario, la solución de elemento más grande k ya mencionada le otorga O(N) para cada conjunto de datos.
Una buena respuesta general a su problema parece ser RANSAC . Dado un modelo y algunos datos ruidosos, el algoritmo recupera eficientemente los parámetros del modelo.
Tendrá que elegir un modelo simple que pueda mapear sus datos. Cualquier cosa suave debe estar bien. Digamos una mezcla de pocos gaussianos. RANSAC establecerá los parámetros de su modelo y estimará un conjunto de alineadores al mismo tiempo. Luego deseche lo que no le quede bien al modelo.