Mediana cruzada invertida de dos matrices

Question

El problema al que me enfrento es el siguiente : Dados dos arrays $A$ y $B,$ Me gustaría encontrar un umbral $t,$ satisfactorio: el número de elementos de $A$ que son inferiores a $t$ es igual al número de elementos de $B$ que son mayores que $t.$ Estoy bastante seguro de que la solución de mi problema es la mediana de alguna matriz formada por $A$ y $B,$ pero no veo exactamente cómo.

Para generalizar, buscamos un umbral que minimice la diferencia entre el número de $A$ y el número de $B$ de los elementos mayores.

Gracias de antemano por sus respuestas.

Answer 1

Pues bien, la mediana de las matrices concatenadas no es ciertamente la respuesta, como tampoco lo es la mediana de la unión de las matrices, aunque éstas tengan la misma longitud. El siguiente código sencillo de Python te desengañará de esa idea:

from random import randint
from statistics import median
import numpy as np

size_a = randint(10, 20)
a = [randint(0, 10) for __ in range(size_a)]
a.sort()

size_b = randint(10, 20)
b = [randint(0, 10) for __ in range(size_b)]
b.sort()

c = list(set(a + b))  // This is testing the union. For concat, eliminate
                      // the list and set calls and just do c = a + b.
c.sort()

print('a = ' + str(a))
print('b = ' + str(b))
print('median of c = a concat b is ' + str(median(c)))

a = np.array(a)  // Useful for conditional indexing.
b = np.array(b) 

print('Number of elements of a less than median: ')
print(str(len(a[a < median(c)])))

print('Number of elements of b greater than median: ')
print(str(len(b[b > median(c)])))

Sin embargo, creo que podemos tomar esta idea básica y ajustarla un poco para resolver tu problema. Idea: tomar las matrices concatenadas c = a + b y empezar con la mediana del resultado. Luego haz una comparación. Si el número de elementos de $a$ es mayor, vaya antes en $c$ . Si no, vete más tarde. Sin embargo, me gustaría señalar que no todas las opciones de $A$ y $B$ dará una solución. Por ejemplo: \begin{align*} A&=[0, 2, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 9, 9, 10] \\ B&=[0, 0, 1, 1, 1, 1, 2, 3, 3, 7, 8] \end{align*} no da una solución. Si se toma $0, 0.5, 1, 1.5, 2, 2.5,$ y $3$ a su vez, se verá que para ninguna de estas posibilidades el número de elementos de $A$ menos que el número igual al número de elementos de $B$ mayor que el número. Además, al recorrer la lista de números que acabo de dar, verás una inversión en los tamaños de las listas que satisfacen el criterio deseado. El siguiente código de Python encontrará un umbral, si existe, y un umbral óptimo que minimice la diferencia entre el número de elementos de $A$ menor que el umbral y el número de elementos de $B$ mayor que el umbral:

from random import randint
from statistics import median
import numpy as np

size_a = randint(10, 20)
a = [randint(0, 10) for __ in range(size_a)]
a.sort()

size_b = randint(10, 20)
b = [randint(0, 10) for __ in range(size_b)]
b.sort()

c = a + b
c.sort()

print('a = ' + str(a))
print('b = ' + str(b))
print('median of c = a concat b is ' + str(median(c)))

a = np.array(a)
b = np.array(b)
c = np.array(c)

t = median(c)
t_index = len(c[c < t])
iter_count = 0
diff = abs(len(a[a < t]) - len(b[b > t]))
best_t = t

while 0 < diff and iter_count < len(c):

    iter_count += 1

    if len(a[a < t]) > len(b[b > t]):
        t = np.mean(c[t_index-1:t_index+1])
        if len(a[a < t]) > len(b[b > t]):
            t_index -= 1
            t = c[t_index]
    else:
        t = np.mean(c[t_index:t_index+2])
        if len(a[a < t]) < len(b[b > t]):
            t_index += 1
            t = c[t_index]

    if abs(len(a[a < t]) - len(b[b > t])) < diff:
        diff = abs(len(a[a < t]) - len(b[b > t]))
        best_t = t

if 0 < diff:
    print('Could not find an exact threshold.')
    print('Optimal threshold was ' + str(best_t))
    print('Difference in set cardinalities was ' + str(diff))
else:
    print('Threshold is ' + str(best_t))

Answer 2

Jeje. Estoy añadiendo un montón de respuestas, pero creo que cada una de ellas tiene valor, y representa un enfoque diferente. Aquí hay un enfoque que utiliza una especie de función de distribución acumulativa para $A$ y una función de distribución "desacumulativa" para $B$ . La idea es encontrar el punto más pequeño de cualquiera de las matrices, el punto más grande de cualquiera de las matrices, construir una cuadrícula de valores de igual tamaño para los números de las matrices $A$ y $B$ , hacer una diferencia, y luego encontrar el mínimo del valor absoluto de la diferencia. Aquí está el código de Python:

from random import randint
import numpy as np

size_a = randint(10, 20)
a = [randint(0, 10) for __ in range(size_a)]
a.sort()

size_b = randint(10, 20)
b = [randint(0, 10) for __ in range(size_b)]
b.sort()

a = np.array(a)
b = np.array(b)

min_ab = np.floor(min([min(a), min(b)])) - 1
max_ab = np.ceil(max([max(a), max(b)])) + 1

print(str(a))
print(str(b))

print(str(min_ab))
print(str(max_ab))

grid = np.arange(min_ab, max_ab + 1, 1)
print(str(grid))

a_cdf = np.array([len(a[a < t]) for t in grid])
b_ddf = np.array([len(b[b > t]) for t in grid])

diff = np.abs(a_cdf - b_ddf)

print('The best value occurs at ' + str(np.min(diff)))
print('The best threshold is ' + str(np.where(diff == np.min(diff))))

print(str(a_cdf))
print(str(b_ddf))
print(str(diff))

Este código sólo utiliza bucles implícitos, como para encontrar el a_cdf y b_ddf variables. Ahora el inconveniente de este enfoque es que no necesariamente sabes si tu cuadrícula es lo suficientemente fina. En este momento, sólo lo tengo funcionando con números enteros. Puedes encontrar que si usas una rejilla lo suficientemente fina, puedes encontrar soluciones más fácilmente que no. Usted puede cambiar fácilmente la grosería de la rejilla cambiando el np.arange(min_ab, max_ab + 1, 1) llamada: hacer más pequeño el último argumento.

Answer 3

Esta respuesta parcial es pensar en el problema de forma más teórica. También es muy manual y no es una matemática rigurosa. Esto es una lluvia de ideas. Dejemos que \begin{align*} A_{<t}&:=\{a\in A:a<t\},\\ A_{=t}&:=\{a\in A:a=t\},\\ B_{<t}&:=\{b\in B:b<t\},\\ B_{>t}&:=\{b\in B:b>t\},\;\text{and}\\ B_{=t}&:=\{b\in B:b=t\}. \end{align*} Utilizamos la notación $|C|$ para denotar la cardinalidad del conjunto $C.$ Tenga en cuenta que $|B_{>t}|=|B|-|B_{<t}|-|B_{=t}|,$ asumiendo que nada de lo que se ve es infinito. Nuestro objetivo es encontrar el $t$ que minimiza $\big| |A_{<t}|-|B_{>t}| \big|,$ o $$\min_{t}\sqrt{(|A_{<t}|-(|B|-|B_{<t}|-|B_{=t}|))^2}. $$ Pero el $t$ que minimiza esta expresión también minimiza sin la raíz cuadrada: $$\min_{t}\,(|A_{<t}|+|B_{<t}|+|B_{=t}|-|B|)^2. $$ Supongamos que podemos diferenciar esta expresión con respecto a $t$ de la siguiente manera: \begin{align*} \frac{d}{dt}\,(|A_{<t}|+|B_{<t}|+|B_{=t}|-|B|)^2&=2(|A_{<t}|+|B_{<t}|+|B_{=t}|-|B|)\,\frac{d}{dt}\,\left(|A_{<t}|+|B_{<t}|+|B_{=t}|-|B|\right). \end{align*} Aquí es donde nos ayudan las estadísticas. Podemos interpretar ambos $|A_{<t}|$ y $|B_{<t}|$ como distribuciones de probabilidad acumulada (no normalizadas). Sabemos que la "derivada" de una distribución de probabilidad acumulada es una función de densidad de probabilidad (se puede pensar en ella como una función de recuento). Así que podemos simplificar la derivada lejana de la siguiente manera: $$\frac{d}{dt}\,\left(|A_{<t}|+|B_{<t}|+|B_{=t}|-|B|\right)=|A_{=t}|+|B_{=t}|+\frac{d}{dt}\,|B_{=t}|. $$ Los dos primeros términos aquí son no negativos, por lo que la única manera de que esta expresión sea cero es que $$\frac{d}{dt}\,|B_{=t}|<0. $$ Así que la función de densidad de probabilidad $|B_{=t}|$ tendría que ser decreciente. O eso, o la solución óptima de $|A_{<t}|+|B_{<t}|+|B_{=t}|-|B|=0,$ que sería claramente el mínimo global.