k-Nearest Neighbors — NumPy দিয়ে নিজে লেখা

মডিউল ১০-এ যন্ত্র ডেটা থেকে শেখে। পর্ব ৩৩ (Vector আর similarity)-এ দূরত্বের তিন মাপ, scaling-এ সবচেয়ে কাছের প্রতিবেশী বদলে যাওয়া আর curse of dimensionality দেখেছেন; এখানে সেই দূরত্ব দিয়ে প্রথম পূর্ণাঙ্গ classifier বানাব। চালানো যায় এমন ব্লকগুলো পাতাতেই চলে (ব্রাউজারের Python, NumPy 2.4.6, scikit-learn 1.8.0). scikit-learn প্রথমবার নামতে প্রায় ১০ সেকেন্ড লাগে; পরের run দ্রুত।

১ · প্রতিবেশী দেখে চেনা — k-NN-এর ধারণা

বাজারঘর (এই কোর্সের কাল্পনিক অনলাইন দোকান) জানতে চায়: যে নতুন গ্রাহক এই মাসে প্রথম কিনলেন, তিনি কি আবার কিনবেন? যাঁরা আবার কিনবেন না বলে মনে হয়, তাঁদের একটি ছাড়ের কুপন পাঠানো যায়। প্রতিটি গ্রাহকের তিনটি feature: প্রথম মাসে কয়টি অর্ডার, গড় ঝুড়ির দাম (টাকা) আর গড়ে কত দিনে ডেলিভারি পেয়েছেন। Label দুটি: ১ মানে পরের তিন মাসে আবার কিনেছেন, ০ মানে কেনেননি। এটি একটি binary classification.

নিয়মটি তিন লাইনে: (১) নতুন বিন্দু q থেকে প্রতিটি training বিন্দুর দূরত্ব মাপুন, সাধারণত Euclidean distance; (২) সবচেয়ে ছোট k-টি দূরত্বের বিন্দু বাছুন; (৩) তাদের label-এর majority vote দিন। Regression-এ ভোটের বদলে গড় (অংশ ৮)।

অন্য প্রায় সব model training-এর সময় কিছু সংখ্যা শেখে: পর্ব ৫১-এর Naive Bayes শব্দ গোনে, পরের পর্বের linear regression ওজন শিখবে। k-NN কিছুই শেখে না; শুধু পুরো training ডেটা মনে রাখে, আর আসল কাজ করে প্রশ্ন আসার পর। একে বলে lazy learning, বা instance-based learning. উল্টো দিকে যেসব model আগেই একটি সূত্র বানিয়ে ডেটা ফেলে দিতে পারে, তাদের বলে eager learner. k-NN আবার একটি nonparametric model: এর “আকার” আগে থেকে ঠিক করা কয়েকটি সংখ্যায় বাঁধা নয়, ডেটা যত বাড়ে model তত বড় হয়।

২ · হাতে k-NN — সাতজন গ্রাহক, k = ১, ৩ আর ৫

প্রথমে কাগজে-কলমে, যেমন বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় আসে। শুধু দুটি feature নিই, যাদের মাপ কাছাকাছি: প্রথম মাসের অর্ডার আর গড় ডেলিভারি দিন। সাতজন চেনা গ্রাহক (কাল্পনিক):

দুই শ্রেণির সমস্যায় k বিজোড় রাখলে ভোটে কখনো টাই হয় না; তিন বা বেশি শ্রেণিতে বিজোড় k-ও টাই ঠেকাতে পারে না (যেমন k = ৩-এ তিন শ্রেণির একটি করে ভোট)। টাই ভাঙার নিয়ম অংশ ৪-এ।

৩ · Distance matrix — broadcasting বনাম ‖a‖² + ‖b‖² − 2a·b

একটি q-এর জন্য হাতে সাতটি দূরত্ব সহজ। কিন্তু ১০০০টি নতুন গ্রাহক আর ৩০০০টি চেনা গ্রাহক হলে লাগবে ৩০ লাখ দূরত্ব। NumPy-তে loop না লিখে পুরো test × train distance matrix একবারে বানানো যায়, দুই পথে।

পথ ১, broadcasting: পর্ব ১৫-এর কৌশল। Query A-এর shape (m, d), train B-এর (n, d). A[:, None, :] হয় (m, 1, d), B[None, :, :] হয় (1, n, d); বিয়োগ করলে (m, n, d), বর্গ করে শেষ অক্ষে যোগ করলে (m, n). সমস্যা মেমরিতে: মাঝের অস্থায়ী array-টি m × n × d × ৮ বাইট; ১০০০ × ৩০০০ × ৩ × ৮ = ৭.২ কোটি বাইট, প্রায় ৭২ MB.

পথ ২, dot-product কৌশল: বর্গ দূরত্বকে খুলে লিখুন। (a − b)·(a − b) = a·a − 2a·b + b·b, অর্থাৎ

‖a − b‖² = ‖a‖² + ‖b‖² − 2 a·b

এখানে ‖a‖² মানে a-এর ঘরগুলোর বর্গের যোগফল, আর a·b হলো dot product (পর্ব ১৭)। সব জোড়ার a·b একসঙ্গে একটি matrix গুণ: A @ B.T, shape (m, d) @ (d, n) → (m, n). ‖a‖² একটি (m, 1) কলাম, ‖b‖² একটি (1, n) সারি, broadcasting-এ যোগ। কোনো (m, n, d) array তৈরি হয় না, আর matrix গুণ NumPy-র সবচেয়ে দ্রুত কাজগুলোর একটি।

দাম একটি: floating-point-এ বড় সংখ্যা থেকে প্রায় সমান বড় সংখ্যা বিয়োগ করলে অর্থবহ অঙ্ক হারিয়ে যায় (catastrophic cancellation). দুটি প্রায় একই গ্রাহকের সত্যিকারের বর্গ দূরত্ব হয়তো 10⁻¹², অথচ ‖a‖² প্রায় 10⁶ (টাকার কলামের জন্য); বিয়োগের পর যা থাকে তা মূলত rounding error, আর তা ঋণাত্মকও হতে পারে। ঋণাত্মক সংখ্যার বর্গমূল nan. নিচের ব্লক দুটি পথ মাপে, argsort আর argpartition তুলনা করে, তারপর ফাঁদটি দেখায়।

import time
import numpy as np
np.set_printoptions(precision=3)

rng = np.random.default_rng(42)
# কাল্পনিক গ্রাহক: [প্রথম মাসের অর্ডার, গড় ঝুড়ি (টাকা), গড় ডেলিভারি দিন]
def customers(n):
    return np.column_stack([rng.poisson(2.5, n), rng.normal(1200, 400, n),
                            rng.uniform(1, 7, n)])
Q, T = customers(1000), customers(3000)          # 1000টি query, 3000টি train

def d2_broadcast(A, B):                           # (m,1,3) − (1,n,3) → (m,n,3)
    return ((A[:, None, :] - B[None, :, :]) ** 2).sum(axis=-1)
def d2_trick(A, B):                               # ‖a‖² + ‖b‖² − 2a·b
    return (A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2 * A @ B.T

for f in (d2_broadcast, d2_trick):
    t0 = time.perf_counter(); D = f(Q, T); t = time.perf_counter() - t0
    print(f"{f.__name__:12} {D.shape}  {t*1000:6.1f} ms")
print("দুই পথ মেলে (allclose)?", np.allclose(d2_broadcast(Q, T), d2_trick(Q, T)))

t0 = time.perf_counter(); full = np.argsort(D, axis=1)[:, :5]; t1 = time.perf_counter()
part = np.argpartition(D, 4, axis=1)[:, :5]; t2 = time.perf_counter()
print(f"argsort {1000*(t1-t0):.1f} ms, argpartition {1000*(t2-t1):.1f} ms,",
      "একই ৫ প্রতিবেশী?", np.array_equal(np.sort(full, 1), np.sort(part, 1)))

near = T[:5] + 1e-6                               # প্রায় হুবহু একই ৫ জন গ্রাহক
print("broadcast:", d2_broadcast(near, T[:5]).diagonal())
bad = d2_trick(near, T[:5]).diagonal()
print("trick    :", bad)
print("sqrt     :", np.sqrt(bad))
print("ঠিক করা  :", np.sqrt(np.maximum(bad, 0)))  # 0-এর নিচে কেটে দেওয়া

d2_broadcast (1000, 3000)   123.0 ms
d2_trick     (1000, 3000)    24.3 ms
দুই পথ মেলে (allclose)? True
argsort 226.3 ms, argpartition 43.3 ms, একই ৫ প্রতিবেশী? True
broadcast: [3.e-12 3.e-12 3.e-12 3.e-12 3.e-12]
trick    : [ 0.000e+00  0.000e+00  0.000e+00  0.000e+00 -9.313e-10]
sqrt     : [ 0.  0.  0.  0. nan]
ঠিক করা  : [0. 0. 0. 0. 0.]

argsort না argpartition?

np.argsort পুরো সারি সাজায়: n টি দূরত্বে মোটামুটি O(n log n). কিন্তু আমাদের দরকার শুধু সবচেয়ে ছোট k-টি, তাদের ভেতরের ক্রমও নয়। np.argpartition(D, k - 1, axis=1) প্রতিটি সারিকে এমনভাবে ভাগ করে যে প্রথম k ঘরে সবচেয়ে ছোট k-টির index থাকে, গড়ে O(n) সময়ে (introselect, quickselect-এর একটি রূপ)। ভেতরের ক্রম নিশ্চিত নয়; ভোটের জন্য তা লাগেও না। দূরত্বের ক্রমে প্রতিবেশী দেখাতে চাইলে প্রথমে argpartition, তারপর শুধু সেই k-টিকে argsort.

৪ · নিজের হাতে k-NN classifier — আর scikit-learn-এর সঙ্গে মেলানো

এবার বাজারঘরের ৬০০ জন কাল্পনিক নতুন গ্রাহকের ডেটা। সম্পর্কটি আমরা নিজেরা বানিয়েছি, আর তা জানা থাকায় পরে যাচাই করা যায়: বেশি অর্ডার আবার কেনার সম্ভাবনা বাড়ায়, ধীর ডেলিভারি কমায়, বড় ঝুড়ি সামান্য বাড়ায়, সঙ্গে এলোমেলো কোলাহল (কোডের logit লাইন; logistic function-এর বিস্তারিত পর্ব ৫৯-এ)। বাস্তব গ্রাহকের আচরণ এত সরল নয়।

ডেটা তিন ভাগ: ৬০% train (৩৬০ জন), ২০% validation (১২০), ২০% test (১২০), stratify দিয়ে দুই শ্রেণির অনুপাত সব ভাগে সমান রেখে। Validation দিয়ে k বাছা হবে, test শুধু শেষ মাপের জন্য; কেন এই তিন ভাগ, তা পর্ব ৫৬ (Train, validation আর test — data leakage-এর ফাঁদ)-এর বিষয়। Scaling-এর গড় আর standard deviation নেওয়া হয় শুধু train থেকে (অংশ ৬)।

ভোট আর টাই ভাঙার নিয়ম

votes = ytr[idx] একটি (m, k) array: প্রতিটি সারিতে একজন query-র k প্রতিবেশীর label. প্রতিটি সারিতে np.bincount(v, minlength=2) প্রতিটি শ্রেণির ভোট গোনে, আর argmax() সবচেয়ে বেশি ভোটের শ্রেণি দেয়। টাই হলে argmax প্রথমটি, অর্থাৎ সবচেয়ে ছোট label ফেরত দেয়। টাই ভাঙার কয়েকটি প্রচলিত নিয়ম:

• ছোট label জেতে: সহজ আর নির্ধারিত; scikit-learn-এর uniform ভোটও কার্যত তাই করে। কিন্তু এতে একটি শ্রেণির দিকে সামান্য পক্ষপাত থাকে।
• সবচেয়ে কাছের প্রতিবেশীর label: টাই হলে k কমিয়ে আবার ভোট, বা টাইয়ে থাকা শ্রেণিগুলোর মধ্যে যার প্রতিবেশী সবচেয়ে কাছে।
• দূরত্বের ওজন: weighted voting-এ (অংশ ৭) সত্যিকারের টাই প্রায় হয়ই না।
• এলোমেলো: seed দিয়ে random বাছাই; পক্ষপাতহীন, কিন্তু একই input-এ ফল seed-এর ওপর নির্ভর করে।

আরেক রকম টাই হলো দূরত্বের টাই: k-তম আর (k + ১)-তম প্রতিবেশী সমান দূরে, কিন্তু label আলাদা। তখন কে ঢুকবে, তা নির্ভর করে algorithm আর training ডেটার ক্রমের ওপর; scikit-learn-এর documentation-ও এ নিয়ে সতর্ক করে। আমাদের ডেটায় ঝুড়ি আর দিন ভগ্নাংশ, তাই এমন টাই কার্যত হয় না।

নিচের ব্লক ডেটা বানায়, নিজের knn_predict লেখে, তারপর একই ডেটায় scikit-learn-এর KNeighborsClassifier চালিয়ে prediction মেলায়। algorithm="kd_tree" দেওয়া হয়েছে কারণ default algorithm ব্রাউজারের Python-এ একটি অপ্রাসঙ্গিক deprecation warning ছাপে; ফল একই। এই ব্লক আর পরের দুটি একই namespace ভাগ করে (data-shared); পরের কোনো ব্লক আগে চালালে এটি আপনা থেকে আগে চলে।

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

rng = np.random.default_rng(42)
n = 600                                   # কাল্পনিক নতুন গ্রাহক
orders = rng.poisson(2.5, n)              # প্রথম মাসের অর্ডার
basket = rng.normal(1200, 400, n).clip(200)   # গড় ঝুড়ি, টাকা
days = rng.uniform(1, 7, n)               # গড় ডেলিভারি দিন
logit = 1.0 * (orders - 2.5) - 0.9 * (days - 4) + 0.001 * (basket - 1200)
y = (rng.random(n) < 1 / (1 + np.exp(-logit))).astype(int)   # 1 = আবার কিনবেন
X = np.column_stack([orders, basket, days])

X_tv, X_te, y_tv, y_te = train_test_split(X, y, test_size=0.2, stratify=y, random_state=42)
X_tr, X_va, y_tr, y_va = train_test_split(X_tv, y_tv, test_size=0.25, stratify=y_tv, random_state=42)
sc = StandardScaler().fit(X_tr)           # শুধু train থেকে μ আর σ
Z_tr, Z_va, Z_te = sc.transform(X_tr), sc.transform(X_va), sc.transform(X_te)

def knn_predict(Ztr, ytr, Zq, k):
    D = (Zq**2).sum(1)[:, None] + (Ztr**2).sum(1)[None, :] - 2 * Zq @ Ztr.T
    D = np.maximum(D, 0)                  # ক্ষুদ্র ঋণাত্মক কেটে দেওয়া
    idx = np.argpartition(D, k - 1, axis=1)[:, :k]   # k-টি সবচেয়ে কাছের (ক্রমহীন)
    votes = ytr[idx]                      # shape (m, k)
    return np.array([np.bincount(v, minlength=2).argmax() for v in votes])

print("train/val/test:", len(y_tr), len(y_va), len(y_te), "| আবার কেনেন:", y.mean().round(3))
for k in (1, 5, 15):
    p = knn_predict(Z_tr, y_tr, Z_te, k)
    sk = KNeighborsClassifier(n_neighbors=k, algorithm="kd_tree").fit(Z_tr, y_tr).predict(Z_te)
    print(f"k={k:2d} test accuracy {np.mean(p == y_te):.3f} | scikit-learn-এর সঙ্গে হুবহু মিল: {np.array_equal(p, sk)}")
raw = knn_predict(X_tr, y_tr, X_te, 15)
print("scaling ছাড়া k=15:", np.mean(raw == y_te).round(3))
print("সবসময় বেশি-শ্রেণি বললে:", max(y_te.mean(), 1 - y_te.mean()).round(3))

train/val/test: 360 120 120 | আবার কেনেন: 0.527
k= 1 test accuracy 0.717 | scikit-learn-এর সঙ্গে হুবহু মিল: True
k= 5 test accuracy 0.733 | scikit-learn-এর সঙ্গে হুবহু মিল: True
k=15 test accuracy 0.750 | scikit-learn-এর সঙ্গে হুবহু মিল: True
scaling ছাড়া k=15: 0.525
সবসময় বেশি-শ্রেণি বললে: 0.525

“Training” কোথায় হলো? কোথাও না: knn_predict প্রতিবার পুরো Z_tr আর y_tr হাতে নেয়। scikit-learn-এর fit-ও মূলত ডেটা জমা রাখে, সঙ্গে kd_tree-র ক্ষেত্রে একটি খোঁজার গাছ বানায় (অংশ ৯)।

৫ · k বাছাই — ছোট k কোলাহলপূর্ণ, বড় k মসৃণ

k = ১ মানে প্রতিটি training বিন্দুর চারপাশে তার নিজের একটি ছোট এলাকা। একজন “উল্টো” গ্রাহক (বেশি অর্ডার দিয়েও আর কেনেননি) তাঁর চারপাশে একটি ভুলের দ্বীপ বানান। Training ডেটায় k = ১-এর accuracy প্রায় সবসময় ১০০% (প্রতিটি বিন্দুর সবচেয়ে কাছের প্রতিবেশী সে নিজেই), যা overfitting-এর পরিষ্কার উদাহরণ। k বাড়লে ভোট অনেকজনের ওপর গড় হয়, সীমারেখা মসৃণ হয়; কিন্তু k খুব বড় হলে, যেমন k = n, সবার জন্য একই উত্তর: সবচেয়ে বড় শ্রেণি। এই টানাপোড়েনই bias আর variance-এর বিনিময়, যার পূর্ণ আলোচনা পর্ব ৬১ (Overfitting, bias আর variance)-এ।

দুই শ্রেণির মাঝের সীমারেখাকে বলে decision boundary. নিচের ব্লক দুটি কাজ করে: (১) বিজোড় k = ১, ৩, …, ৬১-এ validation accuracy মাপে, তিনটি feature দিয়ে; (২) শুধু দুটি feature (অর্ডার আর দিন, scaled) দিয়ে k = ১, ৫, ২৫-এর decision boundary আঁকে, কারণ তিন মাত্রার সীমারেখা কাগজে আঁকা যায় না। ছবিতে নীল = আবার কেনেন (১), লাল = কেনেন না (০)।

import matplotlib.pyplot as plt

ks = list(range(1, 62, 2))                       # বিজোড় k: দুই শ্রেণিতে ভোট টাই হয় না
val = [np.mean(knn_predict(Z_tr, y_tr, Z_va, k) == y_va) for k in ks]
best = ks[int(np.argmax(val))]
print("validation-এ সেরা k:", best, "| accuracy:", round(max(val), 3))
print("k=1:", round(val[0], 3), "| k=5:", round(val[2], 3), "| k=61:", round(val[-1], 3))
print("এই k-তে test accuracy (একবারই):", np.mean(knn_predict(Z_tr, y_tr, Z_te, best) == y_te).round(3))

A = Z_tr[:, [0, 2]]                              # ছবির জন্য দুই feature: অর্ডার আর দিন
g0, g1 = np.meshgrid(np.linspace(A[:, 0].min() - 0.3, A[:, 0].max() + 0.3, 120),
                     np.linspace(A[:, 1].min() - 0.3, A[:, 1].max() + 0.3, 120))
grid = np.column_stack([g0.ravel(), g1.ravel()])
fig, axs = plt.subplots(2, 2, figsize=(8, 6.8))
for ax, k in zip(axs.flat, (1, 5, 25)):
    Zg = knn_predict(A, y_tr, grid, k).reshape(g0.shape)
    ax.contourf(g0, g1, Zg, levels=[-0.5, 0.5, 1.5], colors=["#f8c4b4", "#b9dcf2"])
    ax.scatter(A[:, 0], A[:, 1], c=y_tr, cmap="coolwarm_r", s=9, edgecolors="k", linewidths=0.2)
    ax.set_title(f"k = {k}")
    ax.set_xlabel("orders in first month (scaled)")
    ax.set_ylabel("delivery days (scaled)")
ax = axs[1, 1]
ax.plot(ks, val, marker="o", ms=3)
ax.axvline(best, ls="--", c="gray")
ax.set_title("validation accuracy vs k (3 features)")
ax.set_xlabel("k"); ax.set_ylabel("accuracy")
fig.subplots_adjust(hspace=0.5, wspace=0.35)
plt.show()

validation-এ সেরা k: 25 | accuracy: 0.817
k=1: 0.725 | k=5: 0.758 | k=61: 0.808
এই k-তে test accuracy (একবারই): 0.758

৬ · Scaling কেন বাধ্যতামূলক — টাকা বনাম দিন

পর্ব ৩৩-এ দেখেছেন, কাঁচা সংখ্যায় যে কলামের পরিসর বড়, দূরত্ব প্রায় পুরোটাই সে ঠিক করে। k-NN-এ এর মানে, ভোটও সে ঠিক করে। অংশ ২-এর সাতজন গ্রাহকের সঙ্গে এবার তৃতীয় feature যোগ করি, গড় ঝুড়ি (টাকা): জনি ৮৮০, শিলা ২৬০০, রুমি ১১০০, মিতু ৮৭০, তানহা ১১৫০, পলাশ ১৯০০, সাকিব ৯৫০; নতুন গ্রাহক q-এর ঝুড়ি ৯০০ টাকা। k = ৩-এ ভোট কী হয়?

এই হিসাবের যন্ত্র হলো standardization (feature scaling-এর সবচেয়ে প্রচলিত রূপ), scikit-learn-এ StandardScaler. নিয়মটি অংশ ৪-এর কোডেই আছে: StandardScaler().fit(X_tr), তারপর একই μ আর σ দিয়ে train, validation আর test সবকে transform. পুরো ডেটায় fit করলে test ডেটার গড় আর ছড়ানো আগেই model-এ ঢুকে যায়, একটি ছোট কিন্তু বাস্তব data leakage. scikit-learn 1.8.0-এর StandardScaler σ হিসাব করে n দিয়ে ভাগ করে (ddof = ০); উপরের হাতের হিসাবেও তাই।

দ্বিতীয় যাচাই: wine ডেটাসেট

কাল্পনিক ডেটায় নিজের কোড মেলানো এক কথা; একটি পরিচিত আসল ডেটাসেটে আরেক। scikit-learn-এর সঙ্গে আসা load_wine (UCI Machine Learning Repository-র wine ডেটা; ইতালির একই অঞ্চলের তিন জাতের আঙুর থেকে তৈরি ১৭৮টি wine-এর ১৩টি রাসায়নিক মাপ) দিয়ে ডেস্কটপে একই knn_predict চালানো হয়েছে। কলামগুলোর পরিসর খুব আলাদা, তাই scaling-এর প্রভাব এখানে আরও স্পষ্ট।

~/bazarghar-ai$ python wine_check.py
scikit-learn 1.8.0 | wine: (178, 13) শ্রেণি: [59 71 48]
  proline                278.00 থেকে 1680.00
  nonflavanoid_phenols     0.13 থেকে    0.66
কাঁচা  k= 1 accuracy 0.704 | kd_tree-এর সঙ্গে মিল True
কাঁচা  k= 5 accuracy 0.722 | kd_tree-এর সঙ্গে মিল True
কাঁচা  k=15 accuracy 0.722 | kd_tree-এর সঙ্গে মিল True
scaled k= 1 accuracy 0.963 | kd_tree-এর সঙ্গে মিল True
scaled k= 5 accuracy 0.944 | kd_tree-এর সঙ্গে মিল True
scaled k=15 accuracy 0.981 | kd_tree-এর সঙ্গে মিল True

সত্যিকারের run (ডেস্কটপ, লেখার সময়ে Python 3.14.4, NumPy 2.5.4, scikit-learn 1.8.0; ৭০:৩০ stratified ভাগ, random_state=42, test-এ ৫৪টি wine). proline কলামের মান কয়েকশো থেকে দেড় হাজারের বেশি, nonflavanoid_phenols-এর ১-এর নিচে; কাঁচা দূরত্বে প্রথমটিই প্রায় সব বলে, তাই accuracy ০.৭ এর কাছে। Scaling-এর পর ০.৯৪–০.৯৮. ছয় ক্ষেত্রেই নিজের লেখা k-NN আর kd_tree হুবহু এক। ৫৪টি নমুনায় একটি ভুল মানে ০.০১৯-এর পার্থক্য, তাই k = ৫ আর ১৫-এর তফাতকে গুরুত্ব দেবেন না।

৭ · Distance-weighted voting — কাছের প্রতিবেশীর কথা বেশি ভারী

অংশ ২-এর k = ৫-এ জনি আর মিতু, যাঁরা q থেকে ৩ একক দূরে, ১ একক দূরের রুমির সমান একটি করে ভোট পেয়েছেন। স্বাভাবিক বুদ্ধি বলে, কাছের প্রতিবেশীর মতামত বেশি দামি। Distance-weighted voting-এ প্রতিটি প্রতিবেশীর ভোটের ওজন w = 1/d (কখনো 1/d²); প্রতিটি শ্রেণির ওজন যোগ করে বড়টি জেতে। ধারণাটি পরিচিত হয় S. A. Dudani-র ১৯৭৬ সালের একটি প্রবন্ধে, যদিও তাঁর প্রস্তাবিত ওজনের সূত্র একটু আলাদা ছিল।

scikit-learn-এ KNeighborsClassifier(weights="distance") ঠিক w = 1/d ব্যবহার করে। একটি বিশেষ ক্ষেত্র: query কোনো training বিন্দুর সঙ্গে হুবহু মিলে গেলে d = ০, আর 1/0 অসীম। scikit-learn তখন শূন্য দূরত্বের বিন্দুগুলোকেই সব ওজন দেয়; নিজের কোডে এই ক্ষেত্র আলাদা করে সামলাতে হয় (অনুশীলন ২)। Weighted voting k-র পছন্দকে একটু কম স্পর্শকাতর করে, কারণ দূরের অতিরিক্ত প্রতিবেশীর প্রভাব কম; তবে scaling-এর প্রয়োজন একটুও কমায় না, কারণ d নিজেই scaling-নির্ভর।

৮ · k-NN regression আর অপ্রাসঙ্গিক feature-এর ক্ষতি

লক্ষ্য যদি শ্রেণি না হয়ে একটি সংখ্যা হয়, যেমন “এই অর্ডার কত দিনে পৌঁছাবে”, তাহলে ভোটের বদলে k প্রতিবেশীর মানের গড় নিন: ŷ = (১/k) ∑ y_i, যেখানে ŷ (ওয়াই-হ্যাট) হলো অনুমান আর যোগফল k প্রতিবেশীর ওপর। এটিই k-NN regression. হাতের উদাহরণ: গুদাম থেকে ৮ কিলোমিটার দূরের নতুন অর্ডারের তিনটি সবচেয়ে কাছের পুরোনো অর্ডার ২.০, ২.৪ আর ৩.১ দিনে পৌঁছেছিল; অনুমান (২.০ + ২.৪ + ৩.১)/৩ = ২.৫ দিন। Weighted রূপে গড়ের বদলে ∑w_iy_i / ∑w_i.

নিচের ব্লকের দ্বিতীয় অংশ ১২০টি কাল্পনিক অর্ডারে (দূরত্ব ০.৫–২৫ km; সম্পর্ক: দিন ≈ ১ + ০.২ × km, সঙ্গে কোলাহল) k = ১ আর ১০-এর regression রেখা আঁকে, আর ৪০টি test অর্ডারে mean absolute error (MAE, গড় পরম ভুল) মাপে। প্রথম অংশ আরেকটি প্রশ্নের উত্তর দেয়: বাজারঘরের তিনটি অর্থবহ feature-এর সঙ্গে যদি অর্থহীন কলাম যোগ হয় (যেমন গ্রাহক আইডির শেষ অঙ্ক, অ্যাপ খোলার এলোমেলো সময়), তাহলে কী হয়? এখানে সেই কলামগুলো এলোমেলো normal সংখ্যা, একটি একটি করে বাড়ানো, ৫টি seed-এর গড়।

import matplotlib.pyplot as plt

# (ক) অর্থহীন noise feature যোগ, k = 25, ৫টি seed-এর গড়
for m in (0, 1, 2, 4, 8, 16, 32):
    accs = []
    for s in range(5):
        r = np.random.default_rng(s)
        Ntr, Nva = r.normal(size=(len(y_tr), m)), r.normal(size=(len(y_va), m))
        p = knn_predict(np.hstack([Z_tr, Ntr]), y_tr, np.hstack([Z_va, Nva]), 25)
        accs.append(np.mean(p == y_va))
    print(f"noise feature {m:2d}টি → validation accuracy {np.mean(accs):.3f}")

# (খ) k-NN regression: দূরত্ব (km) থেকে ডেলিভারি দিন
r = np.random.default_rng(42)
km = r.uniform(0.5, 25, 120)
dd = (1 + 0.2 * km + r.normal(0, 0.6, 120)).clip(0.5)
km_tr, dd_tr, km_te, dd_te = km[:80], dd[:80], km[80:], dd[80:]
def knn_reg(xtr, ytr, xq, k):
    D = np.abs(xq[:, None] - xtr[None, :])          # 1 মাত্রায় দূরত্ব
    idx = np.argpartition(D, k - 1, axis=1)[:, :k]
    return ytr[idx].mean(axis=1)                    # ভোট নয়, গড়
for k in (1, 10):
    mae = np.mean(np.abs(knn_reg(km_tr, dd_tr, km_te, k) - dd_te))
    print(f"k={k:2d}: test MAE {mae:.2f} দিন")
print(f"সবসময় train-এর গড় বললে: MAE {np.mean(np.abs(dd_tr.mean() - dd_te)):.2f} দিন")

xs = np.linspace(0.5, 25, 400)
fig, ax = plt.subplots(figsize=(6, 3.8))
ax.scatter(km_tr, dd_tr, s=12, c="gray", label="training orders")
for k, c in ((1, "#d62728"), (10, "#1f77b4")):
    ax.plot(xs, knn_reg(km_tr, dd_tr, xs, k), c=c, label=f"k-NN, k = {k}")
ax.set_xlabel("distance from warehouse (km)"); ax.set_ylabel("delivery days")
ax.set_title("k-NN regression: mean of the k nearest"); ax.legend()
fig.subplots_adjust(bottom=0.16)
plt.show()

noise feature  0টি → validation accuracy 0.817
noise feature  1টি → validation accuracy 0.800
noise feature  2টি → validation accuracy 0.810
noise feature  4টি → validation accuracy 0.765
noise feature  8টি → validation accuracy 0.743
noise feature 16টি → validation accuracy 0.762
noise feature 32টি → validation accuracy 0.685
k= 1: test MAE 0.75 দিন
k=10: test MAE 0.52 দিন
সবসময় train-এর গড় বললে: MAE 1.22 দিন

৯ · খরচ, গতি আর শক্তি-দুর্বলতা

Training-এ খরচ প্রায় শূন্য, তাই সব খরচ prediction-এ। সরাসরি খোঁজায় (brute force) একটি query-র জন্য n টি training বিন্দুর প্রতিটিতে d টি ঘরের হিসাব: O(n·d) সময় (time complexity), সঙ্গে k-টি বাছতে গড়ে O(n). m টি query-তে O(m·n·d). মেমরিতে পুরো training ডেটা রাখতে হয়: n × d × ৮ বাইট (float64). ১০ লাখ গ্রাহক আর ১০০টি feature হলে শুধু ডেটাই প্রায় ৮০০ MB, আর প্রতিটি নতুন গ্রাহকের জন্য ১০ কোটি গুণ-যোগ। তুলনায় linear regression-এর model মাত্র d + ১টি সংখ্যা।

গতি বাড়ানোর তিনটি পরিচিত পথ, এখানে শুধু ধারণা হিসেবে:

• KD-tree (Jon Bentley, ১৯৭৫): জায়গাটিকে বারবার একটি করে অক্ষ ধরে দুই ভাগে কাটা একটি binary গাছ। খোঁজার সময় যে ভাগ নিশ্চিতভাবে দূরে, তা পুরো বাদ। কম মাত্রায় খুব দ্রুত; মাত্রা বাড়লে বাদ দেওয়ার সুযোগ কমে।
• Ball tree: অক্ষের বদলে বিন্দুগুলোকে নেস্টেড “বল”-এ (কেন্দ্র আর ব্যাসার্ধ) ভাগ করে; যেকোনো metric দূরত্বে চলে, কিছু ডেটায় KD-tree-র চেয়ে মাঝারি মাত্রায় ভালো।
• Approximate nearest neighbour (ANN): হুবহু সবচেয়ে কাছের বদলে “প্রায় সবচেয়ে কাছের” দ্রুত দেয়, যেমন graph-ভিত্তিক HNSW বা ভেক্টর ভাগ করে খোঁজা। Embedding আর vector search-এ এটিই চলে (পর্ব ৩৩-এর শেষ অংশ, আর DBMS কোর্সের vector database পর্ব)।

মাত্রা কীভাবে গাছের সুবিধা খেয়ে ফেলে, তা ডেস্কটপে একটি ছোট পরীক্ষায় দেখা গেছে: ১ লাখ এলোমেলো বিন্দু, ১০০০টি query, k = ৫, scikit-learn-এর NearestNeighbors.

~/bazarghar-ai$ python speed.py
d= 3 brute     fit     0.5 ms | 1000 query    91.1 ms
d= 3 kd_tree   fit    81.1 ms | 1000 query     3.5 ms
d= 3 ball_tree fit    47.6 ms | 1000 query    35.9 ms
d=50 brute     fit     2.7 ms | 1000 query    88.8 ms
d=50 kd_tree   fit   952.2 ms | 1000 query 11109.1 ms
d=50 ball_tree fit   539.7 ms | 1000 query 10089.9 ms

সত্যিকারের run (ডেস্কটপ, লেখার সময়ে Python 3.14.4, scikit-learn 1.8.0; একবারের মাপ, অন্য যন্ত্রে সংখ্যা আলাদা হবে)। ৩ মাত্রায় KD-tree brute force-এর চেয়ে প্রায় ২৫ গুণ দ্রুত, গাছ বানানোর খরচ (৮১ ms) সত্ত্বেও। ৫০ মাত্রার এলোমেলো ডেটায় চিত্র উল্টো: দুই গাছই brute force-এর চেয়ে শতগুণের বেশি ধীর, কারণ প্রায় কোনো শাখাই বাদ দেওয়া যায় না, আর গাছ ঘোরার বাড়তি খরচ যোগ হয়। এটি পর্ব ৩৩-এর curse of dimensionality-র বাস্তব চেহারা। মনে রাখবেন, ডেটা পুরোপুরি এলোমেলো; গঠনযুক্ত বাস্তব ডেটায় গাছ এতটা খারাপ না-ও হতে পারে। scikit-learn-এর default algorithm="auto" ডেটা দেখে এদের মধ্যে বাছে।

১০ · AI-এর যুগে — AI assistant-এর লেখা k-NN কোড যাচাই

“k-NN classifier লিখে দাও” বললে AI assistant দ্রুত কাজ চলার মতো কোড দেয়, আর সেটি একটি accuracy-ও ছাপে। কিন্তু k-NN-এ ভুলগুলো চুপচাপ থাকে, কারণ ভুল কোডও একটি সংখ্যা দেয়।

AI-এর লেখা k-NN হাতে পেলে — যাচাইয়ের চেকলিস্ট

• ভাগ আগে, scaler-এর fit শুধু train-এ; test-এর কোনো তথ্য μ, σ বা k বাছাইয়ে ঢোকেনি
• Distance matrix-এর shape আর কয়েকটি ঘর হাতে বা broadcasting দিয়ে মিলিয়েছি; nan বা ঋণাত্মক নেই
• Accuracy-র পাশে baseline, n আর কয়েকটি seed বা fold-এর ছড়ানো আছে
• নিজের কোড আর scikit-learn-এর prediction হুবহু মিলিয়েছি, অন্তত একটি পরিচিত ডেটাসেটে
• কোড নিজে চালিয়েছি, সব warning পড়েছি, parameter-এর নাম নিজের version-এর docs-এ দেখেছি
• কোনো আসল গ্রাহকের ব্যক্তিগত তথ্য AI-তে পেস্ট করিনি