الـ clustering الهرمي والكثافي (التجميع الهرمي والكثافي) | ML-101

أبعد من الـ K-Means

الـ K-Means سريع وبديهي، بس بيجبرك تختار K قبل ما تبدأ وبيفترض إن المجموعات كروية الشكل وأحجامها قريبة من بعض. والبيانات الحقيقية نادرًا ما بتحقق ده. المجرّات بتتشكّل في خيوط، وتصرّفات العملاء بتتجمّع في أشكال مش منتظمة، والتصنيفات البيولوجية متداخلة جوه بعض. وفيه عيلتين من الـ algorithms بيعالجوا القيود دي: الـ hierarchical clustering (التجميع الهرمي) اللي بيبني شجرة من المجموعات المتداخلة من غير ما يحتاج K من الأول، والـ density-based clustering (التجميع الكثافي) اللي بيكشف مجموعات بأي شكل عن طريق إنه يمشي ورا مناطق الكثافة العالية.

الـ hierarchical clustering

الـ hierarchical clustering بيطلّع سلسلة متداخلة من التقسيمات، من أول كل نقطة في مجموعة لوحدها لحد كل النقط في مجموعة واحدة. والناتج هيكل شجري اسمه الـ dendrogram (المخطط الشجري) بيسجّل تاريخ الدمج كله. وتقدر تقطع الـ dendrogram عند أي ارتفاع عشان تاخد أي عدد من المجموعات من غير ما تعيد تشغيل الـ algorithm.

وفيه استراتيجيتين بيكمّلوا بعض:

الـ agglomerative clustering (التجميع التراكمي) (من تحت لفوق): بنبدأ بـ n مجموعة كل واحدة فيها نقطة. وفي كل خطوة بندمج أقرب مجموعتين. ونعيد لحد ما تفضل مجموعة واحدة. ودي الطريقة الأشهر.

الـ divisive clustering (التجميع الانقسامي) (من فوق لتحت): بنبدأ بكل النقط في مجموعة واحدة وبعدين نقسم الأكتر اختلافًا مرة ورا مرة. أعقد حسابيًا ونادرًا ما بيتستخدم عمليًا.

طرق الـ linkage

الـ agglomerative clustering محتاج قاعدة يقيس بيها المسافة بين مجموعتين مش بين نقطتين بس. واختيار معيار الـ linkage (الربط) بيأثّر جامد على الشجرة اللي بتطلع:

الـ single linkage (الربط الأدنى): المسافة بين المجموعتين هي أقل مسافة بين أي نقطتين من كل واحدة. بيطلّع مجموعات طويلة ممطوطة وحسّاس للـ noise.

الـ complete linkage (الربط الأقصى): المسافة هي أكبر مسافة بين أي نقطتين. بيطلّع مجموعات متكتّلة وكروية وأصمد قصاد الـ noise بس ممكن يفتّت المجموعات الكبيرة.

الـ average linkage (الربط المتوسط): المسافة هي متوسط المسافات بين كل أزواج النقط في المجموعتين. توازن معقول بين الـ single والـ complete.

الـ Ward's method (معيار وارد): بدل ما يقيس المسافة على طول، Ward بيدمج الجوز اللي بيقلّل الزيادة في الـ variance الكلي جوه المجموعات. بيطلّع مجموعات متكتّلة وأحجامها متوازنة وهو الاختيار الأشهر عمليًا.

تكلفة الدمج بتاعة Ward

\Delta(A,B) = \dfrac{n_A \, n_B}{n_A + n_B} \, d(\boldsymbol{\mu}_A,\, \boldsymbol{\mu}_B)^2

لما ندمج المجموعتين A وB، معيار Ward بيحسب الزيادة في المجموع الكلي لمربعات الانحرافات جوه المجموعات. n_A وn_B حجمين المجموعتين؛ وd(μ_A, μ_B) المسافة الإقليدية بين مراكزهم. وWard بيكبّر تماسك المجموعات في كل خطوة دمج.

قراية الـ dendrogram

الارتفاع اللي الدمج بيحصل عنده في الـ dendrogram بيعكس المجموعتين مختلفين قد إيه. والقفزة الكبيرة في الارتفاع بين دمجين ورا بعض بتشاور على حد طبيعي مناسب للقطع. وعدد الفروع عند نقطة القطع هو عدد المجموعات اللي بتختاره.

الـ DBSCAN: الـ clustering بالكثافة

الـ DBSCAN (Density-Based Spatial Clustering of Applications with Noise) بياخد نظرة مختلفة خالص: المجموعة هي منطقة كثيفة من النقط بتفصلها عن المناطق الكثيفة التانية مساحة كثافتها خفيفة. والنقط اللي في المناطق الخفيفة بتتصنّف noise (ضوضاء) (شذوذات) ومش تبع أي مجموعة. والـ DBSCAN مش محتاج K وبيكشف مجموعات بأي شكل.

الـ DBSCAN بيعتمد على parameterين:

ε (إبسيلون): نص قطر الجيرة. نقطتين جيران لو المسافة بينهم أقل من أو بتساوي ε.

MinPts: أقل عدد نقط لازم يقع جوه جيرة ε بتاعة النقطة عشان تتحسب core point.

والـ algorithm بيصنّف كل نقطة لنوع من تلاتة:

الـ core point (النقطة الجوهرية): عندها على الأقل MinPts جار جوه نص قطر ε. واقعة جوه منطقة كثيفة.

الـ border point (النقطة الحدودية): عندها أقل من MinPts جار بس واقعة جوه ε من core point. واقعة على طرف المجموعة.

الـ noise point (نقطة الضوضاء): مش core ومش قريبة من أي core point. مش تبع أي مجموعة وبتتعامل كشذوذ.

الجيرة في DBSCAN

N_{\varepsilon}(p) = \{\, q \in X \mid d(p,q) \leq \varepsilon \,\}

جيرة ε للنقطة p هي مجموعة كل النقط اللي بتبعد عنها مسافة أقل من أو بتساوي ε. والنقطة p تبقى core لو |N_ε(p)| ≥ MinPts. والـ DBSCAN بيبني المجموعات بإنه يدمج الـ core points اللي جيراتها متداخلة.

اختيار ε وMinPts

قاعدة عملية مفيدة: خلّي MinPts = 2 × عدد الأبعاد (وأقل حاجة 4). وبعدين ارسم مسافة الجار رقم k الأقرب لكل نقطة (k = MinPts − 1) مترتّبة تصاعدي. ودوّر على "الكوع"، يعني اللفّة الحادة في المنحنى، وده تقدير كويس لـ ε.

مزايا الـ DBSCAN

أي شكل: الـ DBSCAN بيمشي ورا كثافة البيانات مش المسافات من مراكز. الهلالين المتشابكين، والحلقة جوه القرص، والمجرّة الحلزونية — أشكال بتعجّز الـ K-Means — الـ DBSCAN بيفصلها بسهولة طالما كثافتها مختلفة عن كثافة الخلفية.

مش محتاج K: عدد المجموعات بيتحدّد من بنية البيانات. مش محتاج تحدّد K من الأول، وده مفيد خصوصًا في التحليل الاستكشافي لما ميبقاش عندك فكرة عن عدد المجموعات.

كشف الشذوذ جوه الـ algorithm: نقط الـ noise بتتحدّد أوتوماتيك كنتيجة جانبية، فالـ DBSCAN بيبقى algorithm للـ clustering ولكشف الشذوذ في نفس الوقت.

deterministic (حتمي): على عكس الـ K-Means، الـ DBSCAN حتمي — نفس الـ inputs دايمًا بتطلّع نفس النتايج (ممكن تبعية الـ border points تختلف، بس انتماء الـ core points وlabels الـ noise ثابتة).

الـ DBSCAN بيتكعبل لما كثافات المجموعات تختلف جامد، لأن جوز واحد (ε, MinPts) مبيقدرش يمسك في نفس الوقت مجموعة كثيفة ومتلزّقة ومجموعة تانية متفرّقة وكثافتها قليلة. والـ HDBSCAN (DBSCAN الهرمي) بيعالج ده بإنه يغيّر threshold الكثافة ويطلّع سلسلة هرمية من المجموعات، قصاد تعقيد أكبر.

مقارنة التلات طرق

الـ K-Means الأسرع والأكتر قابلية للتوسع. بيشتغل كويس لما المجموعات تبقى كروية وأحجامها قريبة وعددها معروف من الأول. ضعفه: مبيتعاملش مع الأشكال الحرة وحسّاس للـ initialization والشذوذات.

الـ hierarchical clustering بيطلّع شجرة كاملة من التجميعات ومش محتاج K من الأول — بتختار القطع بعد ما تشوف الـ dendrogram. ومعيار Ward غالبًا بيدّي أحسن نتايج. ضعفه: تعقيد O(n² log n) بيخلّيه مش عملي للبيانات الكبيرة.

الـ DBSCAN بيلاقي مجموعات بأي شكل وبيحدّد الشذوذات أوتوماتيك. مش محتاج K. بيشتغل كويس لما كثافات المجموعات تبقى قريبة. ضعفه: أداؤه ضعيف لما الكثافات تختلف جامد بين المجموعات.

في الدرس الجاي، هننتقل لـ الـ dimensionality reduction — PCA وt-SNE وUMAP — تقنيات بتضغط البيانات اللي أبعادها عالية لبُعدين أو تلاتة وهي محافظة على أكبر قدر ممكن من البنية.

أهم النقط

الـ hierarchical clustering بيبني dendrogram من التجميعات المتداخلة؛ اقطعه عند أي ارتفاع عشان تختار K بعد الحساب.
الـ agglomerative clustering (من تحت لفوق) هو الطريقة المعتادة؛ ومعيار Ward بيقلّل زيادة الـ variance وعادةً بيدّي أحسن نتايج.
اختيار طريقة الـ linkage مهم: الـ single بيمطّ المجموعات، والـ complete بيكتّلها، والـ average بيوازن، وWard بيقلّل الـ variance.
الـ DBSCAN بيعرّف المجموعات كمناطق كثيفة بتفصلها مسافات خفيفة؛ مش محتاج K وبيصنّف الشذوذات أوتوماتيك.
الـ DBSCAN بيصنّف النقط لـ: core (جوه الكثيف)، وborder (طرف المجموعة)، وnoise (شذوذ).
الـ DBSCAN بيتعامل مع الأشكال الحرة بس بيعاني لما كثافات المجموعات تختلف جامد.
اختار الـ K-Means للسرعة، والـ hierarchical للأشجار اللي سهل تفسّرها، والـ DBSCAN للأشكال الحرة وكشف الشذوذ.