DBSCAN

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 9 صور
الموسوعة الحرة

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

في عام 2014، حازت الخوارزمية على جائزة "اختبار الزمن" (وهي جائزة تُمنح للخوارزميات التي حظيت باهتمام كبير نظريًا وعمليًا) في مؤتمر ACM SIGKDD الرائد في مجال استخراج البيانات . [ 3 ] اعتبارًا من يوليو 2020 [ 4 ] ، تظهر الورقة البحثية اللاحقة بعنوان "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN" ضمن قائمة أكثر 8 مقالات تحميلاً من مجلة ACM Transactions on Database Systems (TODS) المرموقة . [ 5 ]

تم نشر متابعة أخرى، HDBSCAN* ، في البداية بواسطة ريكاردو جي جي كامبيلو، وديفيد مولافي، ويورغ ساندر في عام 2013، [ 6 ] ثم تم توسيعها مع آرثر زيمك في عام 2015. [ 7 ] وهي تنقح بعض القرارات الأصلية مثل نقاط الحدود، وتنتج نتيجة هرمية بدلاً من نتيجة مسطحة.

تاريخ

في عام 1972، نشر روبرت ف. لينغ خوارزمية وثيقة الصلة في "نظرية وبناء مجموعات k" [ 8 ] في مجلة الكمبيوتر ، مع تقدير تعقيد وقت التشغيل بـ O(n³). [ 8 ]

تتميز خوارزمية DBSCAN بتعقيد زمني في أسوأ الحالات يبلغ O(n²). وتتيح صياغة استعلام النطاق الموجهة لقاعدة البيانات في DBSCAN تسريع عملية الفهرسة. وتختلف الخوارزميات اختلافًا طفيفًا في طريقة تعاملها مع نقاط الحدود.

تمهيدي

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

  • تعتبر النقطة p نقطة أساسية إذا كانت هناك على الأقل minPts نقطة على مسافة ε منها (بما في ذلك p ).
  • يمكن الوصول إلى النقطة q مباشرةً من النقطة p إذا كانت النقطة q تقع ضمن مسافة ε من النقطة الأساسية p . ويُقال إن النقاط يمكن الوصول إليها مباشرةً من النقاط الأساسية فقط.
  • يمكن الوصول إلى النقطة q من النقطة p إذا كان هناك مسار p₁ , ..., pₙ بحيث يكون p₁ = pₙ و pₙ = qₙ ، حيث يمكن الوصول مباشرةً إلى كل نقطة pᵢ₊₁ من pᵢ . لاحظ أن هذا يعني أن النقطة الابتدائية وجميع النقاط على المسار يجب أن تكون نقاطًا أساسية، باستثناء النقطة q .
  • جميع النقاط التي لا يمكن الوصول إليها من أي نقطة أخرى تعتبر نقاطاً شاذة أو نقاطاً ضوضائية .

إذا كانت النقطة p نقطة مركزية، فإنها تُشكّل مجموعة مع جميع النقاط (المركزية وغير المركزية) التي يمكن الوصول إليها منها. تحتوي كل مجموعة على نقطة مركزية واحدة على الأقل؛ يمكن أن تكون النقاط غير المركزية جزءًا من مجموعة، لكنها تُشكّل "حافتها"، لأنها لا تُستخدم للوصول إلى نقاط أخرى.

في هذا الرسم التخطيطي، minPts = 4. النقطة A والنقاط الحمراء الأخرى هي نقاط أساسية، لأن المنطقة المحيطة بها ضمن نصف قطر ε تحتوي على 4 نقاط على الأقل (بما في ذلك النقطة نفسها). ولأنها جميعًا قابلة للوصول من بعضها البعض، فإنها تُشكّل مجموعة واحدة. النقطتان B وC ليستا نقاطًا أساسية، ولكن يمكن الوصول إليهما من A (عبر نقاط أساسية أخرى)، وبالتالي تنتميان إلى المجموعة أيضًا. النقطة N هي نقطة تشويش، وليست نقطة أساسية ولا يمكن الوصول إليها مباشرةً.

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

إذن، تحقق المجموعة خاصيتين:

  1. جميع النقاط داخل المجموعة متصلة ببعضها البعض من حيث الكثافة.
  2. إذا كانت نقطة ما قابلة للوصول إليها من حيث الكثافة من نقطة ما في المجموعة، فإنها تعتبر جزءًا من المجموعة أيضًا.

الخوارزمية

خوارزمية الاستعلام الأصلية

تتطلب خوارزمية DBSCAN مُعاملين: ε (eps) والحد الأدنى لعدد النقاط اللازمة لتكوين منطقة كثيفة [ a ] ( minPts ). تبدأ الخوارزمية بنقطة بداية عشوائية لم تتم زيارتها من قبل. يتم استرجاع جوار هذه النقطة (ε-neighborhood)، وإذا احتوى على عدد كافٍ من النقاط، يتم إنشاء مجموعة. وإلا، تُصنف النقطة على أنها ضوضاء. تجدر الإشارة إلى أنه قد يتم العثور على هذه النقطة لاحقًا في بيئة (ε-neighborhood) ذات حجم كافٍ لنقطة أخرى، وبالتالي تُضاف إلى مجموعة.

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

يمكن استخدام خوارزمية DBSCAN مع أي دالة مسافة [ 1 ] [ 4 ] (بالإضافة إلى دوال التشابه أو غيرها من المسندات). [ 9 ] وبالتالي، يمكن اعتبار دالة المسافة (dist) بمثابة مُعامل إضافي.

يمكن التعبير عن الخوارزمية بلغة شبه رمزية على النحو التالي: [ 4 ]

DBSCAN(DB, distFunc, eps, minPts ) { C := 0 /* عداد المجموعات */ لكل نقطة P في قاعدة البيانات DB { إذا كان label(P) ≠ undefined، فتابع / * تمت معالجتها مسبقًا في الحلقة الداخلية */ الجيران N := RangeQuery(DB, distFunc, P, eps) /* البحث عن الجيران */ إذا كان |N| < minPts ، فـ { /* فحص الكثافة */ label(P) := Noise /* تصنيف كـ Noise */ تابع } C := C + 1 /* تسمية المجموعة التالية */ label(P) := C /* تسمية النقطة الأولية */ SeedSet S := N \ {P} /* الجيران المراد توسيعهم */ for each point Q in S { /* معالجة كل نقطة بذرة Q */ if label(Q) = Noise then label(Q) := C /* تغيير Noise إلى نقطة حدودية */ if label(Q) ≠ undefined then continue /* تمت معالجتها مسبقًا (مثل نقطة حدودية) */ label(Q) := C /* تسمية الجار */ Neighbors N := RangeQuery(DB, distFunc, Q, eps) /* البحث عن الجيران */ if |N| ≥ minPts then { /* التحقق من الكثافة (إذا كانت Q نقطة أساسية) */ S := S ∪ N /* إضافة جيران جدد إلى مجموعة البذور */ } } } }

حيث يمكن تنفيذ RangeQuery باستخدام فهرس قاعدة البيانات لتحسين الأداء، أو باستخدام مسح خطي بطيء:

RangeQuery(DB, distFunc, Q, eps) { الجيران N := قائمة فارغة لكل نقطة P في قاعدة البيانات DB { /* امسح جميع النقاط في قاعدة البيانات */ إذا كانت دالة المسافة (Q، P) ≤ إبسيلون، فقم بما يلي : / * احسب المسافة وتحقق من قيمة إبسيلون */ N := N ∪ {P} /* أضف إلى النتيجة */ } } إرجاع N }

خوارزمية مجردة

يمكن تلخيص خوارزمية DBSCAN في الخطوات التالية: [ 4 ]

  1. ابحث عن النقاط في جوار ε (eps) لكل نقطة، وحدد النقاط الأساسية التي تحتوي على أكثر من minPts من الجيران.
  2. ابحث عن المكونات المتصلة للنقاط الأساسية على الرسم البياني المجاور، مع تجاهل جميع النقاط غير الأساسية.
  3. قم بتعيين كل نقطة غير أساسية إلى مجموعة قريبة إذا كانت المجموعة جارًا بمقدار ε (eps)، وإلا فقم بتعيينها إلى الضوضاء.

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

معيار التحسين

تعمل خوارزمية DBSCAN على تحسين دالة الخسارة التالية: [ 10 ] لأي تجميع ممكنج={ج1،...،جل}{\displaystyle C=\{C_{1},\ldots ,C_{l}\}}من بين جميع مجموعات التجميعج{\displaystyle {\mathcal {C}}}، فهو يقلل عدد المجموعات بشرط أن يكون كل زوج من النقاط في المجموعة قابلاً للوصول إليه من حيث الكثافة، وهو ما يتوافق مع الخاصيتين الأصليتين "الحد الأقصى" و "الاتصال" للمجموعة: [ 1 ]

مينج⊂ج، ددب(ص،q)≤ε ∀ص،q∈جأنا ∀جأنا∈ج|ج|{\displaystyle \min _{C\subset {\mathcal {C}},~d_{db}(p,q)\leq \varepsilon ~\forall p,q\in C_{i}~\forall C_{i}\in C}|C|}

أينددب(ص،q){\displaystyle d_{db}(p,q)}يعطي أصغرε{\displaystyle \varepsilon }بحيث تكون النقطتان p و q متصلتين بالكثافة.

تعقيد

تزور خوارزمية DBSCAN كل نقطة في قاعدة البيانات، وربما عدة مرات (مثلاً، كمرشحين لمجموعات مختلفة). مع ذلك، ولأسباب عملية، فإن التعقيد الزمني يعتمد في الغالب على عدد استدعاءات دالة regionQuery . تُنفذ DBSCAN استعلامًا واحدًا فقط من هذا النوع لكل نقطة، وإذا تم استخدام بنية فهرسة تُنفذ استعلام الجوار في زمن O(log n ) ، فسيتم الحصول على متوسط ​​تعقيد زمني إجمالي قدره O( n log n ) (إذا تم اختيار المعامل ε بطريقة مناسبة، أي بحيث يتم إرجاع O(log n ) نقطة فقط في المتوسط). بدون استخدام بنية فهرسة مُسرِّعة، أو على بيانات مُتدهورة (مثل جميع النقاط التي تقع ضمن مسافة أقل من ε )، يظل التعقيد الزمني في أسوأ الحالات O( n² ) .(ن2){\displaystyle \textstyle {\binom {n}{2}}}يمكن تجسيد المثلث العلوي لمصفوفة المسافة بحجم n = ( n ²- n )/2 لتجنب إعادة حساب المسافة، ولكن هذا يحتاج إلى ذاكرة O ( n ² ) ، في حين أن التنفيذ غير القائم على المصفوفة لـ DBSCAN يحتاج فقط إلى ذاكرة O( n ) .

يستطيع خوارزمية DBSCAN إيجاد مجموعات غير قابلة للفصل خطيًا. لا يمكن تجميع هذه المجموعة من البيانات بشكل كافٍ باستخدام خوارزمية k-means أو خوارزمية التجميع EM باستخدام خليط غاوسي.

المزايا

  1. لا يتطلب DBSCAN تحديد عدد المجموعات في البيانات مسبقًا، على عكس k-means .
  2. تستطيع خوارزمية DBSCAN اكتشاف التجمعات ذات الأشكال العشوائية. بل يمكنها حتى اكتشاف تجمع محاط تمامًا بتجمع آخر (لكنه غير متصل به). وبفضل مُعامل MinPts، يتم تقليل ما يُسمى بتأثير الرابط الأحادي (حيث تتصل التجمعات المختلفة بخط رفيع من النقاط).
  3. يحتوي DBSCAN على مفهوم الضوضاء، وهو قوي في مواجهة القيم الشاذة .
  4. لا تتطلب خوارزمية DBSCAN سوى مُعاملين، وهي غير حساسة في الغالب لترتيب النقاط في قاعدة البيانات. (مع ذلك، قد تتبادل النقاط الواقعة على حافة مجموعتين مختلفتين انتماءها إلى المجموعة إذا تغير ترتيب النقاط، ويكون تعيين المجموعة فريدًا فقط حتى التماثل).
  5. تم تصميم DBSCAN للاستخدام مع قواعد البيانات التي يمكنها تسريع استعلامات المناطق، على سبيل المثال باستخدام شجرة R* .
  6. يمكن تحديد المعلمات minPts و ε بواسطة خبير في المجال، إذا كانت البيانات مفهومة جيدًا.

العيوب

  1. لا تُعدّ خوارزمية DBSCAN حتمية تمامًا: إذ يمكن أن تنتمي نقاط الحدود التي يُمكن الوصول إليها من أكثر من مجموعة إلى أيٍّ من المجموعتين، وذلك تبعًا لترتيب معالجة البيانات. بالنسبة لمعظم مجموعات البيانات والمجالات، لا يتكرر هذا الوضع كثيرًا، ولا يُؤثر تأثيرًا يُذكر على نتيجة التجميع: [ 4 ] تُعتبر خوارزمية DBSCAN حتمية، سواءً بالنسبة للنقاط الأساسية أو نقاط التشويش. أما خوارزمية DBSCAN* [ 6 ] [ 7 ] فهي نسخة مُعدّلة تُعامل نقاط الحدود كتشويش، وبذلك تُحقق نتيجة حتمية تمامًا، بالإضافة إلى تفسير إحصائي أكثر اتساقًا للمكونات المتصلة بالكثافة.
  2. تعتمد جودة خوارزمية DBSCAN على مقياس المسافة المستخدم في الدالة regionQuery(P,ε) . يُعدّ المقياس الإقليدي الأكثر شيوعًا . لكن، خاصةً مع البيانات عالية الأبعاد ، قد يصبح هذا المقياس عديم الفائدة تقريبًا بسبب ما يُعرف بـ" لعنة الأبعاد "، مما يُصعّب إيجاد قيمة مناسبة لـ ε. مع ذلك، يُلاحظ هذا التأثير أيضًا في أي خوارزمية أخرى تعتمد على المسافة الإقليدية.
  3. لا تستطيع خوارزمية DBSCAN تجميع مجموعات البيانات بشكل جيد مع وجود اختلافات كبيرة في الكثافة، لأنه لا يمكن حينها اختيار تركيبة minPts -ε بشكل مناسب لجميع المجموعات. [ 11 ]
  4. إذا لم يتم فهم البيانات والمقياس بشكل جيد، فقد يكون اختيار عتبة مسافة ذات معنى ε أمرًا صعبًا.

انظر القسم أدناه حول الإضافات للاطلاع على التعديلات الخوارزمية لمعالجة هذه المشكلات.

تقدير المعلمات

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

  • MinPts : كقاعدة عامة، يمكن استنتاج الحد الأدنى لـ minPts من عدد الأبعاد D في مجموعة البيانات، حيث minPts ≥ D + 1. القيمة المنخفضة minPts = 1 غير منطقية، لأن كل نقطة تُعتبر حينها نقطة أساسية بحكم التعريف. عندما تكون minPts ≤ 2، ستكون النتيجة مماثلة للتجميع الهرمي باستخدام مقياس الرابط الأحادي، مع قطع مخطط التفرع عند الارتفاع ε. لذلك، يجب اختيار minPts على الأقل 3. مع ذلك، عادةً ما تكون القيم الأكبر أفضل لمجموعات البيانات التي تحتوي على تشويش، وستؤدي إلى مجموعات أكثر أهمية. كقاعدة عامة، يمكن استخدام minPts = 2· dim ، [ 9 ] ولكن قد يكون من الضروري اختيار قيم أكبر للبيانات الكبيرة جدًا، أو البيانات المشوشة، أو البيانات التي تحتوي على العديد من التكرارات. [ 4 ]
  • ε: يمكن اختيار قيمة ε باستخدام رسم بياني للمسافة k ، حيث تُرسم المسافة إلى أقرب جار k = minPts - 1 مرتبةً من الأكبر إلى الأصغر. [ 4 ] القيم الجيدة لـ ε هي تلك التي يظهر عندها هذا الرسم البياني "انحناءً": [ 1 ] [ 9 ] [ 4 ] إذا تم اختيار ε صغيرة جدًا، فلن يتم تجميع جزء كبير من البيانات؛ بينما في حالة اختيار قيمة عالية جدًا لـ ε، ستندمج المجموعات وستكون غالبية العناصر في نفس المجموعة. بشكل عام، يُفضل استخدام قيم صغيرة لـ ε، [ 4 ] وكقاعدة عامة، يجب ألا تتجاوز نسبة النقاط التي تقع ضمن هذه المسافة نسبة صغيرة. بدلاً من ذلك، يمكن استخدام رسم OPTICS لاختيار ε، [ 4 ] ولكن بعد ذلك يمكن استخدام خوارزمية OPTICS نفسها لتجميع البيانات.
  • دالة المسافة: يرتبط اختيار دالة المسافة ارتباطًا وثيقًا باختيار قيمة ε، وله تأثير كبير على النتائج. عمومًا، من الضروري أولًا تحديد مقياس مناسب للتشابه في مجموعة البيانات قبل اختيار قيمة المعامل ε. لا توجد طريقة لتقدير قيمة هذا المعامل، ولكن يجب اختيار دالة المسافة بما يتناسب مع مجموعة البيانات. على سبيل المثال، في البيانات الجغرافية، غالبًا ما تكون مسافة الدائرة العظمى خيارًا جيدًا.

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

في الآونة الأخيرة، قام أحد المؤلفين الأصليين لخوارزمية DBSCAN بإعادة النظر في خوارزميتي DBSCAN وOPTICS، ونشر نسخة محسّنة من خوارزمية DBSCAN الهرمية (HDBSCAN*)، [ 6 ] [ 7 ] والتي لم تعد تتضمن مفهوم نقاط الحدود. وبدلاً من ذلك، تشكل النقاط الأساسية فقط المجموعة.

العلاقة بالتكتل الطيفي

يرتبط تطبيق DBSCAN الطيفي بالتجميع الطيفي في الحالة البسيطة لتحديد مكونات الرسم البياني المتصلة - أي المجموعات المثلى التي لا تحتوي على حواف مقطوعة. [ 12 ] ومع ذلك، قد يكون هذا التطبيق مكلفًا حسابيًا، إلى حد كبير.يا(ن3){\displaystyle O(n^{3})}بالإضافة إلى ذلك، يجب تحديد عدد المتجهات الذاتية المراد حسابها. ولأسباب تتعلق بالأداء، تبقى خوارزمية DBSCAN الأصلية أفضل من تطبيقها الطيفي.

الإضافات

خوارزمية DBSCAN المعممة (GDBSCAN) [ 9 ] [ 13 ] هي تعميمٌ من نفس المؤلفين لخاصيتي "الجوار" و"الكثافة" العشوائيتين. يتم حذف المعاملين ε و minPts من الخوارزمية الأصلية ونقلهما إلى الخاصيتين. على سبيل المثال، في بيانات المضلعات، يمكن أن يكون "الجوار" أي مضلع متقاطع، بينما تستخدم خاصية الكثافة مساحات المضلعات بدلاً من عدد العناصر فقط.

تم اقتراح العديد من التحسينات لخوارزمية DBSCAN، بما في ذلك طرق التوازي، وتقدير المعلمات، ودعم البيانات غير المؤكدة. وقد تم توسيع الفكرة الأساسية لتشمل التجميع الهرمي بواسطة خوارزمية OPTICS . كما تُستخدم DBSCAN كجزء من خوارزميات تجميع الفضاءات الفرعية مثل PreDeCon و SUBCLU . HDBSCAN* [ 6 ] [ 7 ] هي نسخة هرمية من DBSCAN، وهي أسرع من OPTICS، ويمكن من خلالها استخراج تقسيم مسطح يتكون من أبرز المجموعات من التسلسل الهرمي. [ 14 ]

التوافر

أظهرت تطبيقات مختلفة لنفس الخوارزمية تباينات هائلة في الأداء، حيث استغرقت أسرعها 1.4 ثانية على مجموعة بيانات الاختبار، بينما استغرقت أبطأها 13803 ثانية. [ 15 ] ويمكن عزو هذه الاختلافات إلى جودة التنفيذ، واختلافات اللغة والمترجم، واستخدام الفهارس لتسريع العملية.

  • يحتوي Apache Commons Math على تطبيق Java للخوارزمية التي تعمل في وقت تربيعي.
  • يُقدّم برنامج ELKI تطبيقًا لخوارزمية DBSCAN بالإضافة إلى GDBSCAN ومتغيرات أخرى. يُمكن لهذا التطبيق استخدام هياكل فهرسة متنوعة لتحقيق زمن تشغيل أقل من التربيعي، كما يدعم دوال المسافة وأنواع البيانات المختلفة، إلا أنه قد يتفوق عليه أداء التطبيقات المُحسّنة (والمتخصصة) على مستوى منخفض عند التعامل مع مجموعات البيانات الصغيرة.
  • يتضمن mlpack تطبيقًا لخوارزمية DBSCAN مع تسريعها بتقنيات البحث في نطاق الشجرة المزدوجة.
  • يتضمن PostGIS برنامج ST_ClusterDBSCAN، وهو تطبيق ثنائي الأبعاد لخوارزمية DBSCAN يستخدم فهرس R-tree. يدعم البرنامج جميع أنواع الأشكال الهندسية، مثل النقاط والخطوط والمضلعات، إلخ.
  • تحتوي لغة R على تطبيقات لخوارزمية DBSCAN في الحزمتين dbscan و fpc . تدعم كلتا الحزمتين دوال المسافة المختلفة عبر مصفوفات المسافة. لا تدعم الحزمة fpc الفهرسة (وبالتالي يكون وقت التشغيل وتعقيد الذاكرة من الدرجة الثانية)، وهي بطيئة نسبيًا بسبب مُفسِّر R. توفر الحزمة dbscan تطبيقًا سريعًا بلغة C++ باستخدام أشجار kd (للمسافة الإقليدية فقط)، وتتضمن أيضًا تطبيقات لخوارزميات DBSCAN* و HDBSCAN* و OPTICS و OPTICSXi وغيرها من الطرق ذات الصلة.
  • تتضمن مكتبة scikit-learn تطبيقًا بلغة بايثون لخوارزمية DBSCAN لمقاييس مينكوفسكي المختلفة ، والتي يمكن تسريعها باستخدام أشجار kd وأشجار الكرة ، ولكنها تستخدم ذاكرة تربيعية في أسوأ الحالات. كما تُقدم إضافة إلى scikit-learn تطبيقًا لخوارزمية HDBSCAN*.
  • تتضمن مكتبة pyclustering تطبيقًا بلغة Python و C++ لخوارزمية DBSCAN للمسافة الإقليدية فقط بالإضافة إلى خوارزمية OPTICS.
  • يتضمن SPMF تطبيقًا لخوارزمية DBSCAN مع دعم شجرة kd للمسافة الإقليدية فقط.
  • يحتوي برنامج Weka (كحزمة اختيارية في أحدث الإصدارات) على تطبيق أساسي لـ DBSCAN يعمل في وقت تربيعي وذاكرة خطية.
  • يتضمن linfa تطبيقًا لخوارزمية DBSCAN للغة البرمجة Rust .
  • تتضمن لغة جوليا تطبيقًا لخوارزمية DBSCAN في حزمة Clustering.jl الخاصة بإحصائيات جوليا.

انظر أيضاً

ملحوظات

  1. ١ ٢ على الرغم من أن minPts يمثل الحد الأدنى لحجم المجموعة، إلا أن خوارزمية DBSCAN قد تُنتج مجموعات أصغر في بعض الحالات. [ ٤ ] تتكون مجموعة DBSCAN من نقطة أساسية واحدة على الأقل . [ ٤ ] ونظرًا لأن النقاط الأخرى قد تكون نقاط حدودية لأكثر من مجموعة، فلا يوجد ما يضمن احتواء كل مجموعة على minPts نقطة على الأقل.

مراجع

  1. 1 2 3 4 إستر، مارتن ؛ كريغل، هانز-بيتر ؛ ساندر، يورغ ؛ شو، شياووي (1996). سيموديس، إيفانجيلوس؛ هان، جياوي؛ فياض، أسامة م. (محررون). خوارزمية قائمة على الكثافة لاكتشاف التجمعات في قواعد البيانات المكانية الكبيرة مع وجود ضوضاء (ملف PDF) . وقائع المؤتمر الدولي الثاني لاكتشاف المعرفة واستخراج البيانات (KDD-96). مطبعة AAAI . الصفحات 226-231 . CiteSeerX 10.1.1.121.9220 . ISBN   1-57735-004-9.
  2. ↑ "Microsoft Academic Search: Papers" . مؤرشف من الأصل في 21 أبريل 2010. تم الاطلاع عليه في 18 أبريل 2010 .أكثر المقالات استشهاداً في مجال استخراج البيانات وفقاً لبحث مايكروسوفت الأكاديمي؛ يحتل DBSCAN المرتبة 24.
  3. ↑ "جائزة اختبار الزمن لعام 2014 من SIGKDD" . ACM SIGKDD. 18 أغسطس 2014. تاريخ الاسترجاع: 27 يوليو 2016 .
  4. 1 2 3 4 5 6 7 8 9 10 11 12 شوبرت، إريك ؛ ساندر، يورغ ؛ إستر، مارتن ؛ كريغل، هانز بيتر ؛ شو، شياووي (يوليو 2017). "مراجعة خوارزمية DBSCAN: لماذا وكيف يجب عليك (ولا تزال) استخدامها" . مجلة ACM لأنظمة قواعد البيانات . 42 (3): 19:1–19:21. doi : 10.1145/3068335 . ISSN 0362-5915 . S2CID 5156876 .  
  5. ↑ "الصفحة الرئيسية لـ TODS" . tods.acm.org . رابطة آلات الحوسبة . تم الاطلاع عليه بتاريخ 16 يوليو 2020 .
  6. 1 2 3 4 كامبيلو، ريكاردو جيه جي بي؛ مولافي، داوود؛ ساندر، يورغ (2013). بي، جيان؛ تسينغ، فينسنت إس؛ كاو، لونغبينغ؛ موتودا، هيروشي (محررون). التجميع القائم على الكثافة بناءً على تقديرات الكثافة الهرمية . التقدم في اكتشاف المعرفة واستخراج البيانات. المجلد 7819. برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ. الصفحات 160-172 . doi : 10.1007/978-3-642-37456-2_14 . ISBN   978-3-642-37455-5تم الاطلاع عليه بتاريخ 18 أغسطس 2023 .
  7. 1 2 3 4 كامبيلو، ريكاردو جيه جي بي؛ مولافي، داوود؛ زيمك، آرثر ؛ ساندر، يورغ (2015). "تقديرات الكثافة الهرمية لتجميع البيانات، وتصورها، والكشف عن القيم الشاذة". معاملات ACM لاكتشاف المعرفة من البيانات . 10 (1): 1-51 . doi : 10.1145/2733381 . ISSN 1556-4681 . S2CID 2887636 .  
  8. لينغ ، آر إف (1972-01-01). "حول نظرية وبناء مجموعات k" . مجلة الحاسوب . 15 (4): 326-332 . doi : 10.1093/comjnl/15.4.326 . ISSN 0010-4620 . 
  9. 1 2 3 4 ساندر، يورغ ؛ إستر، مارتن ؛ كريغل، هانز-بيتر ؛ شو، شياووي (1998). "التجميع القائم على الكثافة في قواعد البيانات المكانية: خوارزمية GDBSCAN وتطبيقاتها". استخراج البيانات واكتشاف المعرفة . 2 (2). برلين: سبرينغر-فيرلاغ : 169-194 . Bibcode : 1998DMKD....2..169S . doi : 10.1023/A:1009745219419 . S2CID 445002 . 
  10. ↑ بير، آنا؛ دراغانوف، أندرو؛ هوهما، إيلين؛ جان، فيليب؛ فراي، كريستيان إم إم؛ أسنت، إيرا (6 أغسطس 2023). "ربط النقاط - مسافة كثافة الاتصال توحد DBSCAN و k-Center والتجميع الطيفي" . وقائع المؤتمر التاسع والعشرين لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات . ACM. الصفحات 80-92 . doi : 10.1145/3580305.3599283 . ISBN  9798400701030. S2CID 260499476 . 
  11. ↑ كريجل، هانز-بيتر ؛ كروجر، بير؛ ساندر، يورغ ؛ زيمك، آرثر (2011). "التجميع القائم على الكثافة" . مجلة WIREs لاستخراج البيانات واكتشاف المعرفة . 1 (3): 231-240 . doi : 10.1002/widm.30 . S2CID 36920706. مؤرشف من الأصل بتاريخ 17-11-2016 . تم الاطلاع عليه بتاريخ 12-12-2011 . 
  12. ^ شوبرت، إريك ؛ هيس، سيبيل. موريك ، كاتارينا (2018). العلاقة بين DBSCAN وعوامل المصفوفة والتجمعات الطيفية (PDF) . ليرنن، ويسن، داتن، أناليسن (LWDA). ص 330 – 334 – عبر CEUR-WS.org. 
  13. ↑ ساندر، يورغ (1998). التجميع المعمم القائم على الكثافة لاستخراج البيانات المكانية . ميونيخ: دار نشر هربرت أوتز. ISBN 3-89675-469-6.
  14. ↑ كامبيلو، آر. جيه. جي. بي.؛ مولافي، د.؛ زيمك، أ .؛ ساندر، ج. (2013). "إطار عمل للاستخراج الأمثل للمجموعات من التسلسلات الهرمية، شبه الخاضع للإشراف وغير الخاضع للإشراف". استخراج البيانات واكتشاف المعرفة . 27 (3): 344. doi : 10.1007/s10618-013-0311-4 . S2CID 8144686 . 
  15. ↑ كريغل، هانز-بيتر ؛ شوبرت، إريك ؛ زيمك، آرثر (2016). "فن (الأسود) لتقييم وقت التشغيل: هل نقارن الخوارزميات أم التطبيقات؟". نظم المعرفة والمعلومات . 52 (2): 341. doi : 10.1007/s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .