كما ذكرنا سابقًا، لا يمكن استخدام العديد من خوارزميات التجميع مع مجموعات البيانات المستخدَمة في تعلُّم الآلة، والتي غالبًا ما تحتوي على ملايين الأمثلة. على سبيل المثال، تفحص خوارزميات التجميع الهرمي التجميعية أو التقسيمية جميع أزواج النقاط وتتسم بتعقيد \(O(n^2 log(n))\) و \(O(n^2)\)، على التوالي.
تركّز هذه الدورة التدريبية على طريقة "متوسطات k" لأنّها تتغيّر بمعدل \(O(nk)\)، حيث \(k\) هو عدد المجموعات التي اختارها المستخدم. تجمع هذه الخوارزمية النقاط في \(k\) مجموعات عنقودية من خلال تقليل المسافات بين كل نقطة و النقطة المركزية لمجموعتها العنقودية (راجِع الشكل 1).
ونتيجةً لذلك، تتعامل الخوارزمية التصنيفية بفعالية مع البيانات على أنّها تتألف من عدد من التوزيعات الدائرية تقريبًا، وتحاول العثور على مجموعات تتوافق مع هذه التوزيعات. ولكن بيانات العالم الواقعي تحتوي على قيم شاذة ومجموعات مستندة إلى الكثافة وقد لا تتطابق مع الافتراضات الأساسية لطريقة "متوسطات عددية متعدّدة".
خوارزمية التجميع التصنيفي
تتّبع الخوارزمية الخطوات التالية:
قدِّم تخمينًا أوليًا لـ \(k\)، والذي يمكن مراجعته لاحقًا. في هذا المثال، نختار \(k = 3\).
اختَر عشوائيًا \(k\) النقاط المركزية.
الشكل 1: الخوارزمية التصنيفية في مرحلة الإعداد حدِّد كل نقطة وفقًا لأقرب نقطة مركزية للحصول على \(k\) المجموعات العنقودية الأولية.
الشكل 2: المجموعات الأولية. احتسِب نقطة مركزية جديدة لكل مجموعة عنقودية من خلال احتساب متوسط موضع جميع النقاط في المجموعة. تعرض الأسهم في الشكل 4 التغيُّر في مواضع مركز الكتلة.
الشكل 3: المراكز الحسابية التي تمت إعادة احتسابها أعِد تعيين كل نقطة إلى أقرب نقطة مركزية جديدة.
الشكل 4: المجموعات بعد إعادة التعيين كرِّر الخطوتَين 4 و5، مع إعادة احتساب النقاط المركزية وعضوية المجموعة، إلى أن تتوقف النقاط عن تغيير المجموعات. في حال مجموعات البيانات الكبيرة، يمكنك إيقاف الخوارزمية قبل التقارب استنادًا إلى معايير أخرى.
ولأنّ مواضع النقاط المركزية يتم اختيارها في البداية عشوائيًا، يمكن أن تؤدي الخوارزمية التصنيفية إلى اختلاف كبير في النتائج عند إجراء عمليات متتالية. لحلّ هذه الصعوبة، يمكنك تنفيذ طريقة "متوسطة عدد المجموعات" عدة مرات واختيار النتيجة التي تتضمّن أفضل مقاييس الجودة. (سنوضّح مقاييس الجودة لاحقًا في هذه الدورة التدريبية). ستحتاج إلى استخدام إصدار متقدّم من طريقة "متوسطات عددية متعددة" لاختيار مواضع أفضل للمركز الأولي للمجموعة.
على الرغم من أنّه ليس من الضروري فهم الرياضيات بشكل معمّق، إلا أنّه بالنسبة إلى المهتمين، فإنّ خوارزمية "الوسيط الحسابي" هي حالة خاصة من خوارزمية زيادة التوقّعات. يمكنك الاطّلاع على ملاحظات المحاضرة حول الموضوع من جامعة بنسلفانيا.