Nearest Neighbors

kNN Classify by Majority Vote

Classify a query point by the majority class among its k=3 nearest neighbors. One loop computes (squared_distance, index) pairs to avoid sqrt (squaring preserves ranking); .sort() orders them; a second loop over the first 3 tallies votes by looking up labels via index; max(votes, key=votes.get) picks the winner. Library: sklearn.neighbors.KNeighborsClassifier(n_neighbors=3).fit(X, y) .predict([query]). RESULT: predicted class label.

By hand

X_train=[[1,1],[2,1],[4,1],[8,7],[9,8],[7,9]], y=['A','B','A','B','B','B']. Query=[2,2]. Squared distances: [2,1]→1(B), [1,1]→2(A), [4,1]→5(A), others≥61. Three nearest: B, A, A → vote A:2, B:1 → majority A.

naive.py
Replay: real traced execution (multi-file project)
X_train = [[1,1], [2,1], [4,1], [8,7], [9,8], [7,9]]
y_train = ['A', 'B', 'A', 'B', 'B', 'B']
query = [2, 2]
n_train = len(X_train)
dists = []
for i in range(n_train):
    d0 = X_train[i][0] - query[0]
    d1 = X_train[i][1] - query[1]
    dists.append((d0*d0 + d1*d1, i))
dists.sort()
votes = {}
for i in range(3):
    lbl = y_train[dists[i][1]]
    votes[lbl] = votes.get(lbl, 0) + 1
winner = max(votes, key=votes.get)
print('RESULT:', repr(winner))

  1. X_train ← [[1, 1], [2, 1], [4, 1], [8, 7], [9, 8], [7, 9]]

    1X_train = [[1,1], [2,1], [4,1], [8,7], [9,8], [7,9]]2y_train = ['A', 'B', 'A', 'B', 'B', 'B']
    values this step[[1, 1], [2, 1], [4, 1], [8, 7], [9, 8], [7, 9]]X_train

  2. y_train ← ['A', 'B', 'A', 'B', 'B', 'B']

    1X_train = [[1,1], [2,1], [4,1], [8,7], [9,8], [7,9]]2y_train = ['A', 'B', 'A', 'B', 'B', 'B']3query = [2, 2]
    values this step['A', 'B', 'A', 'B', 'B', 'B']y_train

  3. query ← [2, 2]

    2y_train = ['A', 'B', 'A', 'B', 'B', 'B']3query = [2, 2]4n_train = len(X_train)
    values this step[2, 2]query

  4. n_train ← 6

    3query = [2, 2]4n_train = len(X_train)5dists = []
    values this step6n_train

  5. dists ← []

    4n_train = len(X_train)5dists = []6for i in range(n_train):
    values this step[]dists

  6. i ← 0, d0 ← -1, d1 ← -1, dists ← [(2, 0)]

    pass 1 of 6
    5dists = []6for i in range(n_train):7    d0 = X_train[i][0] - query[0]8    d1 = X_train[i][1] - query[1]9    dists.append((d0*d0 + d1*d1, i))10dists.sort()
    values this step0i-1d0-1d1[] → [(2, 0)]dists
    All 6 passes — pass 1 is the card above
    passid0d1dists
    10-1-1[] → [(2, 0)]
    20 → 1-1 → 0—[(2, 0)] → [(2, 0), (1, 1)]
    31 → 20 → 2—[(2, 0), (1, 1)] → [(2, 0), (1, 1), (5, 2)]
    42 → 32 → 6-1 → 5[(2, 0), (1, 1), (5, 2)] → [(2, 0), (1, 1), (5, 2), (61, 3)]
    53 → 46 → 75 → 6[(2, 0), (1, 1), (5, 2), (61, 3)] → [(2, 0), (1, 1), (5, 2), (61, 3), (85, 4)]
    64 → 57 → 56 → 7[(2, 0), (1, 1), (5, 2), (61, 3), (85, 4)] → [(2, 0), (1, 1), (5, 2), (61, 3), (85, 4), (74, 5)]

  7. for i in range(n_train):

    5dists = []6for i in range(n_train):7    d0 = X_train[i][0] - query[0]

  8. dists ← [(1, 1), (2, 0), (5, 2), (61, 3), (74, 5), (85, 4)]

    9    dists.append((d0*d0 + d1*d1, i))10dists.sort()11votes = {}
    values this step[(2, 0), (1, 1), (5, 2), (61, 3), (85, 4), (74, 5)] → [(1, 1), (2, 0), (5, 2), (61, 3), (74, 5), (85, 4)]dists

  9. votes ← {}

    10dists.sort()11votes = {}12for i in range(3):
    values this step{}votes

  10. i ← 0, lbl ← 'B', votes ← {'B': 1}

    pass 1 of 3
    11votes = {}12for i in range(3):13    lbl = y_train[dists[i][1]]14    votes[lbl] = votes.get(lbl, 0) + 115winner = max(votes, key=votes.get)
    values this step5 → 0i'B'lbl{} → {'B': 1}votes
    All 3 passes — pass 1 is the card above
    passilblvotes
    15 → 0'B'{} → {'B': 1}
    20 → 1'B' → 'A'{'B': 1} → {'B': 1, 'A': 1}
    31 → 2—{'B': 1, 'A': 1} → {'B': 1, 'A': 2}

  11. for i in range(3):

    11votes = {}12for i in range(3):13    lbl = y_train[dists[i][1]]

  12. winner ← 'A'

    14    votes[lbl] = votes.get(lbl, 0) + 115winner = max(votes, key=votes.get)16print('RESULT:', repr(winner))
    values this step'A'winner

  13. stdout ← RESULT: 'A'

    15winner = max(votes, key=votes.get)16print('RESULT:', repr(winner))
    values this stepRESULT: 'A'stdout

With scikit-learn

KNeighborsClassifier(n_neighbors=3) uses Euclidean distance by default. kneighbors([query]) exposes the 3 nearest distances and indices for the snapshot. RESULT is the string predicted by .predict.

library.py 
from sklearn.neighbors import KNeighborsClassifier
from dalib.display import set_display
set_display()

X_train = [[1,1], [2,1], [4,1], [8,7], [9,8], [7,9]]
y_train = ['A', 'B', 'A', 'B', 'B', 'B']
query = [2, 2]
clf = KNeighborsClassifier(n_neighbors=3)
clf.fit(X_train, y_train)
dists, indices = clf.kneighbors([query])
neighbors = [y_train[i] for i in indices[0]]
pred = str(clf.predict([query])[0])
print('k=3 neighbors:', neighbors)
print('distances:', [round(float(d), 4) for d in dists[0]])
print('RESULT:', repr(pred))

k=3 neighbors: ['B', 'A', 'A']
distances: [1.0, 1.4142, 2.2361]
RESULT: 'A'

Implementation notes

  • Squared distances are used for ranking (avoids math.sqrt): √a < √b ↔ a < b for non-negative a, b. The votes are over labels, not distances, so the actual distance value is not needed.
  • The 2-1 vote (A:2, B:1) shows majority overriding the single nearest neighbor (which is class B at sq=1). A pure 3-0 unanimous vote would not demonstrate majority voting.
  • Training points and query are chosen so no two training points are equidistant from the query and the 3rd/4th boundary is unambiguous (sq=5 vs sq=61) — eliminating tie-breaking ambiguity between naive and sklearn.
  • sklearn's KNeighborsClassifier auto-selects an efficient neighbor-search structure (algorithm='auto'); it applies the same Euclidean metric, so distances match euclidean-distance (this chapter) exactly.
  • With k=3 and a unanimous vote (3-0), prediction is unambiguous. Ties (e.g. k=2 with one A and one B) require a tie-breaking rule — sklearn uses the class with the smaller index in classes_.
  • Cross-reference: euclidean-distance (this chapter) for the distance formula used to rank neighbors.