Recuperación difusa

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Las técnicas de recuperación difusa están basadas en el Modelo Booleano Extendido y en la teoría de Conjuntos Difusos. Hay dos modelos clásicos de recuperación difusa: Mínimo y Máximo Mixto (MMM - Mixed Min and Max) y el modelo de Paice. Ambos modelos no proveen una vía para la evaluación ponderada de las consultas, lo cual si es considerado por el algoritmo norma-P.


Modelo Mixto Mínimo y Máximo (MMM)[editar]

En la teoría de conjuntos difusos, un elemento tiene un variado grado de pertenencia, digamos dA, a un conjunto A dado en vez de la opción de pertenencia tradicional (es un elemento/ no es un elemento).
En el MMM[1] cada término indexado tiene asociado un conjunto difuso. El peso de un documento con respecto a un término indexado A es medido por el grado de pertenencia del documento en el conjunto difuso asociado con A. El grado de pertenencia para la unión y la intersección está definido en la teoría de conjuntos difusos como sigue:

d_{A\cap B}= min(d_A, d_B)
d_{A\cup B}= max(d_A,d_B)

De acuerdo a esto, los documentos que deberían ser recuperados para una consulta de la forma A o B, deberían estar en el conjunto difuso asociado con la unión de los dos conjuntos A y B. Similarmente, los documentos que deberían ser recueprados para una consulta de la forma A y B, deben estar en el conjunto difuso asociado con la intersección de los dos conjuntos. Por ello, es posible definir la similitud de un documento para la consulta o como max(dA, dB) y la similitud de un documento con la consulta y como min(dA, dB). El modelo MMM intenta suavisar los operadores Booleanos al considerar la similitud consulta-documento como una combinación lineal del mínimo y máximo de los pesos de los documentos.

Dado un documento D con los pesos de los términos indexados dA1, dA2, ..., dAn para los términos A1, A2, ..., An, y las consultas:

Qo = (A1 o A2 o ... o An)
Qy = (A1 y A2 y ... y An)

la similitud documento-consulta en el modelo MMM se calcula como sigue:

SlM(Qo, D) = Co1 * max(dA1, dA2, ..., dAn) + Co2 * min(dA1, dA2, ..., dAn)
SlM(Qy, D) = Cy1 * min(dA1, dA2, ..., dAn) + Cy2 * max(dA1, dA2 ..., dAn)

donde Co1, Co2 son coeficientes "suaves" para el operador o, y Cy1, Cy2 son coeficientes suaves para el operador y. Puesto que queremos dar más importancia al máximo de los pesos de los documentos mientras consideremos una consulta o y mayor importancia al mínimo cuando consideremos una consulta y, generalmente tendremos Co1 > Co2 y Cy1 > Cy2. Por simplicidad se asume generalmente Co1 = 1 - Co2 y Cy1 = 1 - Cy2.

Los experimentos de Lee y Fox[2] indican que la mayor eficiencia usualmente ocurre con Cy1 en el rango [0.5, 0.8] y con Co1 > 0.2. En general, el costo computacional de MMM es bajo, y la efectividad de recuperación es mucho mejor que con el Modelo Estándar Booleano.

El modelo de Paice[editar]

El modelo de Paice[3] es una extensión general para el modelo MMM. En comparación con el modelo MMM que considera solo los pesos mínimo y máximo para los términos indexados, el modelo de Paice incorpora todos los pesos de los términos cuando calcula la similitud:

S(D,Q) = \sum_{i=1}^n\frac{r^{i-1}*w_{di}}{\sum_{j=1}^n 
r^{j-1}}

donde r es un coeficiente constante y wdi es organizado en orden ascendente para consultas y, y en orden descendente para consultas o. Cuando n = 2 el modelo Paice muestra el mismo comportamiento que el modelo MMM.

Los experimentos de Lee y Fox[2] han mostrado que estableciendo r en 1.0 para las consultas y, y en 0.7 para las consultas o proporcionan una buena efectividad en la recuperación. El costo computacional para este modelo es mayor que para el modelo MMM. Esto es porque el modelo MMM solo necesita la determinación del mínimo o máximo de un conjunto de pesos de términos cada vez que una cláusula y u o es considerada, lo cual se puede hacer en O(n). El modelo Paice requiere que los pesos de los términos sean ordenados en orden ascendente o descendente, dependiendo si es considerada una cláusula y o una cláusula o. Esto requiere como míninmo

un algoritmo de ordenación O(n log n). También es necesario
un buen trato en los cálculos de punto flotante.

Mejoramientos en el modelo Estándar Booleano[editar]

Lee y Fox[2] compararon el modelo Estándar Booleano con los modelos MMM y Paice con tres colecciones de prueba: CISI, CACM, y INSPEC. Estos son los resultados reportados para el mejoramiento del promedio de la precisión media:

CISI CACM INSPEC
MMM 68% 109% 195%
Paice 77% 104% 206%

Estos son mejoras muy buenas sobre el modelo Estándar. MMM es muy cercano a los resultados de Paice y noma-P, lo cual indica que puede ser una técnica muy buena, y es la más eficiente de las tres.

Trabajo reciente[editar]

Recientemente Kang et al..[4] ha inventado un sistema de recuperación difusa indexado por indentificación de conceptos.

Si miramos en documentos sobre un aproximamiento puro de Tf-idf, incluso eliminando los stop words, habrán palabras más relevantes con el tópico del documento que otras y tendrán el mismo peso porque tienen la misma frecuencia de términos. Si tomamos en cuenta la intención del usuario sobre una consulta podemos mejorar el peso de los términos de un documento. Cada término puede identificarse como un concepto en una cierta cadena léxica que traduce la importancia de ese concepto para ese documento.
Reportaron mejoras sobre Paice y norma-P sobre la precisión promedio y el recobrado de los 5 mejores documentos recuperados.

Zadrozny[5] revisó el modelo de recuperación de información difusa. Adicionalmente extendió el modelo Booleano extendido difuso:

  • asumiendo términos lingüísticos como pesos importantes de las

palabras claves también en los documentos

  • tomando en cuenta la concerniente incertidumbre en la representación

de documentos y consultas

  • interpretando los términos lingüísticos en la representación de

los documetos y consultas así como su emparejamiento en los términos de la lógica difusa de Zadeh (cálculos de declarciones lingüísticas)

  • localizando algunos aspectos pragmáticos del modelo propuesto,

notablemente las técnicas de indexado de documentos y consultas

El modelo propuesto hace posible capturar impresición e incertidumbre concerniente a la representación y recuperación de información textual.

Ver también[editar]

Lectura adicional[editar]

  • Fox, E.; S.

Betrabet , M. Koushik , W. Lee (1992), [http://www.scribd.com/doc/13742235/Information-Retrieval-Data-Structures-Algorithms-William-B-Frakes Information Retrieval: Algorithms and Data structures; Extended Boolean model], Prentice-Hall, Inc., http://www.scribd.com/doc/13742235/Information-Retrieval-Data-Structures-Algorithms-William-B-Frakes 

Referencias[editar]

  1. Fox, E. A.; S. Sharat (1986), A Comparison of Two Methods for Soft Boolean Interpretation in Information Retrieval, Technical Report TR-86-1, Virginia Tech, Department of Computer Science 
  2. a b c Lee, W. C.; E. A. Fox (1988), Experimental Comparison of Schemes for Interpreting Boolean Queries 
  3. Paice, C. P. (1984), Soft Evaluation of Boolean Search Queries in Information Retrieval Systems, Information Technology, Res. Dev. Applications, 3(1), 33-42 
  4. Kang, Bo-Yeong; Dae-Won Kim, Hae-Jung Kim (2005), [http://www.springerlink.com/content/ac96v4qf4f8adatp/ Fuzzy Information Retrieval Indexed by Concept Identification], Springer Berlin / Heidelberg, http://www.springerlink.com/content/ac96v4qf4f8adatp/ 
  5. Zadrozny, Sławomir; Nowacka, Katarzyna (2009), Fuzzy information retrieval model revisited, Elsevier North-Holland, Inc., doi:10.1016/j.fss.2009.02.012