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