Riferimento tecnico per l'algoritmo Microsoft Decision Trees
L'algoritmo Microsoft Decision Trees è un algoritmo ibrido che incorpora diversi metodi per la creazione di un albero e supporta più attività analitiche, tra le quali sono incluse la regressione, la classificazione e l'associazione. Tale algoritmo supporta la modellazione di attributi discreti e continui.
In questo argomento viene illustrata l'implementazione dell'algoritmo, viene mostrato come personalizzarne il comportamento in base alle diverse attività e vengono forniti collegamenti a ulteriori informazioni sull'esecuzione di query sui modelli di albero delle decisioni.
Implementazione dell'algoritmo Decision Trees
L'algoritmo Microsoft Decision Trees apprende le reti Bayes da una combinazione dei dati statistici e delle conoscenze precedenti. Una parte importante dell'algoritmo è costituita dalla metodologia per la stima del valore delle conoscenze precedenti necessarie per l'apprendimento. L'approccio è basato sul presupposto dell'equivalenza di probabilità, ossia i dati non devono permettere la discriminazione delle strutture di rete che altrimenti rappresenterebbero le stesse asserzioni dell'indipendenza condizionale.
Si presuppone che per ogni case sia presente una singola rete Bayes con probabilità a priori, cui è associata una sola misura di confidenza. Utilizzando queste reti con probabilità a priori, l'algoritmo calcola quindi le probabilità a posteriori relative delle strutture di rete a partire dai dati di training correnti e identifica le strutture di rete con le probabilità a posteriori più elevate.
L'algoritmo Microsoft Decision Trees utilizza diversi metodi per calcolare l'albero ideale. Il metodo utilizzato dipende dal tipo di attività, ovvero regressione lineare, classificazione o analisi di associazione. Un solo modello può contenere più alberi per i diversi attributi stimabili. Ogni albero può inoltre contenere più rami, a seconda del numero di attributi e valori presenti nei dati. La forma e la profondità dell'albero incorporato in un determinato modello dipendono dal metodo di valutazione e dagli altri parametri utilizzati. Le modifiche apportate ai parametri possono influire anche sul punto in cui i nodi si dividono.
Compilazione dell'albero
Quando l'algoritmo Microsoft Decision Trees crea il set dei possibili valori di input, esegue la feature selection per identificare gli attributi e i valori che forniscono il maggior numero di informazioni ignorando i valori che sono molto rari. L'algoritmo inoltre inserisce i valori in contenitori per crearne raggruppamenti che possano essere elaborati come singole unità al fine di ottimizzare le prestazioni.
La compilazione di un albero avviene mediante la definizione delle correlazioni tra un input e il risultato di destinazione. Dopo aver correlato tutti gli attributi, l'algoritmo identifica l'attributo specifico che separa i risultati in modo più netto. Il punto di separazione ideale viene misurato mediante un'equazione che calcola l'Information Gain. L'attributo che presenta il miglior punteggio in termini di Information Gain viene utilizzato per dividere i case in subset che vengono quindi analizzati in modo ricorsivo dallo stesso processo fino a quando non sia possibile suddividere ulteriormente l'albero.
L'equazione esatta utilizzata per valutare l'Information Gain dipende dai parametri impostati quando è stato creato l'algoritmo, dal tipo di dati della colonna stimabile e dal tipo di dati dell'input.
Input discreti e continui
Quando sia l'attributo stimabile sia gli input sono discreti, il conteggio dei risultati per input implica la creazione di una matrice e la generazione di punteggi per ogni cella della matrice.
Quando invece l'attributo stimabile è discreto e gli input sono continui, l'input delle colonne continue viene discretizzato automaticamente. È possibile accettare l'impostazione predefinita e impostare Analysis Services sulla ricerca del numero ottimale di contenitori o controllare il modo in cui gli input continui vengono discretizzati impostando le proprietà DiscretizationMethod e DiscretizationBucketCount. Per ulteriori informazioni, vedere Procedura: Modifica della discretizzazione di una colonna in un modello di data mining.
Per gli attributi continui, l'algoritmo utilizza la regressione lineare per determinare il punto in cui l'albero delle decisioni si divide.
Quando l'attributo stimabile è un tipo di dati numerico continuo, la caratteristica di selezione degli attributi viene applicata anche agli output in modo da ridurre il numero possibile di risultati e da velocizzare la compilazione del modello. È possibile modificare la soglia per la caratteristica di selezione degli attributi e di conseguenza aumentare o ridurre il numero di valori possibili impostando il parametro MAXIMUM_OUTPUT_ATTRIBUTES.
Per una spiegazione più dettagliata del funzionamento dell'algoritmo Microsoft Decision Trees nel caso di colonne stimabili discrete, vedere Learning Bayesian Networks: The Combination of Knowledge and Statistical Data. Per ulteriori informazioni sul funzionamento dell'algoritmo Microsoft Decision Trees nel caso di colonne stimabili continue, vedere l'appendice del documento Autoregressive Tree Models for Time-Series Analysis.
Metodi di valutazione e caratteristica di selezione degli attributi
L'algoritmo Microsoft Decision Trees offre tre formule per valutare l'Information Gain, ovvero l'entropia di Shannon, la rete Bayes con probabilità a priori K2 e la rete Bayes Dirichlet con probabilità a priori a distribuzione uniforme. Tutti e tre i metodi sono consolidati nel campo del data mining. È consigliabile provare a utilizzare diversi parametri e metodi di valutazione in modo da individuare quelli che forniscono i migliori risultati. Per ulteriori informazioni sui metodi di valutazione, vedere Selezione caratteristiche.
Tutti gli algoritmi di data mining Analysis Services utilizzano automaticamente la caratteristica di selezione degli attributi per migliorare l'analisi e ridurre il carico di elaborazione. Il metodo utilizzato per la caratteristica di selezione degli attributi dipende dall'algoritmo impiegato per la compilazione del modello. I parametri dell'algoritmo che controllano la caratteristica di selezione degli attributi per un modello di albero delle decisioni sono MAXIMUM_INPUT_ATTRIBUTES e MAXIMUM_OUTPUT.
Algoritmo |
Metodo di analisi |
Commenti |
|---|---|---|
Decision Trees |
Punteggio di interesse Entropia di Shannon Bayes con probabilità a priori K2 Equivalente Bayes Dirichlet con probabilità a priori a distribuzione uniforme (impostazione predefinita) |
Se esistono colonne contenenti valori continui non binari, viene utilizzato il punteggio di interesse per tutte le colonne, per assicurare coerenza. In caso contrario, viene utilizzato il metodo predefinito o specificato. |
Linear Regression |
Punteggio di interesse |
L'algoritmo Linear Regression può utilizzare solo il punteggio di interesse, perché supporta solo colonne continue. |
Scalabilità e prestazioni
La classificazione è un'importante strategia di data mining. In genere, la quantità di informazioni necessaria a classificare i case cresce in modo direttamente proporzionale al numero di record di input. Ciò limita le dimensioni dei dati classificabili. L'algoritmo Microsoft Decision Trees utilizza i metodi seguenti per risolvere questi problemi, migliorare le prestazioni ed eliminare le restrizioni relative alla memoria:
Caratteristica di selezione degli attributi per ottimizzare la scelta degli attributi.
Valutazione con il metodo Bayes per controllare l'aumento delle dimensioni dell'albero.
Ottimizzazione della creazione di contenitori per gli attributi continui.
Raggruppamento dinamico dei valori di input per individuare i valori più importanti.
L'algoritmo Microsoft Decision Trees è veloce e scalabile ed è stato progettato per essere facilmente eseguito in parallelo, ovvero per fare in modo che tutti i processori interagiscano per compilare un singolo modello coerente. La combinazione di queste caratteristiche rende il classificatore dell'albero delle decisioni uno strumento ideale per il data mining.
Se i vincoli relativi alle prestazioni sono rigidi, è possibile migliorare il tempo di elaborazione durante il training di un modello di albero delle decisioni tramite i metodi seguenti. In tal caso, è tuttavia necessario essere consapevoli del fatto che l'eliminazione degli attributi finalizzata al miglioramento delle prestazioni determinerà la modifica dei risultati del modello rendendoli meno rappresentativi della popolazione totale.
Aumentare il valore del parametro COMPLEXITY_PENALTY per limitare l'aumento delle dimensioni dell'albero.
Limitare il numero di elementi nei modelli di associazione per compilare un numero limitato di alberi.
Aumentare il valore del parametro MINIMUM_SUPPORT per evitare l'overfitting.
Limitare il numero di valori discreti di qualsiasi attributo a 10 o un numero inferiore. È possibile provare a raggruppare i valori in modi e modelli diversi.
Nota
È possibile utilizzare gli strumenti di esplorazione dei dati disponibili in SQL Server 2008 Integration Services per visualizzare la distribuzione di valori nei dati e raggruppare i valori in modo appropriato prima di dare inizio al data mining. Per ulteriori informazioni, vedere Profiling dei dati tramite l'attività Profiling dati e il relativo visualizzatore. È inoltre possibile utilizzare anche i componenti aggiuntivi Data Mining per Excel 2007 per esplorare, raggruppare e rietichettare i dati in Microsoft Excel.
Personalizzazione dell'algoritmo Decision Trees
L'algoritmo Microsoft Decision Trees supporta parametri che influiscono sulle prestazioni e sull'accuratezza del modello di data mining risultante. È anche possibile impostare flag di modellazione nelle colonne del modello o della struttura di data mining per controllare la modalità di elaborazione dei dati.
Impostazione dei parametri dell'algoritmo
Nella tabella seguente vengono descritti i parametri che è possibile utilizzare con l'algoritmo Microsoft Decision Trees.
COMPLEXITY_PENALTY
Consente di controllare l'aumento delle dimensioni dell'albero delle decisioni. Un valore basso comporta l'aumento del numero di divisioni, mentre un valore alto comporta la riduzione del numero di divisioni. Il valore predefinito è basato sul numero di attributi per un modello specifico, come descritto nell'elenco seguente:Per un numero di attributi compreso tra 1 e 9, il valore predefinito è 0,5.
Per un numero di attributi compreso tra 10 e 99, il valore predefinito è 0,9.
Per un numero di attributi uguale o superiore a 100, il valore predefinito è 0,99.
FORCE_REGRESSOR
Impone all'algoritmo l'uso delle colonne specificate come regressori, indipendentemente dall'importanza delle colonne calcolate dall'algoritmo. Questo parametro viene utilizzato solo per gli alberi delle decisioni che stimano un attributo continuo.Nota
Impostando questo parametro, all'algoritmo viene imposto il tentativo di utilizzare l'attributo come regressore. L'eventualità che l'attributo venga realmente utilizzato come regressore nel modello finale dipende invece dai risultati dell'analisi. Per individuare le colonne utilizzate come regressori, è possibile eseguire query sul contenuto del modello.
[SQL Server Enterprise]
MAXIMUM_INPUT_ATTRIBUTES
Definisce il numero di attributi di input che l'algoritmo è in grado di gestire prima di richiamare la caratteristica di selezione degli attributi.Il valore predefinito è 255.
Impostare questo valore su 0 per disattivare la caratteristica di selezione degli attributi.
[SQL Server Enterprise]
MAXIMUM_OUTPUT_ATTRIBUTES
Definisce il numero di attributi di output che l'algoritmo è in grado di gestire prima di richiamare la caratteristica di selezione degli attributi.Il valore predefinito è 255.
Impostare questo valore su 0 per disattivare la caratteristica di selezione degli attributi.
[SQL Server Enterprise]
MINIMUM_SUPPORT
Determina il numero minimo di case foglia necessari per generare una divisione nell'albero delle decisioni.Il valore predefinito è 10.
Può essere necessario aumentare il valore se il set di dati è di dimensioni molto elevate per evitare un overtraining.
SCORE_METHOD
Determina il metodo utilizzato per calcolare il punteggio di divisione. Sono disponibili le opzioni seguenti:ID
Nome
1
Entropia
2
Bayes con probabilità a priori K2
3
Equivalente Bayes Dirichlet con probabilità a priori a distribuzione uniforme
(impostazione predefinita)
Il valore predefinito è 3.
Per una spiegazione relativa ai metodi di valutazione, vedere Selezione caratteristiche.
SPLIT_METHOD
Determina il metodo utilizzato per la divisione del nodo. Sono disponibili le opzioni seguenti:ID
Nome
1
Binary: Indica che l'albero deve essere suddiviso in due rami indipendentemente dal numero effettivo dei valori presenti per l'attributo.
2
Complete: Indica che nell'albero possono essere create tante divisioni quanti sono i valori degli attributi.
3
Both: Specifica che Analysis Services consente di scegliere se utilizzare una divisione binaria o completa per ottenere i risultati migliori.
Il valore predefinito è 3.
Flag di modellazione
L'algoritmo Microsoft Decision Trees supporta i flag di modellazione seguenti. Quando si crea la struttura o il modello di data mining, i flag di modellazione vengono definiti per specificare la modalità di gestione dei valori presenti in ogni colonna durante l'analisi. Per ulteriori informazioni, vedere Flag di modellazione (data mining).
Flag di modellazione |
Descrizione |
|---|---|
MODEL_EXISTENCE_ONLY |
Indica che la colonna verrà considerata come se presentasse due stati possibili: Missing e Existing. Un valore Null è un valore mancante. Si applica alle colonne del modello di data mining. |
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 alle colonne della struttura di data mining. |
Regressori nei modelli di albero delle decisioni
Anche se non si utilizza l'algoritmo Microsoft Linear Regression, qualsiasi modello di albero delle decisioni con input e output numerici continui può contenere nodi che rappresentano una regressione su un attributo continuo.
Non è necessario specificare che una colonna di dati numerici continui rappresenta un regressore. L'algoritmo Microsoft Decision Trees utilizzerà automaticamente la colonna come potenziale regressore e suddividerà il set di dati in aree con modelli significativi anche se non si imposta il flag REGRESSOR nella colonna.
È invece possibile utilizzare il parametro FORCE_REGRESSOR per assicurarsi che l'algoritmo utilizzi un determinato regressore. Questo parametro può essere utilizzato solo con gli algoritmi Microsoft Decision Trees e Microsoft Linear Regression. Quando si imposta il flag di modellazione, l'algoritmo tenterà di individuare equazioni di regressione nel formato a*C1 + b*C2 + ... in base agli schemi presenti nei nodi dell'albero. Viene calcolata la somma dei residui e, se la deviazione è eccessiva, nell'albero viene imposta una divisione.
Se, ad esempio, si stima il comportamento di acquisto dei clienti utilizzando Income come attributo ed è stato impostato il flag di modellazione REGRESSOR nella colonna, l'algoritmo tenta innanzitutto di adattare i valori Income utilizzando una formula di regressione standard. Se la deviazione è eccessiva, la formula di regressione viene abbandonata e l'albero viene diviso in base a un altro attributo. L'algoritmo Decision Trees tenta quindi di adattare un regressore per il reddito in ognuno dei rami dopo la divisione.
Requisiti
Un modello di albero delle decisioni deve contenere una colonna chiave, le colonne di input e almeno una colonna stimabile.
Colonne di input e stimabili
L'algoritmo Microsoft Decision Trees supporta le colonne di input e le 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, Ordered, Table |
Attributo stimabile |
Continuous, Cyclical, Discrete, Discretized, Ordered, Table |
Nota
Sono supportati i tipi di contenuto Cyclical e Ordered ma l'algoritmo li considera come valori discreti e non esegue un'elaborazione speciale.