একটি k-নিয়ারেস্ট-নেইবর অ্যালগরিদম হল একটি ক্লাসিফিকেশন পদ্ধতি যা ক্লাস মেম্বারশিপ (Y) এবং প্রিডিক্টর X1, X2,…. Xn এর মধ্যে সম্পর্কের স্ট্রাকচার সম্পর্কে কোনো ধারণা তৈরি করে না।
এটি একটি ননপ্যারামেট্রিক পদ্ধতি কারণ এতে কোনো প্রিটেন্ডেড ফাংশন ফর্মে প্যারামিটার এস্টিমেশন নেই, লিনিয়ার রিগ্রেশনে প্রিটেন্ডেড লিনিয়ার ফর্মের মত। এই পদ্ধতি ডেটাসেটের ডেটার প্রিডিক্টর ভ্যালুগুলোর সিমিলারিটি থেকে ইনফরমেশন ড্র করে।
k-NN মেথডের সুবিধা
k-NN মেথডের সুবিধা হল তাদের ইন্টিগ্রিটি এবং প্যারামেট্রিক ধারণার প্রয়োজনীয়তা নেই। একটি বড় ট্রেনিং সেটের উপস্থিতিতে, এই পদ্ধতিগুলো খুব ভালো পারফর্ম করে, যখন প্রতিটি ক্লাস প্রিডিক্টর ভ্যালুর বিভিন্ন কম্বিনেশন দ্বারা ক্যারাক্টারাইজড হয়।
উদাহরণস্বরূপ, রিয়েল-এস্টেট ডেটাবেসে, সম্ভবত {হোম টাইপ, রুমের সংখ্যা, নেইবরহুড, আস্কিং প্রাইস, ইত্যাদি} এর বেশ কিছু সেট রয়েছে যা দ্রুত বিক্রি হওয়া হোম এবং যেগুলো মার্কেটে দীর্ঘকাল থাকে তাদের ক্যারাক্টারাইজ করে।
k-NN পদ্ধতির তিনটি कठিনতা
যদিও ট্রেনিং ডেটা থেকে প্যারামিটার এস্টিমেট করতে কোনো সময় লাগে না (যেমন প্যারামেট্রিক মডেলের ক্ষেত্রে রিগ্রেশন সহ), একটি বড় ট্রেনিং সেটে নিকটতম নেইবর খুঁজে বের করতে সময় লাগতে পারে বাধাদানক। এই কঠিনতা অতিক্রম করার জন্য একাধিক কনসেপ্ট ইমপ্লিমেন্ট করা হয়েছে। মূল কনসেপ্টগুলো নিম্নরূপ:
ডাইমেনশন রিডাকশন টেকনিক যেমন প্রিন্সিপাল কম্পোনেন্টস অ্যানালাইসিস ব্যবহার করে রিডিউসড ডাইমেনশনে কাজ করে ডিস্ট্যান্স কম্পিউট করার সময় কমানো যায়।
সফিস্টিকেটেড ডেটা স্ট্রাকচার যেমন সার্চ ট্রি ব্যবহার করে নিকটতম নেইবর আইডেন্টিফিকেশন স্পিড আপ করা যায়। এই পদ্ধতিটি প্রায়শই একটি "আলমোস্ট নিয়ারেস্ট" নেইবর দিয়ে সন্তোষ করে গতি বাড়াতে। একটি উদাহরণ হল বাকেটিং, যেখানে ডেটা বাকেটে কম্বাইন করা হয় যাতে প্রতিটি বাকেটের ভিতরের ডেটা একে অপরের কাছে থাকে।
ট্রেনিং সেটে 'লার্জ' হিসেবে অহরহ করতে জন্য প্রয়োজনীয় একাধিক ডেটা এক্সপোনেনশিয়ালি বৃদ্ধি পায় প্রিডিক্টর p-এর সংখ্যা বড়ার সাথে। এর কারণ হল নিকটতম নেইবরের এক্সপেক্টেড দূরত্ব খুব খারাপভাবে বড়ে p-এর সাথে যদি না ট্রেনিং সেটের পরিমাণ এক্সপোনেনশিয়ালি বড় হয় p-এর সাথে। এই ফিনোমেনাকে ডাইমেনশনালিটির অভিশাপ (curse of dimensionality) বলা হয়, একটি মৌলিক সমস্যা যা কিছু ক্লাসিফিকেশন, প্রেডিকশন এবং ক্লাস্টারিং পদ্ধতির জন্য প্রাসঙ্গিক।
k-NN হল একটি "লেজি লার্নার" (Lazy Learner) - সময়সাপেক্ষ কম্পিউটেশন প্রেডিকশনের সময় পর্যন্ত বিলম্বিত থাকে। প্রতিটি প্রেডিক্ট করার ডেটার জন্য, এর ডিস্ট্যান্স পুরো ট্রেনিং ডেটা সেট থেকে কেবল প্রেডিকশনের সময়ে ক্যালকুলেট করা হয়। এই বিহेवিয়র এই অ্যালগরিদমকে একসাথে অনেক ডেটা রিয়েল-টাইম প্রেডিকশনের জন্য ব্যবহার করা বাধা দেয়।
