K-Means Clustering

يقسم K-Means البيانات إلى K عناقيد عبر تقليل المسافة التربيعية داخل العنقود (العطالة).

$$ J = \sum_{i=1}^{N} \min_{1 \leq j \leq K} \left\lVert x_i - \mu_j \right\rVert^2 $$

يُسند كل عيّنة إلى أقرب مركز، ثم تُعاد حساب المراكز كمتوسط العينات المُسندة.

تتناوب الخوارزمية بين خطوتين حتميتين:

$$ c_i \leftarrow \arg\min_j \lVert x_i - \mu_j \rVert^2 $$

$$ \mu_j \leftarrow \frac{1}{|C_j|}\sum_{x_i \in C_j} x_i $$

تنخفض العطالة بشكل رتيب حتى الوصول إلى أمثلية محلية.

التهيئة العشوائية بسيطة لكنها قد تبدأ من بذور سيئة.

k-means++ يوزع المراكز الأولية وغالبًا ما يعطي تقاربًا أسرع وعطالة نهائية أقل.

في الإنتاج، شغّل عدة مرات ببذور مختلفة لتقليل الحساسية للحدود المحلية.