Big Data Analytics
Classification algorithms
Lorenzo Malandri
Assistant Professor in Computer Science
[Link]@[Link]
Università degli studi di Milano - Bicoccq
Anno accademico 2025/26
Corso di laurea in Economia, Analisi dei Dati e Management
Decision trees
Decision trees are an iterative heuristic method which breaks the input space in regions and has
separate parameters for each region.
DT algorithm:
Dataset: IRIS, 3 kind of flowers:
1. All the observations belong to the root 50 setosa, 50 versicolor, 50 virginica
node. The root is included in the list of the
active nodes L
2. If L is empty, the procedure is stopped.
Otherwise an active node is chosen to be
splitted.
3. The optimal rule to split the node is
generated. The node is splitted. Stopping
condition are verified. If they are met for a
new node, it is deleted from the list of active
nodes and becomes a leaf. Then step 2 is
repeated.
Decision trees – Splitting rules
Simplest decision tree:
Binary: each node has only two branches
Univariate: the splitting rule is based on a single
attribute.
𝑙0 (level 0), root node:
Splitting rule if petal length ≤ 2.45: left branch.
𝑙1 (level 1), left node:
50 setosa, 0 versicolor, 0 virginica.
Thus the class is setosa, and impurity = 0.
How do we chose the splitting rule?
Max Δ(𝑖𝑚𝑝𝑢𝑟𝑖𝑡𝑦𝑙0 − 𝜇(𝑖𝑚𝑝𝑢𝑟𝑖𝑡𝑦𝑙1 ))
Decision trees
Splitting criteria: impurity measures
𝑝𝑘 : % of instances of (target) class k in
the node
𝐺𝐼𝑁𝐼 = 1 − 𝑝𝑘 2
𝑘=1
Entropy = − 𝑝𝑘 𝑙𝑜𝑔2 𝑝𝑘
𝑘=1
𝑀𝑖𝑠𝑐𝑙𝑎𝑠𝑠𝑖𝑓𝑖𝑐𝑎𝑡𝑖𝑜𝑛 = 1 − max 𝑝𝑘
𝑘
Impurity measures for a 2 class problem
Decision trees
The regions: since is a univariate tree, the region borders are orthogonal to the surface borders
Decision trees
1. Simple to explain/understand
2. Are flexible
3. Perform implicit feature selection (variable in top rules are the most important ones)
1. Tend to overfit the training
2. Greedy (may not find the best tree)
3. Only axis-aligned splits of data
Bayesian Classifiers
Are probabilistic classification models which compute the posterior probability 𝑃 𝑦 = 𝑦𝑘 𝒙 that
the observation 𝒙 belongs to the class 𝑦 = 𝑘 by means of Bayes’ thorem.
𝑁𝑘
The probability of class k is : 𝑃 𝑦 = 𝑦𝑘 =
𝑁
The posterior probability is computed by bayes theorem:
𝐿𝑖𝑘𝑒𝑙𝑖ℎ𝑜𝑜𝑑 ∗ 𝑃𝑟𝑖𝑜𝑟 𝑃 𝒙 𝑦 = 𝑦𝑘 𝑃 𝑦 = 𝑦𝑘
𝑃𝑜𝑠𝑡𝑒𝑟𝑖𝑜𝑟 = , 𝑃 𝑦 = 𝑦𝑘 𝒙 =
𝐸𝑣𝑖𝑑𝑒𝑛𝑐𝑒 𝑃(𝑥)
The observation 𝒙 is assigned to the class 𝑦 = 𝑦𝑘 if:
𝑃 𝒙 𝑦 = 𝑦𝑘 𝑃 𝑦 = 𝑦𝑘 > 𝑃 𝒙 𝑦 = 𝑦𝑖 𝑃 𝑦 = 𝑦𝑖 , i = 1,2, … , K, i ≠ 𝑘
Bayesian Classifiers
Naive Bayes (or why Bayesian classifiers need a semplification)
𝑃 𝒙 𝑦 = 𝑦𝑘 with k=2 and n binary attributes: we need to compute 2 ∗ (2𝑛 − 1) parameters, where
2 ∗ (2𝑛 − 1) is the number of values than 𝒙 can assume.
If n = 30 ~3 ∗ 106 parameters. To be reliable, we need around 3 ∗ 107 observations!
If the attributes are not binary, this number grows fast.
«Naive» semplification: attributes are conditionally independent:
𝑛
𝑃 𝒙 𝑦 = 𝑦𝑘 = 𝑃 𝒙𝟏 𝑦 = 𝑦𝑘 × 𝑃 𝒙𝟐 𝑦 = 𝑦𝑘 × ⋯ × 𝑃 𝒙𝒏 𝑦 = 𝑦𝑘 = ෑ× 𝑃 𝒙𝒊 𝑦 = 𝑦𝑘
𝑖=1
For discrete attributes, 𝑃 𝒙𝒊 𝑦 = 𝑦𝑘 is the ratio between the number of times that 𝑥𝑖 assumes
some value when 𝑦 = 𝑦𝑘 and the number of observation belonging to the class 𝑦𝑘
For numerical attributes, 𝑃 𝒙𝒊 𝑦 = 𝑦𝑘 can be estimates assuming that the examples follows a
given distribution.
Bayesian Classifiers
1. Very efficient algorithm
2. Easy to interpret. We have the posterior probability of each conditional feature
3. Have shown good performance on text data
1. They assume conditional independence between decision variables
2. Low prediction accuracy
Logistic Regression
Logistic (sigmoid) function: discriminate between two classed
𝟏
𝒇 𝒙 =
𝟏 + 𝒆−𝒙
Linear regression: values of 𝜎 𝐴𝑥 + 𝐵 are between −∞ and +∞
Logistic regression: values of 𝜎 𝐴𝑥 + 𝐵 are bounded between 0 and 1
Logistic Regression
Is a probabilistic classification models which computes the posterior probability 𝑃 𝑦 = 𝑦𝑘 𝒙 as the
sigmoid function 𝜎(𝒙):
′𝑥
1 𝑒𝑤
𝑃 𝑦=0𝒙 = ′𝑥 𝑃 𝑦=1𝒙 = ′𝑥
1 + 𝑒𝑤 1 + 𝑒𝑤
𝑃 𝑦=1𝒙 ′
Odds: = 𝑒 𝑤 𝑥 ⇒ log 𝑂𝑑𝑑𝑠 = 𝑤 ′ 𝑥 = 𝑧
𝑃 𝑦=0𝒙
It is a type of regression where the target variable is categorical
Parameters are learnt via max log likelihood estimation
Logistic Regression
1. Easy to interpret (provides probabilities for outcomes)
2. Low variance
3. Works well with diagonal features
1. Tends to have high biases
2. Works only with binary target classes
Support Vector Machines (SVM)
SVMs are a separation model driven by a linear function.
Intuition: We can have multiple hyperplanes 𝑤 ′ 𝑥 = 𝑏 separating the same classes (e.g. 𝐻2 , 𝐻3 )
Support Vector Machines (SVM)
We select the hyperplane which maximises the distance with the closest elements of each class.
1 2
min 𝒘
𝒘,𝑏 2
𝑠. 𝑡. 𝑦𝑖 𝒘′ 𝒙𝑖 − 𝑏 ≥ 1, 𝑖 ∈ 𝑁
If it is not linearly separable:
1
min 𝒘 2
+ 𝜆 σ𝑛𝑖=1 𝑑𝑖
𝒘,𝑏 2 Support
vectors
𝑠. 𝑡. 𝑦𝑖 𝒘′ 𝒙𝑖 − 𝑏 ≥ 1 − 𝑑𝑖 , 𝑖 ∈ 𝑁
𝑑𝑖 ≥ 0, 𝑖 ∈ 𝑁
Where 𝑑𝑖 is the distance of observation 𝑖
from the separating hyperplane
Support Vector Machines (SVM)
What about nonlinear separations? The Kernel trick
Support Vector Machines
1. Very robust
2. High accuracy
3. Performs well with non-linear boundary depending on the kernel used
4. Handle well high dimensional data
1. Tends to be computationally expansive to train
2. Susceptible to overfitting (depending on kernel)
Random forest
A Random Forest is an ensemble of multiple
decision trees.
The key idea is bagging (Bootstrap Aggregating).
Bagging works as follows:
• From the training dataset we generate many
bootstrap samples
(random samples of the data, with
replacement).
• For each sample we train a decision tree.
• Each tree makes its own prediction.
• The final prediction is obtained by
aggregating the trees' predictions
(usually by majority vote in classification).
Random forest
1. Usually more accurate than a single decision tree
2. Reduces overfitting thanks to bagging
3. Robust to noise and outliers
4. Works well with large datasets and many features
1. Less interpretable than a single decision tree
2. Can be computationally expensive with many trees
3. Larger models require more memory
Xgboost
XGBoost is based on the idea of boosting.
Unlike Random Forest, the trees are built
sequentially, not independently.
Each new tree tries to correct the errors made by
the previous ones.
Boosting works as follows:
• The first tree makes an initial prediction.
• We look at the errors made by the model.
• A new tree is trained to focus on those errors.
• This process continues, gradually improving
the model.
Xgboost
1. Often achieves very high predictive accuracy
2. Handles complex non-linear relationships well
3. Includes regularization, reducing overfitting
4. Efficient and scalable for large datasets
1. More complex to tune (many hyperparameters)
2. Training can be computationally expensive
3. Less interpretable than simple models like decision trees