۳۰ پرسش و پاسخ درباره‌ی الگوریتم نزدیکترین K همسایه

الگوریتم‌های زیادی برای «یادگیری ماشین» (Machine Learning) ارائه شده‌اند، ولی می‌شود گفت که بهترین آن‌ها الگوریتم‌های «نزدیکترین K همسایه» (K-Nearest Neighbors) و الگوریتم‌های درختی هستند. درک و توضیح هردوی آن‌ها ساده است، همچنین هردو کاملا مناسب استفاده‌ی عمومی هستند. اگر در زمینه‌ی یادگیری ماشین تازه ‌کار هستید، حتما خودتان را در درک مفاهیم این الگوریتم‌ها محک بزنید. این آزمون برای بررسی دانش شخصی در زمینه‌ی الگوریتم نزدیکترین K همسایه است. بیشتر از 650 نفر در این آزمون شرکت کرده‌اند. اگر شما یکی از افرادی هستید که این آزمون را از دست داده‌اید، در اینجا سوال‌ها و جواب‌های آن آمده است.

سوال‌ها و جواب‌های آزمون

1) صحیح یا غلط: الگوریتم (k-NN (K-Nearest Neighbor در زمان تست نسبت به زمان اجرا محاسبات بیشتری می‌کند.

1. صحیح
2. غلط

پاسخ: A

مرحله‌ی یادگیری در این الگوریتم تنها شامل ذخیره‌سازی بردارهای ویژگی و دسته‌بندی نمونه‌ها است.

در مرحله‌ی آزمایش، با استفاده از برچسب‌هایی که در K نمونه‌ی آزمایشی در نزدیکی آن نقطه بیشتر استفاده شده‌اند، یک نقطه‌ی آزمایش ساخته می‌شود، به همین دلیل محاسبات بیشتری انجام می‌گیرد.

2) اگر فرض کنیم داریم از الگوریتم نزدیکترین k همسایه استفاده می‌کنیم، چه مقداری برای k مناسبتر است؟

1. 3
2. 10
3. 20
4. 50

پاسخ: B

هنگامی که مقدار k برابر با 10 است، خطاهای اعتبارسنجی کمتر هستند. به همین جهت، استفاده از این مقدار برای k مناسبتر است.

3) کدام یک از معیارهای فاصله سنجی زیر را نمی‌توان در k-NN استفاده کرد؟

1. منهتن (Manhattan)
2. مینکوسکی (Minkowski)
3. تنیموتو (Tanimoto)
4. ژاکار (Jaccard)
5. ماهالانوبیس (Mahalanobis)
6. از تمامی موارد می‌توان استفاده کرد

پاسخ: F

از تمامی این معیارها می‌توان برای فاصله سنجی در k-NN استفاده کرد.

4) کدام یک از موارد زیر درمورد الگوریتم‌های k-NN صحیح است؟

1. می‌توان از آن برای دسته‌بندی استفاده کرد.
2. می‌توان از آن برای رگرسیون استفاده کرد.
3. می‌توان از آن هم در دسته‌بندی و هم در رگرسیون استفاده کرد.

پاسخ: C

از الگوریتم k-NN می‌توان برای مسائل رگرسیون نیز استفاده کرد. در این حالت می‌توان پیش‌بینی‌ها را بر اساس میانگین یا میانه‌ی k شبیه‌ترین نمونه انجام داد.

5) کدام یک از موارد زیر درمورد الگوریتم k-NN صحیح است؟

1. اگر تمام داده‌ها هم اندازه باشند، k-NN بهتر عمل می‌کند.
2. اگر تعداد ورودی‌ها کم باشد k-NN به خوبی عمل می‌کند، ولی اگر تعداد ورودی‌ها خیلی زیاد باشد، درگیر می‌شود.
3. K-NN هیچ حدسی راجع به نحوه‌ی عملکرد مساله‌ای که در حال حل کردن آن است نمی‌زند.

1. 1 و 2
2. 1 و 3
3. تنها گزینه‌ی 1
4. تمام موارد

پاسخ: D

موارد بالا همه از اهداف الگوریتم k-NN هستند.

6) کدام یک از الگوریتم‌های یادگیری ماشین زیر را می‌توان برای به دست آوردن مقادیر گم شده در متغیرهای دسته‌ای و پیوسته به کار برد؟

1. K-NN
2. رگرسیون خطی (Linear Regression)
3. رگرسیون منطقی (Logistic Regression)

پاسخ: A

از الگوریتم k-NN می‌توان برای پر کردن مقادیر گم شده در متغیرهای دسته‌ای و پیوسته استفاده کرد.

7) کدام یک از موارد زیر در مورد فاصله‌ی منهتن (Manhattan distance) صحیح است؟

1. می‌توان از آن برای متغیرهای پیوسته استفاده کرد.
2. می‌توان از آن برای متغیرهای دسته‌ای استفاده کرد.
3. می‌توان از آن هم برای متغیرهای دسته‌ای و هم برای متغیرهای پیوسته استفاده کرد.
4. هیچکدام

پاسخ: A

فاصله‌ی منهتن برای محاسبه‌ی فواصل بین ویژگی‌هایی با مقدار واقعی طراحی شده است.

8) برای متغیرهای دسته‌ای در k-NN از کدام یک از معیارهای فاصله‌سنجی زیر می‌توان استفاده کرد؟

1. فاصله همینگ (Hamming Distance)
2. فاصله اقلیدسی (Euclidean Distance)
3. فاصله منهتن (Manhattan Distance)

1. 1
2. 2
3. 3
4. 1 و 2
5. 2 و 3
6. 1، 2 و 3

پاسخ: A

از هردو فواصل «منهتن» و «اقلیدسی» می‌توان برای متغیرهای پیوسته استفاده کرد، ولی «همینگ» برای متغیرهای دسته‌ای مورد استفاده قرار می‌گیرد.

9) فاصله‌ی اقلیدسی بین دو داده در نقاط (A(1,3 و (B(2,3 چقدر است؟

1. 1
2. 2
3. 4
4. 8

پاسخ: A

10) فاصله‌ی منهتن بین دو داده در نقاط (A(1,3 و (B(2,3 چقدر است؟

1. 1
2. 2
3. 4
4. 8

پاسخ: A

سوالات 11 تا 12 را براساس توضیحات زیر پاسخ دهید

فرض کنید داده‌های زیر را بهتان داده‌اند که در آن x و y دو متغیر ورودی، و کلاس نیز متغیر وابستگی است.

در پایین یک طرح پراکنده مشاهده می‌کنید که داده‌های بالا را در فضای دو بعدی نمایش می‌دهد.

11) فرض کنید می‌خواهید مقدار کلاس ورودی جدید با مقادیر x=1 و y=1 را توسط فاصله‌ی اقلیدسی در 3-NN به دست آورید. این نقطه متعلق به کدام کلاس است؟

1. کلاس مثبت
2. کلاس منفی
3. نمی‌توان حدس زد
4. هیچکدام

پاسخ: A

تمامی نقاط نزدیک به آن جز کلاس مثبت هستند، پس این نقطه نیز در کلاس مثبت قرار خواهد گرفت.

12) در همان سوال قبلی، اینبار می‌خواهیم به جای 3-NN از 7-NN استفاده کنیم. نقطه‌ی x=1 و y=1 در کدام کلاس قرار می‌گیرد؟

1. کلاس مثبت
2. کلاس منفی
3. نمی‌توان حدس زد
4. پاسخ: B

این نقطه در کلاس منفی قرار خواهد گرفت، زیرا اینبار 4 کلاس منفی و 3 کلاس مثبت در نزدیکی قرار دارند.

سوالات 13 تا 14 را براساس توضیحات زیر پاسخ دهید

فرض کنید داده‌ی دو کلاسی زیر را بهتان داده‌اند که در آن «+» نشانه‌ی یک کلاس مثبت و «-» نشانه‌ی یک کلاس منفی است.

13) به ازای چه مقداری از k در k-NN، می‌توان خطای اعتبارسنجی متقاطع «یکی را کنار گذار» (leave one out cross validation) را به حداقل رساند؟

1. 3
2. 5
3. تفاوتی ندارد
4. هیچکدام

پاسخ: B

به ازای 5-NN کمترین خطای اعتبارسنجی «یکی را کنار گذار» را خواهیم داشت.

14) دقت در اعتبارسنجی «یکی را کنار گذار» به ازای k=5 کدام گزینه خواهد بود؟

1. 2/14
2. 4/14
3. 6/14
4. 8/14
5. هیچکدام

پاسخ: E

دقت در اعتبارسنجی «یکی را کنار گذار» در 5-NN، 10/14 خواهد بود.

15) با در نظر گرفتن «بایاس» (Bias)، کدام یک از موارد زیر در مورد k-NN صحیح است؟

1. با افزایش k، بایاس زیاد می‌شود.
2. با کاهش k، بایاس کم می‌شود.
3. نمی‌توان گفت.
4. هیچکدام

پاسخ: A

هرچه عدد k بیشتر باشد، مدل ساده‌تر است و در مدل ساده، بایاس بیشتر خواهد بود.

16) با در نظر گرفتن واریانس (Variance)، کدام یک از موارد زیر در مورد k-NN صحیح است؟

1. با افزایش k، واریانس زیاد می‌شود.
2. با کاهش k، واریانس زیاد می‌شود.
3. نمی‌توان گفت.
4. هیچکدام

پاسخ: B

مدل ساده، واریانس کمتری دارد.

17) دو فاصله‌ی زیر (فاصله‌ی اقلیدسی و فاصله‌ی منهتن) که به طور کلی در الگوریتم k-NN استفاده می‌شوند را بهتان داده‌اند. این فواصل بین دو نقطه‌ی (A(x1,y2 و (B(x2,y2 قرار دارند.

به تصاویر زیر توجه کنید. کدام تصویر مربوط به کدام فاصله است؟

1. تصویر چپ فاصله‌ی منهتن و تصویر راست فاصله‌ی اقلیدسی است.
2. تصویر چپ فاصله‌ی اقلیدسی و تصویر راست فاصله‌ی منهتن است.
3. هیچکدام فاصله‌ی منهتن نیستند.
4. هیچکدام فاصله‌ی اقلیدسی نیستند.

پاسخ: B

تصویر چپ نمایانگر فاصله‌ی اقلیدسی و تصویر راست نمایانگر فاصله‌ی منهتن است.

18) در k-NN، اگر در داده‌هایتان نویز (noise) پیدا کنید، کدام یک از موارد زیر را انتخاب می‌کنید؟

1. مقدار k را افزایش می‌دهم.
2. مقدار K را کاهش می‌دهم.
3. نویز به مقدار k وابسته نیست.
4. هیچکدام

پاسخ: A

برای اطمینان از دسته‌بندی، می‌توان مقدار k را افزایش داد.

19) به علت داشتن ابعاد زیاد، احتمال «overfit» در k-NN بسیار زیاد است. برای رفع چنین مشکلی، کدام یک از گزینه‌های زیر را انتخاب می‌کنید؟

1. کاهش ابعاد
2. انتخاب ویژگی

1. 1
2. 2
3. 1 و 2
4. هیچکدام

پاسخ: C

در همچین حالتی می‌توان هم از کاهش ابعاد و هم از انتخاب ویژگی استفاده کرد.

20) کدام یک از جملات زیر صحیح است؟

1. الگوریتم k-NN یک الگوریتم برپایه‌ی حافظه است که در آن دسته‌بندی سریعا در هنگام دریافت اطلاعات جدید انجام می‌شود.
2. در بدترین حالت، پیچیدگی محاسباتی در دسته‌بندی نمونه‌ها، با افزایش تعداد نمونه‌های موجود در «دیتاست» (Dataset) زیاد می‌شود.

1. 1
2. 2
3. 1 و 2
4. هیچکدام

پاسخ: C

هردو جمله صحیح هستند و نیاز به توضیح خاصی ندارند.

21) فرض کنید تصاویر زیر را بهتان داده‌اند (از چپ به راست به ترتیب 1، 2 و 3). مقدار k در k-NN را در هر تصویر بیابید.

1. K1 > k2 > k3
2. K1 < k2
3. K1 = k2 = k3
4. هیچکدام

پاسخ: D

مقدار k در k3 دارای بیشترین و در k1 دارای کمترین مقدار است.

22) در گراف زیر، به ازای کدام مقدار از k کمترین دقت را در اعتبارسنجی «یکی را کنار گذار» خواهیم داشت؟

1. 1
2. 2
3. 3
4. 5

پاسخ: B

اگر مقدار k را برابر با 2 قرار دهیم، کمترین دقت در اعتبارسنجی را خواهیم داشت. خودتان می‌توانید این مورد را امتحان کنید.

23) شرکتی یک دسته‌بندی k-NN دارد که در آن یادگیری با دقت 100% انجام می‌شود. پس از پیاده‌سازی این مدل در سمت کلاینت، مشخص شد که این مدل اصلا دقیق نیست. مشکل این مدل کدام یک از موارد زیر است؟

نکته: پیاده‌سازی مدل موفقیت آمیز بوده و هیچ مشکلی فنی در سمت کلاینت دیده نشده است.

1. احتمالا مدل «overfit» است.
2. احتمالا مدل «underfit» است.
3. نمی‌توان گفت.
4. هیچکدام

پاسخ: A

در مدل‌های «overfit» شده، عملکرد به نظر در هنگام یادگیری مناسب می‌آید، ولی در هنگام کار با داده‌های جدید، نتیجه یکسان نخواهد بود.

24) در مورد k-NN، کدام یک از موارد زیر صحیح است؟

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

1. 1
2. 2
3. 1 و 2
4. هیچکدام

پاسخ: C

هر دو گزینه صحیح هستند و نیاز به توضیح خاصی ندارند.

25) در دسته‌بندی‌های k-NN، کدام یک از موارد زیر صحیح است؟

1. هرچه مقدار k بیشتر باشد، دقت دسته‌بندی نیز بیشتر خواهد بود.
2. هرچه مقدار k کمتر باشد، مرز تصمیم‌گیری نیز نرم‌تر خواهد بود.
3. مرز تصمیم‌گیری خطی است.
4. K-NN نیازی به گام یادگیری مشخصی ندارد.

پاسخ: D

گزینه‌ی A: این مورد همیشه صحیح نیست. باید مطمئن باشید که مقدار k نه بیش از حد زیاد است و نه بیش از حد کم.

گزینه‌ی B: این مورد صحیح نیست. ممکن است مرز تصمیم‌گیری کمی ناهموار باشد.

گزینه‌ی C: همانند گزینه‌ی B.

گزینه‌ی D: این مورد صحیح است.

26) صحیح یا غلط: می‌توان با یک الگوریتم دسته‌بندی 1-NN یک الگوریتم دسته بندی 2-NN ساخت.

1. صحیح
2. غلط

پاسخ: A

با مجموعی از الگوریتم‌های 1-NN می‌توان یک الگوریتم 2-NN پیاده‌سازی کرد.

27) هنگامی که در الگوریتم k-NN مقدار k را تغییر می‌دهید چه اتفاقی می‌افتد؟

1. با افزایش مقدار k، مرز تصمیم‌گیری نرم‌تر می‌شود.
2. با کاهش مقدار k، مرز تصمیم‌گیری نرم‌تر می‌شود.
3. نرم بودن مرز تصمیم‌گیری ربطی به مقدار k ندارد.
4. هیچکدام

پاسخ: A

با افزایش مقدار k، مرز تصمیم‌گیری نرم‌تر خواهد شد.

28) کدام یک از جملات زیر درمورد الگوریتم k-NN صحیح است؟

1. با استفاده از «اعتبارسنجی متقاطع» (cross validation) می‌توانیم یک مقدار بهینه برای k انتخاب کنیم.
2. از نظر فاصله‌ی اقلیدسی همه‌ی ویژگی‌ها به یک اندازه مهم هستند.

1. 1
2. 2
3. 1 و 2
4. هیچکدام

پاسخ: C

هر دو جمله صحیح هستند.

سوالات 29 تا 30 را براساس توضیحات زیر پاسخ دهید

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

نکته: محاسبه‌ی فاصله‌ی بین 2 مشاهده، D زمان می‌برد.

29) اگر تعداد مشاهدات در داده‌های آزمایشی بسیار زیاد باشد، زمانی که طول می‌کشد تا 1-NN کار خود را انجام دهد چقدر خواهد بود؟

1. N*D
2. N*D*2
3. N*D)/2)
4. هیچکدام

پاسخ: A

با توجه به اینکه مقدار N بسیار زیاد است، گزینه‌ی A صحیح است.

30) رابطه‌ی بین 1-NN، 2-NN و 3-NN از نظر زمانی چگونه خواهد بود؟

1. 1-NN > 2-NN > 3-NN
2. 1-NN < 2-NN < 3-NN
3. 1-NN ~ 2-NN ~ 3-NN
4. هیچکدام

پاسخ: C

زمان یادگیری در الگوریتم k-NN به ازای هر مقداری ثابت خواهد بود.

اگر مایل به کسب اطلاعات بیشتر در این زمینه باشید، شاید آموزش‌های زیر برای شما مفید باشند:

• آموزش یادگیری عمیق (Deep learning)
• آموزش برنامه نویسی یادگیری عمیق با پایتون
• مجموعه آموزش های شبکه های عصبی مصنوعی در متلب

#