وبلاگ
الگوریتم KNN چیست؟ آموزش K نزدیکترین همسایه با مثال و کاربردها
الگوریتم KNN یا K-Nearest Neighbors یکی از سادهترین و در عین حال کاربردیترین الگوریتمهای یادگیری ماشین است. این الگوریتم برای حل مسائل طبقهبندی (Classification) و رگرسیون (Regression) استفاده میشود و ایده اصلی آن بسیار ساده است: برای پیشبینی یک داده جدید، نزدیکترین نمونههای موجود در دادههای آموزشی را پیدا میکنیم و بر اساس آنها تصمیم میگیریم.
برای مثال، اگر بخواهیم مشخص کنیم یک مشتری جدید به کدام گروه رفتاری تعلق دارد، میتوانیم مشتریانی را که بیشترین شباهت را به او دارند پیدا کنیم و ببینیم بیشتر آنها در چه گروهی قرار گرفتهاند. همین ایده ساده، پایه الگوریتم KNN را تشکیل میدهد.
تعریف کوتاه: KNN یک الگوریتم یادگیری با ناظر است که برای پیشبینی یک نمونه جدید، K نمونه نزدیکتر به آن را در دادههای آموزشی پیدا میکند و بر اساس آنها کلاس یا مقدار خروجی را تعیین میکند.
سرفصل محتوا:
الگوریتم KNN چیست؟
KNN مخفف K-Nearest Neighbors به معنی «K نزدیکترین همسایه» است. این الگوریتم برخلاف بسیاری از مدلهای یادگیری ماشین، در مرحله آموزش یک مدل پیچیده و پارامتریک ایجاد نمیکند. در عوض، دادههای آموزشی را نگه میدارد و هنگام دریافت یک نمونه جدید، فاصله آن را با نمونههای موجود محاسبه میکند.
حرف K در نام الگوریتم نشاندهنده تعداد همسایههایی است که برای تصمیمگیری در نظر گرفته میشوند. اگر K برابر 3 باشد، سه نمونه نزدیکتر به داده جدید بررسی میشوند.
در یک مسئله طبقهبندی، معمولاً کلاسی که بیشترین رأی را میان این همسایهها داشته باشد، به عنوان کلاس پیشبینیشده انتخاب میشود. در یک مسئله رگرسیون نیز میتوان میانگین مقدار هدف همسایههای انتخابشده را به عنوان پیشبینی در نظر گرفت.
KNN چگونه کار میکند؟
برای درک KNN یک فضای دوبعدی را تصور کنید که در آن تعدادی نقطه از دو کلاس مختلف قرار گرفتهاند. حال یک نقطه جدید وارد این فضا میشود و نمیدانیم به کدام کلاس تعلق دارد.
KNN ابتدا فاصله نقطه جدید با نمونههای موجود را محاسبه میکند. سپس K نمونهای را که کمترین فاصله را دارند انتخاب میکند. اگر بیشتر این همسایهها متعلق به یک کلاس باشند، نمونه جدید نیز به همان کلاس اختصاص داده میشود.
فرض کنید K برابر 3 باشد و سه همسایه نزدیک یک نقطه جدید به ترتیب شامل دو نمونه از کلاس A و یک نمونه از کلاس B باشند. در این حالت، KNN کلاس A را برای نمونه جدید پیشبینی میکند.
مراحل الگوریتم KNN
فرایند کلی KNN را میتوان در چند مرحله خلاصه کرد:
- انتخاب مقدار K: تعداد همسایههایی که قرار است در پیشبینی استفاده شوند مشخص میشود.
- محاسبه فاصله: فاصله نمونه جدید با نمونههای آموزشی محاسبه میشود.
- مرتبسازی همسایهها: نمونهها بر اساس فاصله از نزدیکترین تا دورترین مرتب میشوند.
- انتخاب K نمونه نزدیکتر: K نمونه اول انتخاب میشوند.
- تعیین خروجی: در Classification از رأی اکثریت و در Regression معمولاً از میانگین مقادیر همسایهها استفاده میشود.
فاصله در الگوریتم KNN چگونه محاسبه میشود؟
مفهوم «نزدیک بودن» در KNN به معیار فاصلهای که انتخاب میکنیم بستگی دارد. یکی از رایجترین معیارها فاصله اقلیدسی (Euclidean Distance) است.
برای دو نقطه در فضای دوبعدی، فاصله اقلیدسی به صورت زیر محاسبه میشود:
d = √((x₁ − x₂)² + (y₁ − y₂)²)
البته بسته به نوع داده میتوان از معیارهای دیگری مانند فاصله Manhattan، فاصله Chebyshev یا معیارهای مبتنی بر شباهت کسینوسی نیز استفاده کرد.
KNN برای Classification و Regression
KNN در Classification
یکی از رایجترین کاربردهای KNN، طبقهبندی است. در این حالت، دادههای آموزشی دارای برچسب هستند و الگوریتم تلاش میکند برچسب نمونه جدید را تعیین کند.
برای مثال، فرض کنید اطلاعات مشتریان یک فروشگاه در اختیار داریم و هر مشتری به یکی از دو گروه «خرید بالا» و «خرید پایین» تعلق دارد. برای یک مشتری جدید، KNN نزدیکترین مشتریان از نظر ویژگیهایی مانند تعداد خرید، مبلغ خرید و تعداد تعاملات را پیدا میکند و بر اساس رأی آنها گروه مشتری جدید را پیشبینی میکند.
KNN در Regression
KNN فقط برای Classification نیست و میتواند در مسائل رگرسیون نیز استفاده شود. در این حالت، خروجی یک مقدار عددی است.
برای مثال، اگر هدف پیشبینی قیمت یک خانه باشد، میتوان نزدیکترین خانهها را بر اساس ویژگیهایی مانند متراژ، تعداد اتاقها و موقعیت انتخاب کرد و از میانگین قیمت آنها برای تخمین قیمت خانه جدید استفاده کرد.
نکته: تفاوت اصلی KNN در Classification و Regression در نحوه تولید خروجی است. در Classification معمولاً رأی اکثریت همسایهها تعیینکننده است، در حالی که در Regression میتوان میانگین یا میانگین وزندار مقادیر همسایهها را محاسبه کرد.
چرا انتخاب مقدار K در KNN مهم است؟
مقدار K یکی از مهمترین پارامترهای الگوریتم KNN است. انتخاب K بسیار کوچک یا بسیار بزرگ میتواند عملکرد مدل را تحت تأثیر قرار دهد.
K بسیار کوچک
اگر K برابر 1 باشد، الگوریتم تنها نزدیکترین نمونه را در نظر میگیرد. این موضوع باعث میشود مدل به جزئیات و نویز داده بسیار حساس شود و احتمال Overfitting افزایش پیدا کند.
در K=1، اگر داده آموزشی را روی خودش ارزیابی کنیم، هر نمونه نزدیکترین همسایه خودش خواهد بود و خطای آموزش میتواند بسیار پایین یا صفر باشد. اما این موضوع لزوماً به معنی عملکرد خوب روی دادههای جدید نیست.
K بسیار بزرگ
اگر K بیش از حد بزرگ انتخاب شود، تعداد زیادی از نمونهها در تصمیمگیری وارد میشوند. در نتیجه مرز میان کلاسها بیش از حد هموار میشود و مدل ممکن است جزئیات مهم ساختار داده را از دست بدهد. این وضعیت میتواند به Underfitting منجر شود.
چگونه بهترین مقدار K را انتخاب کنیم؟
بهترین مقدار K یک عدد ثابت برای تمام مسائل نیست. انتخاب آن به اندازه داده، تعداد ویژگیها، میزان نویز و ساختار مسئله بستگی دارد.
یک روش رایج، استفاده از Cross-Validation است. در این روش چند مقدار مختلف K آزمایش میشوند و عملکرد مدل روی دادههای اعتبارسنجی مقایسه میشود. مقداری که عملکرد مناسبتری روی دادههای دیدهنشده ایجاد کند، میتواند گزینه مناسبی باشد.
در مسائل Classification معمولاً انتخاب یک K فرد میتواند احتمال مساوی شدن آرای دو کلاس را در مسائل دودویی کاهش دهد؛ با این حال، انتخاب K باید بر اساس داده و ارزیابی تجربی انجام شود.
آیا دادهها را باید در KNN مقیاسبندی کنیم؟
بله، در بسیاری از مسائل KNN مقیاسبندی ویژگیها بسیار مهم است.
دلیل آن این است که KNN بر اساس فاصله کار میکند. فرض کنید دو ویژگی داریم: سن که بین 18 تا 70 قرار دارد و درآمد که ممکن است از چند میلیون تا چند صد میلیون متغیر باشد. اگر دادهها بدون مقیاسبندی وارد مدل شوند، ویژگی درآمد میتواند اثر بسیار بیشتری بر فاصله داشته باشد.
روشهایی مانند Standardization و Normalization میتوانند برای قرار دادن ویژگیها در مقیاس مناسب استفاده شوند.
آیا KNN با دادههای زیاد مناسب است؟
یکی از محدودیتهای مهم KNN این است که در زمان پیشبینی ممکن است نیاز به محاسبه فاصله نمونه جدید با تعداد زیادی از نمونههای آموزشی داشته باشد. بنابراین با افزایش حجم داده، هزینه محاسباتی میتواند افزایش پیدا کند.
همچنین KNN به ذخیره دادههای آموزشی نیاز دارد و برخلاف برخی مدلها، دادههای اصلی را به یک مجموعه کوچک از پارامترها خلاصه نمیکند.
برای مجموعه دادههای بسیار بزرگ میتوان از ساختارهای جستوجوی همسایه نزدیک، روشهای Approximate Nearest Neighbor و زیرساختهای مناسب برای جستوجوی برداری استفاده کرد.
KNN و مشکل ابعاد بالا
یکی دیگر از چالشهای KNN، Curse of Dimensionality یا نفرین ابعاد است. با افزایش تعداد ویژگیها، مفهوم فاصله میتواند کارایی کمتری برای تشخیص شباهت داشته باشد و پیدا کردن همسایههای واقعاً نزدیک دشوارتر شود.
به همین دلیل، در پروژههایی که تعداد ویژگیها بسیار زیاد است، ممکن است لازم باشد پیش از استفاده از KNN از روشهایی مانند Feature Selection یا کاهش ابعاد استفاده شود.
دادههای گمشده در KNN
از آنجا که KNN برای تعیین فاصله به ویژگیهای نمونهها نیاز دارد، مقادیر گمشده میتوانند محاسبه فاصله را با مشکل مواجه کنند.
بنابراین قبل از استفاده از KNN باید Missing Valueها بررسی شوند و بسته به ماهیت داده از روش مناسبی مانند حذف نمونههای نامناسب یا Imputation استفاده شود.
کاربردهای الگوریتم KNN
دستهبندی مشتریان
KNN میتواند برای دستهبندی مشتریان بر اساس ویژگیهای رفتاری و خرید استفاده شود؛ البته در پروژههای بزرگ باید هزینه محاسباتی و مقیاس داده نیز در نظر گرفته شود.
سیستمهای توصیهگر
یکی از ایدههای مهم در سیستمهای توصیهگر، پیدا کردن کاربران یا محصولات مشابه است. روشهای مبتنی بر نزدیکترین همسایه میتوانند در چنین سناریوهایی مورد استفاده قرار گیرند.
تشخیص الگو
KNN در مسائل تشخیص الگو و دستهبندی دادههایی که شباهت میان نمونهها معیار مهمی است، کاربرد دارد.
پردازش تصویر
در برخی مسائل پردازش تصویر و تشخیص الگو میتوان ویژگیهای استخراجشده از تصاویر را به عنوان ورودی KNN استفاده کرد. البته در مسائل مدرن تصویر، روشهای عمیق معمولاً نقش پررنگتری دارند.
پزشکی و زیستداده
KNN میتواند برای دستهبندی نمونههای زیستی یا پزشکی بر اساس ویژگیهای اندازهگیریشده مورد استفاده قرار گیرد. در کاربردهای پزشکی، اعتبارسنجی دقیق و بررسی کیفیت داده اهمیت ویژهای دارد.
تشخیص ناهنجاری
فاصله میان نمونهها میتواند در برخی روشهای مبتنی بر همسایگی برای شناسایی دادههای غیرعادی مورد استفاده قرار گیرد. با این حال، KNN کلاسیک در اصل یک الگوریتم Classification و Regression است و نباید آن را مستقیماً با تمام روشهای تخصصی Anomaly Detection یکسان دانست.
مزایای الگوریتم KNN
- سادگی: ایده و پیادهسازی KNN نسبتاً ساده است.
- عدم نیاز به فرض پیچیده درباره شکل داده: KNN برای تعیین مرز تصمیم به فرم پارامتریک مشخصی متکی نیست.
- قابل استفاده برای Classification و Regression: یک الگوریتم واحد میتواند برای دو نوع مسئله استفاده شود.
- قابل فهم بودن: تصمیم مدل را میتوان با بررسی همسایههای نزدیک توضیح داد.
- انعطافپذیری: با انتخاب معیار فاصله و مقدار K میتوان رفتار الگوریتم را با مسئله تطبیق داد.
معایب الگوریتم KNN
- هزینه پیشبینی: پیدا کردن همسایهها در مجموعه دادههای بزرگ میتواند پرهزینه باشد.
- مصرف حافظه: الگوریتم به دادههای آموزشی برای پیشبینی نمونههای جدید نیاز دارد.
- حساسیت به مقیاس ویژگیها: چون الگوریتم بر فاصله متکی است، مقیاس نامناسب ویژگیها میتواند نتیجه را تغییر دهد.
- حساسیت به انتخاب K: K بسیار کوچک یا بسیار بزرگ میتواند عملکرد مدل را کاهش دهد.
- مشکل در ابعاد بالا: افزایش بیش از حد تعداد ویژگیها میتواند مفهوم فاصله را کماثر کند.
- حساسیت به دادههای نامرتبط و نویزی: ویژگیهای نامناسب میتوانند همسایههای اشتباهی ایجاد کنند.
KNN در برابر برخی الگوریتمهای دیگر
| الگوریتم | ایده اصلی | مزیت مهم | محدودیت مهم |
|---|---|---|---|
| KNN | تصمیمگیری بر اساس نمونههای نزدیک | سادگی و تفسیرپذیری | هزینه پیشبینی در دادههای بزرگ |
| Decision Tree | تقسیم داده بر اساس ویژگیها | تفسیرپذیری بالا | احتمال بیشبرازش |
| Logistic Regression | مدلسازی احتمال کلاس | سادگی و سرعت | محدودیت در روابط بسیار پیچیده |
| SVM | پیدا کردن مرز مناسب میان کلاسها | عملکرد مناسب در برخی فضاهای با ابعاد بالا | حساسیت به تنظیم پارامترها و هزینه محاسباتی |
یک مثال ساده از KNN
فرض کنید میخواهیم مشخص کنیم یک مشتری جدید در کدام یک از دو گروه «مشتری وفادار» یا «مشتری عادی» قرار میگیرد.
برای هر مشتری دو ویژگی در اختیار داریم: تعداد خرید و میانگین مبلغ خرید. مشتری جدید را روی فضای ویژگی قرار میدهیم و فاصله او با مشتریان قبلی را محاسبه میکنیم.
اگر K برابر 5 باشد، پنج مشتری نزدیکتر انتخاب میشوند. اگر سه نفر از آنها «وفادار» و دو نفر «عادی» باشند، رأی اکثریت باعث میشود مشتری جدید در گروه «وفادار» قرار بگیرد.
این مثال ساده نشان میدهد که KNN در واقع تلاش میکند از این فرض استفاده کند که نمونههای مشابه معمولاً خروجی مشابهی دارند.
KNN را فقط حفظ نکنید؛ آن را در یک مسئله واقعی اجرا کنید
یادگیری الگوریتمهای یادگیری ماشین زمانی ارزشمندتر میشود که بتوانید آنها را روی داده واقعی پیادهسازی و ارزیابی کنید.
پیادهسازی KNN با Python
برای پیادهسازی KNN در Python میتوان از کتابخانه scikit-learn استفاده کرد. در یک پروژه واقعی، بهتر است قبل از آموزش مدل، دادهها را بررسی و آمادهسازی کنیم و در صورت نیاز مقیاسبندی ویژگیها را انجام دهیم.
from sklearn.neighbors import KNeighborsClassifier
model = KNeighborsClassifier(n_neighbors=5)
model.fit(X_train, y_train)
predictions = model.predict(X_test)در این مثال مقدار K برابر 5 انتخاب شده است. در پروژه واقعی، مقدار K نباید صرفاً به صورت تصادفی تعیین شود و بهتر است با استفاده از روشهایی مانند Cross-Validation و ارزیابی مناسب انتخاب شود.
آیا KNN الگوریتم یادگیری تنبل است؟
بله. KNN معمولاً در دسته Lazy Learning یا یادگیری تنبل قرار میگیرد. منظور از این اصطلاح این است که الگوریتم در مرحله آموزش، مدل پیچیدهای را برای نمایش روابط میان دادهها یاد نمیگیرد و بخش اصلی محاسبات را هنگام پیشبینی انجام میدهد.
KNN همچنین یک روش Instance-Based Learning محسوب میشود؛ زیرا تصمیمگیری برای نمونه جدید بر اساس نمونههای آموزشی موجود انجام میشود.
آیا KNN یک الگوریتم Non-Parametric است؟
KNN معمولاً یک الگوریتم Non-Parametric در نظر گرفته میشود؛ یعنی برای شکل توزیع داده یا رابطه میان متغیرها یک فرم پارامتریک ثابت مانند یک معادله خطی از پیش تعیین نمیکند.
با این حال، این موضوع به معنی «بدون هیچ پارامتری بودن» نیست. KNN پارامترهایی مانند مقدار K، معیار فاصله و نحوه وزندهی به همسایهها دارد که میتوان آنها را تنظیم کرد.
جمعبندی الگوریتم KNN
الگوریتم KNN یک روش ساده و قابل فهم برای یادگیری ماشین است که پیشبینی خود را بر اساس نزدیکترین نمونههای موجود در دادههای آموزشی انجام میدهد. این الگوریتم میتواند برای Classification و Regression استفاده شود و درک ایده اصلی آن برای یادگیری مفاهیم مهمی مانند فاصله، شباهت، Overfitting و انتخاب پارامتر بسیار مفید است.
با این حال، KNN برای همه مسائل بهترین انتخاب نیست. مقیاس ویژگیها، مقدار K، تعداد نمونهها، تعداد ویژگیها و معیار فاصله همگی میتوانند بر عملکرد آن تأثیر بگذارند. در مجموعه دادههای بزرگ یا با ابعاد بالا نیز باید هزینه محاسباتی و مسئله Curse of Dimensionality را در نظر گرفت.
اگر در حال یادگیری Machine Learning هستید، KNN یکی از الگوریتمهای مناسبی است که میتواند شما را با مفهوم مهم «شباهت میان دادهها» آشنا کند؛ اما برای تبدیل این دانش به مهارت حرفهای، بهتر است آن را در کنار الگوریتمهایی مانند Decision Tree، Logistic Regression، SVM و روشهای Ensemble روی پروژههای واقعی مقایسه و ارزیابی کنید.
سؤالات متداول درباره الگوریتم KNN
الگوریتم KNN چیست؟
KNN یا K-Nearest Neighbors یک الگوریتم یادگیری ماشین با ناظر است که برای پیشبینی نمونه جدید، K نمونه نزدیکتر به آن را پیدا میکند و بر اساس آنها کلاس یا مقدار خروجی را تعیین میکند.
K در الگوریتم KNN به چه معناست؟
K نشاندهنده تعداد نزدیکترین همسایههایی است که الگوریتم برای پیشبینی یک نمونه جدید در نظر میگیرد.
آیا KNN برای Classification و Regression استفاده میشود؟
بله. KNN هم برای طبقهبندی و هم برای رگرسیون قابل استفاده است. در Classification معمولاً از رأی اکثریت و در Regression از میانگین یا میانگین وزندار مقادیر همسایهها استفاده میشود.
بهترین مقدار K در KNN چیست؟
یک مقدار ثابت و مناسب برای همه دادهها وجود ندارد. معمولاً چند مقدار مختلف K با استفاده از Validation یا Cross-Validation ارزیابی میشوند و مقدار مناسب بر اساس عملکرد مدل انتخاب میشود.
چرا Scaling در KNN مهم است؟
چون KNN بر اساس فاصله میان نمونهها تصمیمگیری میکند. اگر ویژگیها مقیاسهای بسیار متفاوتی داشته باشند، ویژگیهایی با دامنه بزرگتر میتوانند تأثیر نامتناسبی بر فاصله داشته باشند.
آیا KNN برای دادههای بزرگ مناسب است؟
KNN میتواند روی دادههای بزرگ نیز استفاده شود، اما هزینه محاسبه فاصله و جستوجوی همسایهها ممکن است با افزایش تعداد نمونهها زیاد شود. در چنین شرایطی باید از روشهای جستوجوی بهینه یا الگوریتمهای جایگزین استفاده کرد.
آیا KNN یک الگوریتم یادگیری با ناظر است؟
بله. در کاربردهای Classification و Regression، KNN از دادههای آموزشی دارای خروجی یا برچسب استفاده میکند و بنابراین یک الگوریتم Supervised Learning محسوب میشود.
ممنون از مقاله خوبتون
سپاسگزاریم.