Classification Algorithms II: K-Nearest Neighbors and Cross Validation

This set of vocabulary flashcards covers the fundamental concepts of the K-Nearest Neighbors (K-NN) algorithm, its characteristics, advantages, drawbacks, and the process of cross-validation as described in the lecture notes.

K-Nearest Neighbors (K-NN)

One of the most basic and easy-to-implement supervised machine learning algorithms used for both classification and regression problems, primarily in pattern recognition and data mining.

Decision Surface

The boundary between two classes in a feature space graph.

Majority Vote

The process where the K-NN algorithm checks the class labels of the $K$ nearest points and decides the predicted class label based on which class is most frequent.

K (in K-NN)

The number of points that the K-NN algorithm checks before doing a majority vote; its value is not fixed and must be optimized for each dataset.

Lazy Learning

A principle where an algorithm does not have a specific training phase and instead uses all the training data while performing a classification operation.

Non-parametric Learning

An algorithm that does not assume anything about the distribution of the data and therefore does not find parameters for the data distribution.

Hyperparameter

In the context of K-NN, this refers to $K$, which is provided by the user to the model.

Imbalanced Data

A dataset where the majority of training data is labeled as one class, leading K-NN to be biased and potentially misclassify objects from the minority class.

Curse of Dimensionality

A phenomenon where the K-NN algorithm struggles to predict the output of a new data point as the number of input variables grows.

Cross Validation

A technique in which a particular portion of a dataset is reserved to test the resulting model after training is over but before finalizing it.

Validation Data

A small portion of the dataset reserved for testing the model to check its accuracy during the cross-validation process.

k-fold cross-validation

A technique where data is split into $k$ different but similar folds, performing $k$ iterations where one fold is used as the validation set and the rest as training sets.

Thumb rule for k in Cross-Validation

When unsure which value to choose for the iterations in cross-validation, a value of $k=10$ is commonly used in applied machine learning.

Optimal K accuracy range

In most cases, K-NN accuracy is highest for $K=7$ to $K=13$ and falls as the value of $K$ increases.