Generalization of the Rødseth's algorithm for the Diophantine Frobenius Problem with n=3

Given a set (a₁, a₂..., a_n) of positive integers (a_i >= 1), the Frobenius Problem looks for the largest number g that cannot be represented by the equation g = a₁·x₁ + a₂·x₂ +... + a_n·x_n, with x_i integers >= 0. g is called the Frobenius number of the set. [1]

This problem is also known as the Coin Problem, where is asked the largest monetary amount that cannot be obtained using only coins of specified denominations.

The Frobenius Problem has applications in diverse areas as sort methods analysis, Petri Nets, tilings, random vectors generation, etc. [1]

A particular case is known as the Mc Nuggets Problem: which is the largest number that cannot be obtained as the sum of pieces in an order of any number of McDonald's Chicken McNuggets boxes, which originally came in quantities of 6, 9 and 20? [2]

If the greatest common divisor of the set is grater than 1, the Frobenius number of the set is undefined. [3]

If n = 2, g(a₁, a₂) = a₁·a₂ - a₁ - a₂. [4]

The general problem with n variable is NP-hard under Turing reductions. [1] That's why there is a variety of algorithms and formulae that try to avoid the brute force approach.

For n = 3 and a₁, a₂, a₃ pairwise coprime integers (greatest common divisor = 1) there is an algorithm by Ø. J. Rødseth than works well on average (probably O(log a₂)), even if in the worst case can take O(a₁ + log a₂) operations. [1]

This algorithm is explained in a few places [1][5] but I couldn't find an implementation in code and I ran into troubles trying to apply proposed generalization when the numbers in the set are not pairwise coprime integers, so I want to share my implementation in Rust.

In this implementation let's define g(A) = -1 when any a_i = 1 (which makes sense since a_i = 1 is all you need to represent any positive integer and 0 can always be represented, so -1 is the largest integer that cannot be obtained), and use this generalization:

d12 = gcd(a₁, a₂);
d13 = gcd(a₁ / d12, a₃);
d23 = gcd(a₂ / d12, a₃ / d13);
a' = (a₁ / d12 / d13, a₂ / d12 / d23, a₃ / d13 / d23)
r = Rødseth algorithm applied to a'
g(a₁, a₂, a₃) = r * d12 * d13 * d23 + a₁ * (d23 - 1) + a₂ * (d13 - 1) + a₃ * (d12 - 1)

This works with any set of positive integers that have a defined Frobenius number (i.e. gcd(a₁, a₂, a₃) = 1).

Examples:
a = (12, 14, 17)
a'= (6, 7, 17)
d12 = 2, d13 = 1, d23 = 1
r = 22
g = 22 * 2 + 12 * 0 + 14 * 0 + 17 * 1 = 61

a = (12, 13, 34)
a'= (6, 13, 17)
d12 = 1, d13 = 2, d23 = 1
r = 33
g = 33 * 2 + 12 * 0 + 13 * 1 + 34 * 0 = 79

a = (5, 9, 21)
a'= (3, 5, 7)
d12 = 1, d13 = 1, d23 = 3
r = 4
g = 4 * 3 + 5 * 2 + 9 * 0 + 21 * 0 = 22

a = (6, 9, 20)
a'= (1, 3, 10)
d12 = 3, d13 = 2, d23 = 1
r = -1
g = -1 * 6 + 6 * 0 + 9 * 1 + 20 * 2 = 43

a = (582795988, 1753241221, 6814151015)
a'= (582795988, 1753241221, 6814151015)
d12 = 1, d13 = 1, d23 = 1
r = 173685179295403
g = 173685179295403 * 1 + 582795988 * 0 + 1753241221 * 0 + 6814151015 * 0 = 173685179295403

a = (4, 16, 30)
g = undefined (gcd(a) = 2)

a = (12, 12, 13)
a'= (1, 1, 13)
d12 = 12, d13 = 1, d23 = 1
r = -1
g = -1 * 12 + 12 * 0 + 12 * 0 + 13 * 11 = 131

a = (1, 6, 15)
a'= (1, 2, 5)
d12 = 1, d13 = 1, d23 = 3
r = -1
g = -1 * 3 + 1 * 2 + 6 * 0 + 15 * 0 = -1


Working code:

Rust playground


[1] https://global.oup.com/academic/product/the-diophantine-frobenius-problem-9780198568209
[2] https://en.wikipedia.org/wiki/Coin_problem#McNugget_numbers
[3] https://en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics
[4] https://www.jstor.org/stable/2369536
[5] http://people.reed.edu/~iswanson/LepilovORourkeSwanson.pdf

Map-Time Surfer

Participé en la competencia IEEE VAST Challenge 2011, en el mini-challenge 1 que se trataba de caracterizar un brote epidémico (tipo H1N1) en una ciudad ficticia (Vastopolis) a partir de 1.023.000 mensajes de texto con ID, latitud, longitud, fecha y hora.

La competencia era tanto de data mining (aplicar los algoritmos que sean necesarios para obtener la información para caracterizar la enfermedad a partir de esa parva de mensajes) como de visualización (ganar conocimiento de la enfermedad a partir de ver los datos de una forma efectiva).

Hice un programa en Processing para visualizar estos datos en el mapa, y lo presenté a la competencia con un video. Mi inglés es vergonzoso, pero aquí está:

Y este es el programita presentado (si los dioses de los permisos, los sistemas operativos, los navegadores y las máquinas virtuales quieren):



Hacer clic y arrastrar para apreciar la perspectiva 3D. Hacer zoom con la ruedita del mouse o las flechas arriba/abajo.

Cabe un agradecimiento para Lucila Santos (compañera de la materia de Visualización), que encontró el evento del accidente del camión, identificado como el disparador de la enfermedad. Sin ese dato todavía estaría tirándome los pelos en búsqueda de este origen.

Sé que el programa no está muy pulido, demora en cargar, tuve que sacar las imágenes de los puntos negros de los primeros 16 días (que igual no aportan nada) porque me quedaba sin memoria, y le toma un siglo en pasar a la pantalla de trayectorias (aunque solo la primera vez), pero como prueba de concepto me deja muy contento. :)

Treemap con intervalos de confianza

Esta es una idea generada a partir de un trabajo práctico de la materia Visualización de Información de la maestría en Data Mining que estoy cursando. El trabajo práctico pedía implementar un treemap.

Un treemap es una forma de mostrar información jerárquica usando rectángulos que ocupan el total del espacio de forma proporcional al valor de una variable.

La vuelta de tuerca que le di es mostrar la variabilidad de los datos a través de la animación, mostrando la media y los límites superiores e inferiores de un intervalo de confianza de forma alternada, en base a un nivel de confianza que se puede establecer interactivamente.

Los datos del ejemplo

Elegí mostrar 17.486 manos de póquer jugadas entre 29/10/2009 y 12/04/2011 en mesas on line de 6 jugadores, modalidad Texas Hold’em No Limit, apuestas entre u$s0,05/0,10 y u$s0,10/0,25. Las manos quedaron registradas en la base de datos del programa Holdem Manager, que permite realizar análisis y seguimiento del juego.

En la modalidad Texas Hold’em se reparten dos cartas a cada jugador, que luego se combinan con 5 cartas comunitarias. Hay cuatro rondas de apuestas.

En mesas de 6 jugadores las posiciones son las siguientes:

• SB (Small blind, ciega pequeña): Apuesta de forma obligada la mitad de la apuesta mínima antes de ver sus cartas.


• BB (Big blind, ciega grande): Apuesta de forma obligada la apuesta mínima antes de ver sus cartas.


• EA (Early position, posición temprana): El primero luego de las ciegas. Jugar primero es una desventaja.


• MD (Medium position, posición media): El siguiente a la posición temprana.


• CO (Cutoff, posición de corte): El anteúltimo.


• BTN (Button, botón que indica quien reparte): Es el último en actuar, lo que supone una ventaja.

Las cartas se pueden agrupar en las siguientes categorías (tomadas del Holdem Manager):

• As y carta alta (As y K o As y Q)


• As y distinto palo


• As y mismo palo (cuando las dos cartas son del mismo palo se indica con una s (suited), por ejemplo A9s)


• Conectores distinto palo (los conectores son dos cartas seguidas, por ejemplo 98 o T9 (T indica el diez (ten)))


• Conectores mismo palo


• Un hueco y distinto palo (un hueco es cuando falta una carta en el medio, por ejemplo KJ o 42)


• Un hueco y mismo palo


• Dos huecos y distinto palo (cuando faltan dos cartas en el medio, por ejemplo KT o 52)


• Dos huecos y mismo palo


• Par de ases


• Par alto (KK, QQ o JJ)


• Par medio (TT, 99, 88 o 77)


• Par bajo (66, 55, 44, 33 o 22)


• Mismo palo (otras)


• Distinto palo (otras)

El jugador decide si jugar la mano o no principalmente en base a la posición y a las cartas que recibe. Si la posición es una de las ciegas y decide no jugar, pierde la apuesta obligada, por lo que en general estas posiciones tienen una expectativa perdedora.

Entonces resulta interesante analizar con qué categoría de cartas se jugó en cada posición y cuál fue el resultado. Quizás se pueda establecer si se está teniendo una estrategia equivocada con alguna categoría de manos o con algunas manos en particular.


La visualización

Los datos se muestran en rectángulos por categorías de manos, y se puede hacer zoom con clic izquierdo para ver la posición (SB, BB, EA, etc.) dentro de cada categoría, y luego para ver las manos en particular dentro de cada posición. Se puede volver a un nivel superior haciendo clic derecho.

El color de los rectángulos indica si esa agrupación de manos dio una ganancia positiva (verde) o negativa (rojo). El brillo también muestra la magnitud de la ganancia o pérdida. Colores oscuros indican manos en las que el resultado fue cercano a cero. Nótese que habiendo hecho zoom a una agrupación en particular, un recuadro puede ocupar un espacio grande pero tener un color oscuro, lo que indica que si bien dentro de la agrupación ese subconjunto es importante, no lo es a nivel general.

El intervalo de confianza muestra cuáles son las ganancias o pérdidas mínimas y máximas en base a los datos registrados, a un nivel de confianza determinado. Los recuadros se agrandan y achican en base a estos valores, y pueden cambiar de color si pasan de ganancia a pérdida o viceversa. A medida que se requiere un nivel de confianza superior, los intervalos se agrandan y la animación se precipita. Cuando se requiere un nivel de confianza inferior los intervalos se achican y la variabilidad se atenúa.

Los intervalos de confianza se calculan en base a la distribución t:

y ± t(α/2,W−1) * SE

donde y es la media aritmética,
α es el nivel de error (1-nivel de confianza)
W es el tamaño de la muestra
SE es el error estándar


Resultados del análisis

En base a la visualización, puede verse que para establecer intervalos de confianza pequeños se debe bajar mucho el nivel de confianza solicitado. Esto es esperable ya que se trata de un juego con alta incidencia del azar.

De todas maneras se pueden sacar algunas conclusiones interesantes:

• Primero notemos que los pares de ases son claramente ganadores, y que para cualquier mano jugar en BTN y en CO da mejores resultados que jugar en BB y SB, conocimiento básico de cualquier jugador.


• Pero me resulta inesperado lo notablemente redituables que se muestran los conectores de distinto palo.


• Y como alerta se destaca la importante pérdida que he tenido con As y carta alta. Debo jugar de manera más conservadora estas manos.

Las herramientas

Se utilizó el lenguaje Processing (processing.org) y la implementación de treemaps que aparece en el capítulo 7 de Visualizing Data (Ben Fry, 2008).

Para establecer los intervalos de confianza se utilizó la biblioteca statdistlib (sourceforge.net/projects/statdistlib/) de Dr. Peter N. Steinmetz y Gregory Warnes.

Los resultados se verificaron con SPSS Statistics 17.0.

¡Aparecí en KDnuggets News!

KDnuggets News es la newsletter (en inglés) dedicada a Data Mining y Knowledge Discovery más reconocida de la actualidad. Trae noticias acerca de eventos, softwares, publicaciones, cursos, ofertas de trabajo, etc. Y también suele incluir alguna cosita humorística o juguetona.

En su último número incluye como destacada una novela (un thriller) de mi autoría. Se trataba de crear una historia relacionada con data mining en seis palabras. Aquí la reproduzco, en su versión completa:

Only six words? Get more data! (¿Sólo seis palabras? ¡Consigan más datos!)

:D

Detección anticipada del brote de gripe porcina mediante data mining

La empresa Veratect con sede en Washington, afirma haber detectado el brote de influeza A H1N1 ("gripe porcina" para los amigos) 18 días antes de que la Organización Mundial de la Salud lo hiciera público el 24 de abril pasado, gracias a técnicas de data mining.

Por lo que dicen sus comunicados de prensa, la empresa monitorea más de 40.000 fuentes de información (como Eurosurveillance o el sitio de la OMS) en busca de amenazas a la salud o al medio ambiente, las integra, y entrega a sus suscriptos (empresas multinacionales u organizaciones de salud) los resultados que le son pertinentes, en cómodos mapitas.

Las actualizaciones respecto a la gripe pueden verse en forma gratuita en su canal de tweeter. Sin embargo buscando en la historia de ese mismo canal, no se encuentra nada relativo a este brote antes del 24/04: http://search.twitter.com/search?q=+from:Veratect+until:2009-04-23.

Quizás sea una noticia agrandada un poco por la empresa misma con el objetivo de obtener publicidad y clientes; quizás avisaron con antelación a las autoridades que correspondía avisar, pero también venían avisando de muchos otros brotes menos importantes con lo que habían perdido credibilidad. Pero de todas maneras me gusta la idea de la aplicación de Data Mining para encontrar anomalías, situaciones críticas que pueden afectar a empresas o gobiernos, a partir de datos públicos no estructurados. El modelo subyacente debe ser capaz de separar lo importante de lo intrascendente, y lo verificado de los meros rumores.

Enlaces:

- Nota de prensa de la empresa (pdf en inglés)

- Noticia en The Houston Chronicle

- Noticia en e-consulta (diario mexicano)

- Noticia en CEJournal (en inglés)

¿Qué es Data Mining?

Creo que la trillada explicación “es la extracción de información previamente desconocida, de grandes volúmenes de datos” sólo tiene sentido para aquellos que ya saben qué es. Para quien no lo sabe, son palabras conocidas pero que juntas no le evocan ninguna imagen o experiencia que le sea familiar, es decir, no se entiende.

Así que estando en los comienzos de este blog, me parece oportuno lanzarme a la difícil tarea de definir su objeto principal, a mi propio y subjetivo modo, buscando ser abarcativo pero sencillo, y lo menos técnico posible. Aquí vamos:

¿Qué es Data Mining?

• "Data Mining" (Minería de Datos) se refiere a un conjunto de técnicas de base estadística y algorítmica (algoritmo = procedimiento computarizable)
  
• organizado con un método
  
• que permite analizar montañas de datos
• buscando relaciones sutiles (no evidentes) existentes en estos datos
  
• En base a estas relaciones se construyen modelos
  
• En base a los modelos se pueden tomar mejores decisiones
  

¿Qué es un modelo?

• Un modelo es una representación simplificada de la realidad, que sin embargo mantiene lo que es “importante”
  
• En base a cómo funciona el modelo, se pueden inferir aspectos del funcionamiento de la realidad, que siempre es mucho más compleja

¿Cuáles son los tipos de modelos más importantes en Data Mining?

• Modelos Explicativos
  
• --- Permiten encontrar qué factores influyen en un resultado
  
• --- Permite agrupar resultados similares
  
• Modelos Predictivos
  
• --- En base a los patrones de comportamiento previo, permite identificar cuál es el comportamiento futuro más probable
  
• --- En base a una clasificación realizada sobre un conjunto de casos conocidos, permite asignarle una clase a un caso nuevo
  

¿Qué aplicaciones concretas tiene Data Mining? Ejemplos:

• Market basket analysis: ¿qué productos se venden juntos?
  
• Modelo de fuga (churn o attrition): ¿qué clientes están por abandonar un servicio?
  
• Segmentación: ¿cuáles son los clientes que se comportan de manera similar? ¿qué prospectos se asemejan a los que son más valiosos para el negocio?
• ¿Cuáles son los factores que más influyen en un proceso? (de producción, logística, ventas, etc.)
  
• Detección de fraudes
  
• Personalización de publicidad en Internet
  
• Predicción de fallas de maquinaria
  
• Predicción de la demanda
  
• Predicción del flujo de caja
  
• Reconocimiento de imágenes
  
• Evaluación de riesgos crediticios
  
• Detección de spam
  
• Estudios genéticos
  
• Catalogación de cuerpos celestes en astronomía
  
• Análisis de documentos no estructurados (text mining y web mining)
  
• Etc., etc., etc…
  

Limitaciones

• No pueden analizarse datos que no se tienen
  
• --- Un posible resultado de un proyecto de DM es la determinación de los datos que deben empezar a recolectarse
  
• Si los datos son erróneos, las predicciones también lo serán
  
• --- Aunque las técnicas son bastante resistentes a una cierta cantidad de “ruido”
  

¿Qué NO es Data Mining?

• Recolección de información personal
• --- Muchas veces se le dice Data Mining a la actividad de los servicios de inteligencia (de gobiernos o empresas). Estas organizaciones probablemente usen Data Mining, pero la etapa recolección de información sin el consentimiento de sus dueños no involucra modelos ni técnicas estadísticas o algorítmicas, por lo que lo dejaría fuera de mi definición.
• Recolección de mails de páginas web
• --- En los sitios de ofertas de trabajo habitualmente surgen requerimientos de programas que recorran un sitio web extrayendo los mails (o los detalles de los productos de un catálogo, o cosa similar). Los llaman "trabajos de Data Mining", pero tampoco tiene nada que ver con lo que estamos tratando. (Tiene un nombre más preciso: web scraping)

¿Se entendió? :)  Ahora para satisfacer al lector más avanzado, dos apartaditos más técnicos:

¿Cuáles son las técnicas más importantes que se usan en Data Mining? Ordenadas por uso (de mayor a menor) según reporte de 2008 de Rexer Analytics:

• Regresiones (lineal, logística, etc.)
  
• Árboles de Decisión
  
• Análisis de conglomerados (cluster analysis)
  
• Series de tiempo
  
• Redes Neuronales
  
• Reglas de asociación
  
• Análisis factorial
  
• Máquinas de soporte vectorial (Support Vector Machines, SVMs)
  
• Redes Bayesianas
  
• Análisis de supervivencia (link a artículo en inglés)
  
• Reglas de inducción (link a artículo en inglés)
  
• Análisis de redes sociales
  
• Algoritmos genéticos
  
• Group Method of Data Handling (GMDH) (link a artículo en inglés)
  

¿Cuáles son los softwares más importantes que se usan en Data Mining? Ordenados por uso (de mayor a menor) según el mismo reporte:

• SPSS Clementine
  
• SAS
  
• Statistica (Statsoft)
  
• SAS Enterprise Miner
  
• SPSS
  
• Rapid Miner
  
• R
  
• Microsoft SQL Server
  
• KXEN
  
• Matlab
  
• Weka

Amor por los árboles (de decisión)

zyxo en su interesante blog Mixotricha, escribió un muy buen artículo relativo a las ventajas de los árboles de decisión y el control del overfitting (sobreentrenamiento), del cual me tomé la libertad de traducir y parafrasear las partes que me parecieron más interesantes:

Desventajas de los árboles de decisión:

- Overfitting (¡pero se puede controlar y usar para mejorar la calidad del modelo!)

Ventajas:

- Legibilidad del resultado: Simples sentencias IF THEN

- Algoritmo simple

- Robustez: El preprocesamiento y la limpieza de datos son un trabajo engorroso, ¡¡pero los árboles funcionan bien sin ellos!!

- Flexibilidad: El manejo de los parámetros permite construir árboles desde muy pequeños a muy grandes

- Overfitting: Si se lo controla apropiadamente

- Parametrización sencilla y poderosa

- Posibilidad de modelos grandes que dan resultados muy "detallados"

- Aprendizaje débil (weak learner), por lo que pueden ganar mucho con técnicas de ensamble como bagging.

Luego el artículo de zyxo habla del bagging, lo que me gustaría dejar para otra oportunidad. Salto al manejo de parámetros para controlar el overfitting:

- Olvídese de la profundidad máxima, establézcala lo más alta posible. Nunca debe ser un criterio de parada si se busca calidad (no así si se busca un modelo más simple, pequeño y legible con propósitos de documentación).

- Use los tamaños mínimos de nodos terminales y de apertura (min child/parent node size en SPSS/Clementine). Estableciendo estos valores muy altos se obtienen árboles pequeños con poco overfitting pero baja calidad. Con valores demasiado pequeños se obtienen árboles enormes con muchísimo overfitting. Es necesario experimentar un poco y evaluar la calidad contra datos de prueba.

Para encontrar los parámetros óptimos el artículo habla de los resultados de la evaluación del bagging, pero en caso de tener un sólo árbol el criterio general sería bajar progresivamente los valores de los tamaños mínimos mientras la evaluación en los datos de prueba dé cada vez mejor, hasta que dé peor (o empiece a dar resultados erráticos), y en ese punto volver un paso atrás y quedarse con los parámetros de dicho paso.

Agrego algunas otras consideraciones:

- Para un árbol de decisión la variable objetivo ideal es binaria: POSITIVO / NEGATIVO. Si la variable es categórica convendría hacer tantos modelos como categorías, tomando como positiva una categoría a la vez, y las demás como negativas. Luego se deberían ensamblar los distintos modelos en uno solo (con otro árbol u otro tipo de modelo). No es la herramienta más adecuada para predecir variables numéricas.

- Tiene manejo de los valores nulos (o missing). Al dividir un nodo por una de las variables, simplemente asigna los casos en que el valor de esa variable es nulo a una de las ramas de la división. Pero atención, esto provoca que se consideren todos los nulos de igual forma (como si tuvieran el mismo valor), algo que en algunos casos no es satisfactorio y requiere una preparación previa más elaborada.

- Soporta una buena cantidad de desbalanceo en la variable objetivo.

- Clasifica (da algún resultado para) cualquier caso que se evalúe, aún si no se le proporcionó ninguno similar durante el entrenamiento.

- Cuidado con las interacciones entre variables. El algoritmo considera de a una variable por vez, y va cortando el espacio de soluciones en "rectángulos", por lo que cualquier interacción entre variables que defina una región importante con forma no rectangular será pobremente representada. Hay técnicas para detectar esto y generar variables adicionales que reflejen estas interacciones para que el árbol las aproveche.

- No existe un único árbol que sea la mejor solución. Pequeñas variaciones en el dataset (como un corte al azar diferente para definir entrenamiento y prueba) pueden dar árboles completamente diferentes. 

- Otro parámetro a tener en cuenta es la selección de la variable inicial, la que divide el nodo raíz. A veces cambiándola manualmente se pueden obtener mejores resultados (o más significativos en el dominio del problema) que dejando que la seleccione automáticamente el algoritmo.

- Acepta variables de entrada de tipo categórico y/o numérico.

- No es afectado por los outliers.