Qué algoritmo usar para segmentar una secuencia de números en n subconjuntos, para minimizar la desviación estándar de la suma de los números en cada subconjunto

Question

Estoy buscando un algoritmo para segmentar una secuencia de números positivos en n subsecuencias, tales que la desviación estándar de la suma de los números en cada subconjunto se minimiza.

El orden de los números en cada subsecuencia tiene que ser el mismo que el orden en la secuencia original

Por ejemplo:

Supongamos que tengo una secuencia {1,1,1,1,1 , 1,10,1} que quería segmentar en 2 subsecuencias.
Creo que la solución óptima sería {1,1,1,1,1,1}, {10,1}.

La suma de la primera subsecuencia es 6, la suma de la segunda subsecuencia es 11
La desviación estándar de los dos números es ~ 3.5, que creo que es la más baja posible.

Supongamos que tengo una secuencia {4,1,1,1,1,6} que quiero segmentar en 3 subsecuencias.
creo que la solución óptima sería {4}, {1,1,1,1}, {6}
La suma de las subsecuencias es 4, 4, y 6.
La desviación estándar de los 3 números es ~ 1.15, que creo que es el más bajo posible.

El mejor algoritmo que pude encontrar fue encontrar la suma acumulativa de cada uno de los números en la secuencia, y segmentar la secuencia en cada intervalo de [totalSum/numSubsequences].

Por ejemplo, dada la secuencia {4,1,1,1,1,6}, las sumas acumulativas de los números de cada secuencia son {4,5,6,7,8,14}. El total de todos los números en la secuencia es 14, así que, dado que quiero 3 subsecuencias, debería segmentar la secuencia cuando el total alcance 14/3 = 4.66 y 2 * 14/3 = 9.333333.

Sin embargo, no hay un lugar real en la secuencia donde el total acumulado es igual a 4.66 - el primer total acumulado es 4, y el siguiente total acumulado es 5. ¿Debería redondear o debería redondear? En este caso, redondeando a 4 da la solución óptima, pero ese no es siempre el caso. Lo mejor que puedo pensar es probar cada combinación de redondeo hacia arriba y hacia abajo, pero eso da como resultado la complejidad O (2^numSubsecuencias).

Este parece ser el tipo de cosa que tendría un algoritmo preexistente para aplicar, sin embargo, mi Google me ha fallado. Conozco el Partition Problem, que es NP-completo, pero que trata de conjuntos desordenados y secuencias no ordenadas.

Cualquier ayuda sería apreciada.

Answer 1

Supongamos que la longitud de la secuencia original es L y el número de subsecuencias es N.

Es posible que simplify the expression for standard deviation para obtener sqrt(E[X^2] - E[X]^2), donde E denota la expectativa/media y X denota la variable aleatoria - en su caso, la suma de las subsecuencias. (Se aplica una fórmula similar para la "desviación estándar de la muestra"). Tenga en cuenta que E[X] no depende de cómo divida su secuencia, porque siempre será la suma total dividida por N. Por lo tanto, solo queremos minimizar E[X^2] o equivalentemente, la suma de X^2 (se diferencian por un factor de N por la definición de promedio).

En este punto, podemos ver que este problema se puede resolver con programación dinámica.Deje f(i,j), por i0-M y j1-N, sea la suma mínima de cuadrados de sumas de subsecuencias de la división de los primeros i elementos de su secuencia en j subsecuencias. Entonces vemos que f(i,j) se puede calcular en términos de todos los f(i',j') con i' <= i y j < j'. Más específicamente, si su secuencia es a[k] indexado de 0 a M-1:

f(i,1) = sum(a[k] for 0 <= k < i)^2 
f(i,j) = minimum of f(l,j-1)+sum(a[k] for l < k < i)^2 for l from 0 to i 

Después de haber minimizado f(N,L), puede utilizar técnicas de programación dinámica estándar para recuperar las divisiones. En particular, puede almacenar el l que minimiza f(i,j).

El tiempo de ejecución de esta solución es O(L^2 N) debido a calcular O(L N) valores diferentes de f y la minimum es más O(L) valores diferentes de l.

Aquí hay una aplicación directa en Perl:

#!/usr/bin/perl 

use strict; 
use warnings; 

local $\ = $/; 
print join ", ", map {"@$_"} best(2, qw(1 1 1 1 1 1 10 1)); 
# prints "1 1 1 1 1 1, 10 1" 

print join ", ", map {"@$_"} best(3, qw(4 1 1 1 1 6)); 
# prints "4, 1 1 1 1, 6" 

sub best { 
    my($N, @a) = @_; 

    my(@f, @g, $i, $j, $k, $sum); 

    # DP base case 
    $sum = 0; 
    $f[0][1] = $g[0][1] = 0; 
    for $i (1 .. @a) { 
     $sum += $a[$i-1]; 
     $f[$i][1] = $sum * $sum; 
     $g[$i][1] = 0; 
    } 

    # DP recurrence 
    for $j (2 .. $N) { 
     $f[0][$j] = $g[0][$j] = 0; 
     for $i (1 .. @a) { 
      $sum = 0; 
      $f[$i][$j] = $f[$i][$j-1]; 
      $g[$i][$j] = $i; 
      for $k (reverse 0 .. $i-1) { 
       $sum += $a[$k]; 
       if($f[$i][$j] > $f[$k][$j-1] + $sum * $sum) { 
        $f[$i][$j] = $f[$k][$j-1] + $sum * $sum; 
        $g[$i][$j] = $k; 
       } 
      } 
     } 
    } 

    # Extract best expansion 
    my(@result); 
    $i = @a; $j = $N; 

    while($j) { 
     $k = $g[$i][$j]; 
     unshift @result, [@a[$k .. $i-1]]; 
     $i = $k; 
     $j--; 
    } 

    return @result; 
} 

Answer 2

Una idea que me viene a la mente es utilizar el algoritmo de búsqueda A *.

Más sobre eso:

http://en.wikipedia.org/wiki/A*_search_algorithm 

buen libro para leer sobre eso:

Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig 

Algunas cosas que usted podría utilizar para el A *:

• Estado inicial: dividir el secuencia en n subsecuencias (tanto como sea posible)
• Siguiente S tate: para cada subconjunto agregue el número izquierdo o derecho (el último número del subconjunto i-1 (si i! = 0) o el primer número del subconjunto i + 1 (si i! = n)) a él (para crear todo nodos descendentes del nodo de estado actual)
• Heurística: el valor óptimo sería la media de todos los valores. Es admisible por lo que se puede utilizar con A *.

No estoy seguro de que realmente te ayude con tu problema, ya que no he resuelto este problema nuevamente, pero creo que podría funcionar bastante bien. También puede no ser la solución más sofisticada para este problema específico, pero seguramente es mejor que cualquier enfoque de "probar todas las combinaciones". También es sólido y completo (debido a la heurística admisible).

Si tiene más preguntas al respecto, le haré todo lo posible para ayudarlo.

Answer 3

Creo que te refieres a dividir en trozos contiguos, o en otras palabras, encontrar n-1 lugares en los que cortar la secuencia en pedazos. (Si realmente quiere permitir subsecuencias que se entrelazan para crear la secuencia principal, probablemente pueda ordenar la secuencia, resolver el problema del fragmento y luego seguir de dónde provienen los números individuales para proporcionar subsecuencias intercaladas).

Creo que puede resolver esto en tiempo proporcional n veces la longitud de la secuencia mediante la programación dinámica. Trabaje de izquierda a derecha para completar las matrices de bestCost [i] [j] y lastCut [i] [j], donde me ejecuto a lo largo de la secuencia yj va de 0 a n-1. bestCost [i] [j] es el costo de la mejor forma de cortar la secuencia de 0 ai en j fragmentos. lastCut [i] [j] es la posición del corte más reciente para el corte que produce bestCost [i] [j]. bestCost [i + 1] [j] = min_k desviación estándar (i + 1 a k) + bestCost [k - 1] [j - 1]. y luego lastCut [i + 1] [j] = k. Al final, calcula el costo de la mejor respuesta para n cortes de la misma manera y luego usa lastCut [] [] para seguir el camino de regreso y encontrar los otros cortes.

Answer 4

Estoy de acuerdo que la programación dinámica puede ser la mejor alternativa - una técnica que iba a descartar es la optimización no lineal. Usted tiene una función objetivo no lineal ya sea que esté minimizando la raíz cuadrada o simplemente la suma de las diferencias al cuadrado. También tiene una variable entera como parte de su conjunto de restricciones: la asignación de miembros a conjuntos requiere algunas variables enteras, independientemente de su formulación. Una optimización no lineal con variables enteras generalmente es muy difícil, si no imposible, de resolver de manera óptima. Si solo necesita una solución aproximada, un algoritmo genético podría ser un buen enfoque donde la cadena genética es una representación de la asignación de un miembro a un conjunto.

En cuanto a hacer todo esto en menos de un segundo .... ¡Buena suerte!