🤖 machine learning

ExDBSCAN: Explaining DBSCAN with Counterfactual Reasoning -- Additional Material

تقدم هذه الورقة ExDBSCAN، وهي طريقة تفسير لاحقة تستخدم نهجاً مضاداً للواقع مستوحى من الفيزياء ومعتمداً على الكثافة لتوفير تفسيرات صالحة ومتنوعة وقريبة لتعيينات مجموعات DBSCAN، متفوقةً بذلك على النماذج المرجعية الحالية عبر 30 مجموعة بيانات.

المؤلفون الأصليون: Pernille Matthews, Lena Krieger, Tommaso Amico, Artur Zimek, Thomas Seidl, Ira Assent

نُشر 2026-05-29

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Pernille Matthews, Lena Krieger, Tommaso Amico, Artur Zimek, Thomas Seidl, Ira Assent

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

إليك شرح لورقة بحث ExDBSCAN، مقسماً إلى مفاهيم بسيطة مع استخدام تشبيهات من الحياة اليومية.

المشكلة: "الصندوق الأسود" للتجميع (Clustering)

تخيل أنك تنظم حفلة ضخمة حيث يتم تقسيم الضيوف إلى دوائر بناءً على مدى تشابههم. أنت تستخدم طريقة شائعة تسمى DBSCAN للقيام بذلك. تتميز DBSCAN بقدرتها العالية على إيجاد مجموعات من الأشخاص يقفون بالقرب من بعضهم البعض في غرفة مزدحمة، حتى لو كانت أشكال المجموعات غريبة (مثل شكل حرف C أو حلزوني) بدلاً من الدوائر المثالية. كما أنها تحدد الأشخاص الذين يقفون بمفردهم في الزاوية كـ "ضجيج" (outliers).

المشكلة: بينما تبرع DBSCAN في عملية "التجميع"، إلا أنها سيئة جداً في "شرح" السبب.

إذا سألت: "لماذا تنتمي أليس إلى مجموعة 'محبي الموسيقى'؟"، ستجيب DBSCAN ببساطة: "لأنها قريبة من مركز تلك المجموعة".
إذا سألت: "لماذا يقف بوب وحيداً في الزاوية؟"، ستجيب DBSCN: "لأنه بعيد عن الجميع".
القطعة المفقودة: هي لا تخبرك ما هي "التغييرات المحددة" التي يحتاجها بوب لينضم إلى مجموعة ما. هل يحتاج لأن يرفع صوته؟ أم يرتدي قميصاً مختلفاً؟ أم يتحرك مترين إلى اليسار؟ بدون هذا، تبدو النتائج وكأنها خدعة سحرية بدلاً من كونها أداة مفيدة.

الحل: ExDBSCAN (دليل "ماذا لو")

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

تقوم الأداة بذلك عبر توليد "الواقعات المضادة" (Counterfactuals). وباللغة البسيطة، الواقع المضاد هو سيناريو "ماذا لو".

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

كيف تعمل: فيزياء الحفلة

الجزء الذكي في ExDBSCAN هو كيفية إيجاد هذه التغييرات. لم يستخدم المؤلفون رياضيات قياسية؛ بل استخدموا الفيزياء لنمذجة المشكلة. هم يتخيلون نقاط البيانات كجسيمات مشحونة في غرفة.

الهدف (القرب): أنت تريد أن يكون التغيير واقعياً. لا تريد أن تطلب من بوب أن "يصبح شخصاً آخر"، بل تريد منه فقط أن يتحرك قلي ลูก قليلاً.
- التشبيه: تخيل زنبركاً (Spring) يربط الشخص الواقف وحيداً (بوب) بالمجموعة التي يريد الانضمام إليها. هذا الزنبرك يريد أن يكون قصيراً، فهو يسحب بوب برفق نحو المجموعة، مما يضمن أن يكون التغيير ضئيلاً وواقعياً.
التنوع (Diversity): لا تريد إجابة واحدة فقط. أنت تريد معرفة كل الطرق المختلفة التي يمكن لبوب من خلالها الانضمام للمجموعة. ربياً يمكنه الانضمام بارتداء قبعة، أو بالتحرك لمكان أقرب، أو بتغيير نبرة صوته.
- التشبيه: تخيل أن المرشحين المحتملين لـ "بوب الجديد" هم مغانط لها نفس الشحنة. إذا وضعت مغناطيسين لهما نفس الشحنة بالقرب من بعضهما، فإنهما يتنافران (يدفعان بعضهما بعيداً). هذا يجبر سيناريوهات "ماذا لو" المختلفة على التباعد والتمايز عن بعضها البعض، بدلاً من أن تكون جميعها مجرد تغييرات طفيفة متطابقة.
الخريطة (الرسم البياني/Graph): تقوم DBSCAN بتجميع الناس بناءً على "الكثافة" (مدى ازدحام المنطقة)، وليس فقط المسافة المستقيمة. قد يكون شخصان قريبين في خط مستقيم، ولكن إذا كان هناك جدار (منطقة قليلة الكثافة) بينهما، فهما ليسا متصلين فعلياً.
- التشبيه: تقوم ExDBSCAN ببناء خريطة للحفلة تحترم الجدران والغرف المزدحمة. هي لا تقيس المسافة "كما يطير الغراب" (المسافة الإقليدية)؛ بل تقيس المسافة كـ "عدد الخطوات التي يجب أن أتخذها عبر الحشد للوصول إلى هناك؟". هذا يضمن أن النصيحة المقدمة قابلة للتطبيق فعلياً ضمن قواعد التجميع.

النتائج: لماذا هي أفضل؟

اختبر المؤلفون ExDBSCAN على 30 مجموعة بيانات مختلفة (مثل قوائم ضيوف حفلات متنوعة) وقارنوها بأربع طرق أخرى.

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

التعامل مع القواعد الواقعية

تذكر الورقة أيضاً أنه في بعض الأحيان لا يمكنك تغيير أشياء معينة.

التشبيه: تخيل أن بوب يبلغ من العمر 80 عاماً. لا يمكنك أن تطلب منه "أن يصبح في العشرين من عمره" ليتناسب مع مجموعة ما. هذه هي "الميزة غير القابلة للتغيير" (unactionable feature).
يمكن لـ ExDBSCAN التعامل مع هذا. فهي تعرف أن تبحث فقط عن التغييرات في الأشياء التي يمكن لبوب التحكم بها (مثل لون قميصه أو مكانه)، وتتجاهل الأشياء التي لا يمكنه تغييرها (مثل عمره).

الملخص

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

ملخص تقني: ExDBSCAN – شرح خوارزمية DBSCAN باستخدام الاستدلال المضاد للواقع

بيان المشكلة

يُعد التجميع (Clustering) تقنية أساسية في التعلم غير الخاضع للإشراف، ومع ذلك، فإنه يعاني من فجوة كبيرة في القابلية للتفسير مقارنة بالتعلم الخاضع للإشراف. وبينما أصبحت التفسيرات المضادة للواقع (Counterfactual Explanations - CEs) معيارًا لشرح النماذج الخاضعة للإشراف من خلال تحديد التغييرات الدنيا في المدخلات التي تغير التنبؤات، إلا أنها لا تنطبق بشكل مباشر على التجميع. وتظهر هذه الفجوة بوضوح في خوارزمية DBSCAN (التجميع المكاني القائم على الكثافة مع وجود ضجيج)، وهي خوارزمية شائعة قادرة على إيجاد عناقيد ذات أشكال عشوائية وتحديد الضجيج.

تقوم DBSCAN بتعيين النقاط كنقاط جوهرية (core)، أو حدودية (border)، أو ضجيج (noise) بناءً على إمكانية الوصول عبر الكثافة (density-reachability) المحددة بمعلمتي $\varepsilon$ و $minPts$. ومع ذلك، فهي لا تقدم أي رؤية حول لماذا حصلت نقطة معينة على هذا التعيين، أو ما إذا كان هذا التعيين متينًا تجاه التغييرات الطفيفة في البيانات. تواجه طرق التفسير المضاد للواقع الحالية ثلاث عقبات رئيسية عند تطبيقها على DBSCAN:

الافتقار إلى القابلية للاشتقاق: لا تستخدم DBSCAN دالة خسارة قابلة للاشتقاق، مما يمنع استخدام طرق البحث القائمة على التدرج (gradient-based) الشائعة في توليد التفسيرات المضادة للواقع الخاضعة للإشراف.
غياب الاحتمالات: على عكس نماذج التصنيف، توفر DBSCA عضويات منفصلة قائمة على الاتصال بدلاً من احتمالات الفئات المستمرة، وهو ما تعتمد عليه العديد من طرق التفسير المضاد للواقع المستقلة عن النموذج.
بنية التشابه المعقدة: تعني بنية الاتصال بالكثافة في DBSCAN أن نقطتين قد تكونان قريبتين في مسافة إقليدس، لكنهما بعيدتان فعليًا من حيث العضوية في العنقود (مما يتطلب مسار كثافة متصل طويل). تفشل مقاييس المسافة الإقليدية القياسية المستخدمة في طرق التفسير الأخرى في التقاط هذا، مما قد يؤدي إلى توليد تفسيرات مضادة للواقع زائدة عن الحاجة أو غير صالحة.

المنهجية: ExDBSCAN

يقترح المؤلفون ExDBSCAN، وهو أول طريقة تفسير "بعد الحدث" (post-hoc) مصممة خصيصًا لـ DBSCAN. تقوم هذه الطريقة بتوليد تفسيرات مضادة للواقع قابلة للتنفيذ لكل من الانتقال من "الضجيج إلى العنقود" ومن "عنقود إلى آخر" مع ضمانات نظرية للصلاحية.

المكونات الأساسية

تمثيل التشابه القائم على الرسم البياني (Graph-Based Similarity Representation):
بدلاً من الاعتماد على المسافة الإقليدية، يقوم ExDBSCAN بنمذجة بنية العنقود كرسم بياني موجه غير موجه وثقل $G(V, E)$ .
- الرؤوس ( $V$ ): تمثل النقاط الجوهرية للعنقود.
- الحواف: تربط بين رأسين إذا كانا قابلين للوصال مباشرة عبر الكثافة (المسافة $< \varepsilon$ ).
- الأوزان: هي المسافة الإقليدية بين النقاط الجوهرية المتصلة.
- مقياس المسافة: تُعرف المسافة بين أي نقطتين بأنها أقصر مسار مرجح في الرسم البياني $G$ . يضمن هذا أن "القرب" يحترم بنية الاتصال بالكثافة للعنقود.
التحسين المستوحى من الفيزياء:
لتوليد مجموعة من $k$ من التفسيرات المضادة للواقع المتنوعة والقريبة، يقوم ExDBSCAN بنمذجة اختيار النقاط الجوهرية المرجعية كمسألة تقليل طاقة فيزيائية. يتعامل النظام مع النقاط الجوهرية المرشحة كجسيمات مشحونة تخضع لقوتين:
- التنافر (التنوع): يتم نمذجته وفقًا لقانون كولوم، حيث تتنافر النقاط الجوهرية المرشحة مع بعضها البعض. قوة التنافر تتناسب عكسيًا مع المسافة المرجحة لأقصر مسار بينها. يضمن هذا توزيع التفسيرات المختارة على مساحة واسعة عبر بنية الكثافة للعنقود، لتجنب التكرار.
- التجاذب (القرب): يتم نمذجته وفقًا لقانون هوك (قوى الزنبرك)، حيث تنجذب النقاط الجوهرية المرشحة إلى النقطة الأصلية $p$ المراد شرحها. تزداد القوة خطيًا مع المسافة، مما يوجه الاختيار نحو أقرب النقاط الجوهرية الصالحة.

تُعرف الطاقة الإجمالية $E_{C'}$ لمجموعة من النقاط الجوهرية المختارة $C'$ كالتالي:
$E_{C'} = \sum_{V_i \in C'} \sum_{V_j \in C': j > i} \frac{1}{D(V_i, V_j)} + \sum_{V_i \in C'} d^2(p, V_i)$
حيث $D$ هي مسافة الرسم البياني المرجح و $d$ هي المسافة الإقليدية للنقطة الأصلية.

التحسين والبناء:
- صعوبة المسائل (NP-Hardness): ثبت أن إيجاد المجموعة المثلى من النقاط الجوهرية لتقليل هذه الطاقة هو مسألة من نوع NP-hard. يستخدم ExDBSCAN خوارزمية جشعة (greedy algorithm) لتقريب الحل. حيث يختار بشكل تكراري النقطة الجوهرية التي تقلل إجمالي طاقة النظام بناءً على المجموعة المختارة حاليًا.
- توليد التفسير المضاد للواقع: بمجرد اختيار مجموعة من النقاط الجوهرية المرجعية، يتم بناء التفسيرات المضادة للواقع النهائية ضمن جوار $\varepsilon$ لهذه النقاط الجوهرية. وتحديدًا، يتم وضع التفسير المضاد للواقع $p'$ عند مسافة $\varepsilon$ من النقطة الجوهرية المرجعية $q$ في اتجاه النقطة الأصلية $p$ .
- ضمان الصلاحية: من خلال البناء، يقع كل تفسير مضاد للواقع مُولد ضمن مسافة $\varepsilon$ من نقطة جوهرية في العنقود المستهدف، مما يضمن استيفاء معايير الاتصال بالكثافة الخاصة بـ DBSCAN وكونه عضوًا صالحًا في العنقود المستهدف.
التعامل مع القيود:
تأخذ الطريقة في الاعتبار السمات غير القابلة للتغيير (مثل العمر، الجنس) من خلال تقييد مساحة البحث. فهي تقوم بتصفية النقاط الجوهرية بحيث يمكن الوصول إلى جوار $\varepsilon$ الخاص بها دون تعديل السمات غير القابلة للتغيير، مما يضمن بقاء التفسيرات واقعية.

المساهمات الرئيسية

أول طريقة مخصصة لـ DBSCAN: يعد ExDBSCAN أول طريقة مصممة لتوليد التفسيرات المضادة للواقع خصيصًا للتجميع القائم على الكثافة، بما يشمل الانتقال من الضجيج إلى العنقود ومن عنقود إلى آخر.
نموذج مبتكر مستوحى من الفيزياء: قدم المؤلفون نموذجًا يوازن بين القرب والتنوع باستخدام التنافر الكهروستاتيكي والتجاذب الشبيه بالزنبرك، مع مراعاة بنية الاتصال بالكثافة لـ DBSCAN صراحةً عبر رسم بياني مرجح.
الصلاحية النظرية: توفر الطريقة ضمانًا نظريًا (النظرية 3.1) بأن كل تفسير مضاد للواقع مُولد هو صالح بموجب قواعد تعيين DBSCAN.
التفوق التجريبي: أظهر التقييم الموسع على 30 مجموعة بيانات جدولية أن ExDBSCAN يتفوق على النماذج المرجعية الموجودة (بما في ذلك الطرق المستقلة عن النموذج مثل BayCon و DiCE و Growing Spheres) من حيث الصلاحية، والقرب، والتنوع.

النتائج التجريبية

قيم المؤلفون ExDBSCAN على 30 مجموعة بيانات من OpenML مقابل سبعة نماذج مرجعية (بما في ذلك DiCE و BayCon و Growing Spheres والنسخ العشوائية).

الصلاحية (Validity): حقق ExDBSCAN صلاحية بنسبة 100% عبر جميع الاستعلامات. في المقابل، واجهت الطرق القائمة على النماذج البديلة (DiCE-Surrogate, GS-Surrogate) والطرق المستقلة عن النموذج (BayCon) صعوبات كبيرة، حيث حققت غالبًا معدلات صلاحية أقل من 50%. ويُعزى ذلك إلى عدم التطابق بين أهداف التحسين المستمرة الخاصة بها وبين تعيينات DBSCAN المنفصلة القائمة على الكثافة.
القرب (Proximity): من بين الطرق التي حققت صلاحية عالية، أنتج ExDBSC تفسيرات مضادة للواقع أقرب بكثير من الحالات الأصلية مقارنة بالمنافسين. ويُعزى ذلك إلى التحسين الصريح لعنصر التجاذب الشبيه بالزنبرك باستخدام المسافة القائمة على الرسم البياني.
التنوع (Diversity): حقق ExDBSCAN أعلى درجات التنوع. فقد ضمنت آلية التنافر الخاصة به، القائمة على المسافة المرجحة لأقصر مسار داخل رسم العنقود البياني، أن التفسات المضادة للواقع المختارة تمثل بدائل متميزة داخل طوبولوجيا العنقود، وليس مجرد كونها قريبة في مسافة إقليدس.
وقت التشغيل (Runtime): بينما يعد ExDBSCAN أكثر استهلاكًا للحوسبة من الهيورستيك العشوائي البسيط، إلا أنه أسرر بشكل عام من التحسين الثقيل المطلوب من DiCE و BayCon، خاصة عندما تفشل تلك الطرق في إيجاد تفسيرات مضادة للواقع صالحة.

الأهمية والادعاءات

تضع الورقة البحثية ExDBSCAN كخطوة حاسمة نحو سد فجوة التفسير في التعلم غير الخاضع للإشراف. ويدعي المؤلفون أنه من خلال الاستفادة من الاستدلال المضاد للواقع المصمم خصيصًا لآليات DBSAN، يمكن للممارسين الحصول على:

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

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