التجميع النادر في الفضاءات الجزئية: الخوارزمية، النظرية، والتطبيقات

في العديد من المشكلات الحقيقية، نتعامل مع مجموعات من البيانات ذات الأبعاد العالية، مثل الصور والفيديوهات والنصوص ومستندات الويب وبيانات شرائح الحمض النووي الريبي (DNA microarray data)، وغيرها. غالباً ما تكمن البيانات ذات الأبعاد العالية بالقرب من هياكل ذات أبعاد منخفضة تتوافق مع عدة فئات أو تصنيفات تنتمي إليها البيانات. في هذا البحث، نقترح وندرس خوارزمية تُسمى التجميع الفراغي للفراغات الجزئية (Sparse Subspace Clustering - SSC) لتصنيف نقاط البيانات التي تقع في اتحاد فراغات جزئية ذات أبعاد منخفضة. الفكرة الأساسية هي أن، بين عدد لا نهائي من التمثيلات الممكنة لنقطة بيانات بدلالة نقاط أخرى، يتوافق التمثيل النادر مع اختيار عدد قليل من النقاط من نفس الفراغ الجزئي. هذا يحفز على حل برنامج تحسين نادر حيث يتم استخدام حله ضمن إطار التجميع الطيفي لاستنتاج تصنيف البيانات إلى فراغات جزئية. نظرًا لأن حل برنامج التحسين النادر يكون عادةً صعبًا للغاية (NP-hard)، فإننا نعتبر استرخاءً محدبًا ونوضح أنه، تحت ظروف ملائمة على ترتيب الفراغات الجزئية وتوزيع البيانات، ينجح البرنامج التقديمي في استعادة التمثيلات النادرة المرغوبة. يمكن حل الخوارزمية المقترحة بكفاءة ويمكنها التعامل مع نقاط البيانات القريبة من تقاطعات الفراغات الجزئية. ميزة رئيسية أخرى للخوارزمية المقترحة مقارنة بأحدث التقنيات هي أنها يمكنها التعامل مباشرة مع الإزعاج في البيانات، مثل الضوضاء والمدخلات الخارجة عن النطاق بشكل نادر والمدخلات المفقودة، وذلك عبر دمج نموذج البيانات في برنامج التحسين النادر. نظهر فعالية الخوارزمية المقترحة من خلال التجارب على بيانات مصنعة وعلى مشكلتين حقيقتين هما تقسيم الحركة وتجميع الوجوه.