Solving Classification Problems in Machine Learning
Classification problems in machine learning are problems in which one wants to classify a discrete random variable based on input data.
For those problems, we aim to find a predictor that produces discrete values.
e.g.: classifying images of dogs and cats, labeling emails as spam or not, etc.
In order to choose the best predictor, we would want to evaluate each predictor’s performance. The most suitable criterion for this type of problems is the “misclassification rate” risk function.
The meaning behind this risk function is the probability for the predictor to make a mistake. This means a lower result equals a better predictor.
We will now look at a couple of methods for solving classification problems.
K-NN (K-Nearest Neighbors)
In this common algorithm, the prediction is made directly based on the given dataset.
When looking at a dataset sample x which we want to classify, we will choose K samples from our dataset that are the closest to x (usually will be done using Euclidean distance).
Next, we will look at the classes of the chosen samples and classify x as the most common class.
Decision Trees
Decision trees are another popular algorithm that can be used in classification problems.
Decision trees are used for building predictors. Each node in the tree contains a question that is defined for a specific parameter in the given dataset. Every branch coming out of a tree node represents a possible outcome for the question.
The idea behind using this data structure is splitting the data into subsets, which allows us to make our prediction based on data that shares the same characteristics as the sample we try to classify.
To make the tree construction process more efficient we want to choose our questions wisely. Our aim in each step is to choose a question based on the most homogeneously distributed parameter in our dataset. This way a clear distinction will be created between the sub-trees.
The homogeneity/heterogeneity is commonly measured via misclassification rate, Gini index, or entropy.
Get Polina Pukh’s stories in your inbox
Join Medium for free to get updates from this writer.
Misclassification rate:
The Gini index:
Entropy:
We will use these criteria to evaluate the total score of the tree split.
The amount of data samples in leaf j will be marked as Nj.
While N is the total amount of samples in the dataset.
The total score resulting from a specific split will be:
We would want to choose the split parameter that results in the lowest total score.
After completing the construction of the tree, we will begin pruning it to avoid overfitting the training data.
In the pruning process, we will look for nodes that can be removed without damaging the predictive power of the tree.
This process is performed using the validation set.
Let’s look at an example:
Given the next dataset, we would like to predict whether or not a person will get sunburned or not.
We will build a decision tree using the entropy criterion.
Step 1: We will start by choosing the best parameter for the tree root.
There are 4 options: hair color, height, weight, and whether or not a lotion has been applied or not.
The total scores of the tree when choosing the next parameters are:
- Hair: 0.5
- Height: 0.69
- Weight: 0.94
- Lotion: 0.6
Therefore we will choose the first split to be made according to the hair parameter.
We will continue building the tree in the same way using the remaining unused parameters until we meet the stopping condition.
In our case - the total tree score of 0.
The final tree will be:
In summary, there are various methods for solving classification problems in machine learning. Here, we have explored two of the most popular approaches.
