K-Nearest Neighbor

Characteristics

• Lazy learning (the test point is not given)
• Non-parametric algorithm (no assumption)
• Heavy computation, not real-time
• A Low K-value is sensitive to outliers and a higher K-value is more resilient to outliers as it considers more voters to decide prediction
• Higher K-value has higher computational time

Pros

• Easy to understand
• No assumptions about data
• Classification and regression (average of the output value for the top K nearest neighbors)
• Works easily on multi-class problems

Cons

• Memory/Computationally expensive
• Sensitive to scale of data
• Struggle when high number of attributes (do standardization before knn)
• Does not work well with categorical features since it is difficult to find the distance between dimensions with categorical features (use one-hot encoding for hamming distances)

Improve

• Principle-Component Analysis (PCA) to reduce dimension
• KD-tree
• Parallelization for distance computations

Applications

• Hand-written character recognition
• Fast content-based image retrieval
• Intrusion detection
• Fault detection for semiconductor manufacturing processes

Steps

1. Prepare training and test dataset
2. Select K
3. Determine distance function
4. Compute distances to n training samples
5. Sort the distances and find K-nearest data samples
6. Assign to class based on majority vote

Standardization

$$X_{new}=\frac{X-\mu }{\sigma }$$

Distance Measures

Euclidean distance

Manhattan distance

• Reduce computation time
• Might not get good result

Cosine distance

• Smaller the distance, the more similar

$$\begin{array}{rl}\cos \theta & =\frac{\vec{a}\cdot \vec{b}}{|\vec{a}||\vec{b}|}\\ \text{Distance}=1-\cos \theta & =\frac{{\sum }_{i=1}^n(x_i^{\text{Train}}\times x_i^{\text{Test}})}{\sqrt{{\sum }_{i=1}^n(x_i^{\text{Train}}{)}^2}\sqrt{{\sum }_{i=1}^n(x_i^{\text{Test}}{)}^2}}\end{array}$$

Cosine distance vs cosine similarity

Hamming Distance

• The number of bit positions in which the bits are different
• For binary data string
• Categorical data

K Value

Suppose we have even number of classes and if we choose K to be an odd number, we can prevent the tie condition

D-fold Cross-Validation

1. Split into d groups
2. Select 1 group for testing, remaining for testing
3. For each value of K, classify the data and record the error
4. Repeat 1-3 for different value of K
5. For each value of K, find the average error across validation sets, choose K with the lowest error

Error Measurement for Classification Problems

Precision

$$\text{Precision}=\frac{\text{TP}}{\text{TP}+\text{FP}}$$

Recall

$$\text{Recall}=\frac{\text{TP}}{\text{TP}+\text{FN}}$$

F1-Score

$$\text{F1-Score}=\frac{2\times \text{Precision}\times \text{Recall}}{\text{Percision}+\text{Recall}}$$ $$\text{Error}=1-\text{F1-Score}$$

Error Measurement for Regression Problems

Mean Absolute Error (MAE)

$$\text{MAE}=\frac{{\sum }_{i=1}^m|a_i-p_i|}{m}$$

Mean Square Error (MSE)

$$\text{MSE}=\frac{{\sum }_{i=1}^m(a_i-p_i{)}^2}{m}$$

Mean Absolute Percentage Error (MAPE)

$$\text{MAPE}=\frac{{\sum }_{i=1}^m\left|\frac{a_i-p_i}{a_i}\right|}{m}$$