- LPU MCA Semester 1
- CAB107
- Unit 4
CAB107 · Unit 4: Machine learning fundamentals
Logistic regression, k-NN, decision trees, random forests and SVM
10 practice questions · in the ETE syllabus
Key points
- Logistic regression outputs a probability via a sigmoid
- k-NN is distance-based and needs scaling
- Gini = 1 minus sum of squared proportions
- Random forests cut variance by averaging trees
Classification algorithms predict a category.
| Algorithm | Idea |
|---|---|
| Logistic regression | Linear score passed through a sigmoid to give a probability |
| k-NN | Majority vote among the k closest training points |
| Decision tree | Sequence of feature splits chosen by impurity |
| Random forest | Many trees on different samples and features, averaged |
| SVM | Hyperplane that maximises the margin between classes |
In k-NN, k is the number of closest training points consulted. With k = 1 it copies the single nearest point; with k equal to the whole training set it always predicts the majority class. It is distance-based, so features must be scaled.
A tree chooses splits that lower Gini impurity, 1 minus the sum of squared class proportions. A node with 3 examples of class A and 1 of class B has 1 - (0.75 squared + 0.25 squared) = 1 - 0.625 = 0.375. The maximum for two classes is 0.5, at a 50-50 split.
A single deep tree overfits. A random forest overfits less because averaging many trees trained on different samples and features reduces variance.
The SVM chooses the maximum-margin hyperplane; kernels let it separate non-linear data.
Exam trap: logistic regression is a classifier despite its name, and Gini impurity is not the proportion of a class.
Try two questions
A parent node has 4 positive and 4 negative examples. A split sends 3 positive and 1 negative to the left and 1 positive and 3 negative to the right. What is the information gain, to two decimals?
- 0.81
- 1.00
- 0.19
- 0.50
Show the answer
C. The parent entropy is 1.00 and the weighted child entropy is 0.81, so the gain is 0.19.
Why not A: 0.81 is the entropy of each child, not the gain.
Why not B: 1.00 is the parent entropy, not the gain.
Why not D: 0.50 is the weight of each child.
Training points are A(1,1) labelled No, B(2,3) labelled Yes, C(4,4) labelled Yes and D(5,1) labelled No. Using Euclidean distance and k = 3, what class is predicted for the query (2,2)?
- Yes
- No
- Tie, so no prediction
- Cannot be decided without scaling
Show the answer
A. The distances are B 1.00, A 1.41, C 2.83 and D 3.16, so the neighbours B, A, C vote Yes, No, Yes.
Why not B: The three nearest are B, A and C, which contain two Yes votes.
Why not C: Three neighbours with two classes cannot tie.
Why not D: Scaling is not required to apply the rule to the given coordinates.