Introduction
A KNN classifier assigns a class to a query point by looking at the labels of nearby training observations. Its decision boundary is the set of locations where the assigned class changes. The boundary is not generally a line chosen in advance: it is determined by the training-point arrangement, the value of \(k\), the distance measure, and the rule used to resolve ties.
A useful way to understand a KNN boundary is to separate two questions. First, which training observations are among the \(k\) nearest? Second, what class wins the vote among those observations? The neighbor set can change without changing the predicted class. The boundary consists only of locations where the prediction changes, with exact ties handled according to the classifier’s specified rule.
One-Dimensional Boundaries
In one dimension, training observations lie on a number line. With \(k=1\), the nearest observation changes at the midpoint between two consecutive training locations. If the labels on either side of that midpoint differ, it is a decision boundary. If their labels agree, the nearest observation changes but the prediction does not.
For \(k\) greater than 1, the same distinction matters. As a query moves, the set of its \(k\) nearest observations can change at a point where two observations are equally distant. But a classification boundary occurs only if the resulting majority class changes. For an odd \(k\), a vote tie is impossible when there are exactly two classes, but the selection of the \(k\) neighbors can still be ambiguous at an exact distance tie.
Worked Example: One-Dimensional Boundary With k = 1
A hypothetical risk-screening data set has three training records, with a one-dimensional score and a binary label: score 1 is class A, score 4 is class B, and score 10 is class A. Use \(k=1\) and ordinary distance on the score axis. Find the regions and classify a query with score 6.
Method. With one neighbor, the prediction is the label of the closest training record. The possible changes in the nearest record occur at the midpoints between consecutive score values.
Between scores 1 and 4, the midpoint is \((1+4)/2=2.5\). Between scores 4 and 10, it is \((4+10)/2=7\). Thus, away from the exact midpoint ties, the nearest record is at score 1 for scores below 2.5, at score 4 for scores between 2.5 and 7, and at score 10 for scores above 7.
The class regions are therefore: class A below 2.5, class B between 2.5 and 7, and class A above 7. For a query at score 6, the distances to the three records are \(5\), \(2\), and \(4\), respectively. The nearest is the class B record at score 4, so the prediction is class B.
Check. At score 2.5, the distances to scores 1 and 4 are both 1.5; at score 7, the distances to scores 4 and 10 are both 3. The prediction at either exact location depends on the specified tie rule. The common mistake is to report a unique class at a midpoint without acknowledging the tie.
Worked Example: A Three-Neighbor Boundary Is Not Every Neighbor Change
Consider five training records on a score axis: scores 0 and 6 have class A, while scores 2, 4, and 8 have class B. Use unweighted KNN with \(k=3\). Determine where the predicted class changes.
Method. Order the records by distance from the query. Because the scores are equally spaced, the three nearest records form consecutive groups of three, except at locations where a distance tie affects which record is included.
For a query below 3, the three nearest records are at 0, 2, and 4. Their labels are A, B, B, so the vote is class B. At score 3, records 0 and 6 are equally distant; on either side of 3, the selected set changes from \(\{0,2,4\}\) to \(\{2,4,6\}\). The second set has labels B, B, A, which also produces class B. Thus, this neighbor-set change is not a classification boundary.
For a query strictly between 3 and 5, the three nearest records are at 2, 4, and 6, with labels B, B, A. The prediction remains class B. For a query above 5, the three nearest records are at 4, 6, and 8, with labels B, A, B? Here the labels are B at 4, A at 6, and B at 8, so the vote is still class B. Consequently, this particular arrangement has no class change: class B wins in all three regions.
At score 5, the records at 2 and 8 are equally distant. Either possible three-record set still gives a B majority: \(\{2,4,6\}\) has two B labels, and \(\{4,6,8\}\) also has two B labels. The prediction at the tie is therefore stable as well.
Check. The neighbor set changes at scores 3 and 5, but the majority is class B on both sides of each change. A common error is to call every midpoint between training records a decision boundary for \(k>1\). The boundary depends on the vote, not solely on neighbor identity.
Why Euclidean Boundaries Have Their Shape
In two dimensions, a query is a point \(z=(x,y)\), and each training observation is a point in the same coordinate system. For \(k=1\), the region assigned to a particular training observation consists of query points closer to it than to any other training point. These regions form a Voronoi diagram. Where the nearest observation changes between two points, their distances are equal.
The perpendicular-bisector formula follows by setting the squared distances equal. Squaring is valid because distances are nonnegative, and it removes the square roots. Expanding both sides cancels the query’s squared-coordinate terms, leaving a linear equation.
This equation describes a line in two dimensions (and a hyperplane in higher dimensions). It explains why the \(k=1\) Euclidean boundary between two nearest-neighbor regions is straight, although the complete set of regions can have several edges and corners. For \(k>1\), portions of such equal-distance lines can divide areas with different neighbor rankings. Some portions do not divide classes because both sides produce the same majority.
Worked Example: A Two-Dimensional Euclidean Boundary
A hypothetical training set contains just two records: \(p=(0,0)\) with class A and \(q=(4,2)\) with class B. Use \(k=1\) and Euclidean distance. Find the boundary and classify the query \(z=(3,1)\).
Method. With only two records, the prediction changes where their Euclidean distances are equal. Using the formula above, \(q-p=(4,2)\), \(\|q\|^2=4^2+2^2=20\), and \(\|p\|^2=0\). Therefore the boundary satisfies \(2(4,2)\mathbin{\cdot}(x,y)=20\), or \(8x+4y=20\). Dividing by 4 gives \(2x+y=5\).
At \(z=(3,1)\), \(2x+y=2(3)+1=7\), which is greater than 5. Direct distances confirm the side of the boundary: the distance to \(p\) is \(\sqrt{3^2+1^2}=\sqrt{10}\), and the distance to \(q\) is \(\sqrt{(3-4)^2+(1-2)^2}=\sqrt{2}\). Since \(\sqrt{2}<\sqrt{10}\), the query is assigned class B.
Check. At a point on the line \(2x+y=5\), the two records are equally distant. The common mistake is to equate the coordinates or draw a line through the training points; the boundary is the perpendicular bisector, not the segment joining the records.
Distance Choice and Training-Point Arrangement
A decision boundary is a property of both the data and the distance measure. Euclidean distance gives the perpendicular-bisector result above. Manhattan distance, which sums absolute coordinate differences, can produce a different equal-distance set. A feature-weighted distance can also alter which observations are nearest by giving some coordinate differences more influence than others.
Worked Example: Changing the Distance Changes the Boundary
Use two hypothetical training records: \(p=(0,0)\) with class A and \(q=(4,2)\) with class B. Compare their boundaries along the horizontal axis \(y=0\), first under Euclidean distance and then under Manhattan distance. Classify \(z=(2.75,0)\) under each measure.
Euclidean distance. For a point \((x,0)\) between the records’ horizontal coordinates, the distances are \(x\) to \(p\) and \(\sqrt{(x-4)^2+2^2}\) to \(q\). Equating their squares gives \(x^2=(x-4)^2+4\). Expanding gives \(x^2=x^2-8x+20\), so \(x=2.5\). At \(x=2.75\), the squared distances are \(2.75^2=7.5625\) and \((-1.25)^2+4=5.5625\). The query is closer to \(q\), so it is class B.
Manhattan distance. Along \(y=0\), the distances are \(x\) to \(p\) and \(|x-4|+2\) to \(q\). For \(0\leq x\leq4\), equality becomes \(x=(4-x)+2\), so \(x=3\). At \(x=2.75\), the distances are 2.75 and \(1.25+2=3.25\), so the query is class A.
Check. The same query is class B under Euclidean distance and class A under Manhattan distance. This comparison is along \(y=0\); it does not assert that either full two-dimensional boundary is a vertical line. The trap is to assume that changing the distance formula cannot change the classifier.
The arrangement of all training points matters as well. A label change between a pair of nearby points does not guarantee a visible boundary between them: a third point may be closer throughout the area. Likewise, with \(k>1\), a class can occupy a region even if none of the training points in that region has that class, because the local vote combines several labels.
Worked Example: A Two-Dimensional Boundary With k = 3
Four hypothetical records form two columns: class A at \((0,0)\) and \((0,4)\), and class B at \((4,0)\) and \((4,4)\). Use Euclidean distance and \(k=3\). Determine the predicted class on each side of the vertical line \(x=2\), and discuss the line itself.
Method. Compare each A point with the B point at the same height. For a query \((x,y)\), the squared-distance difference for either such pair is \((x-4)^2+(y-y_j)^2-\{x^2+(y-y_j)^2\}=16-8x\), where \(y_j\) is 0 or 4. The vertical-coordinate terms cancel.
If \(x<2\), then \(16-8x>0\): each A point is closer than its corresponding B point. The three nearest records cannot include both B points, because each B point would have its paired A point closer; that would require all four records to be at least as close as the two B points. Thus, at most one B point can be among the three nearest, so at least two of the three votes are A. The prediction is class A.
If \(x>2\), then \(16-8x<0\), and each B point is closer than its corresponding A point. By the same reasoning, at most one A point can be among the three nearest, so the prediction is class B. The class regions are separated by \(x=2\).
At \(x=2\), each paired A and B point is equally distant. The three-neighbor selection can omit either an A or a B point; those selections can yield different majorities. Therefore the exact prediction on the line depends on the neighbor tie-breaking rule. The common mistake is to assume that an odd \(k\) eliminates every tie: it eliminates a two-class vote tie among three selected labels, but not ambiguity in selecting the three neighbors.
Reading and Checking a KNN Boundary
A reliable boundary analysis proceeds by identifying the classifier completely before drawing regions. State the coordinates and labels, the value of \(k\), the distance measure, and the treatment of exact ties. Then determine where neighbor rankings can change and evaluate the vote on each resulting region. For small examples, a few representative query points on either side can check the result; a complete solution should also explain why the rankings or votes stay the same within each region.
Record \(k\), the distance definition, equal or weighted voting, and any tie rule. Without these, the boundary may not be uniquely specified.
In one dimension, compare distances along the axis. In two dimensions with Euclidean distance, pairwise equal-distance sets are perpendicular bisectors.
For each region of fixed neighbor ranking, count the labels among the \(k\) selected records. Mark a decision boundary only where the predicted class changes.
Evaluate the stated tie rule on equal-distance locations, and test query points on each side to catch sign or coordinate errors.
The value of \(k\) changes the boundary because it changes which labels contribute to each vote. A small \(k\) can allow individual training labels to create small, irregular regions; a larger \(k\) combines more observations and can merge or remove local regions. This is a geometric expression of the bias-variance tradeoff, not a guarantee that increasing \(k\) always makes a boundary smoother in every particular finite data set.
Distance and feature scaling are equally important. If a coordinate’s numerical scale is much larger than another’s, an unscaled distance can make differences in the larger-scale coordinate dominate neighbor selection. A different metric or feature weighting can therefore move boundaries even though no labels or coordinates have changed. Interpret any plotted boundary only in the coordinate system and distance measure actually used.
Check Your Understanding
For each problem, state the class regions or boundary and account for exact ties where relevant.
- On a one-dimensional score axis, class A is observed at 0 and 11, while class B is observed at 4. With \(k=1\), find the class regions, the boundary locations, and the prediction at score 8. (Answer: A below 2, B between 2 and 7.5, and A above 7.5; score 8 is A; the exact boundaries are distance ties.)
- Five equally spaced observations have scores 1, 3, 5, 7, and 9, with labels A, B, B, A, A in that order. With \(k=3\), identify the predicted class on either side of score 6 and explain whether the neighbor-set change at score 4 is a class boundary. (Answer: class B below 6 and class A above 6; the neighbor set changes at 4 but the vote remains B on both sides, so 4 is not a class boundary.)
- Two training points are \(p=(1,1)\), class A, and \(q=(5,3)\), class B. With \(k=1\) and Euclidean distance, derive the boundary equation and classify \((3,1)\). (Answer: \(2x+y=8\); \((3,1)\) is class A.)
- Two training points are \(p=(0,0)\), class A, and \(q=(6,2)\), class B. Along \(y=0\), find the equal-distance boundary under Euclidean and Manhattan distance. (Answer: Euclidean boundary \(x=10/3\); Manhattan boundary \(x=4\), considering \(0\leq x\leq6\).)
- For \(k=3\), class A points are \((0,0)\) and \((0,4)\), and class B points are \((4,0)\) and \((4,4)\). Under Euclidean distance, state the predicted classes for \(x<2\) and \(x>2\), and explain what is needed to specify the prediction at \(x=2\). (Answer: class A for \(x<2\), class B for \(x>2\); a tie-breaking rule for selecting equally distant neighbors is needed at \(x=2\).)