تجميع K-Means

يقوم تجميع K-means بتقسيم الملاحظات إلى عدد ثابت من المجموعات عن طريق تقليل مجموع المسافات المربعة داخل المجموعة إلى مراكز المجموعات.

Definition

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

Scope

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

Core questions

• كيف يمكن تقسيم الملاحظات لتقليل التشتت داخل المجموعة؟
• لماذا تتقارب الخوارزمية فقط إلى حل أمثل محلي وكيف يمكن التخفيف من ذلك؟
• كيف يتم اختيار عدد المجموعات؟
• ما هي أشكال وحجوم المجموعات التي تفترضها الطريقة ضمنيًا؟

Key theories

تقليل مجموع المربعات داخل المجموعة

يسعى K-means إلى التقسيم ومجموعة المراكز التي تقلل إجمالي المسافة المربعة من النقاط إلى مراكز مجموعاتها، وهو هدف تقلل من أجله تكرارات التعيين-التحديث المتناوبة المعيار بشكل رتيب.

حساسية الحل الأمثل المحلي

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

Clinical relevance

يُعد K-means طريقة سريعة وقابلة للتطوير لتقسيم مجموعات البيانات الكبيرة، ويُستخدم في تكميم المتجهات، وتقليل ألوان الصور، وتجزئة العملاء، وكتهيئة لنماذج أكثر تعقيدًا.

History

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

Debates

الافتراضات الضمنية لـ K-means

يُفضل تقليل المسافة الإقليدية المربعة المجموعات الكروية تقريبًا والمتساوية الحجم، لذا يمكن أن يؤدي K-means إلى نتائج مضللة عندما تكون المجموعات ممدودة أو غير متساوية الحجم أو غير محدبة، مما يحفز البدائل القائمة على النموذج أو الكثافة.

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

لماذا يعطي K-means نتائج مختلفة في كل مرة يتم تشغيله؟

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

كيف أختار عدد المجموعات k؟

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