Condividi tramite

Riferimento tecnico per l'algoritmo Microsoft Sequence Clustering

L'algoritmo Microsoft Sequence Clustering è un algoritmo ibrido che usa l'analisi della catena Markov per identificare le sequenze ordinate e combina i risultati di questa analisi con tecniche di clustering per generare cluster in base alle sequenze e ad altri attributi nel modello. Questo argomento descrive l'implementazione dell'algoritmo, come personalizzare l'algoritmo e i requisiti speciali per i modelli di clustering di sequenza.

Per informazioni più generali sull'algoritmo, tra cui come esplorare ed eseguire query sui modelli di clustering di sequenza, vedere Algoritmo Microsoft Sequence Clustering.

Implementazione dell'algoritmo Microsoft Sequence Clustering

Il modello Microsoft Sequence Clustering usa modelli Markov per identificare le sequenze e determinare la probabilità delle sequenze. Un modello Markov è un grafico diretto che archivia le transizioni tra stati diversi. L'algoritmo Microsoft Sequence Clustering usa catene Markov in ordine n, non un modello Markov nascosto.

Il numero di ordini in una catena Markov indica quanti stati vengono usati per determinare la probabilità degli stati correnti. In un modello Markov di primo ordine, la probabilità dello stato corrente dipende solo dallo stato precedente. In una catena Markov di secondo ordine, la probabilità di uno stato dipende dai due stati precedenti e così via. Per ogni catena Markov, una matrice di transizione archivia le transizioni per ogni combinazione di stati. Man mano che la lunghezza della catena Markov aumenta, anche le dimensioni della matrice aumentano in modo esponenziale e la matrice diventa estremamente sparse. Anche il tempo di elaborazione aumenta proporzionalmente.

Può essere utile visualizzare la catena usando l'esempio di analisi clickstream, che analizza le visite alle pagine Web in un sito. Ogni utente crea una lunga sequenza di clic per ogni sessione. Quando si crea un modello per analizzare il comportamento dell'utente in un sito Web, il set di dati usato per il training è una sequenza di URL, convertito in un grafico che include il conteggio di tutte le istanze dello stesso percorso di clic. Ad esempio, il grafico contiene la probabilità che l'utente passi dalla pagina 1 alla pagina 2 (10%), la probabilità che l'utente passi dalla pagina 1 alla pagina 3 (20%) e così via. Quando si inseriscono tutti i possibili percorsi e parti dei percorsi, si ottiene un grafico che potrebbe essere molto più lungo e più complesso di qualsiasi singolo percorso osservato.

Per impostazione predefinita, l'algoritmo Microsoft Sequence Clustering usa il metodo Expectation Maximization (EM) del clustering. Per altre informazioni, vedere Documentazione tecnica sull'algoritmo Microsoft Clustering.

Le destinazioni del clustering sono sia gli attributi sequenziali che non sequenziali. Ogni cluster viene selezionato in modo casuale usando una distribuzione di probabilità. Ogni cluster ha una catena Markov che rappresenta il set completo di percorsi e una matrice che contiene le transizioni e le probabilità dello stato della sequenza. In base alla distribuzione iniziale, la regola Bayes viene usata per calcolare la probabilità di qualsiasi attributo, inclusa una sequenza, in un cluster specifico.

L'algoritmo Microsoft Sequence Clustering supporta l'aggiunta di attributi non sequenziali al modello. Ciò significa che questi attributi aggiuntivi vengono combinati con gli attributi della sequenza per creare cluster di case con attributi simili, proprio come in un modello di clustering tipico.

Un modello di clustering di sequenze tende a creare molti più cluster rispetto a un tipico modello di clustering. Di conseguenza, l'algoritmo Microsoft Sequence Clustering esegue la scomposizione del clusterper separare i cluster in base a sequenze e altri attributi.

Selezione delle funzionalità in un modello sequence clustering

La selezione delle caratteristiche non viene richiamata durante la compilazione di sequenze; Tuttavia, la selezione delle funzionalità si applica alla fase di clustering.

Tipo di modello Metodo di Selezione delle Caratteristiche Commenti
Clustering di sequenze Non utilizzato La selezione delle funzionalità non viene richiamata; Tuttavia, è possibile controllare il comportamento dell'algoritmo impostando il valore dei parametri MINIMUM_SUPPORT e MINIMUM_PROBABILIITY.
Raggruppamento Punteggio di interesse Anche se l'algoritmo di clustering può usare algoritmi discreti o discretizzati, il punteggio di ogni attributo viene calcolato come distanza ed è continuo; pertanto viene usato il punteggio di interesse.

Per altre informazioni, vedere Selezione funzionalità.

Ottimizzazione delle prestazioni

L'algoritmo Microsoft Sequence Clustering supporta diversi modi per ottimizzare l'elaborazione:

  • Controllo del numero di cluster generati impostando un valore per il parametro CLUSTER_COUNT.

  • Riducendo il numero di sequenze incluse come attributi, aumentando il valore del parametro MINIMUM_SUPPORT. Di conseguenza, le sequenze rare vengono eliminate.

  • Riduzione della complessità prima dell'elaborazione del modello raggruppando gli attributi correlati.

In generale, è possibile ottimizzare le prestazioni di una modalità di catena di Markov di n-esimo ordine in diversi modi.

  • Controllo della lunghezza delle possibili sequenze.

  • Riduzione del valore di n a livello di codice.

  • Archiviazione solo delle probabilità che superano una soglia specificata.

Una discussione completa di questi metodi esula dall'ambito di questo argomento.

Personalizzazione dell'algoritmo Sequence Clustering

L'algoritmo Microsoft Sequence Clustering supporta parametri che influiscono sul comportamento, sulle prestazioni e sull'accuratezza del modello di data mining risultante. È anche possibile modificare il comportamento del modello completato impostando flag di modellazione che controllano il modo in cui l'algoritmo elabora i dati di training.

Impostazione dei parametri dell'algoritmo

La tabella seguente descrive i parametri che possono essere usati con l'algoritmo Microsoft Sequence Clustering.

Conteggio del Cluster
Specifica il numero approssimativo di cluster da compilare dall'algoritmo. Se il numero approssimativo di cluster non può essere compilato dai dati, l'algoritmo compila il maggior numero possibile di cluster. Se si imposta il parametro CLUSTER_COUNT su 0, l'algoritmo usa l'euristica per determinare al meglio il numero di cluster da compilare.

L'impostazione predefinita è 10.

Annotazioni

La specifica di un numero diverso da zero funge da suggerimento per l'algoritmo, che procede con l'obiettivo di trovare il numero specificato, ma potrebbe finire per trovare più o meno.

SUPPORTO_MINIMO
Specifica il numero minimo di case necessari per supportare un attributo per creare un cluster.

L'impostazione predefinita è 10.

STATI_DI_SEQUENZA_MASSIMI
Specifica il numero massimo di stati che una sequenza può avere.

L'impostazione di questo valore su un numero maggiore di 100 può causare la creazione di un modello che non fornisce informazioni significative.

Il valore predefinito è 64.

STATI_MASSIMI
Specifica il numero massimo di stati per un attributo non sequenza supportato dall'algoritmo. Se il numero di stati per un attributo non sequenza è maggiore del numero massimo di stati, l'algoritmo usa gli stati più diffusi dell'attributo e considera gli stati rimanenti come Missing.

L'impostazione predefinita è 100.

Bandiere di modellazione

I flag di modellazione seguenti sono supportati per l'uso con l'algoritmo Microsoft Sequence Clustering.

NON NULLO
Indica che la colonna non può contenere un valore Null. Se Analysis Services rileva un valore Null durante il training del modello, verrà generato un errore.

Si applica alla colonna della struttura di mining.

MODEL_EXISTENCE_ONLY
Significa che la colonna verrà considerata come con due possibili stati: Missing e Existing. Un valore Null viene considerato come valore Missing .

Si applica alla colonna del modello di mining.

Per altre informazioni sull'uso dei valori mancanti nei modelli di data mining e sul modo in cui i valori mancanti influiscono sui punteggi di probabilità, vedere Valori mancanti (Analysis Services - Data mining).

Requisiti

La tabella dei casi deve avere una colonna ID caso. Facoltativamente, la tabella case può contenere altre colonne in cui sono archiviati gli attributi relativi al case.

L'algoritmo Microsoft Sequence Clustering richiede informazioni sulla sequenza, archiviate come tabella nidificata. La tabella nidificata deve avere una singola colonna di Sequenza chiave. Una Key Sequence colonna può contenere qualsiasi tipo di dati che può essere ordinato, inclusi i tipi di dati stringa, ma la colonna deve contenere valori univoci per ogni caso. Inoltre, prima di elaborare il modello, è necessario assicurarsi che sia la tabella dei casi che la tabella nidificata siano ordinate in ordine crescente sulla chiave che collega le tabelle.

Annotazioni

Se si crea un modello che usa l'algoritmo Microsoft Sequence ma non si usa una colonna di sequenza, il modello risultante non conterrà alcuna sequenza, ma si limita a raggruppare i case in base ad altri attributi inclusi nel modello.

Colonne di input e prevedibili

L'algoritmo Microsoft Sequence Clustering supporta le colonne di input specifiche e le colonne stimabili elencate nella tabella seguente. Per altre informazioni sui tipi di contenuto usati in un modello di data mining, vedere Tipi di contenuto (data mining).

colonna Tipi di contenuto
Attributo di input Continuo, Ciclico, Discreto, Discretizzato, Chiave, Sequenza di Chiavi, Tabella e Ordinato.
Attributo prevedibile Continuo, Ciclico, Discreto, Discretizzato, Tabella e Ordinato

Osservazioni:

Vedere anche

Algoritmo di Clusterizzazione Sequenziale di Microsoft
Esempi di query del modello sequence clustering
Contenuto del modello di data mining per i modelli di clustering di sequenze (Analysis Services - Data mining)

  • Last updated on