الجيران الأقرب (K-Nearest Neighbors)

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

كيف تعمل KNN

تعمل KNN من خلال تحديد أقرب ‘k’ نقاط بيانات إلى نقطة استعلام معينة واستخدام هؤلاء الجيران لاتخاذ قرار التنبؤ.

• في مهام التصنيف، تقوم الخوارزمية بإسناد نقطة الاستعلام إلى الفئة الأكثر شيوعاً بين أقرب ‘k’ جيران لها، ويُعرف ذلك بالتصويت بالأغلبية. يمكن فهم التصويت بالأغلبية في KNN على أنه “تصويت التعددية” عند التعامل مع فئات متعددة، حيث تُسند نقطة الاستعلام إلى الفئة التي لديها أعلى عدد بين جيرانها الأقرب، حتى لو لم تكن تشكل أغلبية مطلقة.
• في مهام الانحدار، تتنبأ الخوارزمية بالقيمة من خلال حساب متوسط قيم أقرب ‘k’ جيران.

مبادئ القرب والتشابه، والتي تعد جوهر الإدراك البشري، هي أيضاً مركزية في كيفية عمل KNN، حيث يُفترض أن نقاط البيانات القريبة في فضاء الميزات أكثر تشابهاً وبالتالي من المرجح أن يكون لها نتائج متشابهة.

مقاييس المسافة

لتحديد أقرب الجيران، تستخدم KNN العديد من مقاييس المسافة، والتي تعتبر حاسمة في أدائها:

• المسافة الإقليدية: هي المسافة المستقيمة بين نقطتين في فضاء متعدد الأبعاد، وتستخدم غالباً مع المتغيرات المستمرة. تعتبر المسافة الأكثر شيوعاً في KNN ومفيدة بشكل خاص عندما تكون البيانات كثيفة ومستمرّة.
• مسافة مانهاتن: تعرف أيضاً بمسافة سائق التاكسي، وتحسب المسافة عن طريق جمع الفروق المطلقة بين إحداثيات نقطتين. تكون مفيدة في السيناريوهات التي تشبه الشبكة، حيث تقتصر الحركات على اتجاهات متعامدة.
• مسافة مينكوفسكي: شكل عام لكل من المسافة الإقليدية ومانهاتن، وتُحدد بواسطة المعامل ‘p’. إذا كان p=1 تصبح مسافة مانهاتن، وإذا كان p=2 تصبح المسافة الإقليدية. تمنح هذه المسافة مرونة حسب قيمة ‘p’ المختارة.
• مسافة هامينغ: تُستخدم للبيانات الفئوية، حيث تحسب عدد البتات المختلفة بين متجهين ثنائيين. تعتبر مفيدة بشكل خاص في مشاكل التصنيف الثنائي حيث تكون القيم ثنائية.

اختيار القيمة المناسبة لـ ‘k’

المعامل ‘k’ في KNN يمثل عدد الجيران الذين يجب أخذهم في الاعتبار. اختيار القيمة الصحيحة لـ ‘k’ أمر بالغ الأهمية:

• القيمة الصغيرة لـ ‘k’ قد تؤدي إلى الإفراط في التكيّف، حيث يصبح النموذج حساساً جداً للضجيج في بيانات التدريب ويلتقط أنماطاً غير حقيقية لا تعمم بشكل جيد.
• القيمة الكبيرة لـ ‘k’ قد تؤدي إلى نقص التكيّف، إذ يصبح النموذج عاماً جداً ويتجاهل الأنماط المهمة، مما يؤدي إلى ضعف الأداء التنبؤي.
• عادةً ما يتم اختيار ‘k’ من خلال التحقق المتقاطع، ويفضل أن يكون عدداً فردياً لتجنب التعادل في قرارات التصنيف. يمكن أن يؤثر اختيار ‘k’ بشكل كبير على دقة النموذج وغالباً ما يتم تحديده تجريبياً.

المزايا والعيوب

المزايا

• بسيطة وبديهية: سهلة الفهم والتنفيذ، مما يجعلها خياراً جيداً للمبتدئين. تكمن بساطة KNN في أسلوبها المباشر الذي يقارن عينات الاختبار بالأمثلة المخزنة.
• لا تتطلب مرحلة تدريب: لا تحتاج KNN إلى مرحلة تدريب صريحة، إذ تقوم بالتنبؤات باستخدام مجموعة البيانات المخزنة. يمكن تحديث النموذج بسهولة من خلال إضافة نقاط بيانات جديدة إلى المجموعة.
• متعددة الاستخدامات: يمكن استخدامها لكل من مهام التصنيف والانحدار، وتتميز بتطبيقاتها الواسعة في مجالات مختلفة. كما أنها مفيدة في مشاكل التصنيف متعددة التسميات.

العيوب

• كثيفة الحساب: لأنها تتطلب تخزين ومقارنة كل نقطة بيانات جديدة مع جميع بيانات التدريب، قد تكون بطيئة وتستهلك الموارد، خاصة مع مجموعات البيانات الكبيرة. تعقيد الوقت في KNN هو O(n)، حيث n هو عدد عينات التدريب.
• حساسة للقيم الشاذة: يمكن أن تؤثر القيم الشاذة بشكل كبير على التنبؤات، إذ قد تؤدي هذه النقاط غير الطبيعية إلى تحريف النتائج، خاصة عندما يكون ‘k’ صغيراً.
• لعنة الأبعاد: في الفضاءات عالية الأبعاد، قد يتدهور أداء الخوارزمية لأن المسافات بين النقاط تصبح أقل معنى. فكلما زادت الأبعاد، زاد حجم الفضاء وتصبح البيانات متناثرة، مما يجعل من الصعب على KNN العثور على أقرب الجيران بشكل فعال.

حالات الاستخدام

تُستخدم KNN في العديد من المجالات نظراً لبساطتها وفعاليتها:

• أنظمة التوصية: تُستخدم في توصية المنتجات أو المحتوى للمستخدمين بناءً على تفضيلات مستخدمين مشابهين. تساعد KNN في تحديد المستخدمين أو العناصر المتشابهة من خلال تقييم تشابه الميزات.
• التعرف على الأنماط: تُطبق في التعرف على الكتابة اليدوية ومهام التعرف على الأنماط الأخرى، حيث يمكنها تصنيف الصور بناءً على تشابه قيم البكسل.
• استكمال البيانات الناقصة: مفيدة في ملء القيم المفقودة في مجموعات البيانات عن طريق تقديرها بناءً على نقاط بيانات مشابهة، مما يحافظ على تكامل البيانات.
• المالية والرعاية الصحية: تُستخدم في توقعات سوق الأسهم، وتقييم المخاطر، والتشخيص الطبي من خلال تحليل التشابه في البيانات التاريخية. في الرعاية الصحية، يمكنها التنبؤ بتشخيص المرضى من خلال مقارنة الأعراض مع حالات معروفة.

التنفيذ في بايثون

يمكن تنفيذ KNN باستخدام مكتبات مثل scikit-learn في بايثون. إليك مثالاً أساسياً لاستخدام KNN في التصنيف:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# تحميل مجموعة البيانات
iris = load_iris()
X, y = iris.data, iris.target

# تقسيم البيانات إلى مجموعتي تدريب واختبار
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# تهيئة مصنف KNN مع k=3
knn = KNeighborsClassifier(n_neighbors=3)

# تدريب النموذج
knn.fit(X_train, y_train)

# إجراء التنبؤات
y_pred = knn.predict(X_test)

# تقييم الدقة
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

الجيران الأقرب (KNN) في البحث العلمي

تُعد خوارزمية الجيران الأقرب (KNN) خوارزمية أساسية تُستخدم في مجالات متنوعة مثل استرجاع المعلومات المتعددة الوسائط، والتنقيب في البيانات، وتعلم الآلة، خاصةً في سياق مجموعات البيانات الكبيرة.

أوراق بحثية بارزة:

• “بناء رسم تقريبي للجيران الأقرب: نهج عام عبر الإنترنت” بقلم وان-لي تشاو وآخرين:
  يقدم طريقة فعّالة لكل من البحث التقريبي عن الجيران الأقرب وبناء الرسم البياني. توضح الورقة حلاً ديناميكياً وقابلاً للتطبيق للتعامل مع أحجام وأبعاد بيانات مختلفة، وتدعم التحديثات عبر الإنترنت التي لا تتوفر في العديد من الطرق الحالية. اقرأ المزيد.

• “الجيران الأقرب المتوازيون في الأبعاد المنخفضة مع التحديثات الدفعية” بقلم ماجدلين دوبسون وجاي بليلوك:
  تقدم خوارزميات متوازية تجمع بين شجرة kd وترتيب موريتون ضمن بنية شجرة zd، تم تحسينها للبيانات منخفضة الأبعاد. يوضح المؤلفان أن نهجهما أسرع من الخوارزميات الموجودة، ويحقق تسريعاً كبيراً عبر المعالجة المتوازية. تدعم شجرة zd التحديثات الدفعية المتوازية لأول مرة في هياكل بيانات الجيران الأقرب. اقرأ المزيد.

• “تحسين الانحدار بالجيران الأقرب بواسطة الشبكات العصبية التوأمية” بقلم سيباستيان جيه. ويتزل:
  يستكشف نهجاً جديداً لانحدار الجيران الأقرب باستخدام الشبكات العصبية التوأمية. يركز هذا الأسلوب على التنبؤ بالفروق بين أهداف الانحدار، مما يؤدي إلى أداء محسن مقارنةً بالشبكات العصبية التقليدية وتقنيات انحدار الجيران الأقرب على مجموعات البيانات الصغيرة والمتوسطة الحجم. اقرأ المزيد.