
Nella teoria delle decisioni (per esempio nella gestione dei rischi), un albero di decisione è un grafo di decisioni e delle loro possibili conseguenze, (incluso i relativi costi, risorse e rischi) utilizzato per creare un 'piano di azioni' ("plan") mirato ad uno scopo ("goal"). Un albero di decisione è costruito al fine di supportare l'azione decisionale ("decision making").
Nel machine learning un albero di decisione è un modello predittivo, dove ogni nodo interno rappresenta una variabile, un arco verso un nodo figlio rappresenta un possibile valore per quella proprietà e una foglia il valore predetto per la variabile obiettivo a partire dai valori delle altre proprietà, che nell'albero è rappresentato dal cammino ("path") dal nodo radice ("root") al nodo foglia.
Normalmente un albero di decisione viene costruito utilizzando tecniche di apprendimento a partire dall'insieme dei dati iniziali ("data set"), il quale può essere diviso in due sottoinsiemi: il "training set" sulla base del quale si crea la struttura dell'albero e il "test set" che viene utilizzato per testare l'accuratezza del modello predittivo così creato.
Nel data mining un albero di decisione viene utilizzato per classificare le istanze di grandi quantità di dati (per questo viene anche chiamato albero di classificazione). In questo ambito un albero di decisione descrive una struttura ad albero dove i nodi foglia rappresentano le classificazioni e le ramificazioni l'insieme delle proprietà che portano a quelle classificazioni. Di conseguenza ogni nodo interno risulta essere una macro-classe costituita dall'unione delle classi associate ai suoi nodi figli.
Il predicato che si associa ad ogni nodo interno (sulla base del quale avviene la ripartizione dei dati) è chiamato "condizione di split".
In molte situazioni è utile definire un criterio di arresto ("halting"), o anche "criterio di potatura" ("pruning") al fine di determinarne la profondità massima. Questo perché il crescere della profondità di un albero (ovvero della sua dimensione) non influisce direttamente sulla bontà del modello. Infatti, una crescita eccessiva della dimensione dell'albero potrebbe portare solo ad aumento sproporzionato della complessità computazionale rispetto ai benefici riguardanti l'accuratezza delle previsioni/classificazioni.
Una sua evoluzione è la tecnica foresta casuale ("random forest").
I parametri più largamente usati per le condizioni di split sono:
formula_1
L'indice di Gini raggiunge il suo minimo (zero) quando il nodo appartiene ad una singola categoria. 
formula_2
In entrambe le formule "f" rappresenta la frequenza del valore "j" nel nodo "i".
L'indice di Gini e la variazione di entropia sono i parametri che vengono usualmente utilizzati per guidare la costruzione dell'albero, mentre la valutazione del tasso di errore nella classificazione viene utilizzato per effettuare una ottimizzazione dell'albero nota come processo di "pruning" ("potatura" dei nodi superflui). Poiché, in generale, in un buon albero di decisione i nodi foglia dovrebbero essere il più possibile "puri" (ovvero contenere solo istanze di dati che appartengono ad una sola classe), un'ottimizzazione dell'albero consiste nel cercare di minimizzare il livello di entropia man mano che si scende dalla radice verso le foglie. In tal senso, la valutazione dell'entropia determina quali sono, fra le varie scelte a disposizione, le condizioni di split ottimali per l'albero di classificazione.


Le macchine a vettori di supporto (SVM, dall'inglese "Support-Vector Machines") sono dei modelli di apprendimento supervisionato associati ad algoritmi di apprendimento per la regressione e la classificazione. Dato un insieme di esempi per l'addestramento (training set), ognuno dei quali etichettato con la classe di appartenenza fra le due possibili classi, un algoritmo di addestramento per le SVM costruisce un modello che assegna i nuovi esempi ad una delle due classi, ottenendo quindi un classificatore lineare binario non probabilistico. Un modello SVM è una rappresentazione degli esempi come punti nello spazio, mappati in modo tale che gli esempi appartenenti alle due diverse categorie siano chiaramente separati da uno spazio il più possibile ampio. I nuovi esempi sono quindi mappati nello stesso spazio e la predizione della categoria alla quale appartengono viene fatta sulla base del lato nel quale ricade.
Oltre alla classificazione lineare è possibile fare uso delle SVM per svolgere efficacemente la classificazione non-lineare utilizzando il metodo kernel, mappando implicitamente i loro input in uno spazio delle feature multi-dimensionale.
Quando gli esempi non sono etichettati è impossibile addestrare in modo supervisionato e si rende necessario l'apprendimento non supervisionato, questo approccio cerca di identificare i naturali cluster in cui si raggruppano i dati, mappando successivamente i nuovi dati nei cluster ottenuti. L'algoritmo di clustering a vettori di supporto, creato da Hava Siegelmann e Vladimir N. Vapnik, applica le statistiche dei vettori di supporto, sviluppate negli algoritmi delle SVM, per classificare dati non etichettati, ed è uno degli algoritmi di clustering maggiormente utilizzato nelle applicazioni industriali.
Le macchine a vettori di supporto possono essere pensate come una tecnica alternativa per l'apprendimento di classificatori polinomiali, contrapposta alle tecniche classiche di addestramento delle reti neurali artificiali.
Le reti neurali ad un solo strato hanno un algoritmo di apprendimento efficiente, ma sono utili soltanto nel caso di dati linearmente separabili. Viceversa, le reti neurali multistrato possono rappresentare funzioni non lineari, ma sono difficili da addestrare a causa dell'alto numero di dimensioni dello spazio dei pesi e poiché le tecniche più diffuse, come la "back-propagation", permettono di ottenere i pesi della rete risolvendo un problema di ottimizzazione non convesso e non vincolato che, di conseguenza, presenta un numero indeterminato di minimi locali.
La tecnica di addestramento SVM risolve entrambi i problemi: presenta un algoritmo efficiente ed è in grado di rappresentare funzioni non lineari complesse. I parametri caratteristici della rete sono ottenuti mediante la soluzione di un problema di programmazione quadratica convesso con vincoli di uguaglianza o di tipo box (in cui il valore del parametro deve essere mantenuto all'interno di un intervallo), che prevede un unico minimo globale.
Formalmente, una macchina a vettori di supporto costruisce un iperpiano o un insieme di iperpiani in uno spazio a più dimensioni o a infinite dimensioni, il quale può essere usato per classificazione, regressione e altri scopi come il rilevamento delle anomalie. Intuitivamente una buona separazione si può ottenere dall'iperpiano che ha la distanza maggiore dal punto (del training set) più vicino di ognuna delle classi; in generale maggiore è il margine fra questi punti, minore è l'errore di generalizzazione commesso dal classificatore.
Mentre il problema originale può essere definito in uno spazio di finite dimensioni, spesso succede che gli insiemi da distinguere non siano linearmente separabili in quello spazio. Per questo motivo è stato proposto che lo spazio originale di dimensioni finite venisse mappato in uno spazio con un numero di dimensioni maggiore, rendendo presumibilmente più facile trovare una separazione in questo nuovo spazio. Per mantenere il carico computazionale accettabile, i mapping utilizzati dalle SVM sono fatti in modo tale che i prodotti scalari dei vettori delle coppie di punti in input siano calcolati facilmente in termini delle variabili dello spazio originale, attraverso la loro definizione in termini di una funzione kernel formula_1scelta in base al problema da risolvere. Gli iperpiani in uno spazio multidimensionale sono definiti come l'insieme di punti il cui prodotto scalare con un vettore in quello spazio è costante, dove tale insieme di vettori è un insieme ortogonale (e quindi minimale) di vettori che definiscono un iperpiano. I vettori che definiscono gli iperpiani possono essere scelti come combinazioni lineari con parametri formula_2delle immagini dei vettori delle feature formula_3. Con tale scelta dell'iperpiano, i punti formula_4 nello spazio delle feature che sono mappati nell'iperpiano sono definiti dalla relazione formula_5. Si noti che se formula_1 diventa più piccolo al crescere di formula_7 rispetto ad formula_4, ogni termine della somma misura il grado di vicinanza del punto di test formula_4 al corrispondente punto di base formula_3. Si noti che l'insieme di punti formula_4 mappato in un qualsiasi iperpiano può produrre un risultato piuttosto complicato, permettendo discriminazioni molto più complesse fra insiemi non completamente convessi nello spazio originario.
L'originale algoritmo SVM è stato inventato da Vladimir Vapnik e Aleksej Červonenkis nel 1963.
Nel 1992 Bernhard Boser, Isabelle Guyon e lo stesso Vapnik suggerirono un modo per creare un classificatore non lineare applicando il metodo kernel all'iperpiano con il massimo margine. Lo standard corrente che propone l'utilizzo di un margine leggero fu invece proposto da Corinna Cortes e Vapnik nel 1993 e pubblicato nel 1995.
Alcune applicazioni per cui le SVM sono state utilizzate con successo
sono:
I seguenti framework mettono a disposizione un'implementazione di SVM:
