Riferimento tecnico per l'algoritmo Microsoft Sequence Clustering
L'algoritmo Microsoft Sequence Clustering è un algoritmo ibrido che utilizza l'analisi delle catene di Markov per identificare le sequenze ordinate e combina i risultati di tale analisi con le tecniche di clustering per generare cluster in base alle sequenze e agli altri attributi del modello. In questo argomento viene illustrato come implementare e personalizzare l'algoritmo e vengono descritti requisiti speciali per i modelli Sequence Clustering.
Per informazioni più generali sull'algoritmo, che includono le modalità di esplorazione e di esecuzione di query sui modelli Sequence Clustering, vedere Algoritmo Microsoft Sequence Clustering.
Implementazione dell'algoritmo Microsoft Sequence Clustering
Il modello Microsoft Sequence Clustering utilizza i 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 utilizza catene di Markov di ordine n, non un modello Markov nascosto.
Il numero di ordini di una catena Markov indica quanti stati vengono utilizzati 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 un stato dipende dai due stati precedenti e così via. Per ogni catena Markov una matrice della transizione archivia le transizioni per ogni combinazione di stati. Con l'aumentare della lunghezza della catena di Markov, aumenta anche la dimensione della matrice in modo esponenziale e la matrice diventa di tipo sparse. Anche il tempo di elaborazione aumenta proporzionalmente.
Potrebbe risultare utile visualizzare la catena utilizzando l'esempio di analisi clickstream che analizza le visite alle pagine Web di 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 utilizzato per il training è una sequenza di URL convertiti in un grafico che include il conteggio di tutte le istanze dello stesso percorso di clic. Nel grafico sono indicate ad esempio la probabilità che l'utente si sposti da pagina 1 a pagina 2 (10%), la probabilità che l'utente si sposti da pagina 1 a pagina 3 (20%) e così via. Unendo tutti i possibili percorsi e pezzi di percorso si ottiene un grafico che potrebbe essere molto più lungo e più complesso di qualsiasi singolo percorso osservato.
L'algoritmo Microsoft Sequence Clustering utilizza per impostazione predefinita il metodo di clustering Expectation Maximization (EM). Per ulteriori informazioni, vedere Riferimento tecnico per l'algoritmo Microsoft Clustering.
Le destinazioni del clustering sono attributi sia sequenziali che non sequenziali. Ogni cluster viene selezionato casualmente mediante una distribuzione di probabilità. Ogni cluster ha una catena Markov, che rappresenta il set completo di percorsi, e una matrice, che contiene le probabilità e le transizioni degli stati di sequenza. In base alla distribuzione iniziale, viene utilizzata la regola Bayes per calcolare la probabilità di un 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 di sequenza per creare cluster di case con attributi simili, come accade in un tipico modello di clustering.
Un modello Sequence Clustering tende a creare molti più cluster rispetto a un tipico modello di clustering. L'algoritmo Microsoft Sequence Clustering esegue pertanto la decomposizione del cluster per separare i cluster in base alle sequenze e ad altri attributi.
Funzionalità di selezione degli attributi in un modello Sequence Clustering
La funzionalità di selezione degli attributi non viene richiamata in caso di creazione delle sequenze, tuttavia si applica in fase di clustering.
Tipo di modello |
Metodo relativo alla funzionalità di selezione degli attributi |
Commenti |
|---|---|---|
Sequence Clustering |
Non utilizzato |
La funzionalità di selezione degli attributi non viene richiamata. È tuttavia possibile controllare il comportamento dell'algoritmo impostando i valori dei parametri MINIMUM_SUPPORT e MINIMUM_PROBABILIITY. |
Clustering |
Punteggio di interesse |
Anche se l'algoritmo Clustering può utilizzare algoritmi discreti o discretizzati, il punteggio di ogni attributo viene calcolato come distanza ed è continuo. Viene pertanto utilizzato il punteggio di interesse. |
Per ulteriori informazioni, vedere Selezione funzionalità.
Ottimizzazione delle prestazioni
L'algoritmo Microsoft Sequence Clustering supporta varie modalità di ottimizzazione dell'elaborazione:
Controllo del numero di cluster generati mediante l'impostazione di un valore per il parametro CLUSTER_COUNT.
Riduzione del numero di sequenze incluse come attributi mediante l'aumento del valore del parametro MINIMUM_SUPPORT. Di conseguenza, le sequenze rare vengono eliminate.
Riduzione della complessità prima dell'elaborazione del modello mediante il raggruppamento degli attributi correlati.
In generale, è possibile ottimizzare le prestazioni di un modello di catene Markov di ordine n in diversi modi:
Controllando la lunghezza delle possibili sequenze.
Riducendo a livello di programmazione il valore di n.
Archiviando solo le probabilità che superano una soglia specificata.
Una descrizione esaustiva di questi metodi esula dall'ambito del presente argomento.
Personalizzazione dell'algoritmo Sequence Clustering
L'algoritmo Microsoft Sequence Clustering supporta vari parametri che influiscono sul comportamento, sulle prestazioni e sull'accuratezza del modello di data mining risultante. È inoltre possibile modificare il comportamento del modello completato impostando flag di modellazione che controllano la modalità di elaborazione dei dati di training da parte dell'algoritmo.
Impostazione dei parametri dell'algoritmo
Nella tabella seguente sono descritti i parametri che possono essere utilizzati con l'algoritmo Microsoft Sequence Clustering.
CLUSTER_COUNT
Specifica il numero approssimativo di cluster che devono essere creati dall'algoritmo. Se i dati non consentono di creare il numero approssimativo di cluster, l'algoritmo creerà il maggior numero di cluster possibile. Se si imposta su 0 il parametro CLUSTER_COUNT, l'algoritmo utilizzerà l'euristica per determinare con maggiore accuratezza il numero di cluster da creare.Il valore predefinito è 10.
[!NOTA]
La specifica di un numero diverso da zero funge da hint per l'algoritmo, che procede con l'obiettivo di individuare il numero specificato ma potrebbe individuarne un numero maggiore o minore.
MINIMUM_SUPPORT
Specifica il numero minimo di case richiesto come supporto per un attributo per la creazione di un cluster.Il valore predefinito è 10.
MAXIMUM_SEQUENCE_STATES
Specifica il numero massimo di stati consentiti in una sequenza.Se si imposta un valore numerico maggiore di 100, l'algoritmo potrebbe creare un modello che non restituisce informazioni significative.
Il valore predefinito è 64.
MAXIMUM_STATES
Specifica il numero massimo di stati per un attributo fuori sequenza supportato dall'algoritmo. Se il numero di stati di un attributo fuori sequenza è maggiore del numero massimo, l'algoritmo utilizza gli stati più frequenti dell'attributo e considera gli stati rimanenti come Missing.Il valore predefinito è 100.
Flag di modellazione
Di seguito sono indicati i flag di modellazione il cui utilizzo è supportato con l'algoritmo Microsoft Sequence Clustering.
NOT NULL
Indica che la colonna non può contenere un valore Null. Se Analysis Services rileva un valore Null durante il training del modello, viene restituito un errore.Si applica alla colonna della struttura di data mining.
MODEL_EXISTENCE_ONLY
Indica che la colonna verrà considerata come se disponesse di due stati possibili: Missing e Existing. Un valore Null viene considerato come valore Missing.Si applica alla colonna del modello di data mining.
Per ulteriori informazioni sull'utilizzo di valori Missing nei modelli di data mining e su come tali valori influiscono sui punteggi di probabilità, vedere Valori mancanti (Analysis Services - Data mining).
Requisiti
La tabella del case deve includere una colonna relativa agli ID e può contenere altre colonne che archiviano attributi sul case.
L'algoritmo Microsoft Sequence Clustering richiede informazioni sulla sequenza, archiviate come tabella nidificata. Nella tabella nidificata deve essere presente un'unica colonna Key Sequence. Una colonna Key Sequence può contenere qualsiasi tipo di dati che è possibile ordinare, inclusi tipi di dati string, ma deve contenere valori univoci per ogni case. Prima di elaborare il modello, è inoltre necessario assicurarsi che sia la tabella del case sia la tabella nidificata vengano ordinate in ordine crescente sulla chiave che correla le tabelle.
[!NOTA]
Se si crea un modello che utilizza l'algoritmo di Microsoft Sequence ma non utilizza una colonna Sequence, il modello risultante non conterrà alcuna sequenza, ma raggrupperà semplicemente i case in base ad altri attributi inclusi nel modello.
Colonne di input e stimabili
L'algoritmo Microsoft Sequence Clustering supporta colonne di input e colonne stimabili specifiche, riportate nella tabella seguente. Per ulteriori informazioni sul significato dei tipi di contenuto utilizzati in un modello di data mining, vedere Tipi di contenuto (Data mining).
Colonna |
Tipi di contenuto |
|---|---|
Attributo di input |
Continuous, Cyclical, Discrete, Discretized, Key, Key Sequence, Table e Ordered |
Attributo stimabile |
Continuous, Cyclical, Discrete, Discretized, Table e Ordered |
Osservazioni
La stima delle sequenze mediante la funzione PredictSequence (DMX) è disponibile solo in SQL Server Enterprise.
L'algoritmo Microsoft Sequence Clustering non supporta l'utilizzo dello standard PMML (Predictive Model Markup Language) per la creazione dei modelli di data mining.
L'algoritmo Microsoft Sequence Clustering supporta il drill-through, l'utilizzo di modelli di data mining di OLAP e l'utilizzo di dimensioni di data mining.