# basic imports
import numpy as np
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
# machine learning imports
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_blobs
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_scoreClassification Introduction
Like Regression, But Different
Coming soon!
TODO
In these notes, we will discuss:
- the supervised learning classification task,
- the Bayes classifier,
- \(k\)-nearest neighbors,
- classification metrics,
- and estimating conditional probabilities with a learned model.
Along the way, you should notice that except for the conditional probabilities, the process followed mirrors that of regression.
The Goal of Classification
Like, regression, classification is a supervised learning task. However, while regression is concerned with predicting a numeric target variable, classification seeks to predicts a categorical target variable.
sns.scatterplot(
x=X_train[:, 0],
y=X_train[:, 1],
hue=y_train,
edgecolor="k",
alpha=0.75,
)
plt.show()
Show Code for Plot
Consider new data at \(x = (x_1, x_2)\). The goal of classification is to predict the class label \(y\) for this new data point. Consider the following example when \(x = (-5, 5)\).
Show Code for Plot
fig, ax = plt.subplots()
fig.set_size_inches(8, 6)
scatter = sns.scatterplot(
x=X_train[:, 0],
y=X_train[:, 1],
hue=y_train,
palette="tab10",
ax=ax,
s=50,
alpha=0.75,
)
ax.set_xlabel("$x_1$")
ax.set_ylabel("$x_2$")
ax.set_title("Simulated Training Data for Classification")
ax.plot(
-5,
5,
marker="o",
markersize=10,
color="red",
)
plt.show()
The fundamental question that classification seeks to answer is: what is the probability that \(Y = g\) given \(X = x\)?
So, in this case, what is the probability that:
- \(Y = 0\) (blue) when \(x = (-5, 5)\)?
- \(Y = 1\) (orange) when \(x = (-5, 5)\)?
- \(Y = 2\) (green) when \(x = (-5, 5)\)?
With these questions answered, we can then make a prediction for the class label of \(x = (-5, 5)\). Simply predict the class label with the highest probability!
Unfortunately, we do not know the true conditional probabilities. So instead, we will fit a model that can be used to estimate these probabilities.
Bayes Classifier
The Bayes Classifier, \(C^B(x)\), is the classifier that minimizes the probability of misclassification, and thus is considered the optimal classifier. However, the Bayes Classifier cannot be used in practice as it requires knowledge of the true conditional probabilities. It is simply a useful concept for theoretical understanding of classification.
\[ p_g(x) = P\left[ Y = g \mid X = x \right] \]
\[ C^B(x) = \underset{g \in \{1, 2, \ldots G\}}{\text{argmax}} P\left[ Y = k \mid X = x \right] \]
The Bayes Classifier simply says “predict the class label with the highest conditional probability”.
Be aware that the Bayes Classifier is unrelated to the Naive Bayes Classifier that we will explore later.
Building a Classifier
Given that we cannot use the Bayes Classifier in practice, we will build a model that can be used to estimate the relevant conditional probabilities. With those estimate probabilities, we would then make predictions using the same rule as the Bayes Classifier, but with the estimated probabilities rather than known conditional probabilities.
\[ \hat{p}_g(x) = \hat{P}\left[ Y = k \mid X = x \right] \]
\[ \hat{C}(x) = \underset{g \in \{1, 2, \ldots G\}}{\text{argmax}} \hat{p}_g(x) \]
\(k\)-Nearest Neighbors
Our first model for classification will be the \(k\)-nearest neighbors classifier. Using \(k\)-nearest neighbors for classification is quite similar to \(k\)-nearest neighbors for regression.
After finding the \(k\)-nearest neighbors of \(x\), we will predict the class label of \(x\) as the class label that is most common among the \(k\)-nearest neighbors. More specifically, we can utilize the \(k\)-nearest neighbors to estimate the conditional probabilities. We will simply count the number of neighbors of each class label and divide by \(k\) to get the estimated probabilities!
\[ \hat{p}_g(x) = \hat{P}\left[ Y = k \mid X = x \right] = \frac{1}{k} \sum_{i \in \mathcal{N}_k(x)} I(y_i = g) \]
After estimating the conditional probabilities, we can then make a prediction for the class label of \(x\) that has the highest estimated conditional probability.
\[ \hat{C}(x) = \underset{g \in \{1, 2, \ldots G\}}{\text{argmax}} \hat{p}_g(x) \]
Like \(k\)-nearest neighbors regression, \(k\)-nearest neighbors for classification requires selecting a value for \(k\).
Metrics
There are many metrics to evaluate the performance of a classifier. We will detail a long list of them in the future. For introductory purposes, we will focus on two metrics: accuracy and misclassification.
\[ \text{Accuracy}(y, \hat{y}) = \frac{1}{n} \sum_{i=1}^{n} I(y_i = \hat{y}_i) \]
The accuracy is simply the proportion of correct predictions made by the classifier. We will see that accuracy is in many ways the default metric for classification, especially within sklearn.
Note that until RMSE for regression, which we want to minimize, accuracy is metric that we want to maximize. The classification error, or misclassification rate, is simply the proportion of incorrect predictions made by the classifier. So while these two metrics are related, and essentially measure the same thing, it can sometimes be useful to considered errors instead of correct predictions.
\[ \text{Misclassification}(y, \hat{y}) = \frac{1}{n} \sum_{i=1}^{n} I(y_i \neq \hat{y}_i) \]
\[ I(y_i = \hat{y}_i) = \begin{cases} 1 & \text{if } y_i = \hat{y}_i \\ 0 & \text{otherwise} \end{cases} \]
Example: Tuning a \(k\)-Nearest Neighbors Classifier
k_values = range(1, 501, 10)
train_accuracies = []
validation_accuracies = []
for k in k_values:
knn = KNeighborsClassifier(n_neighbors=k)
knn.fit(X_vtrain, y_vtrain)
y_pred_train = knn.predict(X_vtrain)
y_pred_validation = knn.predict(X_validation)
train_accuracy = accuracy_score(y_vtrain, y_pred_train)
validation_accuracy = accuracy_score(y_validation, y_pred_validation)
train_accuracies.append(train_accuracy)
validation_accuracies.append(validation_accuracy)
best_k = k_values[np.argmax(validation_accuracies)]
print(f"Best k: {best_k}")
print(f"Validation Accuracy: {max(validation_accuracies):.2f}")Best k: 361
Validation Accuracy: 0.86fig, ax = plt.subplots()
fig.set_size_inches(8, 6)
ax.plot(
k_values,
train_error,
label="Train Error",
# color="black",
marker="o",
# markeredgecolor="black",
# markerfacecolor="tab:blue",
)
ax.plot(
k_values,
validation_error,
label="Validation Error",
# color="black",
marker="o",
# markeredgecolor="black",
# markerfacecolor="tab:orange",
)
ax.set_xlabel("k (Number of Neighbors)")
ax.set_ylabel("Error")
ax.set_title("Train and Validation Error versus k")
ax.invert_xaxis()
ax.legend()
plt.show()
1 0.37
0 0.32
2 0.31
Name: proportion, dtype: float64knn = KNeighborsClassifier(n_neighbors=best_k)
knn.fit(X_train, y_train)
y_pred_test = knn.predict(X_test)
test_accuracy = accuracy_score(y_test, y_pred_test)
print(f"Test Accuracy: {test_accuracy:.2f}")Test Accuracy: 0.88[[0.5319 0.3934 0.0748]
[0.2244 0.5651 0.2105]
[0.2216 0.5762 0.2022]
[0.205 0.2133 0.5817]
[0.5568 0.338 0.1053]
[0.5762 0.3906 0.0332]
[0.5319 0.2022 0.2659]
[0.2742 0.1468 0.5789]
[0.1274 0.4404 0.4321]
[0.5817 0.3241 0.0942]]results_df = pd.DataFrame(
{
"Actual": y_test[:10],
"Predicted": y_pred_test[:10],
}
)
prob_df = pd.DataFrame(knn.predict_proba(X_test)[:10])
prob_df.columns = [f"prob_{i}" for i in knn.classes_]
results_df = pd.concat([results_df, prob_df], axis=1)
print(results_df) Actual Predicted prob_0 prob_1 prob_2
0 1 0 0.53 0.39 0.07
1 1 1 0.22 0.57 0.21
2 1 1 0.22 0.58 0.20
3 2 2 0.20 0.21 0.58
4 0 0 0.56 0.34 0.11
5 0 0 0.58 0.39 0.03
6 0 0 0.53 0.20 0.27
7 2 2 0.27 0.15 0.58
8 1 1 0.13 0.44 0.43
9 0 0 0.58 0.32 0.09TODO
- TODO: compare to dummy classifier