تدخل أحجام المجموعات والمسافة بين متوسطاتها في مسافة Ward الإقليدية؛ لذلك لا يكفي ترتيب مسافات المراكز وحده لترتيب الدمج. [1]
الخلاصة السريعة
في مثال Ward نحسب زيادة مجموع المربعات عند الدمج، ثم نقارنها؛ الرقم الذي نسميه زيادة ليس تلقائيًا ارتفاع الشجرة الذي يعرضه برنامج.
- صيغة Ward الإقليدية تعتمد على الحجمين والمسافة بين المتوسطين؛ نستخدم مجموعات مفترضة على خط عددي. [1]
- في المثال، مركزا أ وب أقرب من مركزي ب وج، لكن زيادة مجموع المربعات لدمج ب/ج هي 1.08، مقابل 1.5 لدمج أ/ب.
- العدد 1.08 هو زيادة مجموع المربعات في حسابنا؛ اصطلاح مسافة Ward في المصدر يعطي جذر ضعف الزيادة، فلا نسميهما ارتفاعًا واحدًا. [1]
- عند إدخال مصفوفة نقاط إلى ward في SciPy يستعمل المقياس الإقليدي؛ النتيجة خطوة مقارنة لا إثبات تقسيم مثالي. [2]
لماذا تدخل أحجام المجموعات؟
تعرض الصيغة الإقليدية مسافة Ward بوصفها المسافة بين المتوسطين مضروبة في جذر 2nأnب/(nأ+nب). [1]
نحسب هنا كمية أبسط للمراجعة: زيادة مجموع مربعات بعد النقاط عن متوسط مجموعتها، قبل الدمج وبعده. نسمي هذه الزيادة Δ. وبالجبر يكون Δ=nأnب/(nأ+nب) مضروبًا في مربع الفرق بين المتوسطين.
لماذا؟ بعد دمج أ وب، ينتقل متوسط كل جزء إلى المتوسط المشترك. مجموع فروق نقاط الجزء عن متوسطه يساوي صفرًا، فتختفي الحدود المتقاطعة عند توسيع المربعات، وتبقى كلفة انتقال المتوسطين. بذلك يظهر عامل الحجم بدل الاعتماد على قرب المركزين فقط.
أقرب مركزين لا يفوزان هنا
نفترض أ={−0.1، 0، 0.1} وب={0.9، 1، 1.1} وج={2.2}. متوسطاتها 0 و 1 و 2.2، وأحجامها 3 و 3 و 1. نقارن هذه المجموعات الجاهزة دون ادعاء تشغيل مراحل سابقة.
مسافة مركزي أ/ب هي 1، ومسافة ب/ج هي 1.2. لكن Δ لدمج أ/ب تساوي (3×3/6)×1²=1.5. ولدمج ب/ج تساوي (3×1/4)×1.2²=1.08.
ولدمج أ/ج تساوي (3×1/4)×2.2²=3.63. لذلك أصغر زيادة بين الخيارات الثلاثة هي ب/ج، رغم أن متوسط ب أقرب إلى أ من ج. كل الأرقام نتائج حساب افتراضي، وليست خرج تدريب أو رسم مولد.
تحقق مباشر ثم انتبه إلى اسم الرقم
مجموع المربعات داخل ب قبل الدمج يساوي 0.01+0+0.01=0.02، وداخل ج يساوي صفرًا. متوسط المجموعة المشتركة ب/ج هو (0.9+1+1.1+2.2)/4=1.3.
بعد الدمج، مجموع المربعات هو 0.16+0.09+0.04+0.81=1.1. الفرق 1.1−0.02=1.08، فيوافق Δ التي حسبناها من الحجمين والمتوسطين.
أما اصطلاح المسافة في الصيغة المذكورة، فيعطي مربع المسافة ضعف Δ. لذلك تكون مسافة ب/ج جذر 2.16، أي نحو 1.470. لا نضع 1.08 على محور ارتفاع ونسميه ناتج هذا الاصطلاح؛ هو مقدار مختلف وإن كان ترتيب الخيارين محفوظًا.
ما الحدود التي نحفظها في التطبيق؟
يوثق ward أن إدخال مصفوفة نقاط يستعمل المسافة الإقليدية؛ كما تقيد وثيقة linkage صحة Ward بالمسافات الإقليدية. [2] [3]
ثبتنا المقياس والأحجام والمجموعات الحالية. إذا استبدلنا المسافة بمقياس آخر، فلا نفترض صحة الحساب نفسه. وإذا قرأنا رسمًا، نراجع تعريف عمود الارتفاع قبل مقارنته بزيادة مجموع المربعات.
اختيار ب/ج يقلل الزيادة لهذه الخطوة وبين هذه الخيارات. لا يقدم برهانًا أن التقسيم الكامل أمثل لكل عدد مجموعات أو أنه مناسب لغرض واقعي. ولم نفحص قيمًا شاذة أو جودة. قيمة المثال أنه يكشف أثر الحجم ويميز كمية التحسين عن الرقم المعروض.
المصادر ومتابعة القراءة
- Daniel Müllner: Modern hierarchical, agglomerative clustering algorithms (يفتح في نافذة جديدة)arxiv.org
- SciPy: ward (يفتح في نافذة جديدة)docs.scipy.org
- SciPy: linkage (يفتح في نافذة جديدة)docs.scipy.org
أُعدّ هذا المقال بصياغة عربية أصلية بالاستناد إلى المصادر أعلاه، وهو مدخل تمهيدي إلى الموضوع. اقرأ منهجية المحتوى وحدوده.