الانتقال إلى المحتوى
العودة إلى نتائج البحث

الجيران الأقرباء شبه المُشرف عليهم (Semi-supervised K-Nearest Neighbors)

قدّمه
Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
السنة
2002 (semi-supervised extension); 1967 (KNN base)
النوع
Semi-supervised classifier / label propagation
العائلة
Machine learning

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

يُوسّع خوارزمية الجيران الأقرباء شبه المُشرف عليهم (Semi-supervised KNN) خوارزمية الجيران الأقرباء الكلاسيكية للاستفادة من مجموعات كبيرة من البيانات غير المُصنفة جنبًا إلى جنب مع مجموعة صغيرة مُصنفة. من خلال بناء رسم بياني للـ KNN على جميع الملاحظات ونشر التصنيفات المعروفة عبر حواف الرسم البياني، تستنتج هذه الطريقة تصنيفات للنقاط غير المُصنفة دون الحاجة إلى التسمية اليدوية المكلفة لكل عينة.

الفكرة الحدسية وراء الطريقة

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

التاريخ

تم تنظيم انتشار التصنيفات على رسوم KNN البيانية بواسطة Zhu و Ghahramani في عام 2002، بناءً على آلة المتجهات الداعمة الاستنتاجية (transductive SVM) لفابنيك وأفكار الانتشار القائمة على الرسوم البيانية السابقة. تم توحيد الإطار في مجلد MIT Press التعلم شبه المُشرف (Chapelle et al., 2006)، والذي لا يزال المرجع القياسي. جعلت مكتبات KNN التقريبية القابلة للتطوير (FAISS, Annoy) النهج عمليًا على ملايين النقاط لاحقًا، ويستمر استخدامه كخط أساس قوي لتصنيف الصور والنصوص شبه المُشرف عليه.

متى تُستخدم

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

الحدود والاعتبارات

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

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

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

التطبيقات

  • تصنيف الصور باستخدام مجموعة صغيرة من الصور المُصنفة ومجموعة كبيرة غير مُصنفة.
  • تصنيف النصوص والمستندات حيث تكون التسمية اليدوية مكلفة.
  • تصنيف السجلات الطبية أو شرائح علم الأمراض مع تعليقات الخبراء المحدودة.
  • الكشف عن الاحتيال عندما يتوفر عدد قليل فقط من حالات الاحتيال المؤكدة.
  • تسمية بيانات المستشعرات في إعدادات إنترنت الأشياء الصناعية مع أحداث أرضية حقيقية متفرقة.

كيف يعمل

كيف يعمل

1

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

2

تلتقط أوزان الحواف قوة التشابه بين العقد المتصلة، عادةً عبر نواة غاوسية (RBF) مطبقة على المسافة الإقليدية بين متجهات الميزات. يتحكم معامل عرض النطاق sigma في مدى سرعة اضمحلال التشابه مع المسافة. تحمل الحواف الأقوى التصنيفات بسهولة أكبر أثناء الانتشار.

الصيغة
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)
3

تنتشر التصنيفات تكراريًا من العقد المصنفة إلى الجيران غير المصنفين. في كل تكرار، تقوم كل عقدة بتحديث توزيع التصنيف الناعم الخاص بها كمزيج مرجح من التوزيعات الحالية لجيرانها وتصنيفها الأولي الخاص بها (إذا كانت مصنفة). يوازن معامل الخلط alpha بين تأثير بنية الرسم البياني مقابل التصنيفات الصلبة، ويستمر التكرار حتى تتقارب التوزيعات.

الصيغة
F \leftarrow \alpha W D^{-1} F + (1-\alpha) Y
4

بمجرد تقارب الانتشار، يتم تعيين كل عقدة غير مصنفة للفئة ذات أعلى درجة تصنيف ناعم في توزيعها المتقارب. يتم تثبيت العقد المصنفة على تصنيفاتها الحقيقية طوال العملية، لذلك لا يتم تجاوز التصنيفات المعروفة أبدًا.

الصيغة
\hat{y}_i = \arg\max_c F_{ic}

الأخطاء الشائعة

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

الأسئلة الشائعة

كيف أختار k؟

ابدأ بـ k في النطاق 5-15 واضبطه بناءً على دقة التحقق المُصنفة المحتجزة. يعطي k الأصغر حدودًا أكثر حدة ومحلية؛ يسمح k الأكبر للتصنيفات بالانتشار لمسافة أبعد ولكنه يخاطر بعبور حدود الفئات الحقيقية.

هل يمكنني تقييم الطريقة بصدق عندما تكون معظم البيانات غير مُصنفة؟

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

ماذا لو كانت مجموعة البيانات الخاصة بي كبيرة جدًا بحيث لا يمكن بناء رسم KNN بياني كامل؟

استخدم مكتبات الجيران الأقرباء التقريبية مثل FAISS أو Annoy لبناء الرسم البياني في O(n log n) بدلاً من O(n^2)، ثم طبق انتشار التصنيفات على الرسم البياني التقريبي المتناثر.

هل يتفوق KNN شبه المُشرف عليه دائمًا على KNN المُشرف عليه؟

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

هل هذا هو نفسه انتشار التصنيفات أو انتشار التصنيف في scikit-learn؟

مرتبط ارتباطًا وثيقًا. تنفذ LabelPropagation و LabelSpreading في scikit-learn إطار عمل Zhu و Ghahramani باستخدام رسم بياني لنواة KNN أو RBF، لذا فهي تطبيقات مباشرة للطريقة الموصوفة هنا.

طرق ذات صلة

المصادر

  1. Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    افتح مرجع المنشور
    تم النسخ.
  2. Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ردمك: 978-0-262-03358-9
    تم النسخ.