K-Nearest Neighbors (KNN)

خوارزمية أقرب الجيران k (KNN) هي خوارزمية تعلم خاضع للإشراف تتنبأ بتصنيف مثال جديد انطلاقًا من أقرب الأمثلة المصنفة إليه وعددها k: تصويت الأغلبية بين هؤلاء الجيران في مهام التصنيف، أو متوسط قيمهم في الانحدار. KNN خوارزمية غير معلمية و"كسولة": فهي لا تتعلم أوزانًا، بل تخزّن بيانات التدريب فحسب، ولا تنفّذ عملها إلا عند طلب تنبؤ. قدّم إيفلين فيكس وجوزيف هودجز هذه الطريقة عام 1951، وفي عام 1967 أثبت توماس كوفر وبيتر هارت أن قاعدة أقرب جار واحد، عند توافر بيانات غير محدودة، لا يتجاوز معدل خطئها ضعفي معدل خطأ أفضل مصنّف ممكن. ويُستخدم الآن البحث نفسه عن أقرب الجيران على نطاق واسع في قواعد بيانات المتجهات وأنظمة استرجاع الصور التي تقارن التضمينات المستخرجة من الشبكات العصبية.

كيف تجري KNN التنبؤ#

تنفّذ KNN ثلاث خطوات لكل نقطة استعلام:

1. قياس المسافة: تحسب المسافة بين نقطة الاستعلام وكل مثال مخزّن. وتُعد المسافة الإقليدية الخيار الافتراضي، بينما تُستخدم مسافتا مانهاتن ومينكوفسكي بديلين شائعين، ويشيع استخدام التشابه الجيب التمام مع التضمينات، حيث يحمل اتجاه المتجه معناه.
2. اختيار الجيران: تحتفظ بأمثلة k ذات أصغر المسافات.
3. دمج تصنيفاتهم: يختار التصنيف الفئة الأكثر شيوعًا بين الجيران، بينما يأخذ الانحدار متوسط قيمهم. وعند الترجيح بحسب المسافة (weights="distance" في scikit-learn)، يكون تأثير الجيران الأقرب أكبر.

تسهم كل سمة في المسافة، لذا تطغى السمات ذات المقاييس الكبيرة: فالدخل بالدولار سيطغى على العمر بالسنوات. لذلك تعمل مسارات KNN على توحيد مقاييس السمات أولًا، أو تقارن التضمينات المستخرجة من نموذج استخراج السمات، بحيث تسهم كل بُعد بمقياس قابل للمقارنة.

اختيار k#

تحدّد قيمة k التوازن بين فرط التكيّف ونقص التكيّف. عندما تكون k = 1، تستأثر كل نقطة تدريب، بما في ذلك النقاط المشوشة وتلك الموسومة خطأً، بمنطقة خاصة بها، ويصبح حد القرار متعرجًا. وعندما تكون k كبيرة جدًا، يمتد تأثير كل تصويت إلى مسافة بعيدة عن نقطة الاستعلام، فتطمس حدود الفئات الحقيقية. وعند وجود فئتين، تتفادى قيمة k الفردية تعادل الأصوات، ويُعد التحقق المتقاطع الطريقة القياسية لاختيار k. وعلى مجموعة بيانات الهلالين المشوشة الخاصة بمكتبة scikit-learn، تتجلى المفاضلة في ثلاث قيم:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

عند k = 1، يحفظ المصنّف نقاط التدريب، محققًا درجة 1.00 عليها و0.83 على النقاط المحجوبة. وعند k = 15، يحقق درجتين قدرهما 0.90 و0.89، وهي أفضل نتيجة اختبار بين القيم الثلاث. أما k = 300، أي ما يقارب نصف نقاط التدريب البالغ عددها 700، فتنعّم حد القرار إلى أن تنخفض الدرجتان إلى 0.84 و0.81.

تسريع البحث عن الجيران#

يقارن البحث بالقوة الغاشمة نقطة الاستعلام بجميع النقاط المخزنة وعددها n في أبعاد d، لذا تكون كلفة كل تنبؤ في حدود n × d عملية، وتزداد الذاكرة مع حجم مجموعة البيانات. وتتجاوز بُنى تقسيم الفضاء، مثل أشجار k-d وأشجار الكرة، معظم المقارنات في الأبعاد المنخفضة، فيما يختار algorithm="auto" في scikit-learn بين البحث بالقوة الغاشمة وشجرة k-d وشجرة الكرة. وفي الأبعاد العالية، تجعل لعنة الأبعاد المسافات بين النقاط متقاربة، فلا يعود تقليم الأشجار مجديًا، وتتحول الأنظمة الكبيرة إلى فهارس تقريبية لأقرب الجيران (ANN)، مثل مخططات HNSW وفهارس الملفات المعكوسة (IVF) باستخدام تكميم المنتجات، والمُنفذة في مكتبات مثل FAISS. وتعيد هذه الفهارس معظم أقرب الجيران الحقيقيين، مع مقارنة نقطة الاستعلام بجزء صغير من المتجهات المخزنة:

KNN مقارنةً بالأساليب ذات الصلة#

• التجميع باستخدام K-means: خوارزمية غير خاضعة للإشراف تجمع النقاط غير المصنفة في k عناقيد حول مراكز عنقودية متعلَّمة. وتشابه الاسمين في الحرف محض مصادفة؛ ففي k-means، يحدد k عدد العناقيد.
• البحث المتجهي: هو صيغة الاسترجاع للعملية نفسها؛ إذ يعيد العناصر المخزنة الأقرب إلى تضمين الاستعلام، عادةً عبر فهرس تقريبي، ويستخدم التطبيق تلك العناصر مباشرةً.
• آلات المتجهات الداعمة والانحدار اللوجستي: نماذج معلمية تتعلم حدًا فاصلًا أثناء التدريب، لذا تظل كلفة التنبؤ ثابتة مع نمو مجموعة التدريب.

تطبيقات عملية#

• أنظمة التوصية: توصي التصفية التعاونية القائمة على العناصر بمنتجات تقع متجهات تقييمها أو شرائها أقرب إلى العناصر التي أعجبت المستخدم بالفعل.
• اكتشاف الحالات الشاذة: تُستخدم المسافة بين نقطة وأقرب جار لها من المرتبة k بوصفها درجة للشذوذ، ما يبرز المعاملات أو قراءات المستشعرات البعيدة عن كل مثال طبيعي.
• تعويض القيم المفقودة: تملأ KNNImputer في scikit-learn كل قيمة مفقودة بمتوسط السمة لدى الصفوف k الأكثر تشابهًا.
• استرجاع الصور وإعادة التعرّف: تقارن الأنظمة تضمين الصورة بمعرض للعثور على المنتج أو الوجه أو الشخص نفسه الذي رصدته كاميرا أخرى. ويُضمّن حل البحث بالتشابه من Ultralytics مجلدًا من الصور باستخدام CLIP من OpenAI، ويحسب تشابه كل صورة مفهرسة مع استعلام نصي مثل "سيارة حمراء" باستخدام التشابه الجيب التمام في بحث دقيق بالقوة الغاشمة، ثم يعيد أقرب النتائج، بحد أقصى 30 نتيجة افتراضيًا.