تمثيل النواة ومقياس التشابه للبيانات غير المكتملة

المعلومات الأساسية

• معرّف الورقة: 2510.13352
• العنوان: Kernel Representation and Similarity Measure for Incomplete Data
• المؤلفون: Yang Cao, Sikun Yang, Kai He, Wenjun Ma, Ming Liu, Yujiu Yang, Jian Weng
• التصنيف: cs.LG (التعلم الآلي)
• تاريخ النشر: 15 أكتوبر 2024 (تقديم arXiv)
• رابط الورقة: https://arxiv.org/abs/2510.13352v1

الملخص

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

الخلفية البحثية والدافع

المشكلة الأساسية

قياس التشابه في البيانات غير المكتملة هو تحدٍ أساسي في تعدين الشبكات وأنظمة التوصية وتحليل سلوك المستخدم. البيانات الحقيقية غير مكتملة بطبيعتها بسبب تفضيلات خصوصية المستخدمين وعدم الاستجابة في الاستطلاعات والإفصاح الطوعي عن المعلومات.

أهمية المشكلة

1. الانتشار الواسع: يقيّم المستخدمون في أنظمة التوصية عادة عدداً قليلاً فقط من العناصر، مما ينتج عنه مصفوفة مستخدم-عنصر متناثرة جداً
2. عدم تجانس البيانات: قد يؤثر الفقدان في نفس الوقت على الميزات الرقمية والفئوية أو المختلطة
3. تأثير المهام اللاحقة: قياس التشابه هو أساس مهام التجميع والتصنيف والكشف عن الشذوذ، وتقدير التشابه غير الدقيق يقلل بشكل كبير من أداء المهام

قيود الطرق الموجودة

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

الدافع البحثي

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

المساهمات الأساسية

1. اقتراح طريقة النواة القريبة: من خلال التصنيف متساوي التكرار والتخصيص القريب المستند إلى Voronoi، توقع البيانات إلى تمثيل متناثر عالي الأبعاد دون الحاجة إلى تقدير كثافة صريح
2. استراتيجية التراجع المتسلسلة: بالنسبة لمعالجة القيم المفقودة، تقترح استراتيجية مطابقة تدريجية تخفف القيود من التقاطع إلى الاتحاد إلى الأولويات العامة
3. التعقيد الزمني الخطي: تحقق التعقيد الزمني الخطي، مما يجعل الطريقة قابلة للتوسع إلى مجموعات البيانات الكبيرة
4. التحقق التجريبي: تُظهر أداءً متفوقاً على الطرق الموجودة في مهام التجميع على 12 مجموعة بيانات

شرح الطريقة بالتفصيل

تعريف المهمة

بالنظر إلى مجموعة بيانات D = {x₁, x₂, ..., xₙ} تحتوي على n عينة، حيث كل عينة xᵢ ∈ ℝᵈ هي متجه ميزة d-بعدي قد يحتوي على قيم مفقودة (يُشار إليها بـ NaN). الهدف هو حساب دالة التشابه s : D × D → 0,1، التي تقيس التشابه بين أي عينتين، للاستخدام في المهام اللاحقة مثل التجميع.

معمارية النموذج

1. التصنيف المعتمد على البيانات والتخصيص القريب

اختيار مراكز التصنيف: لكل ميزة j، استخدم التصنيف متساوي التكرار لاختيار مراكز تصنيف nᵦᵢₙₛ:

c_{j,k} = percentile(X_{obs,j}, (k-1)×100/(n_{bins}-1))

حيث k ∈ {1,2,...,nᵦᵢₙₛ}، و Xₒᵦₛ,ⱼ يمثل جميع القيم المرصودة للميزة j.

آلية التخصيص القريب: استخدم التخصيص القريب بدلاً من عضوية الفترة التقليدية:

b_{i,j} = argmin_{k∈{1,...,n_{bins}}} |x_{i,j} - c_{j,k}|

هذا ينشئ مخطط Voronoi لفضاء الميزات، حيث يحدد كل مركز cⱼ,ₖ خلية Voronoi.

الخاصية التكيفية للكثافة:

• في المناطق الكثيفة: المسافة بين المراكز المتتالية صغيرة، تنشئ خلايا Voronoi صغيرة، نقطتان بنفس المسافة أكثر احتمالاً أن تقعا في خلايا مختلفة
• في المناطق المتناثرة: المسافة بين المراكز المتتالية كبيرة، تنشئ خلايا Voronoi كبيرة، نقطتان بنفس المسافة أكثر احتمالاً أن تقعا في نفس الخلية

2. بناء الترميز الفردي

لكل ميزة j وعينة i، بناء متجه ثنائي hᵢ,ⱼ ∈ {0,1}^{n_}:

h_{i,j,k} = {1 if b_{i,j} = k; 0 otherwise}

الترميز الكامل هو تسلسل جميع الميزات: zᵢ = hᵢ,₁, hᵢ,₂, ..., hᵢ,ₐ

3. استراتيجية التراجع المتسلسلة لمعالجة القيم المفقودة

المستوى 1 - مطابقة التقاطع: ابحث عن العينات التي تطابق جميع الميزات المرصودة:

S₁(i) = ∩_{j∈O_i} C_{i,j}

حيث C_{i,j} = {m : m≠i, b_{m,j} = b_{i,j}}

المستوى 2 - مطابقة الاتحاد: إذا كان S₁(i) = ∅، خفف إلى مطابقة أي ميزة مرصودة:

S₂(i) = ∪_{j∈O_i} C_{i,j}

المستوى 3 - الأولوية العامة: إذا كان S₂(i) = ∅، استخدم التوزيع العام:

p_{j,k} = count of samples in bin k for feature j / count of samples with observed feature j

لكل مستوى، استخدم تضمين متوسط النواة (KME) لتقدير الترميز المفقود:

h_{i,j,k} = 1/|S(i)| ∑_{m∈S(i)} h_{m,j,k}

نقاط الابتكار التقني

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

تعريف النواة القريبة

K(x_m, x_n) = 1/d · z_m^T z_n = <z_m, z_n>

تحقق هذه النواة شروط Mercer (التماثل والإيجابية شبه المحددة)، لها تفسير احتمالي: حساب الاحتمالية المتوقعة لسقوط عينتين في نفس التصنيف عبر جميع الميزات.

إعداد التجارب

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

استخدام 12 مجموعة بيانات حقيقية من UCI، تغطي عدة مجالات:

• التشخيص الطبي: Kidney, Hepatitis, Heart, Tumor, Cancer
• التصنيف البيولوجي: Soybean, Mushroom
• التحليل المالي: Credit
• التنبؤ السكاني: Adult
• التحليل السياسي: Voting
• أخرى: Mammography, Horse

تتراوح عدد العينات في مجموعات البيانات من 155 إلى 48,842، والأبعاد من 5 إلى 35، ومعدلات الفقدان من 0.15% إلى 19.39%.

مقاييس التقييم

استخدام المعلومات المتبادلة المعيارية (NMI) لتقييم جودة التجميع، مع تطبيق تجميع K-means، وتعيين عدد المجموعات إلى عدد الفئات الحقيقية.

طرق المقارنة

9 طرق تمثيلية:

1. الاستكمال البسيط: استكمال المتوسط
2. الطرق الإحصائية: MissForest, MICE, KNN, EM
3. التعلم العميق: GAIN, MIRACLE, MIWAE
4. طرق النواة: HI-PMK

تفاصيل التنفيذ

• تكرار كل تجربة 10 مرات وأخذ المتوسط
• ضبط فرط المعاملات لجميع طرق الأساس
• البحث عن عدد التصنيفات للنواة القريبة في {2,3,4,6,8}

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

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

1. الأداء الإجمالية: تحقيق أفضل أو ثاني أفضل أداء على 10 من 12 مجموعة بيانات، أعلى متوسط NMI (0.4245)
2. الدلالة الإحصائية: اختبار Friedman-Nemenyi يُظهر أن النواة القريبة متفوقة بشكل كبير على جميع الطرق الأخرى باستثناء HI-PMK
3. الاستقرار: تُظهر الرسوم البيانية الصندوقية أن النواة القريبة ليست فقط الأفضل في الأداء المتوسطة، بل أيضاً أكثر اتساقاً عبر مجموعات البيانات المختلفة

تجارب قوة الفقدان

اختبار معدلات فقدان 10%-50% على مجموعات بيانات 3L و Messidor:

• الحفاظ على أداء متفوقة مستقرة في معدلات فقدان منخفضة إلى متوسطة (10%-40%)
• الحفاظ على أداء معقولة حتى في معدلات فقدان قصوى (50%)
• بالمقارنة، تنخفض أداء KNN و MissForest إلى ما يقرب من الصفر عند 30% فقدان

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

• التعقيد الزمني: O(nd + d·n log n)، خطي بالنسبة لعدد العينات للبعد الثابت
• التعقيد المكاني: O(nd)، خطي بالنسبة لعدد العينات والميزات
• وقت التشغيل الفعلي: أسرع بشكل كبير من HI-PMK و MIWAE

تحليل الحساسية

عند تغيير عدد التصنيفات من 2 إلى 10، التغيير في NMI عبر ثلاث مجموعات بيانات صغير جداً (على سبيل المثال، مجموعة بيانات Mammo تتراوح بين 0.30-0.33)، مما يُظهر عدم حساسية الطريقة لفرط المعاملات.

الأعمال ذات الصلة

طرق الاستكمال التقليدية

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

طرق التعلم العميق

• GAIN: استخدام الشبكات العدائية التوليدية لتعلم توزيع البيانات المفقودة
• MIWAE: استخدام نماذج متغيرة عميقة لتعظيم حد أدنى للبيانات المرصودة
• MIRACLE: دمج الاستدلال السببي مع التعلم العميق لتحسين جودة الاستكمال

طرق النواة

• المسافات التقليدية: المسافة الإقليدية لا تنطبق مباشرة على البيانات غير المكتملة
• HI-PMK: طريقة نواة معتمدة على البيانات، لكن التعقيد الحسابي مرتفع وحساسة لفرط المعاملات

الخلاصة والمناقشة

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

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

القيود

1. افتراضات آلية الفقدان: التقييم الحالي يعتمد بشكل أساسي على آلية MCAR (الفقدان العشوائي تماماً)، البيانات الحقيقية غالباً ما تُظهر أنماطاً MAR و MNAR أكثر تعقيداً
2. استراتيجية التصنيف: قد لا يكون التصنيف متساوي التكرار الخيار الأمثل لجميع توزيعات البيانات
3. الضمانات النظرية: تفتقر إلى ضمانات التقارب النظري لآلية التراجع المتسلسلة

الاتجاهات المستقبلية

1. دراسة سلوك الطريقة تحت آليات الفقدان MAR و MNAR
2. استكشاف استراتيجيات اختيار تصنيف تكيفية
3. إنشاء ضمانات تقارب نظرية لآلية التراجع المتسلسلة
4. التوسع إلى أنواع بيانات وهياكل أكثر تعقيداً

التقييم المتعمق

المزايا

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

أوجه القصور

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

التأثير

1. المساهمة الأكاديمية: توفير إطار نظري جديد لقياس التشابه في البيانات غير المكتملة
2. القيمة العملية: قيمة مباشرة في التطبيقات مثل أنظمة التوصية وتعدين الشبكات
3. قابلية التكرار: توفير رابط الكود، يساعد على التحقق والنشر الواسع للطريقة

السيناريوهات المناسبة

1. أنظمة التوصية: معالجة تناثر مصفوفة تقييم المستخدم-العنصر
2. تعدين الشبكات: معالجة عدم اكتمال بيانات سلوك المستخدم
3. تحليل البيانات الطبية: معالجة القيم المفقودة في البيانات السريرية
4. معالجة البيانات الكبيرة: التعقيد الخطي مناسب للتطبيقات الكبيرة

المراجع

تستشهد الورقة بـ 21 مرجعاً ذا صلة، تغطي معالجة البيانات المفقودة وطرق النواة والتعلم العميق وغيرها من المجالات المهمة، مما يوفر أساساً نظرياً قوياً ومعايير مقارنة للبحث.

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