K Nearest Neighbors (KNN): How It Works and How to Train One
How KNN Decides
Most models study your rows and boil them down into something smaller, a set of weights or a tree of questions. KNN does not do that, it just keeps the rows. So when a new input arrives it measures the distance from that input to every row it has stored, takes the k closest ones, and counts their labels, the label with the most votes is the answer. With k at 5, if 3 of the 5 nearest rows say billing and 2 say sales, the answer is billing.
That means the whole model is basically "things that look alike probably are alike", and everything about how well it works comes down to what "look alike" means for your data. For numbers, distance is the straight line distance between the 2 rows across all their columns. For text, each message gets turned into a long list of word scores with tf-idf first, so 2 messages are close when they share the same important words.
It also means there is nothing to wait for at training time and all the work happens at predict time, which is the opposite of nearly every other model type. Training a KNN model on 5,000 rows takes about as long as saving the file. Predicting compares the input to all 5,000 rows, which is still only milliseconds at that size, but it grows with every row you add, where a trained random forest answers in the same time no matter how many rows it learned from.
What KNN Is Best At
- Small datasets. With 20 to 30 rows per label there is not enough for a complicated model to learn from, and KNN does not need to learn, it only needs to compare.
- Answers a person has to trust. You can show the 5 neighbors behind any prediction, and "these 5 past tickets were all billing" is a reason anyone can check.
- Labels that form pockets instead of clean lines. If the same label shows up in a few separate regions of your data, a linear model has to draw one boundary and gets it wrong, and KNN just follows the pockets.
- Data that keeps changing. Adding a row and retraining costs nothing, so a model that picks up new examples all day stays cheap.
- A first baseline. It takes 2 minutes to set up, and the number it gets right is the number every heavier model has to beat to be worth it.
Where It Breaks
Now the cases where KNN is the wrong pick, because the same simplicity that makes it easy also means it has no way to protect itself.
- Columns that do not matter. KNN treats every column as equally important, it has no idea which ones decide the answer. Say you have 3 useful columns and 20 that are noise, the noise is 87% of the distance, and the nearest rows end up being near for the wrong reasons.
- Columns on different scales. A column in dollars that runs 0 to 50,000 next to a rating that runs 1 to 5 means the dollars are the only thing being measured, the rating could be the whole answer and it would not move the distance at all. The engine used here scales numeric columns for this class before measuring, so it is handled for you, but it is the first thing to check in any other KNN setup.
- Unbalanced labels. If 90% of your rows are one label, then most of the 5 nearest rows to anything will be that label just from the numbers, and the rare label almost never wins a vote.
- Very large datasets. Every prediction looks at every row, so past a few hundred thousand rows the response time starts to matter and a model that compresses what it learned is the better tool.
- Long, wordy text. Two long documents share a lot of common words without being about the same thing, so KNN on text works best for short inputs like messages, subject lines, and search queries.
Choosing k
k is the only parameter, and it trades one kind of mistake for another. A small k like 1 or 3 follows your data very closely, which sounds good until 1 mislabeled row sits near the input and decides the whole answer. A large k like 25 smooths that out, but now the vote reaches far enough that it starts counting rows that are not really similar, and the biggest label starts winning everything.
So 5 is the default because it is a reasonable middle for small data, and these are the adjustments worth knowing:
- Use an odd number when you have 2 labels, so the vote can not tie.
- Keep k smaller than the row count of your smallest label. If your rarest label has 8 rows, a k of 15 means that label can never win, there are not enough of them to make a majority.
- A rough ceiling is the square root of your total rows, so about 10 for 100 rows and about 30 for 1,000. Past that you are mostly averaging.
- Do not reason your way to the answer, test it. Try 3, 5, 9, and 15 against the same set of inputs and keep the one that gets the most right, it takes a minute because retraining is instant.
How to Train a KNN Classifier Step by Step
These steps use ML Prediction Engine, the free open source tool this topic uses for its examples, where the class is named knn. If it is not installed yet, the machine learning models guide has the 1 command setup.
1. Create a pipeline with the knn class
In the admin, create a pipeline and add one model step. Set the category to classifier, the class to knn, and the input type to text if you are sending messages or numeric if you are sending columns of numbers. Set the parameters to:
{"k": 5}
Leaving the parameters empty also gives you 5.
2. Send only the columns that matter
For text there is nothing to do here, tf-idf puts every word score in the same range. For numeric input the engine scales each column for the knn class before measuring distance, so an order amount of 1,500 and a rating of 4 can go in as they are and neither one drowns out the other. What that leaves for you is the choice of columns. After scaling every column counts the same, so a column that has nothing to do with the answer gets as much say as the one that decides it. Send the 3 to 8 columns that really make 2 cases alike, and send them in the same order every time, for training rows and for predictions.
3. Add balanced labeled rows
Add real inputs with the label you want back, 20 to 30 per label to start, and keep the counts close to each other. Rows go in through the admin or the API:
curl -X POST http://localhost:8080/api.php/dataset/add \
-H "Content-Type: application/json" \
-H "X-API-Key: YOUR_KEY" \
-d '{"pipelineID": 1, "modelIndex": 0, "input": "i was charged twice this month", "label": "billing"}'
A numeric row looks the same with a list of numbers as the input, "input": [1500, 4, 12]. Every row has to have the same number of columns in the same order.
4. Train the model
Click Train, or call the endpoint:
curl -X POST http://localhost:8080/api.php/train \
-H "Content-Type: application/json" \
-H "X-API-Key: YOUR_KEY" \
-d '{"pipelineID": 1, "modelIndex": 0}'
The reply confirms how many rows it holds, {"message": "Model trained from 90 rows.", "samples": 90}. A classifier needs at least 2 different labels in the dataset or training is refused.
5. Test and choose k
Use the test box with inputs that are not in the dataset, testing with rows it already holds proves nothing because the nearest neighbor of a stored row is itself. Write down 20 or so test inputs with the answers you expect, run them, and count how many come back right. Then change k to 3, retrain, and run the same 20, then 9, then 15. Keep the value with the best count, and if 2 values tie, keep the larger one, it is less sensitive to a single bad row.
6. Predict from your app and feed back mistakes
Your code calls one endpoint:
curl -X POST http://localhost:8080/api.php/predict \
-H "Content-Type: application/json" \
-H "X-API-Key: YOUR_KEY" \
-d '{"pipelineID": 1, "input": "why did my card get billed again"}'
The answer comes back as {"output": "billing", "steps": [{"step": 0, "class": "knn", "output": "billing"}]}. When a prediction turns out wrong, add that input as a new row with the correct label and retrain. For KNN this is the most direct fix there is, the next similar input now has the corrected row sitting right next to it.
When to Move Off KNN
KNN is a starting point more often than a final answer, and the signs that it is time to switch are pretty clear. If accuracy stops improving as you add rows, the columns are probably the limit and Random Forest will work out which ones matter on its own. If the input is text and you are past a few hundred rows per label, Naive Bayes or Logistic Regression will usually be more accurate and answer faster. If predict time is creeping up because the dataset got big, any of those 3 fix it, since they do their work at training time.
Switching does not throw anything away. The rows belong to the pipeline step, so you change the class from knn to randomForest, retrain on the same dataset, and run the same test inputs to see if the number went up. And if you want a number back instead of a label, the same neighbor idea exists as the KNN Regressor, which averages the neighbors instead of counting votes.
KNN finds the 5 stored rows most like the new input and takes their majority label. Use it first on small data and anywhere a prediction has to be explained, send only the columns that matter, keep labels balanced, pick k by testing 3, 5, 9, and 15, and move to a heavier class when more rows stop making it better.