K-Nearest Neighbors (KNN) من أبسط خوارزميات التعلم الآلي من حيث الفكرة. عند ظهور عينة جديدة، تبحث الخوارزمية عن العينات المعروفة الأقرب إليها ثم تستخدم نتائجها لاتخاذ القرار.
تستخدم KNN غالباً ضمن التعلم الخاضع للإشراف لأن بيانات التدريب تحتوي على تسميات معروفة.
خطوات العمل
- استقبال بيانات التدريب والتسميات.
- حساب المسافة بين العينة الجديدة وكل عينة تدريب.
- ترتيب العينات حسب المسافة.
- اختيار أقرب
Kعينات. - اختيار الفئة الأكثر تكراراً بينها.
معنى K
تمثل K عدد الجيران المشاركين في القرار. عندما تكون K = 1 يعتمد القرار على أقرب نقطة فقط، بينما تستخدم K = 5 خمسة جيران.
القيم الفردية مثل 3 أو 5 شائعة في التصنيف الثنائي لتقليل احتمال التعادل، لكن الأفضل اختيار K باستخدام بيانات التحقق.
المسافة الإقليدية
من أشهر المقاييس المستخدمة Euclidean Distance:
d = sqrt((x2 - x1)^2 + (y2 - y1)^2)
كلما صغرت المسافة كانت العينتان أقرب حسب الخصائص المستخدمة.
أهمية تقييس الخصائص
إذا كانت إحدى الخصائص بين 1 و100 وأخرى بين 1 و500000 فقد تسيطر الثانية على حساب المسافة. لذلك تستخدم تقنيات مثل Standardization أو Min-Max Scaling قبل تشغيل KNN.
التصنيف والانحدار
في Classification يتم اختيار الفئة الأكثر شيوعاً بين الجيران.
في Regression يمكن استخدام متوسط قيم أقرب الجيران لإنتاج التنبؤ.
المزايا
- سهلة الفهم والتنفيذ
- لا تحتاج إلى تدريب معقد
- مناسبة للبيانات الصغيرة والمتوسطة
- قابلة للاستخدام في التصنيف والانحدار
القيود
- قد تكون بطيئة أثناء التنبؤ
- حساسة لمقياس الخصائص
- تتأثر بالخصائص غير المهمة
- تصبح أقل فعالية في الأبعاد العالية بسبب Curse of Dimensionality
اختيار K
K الصغيرة جداً قد تجعل النموذج حساساً للضوضاء، بينما K الكبيرة جداً قد تخفي الأنماط المحلية. لذلك يفضّل تجربة قيم متعددة واختيار الأفضل على بيانات التحقق.
تطبيقات عملية
يمكن استخدام KNN في:
- تصنيف العملاء حسب التشابه
- أنظمة التوصية البسيطة
- اكتشاف بعض الأنماط الشاذة
- تصنيف العينات الطبية
- التعرف على الأنماط
- بناء Baseline سريع لمشكلة تصنيف
منطق التنفيذ
التنفيذ الأساسي هو:
calculate distance to every training sample
sort by distance
take the nearest K
count labels
return the most frequent label
التنفيذ الموجود في مشروع JavaScript المرفق يتبع هذا المنطق باستخدام Euclidean Distance ثم ترتيب النقاط واختيار أقرب K عناصر.
الخلاصة
تعتمد KNN على فكرة مباشرة: العينات المتشابهة غالباً ما تمتلك نتائج متشابهة. ويعتمد نجاحها على اختيار K المناسب، ومقياس المسافة، وتقييس البيانات، وعدد الخصائص وحجم مجموعة البيانات.