https:\/\/doi.org\/10.29105\/cienciauanl22.96-4<\/a><\/p>\r\n <\/p>\r\n\r\n\r\n\r\n
RESUMEN<\/h4>\r\n\r\n\r\n\r\n La ciencia de datos es un \u00e1rea multidisciplinaria en la que convergen herramientas de estad\u00edstica, c\u00f3mputo cient\u00edfico, matem\u00e1ticas puras y un profundo entendimiento del contexto del problema a estudiar. Dentro de esta \u00e1rea han surgido recientes investigaciones en las que el an\u00e1lisis se enfoca en un aspecto m\u00e1s cualitativo del estudio, a saber: la forma de los datos<\/em>. En el presente trabajo describimos esquem\u00e1ticamente algunas de las herramientas para implementar dicho an\u00e1lisis y presentamos como propuesta un algoritmo eficiente, auxiliar en el estudio de estructuras de baja dimensi\u00f3n simplicial, inmersas en un espacio de representabilidad de dimensi\u00f3n alta.<\/p>\r\n\r\n\r\n\r\nPalabras clave: an\u00e1lisis topol\u00f3gico de datos, complejo de Vietoris-Rips, complejo de Cech, bola minimal.<\/p>\r\n\r\n\r\n\r\n
ABSTRACT<\/h4>\r\n\r\n\r\n\r\n Data science is a multidisciplinary area in which statistics, scientific computation, pure mathematics and adeep understanding of the context of the problem to be studied converge. Within this area, recent studies have emerged in which the analysis centers on a qualitative aspect of the study, the form of the data. In the present research some of the tools to schematically implementthis analysis are described, and an efficient algorithm tothe study of low dimensional structures, immersed in a high dimension representability space is proposed.<\/em><\/p>\r\n\r\n\r\n\r\nKeywords: topological data analysis, Vietoris-Rips complex, Cech complex, miniball problem.<\/em><\/p>\r\n\r\n\r\n\r\nDentro de las matem\u00e1ticas, diversas \u00e1reas han sido tradicionalmente consideradas como puras (o b\u00e1sicas), entre las que se destaca la topolog\u00eda, por considerarse una de las \u201cgeometr\u00edas m\u00e1s elementales\u201d, encargada de estudiar la forma de ciertos objetos, as\u00ed como las propiedades que se preservan al deformarlos continuamente, es decir, sin rompimientos ni pegaduras. Las recientes aplicaciones que \u00e9sta ha tenido junto con el \u00e1lgebra, as\u00ed como la impresionante integraci\u00f3n con \u00e1reas como la combinatoria, la probabilidad, la estad\u00edstica y el c\u00f3mputo cient\u00edfico, han propiciado la consolidaci\u00f3n de una interesante \u00e1rea llamada an\u00e1lisis topol\u00f3gico de datos (ATD); puede consultarse Zomorodian (2012) para una introducci\u00f3n al tema, y Otter\u00a0et al<\/em>. (2017) para una exposici\u00f3n panor\u00e1mica, alcances del ATD y su implementaci\u00f3n computacional.<\/p>\r\n\r\n\r\n\r\nDebido al amplio espectro de t\u00f3picos en donde se ha implementado (Piangerelli et al<\/em>., 2018; Pranav\u00a0et al<\/em>.,\u00a02017; Taylor\u00a0et al<\/em>.,2015; Nicolau, Levine y Carlsson, 2011), el ATD ha revolucionado viejos paradigmas, posicion\u00e1ndose como una herramienta s\u00f3lida y estable para abordar el an\u00e1lisis de complejas estructuras de nubes de datos y consolid\u00e1ndose como un importante\u00a0recurso para el entendimiento de estructuras geom\u00e9tricas de dimensiones superiores.<\/p>\r\n\r\n\r\n\r\nEsquem\u00e1ticamente, el ATD consiste en el uso de las t\u00e9cnicas de la topolog\u00eda y el \u00e1lgebra para el an\u00e1lisis de nubes de puntos (datos) en donde existe una noci\u00f3n de cercan\u00eda, dotando primero a \u00e9stos con una familia de estructuras geom\u00e9tricas (filtraci\u00f3n simplicial). Luego, mediante distintas herramientas del \u00e1lgebra lineal, se realiza el c\u00e1lculo de lo que en topolog\u00eda algebraica es conocido como homolog\u00eda persistente (definida en 2002 por Edelsbrunner, Letscher y Zomorodian) y que consiste de una familia de espacios vectoriales apropiadamente construidos; tal estructura algebraica es representada gr\u00e1ficamente en un c\u00f3digo de barras o en un diagrama de persistencia (Carlsson et al<\/em>.,\u00a02004). Dependiendo de la manera en la que se construye la estructura simplicial filtrada, se tiene una correspondiente interpretaci\u00f3n de lo que el c\u00f3digo de barras est\u00e1 detectando.<\/p>\r\n\r\n\r\n\r\n\r\n
Cada uno de los pasos del ATD se\u00f1alado en la figura 1 representa un \u00e1rea de investigaci\u00f3n actualmente activa, y entrar en mayores detalles escapa de los objetivos del presente escrito, por lo que nos enfocaremos en la primera parte del ATD: la construcci\u00f3n de una estructura simplicial filtrada asociada a una nube de puntos (los datos). Identificar la estructura adecuada con la cual dotar de geometr\u00eda a los datos es uno de los aspectos clave y no triviales para realizar el an\u00e1lisis.<\/p>\r\n\r\n\r\n\r\n
LA FORMA DE LOS DATOS<\/h4>\r\n\r\n\r\n\r\n El ATD se realiza bajo la hip\u00f3tesis de que los datos encajan en cierto modelo salvo ruido, esto es, que existe una estructura geom\u00e9trica y el correspondiente sistema de ecuaciones que la modela, de donde los datos han sido muestreados salvo cierto ruido, y es tarea del ATD inferir dicho espacio mediante la detecci\u00f3n de ciertas caracter\u00edsticas relativas a su forma. Por ejemplo,en la figura 2 se muestran tres nubes de puntos representadasen el plano. Intuitivamente podemos inferir la geometr\u00eda del modelo subyacente en cada caso: en la nube de puntos de la izquierda, la experiencia dicta utilizar un modelo de regresi\u00f3n lineal; para las otras dos nubes de puntos, es claro que el espacio subyacente no tiene una estructura lineal, m\u00e1s bien del tipo peri\u00f3dico para la gr\u00e1fica del centro y de agrupamiento para la gr\u00e1fica de la derecha.<\/p>\r\n\r\n\r\n\r\n
\r\n
DISTINTAS GEOMETR\u00cdAS SOBRE UNA NUBE DE PUNTOS<\/h4>\r\n\r\n\r\n\r\nEl complejo simplicial de Vietoris-Rips<\/h4>\r\n\r\n\r\n\r\n Dada una nube de puntos N={?1,…,?\u207fN<\/em>, es\u00a0construir la gr\u00e1fica cuyo conjunto de v\u00e9rtices\u00a0N<\/em>\u2080\u00a0consta de todos los subconjuntos unitarios {?\u1d62\u00a0} de N<\/em>, y el conjunto de aristas N<\/em>\u2081\u00a0consiste de los subconjuntos de N<\/em> con dos elementos {?i<\/sub>, ?j<\/sub>} \u2282\u00a0N <\/em>que satisfacen que la distancia entre ambos puntos es menor o igual que \u03b5. Podemos considerar a \u00e9sta como una estructura de dimensi\u00f3n simplicial 1. Para construir una estructura geom\u00e9trica de mayor dimensi\u00f3n simplicial, definimos por cada n\u00famero natural k<\/em>\u22650 el conjunto\u00a0N<\/em>k<\/em><\/sub>\u00a0dado por la colecci\u00f3n de todos los subconjuntos con k<\/em>\u00a0+ 1 elementos {?i0<\/sub>,…, ?ik\u00a0<\/sub>} \u2282\u00a0N<\/em> que satisfacen que la distancia entre cada par de elementos es menor o igual que \u03b5. El\u00a0complejo simplicial de Vietoris-Rips\u00a0<\/em>VR (N<\/em>,\u03b5) es la uni\u00f3n de todos los N<\/em>? (Ghrist, 2007, p. 63), y la dimensi\u00f3n simplicial de este complejo corresponde al valor m\u00e1ximo de k<\/em> tal que N<\/em>k<\/em><\/sub>\u00a0es no vac\u00edo. Los elementos en N<\/em>k<\/em><\/sub>\u00a0son llamados k<\/em>-simplejos de Vietoris-Rips.<\/p>\r\n\r\n\r\n\r\nNotemos que si la nube de puntos pertenece a un espacio euclidiano N<\/em>\u00a0\u2282\u00a0\u211d\u1d48, entonces la estructura simplicial de Vietoris-RipsVR<\/em>(N<\/em>, \u03b5) puede reformularse en t\u00e9rminos debolas en\u00a0\u211d\u1d48\u00a0de la siguiente manera: \u03c3 \u2208\u00a0VR<\/em>(N<\/em>,\u03b5) si y s\u00f3lo si B<\/em>(x\u1d62, \u03b5\u20442)\u2229B<\/em>(xj<\/sub>, \u03b5\u20442)\u2260\u2205 para todos\u00a0xi<\/sub>, xj<\/sub>\u2208\u03c3, donde B<\/em>(x,r<\/em>) ={y \u2208\u00a0\u211d\u1d48: dist<\/em>(?,y<\/em>)\u2a7dr} y dist<\/em> representa la distancia euclidiana. Equivalentemente, \u03c3\u2208VR<\/em>(N<\/em>,\u03b5) si y s\u00f3lo si su di\u00e1metro diam<\/em>(\u03c3)=m\u00e1x<\/em>{dist(?i<\/sub>, ?j <\/sub>):?i<\/sub>, ?j<\/sub> \u2208\u03c3} es menor o igual que \u03b5.<\/p>\r\n\r\n\r\n\r\nEn este contexto, un k<\/em>-simplejo \u03c3={?i0<\/sub>,…, ?ik<\/em>\u00a0<\/sub>} \u2208\u00a0VR<\/em> (N<\/em>,\u03b5), cuyos puntos est\u00e1n en posici\u00f3n general, puede identificarse con la envolvente convexa\u0394[?i0<\/sub>,…, ?ik<\/em> <\/sub>]\u00a0del conjunto \u03c3 \u2282\u00a0\u211d\u1d48, esto es, el m\u00ednimo subconjunto convexo en\u211d\u1d48\u00a0que contiene a \u03c3. El conjunto \u0394[?i0<\/sub>,…, ?ik <\/sub>] es llamado una realizaci\u00f3n geom\u00e9trica del k<\/em>-simplejo \u03c3 = {?i0<\/sub>,…, ?ik<\/em>\u00a0<\/sub>}. Para valores peque\u00f1os de k<\/em> es posible visualizar tales realizaciones geom\u00e9tricas como se muestra en la figura 3, donde la realizaci\u00f3n geom\u00e9trica de un 0-simplejo corresponde a un punto, la de un 1-simplejo a un segmento de l\u00ednea, la de un 2-simplejo a un tri\u00e1ngulo y la de un 3-simplejo a un tetraedro.<\/p>\r\n\r\n\r\n\r\n\r\n
El complejo simplicial de Cech<\/h4>\r\n\r\n\r\n\r\n La siguiente estructura simplicial, definida tambi\u00e9n para una nube de puntos N<\/em> \u2282 \u211dd<\/sup> y un par\u00e1metro de proximidad \u03b5\u22650, es llamada complejo de Cech, denotada por C<\/em>(N<\/em>,\u03b5), y es una variante del complejo de Vietoris-Rips que es de hecho una representaci\u00f3n m\u00e1s fiel de la geometr\u00eda subyacente de los datos (Ghrist, 2007, p. 63). Los k-simplejos de Cech son definidos de la siguiente manera: \u03c3={?i0<\/sub>,…, ?ik<\/sub>} \u2208 C<\/em>(N<\/em>,\u03b5) si y s\u00f3lo si B<\/em>(?i0<\/sub>,\u03b5\u20442)\u2229…\u2229B<\/em>(?ik<\/sub>,\u03b5\u20442)\u2260\u2205. En equivalencia, \u03c3 \u2208 C<\/em>(N<\/em>,\u03b5) si puede acotarse por una bola de di\u00e1metro menor o igual que \u03b5. Podemos observar que los 0-simplejos y los 1-simplejos de Cech coinciden con los de Vietoris-Rips. Para k\u22652 todo k-simplejo \u03c3\u2208C<\/em>(N<\/em>,\u03b5) satisface que \u03c3\u2208VR<\/em>(N<\/em>,\u03b5), es decir, C<\/em>(N<\/em>,\u03b5) \u2282VR<\/em>(N<\/em>,\u03b5), pero la contenci\u00f3n es propia en general. Este cambio en la definici\u00f3n de los k-simplejos de Cech con respecto a la estructura de Vietoris-Rips tiene importantes implicaciones en los costos computacionales al momento de construir la estructura simplicial, aun cuando la estructura simplicial de Cech tiene en general una menor cantidad de simplejos que la de Vietoris-Rips (pues para su construcci\u00f3n se debe analizar el subconjunto formado por la intersecci\u00f3n de bolas). Sin embargo, su uso est\u00e1 justificado por ser una representaci\u00f3n m\u00e1s fiel de la geometr\u00eda subyacente de los datos (Ghrist, 2007, p. 63). Adem\u00e1s, la estructura simplicial de Cech aparece de manera natural en distintos estudios, como el an\u00e1lisis de redes (Yuchen, Jialiang y Martins, 2018; Le et al<\/em>., 2017).<\/p>\r\n\r\n\r\n\r\nESTRUCTURA FILTRADA DE CECH Y EL PROBLEMA DE LA BOLA MINIMAL<\/h4>\r\n\r\n\r\n\r\n Como comentamos en la secci\u00f3n anterior, para determinar si\u03c3={?i0<\/sub>,…, ?ik<\/sub>} es un simplejo en la estructura de Cech C<\/em>(N<\/em>,\u03b5), basta con comprobar la existencia de una bola de di\u00e1metro \u03b5 que encierre al subconjunto \u03c3 \u2282\u00a0\u211d\u1d48. Es claro que, para distintos valores del par\u00e1metro de proximidad, tenemos distintas estructuras simpliciales asociadas, como podemos ver en la figura 4, donde cada v\u00e9rtice corresponde a la ubicaci\u00f3n de cada una de las antenas:<\/p>\r\n\r\n\r\n\r\nEl enfoque que aborda el ATD consiste en no fijar un valor para el par\u00e1metro de proximidad \u03b5, sino considerar todos los valores del par\u00e1metro en cierto rango junto con las correspondientes estructuras simpliciales generadas, a fin de identificar aquellas propiedades geom\u00e9tricas que m\u00e1s persisten a trav\u00e9s de esta familia.<\/p>\r\n\r\n\r\n\r\n
Es claro que si \u03b51\u2a7d\u03b5\u2082, entonces C<\/em>(N<\/em>,\u03b5\u2081) \u2282\u00a0C<\/em>(N<\/em>,\u03b5\u2082). Debido a esta propiedad, la estructura simplicial de Cech tiene una estructura filtrada de manera natural:\u00a0C<\/em>(N<\/em>,\u03b5\u2080=0) \u2282\u00a0C<\/em>(N<\/em>,\u03b5\u2081) \u2282…\u2282 C<\/em>(N<\/em>,\u03b5\u029f=\u03b5). Podemos reescribir\u00a0C<\/em>(N<\/em>,\u03b5\u1d62) ={\u03c3 \u2208\u00a0C<\/em>(N<\/em>,\u03b5):\u00a0diam<\/em>(M-B<\/em>(\u03c3))\u2a7d\u03b5\u1d62}, donde\u00a0MB<\/em>(\u03c3) \u2282\u00a0\u211d\u1d48\u00a0denota la bola de radio m\u00ednimo que acota al subconjunto finito \u03c3, de modo que el estudio de la estructura simplicial filtrada de Cech est\u00e1 \u00edntimamente relacionado con el problema de determinar la bola minimal para colecciones de puntos \u03c3={?i0<\/sub>,…, ?ik<\/sub>} con k<\/em>\u2a7dn<\/em>. Encontrar el centro y radio m\u00ednimo de la bola que acote una colecci\u00f3n finita de puntos \u03c3 \u2282\u00a0\u211d\u1d48\u00a0es conocido como el problema de la bola minimal<\/em> (miniball problem<\/em>, en ingl\u00e9s). Este problema ha sido resuelto usando t\u00e9cnicas muy variadas (Fischer, G\u00e4rtner y Kutz, 2003; G\u00e4rtner, 1999).<\/p>\r\n\r\n\r\n\r\nUN ALGORITMO PARA EL C\u00c1LCULO DE LA BOLA MINIMAL<\/h4>\r\n\r\n\r\n\r\n En esta secci\u00f3n presentamos dos algoritmos ad hoc<\/em> para calcular la bola minimal para colecciones de tres o cuatro puntos \u03c3, en un espacio euclidiano de dimensi\u00f3n arbitraria. El punto clave de los algoritmos consiste en identificar cu\u00e1ndo la bola minimal coincide con una bola circunscrita a \u03c3, o bien a un subconjunto de \u03c3 en espec\u00edfico. En la siguiente secci\u00f3n mostraremos la comparaci\u00f3n en tiempos con respecto al algoritmo dado por Fischer, G\u00e4rtner y Kutz (2003), que puede manejar eficientemente conjuntos arbitrarios de puntos en dimensiones altas. Nos referiremos a tal algoritmo como \u201cminibola\u201d. Los algoritmos propuestos en este trabajo, llamados\u00a0MB<\/em>\u2083\u00a0y\u00a0MB<\/em>\u2084, reciben una colecci\u00f3n de tres y cuatro puntos, respectivamente, y calculan la bola minimal\u00a0MB<\/em>(\u03c3) que acota a \u03c3.<\/p>\r\n\r\n\r\n\r\nColecciones de tres puntos<\/h4>\r\n\r\n\r\n\r\n Para una colecci\u00f3n de tres puntos \u03c3 \u2282\u00a0\u211d\u1d48\u00a0s\u00f3lo se presentan dos casos para\u00a0MB<\/em>(\u03c3): (i) cuando la bola minimal coincide con la bola circunscrita\u00a0CB<\/em>([?\u2081,?\u2082]) de los dos puntos m\u00e1s separados ?\u2081\u00a0y ?\u2082, (ii<\/em>) cuando coincide con la bola circunscrita del tri\u00e1ngulo formado por los tres puntos\u00a0CB<\/em>([?\u2081,?\u2082,?\u2083]). Para poder distinguir qu\u00e9 caso debe usarse para el c\u00e1lculo de la bola minimal, s\u00f3lo es necesario verificar el signo del producto escalar \u27e8?\u2081-?\u2083,?\u2082-?\u2083\u27e9; en cualquiera de los dos casos, el problema de encontrar la bola circunscrita se puede resolver con f\u00f3rmulas expl\u00edcitas (Guti\u00e9rrez-Moya, 2018). Esquem\u00e1ticamente, el algoritmo queda descrito como sigue:<\/p>\r\n\r\n\r\n\r\nAlgoritmo\u00a0MB<\/em>\u2083\u00a0Entrada:\u00a0<\/strong>tres puntos \u03c3 = {?\u2081,?\u2082,?\u2083} \u2282\u00a0\u211d\u1d48\u00a0en el espacio euclidiano de dimensi\u00f3n d.\u00a0Salida:\u00a0<\/strong>la bola minimal\u00a0MB(\u03c3).\u00a0Renombrar\u00a0<\/strong>los puntos de \u03c3={?\u2081,?\u2082,?\u2083} de tal forma que dist<\/em>(?\u2081,?\u2082)=diam<\/em>(\u03c3).\u00a0Si\u00a0<\/strong>\u27e8?\u2081-?\u2083,?\u2082-?\u2083\u27e9 \u2264 0,\u00a0entonces<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0MB<\/em>(\u03c3)=CB<\/em>([?\u2081,?\u2082,?\u2083]),en otro caso\u00a0<\/strong>MB<\/em>(\u03c3)=CB<\/em>([?\u2081,?\u2082,?\u2083]).\u00a0Regresar\u00a0<\/strong>MB<\/em>(\u03c3).<\/p>\r\n\r\n\r\n\r\nColecciones de cuatro puntos<\/h4>\r\n\r\n\r\n\r\n El algoritmo\u00a0MB<\/em>\u2084 recibe una colecci\u00f3n de cuatro puntos\u03c3={?\u2081,?\u2082,?\u2083,?\u2084} \u2282 \u211d\u1d48, y proporciona la bola minimal que acota \u03c3. En este caso, la bola minimal corresponde a la bola circunscrita de alguno de los siguientes conjuntos: (i<\/em>) los puntos m\u00e1s alejados, (ii<\/em>) los v\u00e9rtices de alguna de las cuatro caras (tri\u00e1ngulos) del tetraedro formado por \u03c3, (iii<\/em>) el tetraedro \u0394[?\u2081,?\u2082,?\u2083,?\u2084]. De modo que, esencialmente, el algoritmo MB<\/em>\u2084 consiste en iterar el algoritmo\u00a0MB<\/em>\u2083\u00a0para subconjuntos de tres puntos. Esto implica que su tiempo de c\u00f3mputo sea proporcional al del algoritmo\u00a0MB<\/em>\u2083. M\u00e1s expl\u00edcitamente, el algoritmo\u00a0MB<\/em>\u2084 tiene el siguiente pseudoc\u00f3digo.<\/p>\r\n\r\n\r\n\r\nAlgoritmo\u00a0MB<\/em>\u2084\u00a0Entrada:\u00a0<\/strong>cuatro puntos \u03c3={?\u2081,?\u2082,?\u2083,?\u2084} \u2282\u00a0\u211d\u1d48\u00a0en el espacioSalida:\u00a0<\/strong>la bola minimal\u00a0MB<\/em>(\u03c3).\u00a0Renombrar\u00a0<\/strong>los puntos de \u03c3={?\u2081,?\u2082,?\u2083,?\u2084} de tal forma dist<\/em>(?\u2081,?\u2082)=diam<\/em>(\u03c3).\u00a0Si\u00a0<\/strong>\u27e8?\u2081-?\u2083,?\u2082-?\u2083\u27e9\u22640 y \u27e8?\u2081\u2013?\u2084, ?\u2082\u2013?\u2084\u27e9\u22640\u00a0entonces\u00a0<\/strong>MB<\/em>(\u03c3)=CB<\/em>([?\u2081,?\u2082]),\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0ir al Paso (3)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/strong>\u00a0 \u00a0en otro caso \u00a0\u00a0<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0para\u00a0<\/strong>i<\/em>=1\u00a0hasta\u00a0<\/strong>i<\/em>=4\u00a0hacer<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0definir\u00a0<\/strong>N<\/em>\u1d62=\u03c3 \u2013?\u1d62si\u00a0<\/strong>x\u1d62\u00a0\u2208 MB<\/em>(N<\/em>\u1d62)\u00a0entonces<\/strong>MB<\/em>(\u03c3)=MB<\/em>(N\u1d62)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ir al Paso (3)<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 fin para<\/strong>calcular<\/strong>\u00a0MB<\/em>(\u03c3)=CB<\/em>([?\u2081,?\u2082,?\u2083,?\u2084])Regresar\u00a0<\/strong>MB(\u03c3).<\/p>\r\n\r\n\r\n\r\nEs importante mencionar que en la codificaci\u00f3n (en C++) del algoritmo\u00a0MB<\/em>\u2084\u00a0es posible reutilizar varios de los c\u00e1lculos necesarios para las iteraciones en el\u00a0paso 2; adem\u00e1s, todos los productos escalares pueden ser calculados a partir de las distancias entre los puntos en \u03c3. Lo anterior impacta significativamente en la disminuci\u00f3n de los tiempos de c\u00f3mputo en dimensiones altas.<\/p>\r\n\r\n\r\n\r\nEXPERIMENTACI\u00d3N COMPUTACIONAL<\/h4>\r\n\r\n\r\n\r\n A continuaci\u00f3n, presentamos una comparaci\u00f3n entre los tiempos de c\u00f3mputo de los algoritmos\u00a0MB<\/em>\u2083\u00a0y\u00a0MB<\/em>\u2084, con respecto al algoritmo propuesto por Fischer, G\u00e4rtner y Kutz (2003) al que nos referimos por \u201cminibola\u201d; todos codificados en el lenguaje C++. En la gr\u00e1fica de arriba de la figura 5 se muestran los tiempos promedio de ejecuci\u00f3n de los algoritmos\u00a0MB<\/em>\u2083\u00a0y minibola, con respecto a la dimensi\u00f3n del espacio ambiente; en la gr\u00e1fica de abajo se comparan los tiempos promedio de\u00a0MB<\/em>\u2084\u00a0y minibola.<\/p>\r\n\r\n\r\n\r\n\r\n
La experimentaci\u00f3n computacional se realiz\u00f3 sobre espacios euclidianos de dimensi\u00f3n d<\/em>=50k<\/em>, con k<\/em>=1,2,…,200. Para cada uno de tales valores d<\/em>\u00a0se generaron 10,000 nubes de puntos {?\u2081,?\u2082,?\u2083} \u2282 \u211d\u1d48, donde cada ?\u1d62 \u2208 \u211d\u1d48\u00a0consiste de d\u00a0<\/em>n\u00fameros en el intervalo [0,10] elegidos aleatoriamente, y se calcularon los correspondientes tiempos promedio de ejecuci\u00f3n de\u00a0MB<\/em>\u2083\u00a0y minibola; y an\u00e1logamente para la comparaci\u00f3n entre los algoritmos MB<\/em>\u2084\u00a0y minibola.<\/p>\r\n\r\n\r\n\r\nLos c\u00e1lculos se realizaron ejecutando un proceso por cada hilo sobre un procesador Intel Xeon E5-2698v4 a 2.2 GHz. El uso de memoria RAM fue m\u00ednimo. La experimentaci\u00f3n muestra que el algoritmo minibola es de orden cuadr\u00e1tico, lo cual es consistente con lo presentado en Fischer, G\u00e4rtner y Kutz (2003). Por otro lado, los algoritmos MB<\/em>\u2083\u00a0y\u00a0MB<\/em>\u2084\u00a0son de orden lineal y el tiempo promedio de c\u00f3mputo es del orden 10\u207b\u2075, \u00a0 aproximadamente. Tanto los fundamentos matem\u00e1ticos como los c\u00f3digos en C++ de este trabajo pueden consultarse en Guti\u00e9rrez-Moya, 2018.<\/p>\r\n\r\n\r\n\r\nCONCLUSI\u00d3N<\/h4>\r\n\r\n\r\n\r\n En la primera parte de este trabajo describimos c\u00f3mo puede dotarse de distintas geometr\u00edas a una base de datos, vista como una nube de puntos, mediante dos de las estructuras m\u00e1s usuales: los complejos simpliciales de Vietoris-Rips y de Cech. Posteriormente enunciamos el problema de la bola minimal y comentamos su relevancia para la construcci\u00f3n de la filtraci\u00f3n del complejode Cech. Concluimos con la propuesta de dos algoritmos\u00a0MB<\/em>\u2083\u00a0y\u00a0MB<\/em>\u2084, cuyas complejidades son de orden lineal y que permiten calcular los simplejos de Cech de dimensi\u00f3n simplicial dos y tres de manera sumamente eficiente, aun cuando la nube de puntos pertenece a un espacio euclidiano de dimensi\u00f3n alta.<\/p>\r\n\r\n\r\n\r\nLa desventaja de los algoritmos\u00a0MB<\/em>\u2083\u00a0y\u00a0MB<\/em>\u2084\u00a0es que no son adecuados para generalizarse a dimensi\u00f3n simplicial arbitraria. Aun cuando la codificaci\u00f3n en el lenguaje de programaci\u00f3n se vuelve bastante sofisticada, realmente el obst\u00e1culo principal radica en la complejidad algor\u00edtmica. Por ejemplo, si construimos el algoritmo\u00a0MB<\/em>\u2085\u00a0siguiendo la misma metodolog\u00eda que para\u00a0MB<\/em>\u2083\u00a0y\u00a0MB<\/em>\u2084, entonces tal algoritmo iterar\u00eda cinco veces al algoritmo\u00a0MB<\/em>\u2084, el cual, a su vez, itera cuatro veces a\u00a0MB<\/em>\u2083; en general,\u00a0MB<\/em>?\u00a0estar\u00eda iterando n<\/em>\u22c5(n\u00a0<\/em>–\u00a01)\u22c5…\u22c54 veces a MB<\/em>\u2083\u00a0y la eficiencia que se mostr\u00f3 en la secci\u00f3n relativa a la experimentaci\u00f3n computacional se ver\u00eda significativamente disminuida, incluso para valores de n<\/em> no muy grandes.<\/p>\r\n\r\n\r\n\r\nPor otro lado, aunque una gran cantidad de los datos que se generan actualmente en nuestra sociedad son de naturaleza altamente multidimensional, los aspectos que suelen estudiarse en una primera instancia en el an\u00e1lisis topol\u00f3gico de datos son los relativos a la clasificaci\u00f3n (an\u00e1lisis de cl\u00faster<\/em>) y si la variabilidad de los datos puede ser representada significativamente mediante un modelo peri\u00f3dico de baja dimensi\u00f3n simplicial. Sin embargo, un an\u00e1lisis topol\u00f3gico de una base de datos multivariada que requiera una estructura simplicial de Cech tendr\u00e1, en general, una cantidad considerable de k<\/em>-simplejos de Cech y su an\u00e1lisis mediante las librer\u00edas usuales ser\u00e1 computacionalmente costoso, es aqu\u00ed donde radica la importancia para el ATD de contar con algoritmos eficientes como
![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura-1024x164.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura2-2.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura3-2.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura4-2-1024x194.png\")
<\/figure>\r\n\r\n\r\n\r\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura5.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\n