একটি k-নিয়ারেস্ট-নেইবর অ্যালগরিদম হল একটি ক্লাসিফিকেশন পদ্ধতি যা ক্লাস মেম্বারশিপ (Y) এবং প্রিডিক্টর X1, X2,…. Xn এর মধ্যে সম্পর্কের স্ট্রাকচার সম্পর্কে কোনো ধারণা তৈরি করে না।
এটি একটি ননপ্যারামেট্রিক পদ্ধতি কারণ এতে কোনো প্রিটেন্ডেড ফাংশন ফর্মে প্যারামিটার এস্টিমেশন নেই, লিনিয়ার রিগ্রেশনে প্রিটেন্ডেড লিনিয়ার ফর্মের মত। এই পদ্ধতি ডেটাসেটের ডেটার প্রিডিক্টর ভ্যালুগুলোর সিমিলারিটি থেকে ইনফরমেশন ড্র করে।
k-NN কনসেপ্ট
k-নিয়ারেস্ট-নেইবর মেথডের কনসেপ্ট হল ট্রেনিং ডেটাসেটে k রেকর্ড সনাক্ত করা যা নতুন ডেটার সাথে সবচেয়ে সাদৃশ্যপূর্ণ যা ক্লাসিফাই করতে হবে। এই সাদৃশ্যপূর্ণ (নেইবরিং) রেকর্ডগুলো ব্যবহার করা হয় নতুন রেকর্ডকে একটি ক্লাসে অ্যাসাইন করতে, নতুন ডেটাকে এই নেইবরদের মধ্যে প্রबल ক্লাসে অ্যাসাইন করে। এটি নতুন রেকর্ডের প্রিডিক্টর ভ্যালুগুলোকে X1, X2,…. Xn হিসেবে ইন্ডিকেট করে।
ডিস্ট্যান্স মেজারমেন্ট
একটি কেন্দ্রীয় প্রশ্ন হল ডেটার প্রিডিক্টর ভ্যালুগুলোর ওপর ভিত্তি করে ডেটা এর মধ্যে দূরত্ব কীভাবে ক্যালকুলেট করা যায়। বিখ্যাত দূরত্বের মাপ হল ইউক্লিডিয়ান দূরত্ব। দুটি রেকর্ড (X1, X2,…. Xn) এবং (U1, U2,…. Un) এর মধ্যে ইউক্লিডিয়ান দূরত্ব হল:
$$\mathrm{\sqrt{(X_1-U_1)^2+(X_2-U_2)^2+...+(X_n-U_n)^2}}$$
k-NN অ্যালগরিদম বেশ কিছু ডিস্ট্যান্স কম্পিউটেশনের ওপর নির্ভর করে (প্রতিটি প্রেডিক্ট করার ডেটা এবং ট্রেনিং সেটের প্রতিটি ডেটার মধ্যে), এবং সেজন্য ইউক্লিডিয়ান দূরত্ব, যা কম্পিউটেশনালি ইনএক্সপেনসিভ, k-NN-এ সবচেয়ে জনপ্রিয়।
বিভিন্ন প্রিডিক্টরদের যে স্কেলগুলো থাকতে পারে সেগুলো ব্যালেন্স করার জন্য, অধিকাংশ কেসে প্রিডিক্টরগুলোকে স্ট্যান্ডার্ডাইজ করা উচিত ইউক্লিডিয়ান দূরত্ব ক্যালকুলেট করার আগে। মিন এবং স্ট্যান্ডার্ড ডেভিয়েশন যেগুলো নিউ ডেটা স্ট্যান্ডার্ডাইজ করতে পারে সেগুলো ট্রেনিং ডেটার, এবং নিউ ডেটা এতে জড়িত নয় ক্যালকুলেট করার সময়। ভ্যালিডেশন ডেটা, নিউ ডেটার মত, এছাড়া এই ক্যালকুলেশনে জড়িত নয়।
ক্লাস অ্যাসাইনমেন্ট রুল
প্রেডিক্ট করার ডেটা এবং বিদ্যমান রেকর্ডের মধ্যে ডিস্ট্যান্স ক্যালকুলেট করার পর, একটি রুল প্রয়োজন যা রেকর্ডকে একটি ক্লাস অ্যাসাইন করবে এর নেইবরদের ক্লাসের ওপর ভিত্তি করে।
সबচেয়ে সহজ কেস হল k = 1, যেখানে আমরা সবচেয়ে কাছের ডেটা খুঁজি (নিয়ারেস্ট নেইবর) এবং নতুন ডেটাকে একই ক্লাসে ক্লাসিফাই করি তার সবচেয়ে কাছের নেইবর হিসেবে।
এটি একটি অসাধারণ সত্য যে নিকটতম একটি নেইবর ব্যবহার করে রেকর্ড ক্লাসিফাই করার এই সহজ, אינ্টুইটিভ কনসেপ্ট শক্তিশালী হয় যখন আমাদের ট্রেনিং সেটে অনেক রেকর্ড থাকে। এটি বের হয়েছে যে ১-নিয়ারেস্ট নেইবর ডিজাইনের মিসক্লাসিফিকেশন এরর এমন একটি মিসক্লাসিফিকেশন রেট আছে যা প্রতিটি ক্লাসের প্রোব্যাবিলিটি ডেনসিটি ফাংশন সঠিকভাবে বুঝলে এররর চেয়ে দ্বিগুণ বেশি নয়।
