डीबीएससीएएन

शोर के साथ अनुप्रयोगों की घनत्व-आधारित स्थानिक क्लस्टरिंग (डीबीएससीएएन) 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 को दो मापदंडों की आवश्यकता होती है: ε (ईपीएस) और सघन क्षेत्र बनाने के लिए आवश्यक न्यूनतम अंक^{[lower-alpha 1]} (minPts). यह एक मनमाने प्रारंभिक बिंदु से शुरू होता है जिस पर कभी दौरा नहीं किया गया है। इस बिंदु का ε-पड़ोस पुनः प्राप्त किया जाता है, और यदि इसमें पर्याप्त रूप से कई बिंदु हैं, तो एक क्लस्टर शुरू किया जाता है। अन्यथा, बिंदु को शोर के रूप में लेबल किया जाता है। ध्यान दें कि यह बिंदु बाद में किसी भिन्न बिंदु के पर्याप्त आकार के ε-वातावरण में पाया जा सकता है और इसलिए इसे क्लस्टर का हिस्सा बनाया जा सकता है।

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

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

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

DBSCAN(DB, distFunc, eps, minPts) {

    सी:= 0 /*क्लस्टर काउंटर*/
    डेटाबेस डीबी में 'प्रत्येक' बिंदु पी के लिए {
        'यदि' लेबल (पी) ≠ अपरिभाषित 'तब' 'जारी रखें (कीवर्ड)' /* पहले आंतरिक लूप में संसाधित */
        पड़ोसी एन:= रेंजक्वेरी(डीबी, डिस्टफनक, पी, ईपीएस) /*पड़ोसी खोजें*/
        'अगर' |एन| < minPts फिर { /* घनत्व जांच */
            लेबल(पी) := शोर /* शोर के रूप में लेबल करें */
            जारी रखना
        }
        सी := सी + 1 /* अगला क्लस्टर लेबल */
        लेबल(पी) := सी /* लेबल प्रारंभिक बिंदु */
        सीडसेट एस := एन \ {पी} /* पड़ोसियों का विस्तार करने के लिए */
        S में प्रत्येक बिंदु Q के लिए { /* प्रत्येक बीज बिंदु Q को संसाधित करें */
            यदि लेबल (क्यू) = शोर है तो लेबल (क्यू) := सी /* शोर को सीमा बिंदु पर बदलें */
            यदि लेबल (क्यू) ≠ अपरिभाषित है तो जारी रखें /* पहले संसाधित (उदाहरण के लिए, सीमा बिंदु) */
            लेबल(क्यू) := सी /* लेबल पड़ोसी */
            पड़ोसी एन := रेंजक्वेरी(डीबी, डिस्टफनक, क्यू, ईपीएस) /*पड़ोसी खोजें */
            यदि |एन| ≥ minPts फिर { /* घनत्व जांच (यदि क्यू एक मुख्य बिंदु है) */
                एस := एस ∪ एन /* बीज सेट में नए पड़ोसी जोड़ें */
            }
        }
    }
}

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

रेंजक्वेरी(DB, distFunc, Q, eps) {
    पड़ोसी एन := खाली सूची
    डेटाबेस DB में प्रत्येक बिंदु P के लिए { /* डेटाबेस में सभी बिंदुओं को स्कैन करें */
        यदि distFunc(Q, P) ≤ eps तो { /* दूरी की गणना करें और epsilon जांचें */
            एन := एन ∪ {पी} /* परिणाम में जोड़ें */
        }
    }
    वापसी एन
}

सार एल्गोरिथ्म

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

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

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

जटिलता

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

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

फायदे

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

नुकसान

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

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

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

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

न्यूनतम बिंदु: सामान्य नियम के रूप में, न्यूनतम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 और अन्य संबंधित तरीकों का कार्यान्वयन भी शामिल है।
स्किकिट-लर्न में मनमानी मिन्कोव्स्की दूरी के लिए डीबीएससीएएन का पायथन कार्यान्वयन शामिल है, जिसे

[1]

[2]

[3]

[4]

[5]

[6]

[lower-alpha 1]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Anonymous

Search