ما المقصود بخوارزمية الجار الأقرب (KNN)؟

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

في مشكلات التصنيف، يتم تعيين تصنيف الفئة بناءً على تصويت الأغلبية، أي أن التصنيف الأكثر شيوعًا حول نقطة بيانات معينة هو الذي يتم اختياره. بينما يُعرف هذا من الناحية التقنية باسم "تصويت التعددية"، فإن مصطلح "تصويت الأغلبية" هو الأكثر شيوعًا في الأدبيات. الفرق بين هذه المصطلحات هو أن "تصويت الأغلبية" يتطلب من الناحية التقنية أغلبية تزيد عن 50%، ما يجعله مناسبًا بشكل أساسي عندما تكون هناك فئتان فقط. وعند وجود عدة فئات: على سبيل المثال، أربع فئات، لا تحتاج بالضرورة إلى 50% من الأصوات للتوصل إلى استنتاج حول فئة ما؛ يمكنك تعيين تصنيف فئة بتصويت أكبر من 25%. تلخص جامعة ويسكونسن ماديسون هذا جيدًا بمثال هنا.

تستخدِم مشكلات الانحدار مفهومًا مشابهًا لمشكلات التصنيف، ولكن في هذه الحالة، يتم أخذ متوسط جيران أقرب k لإجراء التنبؤ بشأن التصنيف. والتمييز الرئيسي هنا هو أن التصنيف يُستخدَم للقيم المنفصلة، بينما يُستخدم الانحدار مع القيم المستمرة. ومع ذلك، قبل إجراء التصنيف، يجب تحديد المسافة. المسافة الإقليدية هي الأكثر استخدامًا، وسنتناولها بمزيد من التفصيل أدناه.

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

يُنسب إلى Evelyn Fix وJoseph Hodges طرح الأفكار الأولية حول نموذج KNN في هذا البحث الصادر في عام 1951، بينما وسَّع Thomas Cover هذا المفهوم في بحثه Nearest Neighbor Pattern Classification. على الرغم من أنها لم تَعُد شائعة كما كانت من قبل، إلا أنها لا تزال واحدة من أولى الخوارزميات التي يتعلمها المرء في علم البيانات نظرًا لبساطتها ودقتها. ومع ذلك، مع نمو مجموعة البيانات، تصبح خوازرمية KNN غير فعَّالة بشكل متزايد، ما يؤثر في أداء النموذج بشكل عام. وهي تُستخدَم عادةً في أنظمة التوصيات البسيطة، والتعرُّف على الأنماط، والتنقيب عن البيانات، والتنبؤات في الأسواق المالية، وكشف التسلل، وغير ذلك.

للتلخيص، الهدف من خوارزمية k-nearest neighbor هو تحديد أقرب الجيران لنقطة استعلام معينة، حتى نتمكن من تعيين تسمية فئة لتلك النقطة. من أجل فعل ذلك، لدى KNN بعض المتطلبات:

لتحديد نقاط البيانات الأقرب إلى نقطة استعلام معينة، يجب حساب المسافة بين نقطة الاستعلام ونقاط البيانات الأخرى. تساعد مقاييس المسافة هذه على تكوين حدود القرار، والتي تقسِّم نقاط الاستعلام إلى مناطق مختلفة. سترى عادةً حدود القرار مرئية باستخدام مخططات Voronoi.

على الرغم من وجود العديد من مقاييس المسافة التي يمكنك الاختيار من بينها، فإن هذه المقالة ستغطي فقط ما يلي:

المسافة الإقليدية (p=2): تُعَد هذه أكثر مقاييس المسافة استخدامًا، وهي تقتصر على المتجهات ذات القيم الحقيقية. باستخدام الصيغة أدناه، تقيس خطًا مستقيمًا بين نقطة الاستعلام والنقطة الأخرى التي يتم قياسها.

مسافة مانهاتن (p=1): يُعَد هذا أيضًا من المقاييس الشائعة للمسافة، حيث يقيس القيمة المطلقة بين نقطتين. ويُشار إليه أيضًا باسم مسافة سيارات الأجرة أو مسافة الكتلة السكنية في المدينة حيث يتم تصورها عادةً باستخدام الشبكة، والتي توضح كيف يمكن للمرء أن يتنقل من عنوان إلى آخر عبر شوارع المدينة.

مسافة منكوفسكي: مقياس المسافة هذا هو الشكل المعمم لمقاييس المسافة الإقليدية ومقاييس مسافة مانهاتن. تسمح المعلمة p في الصيغة أدناه بإنشاء مقاييس مسافة أخرى. يتم تمثيل المسافة الإقليدية بهذه الصيغة عندما يكون p يساوي اثنين، ويُشار إلى مسافة مانهاتن بـ p يساوي واحدًا.

مسافة هامينج: تُستخدَم هذه التقنية عادةً مع المتجهات المنطقية أو النصية، حيث تُحدِّد النقاط التي لا تتطابق فيها المتجهات. ونتيجةً لذلك، تمت الإشارة إليه أيضًا باسم أحد المقاييس. يمكن تمثيل ذلك بالصيغة التالية:

على سبيل المثال، إذا كانت لديك السلاسل النصية التالية، فستكون مسافة هامينج تساوي 2؛ نظرًا لاختلاف قيمتين فقط.

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

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

للتعمق أكثر، يمكنك استكشاف خوارزمية k-NN عمليًا باستخدام Python ومكتبة scikit-learn (المعروفة أيضًا باسم sklearn). يساعدك البرنامج التعليمي الخاص بنا في Watson Studio على تعلم بناء الجملة الأساسي من هذه المكتبة، والتي تحتوي أيضًا على مكتبات أخرى شائعة، مثل NumPy، وpandas، وMatplotlib. الكود التالي هو مثال على كيفية إنشاء نموذج KNN والتنبؤ باستخدامه:

تم استخدام خوارزمية k-NN في مجموعة متنوعة من التطبيقات، إلى حد كبير ضمن التصنيف. تتضمن بعض حالات الاستخدام هذه ما يلي:

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

مثل أي خوارزمية تعلم آلي، تمتلك k-NN نقاط قوة وضعف. واعتمادًا على المشروع والتطبيق، قد تكون الخيار المناسب أو لا.

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

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