¿Qué es una buena manera de medir la distancia entre subconjuntos finitos de los reales?

Question

Tengo algunos conjuntos de números, y me gustaría tener una manera de hablar acerca de cómo cerca de estos conjuntos son el uno al otro. No estoy seguro de qué características debería tener (por ejemplo, qué se necesita para ser una métrica?). Pero espero que existen ejemplos de mejor define este tipo de problemas con algunas buenas soluciones.

Algunas consideraciones. {1} debe estar más cerca de {1.1} que a {2}. Y {.9,1.1} debe estar más cerca de {1} de {0,2} es. Pero es {1,1.1} más {1} de {2}? Sospecho que cualquier función de distancia tendrá al menos un parámetro para controlar el equilibrio entre la cercanía de los puntos y la cardinalidad de los conjuntos.

Answer 1

Que $A$ sea un subconjunto finito de $\mathbb{R}$. $x\in\mathbb{R}$ Definir $d(x,A)$, la distancia de $x$ $A$, $$d(x,A) = \min\{\vert x-a\vert:a\in A\},$$ the distance from $x$ to the closest point of $A$. If $B$ is another finite subset of $\mathbb{R}$, define $d^* (A, B) $, the asymmetric distance from $A $ to $B $, to be $$d^*(A,B) = \max\{d(a,B):a\in A\}.$$ Finally, define $d(A,B) $, the distance between $%A $ and $B $, to be $% $ $d(A,B) = \max\{d^*(A,B),d^*(B,A)\}.$esto es la distancia de Hausdorff mencionado por deinst.

Algunos ejemplos: $$\begin{align*}d(\{0.9,1.1\},\{1\}) &= \max\{0.1,0.1\} = 0.1\\ d(\{0.9,1.1\},\{2\}) &= \max\{1.1,0.9\} = 1.1\\ d(\{1,1.1\},\{1\}) &= \max\{0.1,0\} = 0.1\\ d(\{1,1.1\},\{2\}) &= \max\{1,0.9\} = 1\\ d(\{0.9,1.1\},\{1.9,2.1\}) &= \max\{1,1\} = 1\\ d(\{0.9,1.1\},\{1.9,2.0,2.1\}) &= \max\{1,1\} = 1\\ d(\{1.9,2.0,2.1\},\{1.9,2.1\}) &= \max\{0.1,0\} = 0.1 \end{align*} $$

Answer 2

Hay varias distancias que se podrían considerar en principio. Dado que usted está considerando finito de conjuntos, tiene sentido para reducir a la métrica popular en verdaderos espacios vectoriales.

Deje $S$ $T$ finita de conjuntos de números reales. En el caso de que $S$ $T$ tienen la misma cardinalidad $n$, vamos a $\mathbf s, \mathbf t \in \mathbb R^n$ ser vectores cuyos coeficientes son los elementos de $S$$T$, respectivamente (en cualquier orden). Entonces, para cualquier entero positivo $p$ (y para $p = \infty$), se puede considerar que un $p$-la distancia definida por $$ \min_\Pi\; \| \Pi \mathbf s - \mathbf t \|_p$$ donde $\Pi$ rangos de todas las matrices de permutación en $\mathbb R^n$, y donde $$\| \mathbf v \|_p := \sqrt[\Big.^{\scriptstyle p}]{\sum_{j=1}^n |v_j|^p\;}$$ (taking the limit as $p \to \infty$ for the norm $\| \mathbf v \|_\infty$). If $S$ and $T$ have different cardinalities, you may vary this (in the case that $S$ is larger) by replacing $\Pi$ with an arbitrary matrix whose columns are distinct standard basis vectors (selecting some subset of $S$ a realizar el cálculo de la distancia).

Independientemente de las dimensiones, también se podría generalizar esto para considerar a una distancia de la forma $$ \min_{\Pi_S, \Pi_T}\; \bigl\| \Pi_{\!S} \;\mathbf s \;-\; \Pi_{\!T} \;\mathbf t \bigr\|_p$$ donde $\Pi_S$ $\Pi_T$ gama de más de matrices cuyas columnas son estándar vectores de la base, posiblemente con la repetición; esto permite calcular el vector de las métricas de uso arbitrario de los pares de elementos de $S$$T$.

Tenga en cuenta que como las cardinalidades de los conjuntos de crecer, estas cantidades son propensos a ser prohibitivo para calcular; pero los conjuntos de vectores que puedo describir el uso de estos permutación/selección de matrices se describen agradable conjuntos convexos, para que la costumbre vector métricas de hacer una cierta cantidad de sentido, y que puede ser susceptible de análisis. Y si en lugar de considerar el límite de $p \to -\infty$, usted debe encontrar el mínimo de par-distancia de la norma descrita por Brian en su post anterior.