Algoritmo migliore per correlare i dati semi-strutturati

I have the need to match incoming fragments of semi-structured text to previously encountered fragments.

Quindi, per il dominio del problema, l'output possibile potrebbe essere classificato come categoriale in cui ogni frammento precedente è una categoria a cui è possibile assegnare il nuovo testo in entrata.

Naive Bayes come algoritmo di classificazione del testo è altamente scalabile ed esegue in termini di complessità lineare. Un algoritmo NB esamina le caratteristiche di una classe senza focalizzarsi sul fatto che queste caratteristiche dipendano l'una dall'altra o dall'esistenza delle altre caratteristiche, tutte queste proprietà contribuiscono indipendentemente alla probabilità che il tuo evento si trovi all'interno di una classe, quindi viene soprannominato 'Naive ', e quindi in esecuzione in tempo lineare senza confronto con ogni vettore della tua lingua di classe.

Essendo un classificatore di probabilità, un algoritmo di Naive Bayes può essere comodo costruito da zero. Esistono molti video di YouTube che mostrano come applicarlo con i pacchetti Machine Learning e Language Processing, per un controllo di comprensione più fondamentale il link qui .

Questo ha detto che gli algoritmi di Naive Bayes sono generalmente di apprendimento supervisionato mentre il tuo attuale metodo di applicazione attraverso K-means applica l'apprendimento senza supervisione.

A seconda della lunghezza delle tue stringhe potresti prendere in considerazione una metrica di distanza delle stringhe raw come la distanza Levenshtein . Questa metrica è veloce e facile da calcolare.

Lo svantaggio di questa metrica è che non considererà l'input "fuori servizio" come simile. Ad esempio "WORD_A WORD_B" WORD_C WORD_D "non è vicino a" WORD_D WORD_C WORD_B WORD_A ".

Il lato positivo di questa metrica (diversa dalla velocità) è che raggruppa rapidamente cose come "SOME_TEXT COMMON_ERROR_MESSAGE" con altri messaggi simili.

È promettente che tu possa ottenere che K-means funzioni in qualche modo con piccoli set di dati. Le probabilità sono buone, potresti avere set più grandi che funzionano quasi altrettanto rapidamente se la tua implementazione campiona il set di dati per primo.

Prova qualcosa del tipo:

1. Scegli un campione n% del tuo grande set di dati
2. Esegui K significa su quel campione
3. Considera il clustering "completato".
4. Classificare il restante 100% del set di dati "adattandoli" al risultato del clustering esistente. Fondamentalmente stai basandosi sul fatto che se K < < SIZE_OF_DATASET quindi non devi preoccuparti troppo di quale data point sono membri del n% campione che hai usato per generare il tuo clustering.

Modifica: nuova metrica

Poiché dovrebbe essere veloce, troviamo una metrica più semplice. :)

In primo luogo, dividi le linee in parole (divisione dello spazio semplice, ignorando tutto il resto)

Dato 2 righe, con rispettivamente N e M parole. Lascia che sia la "somiglianza":

similarity = 2 * S / (N + M)

dove S è la quantità di parole in comune. Quale dovrebbe essere veloce da calcolare usando un hash set.

Poiché il prossimo algoritmo si basa su una soglia, puoi persino scartare questo calcolo quando la quantità di parole è troppo diversa e impostala su 0.

In alternativa ai sofisticati k-means o altri algoritmi di clustering avanzati, suggerisco qualcosa di molto più semplice. Non so se ha un nome.

Fondamentalmente, per ogni riga, controlla a quale cluster la linea è "più vicina" confrontandola con un elemento casuale di essa. Se la somiglianza ha raggiunto una certa soglia, aggiungila al cluster. Altrimenti crea un nuovo cluster contenente questa singola linea.

... forse non è il massimo, ma dovrebbe essere molto efficiente fornendo risultati soddisfacenti.

clusters = [] for line in log: tokens = line.split() candidate = None for c in clusters: c_tokens = tokens of the an item in the cluster c sim = similarity(tokens, c_tokens) if sim > threshold and is the best so far: candidate = c if candidate found: add the line/tokens to candidate found else: add a new cluster containing this line/tokens

La complessità sarebbe O (N * k) dove N è il numero di linee e k il numero di cluster, che dipende dalla soglia.

Ho usato somiglianza del coseno oltre 100K qui.

Un trucco consiste nel fare lo sqrt (sum (a [i] * a [i])) una volta e memorizzarlo.

Esegui una somma parziale (a [i] * b [i]) e rinuncia quando non ha possibilità.