📊 statistics

Partition Tree: Conditional Density Estimation over General Outcome Spaces

تقدم الورقة البحثية "شجرة التقسيم" (Partition Tree)، وهو إطار عمل غير معلمي مبتكر يقدر الكثافات الشرطية عبر فضاءات مخرجات عامة من خلال تعلم تقسيمات متكيفة مع البيانات لتقليل سلب لوغاريتم الاحتمالية، إلى جانب امتداد التجميع الخاص بها، "غابة التقسيم" (Partition Forest)، والتي تُظهر أداءً فائقاً في التنبؤ الاحتمالي مقارنة بالطرق القائمة على الأشجار وطرق "الغابة العشوائية" (Random Forest) الحالية.

المؤلفون الأصليون: Felipe Angelim, Alessandro Leite

نُشر 2026-05-13

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

CC BY 4.0

المؤلفون الأصليون: Felipe Angelim, Alessandro Leite

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

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

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

تقدم هذه الورقة أداة جديدة تسمى شجرة التقسيم (Partition Tree) (ونسختها الجماعية غابة التقسيم - Partition Forest) والتي تعمل كصانعة خرائط ذكية ومرنة للغاية. وإليك كيف تعمل، باستخدام تشبيهات بسيطة:

1. "الخريطة الذكية" بدلاً من "التخمين الواحد"

فكر في بياناتك كغرفة ضخمة مليئة بالناس (المدخلات) وحالاتهم المزاجية (النتيجة).

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

2. نهج "قطع الليغو" (الثابت جزئياً)

تصف الورقة النموذج بأنه "ثابت جزئياً" (piecewise-constant). تخيل أنك تبني جداراً من قطع الليغو.

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

3. التعامل مع "المكونات المختلطة"

أحد أكبر الصداع في علم البيانات هو التعامل مع أنواع مختلفة من البيانات في وقت واحد: الأرقام (مثل العمر أو درجة الحرارة) والفئات (مثل "أحمر"، "أزرق"، أو "نعم"، "لا").

الابتكار: تعامل "شجرة التقسيم" كلا النوعين من البيانات بلغة موحدة. يمكنها تقسيم البيانات بناءً على رقم (مثلاً: "هل العمر > 30؟") أو فئة (مثلاً: "هل اللون أزرق؟") ومع ذلك تبني نفس نوع "خريطة المزاج" للنتيجة. هي لا تحتاج لترجمة كل شيء إلى أرقام أولاً؛ بل تعمل ببساطة مع ما تقدمه لها.

4. البناء بأسلوب "الأفضل أولاً"

كيف تقرر الشجرة أين تقوم بالتقسيم؟

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

5. "الغابة" (Bagging)

تماماً كما يمكن لشجرة واحدة أن تكون متذبذبة أحياناً، ابتكر المؤلفون غابة التقسيم (Partition Forest).

هذا يشبه طلب 100 طاهٍ مختلف لبناء خرائطهم الخاصة لنفس كومة الفاكهة.
بدلاً من اختيار الخريطة "الأفضل"، تأخذ جميع الخرائط المائة وتخرج متوسطها.
النتيجة: هذه "الغابة" أكثر استقراراً وموثوقية. في تجارب الورقة، تفوقت هذه "الغابة" باستمرار على "الغابات العشوائية" (Random Forests) -وهي المعيار الصناعي لهذا النوع من المشكلات- في التنبؤ بالاحتمالات، خاصة عندما كانت البيانات فوضوية أو مشوشة.

6. ماذا أظهرت التجارب؟

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

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

الخلا الخلاصة

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

ملخص تقني: شجرة التقسيم (Partition Tree): تقدير الكثافة الشرطية عبر فضاءات النتائج العامة

بيان المشكلة

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

الافتراضات البارامترية (المعلمية): تستخدم طرق مثل CADET كثافات شرطية بارامترية عند أوراق الشجر، والتي قد لا تستطيع التقاط التوزيعات المعقدة غير الغاوسية (non-Gaussian).
القابلية للتوسع: الطرق مثل CDTree، التي تحسن عمليات التقسيم والمخططات التكرارية (histograms) لكل ورقة بشكل مشترك، يمكن أن تكون مكلفة حاسوبياً، مما يحد من قابليتها للتطبيق على مجموعات البيانات الكبيرة.
الصياغة الموحدة: هناك نقص في إطار عمل موحد يعامل التصنيف والانحدار كحالات خاصة من تقدير الكثافة الشرطية دون فرض قيود بارامترية على توزيع الهدف.

المنهجية

1. الإطار النظري: الصياغة القائمة على نظرية القياس

يقترح المؤلفون شجرة التقسيم (Partition Tree)، وهو إطار عمل قائم على نظرية القياس.

تقسيم الفضاء المشترك: على عكس الأشجار التقليدية التي تقسم فقط فضاء المتغيرات المستقلة $X$ ، تقوم شجرة التقسيم ببناء تقسيم متكيف مع البيانات $\pi_N$ لفضاء المتغيرات المستقلة والنتائج المشترك $Z = X \times Y$ .
التقدير الثابت جزئياً: يتم نمذجة الكثافة الشرطية $f(y|x)$ كدالة ثابتة جزئياً معرفة على هذه التقسيمات.
مشتق رادون-نيكوديم (Radon–Nikodym Derivative): تُعرف الطريقة الكثافة الشرطية عبر مشتق رادون-نيكوديم بالنسبة لمقياس حاصل الضرب $\nu = P_X \otimes \mu_Y$ ، حيث $\mu_Y$ هو مقياس مرجعي (مقياس العد للنتائج المنفصلة، ومقياس ليبيج للمستمرة).
المُقدِّر (Estimator): بالنسبة لخلية $A = A_X \times A_Y$ في التقسيم، يكون تقدير الكثافة:
$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$
حيث $n_{XY}$ و $n_X$ هي الأعداد التجريبية. هذه الصياغة تتعامل طبيعياً مع الأنواع المختلطة من النتائج وتسمح بظهور التصنيف والانحدار كحالات خاصة.

2. خوارزمية بناء الشجرة

يتم نمو الشجرة باستخدام استراتيجية جشعة قائمة على البحث الأفضل (best-first strategy) تعمل مباشرة على تقليل اللوغاريتم السالب للاحتمالية الشرطية.

الهدف: معيار التقسيم يعظم الربح التجريبي في خسارة اللوغاريتم (log-loss):
$\hat{G}(\pi', \pi) = \sum_{A' \in \{A_l, A_r\}} \frac{n_{XY}(A')}{N} \log \left( \frac{n_{XY}(A')}{n_X(A') \mu_Y(A'_Y)} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$
أنواع التقسيم:
- تقسيم المتغيرات المستقلة ( $X$ ): يعمل على تكرير فضاء المتغيرات المستقلة (تقسيمات الأشجار القياسية).
- تقسيم النتائج ( $Y$ ): يعمل على تكرير حاويات النتائج (bins) داخل منطقة ثابتة للمتغيرات المستقلة. وهذا يسمح للشجرة ببناء مخططات تكرارية (histograms) للتوزيع الناتج بشكل متكيف.
الكفاءة: تستخدم الخوارزمية تقنيات الفرز والجمع التراكمي (prefix-sum) الفعالة لتقييم التقسيمات المرشحة في زمن قدره $O(d_Z N \log N)$ (أو $O(d_Z N \log^2 N)$ للأشجار المتوازنة)، مما يطابق قابلية التوسع لأشجار CART القياسية.
القطع (Truncation): بالنسبة للنتائج المستمرة غير المحدودة، تستخدم الطريقة قطعاً يعتمد على البيانات (صندوق الحد الأدنى والأقصى) لضمان قياس منتهٍ، مع ضمانات نظرية بأن هذا القطع يستوعب جميع الكتلة الاحتمالية تقاربياً.

3. غابة التقسيم (Partition Forest)

لتحسين الاستقرار والأداء التنبئي، قدم المؤلفون غابة التقسيم (Partition Forest)، وهي طريقة تجميع (ensemble method). تقوم بمتوسط تقديرات الكثافة الشرطية لعدة أشجار تقسيم يتم تدريبها على عينات bootstrap، مع إمكانية استخدام أخذ عينات فرعية عشوائية للميزات.

4. الضمانات النظرية

تضع الورقة شروطاً كافية لـ الاتساق في مقياس $L^1(\nu)$ للمُقدِّر. يتم ضمان الاتساق إذا استوفى تسلسل التقسيم ما يلي:

ينمو عدد الخلايا بشكل دون خطي بالنسبة لـ $N$ .
دالة النمو لعائلة التقسيم تحقق حدودات محددة لـ VC-dimension.
يتقلص قطر الخلايا إلى الصفر.
ينمو عدد إسقاطات المتغيرات المستقلة المتميزة ببطء كافٍ بالنسبة لـ $\sqrt{\log N / N}$ .

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

إطار عمل موحد: إطار عمل غير بارامتري موحد لتقدير الكثافة الشرطية يتعامل مع النتائج المستمرة، الفئوية، والمختلطة دون افتراضات بارامترية.
التحسين المباشر: خوارزمية لبناء الأشجار تقوم مباشرة بتحسين خسارة اللوغاريتم الشرطية عبر بحث جشع (greedy best-first search)، متجنبة الاختناقات الحسابية الموجودة في تحسين الهيستوغرام والتقسيم المشترك في الأعمال السابقة.
القابلية للتوسع: تنفيذ ذو تعقيد حسابي مماثل لأشجار CART القياسية، مما يجعلها صالحة لمجموعات البيانات الكبيرة.
التوسيع بالتجميع: تقديم "غابة التقسيم"، التي أظهرت أداءً تنبؤياً احتمالياً محسناً مقارنة بالأشجار الفردية.
التحليل النظري: إثباتات اتساق صارمة للمُقدِّر المقترح تحت افتراضات التعقيد والانكماش القياسية.

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

قيم المؤلفون "شجرة التقسيم" و"غابة التقسيم" على مجموعة متنوعة من اختبارات التصنيف والانحدار، مقارنين إياها بـ CART، وRandom Forests، وCADET، وCDTree.

التصنيف:
- الأشجار الفردية: تفوقت شجرة التقسيم على CART في غالبية مجموعات البيانات (8 من أصل 9) من حيث خسارة اللوغاريتم (log-loss).
- التجميع (Ensembles): حققت غابة التقسيم خسارة لوغاريتم أقل من Random Forests في معظم مجموعات البيانات، مما أظهر معايرة احتمالية فائقة.
الانحدار:
- الأشجار الفردية: قدمت شجرة التقسيم تنبؤات نقطية تنافسية وأداءً احتمالياً قوياً. ومن الجدير بالذكر أنها تفوقت على CADET البارامتري في مجموعات البيانات الأكبر (مثل Air, Power, California, Protein)، مما يشير إلى قدرة أفضل على التوسع والتكيف مع حجم العينة.
- التجميع (Ensembles): تفوقت غابة التقسيم باستمرار على Random Forests في معظم اختبارات الانحدار (8 من أصل 10) فيما يتعلق بخسارة اللوغاريتم.
المتانة:
- الضجيج: أظهرت الطريقة متانة تجاه الضجيج المتجانس (homoscedastic) وغير المتجانس (heteroscedastic)، مع تدهور في الأداء مشابه لـ CDTree واستقرار أفضل من CADET.
- الميزات الزائدة: بينما أظهرت CDTree استقراراً أفضل قليلاً ضد تكرار الميزات المترابطة، حققت شجرة التقسيم تنبؤات أكثر اتساقاً (تباين أقل) تحت فساد الميزات مقارنة بـ CADET.
الكفاءة: أظهرت مقارنات وقت التشغيل على مجموعة بيانات Physicochemical Protein أن شجرة التقسيم أسرع بنحو 5 أضعاف من CADET و25 ضعفاً من CDTree عند $N=10,000$ .

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

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

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

يضع المؤلفون شجرة التقسيم كمرشح طبيعي للدمج في مسارات الاستدلال السببي (causal inference) وغيرها من التطبيقات التي تتطلب تقديراً مرناً للكثافة الشرطية، مع الإقرار بأن العمل المستقبلي قد يستكشف أطر تعزيز (boosting) واستراتيجيات تقليم (pruning) مخصصة.