k همسایه نزدیک

روش k همسایه نزدیک

روش k همسایه نزدیک K Nearest Neighbors یا (KNN) یک روش یادگیری موردی ‌است و از جمله ساده‌ترین الگوریتم‌های یادگیری ماشین ^[2] می‌باشد که به روش K نزدیک ترین همسایه نیز معروف است. در این الگوریتم یک نمونه با رای اکثریت از همسایه‌هایش دسته‌بندی می‌شود و این نمونه در عمومی‌ترین کلاس مابین k همسایه نزدیک تعیین می‌شود. K یک مقدار مثبت صحیح و عموماً کوچک است. اگر k=1 باشد نمونه به سادگی در کلاس همسایگان نزدیکش تعیین می‌گردد. فرد بودن مقدار k مفید می‌باشد چون با این کار جلوی آراء برابر گرفته می‌شود.

روش k همسایه‌ نزدیک، برای بسیاری از روش‌ها کاربرد دارد، زیرا اثربخش، غیرپارامتریک و دارای پیاده‌سازی راحت می‌باشد. با این حال زمان دسته‌بندی‌اش طولانی است و یافتن مقدار k بهینه مشکل است. بهترین انتخاب از k، وابسته به داده‌ها می‌باشد به طور کلی مقدار بزرگ از k اثر نویز روی دسته‌بندی را کاهش می‌دهد، اما مرز مابین کلاس‌ها کمتر متمایز می‌شود.

شکل بالا مثالی از الگوریتم دسته‌بندی K نزدیک ترین همسایه، با استفاده از بردار ویژگی چندبعدی می‌باشد که مثلث‌ها کلاس اول و مربع‌ها کلاس دوم رانشان می‌دهند. دایره کوچک در داخل دوایر، نمونه تستی را نشان می‌دهد. حال اگر مقدار k=3 باشد (یعنی 3 همسایه‌ی نزدیک به نمونه) نمونه تستی متعلق به کلاس مثلث و اگر k=5 باشد نمونه متعلق به کلاس مربع می‌باشد.

مراحل آموزش K نزدیک ترین همسایه

مراحل آموزش k همسایه‌ نزدیک به صورت زیر می‌باشد، این الگوریتم یک نمونه تستی را بر اساس ‌k همسایه نزدیک دسته‌بندی می‌کند. نمونه‌های آموزشی به عنوان بردارهایی در فضای ویژگی چند بعدی مطرح می‌شوند. فضا به ناحیه‌هایی با نمونه‌های آموزشی پارتیشن‌بندی ‌می‌شود. یک نقطه در فضا به کلاسی ‌تعلق می‌یابد که بیشترین نقاط آموزشی متعلق به آن کلاس در داخل نزدیک‌ترین نمونه‌ی آموزشی به k در آن باشد.

معمولا فاصله‌ی اقلیدسی یا تشابه کوسینوسی در این روش استفاده می‌شود. در فاز دسته‌بندی K Nearest Neighbors، نمونه تستی به عنوان یک بردار در فضای ویژگی نمایش داده می‌شود و فاصله‌ی اقلیدسی یا تشابه کوسینوسی بردار تستی با کل بردارهای آموزشی محاسبه می‌شود و نزدیکترین نمونه‌ی آموزشی به k انتخاب می‌شود. البته راه‌های زیادی برای دسته‌بندی بردار تستی وجود دارد و بنابراین الگوریتم k همسایه‌ نزدیک کلاسیک، یک نمونه تستی را بر اساس بیشترین آراء از k همسایه‌ی نزدیکش ‌تعیین می‌کند. سه فاکتور مهم در این الگوریتم روش k همسایه‌ی نزدیک، به شرح زیر می‌باشد:

• معیار فاصله یا شباهت، برای پیداکردن k همسایه نزدیک استفاده می‌شود.
•  K تعداد همسایه‌های نزدیک است.
• قانون تصمیم‌گیری برای تعیین (شناسایی) یک کلاس برای سند تستی از k همسایه نزدیک می‌باشد.

الگوریتم

در الگوریتم k همسایه‌ نزدیک یک نمونه با رای اکثریت از همسایگان خود دسته بندی می شود، با این مورد به کلاس رایج ترین در میان K نزدیک ترین همسایگان خود را با استفاده از تابع فاصله (distance function) اندازه گیری شده است. اگر K = 1، سپس مورد به کلاس نزدیکترین همسایه اختصاص داده می شود.

همچنین لازم به ذکر است که تمام سه اندازه گیری فاصله تنها برای متغیرهای پیوسته معتبر است. در مورد متغیرهای گسسته باید از فاصله همینگ (Hamming distance) استفاده شود که مسئله استانداردسازي متغيرهاي عددی بين 0 و 1 را به وجود می آورد در حالی که مخلوطی از متغيرهای عددی و گسسته در مجموعه داده وجود دارد.

در روش k همسایه‌ نزدیک، انتخاب بهترین مقدار برای K بهتر است با اولین برسی داده ها انجام شود. به طور کلی، یک مقدار بزرگ K دقیق تر است زیرا نویز کلی را کاهش می دهد اما هیچ تضمینی برای اعتبار آن وجود ندارد. اعتبار سنجی متقاطع یکی دیگر از راه های به دست آوردن یک K خوب با استفاده از یک مجموعه داده مستقل برای اعتبار سنجی K می باشد. به لحاظ تجربه، K مطلوب برای بیشتر مجموعه داده ها بین 3 تا 10 است. این نتایج بسیار بهتر از 1NN تولید می کند.

مثال

داده های زیر مربوط به اعتبار بانکی را در نظر بگیرید. سن و وام دو متغیر عددی (پیش بینی کننده) هستند و پیش فرض هدف است.

اکنون می توانیم از مجموعه آموزشی برای طبقه بندی یک مورد ناشناخته (سن = 48 و وام = $ 142،000) با استفاده از فاصله اقلیدسی استفاده کنیم. اگر K = 1، نزدیک ترین همسایه آخرین مورد در مجموعه آموزش با Default = Y است.

با K = 3، دو Default = Y و یک Default = N از سه نزدیکترین همسایگان وجود دارد. پیش بینی برای مورد ناشناخته است دوباره Default = Y.

فاصله استاندارد

یکی از معایب عمده در محاسبه اندازه گیری فاصله از مجموعه آموزش در k همسایه‌ نزدیک، در مورد متغیرهایی است که دارای مقیاس اندازه گیری متفاوت هستند و یا ترکیبی از متغیرهای عددی و دسته ای وجود دارد. به عنوان مثال، اگر یک متغیر بر مبنای درآمد سالانه در دلار باشد، و دیگری براساس سن سالها است، درآمد تاثیر زیادی بر محاسبه فاصله دارد. یک راه حل این است که مجموعه آموزشی را به صورت زیر تنظیم کنید.

با استفاده از فاصله استاندارد شده در یک مجموعه آموزشی مشابه، نمونه ناشناخته یک همسایه متفاوت را باز می کند که نشانه خوبی از ثبات در K نزدیک ترین همسایه نیست.

مراجع

https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm ^[3]

https://www.saedsayad.com/k_nearest_neighbors.htm ^[4]