K-Nearest Neighbor (or k-NN) is somewhat self-explanatory. This algorithm simply labels data with the label of whatever known data points are closest to it.
For example, in the plot to the right, we have an unknown (????) flower that has sepal width = 3.8cm and sepal length = 5.8cm. What label would you give this flower? Iris setosa or Iris versicolor? K-Nearest Neighbors would call it Iris setosa because that is its nearest neighbor.
Generalizing this rule, we can draw decision boundaries. Any point that falls in the blue-colored area will classified as a setosa iris because the example closest to it will be a setosa, and the same holds true for the other two regions.
But is this the best way to classify points? Picking only the single nearest neighbour means that our predictions will reproduce very closely the patterns found in our training data but may not generalize as well to new data. To combat this, we can consider not just the single closest point, but any number of neighbours.
The "k" in k-NN refers to how many neighbors should be considered. In the previous example we had a 1-NN model, meaning we only looked for the single closest neighbor when deciding what to call a new unknown flower.
In the plot here, we have the exact same data as before, but because this is now a 2-NN model we're looking for the two nearest neighbors and taking a vote to decide what label to choose. For example, if the two nearest neighbors are both setosa, then our new data point will be labeled setosa as well.
In practice, as we increase the number of neighbors, the boundaries become smoother and less jagged. Try it yourself at the bottom of the page!