DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN (التجميع المكاني للتطبيقات ذات الكثافة القائمة على الكثافة مع الضجيج) خوارزمية تعلّم غير خاضع للإشراف تجمع النقاط المتقاربة بكثافة في عناقيد، وتصنّف النقاط في المناطق المتناثرة على أنها ضجيج. وقد قدّمه مارتن إستر وهانس-بيتر كريغل ويورغ ساندر وشياووي شو في مؤتمر KDD عام 1996. لا يحتاج إلى تحديد عدد العناقيد مسبقًا، ويتعامل مع عناقيد بأشكال مختلفة، مثل الحلقات والأهلة والطرق المتعرجة، كما أن تصنيف الضجيج يؤدي وظيفة بسيطة في اكتشاف الحالات الشاذة. وتتحكم في الخوارزمية كلها معلمتان: نصف قطر الجوار وعدد النقاط اللازمة لاعتبار الجوار كثيفًا.

النقاط المحورية والنقاط الحدّية والضجيج#

يفحص DBSCAN جوار كل نقطة، أي مجموعة النقاط الواقعة ضمن مسافة eps، ويحصي عناصرها:

• نقطة محورية: لها min_samples نقاط على الأقل في جوارها، مع احتسابها هي نفسها في تطبيق scikit-learn. وتشكل النقاط المحورية الجزء الداخلي الكثيف من العنقود.
• نقطة حدّية: عدد جيرانها أقل مما يجعلها نقطة محورية، لكنها تقع على مسافة eps من نقطة محورية. وتشكل النقاط الحدّية أطراف العنقود.
• نقطة ضجيج: ليست نقطة محورية ولا حدّية، لذا لا تنتمي إلى أي عنقود وتحصل على التصنيف -1.

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

اختيار eps وmin_samples#

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

DBSCAN وK-Means وHDBSCAN#

يتطلب التجميع بطريقة K-means تحديد عدد العناقيد مسبقًا، ويُسند كل نقطة إلى أقرب مركز عنقود، لذا يفضّل العناقيد المستديرة والمتماسكة، ويضم القيم الشاذة إلى إحدى المجموعات. ويكتشف DBSCAN عدد العناقيد اعتمادًا على الكثافة ويستبعد القيم الشاذة. وتكمن نقطة ضعفه في استخدام eps عالمي واحد: فعندما تختلف كثافة العناقيد كثيرًا، لا يوجد نصف قطر واحد يفصل العناقيد المتناثرة عن الضجيج والعناقيد الكثيفة بعضها عن بعض. وتعالج HDBSCAN ذلك فعليًا بتشغيل DBSCAN على جميع قيم eps والاحتفاظ بالعناقيد الأكثر استقرارًا، وتتوفر الخوارزميتان في وحدة التجميع في scikit-learn إلى جانب خوارزمية OPTICS ذات الصلة.

يجمع هذا المثال هلالين متداخلين أُضيفت إليهما 20 قيمة شاذة عشوائية، ويقيّم كل نتيجة مقابل المجموعات الحقيقية باستخدام مؤشر راند المعدّل، حيث تمثل 1.0 تطابقًا تامًا:

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

يطبع البرنامج النصي وجود عنقودين و15 نقطة ضجيج في DBSCAN، ومؤشري راند معدّلين قدرهما 0.97 لـ DBSCAN و0.20 لـ k-means. ويرسم DBSCAN حدود الهلالين ويستبعد القيم الشاذة التي وقعت بعيدًا عنهما، بينما يقسم k-means الهلالين بحد مستقيم رغم تزويده بعدد العناقيد الصحيح.

تطبيقات عملية#

• استشعار LiDAR: تزيل مسارات المركبات ذاتية القيادة والروبوتات نقاط الأرض من مسح LiDAR، ثم تجمع النقاط ثلاثية الأبعاد المتبقية في عوائق منفصلة. ويشيع اختيار التجميع القائم على الكثافة لأن عدد الأجسام غير معروف.
• المعالجة اللاحقة للاكتشاف: يمكن تجميع مراكز صناديق اكتشافات YOLO26، المتاحة على هيئة result.boxes.xywh، باستخدام DBSCAN للعثور على مجموعات الأشخاص في الحشود أو مواقع العيوب المتكررة على خط الإنتاج، إذ تُستبعد الاكتشافات المنفردة بوصفها ضجيجًا.
• مراقبة الاحتيال وأجهزة الاستشعار: تقع المعاملات أو القراءات المصنفة بالقيمة -1 بعيدًا عن كل مجموعة كثيفة من السلوكيات الطبيعية، وتصبح مرشحة للمراجعة.
• التحليل الجغرافي المكاني: تجمع شركات التوصيل والنقل التشاركي نقاط GPS للعثور على مواقع التوقف المتكررة ونقاط الالتقاء الساخنة. تقبل DBSCAN في Scikit-learn القيمة metric="haversine" لخطوط العرض والطول بوحدة الراديان، وفي هذه الحالة تكون eps زاوية على الكرة الوحدة، لذا يصبح نصف قطر قدره 100 متر eps = 0.1 / 6371، باستخدام متوسط نصف قطر الأرض البالغ 6,371 كم.