Archivo por meses: agosto 2009

The Google Similarity Distance

Leyendo un artículo me encuentro una referencia a un interesante trabajo: “The Google Similarity Distance”, de Cilibrasi y Vitanyi publicado en IEEE Trans. on Knowledge and Data Engineering.

Los autores presentan una nueva medida de similitud semántica entre dos palabras, es decir, cuánto se parecen o en qué medida están relacionados dos términos. Las medidas de distancia entre elementos de muy diversa índole se emplean asiduamente en técnicas de minería de datos que basan sus operaciones a partir de una distancia conocida entre las instancias tratadas, como puede ser el clustering (agrupamiento de instancias similares) o la clasificación basada en la proximidad de ejemplares conocidos (como KNN).

La novedad de este trabajo es que se propone el uso de Google para calcular la similitud o relación entre dos palabras dadas, defendiéndose que la Web es el mayor recurso de información existente, donde está representado en gran medida el conocimiento humano de forma actualizada. De forma muy resumida, proponen la siguiente fórmula para calcular la similitud entre dos palabras x,y (NGD=Normalized Google Distance):
formula NGD
Donde f(x) y f(y) son el número de páginas devueltas por Google buscando el término x e y, respectivamente. f(x,y) denota el número de páginas devueltas por Google donde aparecen ambas palabras. N es un factor de normalización que suele representar la totalidad de páginas web indexadas por Google. Los autores en sus pruebas manejaron valores entre 8·109 y 9·109, aunque dicen que los resultados suelen ser insensibles a este valor, siempre que sea razonable. El valor de la fórmula toma valor 0 para palabras totalmente similares y tiende a infinito para palabras no relacionadas.

En el trabajo se pueden ver ejemplos muy ilustrativos de la aplicabilidad de la medida. Uno de ellos, demuestra la capacidad de diccionario “enciclopédico” que aporta Google, ya que es capaz de calcular similitudes entre términos más allá de los de un diccionario convencional. Así pues, ejecutan un agrupamiento jerárquico sobre los títulos de obras de diversos autores y, gracias a la similitud calculada que tiende a acercar títulos de un mismo autor (por aparecer juntos en páginas donde se habla de la obra de un autor), el algoritmo crea efectivamente grupos con obras de un mismo autor.

Dejo aquí el artículo completo en PDF.