miércoles, mayo 23, 2007

Recuperación de información: Preprocesamiento II

(Fernando Bordignon y Gabriel Tolosa, extracto del libro "Introducción a la Recuperación de Información", 2004)

3.3 – Indexación en base a técnicas no lingüisticas

Como se mencionó, un documento indexado es una representación del documento original. En la práctica, consiste en una lista de términos o conceptos normalizados, de alto valor semántico, con información adicional asociada (por ejemplo, su frecuencia de aparición o posición en el texto). Los términos pertenecientes al índice pueden estar en su forma original o lematizados y pueden ser palabras simples, multipalabras, siglas o nombres propios.

En general, la indexación de base no lingüística se fundamenta en el análisis de la frecuencia de los términos y su distribución dentro de los documentos. Este análisis tiene como objeto establecer criterios que permitan determinar si una palabra es un término de indexación válido, fundamentalmente porque permite discriminar el contenido de los documentos y – de alguna manera – aporta información. Para ello, se han estudiado y determinado algunas propiedades estadísticas del texto escrito que determinan cómo se distribuyen las frecuencias de aparición de las diferentes palabras en una colección y cómo crece el tamaño del vocabulario conforme crece tal colección. Existen dos leyes empíricas que describen estas propiedades: la ley de Zipf y la ley de Heaps, que presentamos a continuación.

3.3.1 – Ley de Zipf

Además de la eliminación de palabras vacías el vocabulario de una colección puede ser podado utilizando otros criterios. Uno de los más utilizados corresponde a la denominada “Ley de Zipf” [66], quien realizó una serie de estudios empíricos en la década de 1940 que demostraron que la gente al es cribir – normalmente – suele preferir palabras más conocidas sobre aquellas menos conocidas. A esto lo denominó s e lo conoce como la ley del menor esfuerzo.

Zipf descubrió que si se armaba una lista con las palabras, junto con su cantidad de ocurrencias (en documentos en inglés), y se la ordenaba por frecuencia de mayor a menor, se cumplía que la frecuencia de la i-esima palabra multiplicada por i (el ranking), era igual a una constante C, es decir:

C = ranking del término t * frecuencia termino t

Hoy en día, para documentos recientemente escritos, esta ley se cumple si se eleva i a un exponente mayor que 1 (en textos en inglés es 1.8), lo cual indica una creciente pobreza en la utilización de la lengua.

Gráfica de representación de la frecuencia de términos del libro Tom Sawyer

Al graficar la curva utilizando una escala logarítmica en x e y, se obtiene una recta con pendiente negativa.

Gráfica logarítmica de representación de la frecuencia de términos del libro Tom Sawyer

En la tabla siguiente se muestra el cálculo de la constante C sobre algunos términos que forman el vocabulario del libro Tom Sawyer. Nótese que en los primeros lugares aparecen términos del conjunto de las palabras vacías.

Otros trabajos de investigación han demostrado que la ley de Zipf se aplica a otras situaciones relacionadas con la recuperación de información. Para Baeza Yates [http://www.dcc.uchile.cl/~rbaeza/inf/zipf.html] en el espacio web existen fenómenos como los siguientes:

  • · Tamaños de los archivos que transfiere el protocolo HTTP.
  • · Número de enlaces que salen de una página.
  • · Número de enlaces que llegan a una página.
  • · Fecha de actualización de las páginas, existen más páginas nuevas o modificadas que viejas.
  • · Frecuencia de acceso a páginas web.

El comportamiento del vocabulario de acuerdo a la ley de Zipf brinda indicios acerca de la utilidad de los términos. En 1958, Luhn [34] sugirió que las palabras que describen de mejor forma el contenido se encuentran en un área comprendida entre las altamente frecuentes y las muy raras (baja frecuencia) y lo ilustró con la siguiente gráfica:
Las divisiones verticales definen una zona de transición entre las palabras de frecuencia muy alta y las de muy baja. Aquí se encuentran los términos con mayor contenido semántico de un documento.

El límite superior corresponde – generalmente – al comienzo de las palabras vacías y – como mencionamos – no se indexan por no tener poder de discriminación. Por otro lado, el limite inferior corresponde al comienzo de las palabras más raras, y no se incluyen en el vocabulario debido a que existe una baja probabilidad que el usuario las use en una consulta. Estas palabras de baja frecuencia son las que denotan la riqueza y el estilo de vocabulario del autor o bien, corresponden a errores de ortografía y para establecer su frecuencia límite se sugiere: a) Eliminar aquellos términos que estén en 3 o menos documentos y b) Eliminar todas las palabras
que ocurren una o dos veces [39].

3.3.2 – Ley de Heaps

De manera similar a la ley de Zipf, existe otra ley empírica que describe el comportamiento de los términos dentro de un texto escrito denominada ley de Heaps. En esta ley, se plantea una relación entre el tamaño del texto (cantidad de palabras) y el crecimiento del vocabulario (cantidad de palabra únicas). En particular, postula que el tamaño del vocabulario (y su crecimiento) es una función del tamaño del texto.

V = K * (N^beta)

donde:

N: Es el tamaño del documento (cantidad de palabras)

K: Constante que depende del texto, típicamente entre 10 y 100.

beta: También es una constante que depende del texto, donde 0 <>
  • 10 <= K <= 20
  • 0.5 <= beta <= 0.6

Por lo tanto, si K = 20 y beta = 0.5, resulta:

N

V

100000

6325

250000

10000

400000

12649

800000

17889

1000000

20000

Nótese que el tamaño del corpus creció 10 veces, mientras que el vocabulario apenas superó las 3 veces su tamaño inicial.

Una gráfica de sus valores para diferentes tamaños de documentos, resulta similar a la siguiente:


Los resultados de la ley de Heaps plantean que a medida que se incorporan documentos a una colección, cada vez se descubrirán nuevos términos para el vocabulario.

Su aplicación es directa ya que permite estimar el tamaño del vocabulario con lo cual se puede determinar – por ejemplo – la escalabilidad de las estructuras de datos necesarias para almacenar los índices que soportan el SRI. Esto es altamente útil si se utilizará una tabla de hash en memoria para el índice.

Referencias

[34] Luhn, H.P., “The automatic creation of literature abstracts”, IBM Journal of Research and Development, 2, 1pags. 59-165. 1958.

[39] Peña, R., Baeza-Yates, R., Rodriguez, J.V. “Gestión Digital de la Información”. Alfaomega Grupo Editor. 2003.

[66] Zipf, G. K. “Human Behaviour and the Principle of Least Effort” Reading, MA: Addison- Wesley Publishing Co. 1949.


1 comentario:

Anónimo dijo...

Realmente blog informativo aquí mi amigo. Sólo quería hacer un comentario y decir que mantener el trabajo de calidad. He marcado tu ahora y voy a volver a leer más en el futuro de mi amigo! También bien elegidos los colores sobre el tema que va bien con el blog en mi modesta opinión:)