Similitud topológica de usuarios Aplicación a los sistemas de recomendación Jesús Serrano Fernando Díez Alejandro Bellogín UIMP Universidad Autónoma de Madrid Universidad Autónoma de Madrid Santander, España Madrid, España Madrid, España serranopriego@posgrado.uimp.es fernando.diez@uam.es alejandro.bellogin@uam.es ABSTRACT1 forma que se puede clasificar la forma de un espacio por la conexión entre sus elementos. La topología es la rama de las Matemáticas que analiza los En el trabajo que presentamos estudiamos las propiedades de los conjuntos desde un punto de vista diferente, estudiando su forma, conjuntos de usuarios de un sistema de recomendación desde el transformaciones, relaciones, etc. Tradicionalmente, en el estudio punto de vista de la forma que tienen dichos conjuntos. y desarrollo de sistemas de recomendación, los algoritmos Convencionalmente, los perfiles de los usuarios se representan implementados, las métricas empleadas, los métodos de mediante secuencias de valores, en forma de vector, que describen evaluación, etc. están basados en el uso de los datos desde una las preferencias de estos para cada uno de los ítems del sistema. perspectiva Euclídea, la cual difiere completamente de la En sistemas basados en contenido o contextuales, los perfiles representación topológica de los mismos. En el presente artículo incorporan, adicionalmente, valores referidos a atributos del exponemos una línea de trabajo en la que los perfiles de usuarios usuario o del contexto. Todos estos conjuntos de valores se pasan a contemplarse como espacios topológicos. Para poder combinan haciendo uso de diferentes algoritmos para resolver las comprender a los usuarios desde un punto de vista topológico nos tareas habituales de recomendación, como el cálculo de hemos centrado en su caracterización usando sus correspondientes similitudes entre usuarios o la predicción de ratings. Pues bien, a números de Betti. Estos números representan una propiedad diferencia de este uso convencional de los datos, exploramos una característica de los conjuntos. A partir de esta y otras perspectiva diferente basada en la forma de los conjuntos y en las propiedades se definen caracterizaciones como, por ejemplo, los características de los mismos. Nos centraremos en el cálculo de códigos de barras. Cada código de barras representa, desde un los denominados números de Betti, los cuales representan punto de vista topológico, un perfil de usuario. Mediante el características invariantes como son el número de componentes cálculo de similitudes basadas en códigos de barras comparamos conexas o el número de agujeros en la estructura. En la Figura 1 perfiles. Esta nueva perspectiva del tratamiento de datos es parte se muestra la metodología que sigue el TDA para, a partir de un de lo que se denomina Análisis Topológico de Datos y abre conjunto de datos S (en forma de nube de puntos en un espacio n- nuevas perspectivas para el tratamiento de perfiles de usuario y la dimensional), aproximar una representación sólida K, con la que mejora de la personalización de productos y servicios. se obtienen sus invariantes topológicas. KEYWORDS Sistemas de Recomendación, Análisis Topológico de Datos, Modelado de usuario, Códigos de Barras, Números de Betti. 1 Introducción El Análisis Topológico de Datos (o TDA, por sus siglas en inglés) es un área de la topología computacional que desarrolla técnicas para el análisis de datos desde la perspectiva de la Topología, Figura 1. Cálculo de invariantes de un conjunto [2]. rama de las Matemáticas que estudia las propiedades invariantes En (a) se representa el conjunto de datos en el espacio. En (b) se de los conjuntos cuando se aplican transformaciones continuas muestra la estructura asociada al conjunto de puntos. En (c) se como traslaciones o rotaciones [1]. Las propiedades que tienen calculan sus invariantes topológicas (aquí se muestra un ciclo). estos conjuntos que no cambian al aplicar este tipo de A partir de las propiedades invariantes que caracterizan los transformaciones se llaman invariantes topológicas. Una de las conjuntos se pueden realizar diferentes tratamientos de datos invariantes que más se estudia en topología es la conexión, de empleando los algoritmos, técnicas, métricas, etc. existentes en el contexto del TDA. En particular, en este artículo exploramos el uso de una nueva forma de representación de perfiles de usuario 1 Copyright © 2020 for this paper by its authors. Use permitted mediante técnicas TDA que dan lugar a estructuras que los under Creative Commons License Attribution 4.0 International caracterizan, denominadas códigos de barras, así como al cálculo (CC BY 4.0). de similitudes entre usuarios mediante una métrica específica CIRCLE '20, July 6–9 , 2020, Samatan, Gers, France J. Serrano et al. diseñada para comparar los códigos de barras. Además hemos Como decíamos antes, la Topología es la rama de las matemáticas comparado las métricas basadas en la similitud con códigos de que estudia las propiedades de los denominados espacios barras frente a baseline estándar obteniendo resultados que, aun topológicos, que permanecen inalteradas bajo transformaciones o siendo mejorables, resultan prometedores. deformaciones continuas. En un espacio topológico podemos construir estructuras y analizar sus propiedades invariantes, en 2 Antecedentes particular los números de Betti. Una de las estructuras que frecuentemente se emplean son los n- La topología computacional se ha aplicado en distintos ámbitos en simplex. Un n-simplex x es un conjunto de puntos el mundo de la ciencia, como podemos comprobar en [2]. Por geométricamente independientes de un espacio 𝑅 ! . Sobre los n- ejemplo, en el contexto de procesamiento de imágenes, se suele simplex (también denominados simplex), podemos identificar considerar una imagen como un rectángulo formado por píxeles, caras, como subconjuntos de puntos que forman parte del propio blancos y negros, donde los negros representan la imagen y los simplex, los cuales son, a su vez, nuevos simplex. Se denomina blancos el fondo. Una vez pixelada la imagen, se pueden definir Complejo Simplicial K en 𝑅 ! a una colección de simplex en 𝑅 ! diferentes tipos de conexiones entre píxeles. Por ejemplo, dos tales que: píxeles están conectados si comparten aristas o si comparten 1. Cada cara de un simplex de K está en K. aristas o vértices, etc., produciendo como resultado algo similar a 2. La intersección de cualesquiera dos simplex de K es una un esqueleto de la imagen. Una vez obtenido el mismo se está en cara de cada uno de ellos, y por tanto, está en K. condiciones de estudiar el objeto representado desde un punto de La Figura 3 muestra un ejemplo de complejo simplicial en el que vista topológico. se identifican 0-simplex (cada uno de los puntos del conjunto), 1- En cartografía, una práctica común consiste en la deformación de simplex (cada arista del conjunto), 2-simplex (cada triángulo un mapa, en la que están delimitadas ciertas zonas, generando sombreado). El cuadrado blanco del centro es un agujero de áreas deformadas de cada zona en función de una propiedad (por dimensión 1. ejemplo, deformar el mapa de los Estados Unidos en función de los votos existentes en cada estado). A este tipo de mapas se les denomina cartogramas. Esta técnica ofrece una mayor información visual sobre lo que se quiere representar. Estas prácticas se realizan empleando transformaciones topológicas que deforman las regiones del mapa de acuerdo con ciertas propiedades de las transformaciones y de los conjuntos sobre las que se aplican. Un ejemplo común de este tipo de técnicas es la Figura 3. Complejo simplicial [2]. deformación que se aplica sobre una taza para demostrar su Para construir un complejo simplicial sobre un conjunto de puntos equivalencia topológica (homeomorfa) a una rosquilla (Figura 2). existen diferentes alternativas basadas, generalmente, en el El concepto de homeomorfismo se resume en la equivalencia por recubrimiento de los puntos mediante secuencias de bolas transformaciones como, por ejemplo, un cambio de escala, un giro centradas en cada punto y de radios incrementales. Dependiendo o una traslación de puntos. del método escogido generamos diferentes complejos simpliciales. Uno de los más sencillos de generar, incluso en dimensiones altas, es el complejo simplicial de Vietoris-Rips [4]. Consiste, básicamente, en ir uniendo puntos con aristas, a partir de la nube inicial de puntos, a medida que vamos incrementando el radio de las bolas centradas en cada uno de los puntos y estas se van intersecando. En la Figura 4 se ejemplifica el proceso. Figura 2. Taza y rosquilla homeomorfos [2]. En biología, el estudio de la forma de las proteínas puede ayudar en la comprensión de enfermedades y el desarrollo de medicamentos [3]. Para estudiar las proteínas se representa cada uno de sus átomos en el espacio y se analizan sus formas y conexiones. Este estudio puede realizarse con un enfoque geométrico o topológico. El enfoque geométrico se centra en la forma que tiene la molécula viéndola como una figura tridimensional. Sin embargo, el enfoque topológico se centra más Figura 4. Creación de complejos 𝑪𝜺 𝒊 , con radios 𝜺𝒊 [2]. en las conexiones existentes entre los átomos. En (a) se generan aristas entre los puntos cuyas correspondientes 3 Fundamentos teóricos bolas de radio 𝜀! se intersecan. Para dicho radio en la nube de CIRCLE '20, July 6–9 , 2020, Samatan, Gers, France J. Serrano et al. puntos se generan 3 complejos simpliciales no conexos entre sí: representan los agujeros de dimensión 1. No hay huecos por lo un 0-simplex formado por un punto aislado, un 1-simplex, que no habría barras asociadas. formado por dos puntos unidos y un 5-simplex formado por 5 puntos unidos por aristas. En (b) el radio de las bolas se incrementa de modo que 𝜀! > 𝜀! y se comprueba cómo se generan aristas entre los tres complejos simpliciales anteriores dando lugar a un único complejo simplicial sin partes no conexas (desunidas). A los complejos simpliciales podemos asociarles los valores cuantificables que mencionábamos anteriormente: el número de componentes que son independientes de otras (no conexas), el número de agujeros en las superficies y el número de huecos entre las estructuras. En topología a estas propiedades se les da nombres concretos. Son los números de Betti de dimensión cero, uno y dos, respectivamente. Estos valores representan propiedades invariantes muy importantes que ayudan a distinguir entre complejos simpliciales. Comparando los correspondientes valores de distintos objetos sólidos podemos determinar si tienen, o no, la misma topología (es decir, si son equivalentes desde un punto de vista topológico). La idea que proponemos es representar los perfiles de los usuarios como esos objetos sólidos, de forma que sean comparables entre ellos mediante algún tipo de medida de similitud que expondremos más adelante. Figura 5. Códigos de barras de un complejo simplicial [3]. El siguiente paso, una vez definidos los complejos simpliciales, es calcular los correspondientes números de Betti. Y para ello vamos 3.1 Similitudes basadas en códigos de barras a emplear una representación gráfica denominada códigos de Una vez hemos calculado los códigos de barras procedemos con el barras. Las barras son representaciones gráficas de los intervalos estudio de la similitud entre dos objetos representados por dichos de los radios sobre los que persisten las características topológicas códigos. Basándonos en la similitud de Jaccard, definida para dos (componentes, agujeros y huecos). El conjunto de estas barras !∩! conjuntos no vacíos M y N como 𝑆! 𝑀, 𝑁 = , podemos caracteriza la forma en que la topología del objeto cambia a !∪! medida que se va representando el complejo simplicial. La forma calcular una medida de similitud basada en esta expresión que en que se elaboran estos códigos se puede encontrar explicada con promedie las similitudes máximas entre todos los posibles pares detalle en [5] y, en la Figura 5, se muestra, de manera gráfica, la de similitudes de Jaccard entre barras de ambos conjuntos. Esta visualización del código de barras asociado a un conjunto de similitud promedio del solapamiento de códigos de barras puntos a medida que construimos su complejo simplicial (Barcode Overlapping) se define como asociado. El código de barras hemos de interpretarlo del siguiente modo: 1. Cada instancia de cada componente, cada agujero y cada 1 𝑎∩𝑏 𝑎∩𝑏 𝑆!" 𝐴, 𝐵 = sup + sup (1) hueco se representa con una línea. 𝐴 + 𝐵 !∈! 𝑎 ∪ 𝑏 !∈! 𝑎 ∪ 𝑏 !∈! !∈! 2. La posición y longitud de cada barra representa el ciclo de vida de cada componente, agujero y hueco. Puede darse la circunstancia de que los conjuntos a comparar 3. El inicio de la barra representa el radio en que la instancia carezcan de agujeros y huecos. Estos casos se pueden gestionar correspondiente comienza su vida. ampliando la definición anterior a los casos correspondientes a 4. El otro extremo de la barra representa el radio en que la alguno de los conjuntos A o B, o ambos A y B, vacíos. De este instancia correspondiente cesa su vida. modo se define la siguiente expresión general de la similitud En el ejemplo de la Figura 5, inicialmente hay catorce puntos y basada en códigos de barras extendida (Barcode Overlapping catorce barras con origen en la abscisa 0 (en color verde). Al Extended) alcanzar radio 0.75 dos puntos se unen mediante una arista y, en consecuencia, quedan trece barras correspondientes a trece 𝑆!" 𝐴, 𝐵 , 𝑠𝑖 𝐴 ≠ ∅ 𝑦 𝐵 ≠ ∅ componentes (doce puntos y una arista uniendo dos puntos). Y así 𝑆!"# 𝐴, 𝐵 = 1 𝑠𝑖 𝐴 = ∅ 𝑦 𝐵 = ∅ (2) sucesivamente. A medida que los radios crecen se van uniendo 0 𝑒𝑛 𝑐𝑎𝑠𝑜𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜𝑠 componentes y van desapareciendo barras, hasta quedar una sola Los valores de similitudes de las diferentes invariantes barra, a partir de la abscisa 2.2, de la única componente conexa (componentes, agujeros o huecos) se pueden combinar mediante que queda a partir de dicho radio. También podemos observar dos alguna función monótona creciente (por ejemplo el promedio) que barras entre las abscisas 2.4 y 3.7 (en color morado). Estas barras mantenga el orden de clasificación entre objetos, es decir, si un par de objetos es más similar en todos los diferentes códigos de CIRCLE '20, July 6–9 , 2020, Samatan, Gers, France J. Serrano et al. barras que otro par de objetos, la similitud unificada resultante Con los códigos de barras de todos los usuarios calculados, debería ser mayor para el primer par. estamos en condiciones de obtener, para cada par de usuarios ∀ 𝑢, 𝑣 ∈ 𝒰; 𝑢 ≠ 𝑣 del conjunto, su similitud 𝑆!"# 𝑢, 𝑣 . Hemos restringido el cálculo de similitudes a usuarios con menos 4 Experimentación y conclusiones de 50 ratings, dado que es muy costoso computacionalmente En este artículo, además de exponer brevemente el marco general calcular códigos de barras para usuarios con valores mayores. teórico que estamos interesados en explorar, explicamos un Esto supone un contratiempo para estudiar la eficiencia de la ejemplo sencillo que hemos desarrollado con el fin de comprender métrica 𝑆!"# , pues nos estamos restringiendo a usuarios con el problema. Hemos empleado datos del dataset MovieLens 100k, perfiles relativamente pequeños. En [7] se analizan alternativas formado por 100000 ratings, 943 usuarios (miembros del conjunto para optimizar el cálculo de complejos simpliciales, de momento 𝒰) y 1682 items. Convencionalmente los perfiles de los usuarios dejamos el estudio de esas u otras alternativas como trabajo se representan mediante vectores de ratings n-dimensionales. En futuro. En nuestro caso, hemos hecho estimaciones del cálculo de nuestro caso consideraremos los usuarios como colecciones de error RMSE [8] con diferentes parametrizaciones del algoritmo puntos (ítem, valor) en el plano. A partir de dichas colecciones de obteniendo la comparativa que se muestra en la tabla siguiente, puntos podemos construir sus complejos simpliciales asociados a usando un algoritmo básico kNN. cada usuario, obteniendo posteriormente sus invariantes asociadas a los códigos de barras generados para cada uno de ellos. En la 𝑆!"# 𝑆!"# Similitud Coseno Pearson Random Figura 6 se muestra el proceso de construcción del complejo 50 20 100 15 simplicial para un usuario con 3 ratings. RMSE 1.1616 1.1482 1.0791 1.5728 1.1217 Tabla 1. Métricas de error Como se puede comprobar, los valores obtenidos para las similitudes basadas en los códigos de barras tienen un comportamiento razonablemente competitivo, incluso frente a métricas muy consolidadas como Coseno o Pearson, basadas en correlaciones entre los objetos comparados [8, 9], lo cual puede interpretarse como que esta métrica puede ser buena cuando las métricas colaborativas funcionan peor, cuando hay pocos datos. Figura 6. Construcción del complejo simplicial de un usuario Además, es interesante la comparación con el método random, el cual devuelve un valor aleatorio entre un máximo y un mínimo El cálculo de la similitud entre usuarios basada en su códigos de para expresar la similitud entre usuarios, para mostrar que esta barras se ha realizado en Matlab empleando la librería JavaPlex, similitud no está devolviendo datos al azar. dedicada al cálculo de invariantes de complejos simpliciales [6]. En adelante queremos estudiar el comportamiento de esta métrica Se pueden hacer muchas consideraciones sobre el modo en que se de manera más exhaustiva cuando los usuarios tienen pocos datos. representan los usuarios. En nuestro caso hemos optado por la Esto puede ser particularmente interesante para problemas de más intuitiva, aun no siendo probablemente la mejor desde el cold-start. Hemos de complementar este análisis con otros punto de vista del rendimiento del sistema. datasets, otros algoritmos basados en teoría de grafos, Una vez obtenidos los complejos simpliciales asociados a cada optimización u obtención de invariantes, así como otras métricas usuario calculamos sus códigos de barras y sus invariantes. La de similitud y de ranking habituales en el área. Figura 7 muestra el código de barras de la invariante de dimensión 0 para el usuario anterior. Este usuario no presenta invariantes de AGRADECIMIENTOS dimensiones 1 (agujeros) ni 2 (huecos). Investigación en el marco del proyecto BIBECA (RTI2018- 101248-B-I00) financiado por MINECO/FEDER. REFERENCIAS [1] James R Munkres. 1984. Elements of algebraic topology. (volume 2). Addison- Wesley Menlo Park. [2] Afra Zomorodian, 2012. Topological data analysis. Advances in applied and computational topology, 70:1–39. [3] Gabriell Máté, Andreas Hofmann, Nicolas Wenzel, and Dieter W Heermann, 2014. A topological similarity measure for proteins. Biochimica et Biophysica Acta (BBA)-Biomembranes, 1838(4):1180–1190. Figura 7. Código de barras de dimensión 0. [4] Afra Zomorodian. 2010. Fast construction of the Vietoris-Rips complex. In Computers and Graphics, 34:263–271. [5] Robert Ghrist, 2008. Barcodes: the persistent topology of data. Bulletin of the American Mathematical Society. Vol. 45(1), 61-75. CIRCLE '20, July 6–9 , 2020, Samatan, Gers, France J. Serrano et al. [6] Andrew Tausz, Mikael Vejdemo-Johansson, and Henry Adams, 2014. JavaPlex: A research software package for persistent (co)homology. Proceedings of ICMS 2014, Lecture Notes in Computer Science 8592, 129–136. Software available at http://appliedtopology.github.io/javaplex/ [7] Otter, N., Porter, M. A., Tillmann, U., Grindrod, P., & Harrington, H. A. (2017). A roadmap for the computation of persistent homology. EPJ Data Science, 6(1), 17. [8] Xia Ning, Christian Desrosiers, George Karypis. A comprehensive survey of neighborhood-based recommendation methods. Recommender Systems Handbook, (2nd. ed.) 37–76. [9] Marko Balabanović and Yoav Shoham. Fab: content-based, collaborative recommendation. Communications of the ACM, Vol. 40(3), 66-72.