# What's the best way to find KNN by hand?

Lets say I'm given the following and need to find 'use' KNN to predict the class label of record 15 and know beforehand that k is set to 3. What are the proper steps, regardless of table, or label or k is set to in order to do this?

The first 10 are training data, and the other 10 are testing data.

K-Nearest Neighbor is an instance-based learning algorithm that, as the name implies, looks at the K neighbors nearest to the current instance when deciding on a classification. In order to determine which neighbors are nearest, you need a distance measure. In the sample data set above, the distance measure that makes the most sense is the # of matching nominal values/# of attributes (4 in this case). For Record ID 1, we can calculate the distance between this instance and the instances between Record ID 2-10 as follows: ID2: 3 matching attribute values/4 attributes = 0.75 ID3: 3/4 = 0.75 ID4: 2/4 = 0.5 ID5: 3/4 = 0.75 ID6: 2/4 = 0.5 ID7: 2/4 = 0.5 ID8: 1/4 = 0.25 ID9: 3/4 = 0.75 ID10: 2/4 = 0.5

Thus, it is clear that instances ID2,ID3,ID5, and ID9 are ID1's nearest neighbors. However, since K is 3 in this case, we will only consider ID2,ID3, and ID5's labels: ID2: Soft contact ID3: Noncontact ID5: Noncontact

Therefore, the assigned classification for ID1 will be "Noncontact" as this was the majority label/classification for ID1's K-nearest neighbors, which turns out to be the correct label after all. As K-NN is an instance-based learner, the algorithm does not need to be trained in the way a neural network or decision tree does, and can thus assign classifications for all 20 instances within this dataset using the algorithm I have outlined.

• No problem! If you're happy with my answer, please upvote it. Thank you. Commented Oct 11, 2015 at 17:44

Steps for finding KNN:

1. Determine the value of k = number of nearest neighbors to be considered.
2. Calculate the distance (Euclidean is the most popular implementation to work by hand) between the query instance and all the training samples
3. Sort the distance and determine nearest neighbors based on the k-th minimum distance
4. Gather the category/class labels of the k nearest neighbors.

5. Use simple majority of the category of nearest neighbors as the prediction label of the query instance

To perform Step 2, you would need to assign numeric values to the values to compute distance. Any values work - but keep it constant accross the columns(it should not add bias while calculating Euclidean distance). For instance, let us assign values:

• Age -> Young = 0, Pre-presbiopic = 1, Presbiopic = 2
• Spectacle Prescription -> Myope = 0, Hypermetrope = 1
• Astigmatic -> No = 0, Yes = 1
• Tear production Rate -> Reduced = 0, Normal = 1

Solving the example you gave:

1. k = 3
2. The squared distances of record 15 from other labels (Don't take square-root to save computation as we need relative values):

• R1: 1+1+1+0 = 3
• R2: 1+1+1+0 = 3
• R3: 1+1+0+1 = 3
• R4: 1+1+0+0 = 2
• R5: 1+0+1+1 = 3
• R6: 1+0+1+0 = 2
• R7: 1+0+0+1 = 2
• R8: 1+0+0+0 = 1
• R9: 0+1+1+1 = 3
• R10: 0+1+1+0 = 2
3. R8 is the closest. We need 2 more neighbors. The algorithm can give different results if we chose any of the neighbors with squared distance = 2. Consider we picked R8, R7, R10 as nearest neighbors

4. R8: Noncontact, R7: Noncontact, R10: Soft contact.

5. Hence our R15 would be 'Noncontact' as that's the majority.

This aligns with the test data. But if we chose some other neighbors with distance 2 we could have arrived at a different conclusion or contention in the decision. More data could remove this problem.