DBSCAN का अर्थ है Density-Based Spatial Clustering of Applications with Noise (शोर के साथ अनुप्रयोगों का घनत्व-आधारित स्थानिक क्लस्टरिंग)। यह एक घनत्व-आधारित क्लस्टरिंग एल्गोरिदम है। एल्गोरिदम पर्याप्त उच्च घनत्व वाले क्षेत्रों को क्लस्टर्स में बढ़ाता है और शोर के साथ स्थानिक डेटाबेस में मनमाने आर्किटेक्चर के क्लस्टर्स को ढूंढता है। यह एक क्लस्टर को घनत्व-जुड़े बिंदुओं के अधिकतम समूह के रूप में दर्शाता है।
घनत्व-आधारित क्लस्टरिंग की अवधारणा में कई नई परिभाषाएं शामिल हैं जो इस प्रकार हैं -
किसी दिए गए ऑब्जेक्ट की त्रिज्या ε के भीतर का पड़ोस ऑब्जेक्ट के ε-पड़ोस के रूप में जाना जाता है।
यदि किसी ऑब्जेक्ट का ε-पड़ोस कम से कम एक न्यूनतम संख्या, MinPts, ऑब्जेक्ट्स को शामिल करता है, तो ऑब्जेक्ट को कोर ऑब्जेक्ट के रूप में जाना जाता है।
ऑब्जेक्ट्स के एक सेट, D को देखते हुए, यह कहा जा सकता है कि एक ऑब्जेक्ट p, ऑब्जेक्ट q से सीधे घनत्व-पहुंच योग्य है यदि p, q के ε-पड़ोस के अंदर है, और q एक कोर ऑब्जेक्ट है।
ऑब्जेक्ट्स के एक समूह, D में ε और MinPts के संबंध में एक ऑब्जेक्ट p, ऑब्जेक्ट q से घनत्व-पहुंच योग्य है यदि ऑब्जेक्ट्स p1..., pn की एक श्रृंखला है, जहां p1 = q और pn = p जिसमें pi+1, ε और MinPts के संबंध में pi से सीधे घनत्व-पहुंच योग्य है, 1 ≤ i ≤ n के लिए, pi ∈ D।
ऑब्जेक्ट्स के एक समूह, D में ε और MinPts के संबंध में एक ऑब्जेक्ट p, ऑब्जेक्ट q से घनत्व-जुड़ा हुआ है यदि एक ऑब्जेक्ट o ∈ D ऐसा है कि दोनों p और q, ε और MinPts के संबंध में o से घनत्व-पहुंच योग्य हैं।
घनत्व पहुंच क्षमता सीधी घनत्व पहुंच क्षमता का संक्रामक समापन है, और यह संबंध असममित है। केवल कोर ऑब्जेक्ट्स पारस्परिक रूप से घनत्व-पहुंच योग्य हैं। घनत्व कनेक्टिविटी एक सममित संबंध है।
एक घनत्व-आधारित क्लस्टर घनत्व-जुड़े ऑब्जेक्ट्स का एक समूह है जो घनत्व-पहुंच क्षमता के संबंध में अधिकतम है। किसी भी क्लस्टर में शामिल नहीं किए गए प्रत्येक ऑब्जेक्ट को शोर माना जाता है।
DBSCAN डेटाबेस में प्रत्येक बिंदु के ε-पड़ोस का परीक्षण करके क्लस्टर्स की खोज करता है। यदि किसी बिंदु p के ε-पड़ोस में MinPts से अधिक शामिल हैं, तो p को कोर ऑब्जेक्ट के रूप में एक नया क्लस्टर बनाया जाता है। DBSCAN इन कोर ऑब्जेक्ट्स से सीधे घनत्व-पहुंच योग्य ऑब्जेक्ट्स को पुनरावृत्त रूप से एकत्र करता है, जिसमें कुछ घनत्व-पहुंच योग्य क्लस्टर्स का विलय शामिल हो सकता है। प्रक्रिया तब समाप्त होती है जब किसी भी क्लस्टर में कोई नया बिंदु नहीं जोड़ा जा सकता।
यदि एक स्थानिक सूचकांक का उपयोग किया जाता है, तो DBSCAN की कम्प्यूटेशनल जटिलता O(nlogn) है, जहां n डेटाबेस ऑब्जेक्ट्स की संख्या है। इसलिए, यह O(n2) है। उपयोगकर्ता-प्रतिनिधित्व पैरामीटर्स ε और MinPts की उपयुक्त सेटिंग्स के साथ, एल्गोरिदम मनमाने आकार के क्लस्टर्स की खोज में कुशल है।
