الگوریتم K نزدیک ترین همسایه (KNN)  با پایتون

الگوریتم K نزدیک ترین همسایه (KNN) با پایتون

پایتون

تاریخ بروزرسانی : 15 اسفند 1398

حداقل ۱ امتیاز ضروری هست
برو به علاقه مندی ها
الگوریتم K نزدیک ترین همسایه (KNN)  با پایتون

توضیحات

KNN شاید ساده‌ترین الگوریتم در بحثِ طبقه بندیباشد. می‌خواهیم با یک مثال بسیار ساده شروع کنیم. فرض کنید شما یک فروشگاهِ مواد غذایی و دو دسته مشتری دارید، مشتریانِ دسته اول، کسانی هستند که بیشتر از ۱۰۰ هزار تومان در هر بار مراجعه از شما خریداری می‌کنند و دسته‌ی دوم مشتریانی هستند که در هر مراجعه معمولاً کمتر از ۱۰ هزار تومان خرید می‌کنند. شما که فروشنده‌ی با تجربه‌ای هستید، به سبب چند سالی که در این مغازه فعالیت دارید می‌دانید که مشتریان دسته‌ی اول خانم‌هایی هستند که سن بالای ۴۰ سال دارند و با اتومبیل به فروشگاه شما می‌آیند (مثلاً در مراجعه‌ی آن‌ها به این الگو دقت کرده‌اید). و دسته‌ی دوم، یعنی همان مشتریانی که کمتر از ۱۰ هزار تومان از شما خریداری می کنند. معمولاً آقایانی هستند که سن زیر ۲۵ سال دارند و بدون اتومبیل به فروشگاه می‌آیند. حال فرض کنید، یک مشتری جدید به فروشگاه آمده است. این شخص یک خانم ۴۵ ساله است که با اتومبیلِ خود به فروشگاه آمده. شما این مشتری جدید را در کدام دسته (با توجه به مشتریان قبلی) قرار میدهید؟ انتظار دارید که این شخص چقدر از شما خرید کند؟

قطعاً بدون فکر کردن، دسته‌ی اول را برای پاسخ به سوالِ بالا انتخاب می‌کنید. دلیل آن بسیار ساده است. این خانم ۴۵ ساله با اتومبیل، بسیار نزدیک‌تر به مشتریانِ دسته‌ی اول است تا مشتریانِ دسته‌ی دوم (دسته‌ی دوم، آقایانی بودند که زیر ۲۵ سال سن داشتند و بدون اتومبیل به فروشگاه می‌آمدند). واژه نزدیک‌تر، در واقع پایه‌ی عملیاتِ طبقه‌بندیِ K نزدیک‌ترین همسایه می‌باشد. در این الگوریتم، هر کدام از نمونه‌های جدید (مثلاً مشتری‌های جدید) با تمامی نمونه‌های قبلی مقایسه می‌شوند و به هر کدام از نمونه‌های قبلی که نزدیک‌تر باشند، به آن دسته از نمونه‌ها تعلق می گیرند. این دقیقاً همان کاری است که در مثال اول توسط فروشنده‌ی با تجربه‌ی فروشگاه مواد غذایی انجام شد.

حال که مثال اول را درک کردید، اجازه بدهید به یک مثال علمی‌تر بپردازیم. فرض کنید شما مدیریت یک بانک را بر عهده دارید و می‌خواهید از بینِ کسانی که درخواستِ وام کرده‌اند، آن هایی را انتخاب کنید که به احتمال زیاد می‌توانند وام خود را بازگردانند. فرض کنید برای این کار یک دیتاست (dataset) از مشتریانِ قبلیِ خود که وام گرفته‌اند را آماده کرده‌اید و به هر کدام از این مشتریانْ یک برچسبِ بله (یعنی توانسته‌اند وام را بازگردانند) و خیر (یعنی نتوانسته‌اند وام را بازگردانند) نسبت داده‌اید. توجه کنید که این‌ها مشتریانِ قبلی شما هستند که وضعیت برگرداندنِ وام توسط آن‌ها مشخص شده است. هر کدام از مشتری‌های شما هم ۲ ویژگی دارد. ویژگی اول: خانه از خود دارد یا خیر (۰ به معنیِ خانه نداشتن و ۱ به معنیِ داشتنِ خانه از خود است)؟ ویژگی دوم: چند سال است که مشتری بانک است (یک عدد بزرگتر از ۰)؟ هر کدام از این ویژگی‌ها برای تمامیِ مشتریان تکرار می شوند. نگاهی به شکل زیر بیندازید (یک دیتاست با ۶ نمونه و ۲ بٌعد و دارای برچسب):

الگوریتم k نزدیک‌ترین همسایه

همان‌طور که می‌بینید ما ۶ مشتری داریم که هر کدام ویژگی‌های خاصِ خود را دارند. مثلا مشتریِ اول خانه از خود دارد و ۳ سال است که مشتریِ بانک بوده و توانسته وام خود را پس بدهد. مشتریِ دوم خانه از خود ندارد، ۱ سال است مشتری بانک است و نتوانسته وام خود را پس دهد و به همین ترتیب برای بقیه مشتریان.

اجازه بدهید این مشتریان را بر روی یک نمودار رسم کنیم. توجه کنید که در اینجا دو ویژگی داریم، پس دو بُعد وجود دارد. ما محور افقی را خانه داشتن و محور عمودی را مدت زمان مشتریِ بانک بودن به سال، در نظر گرفتیم. هر کدام از نمونه‌ها، اگر توانسته باشند وام خود را پس دهند، با رنگ سبز و اگر نتوانسته باشند وام خود را پس دهند با رنگ قرمز مشخص شدند. پس اگر بخواهیم جدول بالا را بر روی نمودار رسم کنیم مانند شکل زیر است:

الگوریتم k نزدیک‌ترین همسایه

هر نقطه (#) بر روی این نمودار یک مشتری را نمایش می‌دهد. همان طور که می‌بینید یک تفکیک خوب بین مشتریانی که توانسته‌اند وام خود را پس دهند با کسانی که نتوانسته‌اند وام را پس دهند، وجود دارد. حال فرض کنید دو مشتریِ جدید با ویژگی‌هایی مطابق با جدول زیر متقاضیِ جدیدِ وام هستند و که می‌خواهیم تصمیم بگیریم به آن ها وام بدهیم یا خیر

چند سال مشتری بانک است خانه از خود دارد
۲/۵ ۱ new_1
۲ ۰ new_2

در الگوریتم KNN ابتدا بایستی فاصله‌ی هر نمونه‌ی جدید را با نمونه‌های گذشته مقایسه کنیم. اما این مقایسه چگونه باید باشد؟ فرض کنید در شکل بالا میخواهیم مشتری new_1 را با مشتری‌های قبلی مقایسه کنیم و فاصله‌ی این مشتری را با مشتریانِ دیگر به دست آوریم. برای این کار باید هر کدام از ویژگی‌های مختلفِ مشتریِ جدید را با همان ویژگی‌های موجود در یک مشتریِ قدیمی مقایسه کنیم (و از هم دیگر کم کنیم). سپس حاصلِ این کَم‌کردن‌ها را با یکدیگر جمع کنیم. بگذارید برای نمونه فاصله مشتری new_1 را با تمامی ۶ مشتری قبلی محاسبه کنیم:

الگوریتم knn

همان‌طور که مشاهده می‌کنید، هر کدام از ویژگی‌ها را برای هر مشتریان از هم کم کرده‌ایم. یعنی بُعد ۱ را برای مشتریِ جدید از بعد ۱ برای تک‌تکِ مشتریان قبلی کم کردیم و بُعد ۲ را نیز به همین ترتیب از بُعد ۲ برای تک‌تکِ مشتریان قبلی کم می‌کنیم. برای اینکه عددِ منفی به دست نیاید، قدر مطلق آن‌ها را حساب می کنیم و سپس تمامیِ این کم‌کردن‌ها را با هم جمع کرده ایم. در واقع بُعدهای مختلف را نظیر به نظیر با هم مقایسه کرده‌ایم. به این کار، یعنی به دست آوردن تفاضل بُعدهای نظیر به نظیر و سپس جمع آن‌ها، محاسبه فاصله‌ی منهتن میگویند که یکی از معیارهای فاصله برای داده‌های چند بعدی، مانند همین مثال ما است. معیارهای فاصله دیگر نیز وجود دارد. مثلاً معیار اقلیدسی و یا معیار مینکوفسکی که فرمول‌هایی شبیه به هم دارند و در درسی جدا به هر کدام از این معیارها خواهیم پرداخت.

همان طور که میبینید فاصله مشتری new_1 برای ۶ مشتری در شکل بالا محاسبه شده است. اگر بخواهیم ۳ مشتریِ نزدیک‌تر به این مشتریِ جدید، از مشتریان قبلی را انتخاب کنیم، مشتری‌های شماره ۱ و ۳ و ۵ هستند (که کمترین فاصله را در بین مشتریان دیگر به این مشتریِ جدید دارند) که دوتای آن ها توانسته‌اند وام را پس دهند و یکی از آن ها خیر. پس این مشتری نیز احتمالاً می‌تواند وام خود را پس دهد. این روش همان روش KNN است. در اینجا مقدار K برابر ۳ بود، یعنی ۳ مشتریِ نزدیک به مشتریِ جدید را انتخاب کرده‌ایم و برچسبِ اکثریت این ۳ مشتری را به عنوان برچسب برای مشتریِ جدید نیز درج می‌کنیم. مثلاً این‌جا چون برچسبِ اکثریت، بازگرداندنِ وام بود (۲ تا بلی در مقابل یک خیر) پس این مشتریِ جدید نیز به عنوانِ کسی که می‌تواند وام را برگرداند برچسب گذاری می‌شود. در واقع الگوریتمِ KNN با توجه به مشتریانِ قبلی،می‌تواند یک مشتریِ جدید را (که برچسب واقعی او را نمی‌داند) پیش‌بینی کند. اگر بخواهیم بر روی تصویر نیز نمایش دهیم، مشاهده می‌کنید که مشتری جدید new_1 به مشتری های قبلیِ ۱ و ۳ و ۵ نزدیک‌تر از بقیه بود.

الگوریتم knn

تمرین: فاصله مشتری new_2 را با ۶ مشتری قبلی مقایسه کنید. اگر K را برای الگوریتم KNN برابر ۳ قرار دهیم، آنگاه برچسب مشتری new_2 چه می شود؟ آیا این شخص می‌تواند وام خود را پس دهد یا خیر؟

همان طور که گفتیم الگوریتمِ KNN یکی از ساده‌ترین الگوریتم‌های داده‌کاوی و طبقه‌بندی است. این الگوریتم عملیات طبقه‌بندی را به صورت ساده انجام داده و نتایجِ قابل اطمینانی به عنوان پیش‌بینی برمی‌گرداند. البته در اینجا ما به صورت ساده به دو بعد از یک مثال اشاره کردیم (مشتری خانه دارد یا خیر و اینکه چند سال است که مشتری بانک بوده است). در مسائل دنیای واقعی ممکن است ابعادِ بسیار بیشتری وجود داشته باشد. این مسائل را دیگر نمی‌توان روی بردارهای عمودی و افقی به صورت ساده رسم کرد و در واقع مسئله‌هایی در فضای ۳ بعدی یا بیشتری می‌شوند. البته تجسم کردن آن از لحاظ فیزیکی قابل شکل‌سازی نیست ولی در ذهنِ خود به راحتی می‌توانید این فضاها را تجسم کنید. مثلاً به جای اینکه در این‌جا مشتری دو بُعد داشته باشد می‌تواند ۱۰ بعد داشته باشد که هر کدام یک ویژگیِ مشتری را نمایش می‌دهد.(برگرفته از سایت chistio.ir)

شبیه سازی با پایتون

در این شبیه سازی هدف استفاده گرافیک جهت آموزش knn می باشد. از زبان پایتون به این منظور استفاده شده است. برخی از نتایج در شکل های  زیر دیده می شود. جهت اطلاع بیشتر در رابطه با پروژه KNN صفحه تماس با ما مراجعه فرمائید.

قابلیت های شبیه سازی KNN

  • سرعت بالا در بارگزاری
  • رابط گرافیکی
  • تنظیم پارامترها به صورت دستی
  • رابط کاربری آسان
  • ویدئویی اموزش در صورت درخواست
  • پشتیبانی تیم هوش مصنوعی ایران

 

 

 

ویژگی ها

نسخه 2019
سیستم عامل ویندوز و لینوکس
فایل های موجود py
زبان انگلیسی
حجم فایل 50 کیلوبایت
پشتیبانی ندارد

نقد و بررسی‌ها

هیچ دیدگاهی برای این محصول نوشته نشده است.

اولین کسی باشید که دیدگاهی می نویسد “الگوریتم K نزدیک ترین همسایه (KNN) با پایتون”

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

مشخصات محصول
نوع فایل سورس کد
پسوند فایل py
حجم فایل 50 کیلوبایت
راهنما ندارد
تعداد فایل 2
رمز فایل IRAN-AI.IR
جزئیات بیشتر
  • اجرای آسان
  • آموزش ویدئویی در صورت درخواست
فایل ها
elyas

elyas

تاریخ عضویت :‌ شنبه, 19 بهمن 98

نماد های اعتماد

هوش مصنوعی ایران به استناد نماد های زیر ، دارای مجوز رسمی از مراجع زیر در جمهوری اسلامی ایران می باشد !

تمامی حقوق برای هوش مصنوعی ایران محفوظ است | طراحی شده با