الجار الأقرب (K-Nearest Neighbors - KNN)
- قدّمه
- Cover, T.M. & Hart, P.E.
- السنة
- 1967
- النوع
- Instance-based (non-parametric) learning
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
يُعدّ الجار الأقرب (K-Nearest Neighbors - KNN)، الذي صاغه كوفير وهارت في عام 1967، طريقة غير بارامترية تعتمد على الأمثلة، وتصنف أو تتنبأ بملاحظة جديدة من خلال النظر إلى أقرب k مثال في بيانات التدريب. للتصنيف، تأخذ تصويت الأغلبية بين هؤلاء الجيران؛ وللانحدار، تحسب متوسط قيمهم.
الفكرة الحدسية وراء الطريقة
الفكرة بسيطة: المدخلات المتشابهة تميل إلى أن تكون لها مخرجات متشابهة. لتسمية نقطة جديدة، يحدد KNN حفنة من أمثلة التدريب التي تقع الأقرب إليها في فضاء السمات، ويتركها تتخذ القرار. لا توجد معادلة مُلائمة مسبقًا - بيانات التدريب نفسها هي النموذج، ولا يتم إجراء التنبؤ إلا عند وصول نقطة جديدة.
التاريخ
تم إعطاء تصنيف الأنماط بالجار الأقرب أساسه الإحصائي الرسمي من قبل توماس كوفير وبيتر هارت في ورقتهما البحثية عام 1967 في مجلة IEEE Transactions on Information Theory، والتي حللت معدل الخطأ لقاعدة الجار الأقرب. أصبح KNN أحد أقدم طرق التعلم القائمة على الأمثلة وأكثرها ديمومة ولا يزال مصنفًا أساسيًا قياسيًا.
متى تُستخدم
استخدم KNN للتصنيف أو التنبؤ على البيانات الجدولية ذات السمات المستمرة أو الثنائية أو الترتيبية وحوالي 30 ملاحظة على الأقل. لا يفترض أي توزيع معين، ولكنه يتطلب أن تكون السمات موحدة وأن يظل عدد السمات صغيرًا بالنسبة لحجم العينة (يفضل p أقل بكثير من n). في العينات الصغيرة أو عالية الأبعاد، تهيمن لعنة الأبعاد - تصبح مسافات الجوار غير مفيدة - ويكون النموذج البارامتري مثل الانحدار اللوجستي أو بايز الساذج هو الخيار الأفضل.
الحدود والاعتبارات
- حساسة لمقياس السمات؛ بدون توحيد، تهيمن السمات ذات المقياس الكبير على المسافة.
- تتدهور بسرعة في الأبعاد العالية (لعنة الأبعاد)، حيث تفقد مسافات الجوار معناها.
- يتطلب كل تنبؤ مسح مجموعة التدريب بأكملها، وهو أمر بطيء في وقت التنبؤ على البيانات الكبيرة.
- تحتاج إلى حجم عينة معتدل على الأقل؛ في العينات الصغيرة، مسافات الجار الأقرب ليست ذات مغزى.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- بسيطة من الناحية المفاهيمية وسهلة الشرح: لا توجد معادلة وقت التدريب، البيانات هي النموذج.
- غير بارامترية - لا تفترض أي شيء عن التوزيع الأساسي.
- تتعامل بشكل طبيعي مع المشكلات متعددة الفئات والحدود القرار المعقدة وغير الخطية.
- تعمل لكل من التصنيف والانحدار بنفس الفكرة الأساسية.
التطبيقات
- تصنيف البيانات الجدولية إلى فئتين أو أكثر.
- التنبؤ الرقمي (الانحدار) عن طريق حساب متوسط الأمثلة الأقرب.
- خط أساس بسيط وقابل للتفسير قبل تجربة نماذج أكثر تعقيدًا.
- التعرف على الأنماط حيث التشابه مع الأمثلة المعروفة يدفع القرار.
كيف يعمل
كيف يعمل
بالنسبة لملاحظة جديدة، يقيس KNN مدى بعدها عن كل مثال تدريبي، عادةً باستخدام المسافة الإقليدية عبر السمات. نظرًا لأن المسافة حساسة للمقياس، يجب توحيد السمات أولاً - وإلا فإن متغيرًا مقاسًا على مقياس رقمي كبير سيهيمن على الحساب ويشوه الجيران الذين يُعتبرون الأقرب.
الصيغة
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}يتم اختيار نقاط التدريب k ذات المسافات الأقل إلى الملاحظة الجديدة كجيران لها. تتحكم قيمة k في مدى محلية القرار: k صغيرة تتبع البيانات عن كثب ولكنها حساسة للضوضاء، بينما k كبيرة تنعم الحدود. يجب اختيار k عن طريق التحقق المتقاطع (على سبيل المثال، طريقة الكوع) بدلاً من التخمين.
يحدد الجيران التنبؤ: للتصنيف، تأخذ النقطة الجديدة الفئة الأكثر شيوعًا بين جيرانها k (تصويت الأغلبية)، وللانحدار، تأخذ متوسط قيمهم. هذا يجعل الطريقة سهلة الفهم، ولكن كل تنبؤ يتطلب مسح مجموعة التدريب.
الصيغة
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}الأخطاء الشائعة
- تخطي توحيد السمات، بحيث تتحكم متغيرات ذات مقياس كبير بصمت في المسافة.
- اختيار k يدويًا بدلاً من تحديده بالتحقق المتقاطع.
- تطبيق KNN مع العديد من السمات وعدد قليل من الملاحظات، حيث تتسبب نسبة البعد/العينة في فشلها.
- الإبلاغ عن الدقة فقط بدلاً من الدقة، الاستدعاء، F1، ومصفوفة الارتباك.
الأسئلة الشائعة
كيف أختار قيمة k؟
يجب اختيار k بالتحقق المتقاطع بدلاً من التخمين - على سبيل المثال، عن طريق تجربة نطاق من القيم واستخدام طريقة الكوع للعثور على المكان الذي يتوقف فيه الخطأ عن التحسن. k صغيرة تتبع البيانات عن كثب ولكنها حساسة للضوضاء، بينما k كبيرة تنعم حدود القرار.
لماذا يجب علي توحيد السمات؟
يحدد KNN من هو "الأقرب" باستخدام المسافة، وهي حساسة للمقياس. إذا كان أحد السمات على مقياس رقمي أكبر بكثير من الآخرين، فإنه يهيمن على المسافة ويشوه مجموعة الجيران. توحيد السمات (على سبيل المثال باستخدام StandardScaler) مطلوب حتى تساهم كل سمة بشكل عادل.
لماذا يعاني KNN مع العديد من السمات؟
في المساحات عالية الأبعاد، تصبح جميع النقاط متساوية البعد تقريبًا - لعنة الأبعاد - لذا فإن الجيران "الأقرب" لم يعودوا قريبين بشكل مفيد. ينخفض أداء KNN بسرعة، وعادة ما يكون النموذج البارامتري مثل بايز الساذج أو الانحدار اللوجستي مفضلاً. يساعد الاحتفاظ بـ p أقل بكثير من n.
هل هناك خطوة تدريب؟
ليس بالمعنى المعتاد. KNN يعتمد على الأمثلة (كسول): فهو ببساطة يخزن بيانات التدريب ويقوم بكل العمل في وقت التنبؤ، عندما يحسب المسافات للعثور على أقرب جيران لنقطة جديدة.
طرق ذات صلة
المصادر
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
افتح مرجع DOIتم النسخ.