Optimizing Multidimensional Scaling in Gini Metric Spaces

ملخص تقني: تحسين القياس متعدد الأبعاد في فضاءات مقاييس جيني

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

المنهجية
تقترح الورقة إطار عمل "قياس جيني متعدد الأبعاد" (Gini MDS)، والذي يوسع MDS الكلاسيكي باستبدال المقياس الإقليدي بـ مسافة جيني الزائفة المعممة (Generalized Gini Pseudo-Distance).

1. المسافة الجينية الزائفة المعممة ($D_{G,\nu}$):

   • بخلاف مقاييس جيني القياسية التي تعتمد فقط على الرتب أو القيم، فإن هذه المسافة الزائفة تدمج كليهما. وهي معرفة بناءً على مفهوم معيار مينكوفسكي $p$-norm ولكنها مكيفة لتشمل معلومات الرتبة أيضًا.
   • الابتكار الجوهري هو إدخال معلمة فائقة قابلة للضبط، $\nu$ (حيث $\nu > 1$). تتحكم هذه المعلمة في وزن ذيول التوزيع:
     • عندما تكون $\nu = 2$، فإنها تقابل تقليل معامل جيني للمخلفات (بشكل مشابه لانحدار الوسيط).
     • عندما تكون $\nu \in (1, 2)$، فإنها تضع وزنًا أكبر على الجزء العلوي من التوزيع.
     • عندما تكون $\nu > 2$، فإنها تضع وزنًا أكبر على الجزء السفلي من التوزيع.
   • تم جعل المسافة متناظرة لضمان استيفائها لخصائص المسافة الزائفة (التناظر، عدم السلبية، ومتباينة المثلث)، رغم أنه لوحظ أن خاصية "الصفر" تتحقق أيضاً في التوزيعات المتساوية (حيث $x = c\mathbf{1}$) وكذلك في النقاط المتطابقة.
   • يعتمد الهيكل على فجوات الرتب وفجوات القيم، مما يجعله متيناً بطبيعته تجاه القيم المتطرفة.

2. خوارزمية التحسين:

   • يستخدم إطار العمل نهج تقليل الإجهاد (Kruskal's Stress) لإيجاد الفضاء الكامن الأمثل.
   • الخوارزمية 1 تمر عبر نطاق من قيم $\nu$ (على سبيل المثال، من 1.1 إلى 5). لكل قيمة $\nu$، تقوم بحساب مصفوفة المسافة الجينية الزائفة، وتجري عملية MDS لإنشاء تضمين، وتحسب درجة الإجهاد.
   • يتم اختيار $\nu^*$ المثلى كالقيمة التي تقلل متوسط الإجهاد عبر طيات التحقق المتقاطع (cross-validation folds).
   • يستخدم التنفيذ مكتبة PyTorch مع العمليات القائمة على التنسورات (tensor-based operations) للاستفادة من تسريع وحدة معالجة الرسومات (GPU)، مما يوفر تحسينات كبيرة في السرعة مقارنة بالمكتبات القياسية القائمة على المعالج المركزي (CPU).

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

1. مقياس مبتكر: تقديم مسافة جينية زائفة تجمع بين القيم والرتب مع معلمة فائقة $\nu$ قابلة للضبط، مما يسمح باستكشاف مرن للتكوينات الكامنة.
2. المتانة: إثبات أن المسافة الجينية الزائفة متينة تجاه الضجيج والقيم المتطرفة بسبب اعتمادها على فروق الرتب، والتي تخفف من تأثير القيم القصوى.
3. إطار عمل مُحسّن: خوارزمية كاملة لـ "Gini MDS المُحسّن" التي تختار تلقائيًا المعلمة الفائقة الأفضل لتناسب التباينات المرصودة، متفوقة على النهج الإقليدي الثابت.
4. تنفيذ فعال: تنفيذ معزز بواسطة GPU وقائم على التنسورات في PyTorch، مما يقلل وقت الحوسبة بشكل كبير مقارنة بـ sklearn MDS.
5. تقييم شامل: تجارب واسعة النطاق على 16 مجموعة بيانات من UCI (مع وبدون تلوث بالقيم المتطرفة)، وبيانات صور MNIST (مع ضجيج غاوسي)، ومحاكاة على التوزيعات ذات الذيول الثقيلة.

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

• مجموعات بيانات UCI (تلوث القيم المتطرفة):
  • في 16 مجموعة بيانات مع تلوث بنسبة 2% و5%، تفوق Gini MDS باستمرار على Euclidean MDS وثلاثة متغيرات إقليدية محسنة (Huber, Sammon, SMACOF) من حيث الموثوقية (Trustworthiness) (الحفاظ على البنية المحلية) ومقاييس الجار الأقرب (Nearest Neighbor).
  • بينما حققت الطرق الإقليدية أحيانًا درجات Silhouette أعلى (التجميع العالمي) في البيانات النظيفة، أظهر Gini MDS أداءً فائقًا في الحفاظ على الجوارات المحلية عندما كانت البيانات ملوثة.
• تصنيف MNIST (الضجيج):
  • في مهمة تصنيف تميز بين الرقمين 5 و6 مع إضافة ضجيج غاوسي، تفوق Gini MDS على Euclidean MDS عند استخدام مكون تضمين واحد.
  • تشير النتائج إلى أن Gini MDS يمتلك "قدرة ضغط" أعلى، حيث يلتقط المزيد من المعلومات ذات الصلة في المكون الأول تحت ظروف الضجيج.
• محاكاة الذيول الثقيلة:
  • مقارنة بالطرق غير الخطية (t-SNE, Isomap, UMAP) على التوزيعات ذات الذيول الثقيلة، حقق Gini MDS أعلى ارتباطات بيرسون وسبيرمان بين مصفوفات المسافة الأصلية والمضمنة.
  • يشير هذا إلى أن Gini MDS فعال بشكل خاص في الحفاظ على الهيكل الهندسي العالمي (علاقات المسافة الزوجية) للبيانات ذات الذيول الثقيلة، بينما ركزت الطرق الأخرى أكثر على حفظ الجوارات المحلية.
• الأداء:
  • كان تنفيذ PyTorch أسرع بكثير من sklearn (على سبيل المثال، 9 ثوانٍ مقابل 46 ثانية لمجموعة بيانات Banknote التي تحتوي على 1,372 حالة).

الأهمية والادعاءات
تزعم الورقة أن Gini MDS يوفر بديلاً متيناً لـ MDS الكلاسيكي، لا سيالما في التطبيقات الواقعية حيث تكون البيانات مشوبة بالضجيج أو تحتوي على قيم متطرفة. ومن خلال الاستفادة من خصائص إحصاءات جيني (دمج الرتب والقيم) وتحسين المعلمة الفائقة $\nu$، يقدم المنهج:

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

يخلص المؤلفون إلى أنه بينما يظل Euclidean MDS فعالاً للبيانات النظيفة، فإن إطار عمل Gini MDS يعد خيارًا فائقًا للسيناريوهات التي تتضمن تلوث البيانات، حيث يقدم أداة مرنة وفعالة حوسبيًا لاكتشاف البنية الكامنة.