डीबीएससीएएन

शोर के साथ अनुप्रयोगों की घनत्व-आधारित स्थानिक क्लस्टरिंग (डीबीएससीएएन) 1996 में मार्टिन एस्तेर, हंस पीटर क्रिएगेल, जोर्ग सैंडर और ज़ियाओवेई जू द्वारा प्रस्तावित डेटा क्लस्टरिंग एल्गोरिदम है।^[1] यह एक घनत्व-आधारित क्लस्टरिंग गैर-पैरामेट्रिक एल्गोरिथ्म है: किसी स्थान में बिंदुओं का एक सेट दिया जाता है, यह उन बिंदुओं को एक साथ समूहित करता है जो बारीकी से एक साथ पैक किए जाते हैं (किनारे के पास कई निश्चित-त्रिज्या वाले बिंदु), अंकन बाहरी बिंदुओं के रूप में जो कम घनत्व वाले क्षेत्रों में अकेले स्थित हैं (जिनके निकटतम किनारे बहुत दूर हैं)। DBSCAN सबसे सामान्य और सबसे अधिक उद्धृत क्लस्टरिंग एल्गोरिदम में से एक है।^[2]

2014 में, अग्रणी डेटा माइनिंग कॉन्फ्रेंस, ACM SIGKDD में एल्गोरिदम को टेस्ट ऑफ टाइम अवार्ड (सिद्धांत और व्यवहार में पर्याप्त ध्यान प्राप्त करने वाले एल्गोरिदम को दिया जाने वाला पुरस्कार) से सम्मानित किया गया था।^[3] As of July 2020^[update], अनुवर्ती पेपर DBSCAN को फिर से देखा जा सकता है: आपको DBSCAN का उपयोग क्यों और कैसे करना चाहिए (अभी भी)^[4] प्रतिष्ठित डेटाबेस सिस्टम पर एसीएम ट्रांजैक्शंस (टीओडीएस) दैनिकी के 8 सबसे अधिक डाउनलोड किए गए लेखों की सूची में दिखाई देता है।^[5]

इतिहास

1972 में, रॉबर्ट एफ. लिंग ने ^[6] कंप्यूटर जर्नल में k-क्लस्टर्स के सिद्धांत और निर्माण में O(n³) की अनुमानित रनटाइम जटिलता के साथ एक निकट से संबंधित एल्गोरिथ्म प्रकाशित किया।^[6] DBSCAN में O(n²) की सबसे खराब स्थिति है, और DBSCAN का डेटाबेस-उन्मुख रेंज-क्वेरी फॉर्मूलेशन सूचकांक त्वरण की अनुमति देता है। सीमा बिंदुओं को संभालने में एल्गोरिदम थोड़ा भिन्न हैं।

प्रारंभिक

किसी स्थान में क्लस्टर किए जाने वाले बिंदुओं के एक सेट पर विचार करें। मान ले कि $ε$ किसी बिंदु के संबंध में निकट की त्रिज्या निर्दिष्ट करने वाला एक पैरामीटर बनें। DBSCAN क्लस्टरिंग के प्रयोजन के लिए, बिंदुओं को मुख्य बिंदुओं, (सीधे-) पहुंच योग्य बिंदुओं और आउटलेर्स के रूप में वर्गीकृत किया गया है, निम्नानुसार:

एक बिंदु $p$ एक कोर बिंदु है यदि कम से कम $minPts$ अंक दूरी के भीतर हैं $ε$ इसका (सहित) $p$ ).
एक बिंदु $q$ से सीधे पहुंचा जा सकता है $p$ यदि बिंदु $q$ दूरी के भीतर है $ε$ मूल बिंदु से $p$ . कहा जाता है कि अंक केवल मुख्य बिंदुओं से सीधे पहुंच योग्य होते हैं।
एक बिंदु $q$ से पहुंच योग्य है $p$ यदि एक पथ $p 1, ..., p n$ साथ $p 1 = p$ और $p n = q$ , जहां प्रत्येक $p i +1$ सीधे $p i$ से पहुंच योग्य है। ध्यान दें कि इसका तात्पर्य यह है कि प्रारंभिक बिंदु और पथ पर सभी बिंदु कोर बिंदु होना चाहिए, जिसमें $q$ अपवाद हो।
िसी भी अन्य बिंदु से न पहुंच सकने वाले सभी बिंदु आउटलेयर या शोर बिंदु हैं।

अब अगर $p$ एक मुख्य बिंदु है, फिर यह उन सभी बिंदुओं (कोर या गैर-कोर) के साथ मिलकर एक क्लस्टर बनाता है जो इससे पहुंच योग्य हैं। प्रत्येक क्लस्टर में कम से कम एक मुख्य बिंदु होता है; गैर-कोर बिंदु क्लस्टर का हिस्सा हो सकते हैं, लेकिन वे इसका किनारा बनाते हैं, क्योंकि उनका उपयोग अधिक बिंदुओं तक पहुंचने के लिए नहीं किया जा सकता है।

इस आरेख में,

minPts = 4

. बिंदु A और अन्य लाल बिंदु मुख्य बिंदु हैं, क्योंकि इन बिंदुओं के आसपास का क्षेत्र एक में है

ε

त्रिज्या में कम से कम 4 बिंदु होते हैं (स्वयं बिंदु सहित)। क्योंकि वे सभी एक-दूसरे से पहुंच योग्य हैं, वे एक एकल क्लस्टर बनाते हैं। बिंदु B और C मुख्य बिंदु नहीं हैं, लेकिन A (अन्य मुख्य बिंदुओं के माध्यम से) तक पहुंचा जा सकता है और इस प्रकार क्लस्टर से भी संबंधित हैं। प्वाइंट एन एक शोर बिंदु है जो न तो मुख्य बिंदु है और न ही सीधे पहुंच योग्य है।

रीचैबिलिटी एक सममित संबंध नहीं है: परिभाषा के अनुसार, केवल मुख्य बिंदु ही गैर-मुख्य बिंदुओं तक पहुंच सकते हैं। विपरीत सत्य नहीं है, इसलिए एक गैर-मुख्य बिंदु तक पहुंचा जा सकता है, लेकिन उससे कुछ भी नहीं पहुंचा जा सकता है। इसलिए, डीबीएससीएएन द्वारा पाए गए क्लस्टर की सीमा को औपचारिक रूप से परिभाषित करने के लिए कनेक्टिविटी की एक और धारणा की आवश्यकता है। दो बिंदु $p$ और $q$ यदि कोई बिंदु है तो घनत्व-जुड़े हुए हैं $o$ ऐसे कि दोनों $p$ और $q$ से पहुंच योग्य हैं $o$ . घनत्व-संबद्धता सममित है।

एक क्लस्टर तब दो गुणों को पूरा करता है:

क्लस्टर के भीतर सभी बिंदु परस्पर घनत्व से जुड़े हुए हैं।
यदि कोई बिंदु क्लस्टर के किसी बिंदु से घनत्व-पहुंच योग्य है, तो यह क्लस्टर का भी हिस्सा है।

एल्गोरिदम

मूल क्वेरी-आधारित एल्गोरिदम

DBSCAN को दो मापदंडों: ε (eps) और सघन क्षेत्र बनाने के लिए आवश्यक न्यूनतम अंक^{[lower-alpha 1]} (minPts) की आवश्यकता होती है। यह यादृच्छिक प्रारंभिक बिंदु के साथ प्रारंभ होता है जिसे देखा नहीं गया है। इस बिंदु का ε-लघु भाग पुनः प्राप्त किया जाता है, और यदि इसमें पर्याप्त रूप से कई बिंदु हैं, तो एक क्लस्टर प्रारंभ किया जाता है। अन्यथा, बिंदु को शोर के रूप में लेबल किया जाता है। ध्यान दें कि यह बिंदु बाद में किसी भिन्न बिंदु के पर्याप्त आकार के ε-वातावरण में पाया जा सकता है और इसलिए इसे क्लस्टर का हिस्सा बनाया जा सकता है।

यदि कोई बिंदु किसी क्लस्टर का सघन भाग पाया जाता है, तो उसका ε-लघु भाग भी उस क्लस्टर का हिस्सा होता है। इसलिए, ε-लघु भाग के भीतर पाए जाने वाले सभी बिंदुओं को जोड़ा जाता है, जैसा कि उनके अपने ε-लघु भाग में होता है जब वे भी घने होते हैं। यह प्रक्रिया तब तक जारी रहती है जब तक घनत्व से जुड़ा क्लस्टर पूरी तरह से नहीं मिल जाता। फिर, एक नए अनदेखे बिंदु को पुनः प्राप्त किया जाता है और संसाधित किया जाता है, जिससे आगे क्लस्टर या शोर की खोज होती है।

DBSCAN का उपयोग किसी भी दूरी फलन के साथ किया जा सकता है^[1]^[4](साथ ही समानता कार्य या अन्य विधेय)।^[7] इसलिए दूरी फलन (dist) को एक अतिरिक्त पैरामीटर के रूप में देखा जा सकता है।

एल्गोरिथ्म को स्यूडोकोड में इस प्रकार व्यक्त किया जा सकता है:^[4]

    DBSCAN(DB, distFunc, eps, minPts) {

    C := 0                                                  /* Cluster counter */
    for each point P in database DB {
        if label(P) ≠ undefined then continue               /* Previously processed in inner loop */
        Neighbors N := RangeQuery(DB, distFunc, P, eps)     /* Find neighbors */
        if |N| < minPts then {                              /* Density check */
            label(P) := Noise                               /* Label as Noise */
            continue
        }
        C := C + 1                                          /* next cluster label */
        label(P) := C                                       /* Label initial point */
        SeedSet S := N \ {P}                                /* Neighbors to expand */
        for each point Q in S {                             /* Process every seed point Q */
            if label(Q) = Noise then label(Q) := C          /* Change Noise to border point */
            if label(Q) ≠ undefined then continue           /* Previously processed (e.g., border point) */
            label(Q) := C                                   /* Label neighbor */
            Neighbors N := RangeQuery(DB, distFunc, Q, eps) /* Find neighbors */
            if |N| ≥ minPts then {                          /* Density check (if Q is a core point) */
                S := S ∪ N                                  /* Add new neighbors to seed set */
            }
        }
    }
}

जहां बेहतर प्रदर्शन के लिए डेटाबेस इंडेक्स का उपयोग करके या धीमी रैखिक स्कैन का उपयोग करके रेंजक्वेरी को कार्यान्वित किया जा सकता है:

RangeQuery(DB, distFunc, Q, eps) {

    Neighbors N := empty list
    for each point P in database DB {                      /* Scan all points in the database */
        if distFunc(Q, P) ≤ eps then {                     /* Compute distance and check epsilon */
            N := N ∪ {P}                                   /* Add to result */
        }
    }
    return N
}

अमूर्त एल्गोरिथ्म

DBSCAN एल्गोरिथ्म को निम्नलिखित चरणों में संक्षेपित किया जा सकता है:^[4]

प्रत्येक बिंदु के ε (eps) लघु भाग में बिंदु ढूंढें, और इससे अधिक वाले मुख्य बिंदुओं minPts लघु भागियों की पहचान करें।
सभी गैर-कोर बिंदुओं को अनदेखा करते हुए, लघु भागी ग्राफ़ पर मुख्य बिंदुओं के कनेक्टेड घटक (ग्राफ़ सिद्धांत) को ढूंढें।
यदि क्लस्टर एक ε (eps) लघु भागी है, तो प्रत्येक गैर-कोर बिंदु को पास के क्लस्टर में निर्दिष्ट करें, अन्यथा इसे शोर के लिए निर्दिष्ट करें।

इसके सरल कार्यान्वयन के लिए चरण 1 में लघु भाग को संग्रहीत करने की आवश्यकता होती है, इस प्रकार पर्याप्त मेमोरी की आवश्यकता होती है। मूल DBSCAN एल्गोरिदम को एक समय में एक बिंदु के लिए इन चरणों को निष्पादित करने की आवश्यकता नहीं होती है।

जटिलता

DBSCAN डेटाबेस के प्रत्येक बिंदु पर संभवतः कई बार जाता है (उदाहरण के लिए, विभिन्न समूहों के उम्मीदवारों के रूप में)। यद्यपि, व्यावहारिक विचारों के लिए, समय जटिलता अधिकतर क्षेत्रक्वेरी सामान्यंत्रणों की संख्या से नियंत्रित होती है। DBSCAN प्रत्येक बिंदु के लिए ऐसी ही एक क्वेरी निष्पादित करता है, और यदि एक स्थानिक सूचकांक का उपयोग किया जाता है जो लघु भागियों के पास एक निश्चित-त्रिज्या निष्पादित करता है $O(log n)$ , की समग्र औसत रनटाइम जटिलता $O(n log n)$ प्राप्त होता है (यदि पैरामीटर $ε$ को सार्थक तरीके से चुना जाता है, यानी कि केवल औसतन $O(log n)$ अंक लौटाए जाते हैं)। त्वरित सूचकांक संरचना के उपयोग के बिना, या विकृत डेटा पर (जैसे कि से कम दूरी के सभी बिंदु) $ε$ ), सबसे खराब स्थिति में रन टाइम जटिलता $O(n ²)$ बनी रहती है। $\textstyle {\binom {n}{2}}$ - n = (n²-n)/2 दूरी मैट्रिक्स के आकार के ऊपरी त्रिकोण को दूरी पुनर्गणना से बचने के लिए सामग्रीकृत किया जा सकता है, लेकिन इसके लिए $O(n ²)$ मेमोरी की आवश्यकता है, जबकि DBSCAN के गैर-मैट्रिक्स आधारित कार्यान्वयन के लिए केवल $O(n)$ मेमोरी आवश्यकता होती है।

DBSCAN गैर-रैखिक रूप से अलग करने योग्य क्लस्टर ढूंढ सकता है। इस डेटासेट को k-मीन्स या गॉसियन मिक्सचर EM क्लस्टरिंग के साथ पर्याप्त रूप से क्लस्टर नहीं किया जा सकता है।

फायदे

DBSCAN को k-means के विपरीत, डेटा में क्लस्टर की संख्या को प्राथमिकता से निर्दिष्ट करने की आवश्यकता नहीं होती है।
DBSCAN याट्टीच्छक आकार के क्लस्टर ढूंढ सकता है। यह एक ऐसे क्लस्टर को भी ढूंढ सकता है जो पूरी तरह से एक अलग क्लस्टर से घिरा हुआ है (लेकिन उससे जुड़ा नहीं है)। MinPts पैरामीटर के कारण, तथाकथित एकल-लिंक प्रभाव (विभिन्न समूहों को बिंदुओं की एक पतली रेखा से जोड़ा जाना) कम हो जाता है।
DBSCAN में शोर की अवधारणा है, और यह विसंगति का पता लगाने में सक्षम है।
DBSCAN को केवल दो मापदंडों की आवश्यकता होती है और यह डेटाबेस में बिंदुओं के क्रम के प्रति अधिकतर असंवेदनशील होता है। (यद्यपि, यदि बिंदुओं का क्रम बदल जाता है, तो दो अलग-अलग समूहों के किनारे पर बैठे बिंदु क्लस्टर सदस्यता को स्वैप कर सकते हैं, और क्लस्टर असाइनमेंट केवल समरूपता तक अद्वितीय है।)
DBSCAN को ऐसे डेटाबेस के साथ उपयोग के लिए डिज़ाइन किया गया है जो क्षेत्र के प्रश्नों को तेज़ कर सकता है, उदाहरण के लिए R* रेखा का उपयोग करना है।
पैरामीटर minPts और ε को एक डोमेन विशेषज्ञ द्वारा सेट किया जा सकता है, यदि डेटा अच्छी तरह से समझा गया हो।

नुकसान

DBSCAN पूरी तरह से नियतात्मक नहीं है: सीमा बिंदु जो एक से अधिक क्लस्टर से पहुंच योग्य हैं, डेटा संसाधित होने के क्रम के आधार पर किसी भी क्लस्टर का हिस्सा हो सकते हैं। अधिकांश डेटा सेट और डोमेन के लिए, यह स्थिति प्रायः उत्पन्न नहीं होती है और क्लस्टरिंग परिणाम पर इसका बहुत कम प्रभाव पड़ता है:^[4] मुख्य बिंदुओं और शोर बिंदुओं दोनों पर, DBSCAN नियतात्मक है। DBSCAN*^[8]एक भिन्नता है जो सीमा बिंदुओं को शोर के रूप में मानती है, और इस तरह पूरी तरह से नियतात्मक परिणाम के साथ-साथ घनत्व से जुड़े घटकों की अधिक सुसंगत सांख्यिकीय व्याख्या प्राप्त करती है।
DBSCAN की गुणवत्ता रीजनक्वेरी(P,ε) फलन में प्रयुक्त मीट्रिक (गणित) पर निर्भर करती है। उपयोग की जाने वाली सबसे सामान्य दूरी मीट्रिक यूक्लिडियन दूरी है। विशेष रूप से उच्च-आयामी डेटा को क्लस्टर करने के लिए, इस मीट्रिक को तथाकथित आयाम की वक्रता के कारण, इसे अनुवादित करने के लिए एक उचित मूल्य खोजने में मुश्किल बना रहा है, जिससे ε के लिए उचित मान ढूंढना मुश्किल हो जाता है। यद्यपि, यह प्रभाव यूक्लिडियन दूरी पर आधारित किसी अन्य एल्गोरिदम में भी उपस्थित है।
DBSCAN घनत्व में बड़े अंतर के साथ डेटा सेट को अच्छी तरह से क्लस्टर नहीं कर सकता, क्योंकि minPts-ε संयोजन को सभी समूहों के लिए उचित रूप से नहीं चुना जा सकता है।^[9]
यदि डेटा और पैमाने को अच्छी तरह से नहीं समझा जाता है, तो एक सार्थक दूरी सीमा ε का चयन करना मुश्किल हो सकता है।

इन स्थितियो से निपटने के लिए एल्गोरिथम संशोधनों के एक्सटेंशन पर नीचे दिया गया अनुभाग देखें।

पैरामीटर अनुमान

प्रत्येक डेटा माइनिंग कार्य में मापदंडों की समस्या होती है। प्रत्येक पैरामीटर विशिष्ट तरीकों से एल्गोरिदम को प्रभावित करता है। DBSCAN के लिए, पैरामीटर ε और minPts जरूरत है। पैरामीटर उपयोगकर्ता द्वारा निर्दिष्ट किए जाने चाहिए. आदर्श रूप से, ε का मान हल की जाने वाली समस्या (उदाहरण के लिए भौतिक दूरी) द्वारा दिया जाता है और minPts तो वांछित न्यूनतम क्लस्टर आकार है।^{[lower-alpha 1]}

MinPts: सामान्य नियम के रूप में, न्यूनतमminPts को डेटा सेट में आयाम डी की संख्या से प्राप्त किया जा सकता हैminPts ≥ D + 1. का निम्न मानminPts = 1 का कोई मतलब नहीं है, क्योंकि परिभाषा के अनुसार प्रत्येक बिंदु एक मुख्य बिंदु है। साथminPts ≤ 2, परिणाम एकल लिंक मीट्रिक के साथ पदानुक्रमित क्लस्टरिंग के समान होगा, ऊंचाई ε पर डेंड्रोग्राम कट के साथ। इसलिए,minPts को कम से कम 3 चुना जाना चाहिए। यद्यपि, बड़े मान सामान्यतौर पर शोर वाले डेटा सेट के लिए बेहतर होते हैं और इससे अधिक महत्वपूर्ण क्लस्टर प्राप्त होंगे। अंगूठे के नियम के रूप में,minPts = 2·मंद का उपयोग किया जा सकता है,^[7]लेकिन बहुत बड़े डेटा के लिए, शोर वाले डेटा के लिए या कई डुप्लिकेट वाले डेटा के लिए बड़े मान चुनना आवश्यक हो सकता है।^[4]
ε: ε के लिए मान को निकटतम लघु भागी ग्राफ|k-दूरी ग्राफ का उपयोग करके चुना जा सकता है, जो कि k = की दूरी को प्लॉट करता है।minPts-1 निकटतम लघु भागी को सबसे बड़े से सबसे छोटे मूल्य तक ऑर्डर किया गया।^[4]ε के अच्छे मान वे हैं जहां यह प्लॉट कोहनी दिखाता है:^[1]^[7]^[4]यदि ε को बहुत छोटा चुना जाता है, तो डेटा का एक बड़ा हिस्सा क्लस्टर नहीं किया जाएगा; जबकि ε के बहुत अधिक मान के लिए, क्लस्टर विलीन हो जाएंगे और अधिकांश ऑब्जेक्ट एक ही क्लस्टर में होंगे। सामान्य तौर पर, ε के छोटे मान बेहतर होते हैं,^[4]और सामान्य नियम के अनुसार बिंदुओं का केवल एक छोटा सा अंश ही एक दूसरे से इस दूरी के भीतर होना चाहिए। वैकल्पिक रूप से, ε को चुनने के लिए एक प्रकाशिकी एल्गोरिथ्म प्लॉट का उपयोग किया जा सकता है,^[4]लेकिन फिर ऑप्टिक्स एल्गोरिदम का उपयोग डेटा को क्लस्टर करने के लिए किया जा सकता है।
दूरी फलन: दूरी फलन का चुनाव ε की पसंद के साथ मजबूती से जुड़ा हुआ है, और परिणामों पर इसका बड़ा प्रभाव पड़ता है। सामान्य तौर पर, पैरामीटर ε को चुनने से पहले, डेटा सेट के लिए समानता के उचित माप की पहचान करना आवश्यक होगा। इस पैरामीटर के लिए कोई अनुमान नहीं है, लेकिन डेटा सेट के लिए दूरी फलन को उचित रूप से चुना जाना चाहिए। उदाहरण के लिए, भौगोलिक डेटा पर, ग्रेट-सर्कल दूरी प्रायः एक अच्छा विकल्प होती है।

ऑप्टिक्स एल्गोरिदम को DBSCAN के सामान्यीकरण के रूप में देखा जा सकता है जो ε पैरामीटर को अधिकतम मान से बदल देता है जो ज्यादातर प्रदर्शन को प्रभावित करता है। MinPts तब अनिवार्य रूप से खोजने के लिए न्यूनतम क्लस्टर आकार बन जाता है। जबकि एल्गोरिथ्म को DBSCAN की तुलना में पैरामीटराइज़ करना बहुत आसान है, परिणामों का उपयोग करना थोड़ा अधिक कठिन है, क्योंकि यह सामान्यतौर पर DBSCAN द्वारा उत्पादित सरल डेटा विभाजन के बजाय एक पदानुक्रमित क्लस्टरिंग उत्पन्न करेगा।

हाल ही में, DBSCAN के मूल लेखकों में से एक ने DBSCAN और OPTICS पर दोबारा गौर किया है, और पदानुक्रमित DBSCAN (HDBSCAN*) का एक परिष्कृत संस्करण प्रकाशित किया है।^[8] जिसमें अब सीमा बिंदुओं की कोई धारणा नहीं है। इसके बजाय, केवल मुख्य बिंदु ही क्लस्टर बनाते हैं।

वर्णक्रमीय क्लस्टरिंग से संबंध

डीबीएससीएएन का वर्णक्रमीय कार्यान्वयन कनेक्टेड घटक (ग्राफ सिद्धांत) के निर्धारण के तुच्छ मामले में वर्णक्रमीय क्लस्टरिंग से संबंधित है - बिना किनारों के कटे हुए इष्टतम क्लस्टर।^[10] यद्यपि, यह कम्प्यूटेशनल रूप से गहन हो सकता है $O(n^{3})$ . इसके अतिरिक्त, किसी को गणना करने के लिए eigenvectors की संख्या चुननी होगी। प्रदर्शन कारणों से, मूल DBSCAN एल्गोरिथ्म इसके वर्णक्रमीय कार्यान्वयन के लिए बेहतर है।

एक्सटेंशन

सामान्यीकृत डीबीएससीएएन (जीडीबीएससीएएन)^[7]^[11] उन्हीं लेखकों द्वारा मनमाने लघु भाग और सघन विधेय का सामान्यीकरण है। ε औरminPts पैरामीटर को मूल एल्गोरिदम से हटा दिया जाता है और विधेय में ले जाया जाता है। उदाहरण के लिए, बहुभुज डेटा पर, लघु भाग कोई भी प्रतिच्छेदी बहुभुज हो सकता है, जबकि घनत्व विधेय केवल वस्तु गणना के बजाय बहुभुज क्षेत्रों का उपयोग करता है।

DBSCAN एल्गोरिथ्म के विभिन्न विस्तार प्रस्तावित किए गए हैं, जिनमें समानांतरीकरण, पैरामीटर अनुमान और अनिश्चित डेटा के लिए समर्थन के तरीके शामिल हैं। मूल विचार को ऑप्टिक्स एल्गोरिदम द्वारा पदानुक्रमित क्लस्टरिंग तक बढ़ा दिया गया है। DBSCAN का उपयोग PreDeCon और SUBCLU जैसे सबस्पेस क्लस्टरिंग एल्गोरिदम के हिस्से के रूप में भी किया जाता है। एचडीबीएसकैन^[8]डीबीएससीएएन का एक पदानुक्रमित संस्करण है जो ऑप्टिक्स से भी तेज़ है, जिसमें से सबसे प्रमुख समूहों से युक्त एक फ्लैट विभाजन को पदानुक्रम से निकाला जा सकता है।^[12]

उपलब्धता

एक ही एल्गोरिथ्म के अलग-अलग कार्यान्वयन में भारी प्रदर्शन अंतर प्रदर्शित किया गया, परीक्षण डेटा सेट पर सबसे तेज़ 1.4 सेकंड में समाप्त हुआ, सबसे धीमा 13803 सेकंड में समाप्त हुआ।^[13] अंतरों को कार्यान्वयन की गुणवत्ता, भाषा और कंपाइलर अंतर और त्वरण के लिए अनुक्रमणिका के उपयोग के लिए जिम्मेदार ठहराया जा सकता है।

अपाचे कॉमन्स Math में द्विघात समय में चलने वाले एल्गोरिदम का जावा कार्यान्वयन शामिल है।
ELKI DBSCAN के साथ-साथ GDBSCAN और अन्य वेरिएंट का कार्यान्वयन प्रदान करता है। यह कार्यान्वयन उप-द्विघात रनटाइम के लिए विभिन्न सूचकांक संरचनाओं का उपयोग कर सकता है और मनमानी दूरी के कार्यों और मनमाने डेटा प्रकारों का समर्थन करता है, लेकिन यह छोटे डेटा सेट पर निम्न-स्तरीय अनुकूलित (और विशेष) कार्यान्वयन द्वारा बेहतर प्रदर्शन कर सकता है।
MATLAB ने R2019a जारी होने के बाद से अपने सांख्यिकी और मशीन लर्निंग टूलबॉक्स में DBSCAN का कार्यान्वयन शामिल किया है।
mlpack में डुअल-ट्री रेंज सर्च तकनीकों के साथ त्वरित डीबीएससीएएन का कार्यान्वयन शामिल है।
PostGIS में ST_ClusterDBSCAN शामिल है - DBSCAN का 2D कार्यान्वयन जो R-ट्री इंडेक्स का उपयोग करता है। कोई भी ज्यामिति प्रकार समर्थित है, उदा. प्वाइंट, लाइनस्ट्रिंग, बहुभुज, आदि।
आर (प्रोग्रामिंग भाषा) में पैकेज dbscan और fpc में DBSCAN का कार्यान्वयन शामिल है। . दोनों पैकेज दूरी मैट्रिक्स के माध्यम से मनमाने ढंग से दूरी के कार्यों का समर्थन करते हैं। पैकेज एफपीसी में इंडेक्स समर्थन नहीं है (और इस प्रकार इसमें द्विघात रनटाइम और मेमोरी जटिलता है) और आर दुभाषिया के कारण यह धीमा है। पैकेज dbscan k-d पेड़ों (केवल यूक्लिडियन दूरी के लिए) का उपयोग करके तेज़ C++ कार्यान्वयन प्रदान करता है और इसमें DBSCAN*, HDBSCAN*, OPTICS, OPTICSXi और अन्य संबंधित तरीकों का कार्यान्वयन भी शामिल है।
स्किकिट-लर्न में मनमानी मिन्कोव्स्की दूरी के लिए डीबीएससीएएन का पायथन कार्यान्वयन शामिल है, जिसे के-डी पेड़ों और बॉल पेड़ों का उपयोग करके त्वरित किया जा सकता है लेकिन जो सबसे खराब स्थिति वाली द्विघात मेमोरी का उपयोग करता है। एक scikit-learn में योगदान HDBSCAN* एल्गोरिदम का कार्यान्वयन प्रदान करता है।
pyclustering लाइब्रेरी में केवल यूक्लिडियन दूरी के साथ-साथ ऑप्टिक्स एल्गोरिदम के लिए DBSCAN का पायथन और C++ कार्यान्वयन शामिल है।
SPMF में केवल यूक्लिडियन दूरी के लिए k-d ट्री समर्थन के साथ DBSCAN एल्गोर�

[1]

[2]

[3]

[4]

[5]

[6]

[lower-alpha 1]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Anonymous

Search