تقسيم الرسوم البيانية الثنائية وتجميع البيانات

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