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

مدرس: مسعود کاویانی

MasoudKaviani.ir

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

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

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

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

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

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

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

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

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

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

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