نزدیک‌ترین همسایه KNN) ) ( (K Nearest Neighbor

روش K نزدیک‌ترین همسایه یک گروه شامل K رکورد از مجموعه رکورد‌های آموزشی که نزدیک‌ترین رکورد‌ها به رکورد آزمایشی باشند را انتخاب کرده و بر اساس برتری رده یا برچسب مربوط به آن‌ها در مورد دسته رکورد آزمایشی مزبور تصمیم‌گیری می‌نماید. به عبارت ساده‌تر این روش رده‌ای را انتخاب می‎‌کند که در همسایگی انتخاب شده بیشترین تعداد رکورد منتسب به آن دسته باشند. بنابراین رده‌ای که از همه رده‌ها بیشتر در بین K نزدیک‌ترین همسایه مشاهده شود، به عنوان رده رکورد جدید در نظر گرفته می‌شود. ایده اصلی روش KNN این است که اگر موجودی مثل اردک راه برود و مثل اردک quack quack کند، پس حتما یک اردک است.
استفاده از الگوریتمKNN   نیازمند تعیین سه موضوع می‌باشد:
- باید یک مجموعه رکورد داشته باشیم.
- یک معیار محاسبه شباهت نیز باید داشته باشیم.
- مقدار K نیز باید مشخص شود تا بتوان بر اساس آن عمل نمود. برای مسائل دسته بندی دودویی معمولا در نظر گرفتن مقادیر فرد برای K بهتر است. زیرا امکان پیروز شدن یکی از دو دسته را افزایش می‌دهد. برای مسائل رده‌بندی چند رده‌ای باید عددK را بزرگ‌تر از تعداد رده ها و نیز متفاوت با عدد تعداد رده‌ها از نظر زوج یا فرد بودن در نظر گرفت. یعنی اگر تعداد رده‌ها زوج باشدباید K نهایی را فرد در نظر گرفت و بالعکس.
در رده‌بندی‌های KNN برای دسته‌بندی کردن یک رکورد با دسته نا‌مشخص به صورت زیر عمل می‌شود:
- فاصله رکورد جدید از همه رکورد‌های آموزشی محاسبه می‌شود.
- نزدیک‌ترین همسایه‌ها مشخص می‌شوند.
- از برچسب دسته K نزدیک‌ترین همسایه، برای پیش‌بینی دسته رکورد جدید استفاده می‌شود. به
این صورت که بین K رکورد رأی‌گیری شده و دسته‌ای که بیش‌ترین تعداد دفعات دیده‌شدن را در بین این K رکورد داراست، به عنوان دسته رکورد جدید در نظر گرفته خواهد شد.
انتخاب مقدار K در این روش دسته‌بندی بسیار مهم و کلیدی است. اگر مقدار K خیلی کوچک انتخاب شود، الگوریتم به نویز حساس می‌شود. در واقع نویز‌ها نزدیک آن رکورد ممکن است ایجاد اشتباه کنند. اگر مقدار K خیلی بزرگ انتخاب شود، ممکن است در میان نزدیک‌ترین همسایه‌ها، رکورد‌هایی از دسته‌های دیگر نیز قرار بگیرند.
وقتی K عدد بزرگی انتخاب شود، منجر به خطای دسته‌بند در دسته‌بندی رکورد ورودی خواهد شد. یکی از ایده‌هایی که برای حل این مشکل ارائه شده، تعریف فاکتور وزن است. این فاکتور وزنی برابر d2/1 را در نظر می‌گیرد که مقدارd بیانگر فاصله هر رکورد تا رکورد ورودی می‌باشد. به این ترتیب فاصله‌ها برای الگوریتم اهمیت پیدا می‌کنند و این وزن‌دهی سبب می‌شود که به رکورد‌هایی که نزدیک‌تر به رکورد ورودی هستند اهمیت بیش‌تری داده شود.

مطالب مرتبط

شبکه‌های عصبی مصنوعی (Artificial Neural Networks )
ماشین بردار پشتیبان (Support Vector Machines )
الگوریتم مبتنی بر نظریه بیز ( (Bayes and Bayesian Networks
درخت تصمیم ((Decision Trees
  • تهران
  • 09350579640-09124635768
  • 01152218786
  • این آدرس ایمیل توسط spambots حفاظت می شود. برای دیدن شما نیاز به جاوا اسکریپت دارید

ارسال پیام

  Mail is not sent.   Your email has been sent.
Top