📊 statistics

DICS: Data-Informed Centroid Splitting for Decision Tree Classifiers

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

المؤلفون الأصليون: MD Saifur Rahman Mazumder, Feng Yu

نُشر 2026-08-21

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: MD Saifur Rahman Mazumder, Feng Yu

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

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

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

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

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

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

ولضمان متانة نتائجهم، اختبر الباحثون طريقتهم على مجموعة متنوعة من التحديات الواقعية، بما في ذلك اكتشاف رسائل البريد الإلكتروني المزعجة، وتحديد المعاملات المالية الاحتيالية، وتصنيف صور الملابس والأرقام. وفي كل حالة، حافظ النهج الجديد على تفوقه في السرعة. ففي مجموعة بيانات Spambase، على سبيل المثال، استغرق النهج التقليدي جزءًا من الثانية، لكن النهج الجديد كان أسرع بمرتين. وفي مجموعة بيانات Santander الأكبر، التي احتوت على مائتي ألف سجل، كان النهج الجديد أسرع بأكثر من سبع مرات. وحتى في مهام التعرف على الصور المعقدة مثل CIFAR-10، حيث تكون البيانات صعبة المعالجة، كان النهج الجديد أسرع بنحو ١٣ ضعفًا من شجرة القرار القياسية مع الحفاظ على معدل خطأ منخفض.

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

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

ملخص تقني: تقسيم المركز الثقلي الموجه بالبيانات (DICS) لمصنفات أشجار القرار

1. بيان المشكلة

تُستخدم النماذج القائمة على أشجار القرار، بما في ذلك متغيراتها التجميعية مثل الغابات العشوائية (Random Forests) وتعزيز التدرج (Gradient Boosting Machines)، على نطاق واسع لسهولة تفسيرها وأدائها التجريبي. ومع ذلك، تواجه عملية تدريب هذه النماذج عقبة حوسبية كبيرة: البحث الشامل عن التقسيم الأمثل عند كل عقدة.

في بناء أشجار القرار القياسية، تقوم الخوارزمية بتقييم كل نقطة تقسيم محتملة لكل ميزة. بالنسبة لمجموعة بيانات تحتوي على $N$ من العينات و $P$ من الميزات، يتضمن ذلك فرز العينات وتقييم ما يصل إلى $(N-1)P$ من التقسيمات المرشحة لكل عقدة. هذه العملية مكلفة حوسبياً، لا سيما في مجموعات البيانات الضخمة وعالية الأبعاد. وبينما تعمل الطرق الموجودة مثل التقسيم القائم على المدرجات التكرارية (Histogram-based binning) (كما في XGBoost و LightGBM) على تقليل هذه التكلفة من خلال تقطيع الميزات، إلا أنها تُدخل أخطاء التكميم وتتطلب مقايضة بين الكفاءة والدقة. علاوة على ذلك، تفتقر هذه الطرق إلى التوجيه المسبق حول أي التقسيمات من المرجح أن تكون معلوماتية، حيث تعامل جميع عتبات الترشيح بالتساوي.

2. المنهجية: تقسيم المركز الثقلي الموجه بالبيانات (DICS)

يقترح المؤلفون تقسيم المركز الثقلي الموجه بالبيانات (DICS)، وهو إطار عمل يستفيد من المعلومات الهيكلية داخل البيانات لبناء مجموعة مدمجة ومعلوماتية من التقسيمات المرشحة، مما يقلل مساحة البحث دون تغيير هدف الشجرة الجشع الأساسي.

المفهوم الجوهري

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

الخطوات الخوارزمية

التكتل (Clustering): تطبق الخوارزمية خوارزمية K-means لتكتل مصفوفة الميزات $X$ للحصول على $K$ من المراكز الثقلية $\{\mu_c\}_{c=1}^K$ . تمثل هذه المراكز الأنماط السائدة لتوزيع البيانات.
توليد الحدود: بدلاً من تقييم جميع العتبات الممكنة، يقوم DICS بتوليد تقسيمات مرشحة بناءً على الحدود بين المراكز الثقلية.
- حد المنتصف: أبسط حد هو منتصف المسافة بين المركزين الثقليين: $\zeta = \frac{1}{2}(\mu_{c_1} + \mu_{c_2})$ .
- الحد المعدل بالتباين: للتعامل مع الحالات التي تمتلك فيها التكتلات تباينات (انتشار) مختلفة، يقترح المؤلفون حداً معدلاً بالتباين حيث تكون المسافة من المراكز الثقلية إلى التقسيم متناسبة مع الانحرافات المعيارية ( $\hat{\sigma}$ ):
  $\zeta(\mu_{c_1}, \mu_{c_2}) = \frac{\hat{\sigma}_{c_1}\mu_{c_2} + \hat{\sigma}_{c_2}\mu_{c_1}}{\hat{\sigma}_{c_1} + \hat{\sigma}_{c_2}}$
اختيار المرشحين: توجد $\binom{K}{2}$ من أزواج المراكز الثقلية الممكنة. ولتجنب التكرار، تختار الخوارزمية أفضل $m$ من الأزواج ذات أكبر المسافات بين المراكز الثقلية. تحدد هذه الأزواج مجموعة العتبات المرشحة لكل ميزة.
التكامل: تُستخدم مجموعة التقسيمات المرشحة الناتجة لتنمية الشجرة. يتم دمج هذا النهج في:
- CGCT: شجرة التصنيف الموجهة بالتكتل (شجرة قرار قياسية).
- CGRF: الغابة العشوائية الموجهة بالتكتل.
- FastC-GBM: آلة تعزيز التدرج تجمع بين DICS مع أخذ العينات أحادي الجانب القائم على التدرج (GOSS) وأخذ عينات الميزات.

التعقيد الحوسبي

الحساب المسبق: يضيف DICS عبئاً زمنياً لمرة واحدة قدره $O(TKbP)$ باستخدام mini-batch K-means، حيث $T$ هي التكرارات و $b$ هو حجم الدفعة. وهذا يعتبر ضئيلاً مقارنة بمرحلة إيجاد التقسيم.
إيجاد التقسيم: تنخفض التكلفة لكل عقدة من $O(NP)$ (بحث شامل) أو $O(H P)$ (مدرجات تكرارية) إلى $O(mP)$ ، حيث $m$ هو عدد أزواج المراكز الثقلية المختارة. وبما أن $m$ عادة ما يكون صغيراً (على سبيل المثال، $m=10$ لـ $K=5$ )، فإن هذا يوفر تقليلاً كبيراً في التعقيد.

3. التحليل النظري

تقدم الورقة تحليلاً نظرياً (النظرية 1) لإثبات أن DICS لا يؤدي إلى تدهور الأداء التنبؤي تقاربياً.

الافتراضات: يفترض التحليل شرط انتظام الكثافة حيث تكون الكثافة الهامشية للميزات محدودة بالقرب من التقسيم الأمثل.
النتيجة: الفرق في كسب عدم النقاء (impurity gain) بين التقسيم الأمثل الذي تجده عملية البحث الشامل (DT) والتقسيم الأمثل الذي يجده DICS محكوم بـ $O(1/\sqrt{N})$ .
الآثار المترتبة: مع زيادة عدد العينات $N$ ، تتلاشى الفجوة في الأداء بين الطريقتين. الأجزاء التي يسببها DICS تختلف عن الأجزاء المثلى بمقدار $O(\sqrt{N})$ عينة على الأكثر، مما يضمن بقاء نسبة الربح المحتفظ بها عالية حتى في مستويات الشجرة العميقة.

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

قيم المؤلفون DICS على كل من البيانات الاصطناعية والبيانات الواقعية، مقارنة إياها بأشجار القرار القياسية (DT)، والغابات العشوائية (RF)، وXGBoost، وLightGBM، والطريقة ذات الصلة BDTKS.

البيانات الاصطناعية

التسريع: حققت النماذج القائمة على DICS تسريعاً كبيراً.
- CGCT: أسرع بـ 8–22 مرة من DT القياسية.
- CGRF: أسرع بـ 8–30 مرة من RF القياسية.
- FastC-GBM: أسرع بـ 5–50 مرة من XGBoost و3.6–27 مرة من LightGBM.
الدقة: كان التنازل في الدقة هامشياً، وعادة ما يكون ضمن 0.02 من النماذج المرجعية.
المقارنة: وُجد أن الطريقة ذات الصلة BDTKS (التي تطبق K-means بشكل متكرر عند كل عقدة) مكلفة حوسبياً ولم تقدم مزايا في السرعة أو الدقة.

مجموعات البيانات الواقعية

أُجريت التجارب على مجموعات بيانات تشمل Helena، وSpambase، وSantander، وCIFAR-10، وMNIST، وFashion-MNIST.

الكفاءة: قلل DICS باستمرار من أوقات التدريب. على سبيل المثال، كان CGCT أسرع بـ 2–21 مرة من DT في البيانات الواقعية. وكان FastC-GBM أسرع بـ 18.75 مرة من XGBoost.
المتانة: في مجموعة بيانات Helena، أدى LightGBM أداءً ضعيفاً، بينما حافظ FastC-GBM على أداء مستقر، مما يشير إلى تحسن في المتانة.
الدقة: بينما أظهرت بعض مجموعات البيانات (مثل CIFAR-10) انخفاضاً طفيفاً في الدقة مقارنة بالإعدادات الاصطناعية، إلا أن الانخفاض ظل صغيراً، وحافظت الطريقة عموماً على الأداء التنبؤي.

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

تزعم الورقة أن DICS يقدم حلاً قابلاً للتوسع لتدريب المصنفات القائمة على الأشجار من خلال دمج الأولويات الموجهة بالبيانات في عملية اختيار التقسيم.

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

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