خوارزمية تجميع الغطاء النباتي

خوارزمية التجميع العنقودي هي خوارزمية تجميع مسبق غير خاضعة للإشراف ، قدمها أندرو ماكالوم ، وكمال نيغام، ولايل أونغار عام 2000. ^{[ 1 ]} تُستخدم هذه الخوارزمية غالبًا كخطوة تمهيدية لخوارزمية K-means أو خوارزمية التجميع الهرمي . تهدف إلى تسريع عمليات التجميع على مجموعات البيانات الكبيرة ، حيث قد يكون استخدام خوارزمية أخرى مباشرةً غير عملي نظرًا لحجم مجموعة البيانات.

تتم الخوارزمية على النحو التالي، باستخدام عتبتين${\displaystyle T_{1}}$(المسافة الفضفاضة) و${\displaystyle T_{2}}$(المسافة الضيقة)، حيث${\displaystyle T_{1}>T_{2}}$[ ^{1 ] [ 2 ]​}

1. ابدأ بمجموعة نقاط البيانات المراد تجميعها.
2. قم بإزالة نقطة من المجموعة، وابدأ "مظلة" جديدة تحتوي على هذه النقطة.
3. لكل نقطة متبقية في المجموعة، قم بتعيينها إلى المظلة الجديدة إذا كانت المسافة بينها وبين النقطة الأولى في المظلة أقل من المسافة المتبقية.${\displaystyle T_{1}}$.
4. إذا كانت مسافة النقطة أقل من المسافة الضيقة${\displaystyle T_{2}}$، قم بإزالته من المجموعة الأصلية.
5. كرر من الخطوة 2 حتى لا يتبقى أي نقاط بيانات في المجموعة المراد تجميعها.
6. يمكن تقسيم هذه المظلات المتجمعة بتكلفة منخفضة نسبياً إلى مجموعات فرعية باستخدام خوارزمية أكثر تكلفة ولكنها أكثر دقة.

تجدر الإشارة إلى أن نقاط البيانات الفردية قد تكون جزءًا من عدة طبقات. ولتسريع العملية، يمكن استخدام مقياس مسافة تقريبي وسريع في الخطوة 3، بينما يمكن استخدام مقياس مسافة أكثر دقة وأبطأ في الخطوة 4.

بما أن الخوارزمية تستخدم دوال المسافة وتتطلب تحديد عتبات المسافة، فإن قابليتها للتطبيق على البيانات عالية الأبعاد محدودة بسبب مشكلة الأبعاد . فقط عند توفر دالة مسافة تقريبية منخفضة الأبعاد، ستحافظ المظلات الناتجة على التجمعات التي تنتجها خوارزمية K-means.

تشمل فوائده ما يلي:

• يتم تقليل عدد حالات بيانات التدريب التي يجب مقارنتها في كل خطوة.
• هناك بعض الأدلة على تحسن المجموعات الناتجة. ^{[ 3 ]}