Maximizar la diferencia entre la media y la mediana

Question

Tengo un conjunto de números y quiero maximizar la diferencia entre la media y la mediana mediante la eliminación de un número dado de elementos.

Por ejemplo tengo el siguiente conjunto:

0 5 10 45
Mean = 15
Median = 7.5
Mean - Median = 7.5

Si decidimos quitar 1 elemento quiero obtener la siguiente

0 5 45
Mean = 16.66
Median = 5
Mean - Median = 11.66 => MAXIMISED

Podemos suponer que el conjunto se ordena.

Existe un algoritmo para hacer esto?

Answer 1

Esto NO es una respuesta completa, pero trato de esbozar mi idea.

Supongamos que tenemos un conjunto ordenado, digamos, en un orden creciente. Si queremos maximizar la diferencia entre la media y la mediana, es necesario (pero no suficiente) para mantener a los valores atípicos como sea posible (porque significa que está muy afectado por estos valores atípicos, mientras que la mediana no es). Los problemas aquí son: ¿cuántos es "muchos"? y cómo controlar la diferencia?

Supongamos $x_1 < x_2 < ... < x_n$. Podemos calcular su media y la mediana. Mi alogorithm (que todavía no he podido probar hasta ahora) es la siguiente:

1. Si la media de $>$ meadian: eliminar la mediana o el número más próximo que es más GRANDE que la mediana, que es $x_{(n+1)/2}$ si $n $ es impar o $x_{n/2+1}$ si $n$ es incluso. El efecto de hacer esto es: después de cada paso, la media (no siempre) se hace más grande y más grande, pero la mediana (no siempre) se hace más pequeño y más pequeño (y por supuesto, siempre es más grande que la mediana en cada paso). Pero en general, la diferencia se hace más grande.
2. Si la media de $<$ mediana: eliminar la mediana o el número más próximo que es MENOR que la mediana, que es $x_{(n+1)/2}$ si $n $ es impar o $x_{n/2-1}$ si $n$ es incluso. El efecto de hacer esto es: después de cada paso, la media (no siempre) se hace más pequeño y más pequeño, pero la mediana (no siempre) se hace más grande y más grande (y por supuesto, siempre es menor que la mediana en cada paso). Pero en general, la diferencia se hace más grande.

Resulta que, finalmente, sólo deberemos $3$ números de la izquierda (no puede ser $2$, de lo contrario la media de $=$ de la mediana): el más grande, el más pequeño, y el segundo más pequeño (si la media de $>$ de la mediana) o el segundo más grande (si la media de $<$ de la mediana). Estos $3$ números tendrán la diferencia máxima entre la media y la mediana.

Answer 2

Una sugerencia de cómo de rápido calcular es que usted puede precompute la suma de todos los $N$ números, digamos que es $S$, entonces el valor de la media después de la eliminación de los valores de $x_1,\cdots, x_k$ sería $$\frac{1}{N-k}\left({S - \sum_{1}^k x_i}\right)$$ if you want to remove only a small part of the elements, then computing the above will be faster than re-computing the whole sum each time for each new subset of $x_i$. So if we have $N = 100$ elements and remove $k = 3$ for each configuration of $x_i$, sólo tenemos que hacer 3 sustracciones en lugar de 97 adiciones.

---

Para el índice de la mediana, se puede hacer un enfoque iterativo. Primero se calcula la mediana de la primera. Luego tomamos el índice del primer número de quitar, si el índice de la cantidad a eliminar es menor que el índice del promedio actual, entonces el índice para el nuevo mediana aumenta por $1/2$ (¿por qué? y si es de mayor tamaño es reducido por $1/2$. Si es el mismo entonces no hay cambio. Entonces necesitamos un manejo especial para comprobar que el índice final no accidentalmente ser el mismo como uno de los eliminados los números. Si estamos en el procesamiento de la señal, se puede hacer esto con algún tipo de filtrado adaptativo, por ejemplo local normalizado promedio en el que mostramos la certeza de cualquier elemento eliminado a 0 y para los que no se quitan a 1.