الگوریتم KNN - نزدیکترین همسایه - مهدی مشایخی

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

برای مشکلات طبقه‌بندی، یک برچسب کلاس بر اساس اکثریت آرا اختصاص داده می‌شود یعنی برچسبی که بیشتر در اطراف یک نقطه داده نشان داده می‌شود استفاده می‌شود. در حالی که این از نظر فنی "رای گیری اکثریت" در نظر گرفته می شود، اصطلاح "رای اکثریت" بیشتر در ادبیات استفاده می شود. تمایز بین این اصطلاحات این است که "رای اکثریت" از نظر فنی به اکثریت بیش از 50٪ نیاز دارد که در درجه اول زمانی کار می کند که فقط دو دسته وجود داشته باشد. وقتی چندین کلاس دارید - مثلاً چهار دسته، برای نتیجه‌گیری در مورد یک کلاس، لزوماً به 50٪ آرا نیاز ندارید. شما می توانید یک برچسب کلاس با رای بیشتر از 25٪ اختصاص دهید.

مسائل رگرسیون از مفهومی مشابه به عنوان مسئله طبقه‌بندی استفاده می‌کنند، اما در این مورد، میانگین k نزدیک‌ترین همسایه‌ها برای پیش‌بینی در مورد یک طبقه‌بندی گرفته می‌شود. تمایز اصلی در اینجا این است که طبقه‌بندی برای مقادیر گسسته استفاده می شود، در حالی که رگرسیون برای مقادیر پیوسته استفاده می شود. با این حال، قبل از انجام یک طبقه‌بندی، فاصله باید تعریف شود. فاصله اقلیدسی بیشتر مورد استفاده قرار می گیرد که در ادامه بیشتر به آن می پردازیم.
همچنین شایان ذکر است که الگوریتم KNN نیز بخشی از خانواده مدل‌های «یادگیری تنبل» است، به این معنی که تنها یک مجموعه داده آموزشی را در مقابل گذراندن یک مرحله آموزشی ذخیره می‌کند. این همچنین به این معنی است که تمام محاسبات زمانی رخ می دهد که یک طبقه‌بندی یا پیش بینی انجام می شود. از آنجایی که برای ذخیره تمام داده های آموزشی خود به شدت به حافظه متکی است، از آن به عنوان یک روش یادگیری مبتنی بر نمونه یا مبتنی بر حافظه نیز یاد می شود.
ایده های اولیه در مورد مدل KNN را به Evelyn Fix و Joseph Hodges نسبت داده شده است.

معیارهای فاصله

به طور خلاصه، هدف الگوریتم k نزدیکترین همسایه شناسایی نزدیکترین همسایگان یک نقطه پرس و جو است، به طوری که بتوانیم یک برچسب کلاس به آن نقطه اختصاص دهیم. برای انجام این کار، KNN چند الزام دارد:

معیارهای فاصله خود را تعیین کنید

برای تعیین اینکه کدام نقاط داده به یک نقطه پرس و جو نزدیکتر هستند، فاصله بین نقطه پرس و جو و سایر نقاط داده باید محاسبه شود. این معیارهای فاصله به شکل گیری مرزهای تصمیم کمک می کند، که نقاط پرس و جو را به مناطق مختلف تقسیم می کند. معمولاً مرزهای تصمیم را با نمودارهای ورونوی مشاهده خواهید کرد.

فاصله اقلیدسی (p=2):  این رایج ترین اندازه گیری فاصله است و به بردارهای با ارزش واقعی محدود می شود. با استفاده از فرمول زیر، یک خط مستقیم بین نقطه پرس و جو و نقطه دیگر اندازه گیری می شود.

فاصله منهتن (p=1) : این نیز یکی دیگر از معیارهای محبوب فاصله است که قدر مطلق بین دو نقطه را اندازه گیری می کند. همچنین به عنوان فاصله تاکسی یا فاصله بلوک شهر شناخته می شود زیرا معمولاً با یک شبکه تجسم می شود و نشان می دهد که چگونه می توان از یک آدرس به آدرس دیگر از طریق خیابان های شهر حرکت کرد.

فاصله مینکوفسکی : این اندازه‌گیری فاصله، شکل تعمیم یافته معیارهای فاصله اقلیدسی و منهتن است. پارامتر p در فرمول زیر امکان ایجاد سایر معیارهای فاصله را فراهم می کند. فاصله اقلیدسی با این فرمول نشان داده می شود که p برابر با دو باشد و فاصله منهتن با p برابر با یک نشان داده شود.

تعریف (کا) های الگوریتم

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

کد زیر نمونه ای از نحوه ایجاد و پیش بینی با یک مدل KNN است:

from sklearn.neighbors import KNeighborsClassifier

model_name = ‘K-Nearest Neighbor Classifier’
knnClassifier = KNeighborsClassifier(n_neighbors = 5, metric = ‘minkowski’, p=2)
knn_model = Pipeline(steps=[(‘preprocessor’, preprocessorForFeatures), (‘classifier’ ,knnClassifier)])

knn_model.fit(X_train, y_train)
y_pred = knn_model.predict(X_test)

کاربردهای KNN در یادگیری ماشینی

الگوریتم KNN در کاربردهای مختلف، عمدتاً در طبقه‌بند استفاده شده است. برخی از این موارد استفاده عبارتند از:

- پیش پردازش داده ها : مجموعه داده ها اغلب مقادیر گم شده ای دارند، اما الگوریتم KNN می تواند این مقادیر را در فرآیندی به نام داده های گمشده تخمین بزند.

- موتورهای توصیه : با استفاده از داده های جریان کلیک از وب سایت ها، الگوریتم KNN برای ارائه توصیه های خودکار به کاربران در مورد محتوای اضافی استفاده شده است. تحقیقی انجام شده که نشان می دهد که کاربر به یک گروه خاص اختصاص داده شده است و بر اساس رفتار کاربر آن گروه، به آنها توصیه می شود. با این حال، با توجه به مسائل مقیاس‌بندی با KNN، این رویکرد ممکن است برای مجموعه داده‌های بزرگ‌تر بهینه نباشد.

- مراقبت های بهداشتی : KNN در صنعت مراقبت های بهداشتی نیز کاربرد داشته است و خطر حملات قلبی و سرطان پروستات را پیش بینی می کند. این الگوریتم با محاسبه محتمل ترین عبارات ژنی کار می کند.

- تشخیص الگو : KNN همچنین در شناسایی الگوها، مانند طبقه‌بندی متن و رقم کمک کرده است. این به ویژه در شناسایی شماره های دست نویسی که ممکن است در فرم ها یا پاکت های پستی پیدا کنید مفید بوده است.

وبسایت من : اینجا کلیک کنید.

لینک حمایت مالی برای ادامه راه : اینجا کلیک کنید.

آدرس لینکدین من و جواب به سوالات شما : اینجا کلیک کنید.

آدرس توییتر من برای مشارکت در گفت و گو ها : اینجا کلیک کنید.

انجام پروژه های ماشین لرنینگ و یادگیری عمیق در تلگرام : Mashayekhi_Ai@

منبع : https://www.ibm.com/topics/knn#:~:text=The%20k%2Dnearest%20neighbors%20algorithm%2C%20also%20known%20as%20KNN%20or,of%20an%20individual%20data%20point.