المقدمة

خوارزمية DBSCAN (التجميع المكاني القائم على الكثافة مع الضوضاء - Density-Based Spatial Clustering of Applications with Noise) هي خوارزمية تجميع قائمة على الكثافة، تعمل على تجميع النقاط المتقاربة من بعضها البعض في مجموعة واحدة. وخلافًا لخوارزمية K-Means، لا تتطلب DBSCAN منك تحديد عدد المجموعات (clusters) مسبقًا، كما أنها قادرة على تمييز النقاط الشاذة (outliers) واعتبارها ضوضاء (noise).

المفاهيم الأساسية

1. النقاط الأساسية (Core Points)

تُصنَّف النقطة على أنها نقطة أساسية (Core Point) إذا كان يوجد على الأقل minPts من النقاط ضمن مسافة ε (إبسيلون) منها، بما في ذلك النقطة نفسها.

2. النقاط الحدودية (Border Points)

تُصنَّف النقطة على أنها نقطة حدودية (Border Point) إذا تحقق فيها ما يلي:

• ليست نقطة أساسية بحد ذاتها
• تقع ضمن الجوار (ε-neighborhood) لنقطة أساسية واحدة على الأقل

3. نقاط الضوضاء (Noise Points)

تُصنَّف النقطة على أنها نقطة ضوضاء (Noise Point) (نقطة شاذة) إذا لم تكن نقطة أساسية ولا نقطة حدودية.

معاملات الخوارزمية

تتطلب خوارزمية DBSCAN معاملين (parameters) يحددهما المستخدم:

1. ε (إبسيلون): نصف قطر الدائرة (الجوار) حول كل نقطة

   • تُعتبر النقاط الواقعة ضمن هذه المسافة نقاطًا مجاورة (neighbors)
   • يحتاج هذا المعامل إلى ضبط دقيق (tuning) بناءً على طبيعة البيانات

2. minPts: الحد الأدنى لعدد النقاط اللازمة لتشكيل منطقة كثيفة (مجموعة/cluster)

   • تكون النقطة نقطة أساسية إذا كان لديها minPts من النقاط المجاورة على الأقل ضمن مسافة ε
   • يحتاج هذا المعامل أيضًا إلى ضبط دقيق بناءً على طبيعة البيانات

سير عمل الخوارزمية

flowchart TD
    A[Start: Select a point] --> B{Is point already<br/>visited?}
    B -->|Yes| A
    B -->|No| C[Mark point as visited]
    C --> D[Count neighbors within ε radius]
    D --> E{Number of neighbors<br/>≥ minPts?}
    E -->|Yes| F[Mark as Core Point]
    E -->|No| G[Mark as Noise temporarily]
    F --> H[Create new cluster or<br/>extend existing cluster]
    H --> I[Add all neighbors to cluster]
    I --> J[Process each neighbor recursively]
    J --> K{All points<br/>processed?}
    G --> K
    K -->|No| A
    K -->|Yes| L[Classify remaining<br/>Non-Core Points]
    L --> M[End: Clusters formed]

خطوات عمل خوارزمية DBSCAN

الخطوة 1: حساب النقاط المجاورة

بالنسبة لكل نقطة في مجموعة البيانات، يتم حساب عدد النقاط التي تقع ضمن مسافة ε (نصف قطر الدائرة البرتقالية).

graph LR
    A[Point] -->|ε radius| B((Neighborhood))
    B --> C[Count neighbors]

الخطوة 2: تحديد النقاط الأساسية

تُصنَّف النقاط التي يوجد لديها minPts من النقاط المجاورة على الأقل (بما في ذلك النقطة نفسها) ضمن نصف قطر ε على أنها نقاط أساسية (Core Points).

الخطوة 3: تشكيل المجموعات

بدءًا من نقطة أساسية:

• يتم إنشاء مجموعة (cluster) جديدة
• تُضاف جميع النقاط المجاورة لها إلى المجموعة
• بالنسبة لكل نقطة مجاورة تكون هي الأخرى نقطة أساسية، تُضاف نقاطها المجاورة إلى المجموعة كذلك
• تستمر العملية حتى لا يعد بالإمكان إضافة أي نقاط أساسية جديدة إلى المجموعة

الخطوة 4: تصنيف النقاط غير الأساسية

بعد إسناد جميع النقاط الأساسية إلى مجموعاتها:

• تصبح النقاط الواقعة ضمن مسافة ε من أي نقطة أساسية نقاطًا حدودية (Border Points) تابعة لتلك المجموعة
• تُصنَّف النقاط غير القريبة من أي نقطة أساسية على أنها ضوضاء (Noise)

graph TD
    A[All Data Points] --> B{Is Core Point?}
    B -->|Yes| C[Assign to Cluster]
    B -->|No| D{Within ε of<br/>Core Point?}
    D -->|Yes| E[Mark as Border Point]
    D -->|No| F[Mark as Noise]

ملاحظات مهمة

• نصف القطر ε يحدده المستخدم. عند استخدام DBSCAN، قد تحتاج إلى تجربة قيم مختلفة لهذا المعامل للوصول إلى القيمة المثلى المناسبة لمجموعة بياناتك.

• الحد الأدنى لعدد النقاط اللازم لاعتبار نقطة ما نقطة أساسية (minPts) يحدده المستخدم أيضًا. قد تحتاج إلى ضبط هذا المعامل بدوره.

• النقاط غير الأساسية الواقعة ضمن مسافة ε من نقطة أساسية لا تعمل على توسيع المجموعة أكثر. فتوسيع المجموعات يقتصر فقط على النقاط الأساسية.

حساب المسافة

تستخدم خوارزمية DBSCAN المسافة الإقليدية (Euclidean distance) لقياس المسافة بين النقاط:

بالنسبة لنقطتين A(x₁, y₁) وB(x₂, y₂)، تُحسب المسافة بينهما كالتالي:

Distance(A, B) = √[(x₂ - x₁)² + (y₂ - y₁)²]

مثال محلول

نص المسألة

طبّق خوارزمية DBSCAN على نقاط البيانات المعطاة، وأنشئ المجموعات باستخدام القيم التالية:

• minPts = 4
• ε (إبسيلون) = 1.9

مجموعة البيانات

الخطوة 1: حساب مصفوفة المسافات

باستخدام معادلة المسافة الإقليدية، احسب المسافة بين كل زوج من النقاط:

الخطوة 2: تحديد النقاط المجاورة (ε = 1.9)

لكل نقطة، حدد النقاط المجاورة لها ضمن مسافة ε = 1.9:

الخطوة 3: تصنيف النقاط

باستخدام minPts = 4، تكون النقطة نقطة أساسية إذا كان لديها 4 نقاط مجاورة على الأقل (بما في ذلك النقطة نفسها) ضمن مسافة ε.

تحديد النقاط الأساسية:

• P1: نقطتان مجاورتان (2) → ليست نقطة أساسية (ضوضاء/حدودية)
• P2: 3 نقاط مجاورة → ليست نقطة أساسية (ضوضاء/حدودية)
• P3: نقطتان مجاورتان (2) → ليست نقطة أساسية (ضوضاء/حدودية)
• P4: نقطتان مجاورتان (2) → ليست نقطة أساسية (ضوضاء/حدودية)
• P5: 4 نقاط مجاورة → نقطة أساسية ✓
• P6: نقطتان مجاورتان (2) → ليست نقطة أساسية (ضوضاء/حدودية)
• P7: نقطتان مجاورتان (2) → ليست نقطة أساسية (ضوضاء/حدودية)
• P8: نقطة مجاورة واحدة (1) → ليست نقطة أساسية (ضوضاء/حدودية)
• P9: نقطة مجاورة واحدة (1) → ليست نقطة أساسية (ضوضاء/حدودية)
• P10: نقطتان مجاورتان (2) → ليست نقطة أساسية (ضوضاء/حدودية)
• P11: 3 نقاط مجاورة → ليست نقطة أساسية (ضوضاء/حدودية)
• P12: نقطتان مجاورتان (2) → ليست نقطة أساسية (ضوضاء/حدودية)

ملاحظة: فقط P2 وP5 وP11 لديها بالضبط 3 أو 4 نقاط مجاورة. وباستخدام minPts=4، فإن P5 فقط هي النقطة الأساسية (حيث لديها 4 نقاط مجاورة: P4، P6، P7، P8).

الخطوة 4: التصنيف النهائي

النتيجة:

• النقاط الأساسية: P2، P5، P11
• النقاط الحدودية: النقاط الواقعة ضمن مسافة ε من نقاط أساسية لكنها ليست أساسية بحد ذاتها
• نقاط الضوضاء: P9 (غير واقعة ضمن مسافة ε من أي نقطة أساسية)

تصور عملية تشكيل المجموعات

graph TB
    subgraph Cluster_Formation["Cluster Formation Process"]
        A[Start with Core Point P5] --> B[Add P5 to Cluster 1]
        B --> C[Add P5's neighbors: P4, P6, P7, P8]
        C --> D[Check if neighbors are Core Points]
        D --> E[None are Core Points]
        E --> F[Cluster 1 complete]
    end
    
    subgraph Final_Assignment["Final Point Assignment"]
        G[P5: Core - Cluster 1]
        H[P4, P6, P7, P8: Border - Cluster 1]
        I[P2, P11: Core - Form Cluster 2]
        J[P1, P3, P10, P12: Border Points]
        K[P9: Noise]
    end

أهم النقاط المستفادة

1. تكتشف DBSCAN عدد المجموعات تلقائيًا استنادًا إلى كثافة البيانات
2. بإمكانها تمييز النقاط الشاذة واعتبارها نقاط ضوضاء
3. تتطلب الخوارزمية ضبطًا دقيقًا لمعاملي ε وminPts
4. النقاط الأساسية هي التي تقود عملية تشكيل المجموعات؛ أما النقاط غير الأساسية فتنضم فقط إلى مجموعات موجودة مسبقًا
5. تعمل DBSCAN بشكل جيد مع المجموعات ذات الأشكال العشوائية (arbitrary shapes)، على عكس خوارزمية K-Means

مزايا خوارزمية DBSCAN

• لا تتطلب تحديد عدد المجموعات مسبقًا
• قادرة على اكتشاف مجموعات ذات أشكال عشوائية
• قوية وموثوقة في التعامل مع النقاط الشاذة (تصنّفها كضوضاء)
• تحتاج فقط إلى معاملين اثنين (ε وminPts)

عيوب خوارزمية DBSCAN

• حساسة لاختيار قيم المعاملات (ε وminPts)
• تواجه صعوبة مع المجموعات ذات الكثافات المتفاوتة
• ينخفض أداؤها مع البيانات عالية الأبعاد (high-dimensional data)
• لا يمكنها تجميع مجموعات البيانات جيدًا عند وجود فروقات كبيرة في الكثافة

تمرين تطبيقي

جرّب تطبيق خوارزمية DBSCAN باستخدام قيم مختلفة للمعاملات:

1. جرّب القيم ε = 2.5 وminPts = 3
2. قارن المجموعات الناتجة مع المثال المحلول أعلاه
3. لاحظ كيف يؤثر تغيير المعاملات على عملية تشكيل المجموعات