DBSCAN (التجميع المكاني المستند إلى الكثافة للتطبيقات ذات الضوضاء)

كيف يعمل DBSCAN

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

1. إبسيلون (eps): تُحدّد هذه المعلمة المسافة القصوى بين نقطتي بيانات لاعتبار إحداهما في جوار الأخرى. ينشئ بشكل أساسي نصف قطر حول كل نقطة.
2. الحد الأدنى من النقاط (minPts): تحدد هذه البارامتر الحد الأدنى لعدد نقاط البيانات المطلوبة ضمن جوار نقطة ما (بما في ذلك النقطة نفسها) لتصنيف تلك النقطة على أنها "نقطة أساسية".

بناءً على هذه المعلمات، يتم تصنيف نقاط البيانات إلى ثلاثة أنواع:

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

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

المزايا والعيوب الرئيسية

تقدم DBSCAN العديد من المزايا:

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

ومع ذلك، فإن لها قيودًا أيضًا:

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

DBSCAN مقابل طرق التجميع الأخرى

وغالبًا ما تتم مقارنة DBSCAN بخوارزميات التجميع الأخرى، لا سيما خوارزمية التجميع K-means. تشمل الاختلافات الرئيسية ما يلي:

• شكل المجموعة: تفترض K-means أن العناقيد كروية ومتساوية الحجم، بينما يمكن ل DBSCAN العثور على عناقيد ذات شكل عشوائي.
• عدد المجموعات: يتطلب K-means من المستخدم تحديد عدد المجموعات (k) مسبقًا، بينما يحددها DBSCAN تلقائيًا.
• التعامل مع القيم المتطرفة: تقوم K-means بتعيين كل نقطة إلى مجموعة، مما يجعلها حساسة للقيم المتطرفة. أما DBSCAN فيقوم صراحةً بتحديد وعزل القيم المتطرفة كضوضاء.
• التعقيد الحسابي: يعد K-means أسرع بشكل عام من DBSCAN، خاصةً على مجموعات البيانات الكبيرة، على الرغم من أن تعقيد DBSCAN يمكن أن يختلف اعتمادًا على خيارات المعلمات وتحسينات بنية البيانات مثل KD-trees.

التطبيقات الواقعية

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

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

DBSCAN و Ultralytics

ال Ultralytics في المقام الأول على نماذج التعلم الخاضعة للإشراف، مثل Ultralytics YOLO لمهام تشمل اكتشاف الأجسام وتصنيف الصور وتجزئة الصور. بينما لا تُدمج DBSCAN، كونها طريقة غير خاضعة للإشراف، بشكل مباشر في حلقات التدريب الأساسية لنماذج مثل YOLOv8 أو YOLO11فإن مبادئها ذات صلة في السياق الأوسع للرؤية الحاسوبية وتحليل البيانات. ويُعد فهم كثافة البيانات وتوزيعها أمرًا بالغ الأهمية عند إعداد مجموعات البيانات وتحليلها للتدريب أو عند معالجة مخرجات النموذج بعد ذلك، على سبيل المثال، تجميع الأجسام المكتشفة بناءً على قربها المكاني بعد الاستدلال. توفر منصات مثل Ultralytics HUB أدوات لإدارة مجموعات البيانات وتصورها، والتي يمكن أن تكمل تقنيات تحليل البيانات الاستكشافية حيث يمكن تطبيق خوارزميات التجميع مثل DBSCAN.