Neighbors and Regions

Finding the k Nearest

The next step sorts the squared-distance rows. The table shows how k and the equal-distance tie-break select the nearest training indices.

highlighted = computed this step

Pick the k smallest rows

With k=3, the selected rows are the three smallest squared distances.

k=3⇒ take the smallest 3k=3\Rightarrow\text{ take the smallest }3
Nearest neighborsThe nearest rows are selected by exact squared distance.Nearest neighborsquery=(1,1), k=3i(x,y)classd^2nearesttie-break0(0,0)A21low i1(2,0)A22low i2(0,2)A23low i3(3,3)B8low i4(3,1)B4low i5(1,3)B4low idistances use d^2 only; equal d^2 sorts by lowest training index

Why the tie-break is explicit

Equal d^2 values are sorted by lowest training index. Here the nearest indices are 0, 1, and 2.

nearest indices=[0,1,2]\text{nearest indices}=[0,1,2]
Nearest neighborsThe nearest rows are selected by exact squared distance.Nearest neighborsquery=(1,1), k=3i(x,y)classd^2nearesttie-break0(0,0)A21low i1(2,0)A22low i2(0,2)A23low i3(3,3)B8low i4(3,1)B4low i5(1,3)B4low idistances use d^2 only; equal d^2 sorts by lowest training index

Summary

The nearest rows all have class A and d^2=2. The vote has not been summarized yet.

nearest classes=A,A,A\text{nearest classes}=A,A,A
Nearest neighborsThe nearest rows are selected by exact squared distance.Nearest neighborsquery=(1,1), k=3i(x,y)classd^2nearesttie-break0(0,0)A21low i1(2,0)A22low i2(0,2)A23low i3(3,3)B8low i4(3,1)B4low i5(1,3)B4low idistances use d^2 only; equal d^2 sorts by lowest training index