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