Neighbors and Regions

Majority Vote

After the nearest rows are fixed, the class is assigned by a strict majority vote. Odd k keeps the displayed rule deterministic.

highlighted = computed this step

Majority vote

The k nearest labels are A, A, and A. The majority vote assigns class A to the query.

vote=A\text{vote}=A
Majority voteThe selected nearest rows determine the class by exact majority.Majority votequery=(1,1), k=3, vote=Ai(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 indexexact k-NN classification timelinestatic sequence: query -> squared distances -> sorted nearest k -> majority vote1. queryq=(1,1)k=3source: shown training set2. d^2 rowsi0 (0,0) A d^2=2i1 (2,0) A d^2=2i2 (0,2) A d^2=2i3 (3,3) B d^2=8i4 (3,1) B d^2=4i5 (1,3) B d^2=43. sorted k*1: i0 d^2=2 class=A*2: i1 d^2=2 class=A*3: i2 d^2=2 class=A 4: i4 d^2=4 class=B 5: i5 d^2=4 class=B 6: i3 d^2=8 class=Bnearest=[0, 1, 2]4. voteA: 3vote=Ano square rootsequal d^2 sorts by lowest training index

Why k is odd

This surface requires odd k. With k=3, a strict majority exists for the displayed nearest labels.

k=3 is oddk=3\text{ is odd}
Majority voteThe selected nearest rows determine the class by exact majority.Majority votequery=(1,1), k=3, vote=Ai(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 indexexact k-NN classification timelinestatic sequence: query -> squared distances -> sorted nearest k -> majority vote1. queryq=(1,1)k=3source: shown training set2. d^2 rowsi0 (0,0) A d^2=2i1 (2,0) A d^2=2i2 (0,2) A d^2=2i3 (3,3) B d^2=8i4 (3,1) B d^2=4i5 (1,3) B d^2=43. sorted k*1: i0 d^2=2 class=A*2: i1 d^2=2 class=A*3: i2 d^2=2 class=A 4: i4 d^2=4 class=B 5: i5 d^2=4 class=B 6: i3 d^2=8 class=Bnearest=[0, 1, 2]4. voteA: 3vote=Ano square rootsequal d^2 sorts by lowest training index

Summary

The assigned class is A because 3 nearest labels vote A. A changed authored vote is rejected.

assigned class=A\text{assigned class}=A
Majority voteThe selected nearest rows determine the class by exact majority.Majority votequery=(1,1), k=3, vote=Ai(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 indexexact k-NN classification timelinestatic sequence: query -> squared distances -> sorted nearest k -> majority vote1. queryq=(1,1)k=3source: shown training set2. d^2 rowsi0 (0,0) A d^2=2i1 (2,0) A d^2=2i2 (0,2) A d^2=2i3 (3,3) B d^2=8i4 (3,1) B d^2=4i5 (1,3) B d^2=43. sorted k*1: i0 d^2=2 class=A*2: i1 d^2=2 class=A*3: i2 d^2=2 class=A 4: i4 d^2=4 class=B 5: i5 d^2=4 class=B 6: i3 d^2=8 class=Bnearest=[0, 1, 2]4. voteA: 3vote=Ano square rootsequal d^2 sorts by lowest training index