ما وراء K-Means
K-Means سريع وبديهي، لكنه يُلزمك باختيار K قبل البدء ويفترض أن المجموعات كروية الشكل ومتقاربة الحجم. البيانات الحقيقية نادرًا ما تُحقق ذلك. المجرات تتشكل في خيوط، وسلوك العملاء يتجمع في أشكال غير منتظمة، والتصنيفات البيولوجية متداخلة ومتعشّشة. عائلتان من الخوارزميات تعالجان هذه القيود: التجميع الهرمي الذي يبني شجرة من المجموعات المتداخلة دون الحاجة إلى K مسبقًا، والتجميع الكثافي الذي يكشف مجموعات ذات أشكال اعتباطية عبر تتبع مناطق الكثافة العالية.
التجميع الهرمي
التجميع الهرمي ينتج تسلسلًا متداخلًا من التقسيمات، بدءًا من كل نقطة في مجموعتها المستقلة وصولًا إلى كل النقاط في مجموعة واحدة. الناتج هو بنية شجرية تُسمى المخطط الشجري (dendrogram) تُسجّل تاريخ الدمج كاملًا. يمكنك قطع المخطط عند أي ارتفاع للحصول على أي عدد من المجموعات دون إعادة تشغيل الخوارزمية.
هناك استراتيجيتان متكاملتان:
التجميع التراكمي (من الأسفل للأعلى): نبدأ بـ n مجموعة منفردة. في كل خطوة نضم أقرب مجموعتين. نكرر حتى تبقى مجموعة واحدة. هذا النهج الأكثر شيوعًا.
التجميع الانقسامي (من الأعلى للأسفل): نبدأ بكل النقاط في مجموعة واحدة ثم نقسّم الأكثر تباينًا بصفة متكررة. أكثر تعقيدًا حسابيًا ونادر الاستخدام عمليًا.
طرق الربط
يحتاج التجميع التراكمي إلى قاعدة لقياس المسافة بين مجموعتين لا بين نقطتين فقط. اختيار معيار الربط يؤثر تأثيرًا جوهريًا على الشجرة الناتجة:
الربط الأدنى (Single Linkage): المسافة بين المجموعتين هي الحد الأدنى للمسافات بين أي نقطتين من كل منهما. ينتج مجموعات طويلة ممتدة وحساس للضوضاء.
الربط الأقصى (Complete Linkage): المسافة هي الحد الأقصى بين أي نقطتين. ينتج مجموعات مُدمجة وكروية وأكثر صمدًا أمام الضوضاء لكنه قد يُفتّت المجموعات الكبيرة.
الربط المتوسط (Average Linkage): المسافة هي متوسط المسافات الزوجية بين جميع نقاط المجموعتين. توازن معقول بين الربط الأدنى والأقصى.
معيار وارد (Ward's Method): بدلًا من قياس المسافة مباشرة، يضم وارد الزوج الذي يُقلّل الزيادة في إجمالي التباين داخل المجموعات. يُنتج مجموعات مُدمجة ومتوازنة الحجم وهو الخيار الأكثر شيوعًا عمليًا.
الارتفاع الذي يحدث عنده الدمج في المخطط الشجري يعكس مدى الاختلاف بين المجموعتين. القفزة الكبيرة في الارتفاع بين دمجين متتاليين تُشير إلى حد طبيعي مناسب للقطع. عدد الفروع عند نقطة القطع هو عدد المجموعات الذي تختاره.
DBSCAN: التجميع الكثافي
DBSCAN (التجميع المكاني الكثافي مع التعامل مع الضوضاء) يتبنى منظورًا مختلفًا جذريًا: المجموعة هي منطقة كثيفة من النقاط تفصلها مساحة خفيفة الكثافة عن مناطق كثيفة أخرى. النقاط في المناطق الخفيفة تُصنَّف ضوضاء (شذوذات) ولا تنتمي لأي مجموعة. لا يحتاج DBSCAN إلى K ويكشف مجموعات ذات أشكال اعتباطية.
يعتمد DBSCAN على معاملين:
ε (إبسيلون): نصف قطر الحي. نقطتان جارتان إذا كانت المسافة بينهما أقل من أو تساوي ε.
MinPts: الحد الأدنى لعدد النقاط التي يجب أن تقع داخل حي ε للنقطة لكي تُعدّ نقطة جوهرية.
يُصنّف الخوارزم كل نقطة إلى أحد ثلاثة أنواع:
النقطة الجوهرية (Core Point): لها على الأقل MinPts جارة داخل نصف قطر ε. تقع في داخل منطقة كثيفة.
النقطة الحدودية (Border Point): لها أقل من MinPts جارة لكنها تقع داخل ε من نقطة جوهرية. تقع على هامش المجموعة.
نقطة الضوضاء (Noise Point): ليست جوهرية ولا تقع قرب أي نقطة جوهرية. لا تنتمي لأي مجموعة وهي بمثابة شذوذ.
قاعدة عملية مفيدة: اضبط MinPts = 2 × عدد الأبعاد (بحد أدنى 4). ثم ارسم مسافة الجار k الأقرب لكل نقطة (k = MinPts − 1) مرتبةً تصاعديًا. ابحث عن "الكوع" أي الانعطاف الحاد في المنحنى وهو تقدير جيد لـ ε.
مزايا DBSCAN
أشكال اعتباطية: يتتبع DBSCAN كثافة البيانات لا المسافات من المراكز. الهلالان المتشابكان، والحلقة داخل القرص، والمجرة الحلزونية — أشكال تُعجز K-Means — يُفصلها DBSCAN بسهولة.
لا حاجة إلى K: عدد المجموعات يتحدد من بنية البيانات. لا تحتاج إلى تحديده مسبقًا مما يجعله مثاليًا للتحليل الاستكشافي.
كشف الشذوذات مدمج: نقاط الضوضاء تُحدَّد تلقائيًا كنتيجة جانبية للخوارزمية مما يجعل DBSCAN خوارزمية تجميع وكشف شذوذات في آنٍ واحد.
حتمي: على عكس K-Means، نفس المدخلات تُنتج دائمًا نفس النتائج.
مقارنة المناهج الثلاثة
K-Means الأسرع والأكثر قابلية للتوسع. يعمل بشكل جيد عندما تكون المجموعات كروية الشكل ومتقاربة الحجم وعدد المجموعات معروف مسبقًا. ضعفه: لا يتعامل مع الأشكال الاعتباطية وحساس للتهيئة والشذوذات.
التجميع الهرمي يُنتج شجرة كاملة من التجميعات ولا يحتاج إلى K مسبقًا — تختار القطع بعد رؤية المخطط الشجري. معيار وارد يُعطي أفضل النتائج في الغالب. ضعفه: تعقيد O(n² log n) يجعله غير عملي للبيانات الكبيرة.
DBSCAN يجد مجموعات ذات أشكال اعتباطية ويُحدد الشذوذات تلقائيًا. لا يحتاج إلى K. يعمل جيدًا عندما تكون كثافات المجموعات متقاربة. ضعفه: أداء ضعيف عندما تختلف الكثافات اختلافًا كبيرًا بين المجموعات.
- التجميع الهرمي يبني مخططًا شجريًا من التجميعات المتداخلة؛ اقطعه عند أي ارتفاع لاختيار K بعد الحساب.
- التجميع التراكمي (من الأسفل للأعلى) هو النهج المعياري؛ معيار وارد يُقلل زيادة التباين ويُعطي أفضل النتائج عادةً.
- اختيار طريقة الربط مهم: الأدنى يُمدّد المجموعات، الأقصى يُكثّفها، المتوسط يوازن، وارد يُقلل التباين.
- DBSCAN يُعرّف المجموعات كمناطق كثيفة مفصولة بمسافات خفيفة؛ لا يحتاج إلى K ويُصنّف الشذوذات تلقائيًا.
- DBSCAN يُصنّف النقاط إلى: جوهرية (داخل كثيف)، حدودية (هامش المجموعة)، وضوضاء (شذوذ).
- DBSCAN يتعامل مع الأشكال الاعتباطية لكنه يُعاني عندما تختلف كثافات المجموعات اختلافًا كبيرًا.
- اختر K-Means للسرعة، الهرمي للأشجار القابلة للتفسير، DBSCAN للأشكال الاعتباطية وكشف الشذوذات.