« Clustering por K-medi… « || Inicio || » Curso MOOC de NetLogo… »

Mapas semánticos: clasificación y representación

Última modificación: 14 de Diciembre de 2013, y ha tenido 1553 vistas

Etiquetas utilizadas: || || || ||

El problema de la clasificación de objetos es, a grandes rasgos, uno de los problemas centrales de la investigación y donde, quizás de forma más clara, podemos observar la posible mezcla de metodologías provenientes de diversas áreas de estudio.

Una vez que establecemos el concepto de objeto como entidad abstracta que abarca cualquier elemento de un dominio (y que puede ir desde una función matemática hasta una obra de arte, una corriente de pensamiento o un trozo de código de programación), y le agregamos un conjunto de características diferenciables que permiten individualizar los objetos que son nuestro foco de estudio, cualquier análisis que permita diferenciar dichos objetos por medio de estas características nos acerca a un problema de clasificación.

Así, la Geometría (como área de la Matemática) es en gran medida el conjunto de metodologías para clasificar los objetos geométricos (formas, curvas, …); la Literatura es el conjunto de metodologías para clasificar las obras literarias; la Física es el conjunto de metodologías para clasificar el comportamiento de los cuerpos; etc…
Por supuesto, y para evitar una simplificación excesiva, debe indicarse que es en esa generación de las diversas metodologías donde las distintas áreas de estudio toman cuerpo propio y se convierten en disciplinas con rasgos únicos. Gran parte de estas metodologías específicas consiste en decidir qué características son las fundamentales para el análisis de los objetos propios del dominio y en establecer técnicas que permitan medir cualitativa y cuantitativamente dichas características.

En lo que sigue presentamos una metodología de clasificación que se sitúa en un paso posterior al análisis pormenorizado de dichos dominios. Una vez decididas las características que definen nuestros objetos y medidos sus valores para cada uno de ellos, aplicamos una serie de pasos que nos permiten obtener una representación acerca de las posibles clasificaciones que dichas características proporcionan sobre los objetos de estudio.

Una proto-metodología para la clasificación

Buscamos una primera aproximación a una metodología general que ayude a arrojar luz en esa etapa de la clasificación de objetos de un dominio, sobre todo en aquellos dominios en los que los objetos de estudio son lo suficientemente complejos como para que no se hayan establecido unas líneas claras de ejecución o no haya consenso acerca de cuáles son las características básicas que definen sus objetos de estudio.

Imaginemos que tenemos un conjunto de objetos (que, como hemos dicho, puede ser cualquier cosa, desde una obra de arte hasta un personaje de una red social, una comedia o un paquete de software), y que usamos un conjunto de descriptores para referenciar cada uno de los objetos. Por ejemplo, una determinada comedia puede tener como descriptores algo como:

 

El médico de su honra

El galán fantasma

Casa con dos puertas

Aventura

7

38

22

Peligro

23

63

33

Confrontación

30

36

50

Romance

12

12

19

Religioso

0

0

0

Fiesta

0

0

0

Fin de obra

0

1

0

Rescate

0

0

0

Petición

7

0

0

Demostración

1

0

0

Celebración

0

0

0

Invitación

0

0

0

Donde los números que hay en cada fila muestran el número de veces que se presenta una situación del tipo indicado (entre las 12 posibilidades que se dan). Si fijamos los descriptores que usamos para caracterizar los objetos podemos representar cada una de las comedias anteriores de la siguiente forma:

El médico de su honra = (7, 23, 30, 12, 0, 0, 0, 0, 7, 1, 0, 0)

El galán fantasma = (38, 63, 36, 12, 0, 0, 1, 0, 0, 0, 0, 0)

Casa con dos puertas = (22, 33, 50, 19, 0, 0, 0, 0, 0, 0, 0, 0)

O lo que en términos matemáticos se conoce como vectores. Normalmente, este tipo de vectores necesitarán un espacio de 12 dimensiones para representarlos gráficamente (ya que tienen 12 distintas coordenadas). Si el objeto solo usara 2 descriptores, podríamos representarlo en un espacio de 2 dimensiones como sigue (usando el valor de cada descriptor en cada una de las coordenadas):

Pero al tener 12 posibles coordenadas, necesitaríamos de un espacio de 12 dimensiones para poder representarlos, algo que no podemos representar gráficamente en el espacio de 3 dimensiones en el que vivimos.

Además, una vez que asociamos un punto del espacio (sea de la dimensión que sea) a cada uno de nuestros objetos, podemos medir la distancia existente entre ellos, por ejemplo, usando la fórmula de distancia euclídea que se muestra en la siguiente imagen:

De esta forma, objetos que tengan descriptores similares, tendrán asociados vectores similares, y por tanto ocuparán puntos del espacio cercano. Pero, si nuestra descripción usa más de 3 descriptores, ¿cómo podemos usar entonces esta información si no somos capaces de representarla?

Una primera aproximación para responder a esta pregunta nos viene de la mano de un método llamado Multi-Dimensional Scaling (MDS), que nos permite, a partir de las distancias relativas entre puntos de una determinada dimensión, representarlos de forma “suficientemente adecuada” en dimensiones inferiores. En el siguiente ejemplo mostramos este método aplicado a un conjunto de 6 objetos que hacen uso de 4 descriptores (por lo que necesitaríamos 4 dimensiones para una representación fiel):

Aplicando un método similar al anterior para un conjunto de 12 comedias que hacen uso de los descriptores que se mostraron en la tabla obtenemos la siguiente representación bidimensional de los puntos asociados a las obras:

Donde se puede observar cómo, únicamente considerando los descriptores anteriores, obtenemos que debe existir cierta cercanía entre obras como El galán fantasma, El escondido y la tapada y La devoción de la cruz, o entre obras como El Faetonte, El castillo de Lindabridis y La fiera, el rayo y la piedra.

Por supuesto, teniendo en cuenta que los objetos sobre los que tratamos pueden ser de una complejidad considerable, no podemos esperar que este método proporcione una herramienta muy exacta a la hora de clasificar todos los objetos, ya que debe tenerse en cuenta siempre qué conjunto de descriptores se han usado y la metodología que se ha seguido para decidir el valor de dichos descriptores.

Pero además de representar la cercanía de los objetos en función del vector de descriptores que tienen, podemos extender un poco el estudio anterior para analizar qué relación hay entre los descriptores que se han usado.

Desde un punto de vista informal, un método para conseguir visualizar las relaciones entre los descriptores consiste en los siguientes pasos:

  • Realizar el proceso anterior para representar los objetos en el plano 2D intentando mantener la relación de distancias con un error lo más bajo posible (en general, no se puede esperar que no haya error).
  • Imaginar que cada uno de esos objetos es una especie de antena de radio que “emite” cada uno de sus descriptores a su alrededor con una fuerza proporcional al “peso” de ese descriptor en el objeto.
  • Repetir la operación anterior con cada uno de los descriptores, dando como resultado un mapa de superficies superpuestas que refleja la relación de uso entre los descriptores. Finalmente, las superficies obtenidas pueden representarse como superposición de “placas” o como mezcla de superficies traslúcidas.

Desde un punto de vista técnico, solo diremos aquí que estas áreas representan las superficies potenciales de un campo de fuerzas generado por cargas de distintas propiedades colocadas en los puntos que representan los objetos.

Esta última representación es lo que se conoce como mapa semántico, pues establece relaciones semánticas entre los objetos que estamos estudiando. En la actualidad este tipo de representaciones se denominan Semantic landscapes, y entre las herramientas más populares para generarlos destacan los Self-Organization Maps (SOM), que inventó Kohonen a mediados de los años 90.

 

Algunas consideraciones técnicas

En esta sección se profundiza un poco más en los métodos técnicos que permiten obtener los resultados anteriores.

¿Cómo se organizan los objetos (vectores) de forma que se puedan proyectar en un plano a pesar de ser elementos de dimensiones superiores?

No vamos a explicar el método MDS que se utiliza generalmente porque requiere de muchos conocimientos técnicos y su implementación no resulta sencilla, sino un método alternativo que, si bien no da los mismos resultados y puede ser menos eficiente cuando el número de objetos a representar es muy elevado, es de muy sencilla implementación en ciertos entornos (por ejemplo, aquellos como NetLogo en los que el trabajo con nodos y aristas es “natural”) y ofrece algunas ventajas inestimables, como es la robustez a la nueva inclusión de objetos en tiempo real y una pre-visualización de los resultados.

Esencialmente, el método consiste en lo siguiente:

  1. Asociamos a cada uno de los vectores un nodo de un grafo.
  2. Unimos todos los nodos entre sí (es decir, el resultado será un grafo completo), asignando como peso de cada arista la distancia que hay entre los vectores asociados a los nodos que une.
  3. Situamos aleatoriamente los nodos en el espacio 2D (realmente, se pueden situar en cualquier espacio, por lo que el mismo procedimiento puede representar los vectores en un espacio 3D, por ejemplo).
  4. Calculamos el error de cada arista, \(a=(v_1,v_2)\), como \(e(a)=|d(v_1,v_2)-long(a)|\), y el error total del sistema como la suma de los errores de todas las aristas.
  5. Tomamos una arista al azar y acercamos/alejamos sus extremos una cantidad proporcional al error de la arista, dependiendo de si \(d(v_1,v_2) < long(a)\) o \(d(v_1,v_2) > long(a)\), como si la arista fuera un muelle con una longitud ideal.
  6. Repetimos el paso 5 mientras se considere necesario.

Nota 1: Con el fin de alcanzar un error suficientemente bajo, puede ser necesario realizar “sacudidas” aleatorias de todos los nodos del grafo debido a que puede caer en un mínimo local que no sea suficientemente óptimo.

Nota 2: De alguna forma, este método es similar al “spring layout” o “force layout” habitual a la hora de representar grafos, con la diferencia de que en nuestro método la longitud de cada arista puede ser distinta, mientras que en los métodos anteriores todas las aristas tienen la misma longitud por defecto (que se equilibra con fuerza de repulsión entre los nodos del grafo).

¿Cómo se calculan las superficies ocupadas por los distintos descriptores?


El procedimiento es bastante natural y se basa en un concepto muy sencillo de la física: los campos de fuerza, o lo potenciales.


« Clustering por K-medi… « || Inicio || » Curso MOOC de NetLogo… »