डीबीएससीएएन

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

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

इतिहास

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

प्रारंभिक

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

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

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

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

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

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

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

एल्गोरिदम

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

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

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

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

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

    डीबीएससीएएन(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
}

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

डीबीएससीएएन एल्गोरिथ्म को निम्नलिखित चरणों में संक्षेपित किया जा सकता है:

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

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

जटिलता

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

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

फायदे

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

नुकसान

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

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

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

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

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

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

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

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

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

एक्सटेंशन

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

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

उपलब्धता

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

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