Data Science Part 13: Classification

 

A sample binary classification problem is to try to predict the class. For this, we will use training samples in 3-Dimensional Space. For the test data, we want to see if the data yields blue or red. 

One of the algorithms used in this is the K Nearest Neighbors Algorithm. For each test point, find the K Nearest Neighbors among the training samples. Classes of K Nearest Neighbors are known. We will classify using the majority vote, or which class the K Nearest Neighbors is part of. 

If we have a large K set, it can be very stable which can find the large areas easily but very noisy as it may fail to find small patches of other color/classes within the graph. Smaller K results in less stability with smaller areas of a color in each output, but we can classify a lot more precisely. The moderate K offers the best stability/bias tradeoff. Bias is the the disparity between the values that were predicted and the values that were actually observed. 

The optimal value of K depends on the amount of randomness; where we get a greater K for confident majority vote, the size of N, where large N greatly increases computation to find the nearest neighbors, and high dimensional data; which affects "neighborliness" and increases the complexity of the data and thus computation. 

We can also select a "good" K with validation approach. We can partition into training and test data. After this we validate quality on test data after training w/different K, and select the K that gets the most accurate results. 

Let's do an example of the K-nearest neighbors approach.

 Here 4 <= K < 7, because you can clearly classify the classes as "+" or "-" and the training error will be 4/14 = 0.28 which are the outliers on either side. Small values such as k = 1 can give zero error; however, it can also overfit. The nearest neighbor boundary is sketched above. 

Here is the nearest neighbor classification. not that a lot of the points are midpoints between a red point and its corresponding nearest neighbor if it's a blue point and we draw lines to reflect that. We can also have a weighted K Nearest Neighbors, where we basically assign a greater weight to a closer point and see if the weights sum up to > 0.5. An example of the weights could be (0.2 0.15 0.1)... etc. 

The pseudocode of K Nearest Neighbors is as follows: 

1. Load the training and test data 

2. Choose the value of K 

3. For each point in test data:

       - find the Euclidean distance to all training data points

       - store the Euclidean distances in a list and sort it 

       - choose the first k points 

       - assign a class to the test point based on the majority of      classes present in the chosen points

4. End 

It's basically comparing the test data with the training data. 

Another method of classification is the linear model. It is used because of its simplicity, effectiveness, and the fact that many systems are well approximated as linear. It is given as the following equation: 

Here's the method to compute coefficients: 

We have a vector since it's across many dimensions. Linear classifications can be very stable and resistant to crazy variance, but it has a terrible bias especially if an exponential curve fits the data better.