Trazado de gráfico de dispersión con frente no dominado en R

Question

Tengo un conjunto de datos con dos objetivos (tiempo de ejecución y calidad de la solución). ¿Hay alguna manera de dibujar un gráfico de dispersión en R que también dibuje un frente no dominado de los dos objetivos?

Answer 1

Es de suponer que el "tiempo de ejecución" es mejor cuando es bajo y la "calidad de la solución" es mejor cuando es alto. Para que estas variables sean más coherentes en la forma de representar los atributos, primero hay que reexpresarlas de forma que los números altos correspondan siempre a valores mejores. Para esta pregunta, el recíproco del tiempo de ejecución (que podría interpretarse como número de ejecuciones por segundo) sería una buena opción, pero el negativo del tiempo de ejecución también funcionaría bien.

Una vez establecida esta convención, podemos representar cada registro del conjunto de datos asociando el valor de "tiempo de ejecución" reexpresado con la coordenada x y el valor de "calidad de la solución" con la coordenada y, creando un gráfico de dispersión. Un registro $(x,y)$ domina otro $(x',y')$ cuando simultáneamente $x\ge x'$ , $y\ge y'$ y $(x,y) \ne (x',y')$ . Ningún actor racional (que utilice únicamente información sobre el "tiempo de ejecución" y la "calidad de la solución") elegiría la opción dominada $(x',y')$ cuando $(x,y)$ --que sea al menos tan bueno en ambos atributos y mejor en al menos uno-- está disponible. Por lo tanto, dicho actor centraría su interés en el no dominado opciones y sería libre de descuidar todas las demás.

Todos los puntos dominados por el punto rojo sólido se muestran en gris. Todos los posibles puntos que puede dominar constituyen el rectángulo (cerrado) mostrado en rosa. Como evidentemente ningún punto del diagrama de dispersión domina al punto sólido, éste debe encontrarse en la frontera no dominada.

El conjunto de opciones no dominadas forma los vértices de una parte del "casco cuasi-convexo" o "frontera no dominada" del gráfico de dispersión. Se trata de un análogo del más conocido casco convexo. De hecho, el casco cuasi-convexo será invariable bajo todas las reexpresiones monótonas crecientes de las variables, $f(x)$ y $g(y)$ y siempre se pueden encontrar tales reexpresiones para las que el casco cuasi-convexo se convierte realmente en el casco convexo. Esta conexión, y el hecho de que la construcción óptima del casco convexo de $n$ puntos requiere $O(n\log(n))$ El cálculo de la misma, sugiere que busquemos un algoritmo para el casco cuasi-convexo que funcione al menos igual de bien. Tales algoritmos existen. Aquí tenemos uno, dado en R según lo solicitado, que está escrito para portarse fácilmente a otras plataformas informáticas:

hull.qc <- function(xy) {
  i <- order(xy[, 1], xy[, 2], decreasing=TRUE)
  frontier <- rep(0, length(i))
  k <- 0; y <- -Inf
  for (j in i) {
    if (xy[j, 2] > y) {
      frontier[k <- k+1] <- j
      y <- xy[j, 2]
    }
  }
  return(frontier[1:k])
}

Realiza una ordenación lexicográfica decreciente de las coordenadas (tiempo: $O(n\log(n))$ ) y luego recorre la primera coordenada (tiempo: $O(n)$ ), poniendo en marcha un algoritmo de exploración de líneas. Se registran los puntos donde se encuentra un nuevo valor mayor de la segunda coordenada. Sus índices dentro de la matriz de entrada xy se devuelven.

Podemos demostrar que este algoritmo es correcto por inducción. El punto inicial, elegido para tener una primera coordenada máxima y (entre tales puntos) una segunda coordenada máxima, obviamente no está dominado. A partir de él podemos eliminar todos los demás puntos que sí domina, incluido él mismo. El primer punto no eliminado que se encuentra a continuación en el algoritmo tiene necesariamente un valor mayor de su segunda coordenada. Evidentemente, no está dominado por ningún punto, porque si lo estuviera, ya se habría encontrado ese otro punto. Por lo tanto, el algoritmo selecciona efectivamente los puntos no dominados y (por inducción sobre el número de puntos) los encuentra todos, QED.

Para ilustrar estos conceptos y este algoritmo, aquí está el gráfico de un conjunto de datos de $16$ K registros (todos con valores integrales, mostrados jittered) junto con su casco cuasi-convexo (una línea oscura en la parte superior derecha), sus vértices marcados como se pide en la pregunta, y los "rectángulos de dominancia" de esos vértices coloreados.

El código para hacer los cálculos, hacer un gráfico de dispersión y marcar los vértices de su casco cuasi-convexo aparece a continuación. Incluye una versión ligeramente más rápida R -versión centrada en hull.qc . Procesa un millón de puntos en aproximadamente dos segundos en esta máquina.

#
# A faster solution (for R).
#
hull.qc <- function(xy) {
  i <- order(xy[, 1], xy[, 2], decreasing=TRUE)
  y <- xy[i, 2]
  frontier <- which(cummax(y) <= y)
  #
  # Eliminate interior points along edges of the hull.
  #
  y.0 <- y[frontier]
  frontier <- frontier[c(TRUE, y.0[-1] != y.0[-length(y.0)])]
  return(i[frontier])
}
#
# Generate data.
#
library(MASS)
set.seed(17)
n <- 2^14
xy <- floor(mvrnorm(n, c(1,1), matrix(c(1, -1/2, -1/2, 1), 2))^2)
#
# Do the work.
#
system.time(frontier <- hull.qc(xy))
xy.f <- xy[frontier, , drop=FALSE]
#
# Visualization.
#
plot(xy, xlab="X", ylab="Y", main="Quasiconvex Hull")
points(xy.f, pch=19, col="Red")