تصنيف الأنماط بالجار الأقرب

قاعدة الجار الأقرب من أبسط أفكار التصنيف على الإطلاق. الفكرة كالتالي: لديك مجموعة نقاط تدريب مُصنَّفة $(x_1, \theta_1), (x_2, \theta_2), \ldots, (x_n, \theta_n)$، كل نقطة $x_i$ تقع في فضاء متري ما، و$\theta_i$ هو تصنيفها. حين تأتيك نقطة جديدة $x$، ابحث عن أقرب نقطة لها $x'$ في بيانات التدريب وأعطها التصنيف نفسه $\theta'$. هذا كل ما في الأمر.

لا معاملات تُقدَّر، ولا توزيعات تُفترض، ولا عملية أمثَلة تعمل في الخلفية. القاعدة تعمل في أي فضاء يمكنك فيه قياس المسافة — سواء كان الفضاء الإقليدي، أو مسافة تحرير النصوص، أو حتى فضاءات مترية مجردة.

هذا ما يجعلها مُصنِّفاً لامعاملياً: لا تفترض شكلاً محدداً لـالتوزيع الاحتمالي الكامن وراء البيانات. البيانات وحدها هي التي تحدد القرار.

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

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

الملاحظة المهمة هنا: كلما أضفت نقاط تدريب جديدة، تتقلّص خلايا فورونوي ويزداد حد القرار دقة وتفصيلاً — فيتكيّف مع الشكل الحقيقي لمناطق الفئات من تلقاء نفسه، دون أن تحتاج إلى تحديد شكل الحد مسبقاً.

السؤال الذي انطلق منه كَفر وهارت واضح ومباشر: ما أسوأ ما يمكن أن تُقدّمه قاعدة الجار الأقرب مقارنةً بأفضل مُصنِّف ممكن نظرياً؟

أفضل مُصنِّف ممكن هو مُصنِّف بايز الأمثل، وهو مُصنِّف افتراضي يعرف التوزيع الاحتمالي الحقيقي $P(y|x)$ ويختار دائماً الفئة الأكثر احتمالاً. معدل خطئه $R^*$ يمثّل الحد الأدنى المطلق الذي لا تستطيع أي خوارزمية تجاوزه — فهو يعكس الضوضاء الأصيلة في البيانات نفسها.

قاعدة الجار الأقرب لا تعرف $P(y|x)$ أصلاً، فالتوقع الطبيعي أن يكون خطؤها أكبر بكثير. لكنّ كَفر وهارت أثبتا نتيجة مُدهشة: مع بيانات تدريب لا نهائية، يخضع خطأ الجار الأقرب $R$ لمتباينة مزدوجة مُحكَمة.

ما المعنى العملي لهذه النتيجة؟ لو كان خطأ بايز 10%، فخطأ الجار الأقرب لن يتجاوز 18%. ولو كان خطأ بايز 0% — أي أنّ الفئات قابلة للفصل تماماً — فالجار الأقرب أيضاً يحقق 0%. وفي الطرف الآخر، لو كان خطأ بايز 50% — ضوضاء بحتة بلا أي معلومات تصنيفية — فالجار الأقرب يُعطي 50% كذلك. عند الحدّين المتطرفين يتطابق الأداء تماماً مع بايز، وبينهما يكون أسوأ بعامل لا يتجاوز 2.

في حالة $M$ فئة يتعمّم الحد:

البرهان يعتمد على حجّة مُقاربية أنيقة. الفكرة الأساسية: كلما ازداد عدد نقاط التدريب بحيث $n \to \infty$، يقترب الجار الأقرب $x'$ لأي نقطة اختبار $x$ من النقطة $x$ نفسها — في أي توزيع مستمر. عملياً إذن، القاعدة تُجري سحبين مستقلين من التوزيع عند الموضع $x$: التصنيف الحقيقي لنقطة الاختبار، والتصنيف الحقيقي للجار.

متى تُخطئ القاعدة؟ حين يختلف هذان السحبان. في التصنيف الثنائي مع احتمال خلفي $p = P(y=1|x)$، يكون الخطأ الشرطي:

$r(x) = p(1-p) + (1-p)p = 2p(1-p)$

هذا بالضبط احتمال أن تعطي رميتا عملة مستقلتان — بانحياز $p$ — نتيجتين مختلفتين. قارن ذلك بخطأ بايز عند النقطة نفسها: $r^*(x) = \min(p, 1-p)$.

حين نحسب المتوسط على كامل فضاء المدخلات نحصل على الحد الشامل $R \leq 2R^*(1-R^*)$. الفكرة المحورية: الجار الأقرب يرتكب بالضبط الخطأ المتوقع حين تملك تصنيفين مُشوَّشَين بدلاً من معرفة الاحتمال الحقيقي — وهذا أسوأ بالضعف فحسب.

إذا كان جار واحد يلتقط نصف المعلومات، فالسؤال الطبيعي: ماذا لو استشرنا $k$ جيران بدلاً من واحد؟ هذا هو التوسيع المنطقي — قاعدة الجيران الأقرب k (k-NN): ابحث عن أقرب $k$ نقطة تدريب وأعطِ نقطة الاختبار تصنيف الأغلبية بينها.

كلما ازداد $k$ — بشرط أن تبقى النسبة $k/n \to 0$ — يتقارب خطأ k-NN نحو خطأ بايز $R^*$ ذاته، وليس مجرد ضعفه. أثبت ستون ذلك عام 1977 بصرامة رياضية، وبيّن أنّ k-NN يتمتع بـاتساق عالمي: يتقارب نحو المُصنِّف الأمثل لـكل توزيع احتمالي ممكن، بلا أي افتراضات.

المُقايضة بين الانحياز والتباين واضحة هنا: $k$ صغير يُنتج حد قرار مرناً لكن مُضطرباً (تباين عالٍ، انحياز منخفض). $k$ كبير يُنتج حداً أنعم (تباين منخفض، انحياز أعلى). النقطة المثلى تعتمد على طبيعة البيانات — وعادةً ما تقع بين 3 و15.

قاعدة الجار الأقرب تقوم على افتراض ضمني واحد فقط: أنّ النقاط القريبة في فضاء السمات تحمل تصنيفات متشابهة. اختيار مقياس المسافة هو ما يُحدِّد معنى «القرب»، وله تأثير حاسم في جودة التصنيف.

الخيار الأكثر شيوعاً هو المسافة الإقليدية: $d(x, x') = \sqrt{\sum_i (x_i - x'_i)^2}$. لكنّ مقاييس أخرى قد تناسب بيانات معينة بشكل أفضل. مسافة مانهاتن ($L_1$) تجمع الفروقات المطلقة وتكون أكثر مقاومة لـالقيم الشاذة في السمات المنفردة. مسافة مينكوفسكي ($L_p$) تُعمِّم كلتيهما. أما في النصوص، فيُقاس تشابه جيب التمام الذي يهتم بالزاوية بين المتجهات ويتجاهل حجمها.

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

حد كَفر-هارت يفترض بيانات تدريب لا نهائية. لكن في الواقع البيانات محدودة، وقد لا يكون الجار الأقرب قريباً بالمعنى الفعلي — خصوصاً حين يكون عدد الأبعاد كبيراً.

في فضاء بـ$d$ بُعد، تحتاج عدداً من العيّنات ينمو أُسِّيّاً مع $d$ لمجرد الحفاظ على كثافة معقولة حول أي نقطة اختبار. في مكعب فائق وحدوي ذي 100 بُعد مثلاً، حتى مليون نقطة تبقى متناثرة — المسافة إلى أقرب جار تصبح كبيرة، وافتراض أنّ القرب في السمات يدل على تشابه التصنيفات ينهار.

هذا ما يُعرف بـ**لعنة الأبعاد**. مع ازدياد عدد الأبعاد، تتركّز جميع المسافات الزوجية حول قيمة واحدة، فتفقد كلمة «الأقرب» معناها. النسبة بين أبعد نقطة وأقرب نقطة تقترب من 1، ويصبح الجار الأقرب لا يحمل معلومات تزيد عمّا تحمله نقطة تدريب مختارة عشوائياً.

في k-NN القياسي، كل جار يحصل على صوت واحد بغض النظر عن بُعده. لكنّ المنطق يقول إنّ جاراً على مسافة 0.1 يجب أن يكون أكثر تأثيراً من جار على مسافة 5.0. هذا هو مبدأ k-NN الموزون بالمسافة: كل جار يحصل على وزن يتناسب عكسياً مع مسافته:

$w_i = 1 / d(x, x_i)$

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

قبل ورقة كَفر وهارت، كان الوضع النظري للأساليب اللامعاملية ضبابياً. المهندسون كانوا يستخدمون قاعدة الجار الأقرب في التطبيقات العملية منذ أن اقترحها فيكس وهودجز عام 1951، لكن لم يكن أحد قد أثبت رياضياً كم هي جيدة مقارنةً بالحد الأمثل النظري.

مبرهنة كَفر-هارت منحت التصنيف اللامعاملي أول أساس نظري متين. أظهرت أنّ الأساليب البسيطة التي لا تعتمد على أي افتراضات تملك ضمانات أداء مُثبتة رياضياً — وهذه نتيجة شكّلت عقوداً من البحث في نظرية التعلّم الإحصائي، بدءاً من تطوير أساليب النواة وصولاً إلى نظرية الاتساق في التعلّم الآلي.

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