Algorithm/Euristico per raggruppare le cronologie dei messaggi di chat per "conversazione"/sessioni implicite dai timestamp?

Question

Il problema: ho una serie di messaggi chat - tra due utenti - con data e ora. Potrei presentare, per esempio, un'intera giornata di messaggi di chat in una sola volta. Durante l'intera giornata, tuttavia, ci sono state conversazioni/sessioni multiple e discrete ... e sarebbe più utile per l'utente vederle divise in contrapposizione a tutti i giorni come un flusso continuo.

Esiste un algoritmo o euristico che può "dedurre" interruzioni/conversazioni implicite di conversazioni/interruzioni di data/ora? Oltre ad un arbitrario 'se il divario è più di x minuti, è una sessione separata'. E se questo è l'unico caso, come viene determinato questo intervallo? In ogni caso, vorrei evitare questo.

Ad esempio, ci sono ... cinquanta messaggi che vengono inviati tra le 2:00 e le 3:00 e quindi un'interruzione, quindi venti messaggi inviati tra le 4:00 e le 5:00. Ci sarebbe una pausa inserita tra lì ... ma come si determinerebbe la rottura?

Sono certo che esiste già letteratura su questo argomento, ma non so cosa cercare.

Stavo giocando con elementi come algoritmi di rilevamento dei bordi e approcci basati sul gradiente per un po '.

(vedi commenti per ulteriori chiarimenti)

Answer 1

EDIT (migliore idea):

È possibile visualizzare ogni messaggio come di due tipi:

1. Una continuazione di una precedente conversazione
2. Una nuova conversazione

È possibile modellare questi due tipi di messaggi come indipendenti Poisson processes, dove la differenza di tempo tra i messaggi adiacenti è exponential distribution.

È quindi possibile determinare empiricamente i parametri esponenziali per questi due tipi di messaggi a mano (non sarebbe troppo difficile fare dati dati iniziali). Ora hai un modello per questi due eventi.

Infine quando arriva un nuovo messaggio, è possibile calcolare la probabilità che il messaggio sia di tipo 1 o di tipo 2. Se si digita 2, si ha una nuova conversazione.

Chiarimento:

La probabilità che il messaggio sia una nuova conversazione, dato che il ritardo è da tempo T.

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

Utilizzando Bayes' Regola:

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

Lo stesso calcolo vale per P(old conversation | delay=T).

P(delay=T | new conversation) viene dal modello. P(new conversation) è facilmente calcolabile dai dati utilizzati per generare il modello. P(delay=T) non è necessario calcolare affatto poiché tutto ciò che si vuole fare è confrontare le due probabilità.

---

La differenza di data e ora tra i messaggi adiacenti dipende dal tipo di conversazione e dalle persone che partecipano. Quindi vorrai un algoritmo che tenga conto delle caratteristiche locali, al contrario di un parametro di soglia globale.

mia proposta sarebbe la seguente:

1. Ottenere la differenza di tempo tra gli ultimi 10 messaggi adiacenti.
2. Calcolare la media (o mediana)
3. Se il ritardo fino al messaggio successivo è più di 30 volte la media, si tratta di una nuova conversazione.

Ovviamente, ho trovato questi numeri sul posto. Dovrebbero essere sintonizzati per adattarsi al tuo scopo.