Lesson 4.3 - K-Nearest Neighbors Classification
Robbie Beane
K-Nearest Neighbors Classification
The K-Nearest Neighbors Classification algorithm classifies observations by allowing the K observations in the training set that are nearest to the new observation to “vote” on the class of the new observation. More specifically, the algorithm works as follows:
- Calculate the distance between the new observation and EACH obsevation in the training set. Distances are calculated within the feature space.
- Select the
K observations in the training set that are nearest to the new observation.
- Determine the majority class within the
K nearest neighbors.
- Classify the new observation as this majority class.
- If there is a tie in the vote, resolve this according to some pre-determine scheme.
We will demonstrate this classification algorithm through examples.
Load Packages
We will use ggplot2 and gridExtra for plotting. The carat packages will be used for splitting our data and for feature scaling. The functionality for performing KNN classification is provided by the class package.
Example 1: Iris Dataset
For this example, we will be working with the Iris Dataset. This data set is a real-world “toy” dataset that is often used to demonstrate concepts in data science. The iris dataset contains information about several flowers selected from three different species of iris: versicolor, setosa, and virginica.
The dataset contains the following five pieces of information for 150 flowers:
- The sepal length of the flower.
- The sepal width of the flower.
- The petal length of the flower.
- The petal width of the flower.
- The species of the flower.
Load and Explore the Data
## sepal_length sepal_width petal_length petal_width
## Min. :4.300 Min. :2.000 Min. :1.000 Min. :0.100
## 1st Qu.:5.100 1st Qu.:2.800 1st Qu.:1.600 1st Qu.:0.300
## Median :5.800 Median :3.000 Median :4.350 Median :1.300
## Mean :5.843 Mean :3.057 Mean :3.758 Mean :1.199
## 3rd Qu.:6.400 3rd Qu.:3.300 3rd Qu.:5.100 3rd Qu.:1.800
## Max. :7.900 Max. :4.400 Max. :6.900 Max. :2.500
## species
## setosa :50
## versicolor:50
## virginica :50
##
##
##
Build a 3-Nearest Neighbors Model
We will now use the knn function from the class package to create a 3-Nearest Neighbors model for the iris dataset.
## [1] setosa versicolor virginica setosa versicolor versicolor
## [7] versicolor virginica versicolor setosa
## Levels: setosa versicolor virginica
Let’s calculate the model’s training accuracy.
## Training Accuracy: 0.96
Effects of Changing K
The selection of K=3 in the previous model was somewhat arbitrary. In the figure below, we will plot the KNN model’s training accuracy for several values of K.
train_acc <- c()
for (i in 1:150){
set.seed(1)
train_pred <- knn(iris_tr_feat, iris_tr_feat, iris_tr$species, k=i)
train_acc <- c(train_acc, mean(train_pred == iris_tr$species))
}
plot(1:150, train_acc, pch='.', ylim=c(0.3, 1), col='salmon')
lines(1:150, train_acc, lwd=2, col='salmon')
Validation Set
KNN model’s will (almost) always get 100% accuracy on the training set when K=1. For this reason, it is not helpful to use training performance to select the best value of K for our dataset. To select the value of K for which the model is most likely to generalize well, we need to create a validation set.
## sepal_length sepal_width petal_length petal_width
## Min. :4.600 Min. :2.100 Min. :1.30 Min. :0.200
## 1st Qu.:5.200 1st Qu.:2.825 1st Qu.:1.55 1st Qu.:0.400
## Median :5.900 Median :3.000 Median :4.30 Median :1.400
## Mean :5.883 Mean :3.033 Mean :3.73 Mean :1.193
## 3rd Qu.:6.375 3rd Qu.:3.200 3rd Qu.:4.80 3rd Qu.:1.800
## Max. :7.800 Max. :3.900 Max. :6.70 Max. :2.300
## species
## setosa :10
## versicolor:10
## virginica :10
##
##
##
Selecting K
We will now calculate validation accuracy for each of our models, and will use this information to select our final model.
train_acc <- c()
valid_acc <- c()
iris_va_feat <- iris_va[,1:4]
for (i in 1:100){
set.seed(1)
train_pred <- knn(iris_tr_feat, iris_tr_feat, iris_tr$species, k=i)
train_acc <- c(train_acc, mean(train_pred == iris_tr$species))
set.seed(1)
valid_pred <- knn(iris_tr_feat, iris_va_feat, iris_tr$species, k=i)
valid_acc <- c(valid_acc, mean(valid_pred == iris_va$species))
}
plot(1:100, train_acc, pch='.', ylim=c(0.8, 1), col='salmon')
lines(1:100, train_acc, lwd=2, col='salmon')
lines(1:100, valid_acc, lwd=2, col='cornflowerblue')
legend(38, 1, legend=c("Training Acc", "Validation Acc"),
col=c("salmon", "cornflowerblue"), lty=1, lwd=2, cex=0.8)
Selecting K
The largest validation accuracy obtained by any model was 93.33%.
## [1] 0.9666667
The maximum validation accuracy was obtained by the K=11 model.
## [1] 2
Example 2: Pima Diabetes Dataset
For this example, we will be working with the Pima Diabetes Dataset. This dataset is originally from the National Institute of Diabetes and Digestive and Kidney Diseases. The objective is to predict based on diagnostic measurements whether a patient has diabetes. All patients are females at least 21 years old of Pima Indian heritage.
The columns in this dataset are described below.
- Pregnancies: Number of times pregnant
- Glucose: Plasma glucose concentration a 2 hours in an oral glucose tolerance test
- BloodPressure: Diastolic blood pressure (mm Hg)
- SkinThickness: Triceps skin fold thickness (mm)
- Insulin: 2-Hour serum insulin (mu U/ml)
- BMI: Body mass index (weight in kg/(height in m)^2)
- DiabetesPedigreeFunction: Diabetes pedigree function
- Age: Age (years)
- Outcome: Class variable (0 or 1)
Load the Data
## Pregnancies Glucose BloodPressure SkinThickness
## Min. : 0.000 Min. : 0.0 Min. : 0.00 Min. : 0.00
## 1st Qu.: 1.000 1st Qu.: 99.0 1st Qu.: 62.00 1st Qu.: 0.00
## Median : 3.000 Median :117.0 Median : 72.00 Median :23.00
## Mean : 3.845 Mean :120.9 Mean : 69.11 Mean :20.54
## 3rd Qu.: 6.000 3rd Qu.:140.2 3rd Qu.: 80.00 3rd Qu.:32.00
## Max. :17.000 Max. :199.0 Max. :122.00 Max. :99.00
## Insulin BMI DiabetesPedigreeFunction Age
## Min. : 0.0 Min. : 0.00 Min. :0.0780 Min. :21.00
## 1st Qu.: 0.0 1st Qu.:27.30 1st Qu.:0.2437 1st Qu.:24.00
## Median : 30.5 Median :32.00 Median :0.3725 Median :29.00
## Mean : 79.8 Mean :31.99 Mean :0.4719 Mean :33.24
## 3rd Qu.:127.2 3rd Qu.:36.60 3rd Qu.:0.6262 3rd Qu.:41.00
## Max. :846.0 Max. :67.10 Max. :2.4200 Max. :81.00
## Outcome
## 0:500
## 1:268
##
##
##
##
Split the Data
We will use createDataPartition to create a stratified partition of our data into training and validation sets.
## 0 1
## 350 188
## 0 1
## 150 80
3-Nearest Neighbors
For practice, we will create and evaluate a 3-Nearest Neighbors model.
train_feat <- train[,1:8]
valid_feat <- valid[,1:8]
set.seed(1)
train_pred <- knn(train_feat, train_feat, train$Outcome, k=3)
train_acc <- mean(train_pred == train$Outcome)
set.seed(1)
valid_pred <- knn(train_feat, valid_feat, train$Outcome, k=3)
valid_acc <- mean(valid_pred == valid$Outcome)
cat('Training Accuracy: ', train_acc, '\n',
'Validation Accuracy: ', valid_acc, sep='')
## Training Accuracy: 0.8513011
## Validation Accuracy: 0.7130435
Feature Scaling
For many machine learning algorithms, it is important to make sure that the features are on roughly the same scale before training. This is especially true of distance-based algorithms such as K-Nearest Neighbors.
We will consider two types of scaling in this course: Standardization and Min/Max Scaling.
Standardization
With standardization, each column in the training set is scaled to have a mean of zero and a standard deviation of 1. If \(x_i\) is a single observation of a particular feature, then its scaled value \(z_i\) is given by:
\[ z_i = \frac{x_i - \bar x}{s_x}\] Note that the values \(\bar x\) and \(s_x\) are calculated from the training set only, but are used to scale any observation, whether it is from the training set, validation set, testing set, or an entirely new observation.
Min/Max Scaling
With min max scaling, each column in the training set is scaled linearly to have a minimum of zero and a maximum of 1. If \(x_i\) is a single observation of a particular feature, then its scaled value \(w_i\) is given by:
\[ w_i = \frac{x_i - \textrm{min}_x}{\textrm{max}_x - \textrm{min}_x}\] Note that the values \(\textrm{min}_x\) and \(\textrm{max}_x\) are calculated from the training set only, but are used to scale any observation, whether it is from the training set, validation set, testing set, or an entirely new observation.
3-Nearest Neighbors on Scaled Data
We will now create our 3-Nearest Neighbors model on the scaled data for the sake of comparison. We will start with the standardized data.
set.seed(1)
train_pred <- knn(train_s_sc, train_s_sc, train$Outcome, k=3)
train_acc <- mean(train_pred == train$Outcome)
set.seed(1)
valid_pred <- knn(train_s_sc, valid_s_sc, train$Outcome, k=3)
valid_acc <- mean(valid_pred == valid$Outcome)
cat('Training Accuracy: ', train_acc, '\n',
'Validation Accuracy: ', valid_acc, sep='')
## Training Accuracy: 0.8531599
## Validation Accuracy: 0.6956522
We will now consider the 3-nearest neighbors algorithm on the min-max scaled data.
set.seed(1)
train_pred <- knn(train_mm_sc, train_mm_sc, train$Outcome, k=3)
train_acc <- mean(train_pred == train$Outcome)
set.seed(1)
valid_pred <- knn(train_mm_sc, valid_mm_sc, train$Outcome, k=3)
valid_acc <- mean(valid_pred == valid$Outcome)
cat('Training Accuracy: ', train_acc, '\n',
'Validation Accuracy: ', valid_acc, sep='')
## Training Accuracy: 0.8494424
## Validation Accuracy: 0.726087
Selecting K
We will now build several KNN models. For each K from 1 to 100, we will calculate training and validation accuracy for the KNN model, using both the scaled and the unscaled data.
set.seed(1)
train_acc <- c()
valid_acc <- c()
train_acc_s_sc <- c()
valid_acc_s_sc <- c()
train_acc_mm_sc <- c()
valid_acc_mm_sc <- c()
k_range <- 1:100
for (i in k_range){
# Unscaled
set.seed(1)
train_pred <- knn(train_feat, train_feat, train$Outcome, k=i)
train_acc <- c(train_acc, mean(train_pred == train$Outcome))
set.seed(1)
valid_pred <- knn(train_feat, valid_feat, train$Outcome, k=i)
valid_acc <- c(valid_acc, mean(valid_pred == valid$Outcome))
# Standard Scaling
set.seed(1)
train_pred <- knn(train_s_sc, train_s_sc, train$Outcome, k=i)
train_acc_s_sc <- c(train_acc_s_sc, mean(train_pred == train$Outcome))
set.seed(1)
valid_pred <- knn(train_s_sc, valid_s_sc, train$Outcome, k=i)
valid_acc_s_sc <- c(valid_acc_s_sc, mean(valid_pred == valid$Outcome))
# MinMax Scaling
set.seed(1)
train_pred <- knn(train_mm_sc, train_mm_sc, train$Outcome, k=i)
train_acc_mm_sc <- c(train_acc_mm_sc, mean(train_pred == train$Outcome))
set.seed(1)
valid_pred <- knn(train_mm_sc, valid_mm_sc, train$Outcome, k=i)
valid_acc_mm_sc <- c(valid_acc_mm_sc, mean(valid_pred == valid$Outcome))
}
max(valid_acc)
## [1] 0.7869565
## [1] 0.773913
## [1] 0.7608696
Training and Validation Curves for Unscaled Data
plot(k_range, train_acc, pch='.', ylim=c(0.65, 1), col='salmon')
lines(k_range, train_acc, lwd=2, col='salmon')
lines(k_range, valid_acc, lwd=2, col='cornflowerblue')
legend(75, 1, legend=c("Training Acc", "Validation Acc"),
col=c("salmon", "cornflowerblue"), lty=1, lwd=2, cex=0.8)
Training and Validation Curves for Standard Scaled Data
plot(k_range, train_acc_s_sc, pch='.', ylim=c(0.65, 1), col='salmon')
lines(k_range, train_acc_s_sc, lwd=2, col='salmon')
lines(k_range, valid_acc_s_sc, lwd=2, col='cornflowerblue')
legend(75, 1, legend=c("Training Acc", "Validation Acc"),
col=c("salmon", "cornflowerblue"), lty=1, lwd=2, cex=0.8)
Training and Validation Curves for Min-Max Scaled Data
plot(k_range, train_acc_mm_sc, pch='.', ylim=c(0.65, 1), col='salmon')
lines(k_range, train_acc_mm_sc, lwd=2, col='salmon')
lines(k_range, valid_acc_mm_sc, lwd=2, col='cornflowerblue')
legend(75, 1, legend=c("Training Acc", "Validation Acc"),
col=c("salmon", "cornflowerblue"), lty=1, lwd=2, cex=0.8)
Selecting the Final Model
Our best validation performance was obtained using unscaled data. Let’s determine the value of K used to create this particular model.
## [1] 11
We will now recalculate the training and validation accuracies for this model.
set.seed(1)
train_pred <- knn(train, train, train$Outcome, k=11)
train_acc <- mean(train_pred == train$Outcome)
set.seed(1)
valid_pred <- knn(train, valid, train$Outcome, k=11)
valid_acc <- mean(valid_pred == valid$Outcome)
cat('Training Accuracy: ', train_acc, '\n',
'Validation Accuracy: ', valid_acc, sep='')
## Training Accuracy: 0.7788104
## Validation Accuracy: 0.7869565
We can use the table function to create a quick confusion matrix.
## valid_pred
## 0 1
## 0 134 16
## 1 33 47
Evaluating the Final Model
We will use the confusion matrix to view several classification metrics for our final model.
## Confusion Matrix and Statistics
##
## Reference
## Prediction 0 1
## 0 134 33
## 1 16 47
##
## Accuracy : 0.787
## 95% CI : (0.7283, 0.838)
## No Information Rate : 0.6522
## P-Value [Acc > NIR] : 5.84e-06
##
## Kappa : 0.5059
##
## Mcnemar's Test P-Value : 0.02227
##
## Sensitivity : 0.8933
## Specificity : 0.5875
## Pos Pred Value : 0.8024
## Neg Pred Value : 0.7460
## Prevalence : 0.6522
## Detection Rate : 0.5826
## Detection Prevalence : 0.7261
## Balanced Accuracy : 0.7404
##
## 'Positive' Class : 0
##
Weighting Predictors
If we believe that a certain feature will be more or less important than other features in our model, then we can apply a weight to its scaled values in order to have it emphasized more highly when calculating distances.
set.seed(1)
train_acc_w <- c()
valid_acc_w <- c()
w <- c(1, 1, 0, 0, 0, 1, 1, 2)
train_w <- t(t(train_s_sc)*w)
valid_w <- t(t(valid_s_sc)*w)
k_range <- 1:100
for (i in k_range){
# Scaled
set.seed(1)
train_pred <- knn(train_w, train_w, train$Outcome, k=i)
train_acc_w <- c(train_acc_w, mean(train_pred == train$Outcome))
set.seed(1)
valid_pred <- knn(train_w, valid_w, train$Outcome, k=i)
valid_acc_w <- c(valid_acc_w, mean(valid_pred == valid$Outcome))
}
max(valid_acc_w)
## [1] 0.7913043
Weighting Predictors
plot(k_range, train_acc_w, pch='.', ylim=c(0.65, 1), col='salmon')
lines(k_range, train_acc_w, lwd=2, col='salmon')
lines(k_range, valid_acc_w, lwd=2, col='cornflowerblue')
legend(75, 1, legend=c("Training Acc", "Validation Acc"),
col=c("salmon", "cornflowerblue"), lty=1, lwd=2, cex=0.8)
## [1] 0.7913043
## [1] 24
Pros and Cons of KNN
Pros
- Easy to understand.
- Flexible (Although, one must be careful about overfitting.)
- No time required to train.
- Naturally adapts to multi-class classification.
Cons
- Making predictions is computationally intensive, and can be slow on a large dataset.
- Requires a meaningful notion of distance in the feature space.
- Generally requires features to be scaled/normalized.
- Model performance can be diminished when there are many dimensions. (Curse of dimensionality)