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

مقدمه

K یک مقدار مثبت صحیح و عموماً کوچک است. اگر k=1 باشد نمونه به سادگی در کلاس همسایگان نزدیکش تعیین می‌گردد. فرد بودن مقدار k مفید می‌باشد چون با این کار جلوی آراء برابر گرفته می‌شود. روش k همسایه‌ نزدیک، برای بسیاری از روش‌ها کاربرد دارد، زیرا اثربخش، غیرپارامتریک و دارای پیاده‌سازی راحت می‌باشد. با این حال زمان دسته‌بندی‌اش طولانی است و یافتن مقدار k بهینه مشکل است.

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

شکل بالا مثالی از الگوریتم دسته‌بندی K نزدیک ترین همسایه، با استفاده از بردار ویژگی چندبعدی می‌باشد که مثلث‌ها کلاس اول و مربع‌ها کلاس دوم رانشان می‌دهند. دایره کوچک در داخل دوایر، نمونه تستی را نشان می‌دهد. حال اگر مقدار k=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) استفاده شود که مسئله استانداردسازی متغیرهای عددی بین ۰ و ۱ را به وجود می آورد در حالی که مخلوطی از متغیرهای عددی و گسسته در مجموعه داده وجود دارد.

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

به لحاظ تجربه، K مطلوب برای بیشتر مجموعه داده‌ها بین ۳ تا ۱۰ است. این نتایج بسیار بهتر از 1NN تولید می‌کند. در این پست  هدف ما از گردآوری پاورپوینت الگوریتم‌های مهم یادگیری ماشین آشنایی و آموزش شما در زمینه الگوریتم‌های تقویتی و الگوریتم‌های پیشرفته و جدید در یادگیری ماشین می‌باشد برای دسترسی به این فایل به لینک زیر مراجعه کنید.

• پاورپوینت الگوریتم های مهم یادگیری ماشین — کلیک کنید.

مثال K نزدیک‌ترین همسایه

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

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

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

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

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

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

مراجع

https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

https://www.saedsayad.com/k_nearest_neighbors.htm