text - div - ¿Qué algoritmos probados y verdaderos para sugerir artículos relacionados están por ahí?

title attribute anchor tag

Question

Una situación bastante común, apostaría. Usted tiene un blog o sitio de noticias y tiene muchos artículos o blags o como quiera que los llame, y desea, al pie de cada uno, sugerir otros que parezcan estar relacionados.

Supongamos muy pocos metadatos sobre cada elemento. Es decir, sin etiquetas, categorías. Trátelo como una gran cantidad de texto, incluidos el título y el nombre del autor.

¿Cómo se puede encontrar los documentos posiblemente relacionados?

Estoy bastante interesado en el algoritmo real, las soluciones no listas, aunque estaría bien echar un vistazo a algo implementado en ruby ​​o python, o confiar en mysql o pgsql.

editar: la respuesta actual es bastante buena, pero me gustaría ver más. Tal vez algunos realmente muestran un código de ejemplo para una cosa o dos.

Answer 1

Debería leer el libro "Programación de la inteligencia colectiva: creación de aplicaciones inteligentes de la Web 2.0" (ISBN 0596529325).

Para algún método y código: primero pregúntese si desea encontrar similitudes directas basadas en coincidencias de palabras o si desea mostrar artículos similares que pueden no estar directamente relacionados con el actual, pero que pertenecen al mismo grupo de artículos.

Ver Análisis de conglomerados / Agrupación de particiones .

Un método muy simple (pero teórico y lento) para encontrar similitudes directas sería:

Preproceso:

1. Almacene la lista de palabras planas por artículo (no elimine las palabras duplicadas).
2. "Cruce de unirse" a los artículos: cuente el número de palabras en el artículo A que coincidan con las mismas palabras en el artículo B. Ahora tiene una matriz int word_matches[narticles][narticles] (no debe almacenarlo así, similitud de A-> B es lo mismo que B-> A, por lo que una matriz dispersa ahorra casi la mitad del espacio).
3. ¡Normalice los conteos de word_matches al rango 0..1! (Encuentra el recuento máximo, luego divide cualquier recuento por esto) - debes almacenar los flotadores allí, no los enteros;)

Encuentra artículos similares:

1. selecciona los artículos X con los mejores resultados de los juegos de palabras

Answer 2

Este es un caso típico de clasificación de documentos que se estudia en todas las clases de Machine Learning. Si le gustan las estadísticas, las matemáticas y la informática, le recomiendo que eche un vistazo a los métodos no supervisados ​​como kmeans++ , métodos bayesianos y LDA . En particular, los métodos bayesianos son bastante buenos en lo que estás buscando, su único problema es ser lento (pero a menos que tengas un sitio muy grande, eso no debería molestarte demasiado).

En un enfoque más práctico y menos teórico, te recomiendo que eches un vistazo a this y a este otro gran ejemplo de código.

Answer 3

Este es un tema bastante importante: además de las respuestas que se presentan aquí, recomiendo rastrear los programas de estudio para obtener un par de clases de recuperación de información y revisar los libros de texto y los documentos asignados para ellos. Dicho esto, aquí hay una breve descripción de mis propios días de graduado:

El enfoque más simple se llama una bolsa de palabras . Cada documento se reduce a un vector disperso de {word: wordcount} pares, y puede lanzar un NaiveBayes (u otro) clasificador en el conjunto de vectores que representa su conjunto de documentos, o calcular puntajes de similitud entre cada bolsa y cada otro bolsa (esto se llama clasificación k-vecino más cercano). KNN es rápido para la búsqueda, pero requiere O (n ^ 2) almacenamiento para la matriz de puntaje; Sin embargo, para un blog, n no es muy grande. Para algo del tamaño de un periódico grande, KNN rápidamente se vuelve poco práctico, por lo que un algoritmo de clasificación sobre la marcha es a veces mejor. En ese caso, podría considerar una máquina de vectores de soporte de clasificación . Las SVM son ordenadas porque no te limitan a medidas de similitud lineal, y aún son bastante rápidas.

Stemming es un paso de preprocesamiento común para las técnicas de bolsa de palabras; esto implica reducir palabras morfológicamente relacionadas, como "gato" y "gatos", "Bob" y "Bob", o "similar" y "similarmente", hasta sus raíces antes de calcular la bolsa de palabras. Hay un montón de diferentes algoritmos de derivación por ahí; la página de Wikipedia tiene enlaces a varias implementaciones.

Si la similitud de "bolsa de palabras" no es lo suficientemente buena, puedes resumirla en una capa para simular una bolsa de N-gramos, donde creas el vector que representa un documento basado en pares o triples de palabras. (Puedes usar 4-tuplas o incluso tuplas más grandes, pero en la práctica esto no ayuda mucho). Esto tiene la desventaja de producir vectores mucho más grandes, y la clasificación en consecuencia requerirá más trabajo, pero las coincidencias que obtengas estarán mucho más cerca. sintácticamente OTOH, probablemente no necesites esto para similitud semántica; es mejor para cosas como la detección de plagio. También se puede usar Chunking o reducción de un documento a árboles de análisis livianos (existen algoritmos de clasificación para árboles), pero esto es más útil para cosas como el problema de la autoría ("dado un documento de origen desconocido, ¿quién lo escribió?" )

Tal vez más útil para su caso de uso es la minería de conceptos, que consiste en asignar palabras a los conceptos (utilizando un diccionario de sinónimos como WordNet ), y luego clasificar los documentos en función de la similitud entre los conceptos utilizados. Esto a menudo termina siendo más eficiente que la clasificación de similitudes basada en palabras, ya que el mapeo de palabras a conceptos es reductivo, pero el paso de preprocesamiento puede consumir bastante tiempo.

Finalmente, está el análisis del discurso , que implica el análisis de documentos para su estructura semántica; puede ejecutar clasificadores de similitud en árboles de discursos de la misma manera que puede hacerlo en documentos fragmentados.

Casi todos implican la generación de metadatos a partir de texto no estructurado; hacer comparaciones directas entre los bloques de texto sin formato es insoluble, por lo que las personas preprocesan documentos en metadatos primero.

Answer 4

Hace algún tiempo, implementé algo similar. Tal vez esta idea ahora está desactualizada, pero espero que pueda ayudar.

Ejecuté un sitio web ASP 3.0 para programar tareas comunes y comencé desde este principio: el usuario tiene una duda y permanecerá en el sitio web siempre que pueda encontrar contenido interesante sobre ese tema.

Cuando llegó un usuario, inicié un objeto de Session ASP 3.0 y grabé toda la navegación del usuario, al igual que una lista vinculada. En el evento Session.OnEnd , tomo el primer enlace, busco el siguiente enlace y aumento una columna de contador como:

<Article Title="Cookie problem A">
    <NextPage Title="Cookie problem B" Count="5" />
    <NextPage Title="Cookie problem C" Count="2" />
</Article>

Por lo tanto, para consultar los artículos relacionados, solo tenía que enumerar las principales entidades n NextPage , ordenadas por columna de contador descendiendo.

Answer 5

Un pequeño motor de búsqueda de modelos de espacio vectorial en Ruby. La idea básica es que dos documentos están relacionados si contienen las mismas palabras. Entonces contamos la ocurrencia de palabras en cada documento y luego calculamos el coseno entre estos vectores (cada término tiene un índice fijo, si aparece hay un 1 en ese índice, si no un cero). Coseno será 1.0 si dos documentos tienen todos los términos comunes, y 0.0 si no tienen términos comunes. Puedes traducirlo directamente a% values.

terms = Hash.new{|h,k|h[k]=h.size}
docs = DATA.collect { |line| 
  name = line.match(/^/d+/)
  words = line.downcase.scan(/[a-z]+/)
  vector = [] 
  words.each { |word| vector[terms[word]] = 1 }
  {:name=>name,:vector=>vector}
}
current = docs.first # or any other
docs.sort_by { |doc| 
  # assume we have defined cosine on arrays
  doc[:vector].cosine(current[:vector]) 
}
related = docs[1..5].collect{|doc|doc[:name]}

puts related

__END__
0 Human machine interface for Lab ABC computer applications
1 A survey of user opinion of computer system response time
2 The EPS user interface management system
3 System and human system engineering testing of EPS
4 Relation of user-perceived response time to error measurement
5 The generation of random, binary, unordered trees
6 The intersection graph of paths in trees
7 Graph minors IV: Widths of trees and well-quasi-ordering
8 Graph minors: A survey

la definición de Array#cosine se deja como un ejercicio para el lector (debería tratarse con valores nulos y diferentes longitudes, pero bueno para eso tenemos Array#zip ¿verdad?)

Por cierto, los documentos de ejemplo están tomados del documento SVD por Deerwester etal :)