الـ clustering (التجميع) — K-Means | ML-101

التعلّم من غير labels

كل الـ algorithms اللي درسناها في الوحدات اللي فاتت — الـ linear regression، والـ decision trees، والـ support vector machines — اتعلّمت من أمثلة labeled (مُسمّاة). كان فيه حد بيقول للـ model إن الإيميل ده spam أو إن الورم ده خبيث. بس أغلب البيانات في الدنيا بتوصل من غير labels. والـ unsupervised learning (التعلم غير الخاضع للإشراف) هو فرع الـ Machine Learning اللي بيكتشف البنية في البيانات اللي مالهاش labels.

والـ clustering (التجميع) هو المهمة الأساسية في الفرع ده: إنك تقسم الـ dataset لمجموعات بحيث النقط اللي جوه المجموعة الواحدة تبقى شبه بعض أكتر من نقط المجموعات التانية. والـ clustering بيتطبّق في تقسيم العملاء، وتنظيم المستندات، والـ anomaly detection، وضغط الصور، والتصنيف البيولوجي. والتحدي الأساسي إن تعريف “التشابه” لازم يبقى دقيق رياضيًا، وممكن ميبقاش عدد المجموعات معروف من الأول.

الـ K-Means algorithm

الـ K-Means هو أبسط algorithms الـ clustering وأكترها استخدامًا. بتدّيله dataset فيها n نقطة وعدد مستهدف K من المجموعات، فبيقسم البيانات بإنه يبدّل بين خطوتين لحد التقارب:

الخطوة 1 — الـ assignment: كل نقطة بتتحط مع أقرب centroid (مركز تجمّع). والمسافة بتتقاس بالمسافة الإقليدية. وكل نقطة تبع مجموعة واحدة بالظبط.

الخطوة 2 — الـ update: كل centroid بيتعاد حسابه على إنه متوسط كل النقط اللي اتحطّت معاه. فالـ centroid بيتنقل لنص مجموعته.

العملية بتتكرّر لحد ما الـ assignments تبطّل تتغيّر. والتقارب مضمون لأن كل خطوة بتقلّل الـ objective function — مجموع مربعات المسافات جوه المجموعات — وعدد الـ assignments الممكنة محدود.

الـ objective بتاع K-Means (الـ inertia)

J = \sum_{k=1}^{K} \sum_{\mathbf{x} \in C_k} \|\mathbf{x} - \boldsymbol{\mu}_k\|^2

J هو المجموع الكلي لمربعات المسافات جوه المجموعات. وμ_k هو centroid المجموعة C_k. والـ K-Means بيصغّر J خطوة خطوة — كل خطوة مضمون إنها بتقلّل J أو تسيبها زي ما هي.

الـ K-Means بيتقارب عند local minimum ومش لازم يبقى الـ global minimum. والنتيجة النهائية بتعتمد جامد على أماكن الـ centroids في الأول، ومن هنا أهمية الـ initialization.

اختيار K

K هو hyperparameter لازم يتحدّد قبل التدريب. وفيه طريقتين مشهورتين بيساعدوا تختار K المناسب:

الـ elbow method (طريقة المِرفَق): شغّل K-Means لـ K = 1، 2، 3، … وارسم الـ inertia (القصور الذاتي) (الـ variance الكلي جوه المجموعات) قصاد K. وكل ما K تزيد، الـ inertia دايمًا بتقل — لحد ما توصل صفر لما K = n. و“الكوع” — النقطة اللي إضافة مجموعات زيادة بعدها بتجيب فايدة صغيرة — بيشاور على K طبيعي. وعمليًا اللفّة دي غالبًا بتبقى ناعمة وتقديرية.

الـ silhouette score (درجة الصورة الظلية): لكل نقطة i، احسب متوسط المسافة لكل النقط التانية في مجموعتها (a(i)) ومتوسط المسافة لكل النقط في أقرب مجموعة تانية (b(i)). والـ silhouette score هي:

الـ silhouette score

s(i) = \dfrac{b(i) - a(i)}{\max\bigl(a(i),\, b(i)\bigr)}

s(i) بتتراوح بين -1 (متصنّفة غلط) و+1 (متجمّعة بشكل مثالي). ودرجة قريبة من 0 معناها إن i على الحدود. ومتوسط s(i) على كل النقط بيدّي الـ silhouette score الكلية لـ K معيّن — اختار K اللي بيكبّرها.

معرفة المجال فوق المقاييس

لا الـ elbow method ولا الـ silhouette score حاسمين. الاتنين مجرد إرشادات. وعمليًا، معرفة المجال — زي إنك عارف إن عندك خمس فئات منتجات أو تلات مستويات عملاء — هي الدليل الأوثق لاختيار K. استخدم المقاييس عشان تتأكد من اختيارك مش عشان تاخده بعمى.

الـ initialization والـ K-Means++

الـ K-Means العادي بيعمل initialization للـ centroids بإنه يختار K نقطة عشوائي من الـ dataset. وده سريع بس هش: initialization وحشة ممكن توصّل لـ local minima ضعيفة المجموعات فيها شكلها مش طبيعي. وحل مشهور إنك تشغّل K-Means كذا مرة بـ random seeds مختلفة وتحتفظ بأحسن نتيجة (أقل inertia). وscikit-learn بتعمل ده بـ n_init=10 افتراضيًا.

والطريقة الأحسن بكتير هي الـ K-Means++، استراتيجية initialization أذكى قدّمها آرثر وفاسيليفيتسكي سنة 2007. بدل ما تحط كل الـ centroids عشوائي، بتفرّشها:

1. اختار أول centroid عشوائي بالتساوي.

2. لكل centroid بعد كده، اختار نقطة باحتمال متناسب مع مربع مسافتها من أقرب centroid اتختار قبل كده.

3. عيد لحد ما K centroids يتحطّوا.

الـ initialization بتاعة K-Means++ مضمونة احتماليًا إنها تطلّع حل في حدود O(log K) من الـ minimum الأمثل. وعمليًا بتتقارب أسرع وبتطلّع مجموعات أحسن بكتير من الـ initialization العشوائية. وهي دلوقتي الافتراضية في أغلب التطبيقات ومنها scikit-learn.

قيود الـ K-Means

الـ K-Means سريع وبيكبر كويس بس شايل افتراضات في بنيته بتحدّ من استخدامه:

مجموعات كروية: الـ K-Means بيحط كل نقطة مع أقرب centroid بالمسافة الإقليدية، وده بيفترض ضمنيًا إن المجموعات محدّبة وإقليدية — شكلها كتل في فضاء الـ features. ومبيقدرش يكتشف مجموعات ممطوطة أو منحنية أو شكلها مش منتظم.

أحجام متساوية: الـ centroids بتاعة K-Means متوسطات، بتتشد ناحية المناطق الكثيفة. ولما المجموعات تختلف في الحجم أو الكثافة، الـ algorithm بيميل إنه يقسم المجموعات الكبيرة ويدمج الصغيرة.

الحساسية للـ outliers: المتوسطات مش متينة قصاد القيم المتطرفة. outlier واحد يقدر يشد centroid بعيد عن الكتلة الأساسية لمجموعته.

محتاج K من الأول: على عكس الطرق الـ hierarchical، الـ K-Means محتاج K متحدّد قبل التدريب. ولو العدد الحقيقي للمجموعات مش معروف، لازم تشغّل الـ algorithm كذا مرة وتستخدم معيار اختيار.

بيفترض المسافة الإقليدية: المسافة الإقليدية مش مناسبة لكل أنواع البيانات. الـ features الفئوية والنصوص والبيانات اللي ليها بنية graph محتاجة distance functions مختلفة وalgorithms متخصصة.

الـ mini-batch K-Means

الـ K-Means العادي محتاج يحمّل كل البيانات في الـ memory ويعالج الـ dataset كلها في كل iteration. ومع datasets ضخمة جدًا — ملايين النقط — ده بيبقى بطيء لدرجة مستحيلة. والـ mini-batch K-Means بيعالج ده بإنه يحدّث الـ centroids باستخدام mini-batch عشوائية صغيرة من البيانات في كل خطوة، زي الـ stochastic gradient descent في الـ supervised learning.

في كل iteration، بتتسحب عيّنة عشوائية صغيرة (عادةً 100–10,000 نقطة) من الـ dataset. كل نقطة بتتحط مع أقرب centroid، وأماكن الـ centroids بتتحدّث بمتوسط متحرك بـ learning rate بيقل مع الوقت. وده بيقلّل الحساب جامد وفي نفس الوقت بيوصل لحل كويس.

الـ trade-off: الـ mini-batch K-Means بيتقارب أسرع في الوقت الفعلي بس بيطلّع inertia أعلى شوية من الـ K-Means الكامل. ولأغلب التطبيقات العملية اللي بياناتها كبيرة، مكسب السرعة بيغلب خسارة الجودة الصغيرة. وscikit-learn بتوفّر MiniBatchKMeans بنفس الـ interface بتاع KMeans العادي.

اعمل scaling للـ features دايمًا

زي الـ SVMs، الـ K-Means حسّاس لمقياس الـ features لأنه بيستخدم المسافة الإقليدية. feature قيمها بالآلاف (زي الدخل السنوي) هتسيطر على حسابات المسافة قصاد feature قيمها بالآحاد (عدد المشتريات). فاعمل دايمًا normalization للـ features لمتوسط صفر وvariance واحد قبل الـ clustering. ودي من أشهر غلطات الـ unsupervised learning.

في الدرس الجاي، هنعدّي الـ K-Means ونستكشف الـ hierarchical clustering اللي بيبني شجرة من التجميعات المتداخلة، وDBSCAN اللي بيكتشف مجموعات بأي شكل على أساس الكثافة المحلية — من غير ما يحتاج K.

أهم اللي اتعلمناه

الـ clustering بيقسم البيانات اللي مالهاش labels لمجموعات من نقط شبه بعض من غير ما يحتاج labels.
الـ K-Means بيبدّل بين إنه يحط النقط مع أقرب centroids وإنه يحدّث الـ centroids كمتوسطات المجموعات لحد التقارب.
الهدف هو تصغير الـ inertia: المجموع الكلي لمربعات المسافات من كل نقطة للـ centroid بتاعها.
الـ K-Means بيتقارب عند local minimum — الـ initialization مهمة. والـ K-Means++ بيزرع الـ centroids بذكاء وهو الافتراضي دلوقتي.
اختار K بالـ elbow method (منحنى الـ inertia) أو الـ silhouette score؛ ومعرفة المجال غالبًا الأوثق.
الـ K-Means بيفترض مجموعات كروية وأحجامها قريبة من بعض، وحسّاس للـ outliers ولمقياس الـ features.
الـ mini-batch K-Means بيكبر مع الـ datasets الكبيرة بإنه يحدّث الـ centroids على عيّنات عشوائية في كل iteration.