الانتقال إلى المحتوى
العودة إلى نتائج البحث

تجميع K-means

قدّمه
MacQueen, J. B.; Lloyd, S. P.
السنة
1967 (formalized 1982)
النوع
Partitional clustering
العائلة
Machine learning

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

K-means هي خوارزمية تجميع تجزيئي غير خاضع للإشراف كلاسيكية تقسم مجموعة بيانات إلى K مجموعات غير متداخلة عن طريق تعيين كل ملاحظة بشكل متكرر إلى أقرب مركز لها وتحديث المراكز كمتوسط للنقاط المعينة لها. إنها واحدة من أكثر الأدوات الاستكشافية استخدامًا في التعلم الآلي وتحليل البيانات.

الفكرة الحدسية وراء الطريقة

تخيل إسقاط K مغناطيس على خريطة من نقاط البيانات. تنجذب كل نقطة إلى أقرب مغناطيس لها، ثم يتحرك كل مغناطيس إلى مركز ثقل النقاط التي جذبها. كرر دورة السحب والتحريك هذه حتى لا يتحرك شيء: لقد وجدت المغناطيسات K تجمعات طبيعية. تُضفي K-means طابعًا رسميًا على هذه الفكرة بالضبط، مما يقلل من إجمالي المسافة المربعة من كل نقطة إلى مركز مجموعتها، والتي تسمى مجموع المربعات داخل الكتلة (WCSS أو القصور الذاتي).

التاريخ

تم تقديم فكرة k-means بشكل مستقل بواسطة MacQueen في عام 1967، الذي صاغ المصطلح، وتم إضفاء الطابع الرسمي عليها كخوارزمية تكرارية فعالة بواسطة Stuart Lloyd في Bell Labs في الخمسينيات (نُشرت عام 1982). عالج تحسين تهيئة k-means++ بواسطة Arthur و Vassilvitskii في عام 2007 مشكلة حساسية الحد الأدنى المحلي. اليوم، تظل k-means طريقة تعلم غير خاضعة للإشراف أساسية تُدرّس في كل منهج علم بيانات تقريبًا.

متى تُستخدم

تناسب K-means التجميع الاستكشافي لمجموعات البيانات الكبيرة والرقمية البحتة عندما تحتاج إلى تقسيم سريع وقابل للتطوير وتكون مرتاحًا لتحديد K مسبقًا أو البحث عنه باستخدام طريقة الكوع أو الصورة الظلية. تعمل بشكل جيد لتجزئة العملاء، وضغط الصور، وتجميع موضوعات المستندات، والمعالجة المسبقة قبل التعلم الخاضع للإشراف. تجنبها عندما تكون المجموعات غير كروية، أو ذات أحجام أو كثافات متفاوتة بشكل كبير، أو عندما تكون الميزات فئوية أو ترتيبية (استخدم k-modes أو k-prototypes بدلاً من ذلك)، أو عندما يكون عدد المجموعات غير معروف تمامًا وتجارب K المتغيرة غير مجدية، أو عندما تحتوي البيانات على العديد من القيم الشاذة (استخدم DBSCAN أو المتغيرات القوية بدلاً من ذلك).

الحدود والاعتبارات

  • تتطلب تحديد K مسبقًا؛ يؤدي اختيار K بشكل سيء إلى مجموعات لا معنى لها.
  • تفترض مجموعات كروية ومتشابهة الحجم؛ يتم تقسيم أو دمج المجموعات المطولة أو غير المنتظمة أو ذات المقاييس المختلفة بشكل غير صحيح.
  • حساسة للقيم الشاذة: يمكن لنقطة متطرفة واحدة أن تسحب المركز بعيدًا عن الجزء الأكبر من الكتلة.
  • تعمل فقط مع الميزات الرقمية المستمرة؛ تتطلب البيانات الفئوية خوارزمية مختلفة (k-modes).
  • تتقارب إلى حد أدنى محلي؛ يمكن أن تختلف النتائج عبر التشغيلات ببذور عشوائية مختلفة ما لم يتم استخدام k-means++ أو عمليات إعادة تشغيل متعددة.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • سريعة وقابلة للتطوير: O(nKdi) لكل تكرار، عملية على ملايين الملاحظات مع K وأبعاد معتدلة.
  • سهلة التنفيذ، ومتاحة على نطاق واسع في كل إطار عمل رئيسي للتعلم الآلي، وسهلة الشرح للجماهير غير التقنية.
  • تعمل بشكل جيد على المجموعات الكبيرة والمفصولة جيدًا والكروية تقريبًا وذات الحجم المماثل.
  • يقلل تهيئة k-means++ بشكل كبير من الحساسية للظروف الأولية مقارنة بالتهيئة العشوائية.
  • حتمية ضمن بذرة عشوائية ثابتة، مما يجعل النتائج قابلة للتكرار.

التطبيقات

  • تجزئة العملاء للتسويق والتخصيص بناءً على الميزات السلوكية أو الديموغرافية.
  • ضغط الصور عن طريق تكميم ألوان البكسل إلى K قيم تمثيلية (تكميم الألوان).
  • تجميع المستندات والنصوص كخطوة في مسارات نمذجة الموضوع بعد التحويل إلى متجه.
  • المعالجة المسبقة للكشف عن الشذوذ: النقاط البعيدة عن أي مركز هي قيم شاذة محتملة.
  • خطوة التهيئة للخوارزميات الأكثر تعقيدًا مثل نماذج الخليط الغاوسي أو التجميع الهرمي.
  • تحليل التعبير الجيني لتجميع الجينات أو العينات ذات أنماط التعبير المتشابهة.

كيف يعمل

كيف يعمل

1

توضع K مراكز تجمعات في فضاء الميزات، إما عن طريق اختيار K نقاط بيانات عشوائيًا (Forgy) أو عن طريق استراتيجية k-means++ الأكثر ذكاءً التي تنشر المراكز الأولية لتقليل فرصة الوقوع في الحد الأدنى المحلي السيئ. اختيار التهيئة مهم: عادةً ما تؤدي k-means++ إلى تقارب أسرع وحلول نهائية أفضل.

2

تُعيّن كل ملاحظة إلى الكتلة التي يكون مركزها الأقرب وفقًا للمسافة الإقليدية. ينشئ هذا التعيين الصارم K أقسامًا غير متداخلة للبيانات. رسميًا، تُعيّن كل نقطة x_i إلى الكتلة c_i = argmin_k ||x_i - mu_k||^2.

الصيغة
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

يُعاد حساب كل مركز كمتوسط حسابي لجميع النقاط المعينة حاليًا لتلك الكتلة: mu_k = (1/|C_k|) مضروبًا في مجموع كل x_i في C_k. تضمن هذه الخطوة أن المركز الجديد يقلل من WCSS داخل كل كتلة بالنظر إلى التعيين الحالي.

الصيغة
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

تتوالى خطوات التعيين والتحديث حتى تتوقف مواقع المراكز عن التغير (أو تتغير بأقل من عتبة التسامح) أو يتم الوصول إلى الحد الأقصى لعدد التكرارات. تضمن الخوارزمية التقارب إلى حد أدنى محلي لـ WCSS، على الرغم من أنه ليس بالضرورة الحد الأدنى العالمي.

5

تُقيّم جودة الحل باستخدام إجمالي WCSS (القصور الذاتي) J = مجموع عبر الكتل لمجموع عبر النقاط المعينة لـ ||x_i - mu_k||^2. اختيار K هو شاغل منفصل يتم تناوله بواسطة طريقة الكوع (elbow method)، أو درجات الصورة الظلية (silhouette scores)، أو إحصائيات الفجوة (gap statistics)، حيث تتطلب الخوارزمية نفسها تحديد K مسبقًا.

الصيغة
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2

الأخطاء الشائعة

  • نسيان توحيد الميزات قبل التجميع — ستسيطر المتغيرات ذات المقاييس الكبيرة على حسابات المسافة.
  • اختيار K عن طريق فحص WCSS داخل العينة فقط دون مخطط الكوع أو التحقق من الصورة الظلية، مما يؤدي إلى K صغير أو كبير بشكل تافه.
  • تشغيل تهيئة واحدة فقط وقبول النتيجة الأولى دون عمليات إعادة تشغيل متعددة للحماية من الحد الأدنى المحلي السيئ.
  • تضمين متغيرات فئوية أو ترتيبية في مصفوفة الميزات دون ترميز مناسب أو التبديل إلى k-modes.
  • معاملة تسميات الكتلة كهويات مجموعة ذات معنى دون التحقق الخارجي، خاصة عندما لا تكون الكتل مفصولة جيدًا.

الأسئلة الشائعة

كيف أختار العدد الصحيح للمجموعات K؟

شغّل k-means لمجموعة من قيم K، ارسم مجموع المربعات داخل الكتلة مقابل K، وابحث عن 'كوع' حيث يتباطأ معدل الانخفاض بشكل حاد. استكمل هذا بدرجات الصورة الظلية، التي تقيس مدى تشابه كل نقطة مع مجموعتها الخاصة مقابل المجموعات المجاورة؛ تشير الصورة الظلية المتوسطة الأعلى إلى مجموعات محددة بشكل أفضل.

لماذا أحصل على نتائج مختلفة في كل مرة تشغيل؟

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

هل تعمل k-means مع البيانات الفئوية؟

لا. تعتمد K-means على المسافة الإقليدية ومتوسطات المراكز، وهي غير معرفة للمتغيرات الفئوية. للبيانات الفئوية البحتة استخدم k-modes؛ للبيانات المختلطة الرقمية والفئوية استخدم k-prototypes.

متى يجب أن أُفضّل DBSCAN أو GMM على k-means؟

استخدم DBSCAN عندما تكون للمجموعات أشكال غير منتظمة أو تحتاج إلى اكتشاف تلقائي للقيم الشاذة دون تحديد K. استخدم نماذج الخليط الغاوسي (GMM) عندما تريد تعيينات مجموعات ناعمة (احتمالية) أو مجموعات بأحجام واتجاهات مختلفة، على حساب تعقيد حسابي أعلى.

هل أحتاج إلى قياس ميزاتي؟

نعم، دائمًا تقريبًا. تستخدم K-means المسافة الإقليدية، لذا فإن الميزات ذات النطاقات الرقمية الكبيرة ستسيطر على التجميع. طبق توحيد z-score أو قياس min-max قبل ملاءمة k-means، ما لم تكن جميع الميزات بالفعل على نفس المقياس.

طرق ذات صلة

المصادر

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    افتح مرجع DOI
    تم النسخ.
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    افتح مرجع المنشور
    تم النسخ.