الوحدة 4 — التجميع الهرمي والمخطّطات الشجرية

كانت k-means تُلزِمك باختيار $k$ قبل أن ترى أيّ شيء. ويعكس التجميع الهرمي الترتيب: فيبني أوّلاً الشجرة كاملةً لكلّ التجميعات الممكنة، وتقرّر أنت بعد ذلك أين تقطعها. فترى البنية قبل الحسم — وهي ميزةٌ كبيرة في الاستكشاف.

المبدأ التكتّلي: الدمج خطوةً خطوة

تنطلق المقاربة السائدة من الأدقّ وتصعد:

1. تُشكّل كلّ ملاحظة مجموعتها الخاصّة؛
2. تُدمَج أقرب مجموعتين؛
3. يُكرَّر ذلك حتى لا تبقى إلّا مجموعةٌ واحدة تحوي كلّ شيء.

ويُشكّل تاريخ هذه الدمجات الكامل — من انضمّ إلى من، وعند أيّ مسافة — شجرةً: هي المخطّط الشجري. ولا شيء يُقرَّر أثناء البناء؛ فكلّ درجات التفصيل تتعايش في الشجرة.

معيار الربط: القرار الذي يُغيّر كلّ شيء

«أقرب مجموعتين» يفترض تعريف المسافة بين مجموعتين، لا بين نقطتين. وهذا الاختيار، معيار الربط، يُحدّد شكل المجموعات الناتجة أكثر بكثير من غيره.

المعيار	المسافة بين المجموعتين	الميل
الربط الأحد	بين أقرب نقطتين لهما	يتبع الأشكال الممدودة، لكن يُسبّب التسلسل
الربط التامّ	بين أبعد نقطتين لهما	مجموعات متراصّة، حسّاس للشواذّ
الربط المتوسّط	متوسّط كلّ الأزواج	تسويةٌ متوازنة
Ward	زيادة القصور الناتجة عن الدمج	مجموعات متجانسة متقاربة الحجم

Ward هو الافتراض المعقول: فبتصغير زيادة القصور عند كلّ دمج يسعى إلى هدف التراصّ نفسه الذي تسعى إليه k-means، بنتائج متقاربة غالباً لكن مصحوبةً بالشجرة الكاملة. أمّا الربط الأحد فهو الأكثر تفرّداً: قادرٌ على تتبّع الأشكال الممتدّة، لكنّه يشكو أثر التسلسل، حيث تُربَط مجموعتان متمايزتان بجسرٍ رقيق من نقاطٍ وسيطة.

from scipy.cluster.hierarchy import linkage, dendrogram, fcluster

Z = linkage(X_s, method="ward")
dendrogram(Z, truncate_mode="lastp", p=30)   # شجرة مقروءة على الأحجام الكبيرة
groupes = fcluster(Z, t=4, criterion="maxclust")   # قطعٌ إلى 4 مجموعات

قراءة مخطّط شجري واختيار القطع

على المخطّط الشجري، كلّ دمجٍ شريطٌ أفقي يدلّ ارتفاعه على المسافة التي حدث عندها. وهناك تكمن المعلومة: فدمجٌ مرتفعٌ جدّاً يعني أنّنا وحّدنا مجموعتين كانتا متباعدتين — أي، على الأرجح، بنيتين متمايزتين فعلاً.

ومن هنا قاعدة القراءة: نقطع الشجرة تحت قفزةٍ رأسية كبيرة. فالأفرع المنفصلة بذلك تقابل مجموعاتٍ متمايزة جيّداً، وعدد الأفرع المقطوعة يعطي $k$. وهذه القراءة البصرية نظيرُ طريقة الكوع في الوحدة 3، بميزةٍ إضافية: نرى في الوقت نفسه كلّ درجات التفصيل الممكنة، ويُقرأ تداخل المجموعات (شرائح وشرائح فرعية) مباشرةً.

القوّة والكلفة والتكامل مع k-means

فالميزة الرئيسة هي الاستكشاف: لا $k$ مفروض، وتصويرٌ غني، وهرميّة المجموعات الفرعية زيادةً. ويُضاف إليها المرونة: يقبل الهرمي أيّ مصفوفة مسافات، بما فيها غير الإقليدية — وهو نافعٌ لبيانات نصّية أو متسلسلات، حيث تتطلّب k-means متوسّطاً قابلاً للحساب.

والثمن هو كلفة الحساب، التربيعية في الذاكرة كما في الزمن: فبعد بضع عشرات الآلاف من الملاحظات تصير مصفوفة المسافات غير عملية. وفرقٌ جوهري آخر: الدمج نهائي ولا يُعاد فيه النظر أبداً، بينما تُعيد k-means إسناد النقاط عند كلّ تكرار.

الثنائي الناجح عملياً

على مجموعة بياناتٍ كبيرة، تجمع المقاربة الفعّالة بين الاثنين: تجميعٌ هرمي على عيّنة من بضعة آلاف نقطة لقراءة البنية وتقدير $k$ في المخطّط الشجري، ثمّ k-means بذلك $k$ على البيانات كلّها. فنستعيد وضوح الأوّل وقدرة الثاني على المعالجة.

الخلاصة

• تدمج المقاربة التكتّلية أقرب المجموعات خطوةً خطوة وتُنتِج شجرةً كاملة: المخطّط الشجري.
• يحسم معيار الربط شكل المجموعات؛ وWard هو الافتراض المعقول، والربط الأحد يتبع الأشكال الممدودة لكنّه يُسلسِل.
• نختار $k$ بـالقطع تحت قفزةٍ رأسية كبيرة في المخطّط؛ وتُقرأ كلّ درجات التفصيل والتداخل بلمحة.
• ممتازٌ في الاستكشاف ومتوافقٌ مع أيّ مصفوفة مسافات، لكن كلفةٌ تربيعية ودمجاتٌ لا رجعة فيها.

الوحدة التالية: DBSCAN، الذي يتخلّى عن مفهوم المركز لكشف مجموعاتٍ بأشكال حرّة وعزل الضجيج.