#k-means — التعلّم غير المُشرَف

التجميع بلا تسميات: مراكز تتحرّك، قصور ذاتي يهبط، اختيار k — والأشكال التي يفشل عليها k-means.

ما ستُجرّبه

مرحبًا بك في #k-means. على الشاشة: 150 نقطة رمادية داخل مكعّب، مجتمعةً بوضوح في أربع كتل… لم يضع أحد لها تسميات. الكرات الملوّنة الأربع الكبيرة هي المراكز (centroids): وضعناها للتوّ عشوائيًا على أربع نقاط من مجموعة البيانات، ولم تُلوَّن أيّ نقطة بعد. هذا كلّ ما يحصل عليه k-means: سحابة نقاط، وعدد k، وقاعدة واحدة بسيطة تُعاد. لا حقيقة مرجعية للنسخ عنها: هذا تعلّم غير مراقَب (unsupervised learning).
شغّل جولة واحدة: /step. مرحلتان. التخصيص (assignment): كلّ نقطة تنضمّ إلى أقرب مركز وتأخذ لونه. التحديث (update): كلّ مركز يقفز إلى متوسّط النقاط التي كسبها للتوّ.
جولة أخرى /step. تُبدّل بضع نقاط جانبها عند الحدّ بين مجموعتين، وتتحرّك المراكز أقلّ ممّا تحرّكت أوّل مرّة. راقب القصور الذاتي (inertia) في اللوحة اليمنى: مجموع مربّعات المسافات من كلّ نقطة إلى مركزها. يهبط عند كلّ جولة، ولا يرتفع أبدًا: لا يمكن لأيّ من المرحلتين أن ترفعه.
دعه يعمل حتّى النهاية: /run. عندما لا تعود أيّ نقطة تُبدّل جانبها، تتوقّف المراكز عن الحركة: هذا هو التقارب (convergence). لكن انظر إلى النتيجة: بهذه البداية، يتقاسم مركزان وقعا في الكتلة نفسها كتلةً واحدة، بينما يضطرّ مركز وحيد إلى تغطية كتلتين في آنٍ واحد. هذا أدنى موضعي (local minimum): لن يُزحزحهم شيء.
العلاج الأكثر شيوعًا هو بداية أفضل: /init kmeans++. يُسحب المركز الأوّل عشوائيًا؛ ويُسحب كلّ مركز تالٍ باحتمال يتناسب مع مربّع مسافته إلى أقرب مركز موضوع مسبقًا. النقاط المعزولة، البعيدة عن كلّ شيء، أرجحُ للاختيار بكثير: تنتشر المراكز الأوّلية، وتصبح البدايات السيّئة نادرة.
شغّل /run مرّة أخرى وقارِن القصور الذاتي النهائي بالتشغيل السابق (أحتفظ به عنك). النقاط نفسها، وقيمة k نفسها: تغيّرت نقطة الانطلاق فحسب.
لنغيّر شكل السحابة: /dataset rings. حلقتان متمركزتان، إحداهما داخل الأخرى، في المستوى الأفقي. للعين البشرية، مجموعتان واضحتان.
أوّلًا /run، لرؤية القطع الشرائحي: k-means لا يرى شكل المجموعة، بل المسافة إلى مركز فقط (للحلقات، ستحتاج إلى #dbscan). ثمّ السؤال الذي كنّا نتحاشاه: لماذا 4؟ اكتب /elbow: أُعيد تشغيل k-means لـk = 1 حتّى 8 وأسجّل القصور الذاتي النهائي لكلٍّ منها.
دورك: /dataset blobs ثمّ /elbow للحصول على مرفق نظيف عند k = 4؛ /k 2 ثمّ /run على الحلقات (شريحتان، لا حلقتان)؛ /dataset moons و/dataset elongated، شكلان آخران يقطعهما k-means خطأً؛ /init random مع عدّة قيم /seed لجمع الأدنى الموضعية؛ /links لرؤية من ينتمي إلى مَن؛ /reset للبدء من جديد. التالي: #pca، لإسقاط هذه السحب على مستوى ثنائي قبل تجميعها، و#hierarchical-clustering الذي يحرّرك من اختيار k.

أوامر القناة

/k <1..8> — يغيّر عدد العناقيد؛ يُعيد إسقاط المراكز، والتكرار 0.
/step — تكرار واحد لخوارزمية لويد: تخصيص ثمّ تحديث للمراكز.
/run — يكرّر حتّى التقارب (إزاحة < 1e-4) أو 30 جولة.
/init <random|kmeans++> — يغيّر تهيئة المراكز؛ يعيد الانطلاق من التكرار 0.
/seed <1..99> — يُعيد سحب النقاط والمراكز الابتدائية ببذرة أخرى.
/dataset <blobs|rings|moons|elongated> — يغيّر شكل سحابة النقاط؛ يعيد الانطلاق من التكرار 0.
/links — يُظهر أو يُخفي خطًّا رفيعًا من كلّ نقطة إلى مركزها.
/elbow — طريقة المرفق: القصور الذاتي النهائي لـ k = 1..8.
/reset — العودة إلى blobs، k = 4، تهيئة عشوائية، التكرار 0.

المسرد

k-means: خوارزمية تقسيم توزّع n نقطة على k مجموعات بتقليل مجموع مربّعات المسافات من كلّ نقطة إلى مركز مجموعتها. سريعة وبسيطة، لكنّها تفترض مجموعات مستديرة وتشترط تحديد k مسبقًا.
المركز (centroid): مركز العنقود: المتوسّط (المركز الحسابي) لجميع النقاط المخصّصة له. هذه هي «الذاكرة» الوحيدة التي يتركها العنقود في k-means.
القصور الذاتي (inertia): مجموع مربّعات المسافات الإقليدية بين كلّ نقطة ومركز عنقودها، لكلّ النقاط. هذا ما يقلّصه k-means عند كلّ تكرار؛ يتناقص دائمًا مع نموّ k.
التخصيص / التحديث: المرحلتان في خوارزمية لويد: كلّ نقطة تنضمّ إلى أقرب مركز (تخصيص)، ثمّ يقفز كلّ مركز إلى متوسّط نقاطه (تحديث). يُكرَّر الأمر حتّى لا يتغيّر شيء.
التقارب (convergence): حين لا تعود أيّ نقطة تغيّر عنقودها: تتوقّف المراكز عن الحركة ويكفّ القصور الذاتي عن الانخفاض. هنا نتوقّف عندما ينخفض متوسّط الإزاحة تحت 1e-4، أو بعد 30 جولة.
الأدنى الموضعي (local minimum): تقسيم يتوقّف عنده k-means دون أن يكون الأفضل الممكن: مركزان يتقاسمان مجموعة بينما يغطّي مركز آخر مجموعتين. لا مخرج للخوارزمية؛ بداية مختلفة وحدها قد تعطي نتيجة أفضل.
k-means++: تهيئة تختار المركز الأوّل عشوائيًا، ثمّ كلّ مركز تالٍ باحتمال يتناسب مع مربّع المسافة إلى أقرب مركز موضوع مسبقًا. المراكز الابتدائية تنتشر جيّدًا، ما يتفادى معظم الأدنى الموضعية السيّئة.
طريقة المرفق (elbow method): طريقة لاختيار k: يُرسم القصور الذاتي النهائي لـ k = 1، 2، 3… ويُبقى على k الذي يحدث عنده كسر في المنحنى، وهو «المرفق»: بعده لا يفيد مركز إضافي إلّا قليلًا.
التعلّم غير المراقَب (unsupervised learning): التعلّم بلا تسميات: يرى النموذج البيانات فقط، دون معرفة الإجابة الصحيحة. التجميع (k-means)، وتقليل الأبعاد (PCA)، وكشف الشذوذ تنتمي كلّها إليه.
العنقود (cluster): مجموعة من النقاط تُعدّ متشابهة فيما بينها ومختلفة عن غيرها. التجميع (clustering) هو تقسيم مجموعة بيانات إلى عناقيد دون معرفة أيّ فئات مسبقًا.

قنوات أخرى في التعلّم غير المُشرَف

#k-means — التجميع بلا تسميات: مراكز تتحرّك، قصور ذاتي يهبط، اختيار k — والأشكال التي يفشل عليها k-means.
#pca — تحليل المكوّنات الرئيسية: أوجِد المحاور التي تتغيّر عليها البيانات أكثر ما يكون، أسقِط، اضغط — وقِس ما فُقد.
#hierarchical-clustering — ادمج النقاط اثنتَين اثنتَين حتّى لا يبقى إلّا واحدة: المخطّط الشجريّ، ومعايير الوصلة، وارتفاع القطع الذي يحدّد عدد العناقيد.
#dbscan — التجميع بحسب الكثافة: إبسيلون، MinPts، نقاط النواة والحافّة والضوضاء — الخوارزميّة التي تجد الأشكال الاعتباطيّة وتتجاهل المتطفّلين.
#anomaly-detection — اكتشِف ما لا يُطابق شيئًا: z-score / ماهالانوبيس، Isolation Forest، LOF — ثلاث طرق لقول «هذه النقطة غريبة».
#t-sne-umap — ارسم خريطة الأبعاد العالية: t-SNE وUMAP يفتحان بيانات ذات 10 أبعاد إلى خريطة قابلة للقراءة في بُعدَين — الحيرة، الجيران، ومغالطات القراءة.