10 Recuperación de información
En recuperación de información (IR), tenemos una colección de documentos, tenemos alguna tarea o necesidad de información, y queremos utilizar la colección para resolver su tarea o su pregunta. Se formula una consulta al sistema de recuperación, y obtiene una colección de resultados (documentos recuperados) que esperamos sean relevantes para contestar su pregunta.
El desempeño del sistema de recuperación puede ser medido de distintas formas. Una de las más usuales es usar precisión y recall o exhaustividad:
- Precisión: fracción de documentos recuperados que son relevantes a la búsqueda (total de recuperados correctos o relevantes entre total recuperados).
- Exhaustividad: fracción de los documentos relevantes que son recuperados (total de recuperados correctos o relevantes entre todos los relevantes).
Evitamos usar medidas como \(\%\) de correctos, pues en cada búsqueda típicamente la fracción de documentos relevantes es pequeña, y el número de documentos recuperados también es relativamente chico. Esto quiere decir, por ejemplo, que un sistema que recupera documentos al azar típicamente tiene un \(\%\) alto de correctos, pues la mayor parte de los documentos no relevantes no son recuperados.
10.1 Recuperación booleana
El enfoque más simple es recuperación booleana: una consulta es un documento (típicamente corto) que incluye ciertas palabras \(q_1,q_2,\ldots, q_m\). Buscamos entonces todos los documentos que incluyen todas estas palabras.
Más en general, una consulta puede ser una expresión booleana en palabras. Por ejemplo:
- deportes y atletismo pero no olimpiada,
- deportes o atletismo.
En principio podríamos hacer una búsqueda lineal (grep) sobre todos los documentos, y regresar todos los que evalúan la búsqueda a verdadero. Este enfoque es poco escalable en el número de documentos (en cada búsqueda hay que recorrer la colección completa) y no existe un concepto de orden en los resultados obtenidos.
10.2 Matrices de incidencias términos-documentos
Podemos construir un índice para evitar hacer pases de los documentos cada vez que tenemos un nueva consulta. Una manera de hacerlo es construyendo la matriz \(M\) de términos documentos, donde \(M_{td} = 1\) si el término \(t\) está en el documento \(d\), y \(M_{td}=0\) en otro caso.
Con esta matriz, consultas booleanas pueden ser calculadas usando los renglones de términos:
Ejemplo
Consideramos la siguiente colección de documentos:
frases <- c('el perro y el gato viven en la casa',
'el perro juega con la pelota',
'la pelota es amarilla',
'el gato juega con la pelota y el perro juega con el gato')Construimos una matriz binaria que indica qué términos aparecen en qué documentos:
vs <- VectorSource(frases)
corpus <- VCorpus(vs)
control_pars <- list(weighting = weightBin, wordLengths = c(2, Inf))
td_sparse <- TermDocumentMatrix(corpus, control = control_pars)
td_mat <- as.matrix(td_sparse)
td_mat## Docs
## Terms 1 2 3 4
## amarilla 0 0 1 0
## casa 1 0 0 0
## con 0 1 0 1
## el 1 1 0 1
## en 1 0 0 0
## es 0 0 1 0
## gato 1 0 0 1
## juega 0 1 0 1
## la 1 1 1 1
## pelota 0 1 1 1
## perro 1 1 0 1
## viven 1 0 0 0Si queremos hacer una consulta, por ejemplo de “gato y perro pero no casa”, por ejemplo, podemos hacer lógica booleana con los vectores de términos:
## [1] "Contienen perro:"## [1] "el perro y el gato viven en la casa"
## [2] "el perro juega con la pelota"
## [3] "el gato juega con la pelota y el perro juega con el gato"## [1] "contienen perro y gato"## [1] "el perro y el gato viven en la casa"
## [2] "el gato juega con la pelota y el perro juega con el gato"## [1] "Contienen perro y cato pero no casa:"## [1] "el gato juega con la pelota y el perro juega con el gato"Observaciones:
- Como hemos visto en otros casos, no conviene usar una matriz densa. Típicamente la matriz de términos documentos es grande (podría ser fácilmente de cientos de miles por millones, por ejemplo) y rala (relativamente pocos 1’s), por lo que es mejor usar una matriz rala.
## <<TermDocumentMatrix (terms: 12, documents: 4)>>
## Non-/sparse entries: 24/24
## Sparsity : 50%
## Maximal term length: 8
## Weighting : binary (bin)## List of 6
## $ i : int [1:24] 2 4 5 7 9 11 12 3 4 8 ...
## $ j : int [1:24] 1 1 1 1 1 1 1 2 2 2 ...
## $ v : int [1:24] 1 1 1 1 1 1 1 1 1 1 ...
## $ nrow : int 12
## $ ncol : int 4
## $ dimnames:List of 2
## ..$ Terms: chr [1:12] "amarilla" "casa" "con" "el" ...
## ..$ Docs : chr [1:4] "1" "2" "3" "4"
## - attr(*, "class")= chr [1:2] "TermDocumentMatrix" "simple_triplet_matrix"
## - attr(*, "weighting")= chr [1:2] "binary" "bin"Ventajas de las búsquedas binarias: para usuarios avanzados es una técnica útil (por ejemplo, búsquedas muy particulares en documentos legales). Es fácil entender exactamente que documentos son los recuperados.
Desventajas: Menos útil cuando no sabemos exactamente qué estamos buscando. No hay una medida de ordenamiento de los resultados. No utiliza frecuencia de aparición de los términos, lo cual puede ser un indicador de relevancia.
10.3 Índice invertido
En primer lugar, mostramos la estructura estándar que se utiliza para recuperacion de documentos: el índice invertido.
El índice invertido agrupa, para cada término \(t\), todos los id’s de los documentos que lo contienen.
Ejemplo
Veamos dos maneras de calcular el índice invertido (en estos ejemplos hacemos el cálculo en memoria, pues nuestros datos son chicos):
df_frases <- data_frame(id = 1:length(frases), frase = frases) %>%
unnest_tokens(palabras, frase) %>%
group_by(id, palabras) %>%
summarise(term_frec = length(palabras)) %>%
group_by(palabras) %>%
mutate(doc_frec = length(id))## Warning: `data_frame()` is deprecated, use `tibble()`.
## This warning is displayed once per session.ii_lista <- split(df_frases, df_frases$palabras) %>%
map(function(df){ select(ungroup(df), -palabras) %>% ungroup })
ii_lista[1:3]## $amarilla
## # A tibble: 1 x 3
## id term_frec doc_frec
## <int> <int> <int>
## 1 3 1 1
##
## $casa
## # A tibble: 1 x 3
## id term_frec doc_frec
## <int> <int> <int>
## 1 1 1 1
##
## $con
## # A tibble: 2 x 3
## id term_frec doc_frec
## <int> <int> <int>
## 1 2 1 2
## 2 4 2 2Y también podríamos hacer (usando la tabla hash de los environments de R, que es más eficiente para bucar términos, como un diccionario de python):
crear_indice <- function(frases){
indice <- new.env(hash = TRUE)
for(i in 1:length(frases)){
# convertimos a tokens
tokens <- tokenizers::tokenize_words(frases[i], simplify = TRUE)
# los numeramos
tokens_f <- factor(tokens)
# contamos para tener frecuencia de ocurrencia en el doc
tokens_conteo <- tabulate(tokens_f)
nombres <- levels(tokens_f)
# agregar documentos a cada token
for(j in 1:length(tokens_conteo)){
token <- nombres[j]
indice[[token]] <- c(indice[[token]],
list(c('doc' = i, 'frec_doc' = tokens_conteo[j])))
}
}
indice
}
ii_env <- crear_indice(frases)
ii_env[["el"]]## [[1]]
## doc frec_doc
## 1 2
##
## [[2]]
## doc frec_doc
## 2 1
##
## [[3]]
## doc frec_doc
## 4 3Para construir un índice invertido de una colección de textos,
- Limpiamos la colección de textos (eliminar puntuación, HTML, etc).
- Tokenizamos los textos, convirtiendo cada documento en una colección de tokens (usando como separadores espacios en blanco y/o puntuación).
- Hacemos preprocesamiento de los tokens (por ejemplo, pasar a minúsculas, lematizar, eliminar stopwords). También podemos agregar términos como sinónimos (si aparece brincar, agregar también saltar, etc).
- Creamos el índice invertido, que consiste de un diccionario indexado por los términos, y término apunta a los indentificadores de los documentos que contienen este término (el diccionario puede estar en memoria, y contener apuntadores a archivos de disco donde estan los doc_id).
Para hacer búsquedas con el índice invertido de conjunciones de términos, encontramos los términos, e intersectamos las listas de doc_id's.
Ejemplo
Supongamos que buscamos perro y gato.
perro_y_gato <- intersect(ii_lista[["perro"]] %>% pull(id),
ii_lista[["gato"]] %>% pull(id))
frases[perro_y_gato]## [1] "el perro y el gato viven en la casa"
## [2] "el gato juega con la pelota y el perro juega con el gato"Observaciones
- Como los id's están ordenados, es posible encontrar la intersección de forma más eficiente. Ver (Manning, Raghavan, and Schütze 2008), capítulo 1.
- Piensa cómo sería el procesamiento de consultas cuando hay AND, OR, y NOT.
Más acerca del índice invertido
- Para una colección grande de documentos, el índice invertido puede tener gran tamaño, y el desempeño en recuperación debe ser bueno. El índice invertido puede, por ejemplo, estar particionado en varios nodos de un cluster. Cada nodo contiene el índice de un subconjunto de documentos. Cuando hacemos una consulta se envía a todos los nodos, y cada uno de ellos devuelve documentos candidatos para ser agregados y presentados al usuario. Ver por ejemplo Elasticsearch, y el capítulo 4 de (Manning, Raghavan, and Schütze 2008).
10.4 Modelo de espacio vectorial
Como discutimos arriba, el método de recuperación booleano tiene el defecto de que no produce ningún ordenamiento de los resultados.
En el modelo de espacio vectorial tradicional,
- Consideramos documentos (inicialmente) como vectores en un espacio de términos que contienen
- Consideramos queries o búsquedas también como documentos, así que también están representados como vectores en el espacio de términos.
- Si \(d\) es un documento, y \(q\) es una búsqueda, entonces documentos relevantes son los que tienen \(\sim(d, q)\) alto.
Podríamos considerar intentar algo como usar similitud de Jaccard entre documentos recuperados y consulta, pero esto no va a funcionar muy bien: en primer lugar, la consulta es de tamaño fijo, pero los documentos pueden variar mucho en tamaño. El coeficiente de Jaccard tendería a dar menor similitud para documentos más largos. En segundo lugar, documentos con más alta frecuencia de los términos consultados son típicamente más relevantes a la consulta, y el coeficiente de Jaccard no toma en cuenta el número de ocurrencias.
Un primer paso es ponderar cada término en un documento dependiendo del número de veces que el término aparece en el documento.
10.4.1 Ponderación por frecuencia de términos
En primer lugar, tomamos en cuenta la frecuencia de términos dentro de los documentos. Definimos \(tf_{i,d}\) como el número de veces que aparece el término (palabra) \(i\) en el documento \(d\). Podemos definir el peso de un término dentro de un documento de varias maneras:
Frecuencia \[ w_{i,d} = tf_{i,d}.\]
Log-frecuencia:
\[\begin{equation} w_{i,d}=\left\{ \begin{array}{lr} 1+ \log (tf_{i,d}), & tf_{i,d}>0\\ 0, & tf_{id}=0. \end{array} \right. \end{equation}\]
- Frecuencia normalizada \[ w_{i,d} = \frac{tf_{id}}{\max_j tf_{jd}}.\]
Denotamos por \(w_d\) el vector que contiene las frecuencias para cada término: \[w_d = (w_{1,d}, w_{2,d},\ldots, w_{m, d}).\]
Nótese que los primeros dos tienen la propiedad de dar más importancia, generalmente, a documentos más grandes, pues los términos tienden a aparecer más veces en ellos (a la inversa de lo que vimos antes). Esto no necesariamente es indeseable. La segunda opción modera el crecimiento de estos conteos a través del logaritmo.
Idea: usar distancia de coseno de los vectores de frecuencias (en lugar de 1s o 0s). Esto hace más similares documentos en los que un mismo término aparece varias veces.
Con esto podemos dar nuestra primera medida de similitud entre documentos (o entre un documento \(d\) y una consulta \(q\)):
\[sim(q, d) = \frac{< w_{q}, w_d>}{||w_d||\cdot||w_q||},\] que es igual a \[sim(q, d) = \frac{\sum_i w_{i,q} w_{i,d}} {\sqrt{\sum_i w_{i,q}^2}\sqrt{\sum_i w_{i,d}^2}},\] que es el producto punto de los vectores \(w_q\) y \(w_d\) después de normalizarlos.
Observación: nótese que para calcular distancia coseno entre los documentos de una colección y un documento query, basta:
- Calcular la matriz términos documentos ponderada por frecuencia, y normalizada para que cada columna tenga tamaño 1.
- Calcular el vector de frecuencias normalizado para el query.
- Multiplicar este último vector por la matriz términos documentos.
El vector resultante da las distancias coseno entre el documento y el query.
Ejemplo
Para nuestro minicorpus anterior:
## $encoding
## [1] ""
##
## $length
## [1] 4
##
## $position
## [1] 0
##
## $reader
## function (elem, language, id)
## {
## if (!is.null(elem$uri))
## id <- basename(elem$uri)
## PlainTextDocument(elem$content, id = id, language = language)
## }
## <bytecode: 0x55b4c51a7bf0>
## <environment: namespace:tm>
##
## $content
## [1] "el perro y el gato viven en la casa"
## [2] "el perro juega con la pelota"
## [3] "la pelota es amarilla"
## [4] "el gato juega con la pelota y el perro juega con el gato"
##
## attr(,"class")
## [1] "VectorSource" "SimpleSource" "Source"corpus <- VCorpus(vs)
control_pars <- list(weighting = weightTf, wordLengths = c(2, Inf))
td_sparse <- TermDocumentMatrix(corpus, control = control_pars)
td_sparse## <<TermDocumentMatrix (terms: 12, documents: 4)>>
## Non-/sparse entries: 24/24
## Sparsity : 50%
## Maximal term length: 8
## Weighting : term frequency (tf)## [1] "amarilla" "casa" "con" "el" "en" "es"
## [7] "gato" "juega" "la" "pelota" "perro" "viven"library(slam)
procesar_query <- function(query, vocabulario){
control_pars <- list(weighting = weightTf, wordLengths = c(2, Inf),
dictionary = vocabulario) #usar vocabulario fijo
vs <- VectorSource(query)
corpus_q <- VCorpus(vs)
td_sparse <- TermDocumentMatrix(corpus_q, control = control_pars)
td_sparse
}
vec <- procesar_query("gato perro gato", vocabulario)
inspect(vec)## <<TermDocumentMatrix (terms: 12, documents: 1)>>
## Non-/sparse entries: 2/10
## Sparsity : 83%
## Maximal term length: 8
## Weighting : term frequency (tf)
## Sample :
## Docs
## Terms 1
## amarilla 0
## casa 0
## con 0
## el 0
## en 0
## es 0
## gato 2
## juega 0
## la 0
## perro 1Ahora podemos calcular las similitudes coseno:
sim_cos <- function(x, y){
sum(x*y) / (sqrt(sum(x^2)) * sqrt(sum(y^2)))
}
similitudes <- sapply(1:ncol(td_sparse), function(j) {sim_cos(td_sparse[, j], vec) })
similitudes## [1] 0.4242641 0.1825742 0.0000000 0.4564355## [1] "el perro y el gato viven en la casa"
## [2] "el perro juega con la pelota"
## [3] "la pelota es amarilla"
## [4] "el gato juega con la pelota y el perro juega con el gato"Ejemplo
Ahora haremos prueba con nuestro corpus de fragmentos de noticias.
periodico_original <- read_lines(file = '../datos/noticias/Es_Newspapers.txt',
progress = FALSE)
length(periodico_original)## [1] 309918Nuestra función para normalizar textos será:
normalizar <- function(texto, vocab = NULL){
texto <- tolower(texto)
texto <- gsub("-", " ", texto) # separar palabras con guión
texto <- gsub("\\.[^0-9]", " ", texto) # quitar puntos
texto <- gsub("[«»;\\:\\.,'\"()¿?!¡\\-\\/]", " ", texto)
texto <- gsub("\\s+", " ", texto)
texto
}
periodico <- normalizar(periodico_original)
periodico[c(1,5,7)]## [1] "en este sentido señala que no podemos consentir que se repita el malogrado caso del centro de transportes de benavente donde la falta de control ha supuesto un cúmulo de irregularidades que rozan lo delictivo "
## [2] "la administración norteamericana no ha dado aún su aprobación pero la dirección de british espera que lo haga en breve según afirmó la empresa desde londres las compañías concernidas se comprometen a dar acceso a la competencia en determinadas franjas horarias del aeropuerto de heathrow para enlaces con nueva york boston dallas y miami "
## [3] "el doctor del área de prehistoria de la umu lomba maurandi forma parte del equipo que dirige los trabajos en el enterramiento actualmente en proceso de excavación que consiste en una cavidad de ocho por cinco metros con una profundidad de dos metros según fuentes del departamento de promoción de la investigación de la institución docente prinum consultadas por europa press "vs <- VectorSource(periodico)
corpus_noticias <- VCorpus(vs, readerControl = list(language = "es"))
td_noticias <- TermDocumentMatrix(corpus_noticias,
control = list(weighting = weightTf, wordLengths = c(2, Inf)))
vocabulario_noticias <- td_noticias$dimnames$Terms
td_noticias_tf <- weightSMART(td_noticias, spec = "nnc")Y vamos a hacer un query:
procesar_query <- function(query, vocabulario, normalizar_fun){
query <- normalizar_fun(query)
vs <- VectorSource(query)
corpus_q <- VCorpus(vs)
td_sparse <- TermDocumentMatrix(corpus_q,
control = list(weighting = weightTf,
wordLengths = c(2, Inf),
dictionary = vocabulario)) #usar vocabulario fijo
td_sparse
}
calc_sim <- function(vec, td_noticias){
norm_2 <- sqrt(col_sums(vec^2))
cross_prod <- crossprod_simple_triplet_matrix(vec, td_noticias)
print(length(norm_2))
cross_prod /norm_2
}
vec <- procesar_query("comida cocina", vocabulario_noticias, normalizar)
similitudes <- calc_sim(vec, td_noticias_tf)## [1] 1## [1] "la comida "
## [2] " brunch o comida formal "
## [3] "segundo de cocina "
## [4] " cómo cocina sus personajes "
## [5] " cómo definiría su cocina "
## [6] " hemos cerrado la cocina "
## [7] " la cocina catalana es ligera "
## [8] "hoy pronuncia la conferencia medicina en la cocina la cocina es una buena consulta médica "
## [9] "las primeras palabras de la cocina"
## [10] " en la cocina tocas pelo o diriges "
## [11] "el exotismo de la cocina amazónica"
## [12] " hay una cocina para la crisis "
## [13] "malos hábitos comida rápida y bollería industrial "
## [14] "comida sana frutas verduras legumbres y hortalizas "
## [15] "hiroyoshi ishida es el único gran chef del orbe gastronómico que cocina desde un radical concepto espiritual a sus 66 años es el más auténtico representante de la cocina kaiseki que va mucho más allá del sushi y la tempura con platos elaborados para el paladar la vista y el pensamiento es la comida de los emperadores y nobles del siglo xvii convertida en un pequeño arte por las manos de un budista zen que según afirma su entregado admirador ferran adrià cocina con el alma y trata en cada comida de transmitir vivencias y contar historias "
## [16] "– la alta cocina puede ser un timo "
## [17] "los obama apuestan por la comida sana"
## [18] " si se hace bien todo tiene su lugar vivimos en un mundo donde cada día se nos exige más esfuerzo y en las familias todo el mundo trabaja por lo que no podemos pedirles que se pongan a cocinar comida tradicional y tardar el mismo tiempo que antes la comida rápida no tiene por qué ser de mala calidad hay comida rápida de altísima calidad y que debe formar parte de la cocina "
## [19] " sí bastantes ahora hago la cocina de l´atelier mañana otra cosa la restauración es muy cambiante y tal vezpronto empiece un nuevo concepto con una cocina más popular "
## [20] " me encanta la cocina de mercado natural con ingredientes muy frescos las delicatessen son agradables pero disfruto más con la cocina de aquí "Los resultados se ven razonables. Sin embargo, si utilizamos este sistema, podríamos intentar también la consulta:
vec <- procesar_query("la comida y la cocina", vocabulario_noticias, normalizar)
similitudes <- calc_sim(vec, td_noticias_tf)## [1] 1## [1] "la comida "
## [2] " la"
## [3] " la gandora a la"
## [4] "la costera la canal la vall"
## [5] "la ética la caridad la historia la convivencia el amor al prójimo la igualdad la paz eran asignaturas de adorno "
## [6] "y para todo ello la creatividad y la innovación van a resultarnos imprescindibles como digo la asignatura pendiente en la gestión de la empresa actual y me atrevería a decir que esto ha sido la causa de la crisis actual es la generación de una cultura basada en la honradez la ética y la transparencia por parte de la gerencia "
## [7] "la actividad de cabal fue especialmente intensa en distintos campos como la investigación periodística la narración oral la edición la docencia y la promoción de la lectura "
## [8] "hoy pronuncia la conferencia medicina en la cocina la cocina es una buena consulta médica "
## [9] "a los valores que hasta ahora protegía dicha ley como eran la salvaguarda del orden público la investigación penal la seguridad pública la defensa nacional la salud pública la dignidad de la persona el principio de no discriminación o la protección de la juventud y la infancia se suma ahora un valor muy cuestionado en internet la propiedad intelectual "
## [10] " vuestra nación debería seguir defendiendo la indisolubilidad del matrimonio además de la verdadera naturaleza de la familia la defensa de la sacralidad de la vida humana desde la concepción hasta la muerte natural o la libertad religiosa "Y los resultados son muy malos. La razón es que muchos documentos contienen la palabra la, y resultan en una similitud alta con la consulta. Sin embargo, la palabra la ocurre en una gran parte de los documentos, de modo que no discrimina mucho en nuestra búsqueda, y deberíamos ponderar más las palabras cocina y comida, que ocurren en una fracción menor y por lo tanto son más específicas a nuestra consulta.
10.5 Frecuencia inversa en documentos
Ahora tenemos que considerar que los términos que ocurren poco (cuando coinciden con nuestras búsquedas), son mejores para discriminar que términos que ocurren mucho, de modo que distintos términos tienen que tener distintos pesos al ordenar los resultados.
Si \(df_i\) es el número de veces que aparece un término \(i\) en la colección de documentos, y \(N\) es el total de documentos en la colección, definimos: la frecuencia inversa de documentos como \[idf_i = log\left(\frac{N}{df_i}\right)\]
Y definimos los pesos finales tf-idf como sigue
\[w_{i,d} = idf_i \times tf_{i,d}\]
Puede intentarse también usar la frecuencia inversa sin logaritmo, pero la forma con logaritmo es más común.
Bajo este esquema de podneración por término y frecuencia inversa en documentos, la similitud entre un documento \(d\) dado y un query \(q\) está dada por
\[sim(q, d) = \frac{ \sum_{w\in q,d} tf_{w,q}tf_{w,d} (idf_w)^2 }{\sqrt{\sum_{i\ in q}(tf_{i,q} idf_i)^2 }\sqrt{\sum_{i \in d} (tf_{i,d} idf_i)^2 }}\]
Ejercicio
Si hacemos un query de un solo término, ¿cómo afecta agregar el idf al scoring de los resultados?
Respuesta: no afecta en nada. La razón es que el idf depende del término, y no del documento.
Sin embargo, para queries de más de un término, el idf puede ayudar mucho: por ejemplo, si buscamos el perro, la palabra el estará ponderada hacia abajo, pues ocurre mucho, y se valorarán más alto documentos que contengan la palabra perro.
Ejemplo
En nuestro minicorpus, las frecuencias inversas son
td_mat <- as.matrix(td_sparse)
n_i <- row_sums(td_mat > 0)
idf <- log(ncol(td_mat)/n_i)
data_frame(termino = names(n_i), n = n_i, idf = round((idf), 3)) %>% arrange(desc(idf))## # A tibble: 12 x 3
## termino n idf
## <chr> <dbl> <dbl>
## 1 amarilla 1 1.39
## 2 casa 1 1.39
## 3 en 1 1.39
## 4 es 1 1.39
## 5 viven 1 1.39
## 6 con 2 0.693
## 7 gato 2 0.693
## 8 juega 2 0.693
## 9 el 3 0.288
## 10 pelota 3 0.288
## 11 perro 3 0.288
## 12 la 4 0Y entonces la representación vectorial está dada por:
## Docs
## Terms 1 2 3 4
## amarilla 0.0000000 0.0000000 1.3862944 0.0000000
## casa 1.3862944 0.0000000 0.0000000 0.0000000
## con 0.0000000 0.6931472 0.0000000 1.3862944
## el 0.5753641 0.2876821 0.0000000 0.8630462
## en 1.3862944 0.0000000 0.0000000 0.0000000
## es 0.0000000 0.0000000 1.3862944 0.0000000
## gato 0.6931472 0.0000000 0.0000000 1.3862944
## juega 0.0000000 0.6931472 0.0000000 1.3862944
## la 0.0000000 0.0000000 0.0000000 0.0000000
## pelota 0.0000000 0.2876821 0.2876821 0.2876821
## perro 0.2876821 0.2876821 0.0000000 0.2876821
## viven 1.3862944 0.0000000 0.0000000 0.0000000Ejemplo
Regresamos a nuestro ejemplo anterior. Este proceso donde dominan los términos frecuentes “la” e “y”:
Y ahora ponderamos por la frecuencia inversa en documentos:
## Warning in weightSMART(td_noticias, spec = "ntc"): empty document(s): 9277
## 10875 14069 15207 18525 22875 25191 26455 26774 29822 38785 39600 45396 47545
## 47857 50522 55948 59352 60046 62017 68213 72636 90667 98192 101282 103821 109647
## 111977 113312 116393 116697 117585 121357 121525 133355 138813 143745 152743
## 152962 153171 158791 160317 161910 163064 175503 180262 182557 183815 190362
## 193141 193783 194294 196045 196387 196516 197574 200539 202709 206885 210399
## 211885 212686 213636 215475 216601 219764 227261 233237 237532 249043 255134
## 260972 262030 263265 268661 269837 270657 272935 273803 285378 287887 291144
## 301231 304532 308472vec <- procesar_query("la comida y la cocina", vocabulario_noticias, normalizar)
similitudes <- calc_sim(vec, td_noticias_tfidf)## [1] 1## [1] "la comida "
## [2] " brunch o comida formal "
## [3] "segundo de cocina "
## [4] " hemos cerrado la cocina "
## [5] " cómo cocina sus personajes "
## [6] " cómo definiría su cocina "
## [7] " la cocina catalana es ligera "
## [8] "hoy pronuncia la conferencia medicina en la cocina la cocina es una buena consulta médica "
## [9] "las primeras palabras de la cocina"
## [10] " en la cocina tocas pelo o diriges "
## [11] "el exotismo de la cocina amazónica"
## [12] " hay una cocina para la crisis "
## [13] "malos hábitos comida rápida y bollería industrial "
## [14] "comida sana frutas verduras legumbres y hortalizas "
## [15] "los obama apuestan por la comida sana"
## [16] "– la alta cocina puede ser un timo "
## [17] "hiroyoshi ishida es el único gran chef del orbe gastronómico que cocina desde un radical concepto espiritual a sus 66 años es el más auténtico representante de la cocina kaiseki que va mucho más allá del sushi y la tempura con platos elaborados para el paladar la vista y el pensamiento es la comida de los emperadores y nobles del siglo xvii convertida en un pequeño arte por las manos de un budista zen que según afirma su entregado admirador ferran adrià cocina con el alma y trata en cada comida de transmitir vivencias y contar historias "
## [18] "el menú del día propone básicamente una cocina muy tradicional cocina vasca podemos elegir entre siete primeros platos siete segundos y cinco postres caseros su carta comienza con los entrantes fríos entre ellos destacan la ensalada de queso de cabra con naranja plato de la cocina marroquí la ensalada olivie típica de la cocina rusa la escalibada catalana o la piperrada asada con huevo escalfado "
## [19] " sí bastantes ahora hago la cocina de l´atelier mañana otra cosa la restauración es muy cambiante y tal vezpronto empiece un nuevo concepto con una cocina más popular "
## [20] " me encanta la cocina de mercado natural con ingredientes muy frescos las delicatessen son agradables pero disfruto más con la cocina de aquí "Nótese que en este ejemplo no multiplicamos las frecuencias inversas sobre documentos en el vector de query.
10.6 Notación SMART
Las alternativas que tenemos para nuestro sistema de recuperació́n de textos son, para documentos y queries:
- Frecuencia de términos: frecuencia bruta (n) o logarítmica (l).
- Frecuencia de documentos: ninguna (n), idf (t).
- Normalización: ninguna (n), coseno (c).
Denotamos como xxx.yyy a un sistema dado. Por ejemplo, un sistema que usa frecuencia logarítmica, sin frecuencia de documentos, con normalizació́n coseno para los documentos, y para los queries frecuencia logarítmica con idf y normalizació́n coseno es lnc.ltc
- El método más popular es ntc.ntc, aunque también se utilizan otros como lnc.ltc.
10.7 Definición del diccionario
En esta parte discutimos distintas posibilidades para el paso de tokenización.
10.7.1 Stopwords (términos comunes)
En algunos casos puede ser conveniente eliminar del todo palabras stopword (palabras que tienden a ocurrir en casi todos los textos, como artículos, preposiciones, conjunciones, etc.) La idea es que estos términos no ayudan en las búsquedas, y pueden reducir el tamaño del índice invertido (o de la matriz de pesos términos-documentos).
En sistemas más avanzados y recientes, las stopwords no se eliminan muchas veces para conservar el significado de consultas como “viajes a Londres”: en este caso, también necesitamos incluir en nuestro índice invertido las posiciones donde aparecen las palabras (ver (Manning, Raghavan, and Schütze 2008), sección 2.4).
10.7.2 Normalización
En la normalización, buscamos crear clases de equivalencia entre tokens que aparecen en nuestro texto, que deben ser considerados como equivalentes en las búsquedas. Las normalizaciones más comunes son (todas pueden ayudar o dañar el desempeño):
Reducir todos los tokens a minúsculas (de forma que no importa si los términos ocurren al principio de una frase). En general es buena idea, aunque en algunos casos pueden hacerse forma más refinada (por ejemplo, la ciudad Pisa y el verbo pisa).
Corregir ortografía. También es posible hacer corrección de ortografía para mejorar el resultado de consultas. Este paso se puede hacer solamente para las consultas, por ejemplo.
Quitar acentos. Esto tiene la ventaja de poder dar buenas respuestas a consultas que tienen faltas de ortografía. Por otro lado, también introduce ambiguedades.
10.7.3 Stemming
En el paso de stemming intentamos reducir los tokens a palabras raíz. Por ejemplo, si alguien busca “frutas”, la búsqueda debería incluir también términos como “fruta”, “frutería”, etc. Una consulta como “comiendo frutas” debería regresar resultados como “comer fruta”, “comer frutas”.
Existen stemmers automáticos que intentan aproximar la palabra raíz de cada forma que observamos. En español, podemos usar el Snowball stemmer, que es relativamente simple (ver esta liga).
## [1] "Esos mes com much frut"## [1] "Ese mes com much frut"## [1] "comenz comenz comienz comienz bibliotec bibliotecari"Pero el stemming puede también afectar el desempeño: por ejemplo, si queremos buscar “investigación de operaciones”, el stemmer no necesariamente ayuda a encontrar resultados relevantes;
## [1] "investig oper"## [1] "oper investig"Observación:
- Es importante recordar que típicamente, todas las transformaciones que hacemos al construir el índice deben de repetirse para las consultas.
Ejemplo
Agregamos stemming:
normalizar_stem <- function(texto, vocab = NULL){
texto <- tolower(texto)
texto <- gsub("-", " ", texto) # separar palabras con guión
texto <- gsub("\\.[^0-9]", " ", texto) # quitar puntos
texto <- gsub("[«»;\\:\\.,'\"()¿?!¡\\-\\/]", " ", texto)
texto <- gsub("\\s+", " ", texto)
stemDocument(texto, language = "spanish")
}
periodico <- normalizar_stem(periodico_original)
vs <- VectorSource(periodico)
corpus_noticias <- VCorpus(vs, readerControl = list(language = "es"))
td_noticias <- TermDocumentMatrix(corpus_noticias,
control = list(weighting = weightTf, wordLengths = c(2, Inf)))
vocabulario_noticias <- td_noticias$dimnames$Terms
sample(vocabulario_noticias, 50)## [1] "mononucleosis" "apatzing" "chust"
## [4] "tracey" "neurolingü" "iberia–"
## [7] "eleuteri" "maktoum" "thedeathlyhallows"
## [10] "velociped" "aminal" "confetis"
## [13] "col2a1" "imprescindibles”" "romaric"
## [16] "chicadelatel" "centerfield" "modotti"
## [19] "oles" "mareantes”" "herriak"
## [22] "33528" "intersemanal" "revueltos’"
## [25] "urbespaci" "galardons" "homenaj"
## [28] "“fall" "retirart" "baladruz"
## [31] "onubense’" "kiernikowski" "karlsson"
## [34] "descripcion" "nanny" "poncin"
## [37] "wackenhut" "crid" "merritt"
## [40] "blumarin" "ertha" "–otr"
## [43] "rizzi" "monolingü" "mancheñ"
## [46] "calabacin" "guareñ" "–niqab"
## [49] "atac" "corten"vec <- procesar_query("la comida y la cocina", vocabulario_noticias, normalizar_stem)
similitudes <- calc_sim(vec, td_noticias_tfidf)## [1] 1recuperados <- periodico_original[order(similitudes[1,], decreasing = TRUE)[1:100]]
head(recuperados, 20)## [1] "-¿Sabe cocinar?"
## [2] "-¿Cómo cocina sus personajes?"
## [3] "-¿Cómo definiría su cocina?"
## [4] "¿Por qué cocinas?"
## [5] "Segundo de Cocina:"
## [6] "-Hemos cerrado la cocina."
## [7] "-¿La cocina catalana es ligera?"
## [8] "-¿Como definiría las cualidades de la cocina gallega?"
## [9] "Hoy pronuncia la conferencia 'Medicina en la cocina', ¿la cocina es una buena consulta médica?"
## [10] "Cajamar AcremarDPV-Vacceos Cocinas y Baños 0-4"
## [11] "–En mi casa cocina siempre mi mujer (risas). Me gusta cocinar en los saraos, barbacoas o hacerle la pasta a las niñas. Mi mujer no tiene ningún tipo de complejo a la hora de cocinarme."
## [12] "Las primeras palabras de la cocina"
## [13] "-En la cocina, ¿tocas pelo o diriges?"
## [14] "El exotismo de la cocina amazónica"
## [15] "-¿Hay una cocina para la crisis?"
## [16] "12. Cocinas Moisés (Jaime Yllera) 96"
## [17] "-¿Y para qué futbolista le gustaría cocinar?"
## [18] "–¿La alta cocina puede ser un timo?"
## [19] "El menú del día propone básicamente una cocina muy tradicional, cocina vasca. Podemos elegir entre siete primeros platos, siete segundos y cinco postres caseros. Su carta comienza con los entrantes fríos. Entre ellos destacan la ensalada de queso de cabra con naranja, plato de la cocina marroquí, la ensalada Olivie, típica de la cocina rusa, la escalibada catalana, o la piperrada asada con huevo escalfado."
## [20] "-Sí, bastantes. Ahora hago la cocina de L´Atelier, mañana otra cosa... La restauración es muy cambiante y tal vezpronto empiece un nuevo concepto con una cocina más popular."10.8 Indexado semántico latente
El modelo de espacio vectorial para recuperación de documentos (o en otras tareas como creación de variables para construir modelos de clasificación, por ejemplo), tiene la desventaja de no explotar la estructura de la colección de documentos más allá de frecuencias de términos particulares. En particular, por ejemplo, no es posible directamente cuáles términos son sinónimos o cercanos a sinónimos, ni entender que una palabra puede tener más de un significado. Este tipo de aspectos pueden resolverese en parte considerando la ocurrencia conjunta de términos, por ejemplo:
- Si consideramos que “carro” y “coche” ocurren en varios documentos que tienen frecuencias similares de otros términos (gasolina, llantas, viaje, etc.), quizá podríamos “agruparlos”, de manera que búsquedas de uno o otro término resulte en devolver colecciones de documentos similares.
Una idea para construir estas “agrupaciones” es utilizar la descomposición en valores singulares (DVS) de la matriz términos - documentos para aproximar esta matriz mediante otra de rango bajo.
Consideremos entonces una matriz \(C\) de términos-documentos de tamaño \(M\times N\). Utilizando la DVS, podemos aproximar \(C\) mediante una matriz \(C_k\) dada por:
\[C \approx C_k = U_k\Sigma_k V_k^t,\]
donde \(U_k\) es una matriz ortogonal de tamaño \(M\times k\), \(V_k\) es una matriz ortogonal de tamaño \(M\times k\), y \(\Sigma_k\) es una matriz diagonal con los \(k\) valores singulares más grandes en la diagonal (ver por ejemplo esta explicación.
Esta reducción de dimensionalidad la podemos ver como una tarea de compresión, donde términos que tienen co-ocurrencias similares de otros términos tienden a agruparse en una sola dimensión.
Ejemplo
Consideremos los siguientes textos:
frases <- c('viajamos en carro y se ponchó una llanta',
'los coches tienen llantas',
'un coche sin llantas',
'un carro con llantas ponchadas',
'hicimos un viaje en coche',
'viajamos en carro', 'viajamos en coche',
'La cocina catalana es ligera',
'me gusta cocinar',
'una cocina muy tradicional',
'me gusta la cocina tradicional')
frases_norm <- normalizar_stem(frases)Construimos una matriz binaria que indica qué términos aparecen en qué documentos:
vs <- VectorSource(frases_norm)
corpus <- VCorpus(vs)
td_sparse <- TermDocumentMatrix(corpus,
control = list(weighting = weightBin,
wordLengths = c(3, Inf)))
td_mat <- as.matrix(td_sparse)
td_mat## Docs
## Terms 1 2 3 4 5 6 7 8 9 10 11
## carr 1 0 0 1 0 1 0 0 0 0 0
## catalan 0 0 0 0 0 0 0 1 0 0 0
## coch 0 1 1 0 1 0 1 0 0 0 0
## cocin 0 0 0 0 0 0 0 1 1 1 1
## con 0 0 0 1 0 0 0 0 0 0 0
## gust 0 0 0 0 0 0 0 0 1 0 1
## hic 0 0 0 0 1 0 0 0 0 0 0
## liger 0 0 0 0 0 0 0 1 0 0 0
## llant 1 1 1 1 0 0 0 0 0 0 0
## los 0 1 0 0 0 0 0 0 0 0 0
## muy 0 0 0 0 0 0 0 0 0 1 0
## ponch 1 0 0 1 0 0 0 0 0 0 0
## sin 0 0 1 0 0 0 0 0 0 0 0
## tien 0 1 0 0 0 0 0 0 0 0 0
## tradicional 0 0 0 0 0 0 0 0 0 1 1
## una 1 0 0 0 0 0 0 0 0 1 0
## viaj 1 0 0 0 1 1 1 0 0 0 0Consideremos la descomposición en valores singulares:
Las columnas de la matriz \(U\) pueden ser considerados como “documentos latentes”. Consideramos los primeros dos:
U_2 <- - svd_ejemplo$u[,1:2]
rownames(U_2) <- rownames(td_mat)
U_ord <- round(U_2, 1)[order(U_2[,1]),]
U_ord## [,1] [,2]
## catalan 0.0 0.1
## liger 0.0 0.1
## gust 0.0 0.4
## muy 0.0 0.2
## tradicional 0.1 0.4
## cocin 0.1 0.7
## hic 0.1 0.0
## sin 0.1 0.0
## los 0.1 0.0
## tien 0.1 0.0
## con 0.1 0.0
## una 0.2 0.2
## ponch 0.3 0.0
## coch 0.4 -0.1
## carr 0.4 0.0
## viaj 0.4 -0.1
## llant 0.5 -0.1Y notamos que la primera dimensión captura aquellos documentos con ocurrencia alta de términos relacionados con coches: este es un término nuevo que podemos llamar “automotriz”, por ejemplo. Estos términos están agrupados en esta dimensión pues ocurren juntos en varios documentos, lo que implica que podemos “comprimir” estas frecuencias en una sola dimensión.
Los documentos con contenido alto del nuevo término “automotriz” son los que tienes valores altos en este primer término, por ejemplo:
V_2 <- -svd_ejemplo$v[,1:2] # podemos cambiar signo de U y V
tibble(frase = frases, v_1 = round(V_2[, 1], 1), v_2 = round(V_2[, 2], 1))## # A tibble: 11 x 3
## frase v_1 v_2
## <chr> <dbl> <dbl>
## 1 viajamos en carro y se ponchó una llanta 0.6 0
## 2 los coches tienen llantas 0.4 -0.1
## 3 un coche sin llantas 0.3 -0.1
## 4 un carro con llantas ponchadas 0.4 0
## 5 hicimos un viaje en coche 0.3 -0.1
## 6 viajamos en carro 0.3 0
## 7 viajamos en coche 0.3 -0.1
## 8 La cocina catalana es ligera 0 0.4
## 9 me gusta cocinar 0 0.4
## 10 una cocina muy tradicional 0.1 0.6
## 11 me gusta la cocina tradicional 0 0.6Nótese que podemos pensar que esta es nuestra nueva matriz documentos-términos (\(V_k\)), con “términos” latentes o dimensiones latentes, y podemos calcular similitudes de documentos usando la similitud coseno. Para encontrar las coordenadas latentes de los documentos (en coordenadas \(V\)), notamos que como \(C_k = U_k^t \Sigma_kV_kt\), entonces
\[V_k^t = \Sigma_k^{-1}U_k^tC_k.\] De modo que para mapear un nuevo documento o query \(q\) en el espacio de dimensiones semánticas hacemos \[q_s = \Sigma_k^{-1} U_k^t q,\] donde \(q\) es la respresentación vectorial del query. Podemos ahora comparar \(q_s\) directamente con los vectores de la matriz \(V_k.\)
Ejemplo
Supongamos que tenemos el query “un viaje en coche”. El vector asociado es:
vocab_ejemplo <- rownames(td_mat)
q <- procesar_query("un viaje en coche", vocab_ejemplo, normalizar_stem)
q <- as.matrix(q)
q## Docs
## Terms 1
## carr 0
## catalan 0
## coch 1
## cocin 0
## con 0
## gust 0
## hic 0
## liger 0
## llant 0
## los 0
## muy 0
## ponch 0
## sin 0
## tien 0
## tradicional 0
## una 0
## viaj 1Ahora mapeamos a las dimensiones latentes:
## Docs
## 1
## [1,] 0.25289996
## [2,] -0.06872417Y ahora podemos comparar con los reglones de \(V\), que dan la representación de los documentos originales.
normas <- apply(V_2, 1, function(x){ sqrt(sum(x^2)) })
V_2_norm <- V_2 / normas
q_s_norm <- q_s / sqrt(sum(q_s^2))
tibble(frases = frases, sim = V_2_norm %*% q_s_norm %>% as.numeric) %>% arrange(desc(sim))## # A tibble: 11 x 2
## frases sim
## <chr> <dbl>
## 1 viajamos en coche 1.000
## 2 hicimos un viaje en coche 1.000
## 3 un coche sin llantas 1.000
## 4 los coches tienen llantas 0.999
## 5 un carro con llantas ponchadas 0.987
## 6 viajamos en carro 0.987
## 7 viajamos en carro y se ponchó una llanta 0.952
## 8 una cocina muy tradicional -0.0686
## 9 me gusta la cocina tradicional -0.186
## 10 La cocina catalana es ligera -0.193
## 11 me gusta cocinar -0.193Nótese como recuperamos también frases similares con el término “carro”, que no está en el query original.
10.8.1 Ejemplo
Ahora repetimos con el corpus de noticias. Consideremos solo unas cuantas dimensiones latentes importantes (normalmente utilizaríamos orden de cientos para similitud):
library(irlba)
td_sparse <- sparseMatrix(i = td_noticias_tfidf$i, j = td_noticias_tfidf$j, x = td_noticias_tfidf$v)
noticias_svd <- irlba(td_sparse, nv = 5, nu = 5)Por ejemplo, los términos:
terminos <- tibble(termino = Terms(td_noticias_tfidf),
dim_1 = noticias_svd$u[,3], dim_2 = noticias_svd$u[,4])
head(terminos %>% arrange(dim_2),40)## # A tibble: 40 x 3
## termino dim_1 dim_2
## <chr> <dbl> <dbl>
## 1 eur 0.0973 -0.485
## 2 millon 0.0859 -0.328
## 3 000 0.0455 -0.257
## 4 me -0.0139 -0.173
## 5 mas 0.00207 -0.119
## 6 año -0.00879 -0.108
## 7 mi -0.00437 -0.0880
## 8 es 0.103 -0.0820
## 9 preci 0.0164 -0.0804
## 10 cient 0.00122 -0.0720
## # … with 30 more rows## # A tibble: 40 x 3
## termino dim_1 dim_2
## <chr> <dbl> <dbl>
## 1 hor -0.168 -0.0104
## 2 00 -0.154 -0.0277
## 3 minut -0.144 0.00426
## 4 fue -0.138 0.0261
## 5 equip -0.137 0.0154
## 6 punt -0.129 -0.0190
## 7 dos -0.129 0.00709
## 8 segund -0.129 -0.00464
## 9 primer -0.106 0.0122
## 10 jug -0.0949 -0.00511
## # … with 30 more rowsEl método de indexado semántico latente es intensivo en cómputo, y es difícil escalar a colecciones muy grandes.
Sin embargo, en algunos casos puede dar ventajas en recuperación de documentos gracias a la reducción de dimensionalidad (reconocimiento de sinónimos, por ejemplo).
También es posible usar las dimensiones latentes para construir modelo de clasificación de textos o clustering, por ejemplo.
Referencias
Manning, Christopher D., Prabhakar Raghavan, and Hinrich Schütze. 2008. Introduction to Information Retrieval. New York, NY, USA: Cambridge University Press.