التجميع بالمتوسطات k

تبحث خوارزمية المتوسطات k عن تقسيم للبيانات إلى k مجموعة يصغّر مجموع المسافات التربيعية من كل نقطة إلى مركز مجموعتها. والبحث في كل التقسيمات الممكنة غير عملي، فتستعمل الخوارزمية تحسينًا تكراريًا بسيطًا وسريعًا.

وتتناوب خطوتان. فبالنظر إلى المراكز الحالية، تُسنَد كل نقطة إلى أقربها. وبالنظر إلى تلك الإسنادات، يُعاد حساب كل مركز كمتوسط أعضائه. وكل خطوة لا يمكنها إلا أن تخفض مجموع المسافات التربيعية داخل العناقيد أو تُبقيه، وبما أن الإسنادات الممكنة متناهية العدد فلا بدّ للإجراء أن ينتهي.

غير أن التقارب يكون إلى أمثلية محلية. فقد تنتج تهيئة رديئة تقسيمًا سيئًا فعلًا، ولذلك تنفّذ التطبيقات الخوارزمية عدة مرات من نقاط بدء مختلفة وتحتفظ بأفضل نتيجة. ويحسّن مخطط التهيئة k-means++‎ الأمر بمباعدة المراكز الابتدائية بدل اختيارها بانتظام عشوائيًا.

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

في تقسيم العملاء بحسب الإنفاق وتكرار الزيارة عند ‎k = 3‎، تبدأ الخوارزمية من ثلاثة مراكز اعتباطية، وتُسنِد كل عميل إلى أقربها، ثم تنقل كل مركز إلى متوسط العملاء المسنَدين إليه، وتكرّر حتى تتوقف الإسنادات عن التغير.

واختيار k هو المسألة الأصعب. فطريقة الكوع ترسم التباين الكلي داخل العناقيد بدلالة k: وهو ينخفض دائمًا كلما ارتفع k، لكن معدل التحسن يهبط عادةً هبوطًا حادًا عند نقطة ما، وتلك الانحناءة تقترح قيمة معقولة. ويستخدم جيمس وزملاؤه هذا النوع من معيار الكوع البصري تحديدًا عند تقرير كم مركّبة يُحتفظ بها في تحليل المركّبات الرئيسية.

والمعيار استدلال تقريبي لا اختبار. فعلى بيانات لا بنية عنقودية حقيقية فيها تعيد الخوارزمية مع ذلك k مجموعة أنيقة المظهر، وقد يكون الكوع ملتبسًا أو غائبًا. وينبغي التحقق من البنية العنقودية بمعرفة المجال لا قبولها لمجرد أن الخوارزمية أنتجتها.