Algoritmo/Heurística para agrupar historias de mensajes de chat por 'conversación'/sesiones implícitas de marcas de tiempo?

Question

El problema: tengo una serie de mensajes de chat, entre dos usuarios, con marcas de tiempo. Podría presentar, digamos, un día completo de mensajes de chat a la vez. Durante todo el día, sin embargo, hubo múltiples conversaciones/sesiones discretas ... y sería más útil para el usuario ver estos divididos en oposición a todos los días como una transmisión continua.

¿Hay algún algoritmo o heurística que pueda 'deducir' inicios de sesiones/conversaciones implícitas/interrupciones de las marcas de tiempo? Además de un arbitrario 'si el espacio es más de x minutos, es una sesión separada'. Y si ese es el único caso, ¿cómo se determina este intervalo? En cualquier caso, me gustaría evitar esto.

Por ejemplo, hay ... cincuenta mensajes que se envían entre las 2:00 y 3:00, y luego un descanso, y luego veinte mensajes enviados entre las 4:00 y las 5:00. Habría un descanso insertado entre allí ... ¿pero cómo se determinaría el descanso?

Estoy seguro de que ya hay literatura sobre este tema, pero simplemente no sé qué buscar.

Estaba jugando con cosas como algoritmos de detección de bordes y enfoques basados ​​en gradiente por un tiempo.

(ver comentarios para mayor clarificación)

Answer 1

EDITAR (mejor idea):

Usted puede ver cada mensaje como ser de dos tipos:

1. A continuación de una conversación anterior
2. Una nueva conversación

Puede modelar estos dos tipos de mensajes como Poisson processes, donde la diferencia de tiempo entre mensajes adyacentes es exponential distribution.

A continuación, puede determinar empíricamente los parámetros exponenciales para estos dos tipos de mensajes a mano (no sería demasiado difícil hacerlo dados algunos datos iniciales). Ahora tienes un modelo para estos dos eventos.

Finalmente, cuando aparece un mensaje nuevo, puede calcular la probabilidad de que el mensaje sea de tipo 1 o tipo 2. Si es 2, entonces tiene una nueva conversación.

Aclaración:

La probabilidad de que el mensaje sea una nueva conversación, dado que el retraso es un tiempo T.

P(new conversation | delay=T) = P(new conversation AND delay=T)/P(delay=T) 

El uso de Bayes Regla:

= P(delay=T | new conversation)*P(new conversation)/P(delay=T) 

El mismo cálculo se aplica a P(old conversation | delay=T).

P(delay=T | new conversation) viene del modelo. P(new conversation) es fácilmente calculable a partir de los datos utilizados para generar su modelo. P(delay=T) no necesita calcular nada, ya que todo lo que quiere hacer es comparar las dos probabilidades.

---

La diferencia en las marcas de tiempo entre mensajes adyacentes depende del tipo de conversación y de las personas que participan. Por lo tanto, querrá un algoritmo que tenga en cuenta las características locales, a diferencia de un parámetro de umbral global.

Mi propuesta sería la siguiente:

1. Consigue la diferencia de tiempo entre los 10 últimos mensajes adyacentes.
2. Calcule la media (o la mediana)
3. Si la demora hasta el siguiente mensaje es más de 30 veces la media, es una conversación nueva.

Por supuesto, se me ocurrieron estos números en el acto. Tendrían que estar sintonizados para adaptarse a su propósito.