marzo 2005

El Modelo del Espacio Vectorial (I): similitud entre vectores.

representación de la función del coseno para calcular la similitud de dos vectores de documentos en recuperación de información

En algunas partes de este sitio web hablamos de Gerad Salton y de «su Modelo del Espacio Vectorial que implementan la mayoría de los motores de búsqueda lo implementan como estructura de datos y que el alineamiento suele realizarse en función del parecido (o similitud) de la pregunta con los documentos almacenados. Viniendo hacia el trabajo me he parado a pensar que igual muchos no saben cómo funciona realmente este modelo y que no sería nada malo dedicarle una pequeña serie de posts para explicarlo. Vamos a ello.

La idea básica de este modelo reside en la construcción de una matriz (podría llamarse tabla) de términos y documentos, donde las filas fueran estos últimos y las columnas correspondieran a los términos incluidos en ellos. Así, las filas de esta matriz (que en términos algebraicos se denominan vectores) serían equivalentes a los documentos que se expresarían en función de las apariciones (frecuencia) de cada término. De esta manera, un documento podría expresarse de la manera d1=(1, 2, 0, 0, 0, … … …, 1, 3) siendo cada uno de estos valores el número de veces que aparece cada término en el documento. La longitud del vector de documentos sería igual al total de términos de la matriz (el número de columnas).

De esta manera, un conjunto de m documentos se almacenaría en una matriz de m filas por n columnas, siendo n el total de términos almacenamos en ese conjunto de documentos. La segunda idea asociada a este modelo es calcular la similitud entre la pregunta (que se convertiría en el vector pregunta, expresado en función de la aparición de los n términos en la expresión de búsqueda) y los m vectores de documentos almacenados. Los más similares serían aquellos que deberían colocarse en los primeros lugares de la respuesta.

¿Cómo se calcula esta similitud? Disponemos de varias fórmulas que nos permiten realizar este cálculo, la más conocida es la Función del Coseno, que equivale a calcular el producto escalar de dos vectores de documentos (A y B) y dividirlo por la raíz cuadrada del sumatorio de los componentes del vector A multiplicada por la raíz cuadrada del sumatorio de los componentes del vector B.

representación de la función del coseno para calcular la similitud de dos vectores de documentos en recuperación de información

No hay que asustarse a la hora de oir hablar de «producto escalar de dos vectores», ya que se calcula multiplicando componente a componente y sumando los productos. Así, si disponemos de los vectores de documentos A (1, 0, 1, 0, 1, 0) y B (1, 0, 1, 1, 0, 0) su valor de similitud según la función del Coseno se calculará tal como podemos ver en la siguiente tabla:

tabla de ejemplo de cálculo de la función de similitud del coseno

De esta manera tan sencilla se calcula este valor de similitud. Como es obvio, si no hay coincidencia alguna entre los componentes, la similitud de los vectores será cero ya que el producto escalar será cero (circunstancia muy frecuente en la realidad ya que los vectores llegan a tener miles de componentes y se da el caso de la no coincidencia con mayor frecuencia de lo que cabría pensar). También es lógico imaginar que la similitud máxima sólo se da cuando todos los componentes de los vectores son iguales, en este caso la función del coseno obtiene su máximo valor, la unidad. Lo normal es que los términos de las columnas de la matriz hayan sido filtrados (supresión de palabras vacías) y que en lugar de corresponder a palabras, equivalgan a su raíz ‘stemmed’ (agrupamiento de términos en función de su base léxica común, por ejemplo: economista, económico, economía, económicamente, etc.). Generalmente las tildes y las mayúsculas/minúsculas son ignorados. Esto se hace para que las dimensiones de la matriz, de por sí considerablemente grandes no alcancen valores imposibles de gestionar. No obstante podemos encontrar excepciones a la regla general, tal como parece ser el caso de Yahoo!, que no ignora las palabras vacías.

Para finalizar, la del coseno no es la única función de similitud. Existen otras, entre las que destacan las de Dice y Jaccar, pero que pueden resultar algo más engorrosas no sólo de calcular sino más bien de interpretar y que por tanto son menos aplicadas en Recuperación de Información