خوارزمية التجميع المكاني القائم على الكثافة للتطبيقات المزودة بالضوضاء (DBSCAN) (DBSCAN: Density-based spatial clustering of applications with noise)

مبادئ العمل الأساسية لـ DBSCAN

تعتمد DBSCAN على مفهوم الكثافة لتحديد المجموعات. يتم تعريف الكثافة من خلال المعلمات التالية:

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

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

• نقاط أساسية (Core points): نقطة بيانات لديها minPts نقاط أخرى داخل دائرة نصف قطرها ε.
• نقاط حدودية (Border points): نقطة بيانات تقع داخل دائرة نصف قطرها ε لنقطة أساسية، ولكنها ليست نقطة أساسية بحد ذاتها (أي أن لديها أقل من minPts نقاط داخل دائرة نصف قطرها ε).
• نقاط ضوضاء (Noise points): نقطة بيانات ليست نقطة أساسية ولا نقطة حدودية. هذه النقاط تعتبر نقاطًا شاذة أو قيمًا متطرفة.

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

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

يمكن تلخيص خطوات عمل خوارزمية DBSCAN على النحو التالي:

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

مزايا DBSCAN

تمتلك DBSCAN العديد من المزايا التي تجعلها أداة قوية في تحليل البيانات:

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

عيوب DBSCAN

على الرغم من مزاياها، فإن DBSCAN لديها بعض العيوب التي يجب مراعاتها:

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

تطبيقات DBSCAN

تستخدم DBSCAN على نطاق واسع في العديد من المجالات، بما في ذلك:

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

العلاقة بـ K-means

تعتبر خوارزميتا DBSCAN و K-means من أشهر خوارزميات التجميع، ولكنها تختلفان في عدة جوانب:

• متطلبات المدخلات: تتطلب K-means تحديد عدد المجموعات مسبقًا، بينما لا تفعل DBSCAN.
• هيكل المجموعات: تفترض K-means أن المجموعات كروية الشكل، بينما يمكن لـ DBSCAN التعامل مع المجموعات ذات الأشكال التعسفية.
• التعامل مع الضوضاء: لا تتعامل K-means بشكل جيد مع الضوضاء، بينما تم تصميم DBSCAN للتعامل معها.

بشكل عام، تعتبر DBSCAN خيارًا أفضل عندما يكون شكل المجموعات غير معروف، أو عندما تكون هناك ضوضاء في البيانات. K-means قد تكون أكثر كفاءة في الحالات التي تكون فيها المجموعات كروية الشكل ومعروف عددها.

تحسينات على DBSCAN

هناك العديد من التحسينات والاقتراحات لتوسيع قدرات DBSCAN، مثل:

• HDBSCAN: نسخة محسنة من DBSCAN قادرة على التعامل مع المجموعات ذات الكثافات المختلفة.
• OPTICS: خوارزمية أخرى تعتمد على الكثافة، والتي تقوم بإنشاء تسلسل هرمي للمجموعات.
• DBSCAN مع مؤشرات المسافة المختلفة: يمكن استخدام مؤشرات مسافة مختلفة (مثل مسافة مانهاتن) لتحسين أداء الخوارزمية في مجموعات بيانات معينة.

خاتمة

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

المراجع

• Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, August). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd international conference on knowledge discovery and data mining (pp. 226-231).
• Scikit-learn DBSCAN Documentation
• DBSCAN clustering in Machine Learning – GeeksForGeeks