خوارزميات التجميع العنقودي

يمكن أن تحتوي مجموعات بيانات تعلُّم الآلة على ملايين المثال، ولكن لا يمكن توسيع نطاق بعض خوارزميات التجميع بكفاءة. تُحسِّب العديد من خوارزميات التجميع التشابه بين كل أزواج الأمثلة، ما يؤدي إلى زيادة وقت التشغيل بمعدل مربّع عدد الأمثلة \(n\)، ويُشار إليه باسم \(O(n^2)\) في رمز التعقيد.لا تكون خوارزميات \(O(n^2)\) مفيدة للمجموعات التي تتضمّن ملايين الأمثلة.

تبلغ الصعوبة الحسابية للخوارزمية التصنيفية \(O(n)\)، ما يعني أنّ الخوارزمية تتغيّر بشكل خطي مع \(n\). ستكون هذه الخوارزمية محور هذه الدورة التدريبية.

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

للحصول على قائمة شاملة بالمناهج المختلفة للتجميع، اطّلِع على A Comprehensive Survey of Clustering Algorithms (استطلاع شامل حول خوارزميات التجميع) الذي كتبه "د. شين تشو". & Tian, Y. منى. بيانات. Sci. (2015) 2: 165. ويكون كلّ منهج مناسبًا بشكلٍ أفضل لتوزيع بيانات معيّن. تتناول هذه الدورة التدريبية بشكل موجز أربعة اتّجاهات شائعة.

التجميع العنقودي المستنِد إلى النقاط المركزية

النقطة المركزية لمجموعة عنقودية هي المتوسّط الحسابي لجميع النقاط في المجموعة. يُنظِّم التجميع المستنِد إلى مركز الكتلة البيانات في مجموعات غير هرمية. تكون خوارزميات التجميع العنقودي المستندة إلى مركز الكتلة فعّالة، ولكنها حسّاسة terhadap الشروط الأولية والقيم الشاذة. ومن بين هذه الخوارزميات، تُعدّ خوارزمية "المركز المتوسط لنقاط متعددة" هي الأكثر استخدامًا. وتتطلّب من المستخدمين تحديد عدد المراكز الحسابية، k، وتعمل بشكل جيد مع المجموعات العنقودية ذات الحجم المتساوٍ تقريبًا.

أمثلة مجمّعة في مجموعات باستخدام التجميع المستنِد إلى النقاط المركزية
           تعرِض الخطوط الحدود بين المجموعات.
الشكل 1: مثال على التجميع المستنِد إلى النقطة المركزية

التجميع العنقودي القائم على الكثافة

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

أمثلة مجمّعة في مجموعتَين باستخدام التجميع العنقودي القائم على الكثافة
      لا يمكن فصل المجموعات بشكل خطي.
الشكل 2: مثال للتجميع العنقودي القائم على الكثافة

التجميع العنقودي المستنِد إلى التوزيع

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

أمثلة مجمّعة باستخدام التجميع المستنِد إلى التوزيع يوضّح التظليل لكثافة الأمثلة في كل مجموعة كيف تتمّ ربط المجموعات بالتوزيعات.
الشكل 3: مثال على التجميع المستنِد إلى التوزيع

التجميع الهرمي

يُنشئ التجميع الهرمي شجرة من المجموعات العنقودية. ليس من المستغرب أنّ التجميع الهرمي يناسب البيانات الهرمية، مثل التصنيفات. يمكنك الاطّلاع على مقالة مقارنة بين 61 جينومًا من البكتيريا القولونية التي تم تسلسلها التي كتبها Oksana Lukjancenko وTrudy Wassenaar وDave Ussery كمثال. يمكن اختيار أي عدد من المجموعات العنقودية من خلال قطع الشجرة على المستوى المناسب.

الحيوانات المجمّعة باستخدام شجرة هرمية
الشكل 4: مثال على شجرة هرمية تتضمّن مجموعة من الحيوانات.