Core Algorithmsপড়তে ৭ মিনিট লাগবে

কে-নিয়ারেস্ট নেইবোরস বা প্রতিবেশীরা (K-Nearest Neighbours - KNN)

আপনার সবচেয়ে কাছের প্রতিবেশীদের জিজ্ঞাসা করুন এবং সংখ্যাগরিষ্ঠ বা মেজরিটির (majority) সাথে একমত হোন

training:O(1) — আক্ষরিক অর্থেই এটি শুধুমাত্র ডেটা স্টোর (stores) করে, আর কিছুই করে নাprediction:O(n * d) — স্টোর (stored) করা প্রতিটি পয়েন্টের সাথে তুলনা করেmemory:O(n * d) — সম্পূর্ণ ডেটাসেটটিকেই (dataset) মেমোরিতে (memory) রেখে দেয়

ধরা যাক, আপনি একটি নতুন শহরে এসেছেন এবং আপনি ভীষণ ক্ষুধার্ত। এখানকার কোনো রেস্তোরাঁই (restaurants) আপনার চেনা নেই, তাই আপনি আপনার সবচেয়ে কাছের বা নিয়ারেস্ট (nearest) ৫ জন প্রতিবেশীর (neighbours) দরজায় কড়া নাড়লেন এবং তাদের প্রত্যেককে জিজ্ঞাসা করলেন: "আচ্ছা, এই আশেপাশের সবচেয়ে ভালো রেস্তোরাঁ কোনটি?"

তাদের মধ্যে তিনজন বললো "মারিওস পিজা (Mario's Pizza)।" একজন বললো "থাই প্যালেস (Thai Palace)।" আর অন্যজন বললো "বার্গার বার্ন (Burger Barn)।" আপনি সবার উত্তরের এই সংখ্যাগরিষ্ঠতা বা মেজরিটির (majority) সাথেই একমত হলেন — অর্থাৎ আপনি মারিওস পিজাতেই (Mario's Pizza) যাওয়ার সিদ্ধান্ত নিলেন।

আর ঠিক এটিই হলো কে-এন-এন (KNN)। যখনই এর নতুন কোনো ডেটা পয়েন্টকে (data point) ক্লাসিফাই (classify) বা শ্রেণীভুক্ত করার প্রয়োজন পড়ে, তখন এটি এর ট্রেইনিং সেটের (training set) ওই K সংখ্যক সবচেয়ে কাছের বা ক্লোজেস্ট (closest) ডেটা পয়েন্টগুলোর দিকে লক্ষ্য করে এবং তাদের ভোট দিতে বলে। এরপর এই মেজরিটি ক্লাস (majority class) বা সংখ্যাগরিষ্ঠরাই মূলত জয়ী বা উইন (wins) হয়।

কোনো ট্রেইনিং (training) নেই? সত্যিই? (No training? Really?)

KNN-এর সবচেয়ে পাগলাটে বা চমৎকার বিষয়টি হলো: এখানে আসলে ট্রেইনিংয়ের (training) জন্য আলাদা কোনো ধাপ বা স্টেপ (step) নেই। এই মডেলটি মূলত এখানকার সম্পূর্ণ ডেটাসেটটিকে (dataset) মুখস্থ করে নেয় বা মনে রেখে দেয়। যখনই এখানে নতুন কোনো পয়েন্টের (point) আগমন ঘটে, এটি তখন স্টোর করে রাখা আগের প্রতিটি পয়েন্টের সাথে এর দূরত্ব (distance) মেপে দেখে, এরপর সবচেয়ে কাছের বা ক্লোজেস্ট K সংখ্যক (K closest) পয়েন্ট খুঁজে বের করে এবং তাদের থেকে ভোট বা মেজরিটি (vote) সংগ্রহ করে。

এই ব্যাপারটিই মূলত KNN-কে একটি "অলস শিক্ষার্থী বা চোর (lazy learner)" হিসেবে তৈরি করে — এটি আগে থেকে কোনো সমীকরণ বা ইকুয়েশন (equation) শেখে না কিংবা আগে থেকে কোনো গাছ বা ট্রি (tree) তৈরি করেও রাখে না। এটি মূলত ভবিষ্যদ্বাণী করার বা প্রেডিকশনের (prediction) সময়ই এর সম্পূর্ণ কাজগুলো করে থাকে।

আমরা কীভাবে এর এই "নৈকট্য বা closeness" পরিমাপ করবো? (How do we measure "closeness"?)

এ কাজের জন্য এখানকার সবচেয়ে সাধারণ উপায়টি হলো ইউক্লিডিয়ান ডিস্টেন্স (Euclidean distance) ব্যবহার করা — অর্থাৎ দুটি বিন্দুর বা পয়েন্টের মধ্যকার সরলরৈখিক বা সোজা দূরত্ব (straight-line distance)। ম্যাপের (map) ওপর থাকা বা প্লট করা দুটি বাড়ির কথা চিন্তা করে দেখুন। এদের মধ্যকার দূরত্ব বলতে মূলত এদের এক বাড়ি থেকে শুরু করে অন্য বাড়ি পর্যন্ত টানা একটি সরলরেখার বা লাইনের (line) দৈর্ঘ্যকেই বোঝায়।

যেকোনো দুইটি ফিচার (x1, y1) এবং (x2, y2)-এর জন্য:

দূরত্ব বা ডিস্টেন্স (distance) = sqrt((x2 - x1)^2 + (y2 - y1)^2)

এটি মূলত ডেটা সায়েন্সের (data science) পোশাকে সেজে থাকা সেই বিখ্যাত পিথাগোরাসের উপপাদ্য (Pythagorean theorem) ভিন্ন অন্য কিছুই নয়।

K বেছে নেওয়া: দ্য ম্যাজিক নাম্বার (Choosing K: the magic number)

এখানকার K-এর মানটাই মূলত সবকিছু বদলে দেয়:

K = 1: এটি শুধুমাত্র এর সবচেয়ে কাছের বা নিয়ারেস্ট (nearest) প্রতিবেশীকেই (neighbour) অনুকরণ বা কপি (copy) করে। এটি যেকোনো নয়েজের (noise) প্রতি খুবই সেনসিটিভ (sensitive) বা সংবেদনশীল হয়ে থাকে — এখানে শুধুমাত্র একটি অদ্ভুত বা উইয়ার্ড ডেটা পয়েন্টই (weird data point) এর পুরো হিসাব-নিকাশ পালটে ফেলতে পারে।
K = 3 বা 5: বেশিরভাগ সমস্যার সমাধান করার জন্য এটি একটি চমৎকার বা সুইট স্পট (sweet spot)। এটি এর প্রতিক্রিয়া বা রেসপন্স (responsive) ঠিক রেখে এখানকার যেকোনো নয়েজকে (noise) স্মুথ (Smooths) করে দেয়।
K = 100: এটি অনেক বেশি স্মুথ (smooth) প্রেডিকশন বা ভবিষ্যদ্বাণী দেয়, কিন্তু এর ফলে আপনি হয়তো এর লোকাল বা নির্দিষ্ট কোনো প্যাটার্ন (local patterns) মিস করতে পারেন। অনেকটা ১০০ জন প্রতিবেশীর (neighbours) কাছে কিছু জিজ্ঞাসা করার মতো ব্যাপার — এর ফলে আপনি হয়তো আপনার ব্লকের (block) বা আপনার এলাকার মানুষের মতামত না জেনে, পুরো শহরের একটি সাধারণ বা এভারেজ (average) মতামত জানতে পারবেন।

প্রো টিপ (Pro tip): যেকোনো বাইনারি ক্লাসিফিকেশনের (binary classification) জন্য সবসময় একটি বিজোড় বা অড (odd K) K ব্যবহার করবেন। ধরা যাক, আপনার K = 4 এবং আপনি ২-২ এ টাই (2-2 tie) করলেন... ব্যাপারটি তখন সত্যিই বেশ অদ্ভুত (awkward) হবে।

স্ক্র্যাচ বা একেবারে প্রথম থেকে তৈরি KNN (KNN from Scratch)

import math
from collections import Counter

def euclidean(a, b):
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))

def knn_predict(train_X, train_y, new_point, k=3):
    # প্রতিটি ট্রেইনিং পয়েন্টের (training point) দূরত্ব বা ডিস্টেন্স (distance) হিসেব (Calculate) করুন
    distances = []
    for i, x in enumerate(train_X):
        d = euclidean(x, new_point)
        distances.append((d, train_y[i]))
    
    # এদের দূরত্বের (distance) ওপর ভিত্তি করে ছোট থেকে বড় বা সর্ট (Sort) করুন এবং K সংখ্যক সবচেয়ে কাছের পয়েন্টকে বা নিয়ারেস্টগুলোকে (nearest) বেছে নিন
    distances.sort()
    k_nearest = [label for _, label in distances[:k]]
    
    # সংখ্যাগরিষ্ঠ বা মেজরিটি ভোট (Majority vote)
    vote = Counter(k_nearest).most_common(1)[0][0]
    return vote

# ফলের ডেটা (Fruit data): [ওজন_গ্রাম, মিষ্টতা]
train_X = [[150, 7], [170, 8], [130, 3], [140, 2], [180, 9], [120, 4]]
train_y = ['apple', 'apple', 'lemon', 'lemon', 'apple', 'lemon']

mystery = [155, 6]
print(f"અজানা ফলটি হলো (Mystery fruit): {knn_predict(train_X, train_y, mystery, k=3)}")

Output

Mystery fruit: apple

Note: ফিচার স্কেলগুলো (feature scale) মূলত KNN-কে অনেক বেশি প্রভাবিত করতে পারে। যদি এখানকার একটি ফিচারের সীমা বা রেঞ্জ 0-1000 (যেমন: বেতন বা salary) হয় এবং অন্য একটির রেঞ্জ 0-5 (যেমন: রেটিং বা rating) হয়, তবে এখানকার বেতন বা salary-ই মূলত এর দূরত্ব বা ডিস্টেন্স নির্ণয়ের (distance calculations) জায়গাটিতে ডমিনেট (dominate) বা প্রভাব বিস্তার করবে। তাই KNN ব্যবহার করার আগে সবসময় আপনার ফিচারগুলোকে (features) নরমালাইজ (normalize) করে নিন!