أساسيات تعلم الآلة1996تأسيسي12 دقيقة قراءة

خوارزمية قائمة على الكثافة لاكتشاف العناقيد في قواعد البيانات المكانية الكبيرة مع وجود ضوضاء

A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise

Ester, M. · Kriegel, H.-P. · Sander, J. · Xu, X. — KDD

المشكلة

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

الإسهام

تطرح DBSCAN تعريفاً للعنقود مبنياً على الكثافة: العنقود هو أكبر مجموعة من النقاط المترابطة كثافياً. الخوارزمية تحتاج مُعاملَين فقط — ε (نصف قطر الجوار) وMinPts (أقل عدد مطلوب من الجيران) — وهذان المعاملان يحدّدان ما معنى «كثيف بما يكفي». أي نقطة حولها MinPts جيران على الأقل ضمن مسافة ε تُعتبر نقطة نواتية وتشكّل ركيزة للعنقود. النقاط التي يمكن بلوغها عبر سلاسل من النقاط النواتية تنضمّ للعنقود نفسه، أما ما لا يمكن الوصول إليه من أي نقطة نواتية فيُصنَّف ضوضاءً. لا تحتاج الخوارزمية لمعرفة عدد العناقيد مسبقاً، وتكتشف عناقيد بأشكال حرة تماماً.

الأثر

أصبحت DBSCAN واحدة من أكثر الخوارزميات اقتباساً في تاريخ تنقيب البيانات، وحصلت على جائزة KDD لاختبار الزمن عام 2014. وهي الخوارزمية المعتمدة للعنقدة الكثافية في scikit-learn وPostGIS وعدد كبير من خطوط التحليل المكاني. قدرتها على تمييز الضوضاء جعلتها أساساً في مجال كشف الشذوذ، وأفكارها ألهمت خوارزميات لاحقة مثل OPTICS وHDBSCAN وغابات العزل. في أي مجال تظهر فيه عناقيد بأشكال غير منتظمة مع نقاط شاذة — من تحليل مسارات GPS إلى المسوحات الفلكية — غالباً تكون DBSCAN أول ما يلجأ إليه الممارسون.

تخيّل أنك تحلّق فوق قارة مظلمة ليلاً وتنظر إلى الأسفل. ترى أضواءً متناثرة: بعضها متكتّل في مدن ساطعة، وبعضها يرسم خطوطاً رفيعة على طول الأنهار، وبعضها مجرد نيران معسكرات وحيدة في العراء.

k-means تتعامل مع المشهد برسم k دوائر بالضبط على الخريطة، مركز كل دائرة هو متوسط مواقع الأضواء داخلها. المشكلة أن المدن ليست دوائر: واحدة ممتدة على الساحل، وأخرى ملتفّة حول جبل. والأسوأ أن نيران المعسكرات المنعزلة تُجبَر على الانضمام لأقرب مدينة، فتتشوّه الصورة كلها.

DBSCAN تعمل بمنطق مختلف تماماً، أشبه بحريق بري: أسقط شرارة على أي ضوء حوله جيران كافون. تنتشر النار منه إلى كل ضوء قريب، ومن كل ضوء إلى جيرانه هو، فترسم تلقائياً حدود مدينة الساحل وسلسلة النهر دون أن يحدّد أحد شكلاً مسبقاً. أما نيران المعسكرات المنعزلة فلا تشتعل — تبقى ببساطة.

القيد: k-means تفترض أن العناقيد كُروية

k-means هي أشهر خوارزميات وأكثرها تدريساً، ولسبب وجيه: سريعة وبسيطة وتؤدي جيداً حين تكون العناقيد كروية تقريباً ومتقاربة الحجم. لكن فيها ثلاثة قيود جوهرية تجعلها غير مناسبة لكثير من البيانات المكانية الواقعية.

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

افتح في المختبر

يساراً: k-means تُجبر بيانات هلالية الشكل على عناقيد دائرية. يميناً: DBSCAN تتتبع الشكل الحقيقي وتعزل الضوضاء.

تستيقظ التجربة عند وصولك…

الفكرة الجوهرية: العناقيد مناطق كثيفة تفصل بينها مناطق متناثرة

الفكرة الأساسية في DBSCAN بسيطة جداً: العنقود هو منطقة تتراصّ فيها النقاط بكثافة عالية، والعناقيد المختلفة يفصل بينها مناطق خفيفة الكثافة. وهذا بالضبط ما يفعله الإنسان تلقائياً حين ينظر إلى نقاط مبعثرة على ورقة — لا يرسم دوائر، بل يبحث عن «تجمّعات» بينها «فراغات».

لتحويل هذا الحدس إلى خوارزمية محدّدة، تحتاج DBSCAN مُعاملَين فقط: ε (إبسيلون) — نصف قطر الجوار — وMinPts — أقل عدد مطلوب من الجيران. هذان الرقمان يجيبان عن سؤال واحد بسيط: «هل هذا الجوار كثيف بما يكفي ليُعدّ جزءاً من عنقود؟»

ثلاثة أنواع من النقاط: نواتية وحدودية وضوضاء

تقسم DBSCAN كل نقطة في مجموعة البيانات إلى واحد من ثلاثة أنواع. لو فهمت هذه الأنواع الثلاثة فهمتَ الخوارزمية كلها.

النقطة النواتية هي نقطة حولها على الأقل MinPts من الجيران ضمن مسافة ε (بما فيها هي نفسها). فكّر فيها كشخص في حفلة مزدحمة حوله أصدقاء كثيرون — هو مَن يُثبّت التجمّع ويجذب الناس حوله.

النقطة الحدودية تقع داخل جوار ε لنقطة نواتية، لكنها هي نفسها ليس حولها جيران يكفون لتكون نواتية. أشبه بشخص يقف على طرف الحشد — قريب بما يكفي لينتمي للمجموعة، لكنه ليس في قلبها.

نقطة الضوضاء (النقطة الشاذة) لا هي نواتية ولا تقع في مدى أي نقطة نواتية. تقف وحيدة بعيداً عن كل تجمّع — كنار معسكر معزولة في البراري.

افتح في المختبر

اضبط ε وMinPts لتشاهد كيف تُصنَّف النقاط إلى نواتية (مملوءة) وحدودية (مفرّغة) وضوضاء (×). جرّب إعدادات مختلفة لتبني حدسك.

تستيقظ التجربة عند وصولك…

التعريفات الرسمية: جوار ε، والوصول الكثافي، والترابط الكثافي

قبل الدخول في التعريفات الرسمية، استحضر تشبيه الحريق: النقطة النواتية هي مصدر الاشتعال، والوصول الكثافي هو انتشار النار عبر سلسلة مصادر، والعنقود هو كل ما احترق انطلاقاً من السلسلة المتصلة ذاتها.

جوار ε للنقطة p هو ببساطة كل النقاط التي تبعد عنها مسافة لا تتجاوز ε. إذا كان في هذا الجوار MinPts نقاط على الأقل، تكون p نقطة نواتية.

N_\varepsilon(p) = \{ q \in D \mid \text{dist}(p, q) \le \varepsilon \}

جوار إبسيلون — كل النقاط الواقعة ضمن نصف القطر ε حول النقطة p. إذا كان |N_ε(p)| ≥ MinPts فإنّ p نقطة نواتية — أي أن «دائرة جيرانها» مزدحمة بما يكفي.

نقول إن النقطة q قابلة للوصول الكثافي المباشر من p إذا كانت p نواتية وكانت q داخل جوارها ε. بتشبيه الحريق: النار عند p تصل إلى q مباشرة في خطوة واحدة.

نقول إن q قابلة للوصول الكثافي من p إذا وُجدت سلسلة نقاط p = p₁, p₂, …, pₙ = q كل حلقة فيها قابلة للوصول المباشر من سابقتها. بتشبيه الحريق: النار تنتقل من p إلى q عبر سلسلة نقاط نواتية متتالية، كفتيل يصل بين ألعاب نارية.

أما الترابط الكثافي فيعني أن هناك نقطة o يمكن الوصول الكثافي منها إلى كلٍّ من p وq. هذا المفهوم المتناظر هو ما يلصق العنقود ببعضه: حتى لو لم تستطع النار الانتقال مباشرة من p إلى q، يظلّان في العنقود نفسه ما دام كلاهما يُبلَغ من أصل مشترك.

افتح في المختبر

انقر على أي نقطة نواتية لتشاهد مجموعة الوصول الكثافي تتوسع خطوة بخطوة — هذا هو بالضبط كيف تبني DBSCAN العنقود.

تستيقظ التجربة عند وصولك…

عنقود DBSCAN: التعريف الرسمي

الآن وقد بنينا هذه المفاهيم، يصبح تعريف العنقود مباشراً:

العنقود C مجموعة جزئية غير فارغة من مجموعة البيانات D تستوفي شرطين: (1) الشمولية — إذا كانت p في C وكانت q قابلة للوصول الكثافي من p، فإن q في C أيضاً. (2) الترابط — أي نقطتين في C مترابطتان كثافياً.

ببساطة: العنقود أكبر مجموعة نقاط يمكن الوصول المتبادل بينها. يضمّ كل نقطة تبلغها النار ولا شيء زيادة.

أما الضوضاء فهي كل ما تبقّى — النقاط التي لا تنتمي لأي عنقود.

الخوارزمية: خطوة بخطوة

خوارزمية DBSCAN بسيطة بشكل مدهش. تمرّ على مجموعة البيانات مرة واحدة وتزور كل نقطة مرة واحدة فقط:

اختر نقطة p لم تُزَر بعد.
احسب جوار ε حولها. إذا كان عدد الجيران أقل من MinPts، اعتبرها ضوضاء مبدئياً — قد تتحوّل لاحقاً إلى نقطة حدودية إذا ضمّها عنقود.
إذا كان عدد الجيران ≥ MinPts، فإن p نواتية. أنشئ عنقوداً جديداً C وأضف p إليه.
لكل نقطة q في جوار p: إذا لم تُزَر بعد، زُرها واحسب جوارها. إذا كانت هي أيضاً نواتية، أضف جيرانها إلى قائمة الانتظار. إذا لم تنتمِ q لأي عنقود بعد، ألحقها بـ C.
كرّر حتى تُزار كل النقاط.

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

افتح في المختبر

شاهد DBSCAN تكتشف العناقيد نقطة بنقطة. الأخضر: توسّع العنقود. × الأحمر: ضوضاء. اضغط «خطوة» للتقدم أو «تشغيل» للتحريك.

تستيقظ التجربة عند وصولك…

الفكرة ذاتها في شيفرة برمجية

DBSCAN كاملةًpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import numpy as np
from collections import deque

def dbscan(X, eps, min_pts):
    """
    X:        مصفوفة (n, d) من النقاط
    eps:      نصف قطر الجوار
    min_pts:  الحد الأدنى لعدد الجيران لتكون نقطة نواتية
    يُعيد:    مصفوفة تصنيفات (-1 = ضوضاء)
    """
    n = len(X)
    labels = np.full(n, -1)      # -1 تعني غير مُصنَّفة
    cluster_id = 0

    for i in range(n):
        if labels[i] != -1:       # صُنِّفت بالفعل
            continue

        # ابحث عن الجيران ضمن eps
        neighbors = region_query(X, i, eps)

        if len(neighbors) < min_pts:
            labels[i] = -2        # علّمها ضوضاء (مؤقتاً)
            continue

        # i نقطة نواتية — ابدأ عنقوداً جديداً
        labels[i] = cluster_id
        seed_set = deque(neighbors - {i})

        while seed_set:
            q = seed_set.popleft()
            if labels[q] == -2:   # كانت ضوضاء → أصبحت حدودية
                labels[q] = cluster_id
            if labels[q] != -1:   # تنتمي بالفعل لعنقود
                continue
            labels[q] = cluster_id
            q_neighbors = region_query(X, q, eps)
            if len(q_neighbors) >= min_pts:
                seed_set.extend(q_neighbors)

        cluster_id += 1

    labels[labels == -2] = -1     # ثبّت تصنيف الضوضاء
    return labels

def region_query(X, idx, eps):
    """أعد فهارس كل النقاط ضمن eps من X[idx]."""
    dists = np.linalg.norm(X - X[idx], axis=1)
    return set(np.where(dists <= eps)[0])

اختيار ε وMinPts: منحنى المسافة k

DBSCAN تحتاج مُعاملَين فقط، لكن اختيارهما الجيد يحدث فرقاً كبيراً. الورقة الأصلية تقترح طريقة عملية هي منحنى المسافة k.

الفكرة: اجعل k = MinPts، ثم لكل نقطة احسب إلى جارها رقم k (أبعد جار من بين أقرب k جيران). رتّب هذه المسافات تنازلياً وارسمها. المنحنى الناتج عادةً يُظهر انعطافاً حاداً يشبه «المِرفَق»: النقاط قبله في مناطق كثيفة (مسافة k صغيرة)، والنقاط بعده في مناطق متناثرة أو ضوضاء (مسافة k كبيرة). القيمة المثلى لـ ε تقع عند هذا المرفق تحديداً — هي الحد الفاصل بين نظام العناقيد ونظام الضوضاء.

بالنسبة لـ MinPts، القاعدة العملية الشائعة هي MinPts ≥ عدد الأبعاد + 1، وعادةً MinPts = 4 أو 5 يكفي للبيانات ثنائية . كلما رفعت MinPts أصبحت العناقيد أكثر تحفظاً واحتاجت جواراً أكثف لتتشكّل.

افتح في المختبر

منحنى المسافة k لبيانات نموذجية. اسحب علامة المرفق لتحديد ε وشاهد نتيجة العنقدة تتحدّث لحظياً.

تستيقظ التجربة عند وصولك…

التعقيد الحسابي: ما سرعة DBSCAN؟

العملية الأساسية في DBSCAN هي حساب جوار ε لكل نقطة. بدون بنية بيانات مساعدة، كل استعلام جوار يتطلب مسحاً كاملاً بتكلفة O(n)، فتصبح التكلفة الكلية O(n²). لكن إذا استخدمنا فهرساً مكانياً كشجرة R* أو شجرة k-d، ينخفض كل استعلام إلى O(log n) في المتوسط، ويصبح الإجمالي O(n log n). هذه نقطة قوة عملية مهمة: DBSCAN تتدرّج جيداً مع الفهرسة المكانية وتتعامل مع ملايين النقاط بكفاءة.

T(n) = \begin{cases} O(n^2) & \text{without spatial index} \\ O(n \log n) & \text{with R*-tree / k-d tree} \end{cases}

التعقيد الزمني — عنق الزجاجة هو استعلامات الجوار. الفهرس المكاني يختصر كل مسح من O(n) إلى O(log n)، فتصبح DBSCAN عملية على ملايين النقاط.

نقاط القوة والقيود

نقاط قوة DBSCAN:

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

قيود DBSCAN:

تتعثّر مع الكثافات المتفاوتة. إذا كان هناك عنقود كثيف جداً وآخر متناثر، لا توجد قيمة ε واحدة تناسب كليهما: صغّرها فيتشظّى المتناثر، كبّرها فتندمج الكثيفة. OPTICS وHDBSCAN صُمّمتا لمعالجة هذا القيد.
حسّاسة لـ ε في الأبعاد العالية. مع ازدياد عدد الأبعاد تتشابه المسافات بين النقاط (ظاهرة «لعنة الأبعاد»)، فيصعب إيجاد ε يميّز الكثيف من المتناثر.
غموض النقاط الحدودية. نقطة حدودية في مدى عنقودين تُلحَق بأيهما يصلها أولاً — والنتيجة تعتمد على ترتيب المعالجة.

DBSCAN مقابل k-means والعنقدة الطيفية

كل أسلوب عنقدة يقوم على افتراضات مختلفة ويقدّم مقايضات مختلفة:

k-means — سريعة وبسيطة، لكنها تتطلب k مسبقاً ولا تكتشف إلا العناقيد المحدّبة ولا تتعامل مع الضوضاء. تناسب العناقيد شبه الكروية المتقاربة الحجم.
DBSCAN — لا تحتاج k، تكتشف أشكالاً حرة، وتعزل الضوضاء تلقائياً. تناسب البيانات المكانية ذات العناقيد غير المنتظمة والنقاط الشاذة. تتعثّر مع الكثافات المتفاوتة.
العنقدة الطيفية — تبني بيان وتقطعه، فتجد أشكالاً حرة كـ DBSCAN. لكنها تحتاج k، ومكلّفة حسابياً (تفكيك طيفي لمصفوفات كبيرة)، ولا تعزل الضوضاء تلقائياً.

DBSCAN هي الخيار الأول حين لا تعرف عدد العناقيد وتتوقع أشكالاً حرة وتحتاج — وهذا حال معظم البيانات المكانية الواقعية.

الأثر: من مؤتمر KDD 1996 إلى كل مكان

1996
نشر DBSCAN
قدّم إستر وكريغل وساندر وشو DBSCAN في مؤتمر KDD — أول خوارزمية تجمع العنقدة الكثافية مع كشف الضوضاء بشكل منهجي، وتكتشف عناقيد بأشكال حرة بدون تحديد k.
1999
OPTICS — هرمية الكثافة
قدّم أنكرست وبروينيغ وكريغل وساندر OPTICS التي تُنتج ترتيباً للنقاط يعكس بنية العنقدة عند كل مستويات الكثافة، فتعالج مشكلة الكثافات المتفاوتة التي تعاني منها DBSCAN.
2008
غابة العزل
قدّم ليو وتينغ وزو غابة العزل — كاشف شذوذ مبني على الأشجار، فكرته أن النقاط الشاذة يسهل عزلها. تشترك مع DBSCAN في حدس أن الشذوذ يقع في المناطق المتناثرة، لكنها تقترب من المشكلة من الاتجاه المعاكس.
2013
HDBSCAN
قدّم كامبيلو ومولافي وساندر HDBSCAN — امتداد هرمي لا يحتاج تحديد ε، بل يبني هرمية كثافية ويستخلص العناقيد الأكثر استقراراً تلقائياً.
2014
جائزة KDD لاختبار الزمن
حصلت DBSCAN على جائزة KDD لاختبار الزمن تقديراً لأثرها المستمر في تنقيب البيانات بعد نحو عقدين من نشرها.

أثر DBSCAN يتجاوز العنقدة بكثير. فكرتها أن النقاط في المناطق المتناثرة مشبوهة أصبحت ركيزة في مجال كشف الشذوذ. غابة العزل مثلاً، وهي من أشهر أدوات كشف الشذوذ اليوم، تنطلق من نفس الحدس الكثافي. وفلسفة DBSCAN الأعمق — أن تدع البيانات تحدّد بنية العناقيد بدل أن تفرض عليها افتراضات — أثّرت في جيل كامل من الخوارزميات الواعية بالكثافة.

المرجعEster, Kriegel, Sander, Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD, 1996.

مصطلحات هذه الورقة

العنقَدةClustering
الضجيج الحسابيNoise
القيمة الشاذةOutlier
رصد القيم الشاذةOutlier Detection
المسافة الإقليديةEuclidean Distance
خوارزمية الجيران الأقرب (KNN)k-Nearest Neighbors
العنقَدة بـ k-متوسطاتk-means Clustering
التعلّم غير الخاضع للإشرافUnsupervised Learning