tag:blogger.com,1999:blog-26086078355103555612024-02-07T06:22:42.590-08:00Parra MiningData mining argentino.Unknownnoreply@blogger.comBlogger11125tag:blogger.com,1999:blog-2608607835510355561.post-53220098451212756622019-09-29T16:00:00.000-07:002019-09-30T16:00:27.230-07:00Generalization of the Rødseth's algorithm for the Diophantine Frobenius Problem with n=3Given a set (a<sub>1</sub>, a<sub>2</sub>..., a<sub>n</sub>) of positive integers (a<sub>i</sub> >= 1), the Frobenius Problem looks for the largest number g that cannot be represented by the equation g = a<sub>1</sub>·x<sub>1</sub> + a<sub>2</sub>·x<sub>2</sub> +... + a<sub>n</sub>·x<sub>n</sub>, with x<sub>i</sub> integers >= 0. g is called the Frobenius number of the set. [1]<br /><br />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.<br /><br />The Frobenius Problem has applications in diverse areas as sort methods analysis, Petri Nets, tilings, random vectors generation, etc. [1]<br /><br />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]<br /><br />If the greatest common divisor of the set is grater than 1, the Frobenius number of the set is undefined. [3]<br /><br />If n = 2, g(a<sub>1</sub>, a<sub>2</sub>) = a<sub>1</sub>·a<sub>2</sub> - a<sub>1</sub> - a<sub>2</sub>. [4]<br /><br />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.<br /><br />For n = 3 and a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub> pairwise coprime integers (greatest common divisor = 1) there is an algorithm by Ø. J. Rødseth than works well on average (probably O(log a<sub>2</sub>)), even if in the worst case can take O(a<sub>1</sub> + log a<sub>2</sub>) operations. [1]<br /><br />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.<br /><br />In this implementation let's define g(A) = -1 when any a<sub>i</sub> = 1 (which makes sense since a<sub>i</sub> = 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:<br /><br />d12 = gcd(a<sub>1</sub>, a<sub>2</sub>);<br />d13 = gcd(a<sub>1</sub> / d12, a<sub>3</sub>);<br />d23 = gcd(a<sub>2</sub> / d12, a<sub>3</sub> / d13);<br />a' = (a<sub>1</sub> / d12 / d13, a<sub>2</sub> / d12 / d23, a<sub>3</sub> / d13 / d23)<br />r = Rødseth algorithm applied to a'<br />g(a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>) = r * d12 * d13 * d23 + a<sub>1</sub> * (d23 - 1) + a<sub>2</sub> * (d13 - 1) + a<sub>3</sub> * (d12 - 1)<br /><br />This works with any set of positive integers that have a defined Frobenius number (i.e. gcd(a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>) = 1).<br /><br />Examples:<br />a = (12, 14, 17)<br />a'= (6, 7, 17)<br />d12 = 2, d13 = 1, d23 = 1<br />r = 22<br />g = 22 * 2 + 12 * 0 + 14 * 0 + 17 * 1 = 61<br /><br />a = (12, 13, 34)<br />a'= (6, 13, 17)<br />d12 = 1, d13 = 2, d23 = 1<br />r = 33<br />g = 33 * 2 + 12 * 0 + 13 * 1 + 34 * 0 = 79<br /><br />a = (5, 9, 21)<br />a'= (3, 5, 7)<br />d12 = 1, d13 = 1, d23 = 3<br />r = 4<br />g = 4 * 3 + 5 * 2 + 9 * 0 + 21 * 0 = 22<br /><br />a = (6, 9, 20)<br />a'= (1, 3, 10)<br />d12 = 3, d13 = 2, d23 = 1<br />r = -1<br />g = -1 * 6 + 6 * 0 + 9 * 1 + 20 * 2 = 43<br /><br />a = (582795988, 1753241221, 6814151015)<br />a'= (582795988, 1753241221, 6814151015)<br />d12 = 1, d13 = 1, d23 = 1<br />r = 173685179295403<br />g = 173685179295403 * 1 + 582795988 * 0 + 1753241221 * 0 + 6814151015 * 0 = 173685179295403<br /><br />a = (4, 16, 30)<br />g = undefined (gcd(a) = 2)<br />
<br />
a = (12, 12, 13)<br />
a'= (1, 1, 13)<br />
d12 = 12, d13 = 1, d23 = 1<br />
r = -1<br />
g = -1 * 12 + 12 * 0 + 12 * 0 + 13 * 11 = 131<br />
<br />a = (1, 6, 15)<br />a'= (1, 2, 5)<br />d12 = 1, d13 = 1, d23 = 3<br />r = -1<br />g = -1 * 3 + 1 * 2 + 6 * 0 + 15 * 0 = -1<br /><br /><br />Working code:<br />
<br />
<a href="https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1424a910a196fb3d0e964c754fbf325c">Rust playground</a> <br />
<br />
<br />[1] <a href="https://global.oup.com/academic/product/the-diophantine-frobenius-problem-9780198568209">https://global.oup.com/academic/product/the-diophantine-frobenius-problem-9780198568209</a><br />[2] <a href="https://en.wikipedia.org/wiki/Coin_problem#McNugget_numbers">https://en.wikipedia.org/wiki/Coin_problem#McNugget_numbers</a><br />[3] <a href="https://en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics">https://en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics</a><br />[4] <a href="https://www.jstor.org/stable/2369536">https://www.jstor.org/stable/2369536</a><br />[5] <a href="http://people.reed.edu/~iswanson/LepilovORourkeSwanson.pdf">http://people.reed.edu/~iswanson/LepilovORourkeSwanson.pdf</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2608607835510355561.post-59989928138331438852011-07-03T17:50:00.000-07:002011-07-03T18:13:21.016-07:00Map-Time SurferParticipé en la competencia <a href="http://hcil.cs.umd.edu/localphp/hcil/vast11/index.php/">IEEE VAST Challenge 2011</a>, 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.<br /><br />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).<br /><br />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á:<br /><br /><script type="text/javascript" src="http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/swfobject.js"></script><br /> <script type="text/javascript"><br /> swfobject.registerObject("csSWF", "9.0.115", "http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/expressInstall.swf");<br /></script><br /><br /><div id="media"><br /> <object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" width="640" height="658" id="csSWF"><br /> <param name="movie" value="http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/Vast2011-mc1_controller.swf" /><br /> <param name="quality" value="best" /><br /> <param name="bgcolor" value="#1a1a1a" /><br /> <param name="allowfullscreen" value="true" /><br /> <param name="scale" value="showall" /><br /> <param name="allowscriptaccess" value="always" /><br /> <param name="flashvars" value="autostart=false&thumb=http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/FirstFrame.png&thumbscale=45&color=0x000000,0x000000" /><br /> <!--[if !IE]>--><br /> <object type="application/x-shockwave-flash" data="Vast2011-mc1_controller.swf" width="640" height="658"><br /> <param name="quality" value="best" /><br /> <param name="bgcolor" value="#1a1a1a" /><br /> <param name="allowfullscreen" value="true" /><br /> <param name="scale" value="showall" /><br /> <param name="allowscriptaccess" value="always" /><br /> <param name="flashvars" value="autostart=false&thumb=http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/FirstFrame.png&thumbscale=45&color=0x000000,0x000000" /><br /> <!--<![endif]--><br /> <div id="noUpdate"><br /> <p>The Camtasia Studio video content presented here requires JavaScript to be enabled and the latest version of the Adobe Flash Player. If you are using a browser with JavaScript disabled please enable it now. Otherwise, please update your version of the free Adobe Flash Player by <a href="http://www.adobe.com/go/getflashplayer">downloading here</a>. </p><br /> </div><br /> <!--[if !IE]>--><br /> </object><br /> <!--<![endif]--><br /> </object><br /> </div><br /> <!-- Users looking for simple object / embed tags can copy and paste the needed tags below.<br /> <div id="media"><br /> <object id="csSWF" classid="clsid:d27cdb6e-ae6d-11cf-96b8-444553540000" width="640" height="658" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=9,0,115,0"><br /> <param name="src" value="http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/Vast2011-mc1_controller.swf"/><br /> <param name="bgcolor" value="#1a1a1a"/><br /> <param name="quality" value="best"/><br /> <param name="allowScriptAccess" value="always"/><br /> <param name="allowFullScreen" value="true"/><br /> <param name="scale" value="showall"/><br /> <param name="flashVars" value="autostart=false#&thumb=http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/FirstFrame.png&thumbscale=45&color=0x000000,0x000000"/><br /> <embed name="csSWF" src="http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/Vast2011-mc1_controller.swf" width="640" height="658" bgcolor="#1a1a1a" quality="best" allowScriptAccess="always" allowFullScreen="true" scale="showall" flashVars="autostart=false&thumb=http://www.matotuonda.com.ar/infovis/MapTimeSurfer/UBA-MapTimeSurfer-MC1/FirstFrame.png&thumbscale=45&color=0x000000,0x000000" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash"></embed><br /> </object><br /> </div><br /> --><br /><br />Y este es el programita presentado (si los dioses de los permisos, los sistemas operativos, los navegadores y las máquinas virtuales quieren):<br /><br /><iframe src="http://www.matotuonda.com.ar/infovis/MapTimeSurfer/maptimesurfer.html" width="640" height="640" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"><p>Su navegador no soporta iframes.</p></iframe><br /><br /><em>Hacer clic y arrastrar para apreciar la perspectiva 3D. Hacer zoom con la ruedita del mouse o las flechas arriba/abajo.</em><br /><br />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.<br /><br />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. :)Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2608607835510355561.post-81185834993134025782011-05-15T23:30:00.000-07:002011-05-15T19:58:41.978-07:00Treemap con intervalos de confianza<iframe src="http://www.matotuonda.com.ar/infovis/MapaDeManos/index.html" width="640" height="506" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"><p>Su navegador no soporta iframes.</p></iframe><br /><br />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.<br /><br />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.<br /><br />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.<br /><br /><span style="font-weight:bold;">Los datos del ejemplo</span><br /><br />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.<br /><br />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.<br /><br />En mesas de 6 jugadores las posiciones son las siguientes:<br /><br /><ul><li>SB (<span style="font-style:italic;">Small blind</span>, ciega pequeña): Apuesta de forma obligada la mitad de la apuesta mínima antes de ver sus cartas.</li><br /><li>BB (<span style="font-style:italic;">Big blind</span>, ciega grande): Apuesta de forma obligada la apuesta mínima antes de ver sus cartas.</li><br /><li>EA (<span style="font-style:italic;">Early position</span>, posición temprana): El primero luego de las ciegas. Jugar primero es una desventaja.</li><br /><li>MD (<span style="font-style:italic;">Medium position</span>, posición media): El siguiente a la posición temprana.</li><br /><li>CO (<span style="font-style:italic;">Cutoff</span>, posición de corte): El anteúltimo.</li><br /><li>BTN (<span style="font-style:italic;">Button</span>, botón que indica quien reparte): Es el último en actuar, lo que supone una ventaja.</li></ul><br /><br />Las cartas se pueden agrupar en las siguientes categorías (tomadas del Holdem Manager):<br /><br /><ul><li>As y carta alta (As y K o As y Q)</li><br /><li>As y distinto palo</li><br /><li>As y mismo palo (cuando las dos cartas son del mismo palo se indica con una s (<span style="font-style:italic;">suited</span>), por ejemplo A9s)</li><br /><li>Conectores distinto palo (los conectores son dos cartas seguidas, por ejemplo 98 o T9 (T indica el diez (<span style="font-style:italic;">ten</span>)))</li><br /><li>Conectores mismo palo</li><br /><li>Un hueco y distinto palo (un hueco es cuando falta una carta en el medio, por ejemplo KJ o 42)</li><br /><li>Un hueco y mismo palo</li><br /><li>Dos huecos y distinto palo (cuando faltan dos cartas en el medio, por ejemplo KT o 52)</li><br /><li>Dos huecos y mismo palo</li><br /><li>Par de ases</li><br /><li>Par alto (KK, QQ o JJ)</li><br /><li>Par medio (TT, 99, 88 o 77)</li><br /><li>Par bajo (66, 55, 44, 33 o 22)</li><br /><li>Mismo palo (otras)</li><br /><li>Distinto palo (otras)</li></ul><br /><br />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.<br /><br />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.<br /><br /><br /><span style="font-weight:bold;">La visualización</span><br /><br />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.<br /><br />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.<br /><br />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.<br /><br />Los intervalos de confianza se calculan en base a la distribución t:<br /><br />y ± t(α/2,W−1) * SE<br /><br />donde y es la media aritmética,<br />α es el nivel de error (1-nivel de confianza)<br />W es el tamaño de la muestra<br />SE es el error estándar<br /><br /><br /><span style="font-weight:bold;">Resultados del análisis</span><br /><br />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.<br /><br />De todas maneras se pueden sacar algunas conclusiones interesantes:<br /><br /><ul><li>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.</li><br /><li>Pero me resulta inesperado lo notablemente redituables que se muestran los conectores de distinto palo.</li><br /><li>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.</li></ul><br /><br /><br /><span style="font-weight:bold;">Las herramientas</span><br /><br />Se utilizó el lenguaje Processing (<a href="http://processing.org">processing.org</a>) y la implementación de treemaps que aparece en el capítulo 7 de <span style="font-style:italic;">Visualizing Data</span> (Ben Fry, 2008).<br /><br />Para establecer los intervalos de confianza se utilizó la biblioteca statdistlib (<a href="http://sourceforge.net/projects/statdistlib/">sourceforge.net/projects/statdistlib/</a>) de Dr. Peter N. Steinmetz y Gregory Warnes.<br /><br />Los resultados se verificaron con SPSS Statistics 17.0.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2608607835510355561.post-67048715152557797222009-05-19T12:41:00.000-07:002009-05-21T14:55:28.511-07:00¡Aparecí en KDnuggets News!<a href="http://www.kdnuggets.com/news/index.html">KDnuggets News</a> 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.<br /><br />En su <a href="http://www.kdnuggets.com/news/2009/n09/index.html?c2">último número</a> <a href="http://www.kdnuggets.com/news/2009/n09/3i.html">incluye</a> como destacada una novela (un thriller) de mi autoría. Se trataba de crear una historia relacionada con data mining en <b>seis palabras</b>. Aquí la reproduzco, en su versión completa:<br /><br /><em>Only six words? Get more data!</em> (¿Sólo seis palabras? ¡Consigan más datos!)<br /><br />:DUnknownnoreply@blogger.com1tag:blogger.com,1999:blog-2608607835510355561.post-32459141153929062052009-05-03T18:17:00.000-07:002009-05-18T03:28:19.239-07:00Detección anticipada del brote de gripe porcina mediante data mining<div>La empresa <a href="http://www.veratect.com/index.html">Veratect</a> 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.<br /></div><div><br /></div><div>Por lo que dicen sus comunicados de prensa, la empresa monitorea más de 40.000 fuentes de información (como <a href="http://www.eurosurveillance.org/Default.aspx">Eurosurveillance</a> o el sitio de la <a href="http://www.who.int/csr/en/">OMS</a>) 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.</div><div><br /></div><div>Las actualizaciones respecto a la gripe pueden verse en forma gratuita en <a href="http://twitter.com/Veratect">su canal de tweeter</a>. Sin embargo buscando en la historia de ese mismo canal, no se encuentra nada relativo a este brote antes del 24/04: <a href="http://search.twitter.com/search?q=+from:Veratect+until:2009-04-23">http://search.twitter.com/search?q=+from:Veratect+until:2009-04-23</a>.</div><div><br /></div><div>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.</div><div><br /></div><div>Enlaces:</div><div>- <a href="http://www.veratect.com/media/042609_release.pdf">Nota de prensa de la empresa</a> (pdf en inglés)</div><div>- <a href="http://www.chron.com/disp/story.mpl/sp/us/6398928.html">Noticia en The Houston Chronicle</a></div><div>- <a href="http://www.e-consulta.com/index.php?option=com_content&task=view&id=26675&Itemid=181">Noticia en e-consulta</a> (diario mexicano)</div><div>- <a href="http://www.cejournal.net/?p=1802">Noticia en CEJournal</a> (en inglés)<br /></div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2608607835510355561.post-18742208624484792462009-04-27T18:10:00.000-07:002009-05-03T18:26:30.851-07:00¿Qué es Data Mining?<div>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.</div><div><br /></div><div>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:</div><div><br /></div><div><div><span class="Apple-style-span" style="font-weight: bold;">¿Qué es Data Mining?</span></div><div><ul><li>"Data Mining" (Minería de Datos) se refiere a un conjunto de técnicas de base estadística y algorítmica (algoritmo = procedimiento computarizable)<br /></li><li>organizado con un método<br /></li><li>que permite analizar montañas de datos</li><li>buscando relaciones sutiles (no evidentes) existentes en estos datos<br /></li><li>En base a estas relaciones se construyen modelos<br /></li><li>En base a los modelos se pueden tomar mejores decisiones<br /></li></ul></div><div><div><span class="Apple-style-span" style="font-weight: bold;">¿Qué es un modelo?</span></div><div><ul><li>Un modelo es una representación simplificada de la realidad, que sin embargo mantiene lo que es “importante”<br /></li><li>En base a cómo funciona el modelo, se pueden inferir aspectos del funcionamiento de la realidad, que siempre es mucho más compleja</li></ul></div><div><div><span class="Apple-style-span" style="font-weight: bold;">¿Cuáles son los tipos de modelos más importantes en Data Mining?</span></div><div><ul><li>Modelos Explicativos<br /></li><li><span class="Apple-style-span" style="font-style: italic;">--- Permiten encontrar qué factores influyen en un resultado<br /></span></li><li><span class="Apple-style-span" style="font-style: italic;">--- Permite agrupar resultados similares</span><br /></li><li>Modelos Predictivos<br /></li><li><span class="Apple-style-span" style="font-style: italic;">--- En base a los patrones de comportamiento previo, permite identificar cuál es el comportamiento futuro más probable<br /></span></li><li><span class="Apple-style-span" style="font-style: italic;">--- En base a una clasificación realizada sobre un conjunto de casos conocidos, permite asignarle una clase a un caso nuevo</span><br /></li></ul></div><div><span class="Apple-style-span" style="font-weight: bold;">¿Qué aplicaciones concretas tiene Data Mining?</span> Ejemplos:<br /></div><div><ul><li>Market basket analysis: ¿qué productos se venden juntos?<br /></li><li>Modelo de fuga (churn o attrition): ¿qué clientes están por abandonar un servicio?<br /></li><li>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?</li><li>¿Cuáles son los factores que más influyen en un proceso? (de producción, logística, ventas, etc.)<br /></li><li>Detección de fraudes<br /></li><li>Personalización de publicidad en Internet<br /></li><li>Predicción de fallas de maquinaria<br /></li><li>Predicción de la demanda<br /></li><li>Predicción del flujo de caja<br /></li><li>Reconocimiento de imágenes<br /></li><li>Evaluación de riesgos crediticios<br /></li><li>Detección de spam<br /></li><li>Estudios genéticos<br /></li><li>Catalogación de cuerpos celestes en astronomía<br /></li><li>Análisis de documentos no estructurados (text mining y web mining)<br /></li><li>Etc., etc., etc…<br /></li></ul></div><div><div><span class="Apple-style-span" style="font-weight: bold; ">Limitaciones</span><br /></div></div><div><ul><li>No pueden analizarse datos que no se tienen<br /></li><li><span class="Apple-style-span" style="font-style: italic;">--- Un posible resultado de un proyecto de DM es la determinación de los datos que deben empezar a recolectarse</span><br /></li><li>Si los datos son erróneos, las predicciones también lo serán<br /></li><li><span class="Apple-style-span" style="font-style: italic;">--- Aunque las técnicas son bastante resistentes a una cierta cantidad de “ruido”</span><br /></li></ul></div><div><div><div><span class="Apple-style-span" style="font-weight: bold; ">¿Qué NO es Data Mining?</span></div><div><ul><li>Recolección de información personal</li><li><span class="Apple-style-span" style="font-style: italic;">--- 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.</span></li><li>Recolección de mails de páginas web</li><li><span class="Apple-style-span" style="font-style: italic;">--- 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: </span><a href="http://en.wikipedia.org/wiki/Web_scraping"><span class="Apple-style-span" style="font-style: italic;">web scraping)</span></a></li></ul></div></div></div><div>¿Se entendió? :) Ahora para satisfacer al lector más avanzado, dos apartaditos más técnicos:<br /></div><div><br /></div><div><span class="Apple-style-span" style="font-weight: bold;">¿Cuáles son las técnicas más importantes que se usan en Data Mining?</span> Ordenadas por uso (de mayor a menor) según <a href="http://www.rexeranalytics.com/Data-Miner-Survey-Results-2008.html">reporte de 2008 de Rexer Analytics</a>:</div><div><ul><li>Regresiones (<a href="http://es.wikipedia.org/wiki/Regresi%C3%B3n_lineal">lineal</a>, <a href="http://es.wikipedia.org/wiki/Regresi%C3%B3n_log%C3%ADstica">logística</a>, etc.)<br /></li><li><a href="http://es.wikipedia.org/wiki/Algoritmo_de_agrupamiento">Árboles de Decisión</a><br /></li><li><a href="http://es.wikipedia.org/wiki/Algoritmo_de_agrupamiento">Análisis de conglomerados</a> (cluster analysis)<br /></li><li><a href="http://es.wikipedia.org/wiki/Series_de_tiempo">Series de tiempo</a><br /></li><li><a href="http://es.wikipedia.org/wiki/Redes_neuronales">Redes Neuronales</a><br /></li><li><a href="http://es.wikipedia.org/wiki/Reglas_de_asociaci%C3%B3n">Reglas de asociación</a><br /></li><li><a href="http://es.wikipedia.org/wiki/An%C3%A1lisis_factorial">Análisis factorial</a><br /></li><li><a href="http://es.wikipedia.org/wiki/M%C3%A1quinas_de_vectores_de_soporte">Máquinas de soporte vectorial</a> (Support Vector Machines, SVMs)<br /></li><li><a href="http://es.wikipedia.org/wiki/Red_bayesiana">Redes Bayesianas</a><br /></li><li><a href="http://en.wikipedia.org/wiki/Survival_analysis">Análisis de supervivencia (link a artículo en inglés)</a><br /></li><li><a href="http://en.wikipedia.org/wiki/Rule_induction">Reglas de inducción</a><a href="http://en.wikipedia.org/wiki/Survival_analysis"> (link a artículo en inglés)</a><br /></li><li><a href="http://es.wikipedia.org/wiki/Red_social">Análisis de redes sociales</a><br /></li><li><a href="http://es.wikipedia.org/wiki/Algoritmos_gen%C3%A9ticos">Algoritmos genéticos</a><br /></li><li><a href="http://en.wikipedia.org/wiki/GMDH">Group Method of Data Handling (GMDH)</a><a href="http://en.wikipedia.org/wiki/Survival_analysis"> (link a artículo en inglés)</a><br /></li></ul></div><div><span class="Apple-style-span" style="font-weight: bold;">¿Cuáles son los softwares más importantes que se usan en Data Mining?</span> Ordenados por uso (de mayor a menor) según el mismo reporte:</div><div><ul><li><a href="http://www.spss.com/la/productos/clementine/clementine.htm">SPSS Clementine</a><br /></li><li><a href="http://www.sas.com/offices/latinamerica/argentina/">SAS</a><br /></li><li><a href="http://www.statsoft.com/products/products.htm">Statistica (Statsoft)</a><br /></li><li><a href="http://www.sas.com/technologies/analytics/datamining/miner/">SAS Enterprise Miner</a><br /></li><li><a href="http://www.spss.com/statistics/">SPSS</a><br /></li><li><a href="http://rapid-i.com/content/blogcategory/38/69/lang,en/">Rapid Miner</a><br /></li><li><a href="http://www.r-project.org/">R</a><br /></li><li><a href="http://www.sqlserverdatamining.com/ssdm/">Microsoft SQL Server</a><br /></li><li><a href="http://www.kxen.com/">KXEN</a><br /></li><li><a href="http://www.mathworks.com/products/matlab/">Matlab</a><br /></li><li><a href="http://www.cs.waikato.ac.nz/ml/weka/">Weka</a></li></ul></div></div></div></div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2608607835510355561.post-55850086165407436692009-04-20T17:50:00.000-07:002009-05-03T19:10:00.769-07:00Amor por los árboles (de decisión)<span class="Apple-style-span" style=" ;font-family:'Times New Roman';"><div style="margin-top: 8px; margin-right: 8px; margin-bottom: 8px; margin-left: 8px; font: normal normal normal small/normal arial; "><div>zyxo en su interesante blog <a href="http://zyxo.wordpress.com/">Mixotricha</a>, escribió un muy buen <a href="http://zyxo.wordpress.com/2009/01/14/data-mining-with-decision-trees-what-they-never-tell-you/">artículo</a> relativo a las ventajas de los árboles de decisión y el control del overfitting (<wbr>sobreentrenamiento), del cual me tomé la libertad de traducir y parafrasear las partes que me parecieron más interesantes:</div><div><br /></div><div><span style="font-style: italic; ">Desventajas de los árboles de decisión:</span></div><div><span style="font-style: italic; ">- Overfitting (¡pero se puede controlar y usar para mejorar la calidad del modelo!)</span></div><div><br /></div><div><span style="font-style: italic; ">Ventajas:</span></div><div><span style="font-style: italic; ">- Legibilidad del resultado: Simples sentencias IF THEN</span></div><div><span style="font-style: italic; ">- Algoritmo simple</span></div><div><span style="font-style: italic; ">- Robustez: El preprocesamiento y la limpieza de datos son un trabajo engorroso, ¡¡pero los árboles funcionan bien sin ellos!!</span></div><div><span style="font-style: italic; ">- Flexibilidad: El manejo de los parámetros permite construir árboles desde muy pequeños a muy grandes</span></div><div><span style="font-style: italic; ">- Overfitting: Si se lo controla apropiadamente</span></div><div><span style="font-style: italic; ">- Parametrización sencilla y poderosa</span></div><div><span style="font-style: italic; ">- Posibilidad de modelos grandes que dan resultados muy "detallados"</span></div><div><span style="font-style: italic; ">- Aprendizaje débil (weak learner), por lo que pueden ganar mucho con técnicas de ensamble como bagging.</span></div><div><br /></div><div>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:</div><div><br /></div><div><span style="font-style: italic; ">- 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).</span></div><div><span style="font-style: italic; ">- Use los tamaños mínimos de nodos terminales y de apertura</span><span> (min child/parent node size en SPSS/Clementine)</span><span style="font-style: italic; ">. 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.</span></div><div><br /></div><div>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.</div><div><br /></div><div>Agrego algunas otras consideraciones:</div><div><br /></div><div>- 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.</div><div>- 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.</div><div>- Soporta una buena cantidad de desbalanceo en la variable objetivo.</div><div>- Clasifica (da algún resultado para) cualquier caso que se evalúe, aún si no se le proporcionó ninguno similar durante el entrenamiento.</div><div>- 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.</div><div>- 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. </div><div>- 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.</div><div><div>- Acepta variables de entrada de tipo categórico y/o numérico.</div><div>- No es afectado por los outliers.<br /></div></div><div></div></div></span>Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-2608607835510355561.post-1048294804909216802009-04-14T17:36:00.000-07:002009-05-03T18:27:56.907-07:00Punto de corte en modelo de fuga<div>Si tomamos el modelo de fuga (churn o attrition) como un problema de ordenamiento, es claro que la parte más difícil es establecer el orden de los clientes de acuerdo a su propensión estimada a cancelar sus productos o servicios. Esto puede hacerse con un score calculado a partir de un árbol de decisión, un generador de reglas de decisión, una red neuronal, etc.<br /></div><div><br /></div><div>Ahora, una vez ordenados los clientes, ¿sobre cuántos se debe efectuar la acción de retención? Una sencilla respuesta es definirlo por el presupuesto que tiene destinado el departamento de Marketing. Si cada acción cuesta $10, y el presupuesto es de $40.000, simplemente se toman los primeros 4.000 clientes de la lista ordenada y se realiza la acción sobre ellos.</div><div><br /></div><div>El problema con este enfoque es que no toma en cuenta la ganancia esperada de cada cliente de la lista, y puede quedarse corto (no llegando a efectuar la acción sobre clientes que tienen ganancia esperada positiva), o peor aún, pasarse del punto de corte óptimo, efectuando la acción sobre clientes que tienen ganancia esperada negativa. Veámoslo con un ejemplo:</div><div><br /></div><div>Costo de acción: $10</div><div>Ganancia por acierto de predicción: $500</div><div>Saldo por acierto: $490</div><div>Clientes: 100.000</div><div>Clientes que se fugarían: 1.000 (1% del total)</div><div><br /></div><p>Supongamos que un árbol de decisión nos genera una lista de 5 nodos que clasifican los clientes, para los cuales se estima la siguiente distribución esperada:</p><br /><table border="1"><tbody><tr><td></td><td>Clientes</td><td>Fuga</td><td>%</td></tr><tr><td style="text-align: right;">Nodo 1</td><td style="text-align: right;">200</td><td style="text-align: right;">50</td><td style="text-align: right;">25,00%</td></tr><tr><td style="text-align: right;">Nodo 2</td><td style="text-align: right;">1.000</td><td style="text-align: right;">100</td><td style="text-align: right;">10,00%</td></tr><tr><td style="text-align: right;">Nodo 3</td><td style="text-align: right;">2.500</td><td style="text-align: right;">200</td><td style="text-align: right;">8,00%</td></tr><tr><td style="text-align: right;">Nodo 4</td><td style="text-align: right;">80.000</td><td style="text-align: right;">600</td><td style="text-align: right;">0,75%</td></tr><tr><td style="text-align: right;">Nodo 5</td><td style="text-align: right;">16.300</td><td style="text-align: right;">50</td><td style="text-align: right;">0,31%</td></tr><tr><td style="text-align: right;">Total</td><td style="text-align: right;">100.000</td><td style="text-align: right;">1.000</td><td style="text-align: right;">1,00%</td></tr></tbody></table><br /><div>La ganancia esperada para cada nodo se puede calcular como la ganancia de los aciertos, menos el costo de realizar la acción sobre el total de clientes del nodo. Para el nodo 1 esto sería $500 * 50 - $10 * 200 = $38.000. Dividiendo esto por el total de clientes se obtiene una ganancia esperada por cada cliente del nodo: $38.000/200 = $190. Completando la tabla anterior:</div><br /><table border="1"><tbody><tr><td></td><td>Clientes</td><td>Fuga</td><td>%</td><td> Ganancia<br />esperada</td><td>G.E. por cliente</td></tr><tr><td style="text-align: right;">Nodo 1</td><td style="text-align: right;">200</td><td style="text-align: right;">50</td><td style="text-align: right;">25,00%</td><td style="text-align: right;">$38.000</td><td style="text-align: right;">$190</td></tr><tr><td style="text-align: right;">Nodo 2</td><td style="text-align: right;">1.000</td><td style="text-align: right;">100</td><td style="text-align: right;">10,00%</td><td style="text-align: right;">$70.000</td><td style="text-align: right;">$70</td></tr><tr><td style="text-align: right;">Nodo 3</td><td style="text-align: right;">2.500</td><td style="text-align: right;">200</td><td style="text-align: right;">8,00%</td><td style="text-align: right;">$135.000</td><td style="text-align: right;">$54</td></tr><tr><td style="text-align: right;">Nodo 4</td><td style="text-align: right;">80.000</td><td style="text-align: right;">600</td><td style="text-align: right;">0,75%</td><td style="text-align: right;">-$320.000</td><td style="text-align: right;">-$4</td></tr><tr><td style="text-align: right;">Nodo 5</td><td style="text-align: right;">16.300</td><td style="text-align: right;">50</td><td style="text-align: right;">0,31%</td><td style="text-align: right;">-$123.000</td><td style="text-align: right;">-$8</td></tr><tr><td style="text-align: right;">Total</td><td style="text-align: right;">100.000</td><td style="text-align: right;">1.000</td><td style="text-align: right;">1,00%</td></tr></tbody></table><br /><div>Entonces, si se toman sólo los nodos de ganancia esperada positiva, se efectuaría la acción sobre 3.700 clientes, obteniéndose una ganancia de $243.000 (sumas de los valores de los 3 primeros nodos). Si se continúa efectuando la acción sobre 300 clientes más (para llegar a 4.000), al pertenecer al siguiente nodo estos tienen una ganacia esperada de -$4, dando un total de -$1.200, disminuyendo la ganancia total a $241.800. Convendría ahorrar los $3.000 que se gastarían en estos 300 clientes y sumarlos a la ganancia de los nodos positivos, dando un total general del proyecto de +$246.000.</div>Unknownnoreply@blogger.com4tag:blogger.com,1999:blog-2608607835510355561.post-29043629956772921642009-04-13T17:10:00.000-07:002009-05-03T18:30:14.965-07:00SPSS renombra sus productos<div><div>En la nueva versión de sus productos prevista para 2010, SPSS cambia sus nombres unificándolos bajo el prefijo PASW (Predictive Analytics Software):</div><div><br /></div><div>SPSS Statistic -> PASW Statistics 17</div><div>Clementine -> PASW Modeler 13</div><div>Dimensions mrStudio -> PASW Data Collection Base</div><div>SPSS Predictive Enterprise Services Base Services -> PASW Collaboration Services</div><div>etc...</div><div><br /></div><div>Todo más claro, aunque "Clementine" es un nombre mucho más lindo...</div><div><br /></div><div>Enlace: <a href="http://www.spss.com/es/software/product-name-guide/">http://www.spss.com/es/software/product-name-guide/</a></div></div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2608607835510355561.post-91558889404255665412009-04-13T16:40:00.000-07:002009-04-13T17:09:51.487-07:00KDD Cup 2009¡Todavía estamos a tiempo de participar! Al menos en el desafío "lento", cuya fecha límite es el 11 de mayo (el "rápido" terminó el 10 de abril).<div><br /></div><div>Se trata de desarrollar un modelo (o varios) para predecir fuga (churn o attrition), afinidad (appetency, compra de nuevos productos o servicios) y venta cruzada (up-selling, compra de productos adicionales) en una base de datos de clientes de una empresa francesa de telefonía.</div><div><br /></div><div>Hay un desafío rápido y uno lento, y a la vez un dataset grande (15.000 variables) y uno pequeño (230 variables).</div><div><br /></div><div>El desafío rápido busca evaluar la capacidad de obtener buenas predicciones sobre el dataset grande en un tiempo limitado (5 días). El desafío lento da más tiempo y se puede trabajar sobre la base grande o sobre la pequeña (pensada para aquellos que no cuentan con equipo tan poderosos).</div><div><br /></div><div>Yo ya me bajé el dataset pequeño, espero tener tiempo para desarrollar los modelos y participar. :)</div><div><br /></div><div>Enlace: <a href="http://www.kddcup-orange.com/index.php">http://www.kddcup-orange.com/index.php</a></div>Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-2608607835510355561.post-38666950559803486152009-04-13T16:22:00.000-07:002009-04-13T17:30:49.355-07:00PresentaciónEste blog tiene por objetivo presentar (e idealmente discutir) ideas, softwares y noticias relacionadas con Data Mining (o Minería de Datos), Aprendizaje Automático (Machine Learning) y temas afines, desde la perspectiva de un estudiante argentino del tema.<br /><br />Está dirigido a aquellos que estén estudiando el tema (pienso en las alumnos de las maestrías que se dictan en la <a href="http://www-2.dc.uba.ar/materias/mdmkd/index_1024.html">UBA</a>, la <a href="http://web.austral.edu.ar/ingenieria-posgrado-carreras-datamining.asp">Universidad Austral</a>, y la <a href="http://www.ba.unibo.it/BuenosAires/formacionacademica/maestrias/datamining.htm">Universidad de Bologna</a>), trabajen en el área, o simplemente tengan un interés autodidacta. En algunos artículos se asume un conocimiento mínimo de los softwares más utilizados.<br /><br />Cada artículo está escrito en forma independiente, es decir, no da por sentado que se leyeron los anteriores, y de ser necesario incluye links a las referencias pertinentes.<br /><br />El sistema de comentarios permite escribir como usuario registrado o como anónimo, y desde ya se agradece cualquier tipo de feedback. De todas maneras me reservo el derecho de eliminar sin previo aviso todo aquello que no esté relacionado con el tópico en cuestión (especialmente el spam).<br /><br /><span class="Apple-style-span" style="font-weight: bold;">El Autor</span><br /><br />Mi nombre es Andrés Parra, tengo formación en Ingeniería en Computación, vivo en Buenos Aires, y estoy cursando la maestría de la UBA. No estoy trabajando en el área, aunque espero hacerlo pronto. Estos temas me apasionan como a quien gusta de resolver crucigramas y acertijos. Espero poder transmitir parte de esa inquietud. :)<br /><br />Mi correo es parra.andres arroba gmail.com, para lo que guste mandar.Unknownnoreply@blogger.com0