डीबीएससीएएन: Difference between revisions

Revision as of 12:48, 2 August 2023

शोर के साथ अनुप्रयोगों की घनत्व-आधारित स्थानिक क्लस्टरिंग (डीबीएससीएएन) 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 नियतात्मक है। डीबीएससीएएन*^[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 और अन्य संबंधित तरीकों का कार्यान्वयन भी शामिल है।
स्किकिट-लर्न में मनमानी मिन्कोव्स्की दूरी के लिए डीबीएससीएएन का पायथन कार्यान्वयन शामिल है, जिसे के-डी पेड़ों और बॉल पेड़ों का उपयोग करके त्वरित किया जा सकता है लेकिन जो सबसे खराब स्थिति वाली द्विघात मेमोरी का उपयोग करता है। एक scikit-learn में योगदान HDBSCAN* एल्गोरिदम का कार्यान्वयन प्रदान करता है।
pyclustering लाइब्रेरी में केवल यूक्लिडियन दूरी के साथ-साथ ऑप्टिक्स एल्गोरिदम के लिए DBSCAN का पायथन और C++ कार्यान्वयन शामिल है।
SPMF में केवल यूक्लिडियन दूरी के लिए k-d ट्री समर्थन के साथ DBSCAN एल्गोरिथ्म का कार्यान्वयन शामिल है।
वीका (मशीन लर्निंग) में (नवीनतम संस्करणों में एक वैकल्पिक पैकेज के रूप में) डीबीएससीएएन का एक बुनियादी कार्यान्वयन शामिल है जो द्विघात समय और रैखिक मेमोरी में चलता है।
linfa में रस्ट (प्रोग्रामिंग भाषा) के लिए DBSCAN का कार्यान्वयन शामिल है।

↑ ^1.0 ^1.1 While minPts intuitively is the minimum cluster size, in some cases DBSCAN can produce smaller clusters.^[4] A DBSCAN cluster consists of at least one core point.^[4] As other points may be border points to more than one cluster, there is no guarantee that at least minPts points are included in every cluster.

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (eds.). A density-based algorithm for discovering clusters in large spatial databases with noise (PDF). Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. CiteSeerX 10.1.1.121.9220. ISBN 1-57735-004-9.
↑ "Microsoft Academic Search: Papers". Archived from the original on April 21, 2010. Retrieved 2010-04-18. Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24.
↑ "2014 SIGKDD Test of Time Award". ACM SIGKDD. 2014-08-18. Retrieved 2016-07-27.
↑ ^4.00 ^4.01 ^4.02 ^4.03 ^4.04 ^4.05 ^4.06 ^4.07 ^4.08 ^4.09 ^4.10 ^4.11 Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei (July 2017). "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN". ACM Trans. Database Syst. 42 (3): 19:1–19:21. doi:10.1145/3068335. ISSN 0362-5915. S2CID 5156876.
↑ "टोड्स होम". tods.acm.org (in English). Association for Computing Machinery. Retrieved 2020-07-16.
↑ ^6.0 ^6.1 Ling, R. F. (1972-01-01). "के-क्लस्टर के सिद्धांत और निर्माण पर". The Computer Journal (in English). 15 (4): 326–332. doi:10.1093/comjnl/15.4.326. ISSN 0010-4620.
↑ ^7.0 ^7.1 ^7.2 ^7.3 Sander, Jörg; Ester, Martin; Kriegel, Hans-Peter; Xu, Xiaowei (1998). "Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications". Data Mining and Knowledge Discovery. Berlin: Springer-Verlag. 2 (2): 169–194. doi:10.1023/A:1009745219419. S2CID 445002.
↑ ^8.0 ^8.1 ^8.2 Campello, Ricardo J. G. B.; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg (2015). "डेटा क्लस्टरिंग, विज़ुअलाइज़ेशन और आउटलायर डिटेक्शन के लिए पदानुक्रमित घनत्व अनुमान". ACM Transactions on Knowledge Discovery from Data. 10 (1): 1–51. doi:10.1145/2733381. ISSN 1556-4681. S2CID 2887636.
↑ Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). "घनत्व-आधारित क्लस्टरिंग". WIREs Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30. S2CID 36920706. Archived from the original on 2016-11-17. Retrieved 2011-12-12.
↑ Schubert, Erich; Hess, Sibylle; Morik, Katharina (2018). मैट्रिक्स फैक्टराइजेशन और स्पेक्ट्रल क्लस्टरिंग से डीबीएससीएएन का संबंध (PDF). Lernen, Wissen, Daten, Analysen (LWDA). pp. 330–334 – via CEUR-WS.org.
↑ Sander, Jörg (1998). स्थानिक डेटा खनन के लिए सामान्यीकृत घनत्व-आधारित क्लस्टरिंग. München: Herbert Utz Verlag. ISBN 3-89675-469-6.
↑ Campello, R. J. G. B.; Moulavi, D.; Zimek, A.; Sander, J. (2013). "पदानुक्रमों से समूहों के अर्ध-पर्यवेक्षित और अपर्यवेक्षित इष्टतम निष्कर्षण के लिए एक रूपरेखा". Data Mining and Knowledge Discovery. 27 (3): 344. doi:10.1007/s10618-013-0311-4. S2CID 8144686.
↑ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.

[minpts-7] 1.0 ^1.1 While minPts intuitively is the minimum cluster size, in some cases DBSCAN can produce smaller clusters.^[4] A DBSCAN cluster consists of at least one core point.^[4] As other points may be border points to more than one cluster, there is no guarantee that at least minPts points are included in every cluster.

[dbscan-1] 1.0 ^1.1 ^1.2 Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (eds.). A density-based algorithm for discovering clusters in large spatial databases with noise (PDF). Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. CiteSeerX 10.1.1.121.9220. ISBN 1-57735-004-9.

[2] "Microsoft Academic Search: Papers". Archived from the original on April 21, 2010. Retrieved 2010-04-18. Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24.

[3] "2014 SIGKDD Test of Time Award". ACM SIGKDD. 2014-08-18. Retrieved 2016-07-27.

[tods-4] 4.00 ^4.01 ^4.02 ^4.03 ^4.04 ^4.05 ^4.06 ^4.07 ^4.08 ^4.09 ^4.10 ^4.11 Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei (July 2017). "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN". ACM Trans. Database Syst. 42 (3): 19:1–19:21. doi:10.1145/3068335. ISSN 0362-5915. S2CID 5156876.

[5] "टोड्स होम". tods.acm.org (in English). Association for Computing Machinery. Retrieved 2020-07-16.

[:1-6] 6.0 ^6.1 Ling, R. F. (1972-01-01). "के-क्लस्टर के सिद्धांत और निर्माण पर". The Computer Journal (in English). 15 (4): 326–332. doi:10.1093/comjnl/15.4.326. ISSN 0010-4620.

[:0-8] 7.0 ^7.1 ^7.2 ^7.3 Sander, Jörg; Ester, Martin; Kriegel, Hans-Peter; Xu, Xiaowei (1998). "Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications". Data Mining and Knowledge Discovery. Berlin: Springer-Verlag. 2 (2): 169–194. doi:10.1023/A:1009745219419. S2CID 445002.

[hdbscan1-9] 8.0 ^8.1 ^8.2 Campello, Ricardo J. G. B.; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg (2015). "डेटा क्लस्टरिंग, विज़ुअलाइज़ेशन और आउटलायर डिटेक्शन के लिए पदानुक्रमित घनत्व अनुमान". ACM Transactions on Knowledge Discovery from Data. 10 (1): 1–51. doi:10.1145/2733381. ISSN 1556-4681. S2CID 2887636.

[WIREs-10] Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). "घनत्व-आधारित क्लस्टरिंग". WIREs Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30. S2CID 36920706. Archived from the original on 2016-11-17. Retrieved 2011-12-12.

[11] Schubert, Erich; Hess, Sibylle; Morik, Katharina (2018). मैट्रिक्स फैक्टराइजेशन और स्पेक्ट्रल क्लस्टरिंग से डीबीएससीएएन का संबंध (PDF). Lernen, Wissen, Daten, Analysen (LWDA). pp. 330–334 – via CEUR-WS.org.

[12] Sander, Jörg (1998). स्थानिक डेटा खनन के लिए सामान्यीकृत घनत्व-आधारित क्लस्टरिंग. München: Herbert Utz Verlag. ISBN 3-89675-469-6.

[13] Campello, R. J. G. B.; Moulavi, D.; Zimek, A.; Sander, J. (2013). "पदानुक्रमों से समूहों के अर्ध-पर्यवेक्षित और अपर्यवेक्षित इष्टतम निष्कर्षण के लिए एक रूपरेखा". Data Mining and Knowledge Discovery. 27 (3): 344. doi:10.1007/s10618-013-0311-4. S2CID 8144686.

[14] Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.

[1]

[2]

[3]

[4]

[5]

[6]

[lower-alpha 1]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Line 41: / Line 41: @@
 === मूल क्वेरी-आधारित एल्गोरिदम ===
-DBSCAN को दो मापदंडों की आवश्यकता होती है: ε (ईपीएस) और सघन क्षेत्र बनाने के लिए आवश्यक न्यूनतम अंक{{efn|name=minpts|While {{not a typo|minPts}} intuitively is the minimum cluster size, in some cases DBSCAN ''can'' produce smaller clusters.<ref name="tods" /> A DBSCAN cluster consists of at least ''one core point''.<ref name="tods" /> As other points may be border points to more than one cluster, there is no guarantee that at least {{not a typo|minPts}} points are included in every cluster.}} ({{not a typo|minPts}}). यह एक मनमाने प्रारंभिक बिंदु से शुरू होता है जिस पर कभी दौरा नहीं किया गया है। इस बिंदु का ε-पड़ोस पुनः प्राप्त किया जाता है, और यदि इसमें पर्याप्त रूप से कई बिंदु हैं, तो एक क्लस्टर शुरू किया जाता है। अन्यथा, बिंदु को शोर के रूप में लेबल किया जाता है। ध्यान दें कि यह बिंदु बाद में किसी भिन्न बिंदु के पर्याप्त आकार के ε-वातावरण में पाया जा सकता है और इसलिए इसे क्लस्टर का हिस्सा बनाया जा सकता है।
+DBSCAN को दो मापदंडों: ε (eps) और सघन क्षेत्र बनाने के लिए आवश्यक न्यूनतम अंक{{efn|name=minpts|While {{not a typo|minPts}} intuitively is the minimum cluster size, in some cases DBSCAN ''can'' produce smaller clusters.<ref name="tods" /> A DBSCAN cluster consists of at least ''one core point''.<ref name="tods" /> As other points may be border points to more than one cluster, there is no guarantee that at least {{not a typo|minPts}} points are included in every cluster.}} ({{not a typo|minPts}}) की आवश्यकता होती है। यह यादृच्छिक प्रारंभिक बिंदु के साथ प्रारंभ होता है जिसे देखा नहीं गया है। इस बिंदु का ε-लघु भाग पुनः प्राप्त किया जाता है, और यदि इसमें पर्याप्त रूप से कई बिंदु हैं, तो एक क्लस्टर प्रारंभ किया जाता है। अन्यथा, बिंदु को शोर के रूप में लेबल किया जाता है। ध्यान दें कि यह बिंदु बाद में किसी भिन्न बिंदु के पर्याप्त आकार के ε-वातावरण में पाया जा सकता है और इसलिए इसे क्लस्टर का हिस्सा बनाया जा सकता है।
-यदि कोई बिंदु किसी क्लस्टर का सघन भाग पाया जाता है, तो उसका ε-पड़ोस भी उस क्लस्टर का हिस्सा होता है। इसलिए, ε-पड़ोस के भीतर पाए जाने वाले सभी बिंदुओं को जोड़ा जाता है, जैसा कि उनके अपने ε-पड़ोस में होता है जब वे भी घने होते हैं। यह प्रक्रिया तब तक जारी रहती है जब तक घनत्व से जुड़ा क्लस्टर पूरी तरह से नहीं मिल जाता। फिर, एक नए अनदेखे बिंदु को पुनः प्राप्त किया जाता है और संसाधित किया जाता है, जिससे आगे क्लस्टर या शोर की खोज होती है।
+यदि कोई बिंदु किसी क्लस्टर का सघन भाग पाया जाता है, तो उसका ε-लघु भाग भी उस क्लस्टर का हिस्सा होता है। इसलिए, ε-लघु भाग के भीतर पाए जाने वाले सभी बिंदुओं को जोड़ा जाता है, जैसा कि उनके अपने ε-लघु भाग में होता है जब वे भी घने होते हैं। यह प्रक्रिया तब तक जारी रहती है जब तक घनत्व से जुड़ा क्लस्टर पूरी तरह से नहीं मिल जाता। फिर, एक नए अनदेखे बिंदु को पुनः प्राप्त किया जाता है और संसाधित किया जाता है, जिससे आगे क्लस्टर या शोर की खोज होती है।
-DBSCAN का उपयोग किसी भी दूरी फ़ंक्शन के साथ किया जा सकता है<ref name="dbscan" /><ref name="tods" />(साथ ही समानता कार्य या अन्य विधेय)।<ref name=":0" />इसलिए दूरी फ़ंक्शन (dist) को एक अतिरिक्त पैरामीटर के रूप में देखा जा सकता है।
+DBSCAN का उपयोग किसी भी दूरी फलन के साथ किया जा सकता है<ref name="dbscan" /><ref name="tods" />(साथ ही समानता कार्य या अन्य विधेय)।<ref name=":0" /> इसलिए दूरी फलन (dist) को एक अतिरिक्त पैरामीटर के रूप में देखा जा सकता है।
-एल्गोरिथ्म को [[छद्मकोड]] में इस प्रकार व्यक्त किया जा सकता है:<ref name="tods" />
+एल्गोरिथ्म को [[छद्मकोड|स्यूडोकोड]] में इस प्रकार व्यक्त किया जा सकता है:<ref name="tods" />
       DBSCAN(DB, distFunc, eps, minPts) {
@@ Line 84: / Line 84: @@
   }
-=== सार एल्गोरिथ्म ===
+=== अमूर्त एल्गोरिथ्म ===
 DBSCAN एल्गोरिथ्म को निम्नलिखित चरणों में संक्षेपित किया जा सकता है:<ref name="tods" />
-# प्रत्येक बिंदु के ε (ईपीएस) पड़ोस में बिंदु ढूंढें, और इससे अधिक वाले मुख्य बिंदुओं की पहचान करें {{not a typo|minPts}} पड़ोसियों।
+# प्रत्येक बिंदु के ε (eps) लघु भाग में बिंदु ढूंढें, और इससे अधिक वाले मुख्य बिंदुओं {{not a typo|minPts}} लघु भागियों की पहचान करें।
-# सभी गैर-कोर बिंदुओं को अनदेखा करते हुए, पड़ोसी ग्राफ़ पर मुख्य बिंदुओं के [[कनेक्टेड घटक (ग्राफ़ सिद्धांत)]] को ढूंढें।
+# सभी गैर-कोर बिंदुओं को अनदेखा करते हुए, लघु भागी ग्राफ़ पर मुख्य बिंदुओं के [[कनेक्टेड घटक (ग्राफ़ सिद्धांत)]] को ढूंढें।
-# यदि क्लस्टर एक ε (ईपीएस) पड़ोसी है, तो प्रत्येक गैर-कोर बिंदु को पास के क्लस्टर में निर्दिष्ट करें, अन्यथा इसे शोर के लिए निर्दिष्ट करें।
+# यदि क्लस्टर एक ε (eps) लघु भागी है, तो प्रत्येक गैर-कोर बिंदु को पास के क्लस्टर में निर्दिष्ट करें, अन्यथा इसे शोर के लिए निर्दिष्ट करें।
-इसके सरल कार्यान्वयन के लिए चरण 1 में पड़ोस को संग्रहीत करने की आवश्यकता होती है, इस प्रकार पर्याप्त मेमोरी की आवश्यकता होती है। मूल DBSCAN एल्गोरिदम को एक समय में एक बिंदु के लिए इन चरणों को निष्पादित करने की आवश्यकता नहीं होती है।
+इसके सरल कार्यान्वयन के लिए चरण 1 में लघु भाग को संग्रहीत करने की आवश्यकता होती है, इस प्रकार पर्याप्त मेमोरी की आवश्यकता होती है। मूल DBSCAN एल्गोरिदम को एक समय में एक बिंदु के लिए इन चरणों को निष्पादित करने की आवश्यकता नहीं होती है।
 ==जटिलता==
-DBSCAN डेटाबेस के प्रत्येक बिंदु पर संभवतः कई बार जाता है (उदाहरण के लिए, विभिन्न समूहों के उम्मीदवारों के रूप में)। हालाँकि, व्यावहारिक विचारों के लिए, समय जटिलता अधिकतर क्षेत्रक्वेरी सामान्यंत्रणों की संख्या से नियंत्रित होती है। DBSCAN प्रत्येक बिंदु के लिए ऐसी ही एक क्वेरी निष्पादित करता है, और यदि एक [[स्थानिक सूचकांक]] का उपयोग किया जाता है जो पड़ोसियों के पास एक निश्चित-त्रिज्या निष्पादित करता है {{math|O(log ''n'')}}, की समग्र औसत रनटाइम जटिलता {{math|O(''n'' log ''n'')}} प्राप्त होता है (यदि पैरामीटर {{math|ε}} को सार्थक तरीके से चुना जाता है, यानी कि केवल औसतन {{math|O(log ''n'')}} अंक लौटाए जाते हैं)। त्वरित सूचकांक संरचना के उपयोग के बिना, या विकृत डेटा पर (जैसे कि से कम दूरी के सभी बिंदु) {{math|ε}}), सबसे खराब स्थिति में रन टाइम जटिलता बनी रहती है {{math|O(''n''²)}}. <math>\textstyle\binom n2</math> ज> {{math|- ''n''}} = {{math|(''n''²-''n'')/2}दूरी मैट्रिक्स के }-आकार के ऊपरी त्रिकोण को दूरी पुनर्गणना से बचने के लिए भौतिक बनाया जा सकता है, लेकिन इसकी आवश्यकता है {{math|O(''n''²)}} मेमोरी, जबकि DBSCAN के गैर-मैट्रिक्स आधारित कार्यान्वयन के लिए केवल आवश्यकता होती है {{math|O(''n'')}} याद।
+DBSCAN डेटाबेस के प्रत्येक बिंदु पर संभवतः कई बार जाता है (उदाहरण के लिए, विभिन्न समूहों के उम्मीदवारों के रूप में)। यद्यपि, व्यावहारिक विचारों के लिए, समय जटिलता अधिकतर क्षेत्रक्वेरी सामान्यंत्रणों की संख्या से नियंत्रित होती है। DBSCAN प्रत्येक बिंदु के लिए ऐसी ही एक क्वेरी निष्पादित करता है, और यदि एक [[स्थानिक सूचकांक]] का उपयोग किया जाता है जो लघु भागियों के पास एक निश्चित-त्रिज्या निष्पादित करता है {{math|O(log ''n'')}}, की समग्र औसत रनटाइम जटिलता {{math|O(''n'' log ''n'')}} प्राप्त होता है (यदि पैरामीटर {{math|ε}} को सार्थक तरीके से चुना जाता है, यानी कि केवल औसतन {{math|O(log ''n'')}} अंक लौटाए जाते हैं)। त्वरित सूचकांक संरचना के उपयोग के बिना, या विकृत डेटा पर (जैसे कि से कम दूरी के सभी बिंदु) {{math|ε}}), सबसे खराब स्थिति में रन टाइम जटिलता  {{math|O(''n''²)}} बनी रहती है। <math>\textstyle\binom n2</math>- ''n'' = (''n''²-''n'')/2 दूरी मैट्रिक्स के आकार के ऊपरी त्रिकोण को दूरी पुनर्गणना से बचने के लिए सामग्रीकृत किया जा सकता है, लेकिन इसके लिए {{math|O(''n''²)}} मेमोरी की आवश्यकता है, जबकि DBSCAN के गैर-मैट्रिक्स आधारित कार्यान्वयन के लिए केवल {{math|O(''n'')}} मेमोरी आवश्यकता होती है।
 [[File:DBSCAN-density-data.svg|thumb|DBSCAN गैर-रैखिक रूप से अलग करने योग्य क्लस्टर ढूंढ सकता है। इस डेटासेट को k-मीन्स या गॉसियन मिक्सचर EM क्लस्टरिंग के साथ पर्याप्त रूप से क्लस्टर नहीं किया जा सकता है।]]
@@ Line 101: / Line 101: @@
 ==फायदे==
-# DBSCAN को [[K-मतलब एल्गोरिदम]]|k-मीन्स के विपरीत, डेटा में क्लस्टर की संख्या को प्राथमिकता से निर्दिष्ट करने की आवश्यकता नहीं होती है।
+# DBSCAN को  [[K-मतलब एल्गोरिदम|k-means]] के विपरीत, डेटा में क्लस्टर की संख्या को प्राथमिकता से निर्दिष्ट करने की आवश्यकता नहीं होती है।
-# DBSCAN मनमाने आकार के क्लस्टर ढूंढ सकता है। यह एक ऐसे क्लस्टर को भी ढूंढ सकता है जो पूरी तरह से एक अलग क्लस्टर से घिरा हुआ है (लेकिन उससे जुड़ा नहीं है)। MinPts पैरामीटर के कारण, तथाकथित सिंगल-लिंक प्रभाव (विभिन्न समूहों को बिंदुओं की एक पतली रेखा से जोड़ा जाना) कम हो जाता है।
+# DBSCAN याट्टीच्छक आकार के क्लस्टर ढूंढ सकता है। यह एक ऐसे क्लस्टर को भी ढूंढ सकता है जो पूरी तरह से एक अलग क्लस्टर से घिरा हुआ है (लेकिन उससे जुड़ा नहीं है)। MinPts पैरामीटर के कारण, तथाकथित एकल-लिंक प्रभाव (विभिन्न समूहों को बिंदुओं की एक पतली रेखा से जोड़ा जाना) कम हो जाता है।
 # DBSCAN में शोर की अवधारणा है, और यह विसंगति का पता लगाने में सक्षम है।
-# DBSCAN को केवल दो मापदंडों की आवश्यकता होती है और यह डेटाबेस में बिंदुओं के क्रम के प्रति अधिकतर असंवेदनशील होता है। (हालाँकि, यदि बिंदुओं का क्रम बदल जाता है, तो दो अलग-अलग समूहों के किनारे पर बैठे बिंदु क्लस्टर सदस्यता को स्वैप कर सकते हैं, और क्लस्टर असाइनमेंट केवल समरूपता तक अद्वितीय है।)
+# DBSCAN को केवल दो मापदंडों की आवश्यकता होती है और यह डेटाबेस में बिंदुओं के क्रम के प्रति अधिकतर असंवेदनशील होता है। (यद्यपि, यदि बिंदुओं का क्रम बदल जाता है, तो दो अलग-अलग समूहों के किनारे पर बैठे बिंदु क्लस्टर सदस्यता को स्वैप कर सकते हैं, और क्लस्टर असाइनमेंट केवल समरूपता तक अद्वितीय है।)
-# DBSCAN को ऐसे डेटाबेस के साथ उपयोग के लिए डिज़ाइन किया गया है जो क्षेत्र के प्रश्नों को तेज़ कर सकता है, उदाहरण के लिए R* वृक्ष का उपयोग करना।
+# DBSCAN को ऐसे डेटाबेस के साथ उपयोग के लिए डिज़ाइन किया गया है जो क्षेत्र के प्रश्नों को तेज़ कर सकता है, उदाहरण के लिए R* रेखा का उपयोग करना है।
 # पैरामीटर {{not a typo|minPts}} और ε को एक डोमेन विशेषज्ञ द्वारा सेट किया जा सकता है, यदि डेटा अच्छी तरह से समझा गया हो।
 ==नुकसान==
 # DBSCAN पूरी तरह से नियतात्मक नहीं है: सीमा बिंदु जो एक से अधिक क्लस्टर से पहुंच योग्य हैं, डेटा संसाधित होने के क्रम के आधार पर किसी भी क्लस्टर का हिस्सा हो सकते हैं। अधिकांश डेटा सेट और डोमेन के लिए, यह स्थिति अक्सर उत्पन्न नहीं होती है और क्लस्टरिंग परिणाम पर इसका बहुत कम प्रभाव पड़ता है:<ref name="tods">{{Cite journal|last1=Schubert|first1=Erich|last2=Sander|first2=Jörg|last3=Ester|first3=Martin|last4=Kriegel|first4=Hans Peter|author-link4=Hans-Peter Kriegel|last5=Xu|first5=Xiaowei|date=July 2017|title=DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN|url=https://www.vitavonni.de/research/acm.html#item3068335|journal=ACM Trans. Database Syst.|volume=42|issue=3|pages=19:1–19:21|doi=10.1145/3068335|s2cid=5156876|issn=0362-5915}}</ref> मुख्य बिंदुओं और शोर बिंदुओं दोनों पर, DBSCAN नियतात्मक है। डीबीएससीएएन*<ref name="hdbscan1" />एक भिन्नता है जो सीमा बिंदुओं को शोर के रूप में मानती है, और इस तरह पूरी तरह से नियतात्मक परिणाम के साथ-साथ घनत्व से जुड़े घटकों की अधिक सुसंगत सांख्यिकीय व्याख्या प्राप्त करती है।
-# DBSCAN की गुणवत्ता रीजनक्वेरी(P,ε) फ़ंक्शन में प्रयुक्त मीट्रिक (गणित) पर निर्भर करती है। उपयोग की जाने वाली सबसे सामान्य दूरी मीट्रिक [[यूक्लिडियन दूरी]] है। विशेष रूप से उच्च-आयामी डेटा | उच्च-आयामी डेटा को क्लस्टर करने के लिए, इस मीट्रिक को तथाकथित आयामीता #दूरी कार्यों के अभिशाप के कारण लगभग बेकार बना दिया जा सकता है, जिससे ε के लिए उचित मान ढूंढना मुश्किल हो जाता है। हालाँकि, यह प्रभाव यूक्लिडियन दूरी पर आधारित किसी अन्य एल्गोरिदम में भी मौजूद है।
+# DBSCAN की गुणवत्ता रीजनक्वेरी(P,ε) फलन में प्रयुक्त मीट्रिक (गणित) पर निर्भर करती है। उपयोग की जाने वाली सबसे सामान्य दूरी मीट्रिक [[यूक्लिडियन दूरी]] है। विशेष रूप से उच्च-आयामी डेटा | उच्च-आयामी डेटा को क्लस्टर करने के लिए, इस मीट्रिक को तथाकथित आयामीता #दूरी कार्यों के अभिशाप के कारण लगभग बेकार बना दिया जा सकता है, जिससे ε के लिए उचित मान ढूंढना मुश्किल हो जाता है। यद्यपि, यह प्रभाव यूक्लिडियन दूरी पर आधारित किसी अन्य एल्गोरिदम में भी मौजूद है।
 # DBSCAN घनत्व में बड़े अंतर के साथ डेटा सेट को अच्छी तरह से क्लस्टर नहीं कर सकता, क्योंकि {{not a typo|minPts}}-ε संयोजन को सभी समूहों के लिए उचित रूप से नहीं चुना जा सकता है।<ref name="WIREs">{{Cite journal | author1-link = Hans-Peter Kriegel | first1 = Hans-Peter | last1 = Kriegel | first2 = Peer | last2 = Kröger | author3-first = Jörg | author3-last = Sander | author4-first = Arthur | author4-last = Zimek | author-link4 = Arthur Zimek | title = घनत्व-आधारित क्लस्टरिंग| journal = WIREs Data Mining and Knowledge Discovery | volume = 1 | issue = 3 | year = 2011 | pages = 231–240 | url = http://wires.wiley.com/WileyCDA/WiresArticle/wisId-WIDM30.html | doi = 10.1002/widm.30 | s2cid = 36920706 | access-date = 2011-12-12 | archive-date = 2016-11-17 | archive-url = https://web.archive.org/web/20161117070919/http://wires.wiley.com/WileyCDA/WiresArticle/wisId-WIDM30.html | url-status = dead }}</ref>
 # यदि डेटा और स्केल को अच्छी तरह से नहीं समझा गया है, तो एक सार्थक दूरी सीमा ε चुनना मुश्किल हो सकता है।
@@ Line 120: / Line 120: @@
 प्रत्येक डेटा माइनिंग कार्य में मापदंडों की समस्या होती है। प्रत्येक पैरामीटर विशिष्ट तरीकों से एल्गोरिदम को प्रभावित करता है। DBSCAN के लिए, पैरामीटर ε और{{not a typo|minPts}} जरूरत है। पैरामीटर उपयोगकर्ता द्वारा निर्दिष्ट किए जाने चाहिए. आदर्श रूप से, ε का मान हल की जाने वाली समस्या (उदाहरण के लिए भौतिक दूरी) द्वारा दिया जाता है, और{{not a typo|minPts}} तो वांछित न्यूनतम क्लस्टर आकार है।{{efn|name=minpts}}
-* न्यूनतम बिंदु: सामान्य नियम के रूप में, न्यूनतम{{not a typo|minPts}} को डेटा सेट में आयाम डी की संख्या से प्राप्त किया जा सकता है{{not a typo|minPts}} ≥ D + 1. का निम्न मान{{not a typo|minPts}} = 1 का कोई मतलब नहीं है, क्योंकि परिभाषा के अनुसार प्रत्येक बिंदु एक मुख्य बिंदु है। साथ{{not a typo|minPts}} ≤ 2, परिणाम एकल लिंक मीट्रिक के साथ [[पदानुक्रमित क्लस्टरिंग]] के समान होगा, ऊंचाई ε पर डेंड्रोग्राम कट के साथ। इसलिए,{{not a typo|minPts}} को कम से कम 3 चुना जाना चाहिए। हालाँकि, बड़े मान सामान्यतौर पर शोर वाले डेटा सेट के लिए बेहतर होते हैं और इससे अधिक महत्वपूर्ण क्लस्टर प्राप्त होंगे। अंगूठे के नियम के रूप में,{{not a typo|minPts}} = 2·मंद का उपयोग किया जा सकता है,<ref name=":0" />लेकिन बहुत बड़े डेटा के लिए, शोर वाले डेटा के लिए या कई डुप्लिकेट वाले डेटा के लिए बड़े मान चुनना आवश्यक हो सकता है।<ref name="tods" />* ε: ε के लिए मान को [[निकटतम पड़ोसी ग्राफ]]|k-दूरी ग्राफ का उपयोग करके चुना जा सकता है, जो कि k = की दूरी को प्लॉट करता है।{{not a typo|minPts}}-1 निकटतम पड़ोसी को सबसे बड़े से सबसे छोटे मूल्य तक ऑर्डर किया गया।<ref name="tods" />ε के अच्छे मान वे हैं जहां यह प्लॉट कोहनी दिखाता है:<ref name="dbscan" /><ref name=":0" /><ref name="tods" />यदि ε को बहुत छोटा चुना जाता है, तो डेटा का एक बड़ा हिस्सा क्लस्टर नहीं किया जाएगा; जबकि ε के बहुत अधिक मान के लिए, क्लस्टर विलीन हो जाएंगे और अधिकांश ऑब्जेक्ट एक ही क्लस्टर में होंगे। सामान्य तौर पर, ε के छोटे मान बेहतर होते हैं,<ref name="tods" />और सामान्य नियम के अनुसार बिंदुओं का केवल एक छोटा सा अंश ही एक दूसरे से इस दूरी के भीतर होना चाहिए। वैकल्पिक रूप से, ε को चुनने के लिए एक [[प्रकाशिकी एल्गोरिथ्म]] प्लॉट का उपयोग किया जा सकता है,<ref name="tods" />लेकिन फिर ऑप्टिक्स एल्गोरिदम का उपयोग डेटा को क्लस्टर करने के लिए किया जा सकता है।
+* न्यूनतम बिंदु: सामान्य नियम के रूप में, न्यूनतम{{not a typo|minPts}} को डेटा सेट में आयाम डी की संख्या से प्राप्त किया जा सकता है{{not a typo|minPts}} ≥ D + 1. का निम्न मान{{not a typo|minPts}} = 1 का कोई मतलब नहीं है, क्योंकि परिभाषा के अनुसार प्रत्येक बिंदु एक मुख्य बिंदु है। साथ{{not a typo|minPts}} ≤ 2, परिणाम एकल लिंक मीट्रिक के साथ [[पदानुक्रमित क्लस्टरिंग]] के समान होगा, ऊंचाई ε पर डेंड्रोग्राम कट के साथ। इसलिए,{{not a typo|minPts}} को कम से कम 3 चुना जाना चाहिए। यद्यपि, बड़े मान सामान्यतौर पर शोर वाले डेटा सेट के लिए बेहतर होते हैं और इससे अधिक महत्वपूर्ण क्लस्टर प्राप्त होंगे। अंगूठे के नियम के रूप में,{{not a typo|minPts}} = 2·मंद का उपयोग किया जा सकता है,<ref name=":0" />लेकिन बहुत बड़े डेटा के लिए, शोर वाले डेटा के लिए या कई डुप्लिकेट वाले डेटा के लिए बड़े मान चुनना आवश्यक हो सकता है।<ref name="tods" />* ε: ε के लिए मान को [[निकटतम पड़ोसी ग्राफ|निकटतम लघु भागी ग्राफ]]|k-दूरी ग्राफ का उपयोग करके चुना जा सकता है, जो कि k = की दूरी को प्लॉट करता है।{{not a typo|minPts}}-1 निकटतम लघु भागी को सबसे बड़े से सबसे छोटे मूल्य तक ऑर्डर किया गया।<ref name="tods" />ε के अच्छे मान वे हैं जहां यह प्लॉट कोहनी दिखाता है:<ref name="dbscan" /><ref name=":0" /><ref name="tods" />यदि ε को बहुत छोटा चुना जाता है, तो डेटा का एक बड़ा हिस्सा क्लस्टर नहीं किया जाएगा; जबकि ε के बहुत अधिक मान के लिए, क्लस्टर विलीन हो जाएंगे और अधिकांश ऑब्जेक्ट एक ही क्लस्टर में होंगे। सामान्य तौर पर, ε के छोटे मान बेहतर होते हैं,<ref name="tods" />और सामान्य नियम के अनुसार बिंदुओं का केवल एक छोटा सा अंश ही एक दूसरे से इस दूरी के भीतर होना चाहिए। वैकल्पिक रूप से, ε को चुनने के लिए एक [[प्रकाशिकी एल्गोरिथ्म]] प्लॉट का उपयोग किया जा सकता है,<ref name="tods" />लेकिन फिर ऑप्टिक्स एल्गोरिदम का उपयोग डेटा को क्लस्टर करने के लिए किया जा सकता है।
-* दूरी फ़ंक्शन: दूरी फ़ंक्शन का चुनाव ε की पसंद के साथ मजबूती से जुड़ा हुआ है, और परिणामों पर इसका बड़ा प्रभाव पड़ता है। सामान्य तौर पर, पैरामीटर ε को चुनने से पहले, डेटा सेट के लिए समानता के उचित माप की पहचान करना आवश्यक होगा। इस पैरामीटर के लिए कोई अनुमान नहीं है, लेकिन डेटा सेट के लिए दूरी फ़ंक्शन को उचित रूप से चुना जाना चाहिए। उदाहरण के लिए, भौगोलिक डेटा पर, ग्रेट-सर्कल दूरी अक्सर एक अच्छा विकल्प होती है।
+* दूरी फलन: दूरी फलन का चुनाव ε की पसंद के साथ मजबूती से जुड़ा हुआ है, और परिणामों पर इसका बड़ा प्रभाव पड़ता है। सामान्य तौर पर, पैरामीटर ε को चुनने से पहले, डेटा सेट के लिए समानता के उचित माप की पहचान करना आवश्यक होगा। इस पैरामीटर के लिए कोई अनुमान नहीं है, लेकिन डेटा सेट के लिए दूरी फलन को उचित रूप से चुना जाना चाहिए। उदाहरण के लिए, भौगोलिक डेटा पर, ग्रेट-सर्कल दूरी अक्सर एक अच्छा विकल्प होती है।
 ऑप्टिक्स एल्गोरिदम को DBSCAN के सामान्यीकरण के रूप में देखा जा सकता है जो ε पैरामीटर को अधिकतम मान से बदल देता है जो ज्यादातर प्रदर्शन को प्रभावित करता है। MinPts तब अनिवार्य रूप से खोजने के लिए न्यूनतम क्लस्टर आकार बन जाता है। जबकि एल्गोरिथ्म को DBSCAN की तुलना में पैरामीटराइज़ करना बहुत आसान है, परिणामों का उपयोग करना थोड़ा अधिक कठिन है, क्योंकि यह सामान्यतौर पर DBSCAN द्वारा उत्पादित सरल डेटा विभाजन के बजाय एक पदानुक्रमित क्लस्टरिंग उत्पन्न करेगा।
@@ Line 128: / Line 128: @@
 == [[वर्णक्रमीय क्लस्टरिंग]] से संबंध ==
-डीबीएससीएएन का वर्णक्रमीय कार्यान्वयन कनेक्टेड घटक (ग्राफ सिद्धांत) के निर्धारण के तुच्छ मामले में वर्णक्रमीय क्लस्टरिंग से संबंधित है - बिना किनारों के कटे हुए इष्टतम क्लस्टर।<ref>{{Cite conference|last1=Schubert|first1=Erich|last2=Hess|first2=Sibylle|last3=Morik|first3=Katharina|date=2018|title=मैट्रिक्स फैक्टराइजेशन और स्पेक्ट्रल क्लस्टरिंग से डीबीएससीएएन का संबंध|url=http://ceur-ws.org/Vol-2191/paper38.pdf|conference=Lernen, Wissen, Daten, Analysen (LWDA)|pages=330–334|via=CEUR-WS.org}}</ref> हालाँकि, यह कम्प्यूटेशनल रूप से गहन हो सकता है <math>O(n^3)</math>. इसके अतिरिक्त, किसी को गणना करने के लिए eigenvectors की संख्या चुननी होगी। प्रदर्शन कारणों से, मूल DBSCAN एल्गोरिथ्म इसके वर्णक्रमीय कार्यान्वयन के लिए बेहतर है।
+डीबीएससीएएन का वर्णक्रमीय कार्यान्वयन कनेक्टेड घटक (ग्राफ सिद्धांत) के निर्धारण के तुच्छ मामले में वर्णक्रमीय क्लस्टरिंग से संबंधित है - बिना किनारों के कटे हुए इष्टतम क्लस्टर।<ref>{{Cite conference|last1=Schubert|first1=Erich|last2=Hess|first2=Sibylle|last3=Morik|first3=Katharina|date=2018|title=मैट्रिक्स फैक्टराइजेशन और स्पेक्ट्रल क्लस्टरिंग से डीबीएससीएएन का संबंध|url=http://ceur-ws.org/Vol-2191/paper38.pdf|conference=Lernen, Wissen, Daten, Analysen (LWDA)|pages=330–334|via=CEUR-WS.org}}</ref> यद्यपि, यह कम्प्यूटेशनल रूप से गहन हो सकता है <math>O(n^3)</math>. इसके अतिरिक्त, किसी को गणना करने के लिए eigenvectors की संख्या चुननी होगी। प्रदर्शन कारणों से, मूल DBSCAN एल्गोरिथ्म इसके वर्णक्रमीय कार्यान्वयन के लिए बेहतर है।
 ==एक्सटेंशन==
@@ Line 147: / Line 147: @@
   | issue = 2
 | s2cid = 445002
-  }}</ref><ref>{{Cite book | first = Jörg | last = Sander | title = स्थानिक डेटा खनन के लिए सामान्यीकृत घनत्व-आधारित क्लस्टरिंग| isbn=3-89675-469-6 | year=1998 | place = München | publisher = Herbert Utz Verlag }}</ref> उन्हीं लेखकों द्वारा मनमाने पड़ोस और सघन विधेय का सामान्यीकरण है। ε और{{not a typo|minPts}} पैरामीटर को मूल एल्गोरिदम से हटा दिया जाता है और विधेय में ले जाया जाता है। उदाहरण के लिए, बहुभुज डेटा पर, पड़ोस कोई भी प्रतिच्छेदी बहुभुज हो सकता है, जबकि घनत्व विधेय केवल वस्तु गणना के बजाय बहुभुज क्षेत्रों का उपयोग करता है।
+  }}</ref><ref>{{Cite book | first = Jörg | last = Sander | title = स्थानिक डेटा खनन के लिए सामान्यीकृत घनत्व-आधारित क्लस्टरिंग| isbn=3-89675-469-6 | year=1998 | place = München | publisher = Herbert Utz Verlag }}</ref> उन्हीं लेखकों द्वारा मनमाने लघु भाग और सघन विधेय का सामान्यीकरण है। ε और{{not a typo|minPts}} पैरामीटर को मूल एल्गोरिदम से हटा दिया जाता है और विधेय में ले जाया जाता है। उदाहरण के लिए, बहुभुज डेटा पर, लघु भाग कोई भी प्रतिच्छेदी बहुभुज हो सकता है, जबकि घनत्व विधेय केवल वस्तु गणना के बजाय बहुभुज क्षेत्रों का उपयोग करता है।
 DBSCAN एल्गोरिथ्म के विभिन्न विस्तार प्रस्तावित किए गए हैं, जिनमें समानांतरीकरण, पैरामीटर अनुमान और अनिश्चित डेटा के लिए समर्थन के तरीके शामिल हैं। मूल विचार को ऑप्टिक्स एल्गोरिदम द्वारा पदानुक्रमित क्लस्टरिंग तक बढ़ा दिया गया है। DBSCAN का उपयोग PreDeCon और [[SUBCLU]] जैसे सबस्पेस क्लस्टरिंग एल्गोरिदम के हिस्से के रूप में भी किया जाता है। एचडीबीएसकैन<ref name="hdbscan1" />डीबीएससीएएन का एक पदानुक्रमित संस्करण है जो ऑप्टिक्स से भी तेज़ है, जिसमें से सबसे प्रमुख समूहों से युक्त एक फ्लैट विभाजन को पदानुक्रम से निकाला जा सकता है।<ref>{{Cite journal | last1 = Campello | first1 = R. J. G. B. | last2 = Moulavi | first2 = D. | last3 = Zimek | first3 = A. |author-link3 = Arthur Zimek | last4 = Sander | first4 = J. | title = पदानुक्रमों से समूहों के अर्ध-पर्यवेक्षित और अपर्यवेक्षित इष्टतम निष्कर्षण के लिए एक रूपरेखा| doi = 10.1007/s10618-013-0311-4 | journal = Data Mining and Knowledge Discovery | volume = 27 | issue = 3 | pages = 344 | year = 2013 | s2cid = 8144686 }}</ref>

Anonymous

Search

डीबीएससीएएन: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:48, 2 August 2023

Contents

इतिहास

प्रारंभिक

एल्गोरिदम

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

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

जटिलता

फायदे

नुकसान

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

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

एक्सटेंशन

उपलब्धता

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डीबीएससीएएन: Difference between revisions

Revision as of 12:48, 2 August 2023

इतिहास

प्रारंभिक

एल्गोरिदम

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

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

जटिलता

फायदे

नुकसान

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

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

एक्सटेंशन

उपलब्धता

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories