Gli algoritmi degli alberi di decisione di solito implementano la potatura, cioè la rimozione di un sotto albero e la sostituzione con un nodo foglia. Rendendo così le regole dell'albero più generali.

First of all i want to explain what is overfitting and give my view of explination?

A Hypothesis H is overfit the Training data. If there is another Hypothesis H' such that H' has more error than H on the same Training data T but H' has less error than H on Test data T'

Overfitting is due to

1. hign noise of data
2. Less training data

We are defining the classifier based on the Training data so it obviously have hign accuracy we have to check whether that classifier is giving correct result by taking Test data.

When we are checking up to some extent the classifier gives correct results (low error rate) on Test data and again it gives incorrect results (high error rate) as the number of nodes increases in Decision Tree . The point where it's error rate increases causes Overfitting.

Techniques to deal with Overfitting?

Pre-Pruning: Stop growing the tree when information gain is statically significant. i.e..

1. Evaluate the splits before growing the tree. If the split gives less error on Test data then attach the node to decision tree otherwise discard that split.
2. Repeat this process to all the nodes.

Typical stopping conditions for a node:

1. Stop if all the examples belong to same class
2. Stop if all the attribute values are same

Post -Pruning: Grow full tree and remove unecessary nodes.

1. After removing the nodes it has to increase the accuracy on Test data.
2. Any non-leaf node is eligible for removing
3. Minimum description length (MDL) and cross validation algorithms is used in post pruning.

Apply pruning. Tune the following parameters and re-observe the performance please.
(1) max_depth: represents how deep your tree will be (1 to 32). More you increase the number, more will be the number of splits and the possibility of overfitting.
(2) min_samples_split: represents minimum number of samples required to split an internal node. If you use 100% of the samples at each node, it will show underfitting, if you use 10%, it might show overfitting. Tune it accordingly.
(3) min_samples_leaf: represents min. no. of samples required to be in the leaf node. The more you increase the number, more is the possibility of overfitting.

Irrespective of whatever classifier you are using, apply cross validation. Partition the training data set into 65%-70% training and 30%-35% validation to avoid overfitting. If still the problem of overfitting persists, use Random Forest classifier instead of a single decision tree. RF affronta questo problema automaticamente riducendo la varianza ma senza aumentare il bias.

In termini comuni possiamo dire che l'overfitting si verifica negli alberi decisionali a causa dell'overtraining o a causa della mancanza di dati con una distribuzione sufficiente che porta all'overfitting. In questo DT dà una maggiore accuratezza sui dati di allenamento ma l'accuratezza diminuisce notevolmente per i dati di test.

L'overfitting potrebbe essere evitato con il PRUNING.

Dividere i dati in 3 set: allenamento, test, validazione e procedere

Metodo K-fold

In Narrow sense, Regularization (commonly defined as adding Ridge or Lasso Penalty) is difficult to implement for Trees. Tree is a heuristic algorithm.

In broader sense, Regularization (as any means to prevent overfit) for Trees is done by:

1. limit max. depth of trees
2. ensembles / bag more than just 1 tree
3. set stricter stopping criterion on when to split a node further (e.g. min gain, number of samples etc.)

Grazie per A2A! Avendo letto anche le altre risposte, direi che i modi per prevenire l'overfitting dipendono dal tipo di algoritmo di formazione utilizzato e anche dal tipo di set di dati che hai. Ritengo che i seguenti siano i punti importanti da considerare :

(1) Deep Learning (modelli basati su CNN, RNN, LSTM, ecc.) - Il modo standard per prevenire l'overfitting è quello di utilizzare la procedura di dropout durante l'addestramento. Questo è normalmente incorporato per impostazione predefinita in tutte le definizioni di architettura di rete che si possono ottenere su GitHub. Inoltre, si impiega sempre la regolarizzazione L2 sui pesi della rete durante l'allenamento. La regolarizzazione L1 normalmente non funziona bene con l'apprendimento profondo, e dovrebbe essere per lo più evitata. Il dropout con la regolarizzazione L2 dovrebbe generalmente bastare.

Al fine di garantire che il vostro modello non si stia allenando inutilmente, è possibile avere un controllo simultaneo sull'errore di convalida e sull'errore di allenamento. Se si verifica uno scenario in cui l'errore di addestramento diminuisce ma l'errore di convalida aumenta, indica un overfitting (su quella scala temporale), e si dovrebbe abbassare il tasso di apprendimento di qualche buon fattore (di solito 10 volte) per garantire che ci si alleni nel giusto spazio della funzione di errore. Empiricamente, i modelli di deep learning sono addestrati con la discesa del gradiente stocastico basata sul momentum, quindi nel caso in cui non si controlli nemmeno la validazione e l'errore di addestramento, non si ha comunque un overfitting nel lungo periodo, a causa della procedura di dropout in atto.

Ora, la convergenza dell'addestramento qui dipende dal tipo di classi nel dataset che si mira a discriminare. Come per le CNN, se le classi possono essere separate facilmente nello spazio dell'immagine (come gli oggetti), allora la precisione sarà alta e la convergenza sarà lenta, poiché la rete vedrà abbastanza opportunità per separare le classi. D'altra parte, per alcune classi che sono di natura astratta (come gli attributi dei volti, gli attributi degli abiti di moda, le classi a grana fine), la loro discriminazione nello spazio dell'immagine non è facile da ottenere, e quindi si potrebbe vedere una convergenza più veloce, forse una precisione ragionevole, ma un potenziale di generalizzazione inferiore. Questo non è esattamente overfitting, ma è un tipo di overfitting. Qui, la rete sta imparando solo alcuni (o addirittura sbagliati) aspetti della discriminazione, a causa delle limitazioni delle operazioni e dell'architettura sottostante, e non perché il modello è complesso o ci sono troppi parametri.

(2) Classificatori a margine massimo (SVM) - Il trucco principale per evitare l'overfitting negli SVM è quello di sintonizzare attentamente il parametro di regolarizzazione C, insieme ai parametri del kernel (nel caso in cui si stia eseguendo un kernel (non lineare) SVM). La messa a punto dei parametri è generalmente fatta usando la convalida incrociata o il set di convalida.

In generale, l'apprendimento in ensemble (come il dropout) e la regolarizzazione sono i modi standard per ridurre l'overfitting, ma si dovrebbe vedere quale algoritmo di formazione sottoscrive cosa in quale capacità. Spero che questo aiuti !!

To answer this, I will begin by describing the overfitting phenomenon.

One of the major reason we want models is to be able to describe an underlying pattern. Unfortunately, real life data is not without some level of noise (or outliers). For the most part we want the model to capture the signal in the data and not the noise.

Now, in an effort to capture the underlying pattern in the data accurately, the model may incorporate the noise. The implication is that the derived model fits the modelling data so well but does not generalize well enough to other samples that have not been included in the modelling process.

Overfitting is suspect when the model accuracy is high with respect to the data used in training the model but drops significantly with new data. Effectively the model knows the training data well but does not generalize. This makes the model useless for purposes such as prediction.

A simple way to detect this effect in practice is cross-validation. This attempts to examine the trained model with new data set to check it’s predictive accuracy. Given a dataset, some portion of this is held out (say 30%) while the rest is used in training the model. Upon training the model, the held out data is then used to check the accuracy compared to the accuracy of derived from the data used in training. A significant variance in these two flags overfitting.

The diametric opposite of overfitting is under-fitting and the topic of Bias–variance tradeoff helps for better understanding.

Simple answer, don’t use a decision tree classifier. Ensemble techniques like Random Forest and Gradient boosting perform better and can tackle overfitting for you.

If you really want to use decision tree classifier, pruning is the way to go. Setting max_depth stops your tree from growing too much and doesn’t start learning the noise in your data and won’t generalize well.

The documentation for decision tree is really good on sklearn and has good information on hyperparameters: 1.10. Decision Trees

Cross-validation also helps with overfitting. I usually use hyperparameter tuning like grid search cv or random search cv to find the best parameters.

Try these techniques and see that your test set score should be near or less than your training set score. Hope this helps.

Sì, un modello di foresta casuale può andare in overfit. Discutiamo cosa significa.

Overfitting significa che il modello si adatta al set di dati utilizzato per crearlo, ma non fornisce buoni risultati quando applicato ad altri dati.

Questo può accadere con qualsiasi tecnica di modellazione. Ripeto, l'overfitting può accadere con qualsiasi tecnica di modellazione.

Overfitting è semplicemente adattare un modello a un campione di dati che non rappresenta bene la popolazione da cui è stato tratto. Questo potrebbe essere dovuto semplicemente a piccole dimensioni del campione, ma più spesso, il problema è il campionamento non casuale.

Tutti i metodi di modellazione statistica sono basati sulla teoria che assume che i dati siano un campione estratto casualmente dalla popolazione che rappresenta. In pratica, però, i modelli sono spesso sviluppati utilizzando dati che non soddisfano questo requisito.

Decision Trees

• Decision tree is a hierarchical tree structure that can be used to divide up a large collection of records into smaller sets of classes by applying a sequence of simple decision rules.
• A decision tree model consists of a set of rules for dividing a large heterogenous population into smaller, more homogenous (mutually exclusive) classes.
• The attributes of the classes can be any type of variables from binary, nominal, ordinal and quantitative values, while the classes must be qualitative type (categorical or binary, or ordinal).
• In short, given a data of attributes together with its classes, a decision tree produces a sequence of rules ( or series of questions ) that can be used to recognize the class.
• One rule is applied after another, resulting in a hierarchy of segments within segments. The hierarchy is called a tree, and each segment is called a node.
• With each successive division, the members of the resulting sets become more and more similar to each other.
• Hence, the algorithm used to construct decision tree is referred to as recursive partitioning.
• The algorithm is popularly known as CART - Classification And Regression Trees.

Example:

Consider the above scenario of a factory where

• Expanding factor costs $1.5 million, probability of good economy is 0.4 (40%) which leads to $6 million profit and probability of bad economy is 0.6 (60%) which leads to $2 million profit.
• Not expanding factor with $0 cost, probability of good economy is 0.4 which leads to $3M profit and probability of bad economy is 0.6 which leads to $1M profit.

The management needs to take a decision to expand or not based on the above data,

NetExpand = ( 0.4 * 6 + 0.6 * 2) - 1.5 = $2.1M

NetNo Expand = ( 0.4 * 3 + 0.6 * 1) - 0 = $1.8M

$2.1M > $1.8M, therefore the factory should be expanded

Applications:

• Predicting tumor cells as benign or malignant
• Classifying credit card transactions as legitimate or fraudulent
• Classifying buyers from non-buyers
• Decision on whether or not to approve a loan
• Diagnosis of various diseases based on symptoms and profile.

Types of decision trees:

• The target variable is usually categorical and the decision tree is used either to calculate the probability that a given record belong to each of the category or to classify the record by assigning it to the most likely class ( or category).
• Decision tree can also be used to estimate the value of a continuous target variable. Tuttavia, i modelli di regressione e le reti neurali sono generalmente più appropriati per tali stime.