El Problema del Árbol Generador Central

Los árboles generadores son un primitive importante en muchas tareas de análisis de datos, cuando un conjunto de datos necesita ser resumido en términos de su "esqueleto", o cuando se requiere un grafo en forma de árbol sobre todas las observaciones para el procesamiento posterior. Las definiciones populares de árboles generadores incluyen el árbol generador mínimo y el árbol generador de distancia óptima, también conocido como el árbol de costo de enrutamiento mínimo. Al buscar el árbol generador más corto pero admitiendo puntos de ramificación adicionales, se pueden realizar árboles generadores aún más cortos: árboles de Steiner. Desafortunadamente, tanto los árboles generadores mínimos como los árboles de Steiner no son robustos frente al ruido en las observaciones; es decir, pequeñas perturbaciones del conjunto de datos original a menudo conducen a cambios drásticos en los árboles generadores asociados. En respuesta, hacemos dos contribuciones cuando los datos se encuentran en un espacio euclidiano: en el lado teórico, presentamos un nuevo problema de optimización, el "árbol generador central (ramificado)", que subsume todas las definiciones mencionadas anteriormente como casos especiales. En el lado práctico, mostramos empíricamente que el árbol generador central (ramificado) es más robusto al ruido en los datos, y como tal es más adecuado para resumir un conjunto de datos en términos de su esqueleto. También proponemos una heurística para abordar el problema de optimización NP-difícil y ilustramos su uso en datos de expresión de ARN de células individuales de biología y nubes de puntos 3D de plantas.