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

Revision as of 13:05, 3 August 2023

शोर के साथ अनुप्रयोगों की घनत्व-आधारित स्थानिक क्लस्टरिंग (DBSCAN) 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$ एक मुख्य बिंदु है, फिर यह उन सभी बिंदुओं (कोर या गैर-कोर) के साथ मिलकर एक क्लस्टर बनाता है जो इससे पहुंच योग्य हैं। प्रत्येक क्लस्टर में कम से कम एक मुख्य बिंदु होता है; गैर-कोर बिंदु क्लस्टर का हिस्सा हो सकते हैं, लेकिन वे इसका किनारा बनाते हैं, क्योंकि उनका उपयोग अधिक बिंदुओं तक पहुंचने के लिए नहीं किया जा सकता है।

File:DBSCAN-Illustration.svg

इस आरेख में,

minPts = 4

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

ε

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

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

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

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

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

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

एक्सटेंशन

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

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

उपलब्धता

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

अपाचे कॉमन्स Math में द्विघात समय में चलने वाले एल्गोरिदम का जावा कार्यान्वयन सम्मिलित है।
ELKI DBSCAN के साथ-साथ GDBSCAN और अन्य वेरिएंट का कार्यान्वयन प्रदान करता है। यह कार्यान्वयन उप-द्विघात रनटाइम के लिए विभिन्न सूचकांक संरचनाओं का उपयोग कर सकता है और यादृच्छिक दूरी के कार्यों और यादृच्छिक डेटा प्रकारों का समर्थन करता है, लेकिन यह छोटे डेटा सेट पर निम्न-स्तरीय अनुकूलित (और विशेष) कार्यान्वयन द्वारा बेहतर प्रदर्शन कर सकता है।
MATLAB ने R2019a जारी होने के बाद से अपने सांख्यिकी और मशीन लर्निंग टूलबॉक्स में DBSCAN का कार्यान्वयन सम्मिलित किया है।
mlpack में डुअल-ट्री रेंज सर्च तकनीकों के साथ त्वरित DBSCAN का कार्यान्वयन सम्मिलित है।
PostGIS में ST_ClusterDBSCAN सम्मिलित है - DBSCAN का 2D कार्यान्वयन जो R-ट्री इंडेक्स का उपयोग करता है। कोई भी ज्यामिति प्रकार समर्थित है, उदा. प्वाइंट, लाइनस्ट्रिंग, बहुभुज, आदि।
आर (प्रोग्रामिंग भाषा) में पैकेज dbscan और fpc में DBSCAN का कार्यान्वयन सम्मिलित है। दोनों पैकेज दूरी मैट्रिक्स के माध्यम से यादृच्छिक ढंग से दूरी के कार्यों का समर्थन करते हैं। पैकेज एफपीसी में इंडेक्स समर्थन नहीं है (और इस प्रकार इसमें द्विघात रनटाइम और मेमोरी जटिलता है) और आर दुभाषिया के कारण यह धीमा है। पैकेज dbscan k-d trees (केवल यूक्लिडियन दूरी के लिए) का उपयोग करके तेज़ C++ कार्यान्वयन प्रदान करता है और इसमें DBSCAN*, HDBSCAN*, OPTICS, OPTICSXi और अन्य संबंधित तरीकों का कार्यान्वयन भी सम्मिलित है।
स्किकिट-लर्न में यादृच्छिक मिन्कोव्स्की दूरी के लिए DBSCAN का पायथन कार्यान्वयन सम्मिलित है, जिसे k-d trees और बॉल ट्री का उपयोग करके त्वरित किया जा सकता है लेकिन जो सबसे खराब स्थिति वाली द्विघात मेमोरी का उपयोग करता है। एक scikit-learn में योगदान HDBSCAN* एल्गोरिदम का कार्यान्वयन प्रदान करता है।
pyclustering लाइब्रेरी में केवल यूक्लिडियन दूरी के साथ-साथ ऑप्टिक्स एल्गोरिदम के लिए DBSCAN का पायथन और C++ कार्यान्वयन सम्मिलित है।
SPMF में केवल यूक्लिडियन दूरी के लिए k-d ट्री समर्थन के साथ DBSCAN एल्गोरिथ्म का कार्यान्वयन सम्मिलित है।
वीका (मशीन लर्निंग) में (नवीनतम संस्करणों में एक वैकल्पिक पैकेज के रूप में) 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 1: / Line 1: @@
 {{short description|Density-based data clustering algorithm}}
 {{Machine learning|Clustering}}
-'''शोर के साथ अनुप्रयोगों की घनत्व-आधारित स्थानिक क्लस्टरिंग (डीबीएससीएएन)''' 1996 में [[ मार्टिन एस्तेर | मार्टिन एस्तेर]], [[हंस पीटर क्रिएगेल]], जोर्ग सैंडर और ज़ियाओवेई जू द्वारा प्रस्तावित [[डेटा क्लस्टरिंग]] एल्गोरिदम है।<ref name="dbscan">{{Cite conference
+'''शोर के साथ अनुप्रयोगों की घनत्व-आधारित स्थानिक क्लस्टरिंग (DBSCAN)''' 1996 में [[ मार्टिन एस्तेर | मार्टिन एस्तेर]], [[हंस पीटर क्रिएगेल]], जोर्ग सैंडर और ज़ियाओवेई जू द्वारा प्रस्तावित [[डेटा क्लस्टरिंग]] एल्गोरिदम है।<ref name="dbscan">{{Cite conference
   | author1-link = Martin Ester | author1-first = Martin | author1-last = Ester | author2-link = Hans-Peter Kriegel | author2-first = Hans-Peter | author2-last =Kriegel | first3 = Jörg | last3 = Sander | first4 = Xiaowei | last4 = Xu
   | title = A density-based algorithm for discovering clusters in large spatial databases with noise
@@ Line 32: / Line 32: @@
 अब अगर {{mvar|p}} एक मुख्य बिंदु है, फिर यह उन सभी बिंदुओं (कोर या गैर-कोर) के साथ मिलकर एक क्लस्टर बनाता है जो इससे पहुंच योग्य हैं। प्रत्येक क्लस्टर में कम से कम एक मुख्य बिंदु होता है; गैर-कोर बिंदु क्लस्टर का हिस्सा हो सकते हैं, लेकिन वे इसका किनारा बनाते हैं, क्योंकि उनका उपयोग अधिक बिंदुओं तक पहुंचने के लिए नहीं किया जा सकता है।
-[[File:DBSCAN-Illustration.svg|thumb|center|400px|इस आरेख में, {{math|{{not a typo|minPts}} {{=}} 4}}. बिंदु A और अन्य लाल बिंदु मुख्य बिंदु हैं, क्योंकि इन बिंदुओं के आसपास का क्षेत्र एक में है {{mvar|ε}} त्रिज्या में कम से कम 4 बिंदु होते हैं (स्वयं बिंदु सहित)। क्योंकि वे सभी एक-दूसरे से पहुंच योग्य हैं, वे एक एकल क्लस्टर बनाते हैं। बिंदु B और C मुख्य बिंदु नहीं हैं, लेकिन A (अन्य मुख्य बिंदुओं के माध्यम से) तक पहुंचा जा सकता है और इस प्रकार क्लस्टर से भी संबंधित हैं। प्वाइंट एन एक शोर बिंदु है जो न तो मुख्य बिंदु है और न ही सीधे पहुंच योग्य है।]]रीचैबिलिटी एक सममित संबंध नहीं है: परिभाषा के अनुसार, केवल मुख्य बिंदु ही गैर-मुख्य बिंदुओं तक पहुंच सकते हैं। विपरीत सत्य नहीं है, इसलिए एक गैर-मुख्य बिंदु तक पहुंचा जा सकता है, लेकिन उससे कुछ भी नहीं पहुंचा जा सकता है। इसलिए, डीबीएससीएएन द्वारा पाए गए क्लस्टर की सीमा को औपचारिक रूप से परिभाषित करने के लिए कनेक्टिविटी की एक और धारणा की आवश्यकता है। दो बिंदु {{mvar|p}} और {{mvar|q}} यदि कोई बिंदु है तो घनत्व-जुड़े हुए हैं {{mvar|o}} ऐसे कि दोनों {{mvar|p}} और {{mvar|q}} से पहुंच योग्य हैं {{mvar|o}}. घनत्व-संबद्धता सममित है।
+[[File:DBSCAN-Illustration.svg|thumb|center|400px|इस आरेख में, {{math|{{not a typo|minPts}} {{=}} 4}}. बिंदु A और अन्य लाल बिंदु मुख्य बिंदु हैं, क्योंकि इन बिंदुओं के आसपास का क्षेत्र एक में है {{mvar|ε}} त्रिज्या में कम से कम 4 बिंदु होते हैं (स्वयं बिंदु सहित)। क्योंकि वे सभी एक-दूसरे से पहुंच योग्य हैं, वे एक एकल क्लस्टर बनाते हैं। बिंदु B और C मुख्य बिंदु नहीं हैं, लेकिन A (अन्य मुख्य बिंदुओं के माध्यम से) तक पहुंचा जा सकता है और इस प्रकार क्लस्टर से भी संबंधित हैं। प्वाइंट एन एक शोर बिंदु है जो न तो मुख्य बिंदु है और न ही सीधे पहुंच योग्य है।]]रीचैबिलिटी एक सममित संबंध नहीं है: परिभाषा के अनुसार, केवल मुख्य बिंदु ही गैर-मुख्य बिंदुओं तक पहुंच सकते हैं। विपरीत सत्य नहीं है, इसलिए एक गैर-मुख्य बिंदु तक पहुंचा जा सकता है, लेकिन उससे कुछ भी नहीं पहुंचा जा सकता है। इसलिए, DBSCAN द्वारा पाए गए क्लस्टर की सीमा को औपचारिक रूप से परिभाषित करने के लिए कनेक्टिविटी की एक और धारणा की आवश्यकता है। दो बिंदु {{mvar|p}} और {{mvar|q}} यदि कोई बिंदु है तो घनत्व-जुड़े हुए हैं {{mvar|o}} ऐसे कि दोनों {{mvar|p}} और {{mvar|q}} से पहुंच योग्य हैं {{mvar|o}}. घनत्व-संबद्धता सममित है।
 एक क्लस्टर तब दो गुणों को पूरा करता है:
@@ Line 120: / Line 120: @@
 प्रत्येक डेटा माइनिंग कार्य में मापदंडों की समस्या होती है। प्रत्येक पैरामीटर विशिष्ट तरीकों से एल्गोरिदम को प्रभावित करता है। DBSCAN के लिए, पैरामीटर ε और {{not a typo|minPts}} जरूरत है। पैरामीटर उपयोगकर्ता द्वारा निर्दिष्ट किए जाने चाहिए. आदर्श रूप से, ε का मान हल की जाने वाली समस्या (उदाहरण के लिए भौतिक दूरी) द्वारा दिया जाता है और {{not a typo|minPts}} तो वांछित न्यूनतम क्लस्टर आकार है।{{efn|name=minpts}}
-* ''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" />
+* ''MinPts'': सामान्य नियम के रूप में, न्यूनतम {{not a typo|minPts}} को डेटा सेट में आयाम ''D'' की संख्या {{not a typo|minPts}} ≥ D + 1 से प्राप्त किया जा सकता है। {{not a typo|minPts}} = 1 का कोई मतलब नहीं है, क्योंकि परिभाषा के अनुसार प्रत्येक बिंदु एक मुख्य बिंदु है। ''minPts'' ≤ 2 के साथ परिणाम एकल लिंक मीट्रिक के साथ [[पदानुक्रमित क्लस्टरिंग]] के समान होगा, ऊंचाई ε पर डेंड्रोग्राम कट के साथ, इसलिए {{not a typo|minPts}} को कम से कम 3 चुना जाना चाहिए। यद्यपि, बड़े मान सामान्यतः शोर वाले डेटा सेट के लिए बेहतर होते हैं और इससे अधिक महत्वपूर्ण क्लस्टर प्राप्त होंगे। अंगूठे के नियम के रूप में, {{not a typo|minPts}} = 2·''dim'' का उपयोग किया जा सकता है,<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" />लेकिन फिर ऑप्टिक्स एल्गोरिदम का उपयोग डेटा को क्लस्टर करने के लिए किया जा सकता है।
+*ε: ε के लिए मान को k-दूरी ग्राफ का उपयोग करके चुना जा सकता है, जो कि ''k'' = ''minPts''-1 की दूरी को प्लॉट करता है। {{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 द्वारा उत्पादित सरल डेटा विभाजन के बजाय एक पदानुक्रमित क्लस्टरिंग उत्पन्न करेगा।
+ऑप्टिक्स एल्गोरिदम को DBSCAN के सामान्यीकरण के रूप में देखा जा सकता है जो ε पैरामीटर को अधिकतम मान से बदल देता है जो ज्यादातर प्रदर्शन को प्रभावित करता है। ''MinPts'' तब अनिवार्य रूप से खोजने के लिए न्यूनतम क्लस्टर आकार बन जाता है। जबकि एल्गोरिथ्म को DBSCAN की तुलना में पैरामीटराइज़ करना बहुत आसान है, परिणामों का उपयोग करना थोड़ा अधिक कठिन है, क्योंकि यह सामान्यतः DBSCAN द्वारा उत्पादित सरल डेटा विभाजन के अतिरिक्त एक पदानुक्रमित क्लस्टरिंग उत्पन्न करेगा।
-हाल ही में, DBSCAN के मूल लेखकों में से एक ने DBSCAN और OPTICS पर दोबारा गौर किया है, और पदानुक्रमित DBSCAN (HDBSCAN*) का एक परिष्कृत संस्करण प्रकाशित किया है।<ref name="hdbscan1">{{cite journal|last1=Campello|first1=Ricardo J. G. B.|last2=Moulavi|first2=Davoud|last3=Zimek|first3=Arthur|author-link3=Arthur Zimek|last4=Sander|first4=Jörg|title=डेटा क्लस्टरिंग, विज़ुअलाइज़ेशन और आउटलायर डिटेक्शन के लिए पदानुक्रमित घनत्व अनुमान|journal=ACM Transactions on Knowledge Discovery from Data|volume=10|issue=1|year=2015|pages=1–51|issn=1556-4681|doi=10.1145/2733381|s2cid=2887636}}</ref> जिसमें अब सीमा बिंदुओं की कोई धारणा नहीं है। इसके बजाय, केवल मुख्य बिंदु ही क्लस्टर बनाते हैं।
+हाल ही में, DBSCAN के मूल लेखकों में से एक ने DBSCAN और OPTICS पर दोबारा गौर किया है, और पदानुक्रमित DBSCAN (HDBSCAN*) का एक परिष्कृत संस्करण प्रकाशित किया है।<ref name="hdbscan1">{{cite journal|last1=Campello|first1=Ricardo J. G. B.|last2=Moulavi|first2=Davoud|last3=Zimek|first3=Arthur|author-link3=Arthur Zimek|last4=Sander|first4=Jörg|title=डेटा क्लस्टरिंग, विज़ुअलाइज़ेशन और आउटलायर डिटेक्शन के लिए पदानुक्रमित घनत्व अनुमान|journal=ACM Transactions on Knowledge Discovery from Data|volume=10|issue=1|year=2015|pages=1–51|issn=1556-4681|doi=10.1145/2733381|s2cid=2887636}}</ref> जिसमें अब सीमा बिंदुओं की कोई धारणा नहीं है। इसके अतिरिक्त, केवल मुख्य बिंदु ही क्लस्टर बनाते हैं।
 == [[वर्णक्रमीय क्लस्टरिंग]] से संबंध ==
-डीबीएससीएएन का वर्णक्रमीय कार्यान्वयन कनेक्टेड घटक (ग्राफ सिद्धांत) के निर्धारण के तुच्छ मामले में वर्णक्रमीय क्लस्टरिंग से संबंधित है - बिना किनारों के कटे हुए इष्टतम क्लस्टर।<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 एल्गोरिथ्म इसके वर्णक्रमीय कार्यान्वयन के लिए बेहतर है।
+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>कम्प्यूटेशनल रूप से गहन हो सकता है। इसके अतिरिक्त, किसी को गणना करने के लिए आइजन्वेक्टर की संख्या चुननी होगी। प्रदर्शन कारणों से, मूल DBSCAN एल्गोरिथ्म इसके वर्णक्रमीय कार्यान्वयन के लिए बेहतर है।
 ==एक्सटेंशन==
-सामान्यीकृत डीबीएससीएएन (जीडीबीएससीएएन)<ref name=":0">{{Cite journal
+सामान्यीकृत DBSCAN (GDBSCAN)<ref name=":0">{{Cite journal
   | first1 = Jörg       | last1 = Sander
   | first2 = Martin     | last2 = Ester
@@ Line 148: / Line 148: @@
   | 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>
+DBSCAN एल्गोरिथ्म के विभिन्न विस्तार प्रस्तावित किए गए हैं, जिनमें समानांतरीकरण, पैरामीटर अनुमान और अनिश्चित डेटा के लिए समर्थन के तरीके सम्मिलित हैं। मूल विचार को ऑप्टिक्स एल्गोरिदम द्वारा पदानुक्रमित क्लस्टरिंग तक बढ़ा दिया गया है। DBSCAN का उपयोग PreDeCon और [[SUBCLU]] जैसे सबस्पेस क्लस्टरिंग एल्गोरिदम के हिस्से के रूप में भी किया जाता है। HDBSCAN<ref name="hdbscan1" /> DBSCAN का एक पदानुक्रमित संस्करण है जो ऑप्टिक्स से भी तेज़ है, जिसमें से सबसे प्रमुख समूहों से युक्त एक फ्लैट विभाजन को पदानुक्रम से निकाला जा सकता है।<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>
@@ Line 157: / Line 157: @@
 एक ही एल्गोरिथ्म के अलग-अलग कार्यान्वयन में भारी प्रदर्शन अंतर प्रदर्शित किया गया, परीक्षण डेटा सेट पर सबसे तेज़ 1.4 सेकंड में समाप्त हुआ, सबसे धीमा 13803 सेकंड में समाप्त हुआ।<ref>{{cite journal|last1=Kriegel|first1=Hans-Peter|author-link1=Hans-Peter Kriegel|last2=Schubert|first2=Erich|last3=Zimek|first3=Arthur|author-link3 = Arthur Zimek |title=The (black) art of runtime evaluation: Are we comparing algorithms or implementations?|journal=Knowledge and Information Systems|volume=52|issue=2|pages=341|year=2016|issn=0219-1377|doi=10.1007/s10115-016-1004-2|s2cid=40772241}}</ref> अंतरों को कार्यान्वयन की गुणवत्ता, भाषा और कंपाइलर अंतर और त्वरण के लिए अनुक्रमणिका के उपयोग के लिए जिम्मेदार ठहराया जा सकता है।
-* [[अपाचे कॉमन्स]] [http://commons.apache.org/proper/commons-math/ Math] में द्विघात समय में चलने वाले एल्गोरिदम का जावा कार्यान्वयन शामिल है।
+* [[अपाचे कॉमन्स]] [http://commons.apache.org/proper/commons-math/ Math] में द्विघात समय में चलने वाले एल्गोरिदम का जावा कार्यान्वयन सम्मिलित है।
-* [[ELKI]] DBSCAN के साथ-साथ GDBSCAN और अन्य वेरिएंट का कार्यान्वयन प्रदान करता है। यह कार्यान्वयन उप-द्विघात रनटाइम के लिए विभिन्न सूचकांक संरचनाओं का उपयोग कर सकता है और मनमानी दूरी के कार्यों और मनमाने डेटा प्रकारों का समर्थन करता है, लेकिन यह छोटे डेटा सेट पर निम्न-स्तरीय अनुकूलित (और विशेष) कार्यान्वयन द्वारा बेहतर प्रदर्शन कर सकता है।
+* [[ELKI]] DBSCAN के साथ-साथ GDBSCAN और अन्य वेरिएंट का कार्यान्वयन प्रदान करता है। यह कार्यान्वयन उप-द्विघात रनटाइम के लिए विभिन्न सूचकांक संरचनाओं का उपयोग कर सकता है और यादृच्छिक दूरी के कार्यों और यादृच्छिक डेटा प्रकारों का समर्थन करता है, लेकिन यह छोटे डेटा सेट पर निम्न-स्तरीय अनुकूलित (और विशेष) कार्यान्वयन द्वारा बेहतर प्रदर्शन कर सकता है।
-* [[MATLAB]] ने R2019a जारी होने के बाद से अपने सांख्यिकी और मशीन लर्निंग टूलबॉक्स में DBSCAN का कार्यान्वयन शामिल किया है।
+* [[MATLAB]] ने R2019a जारी होने के बाद से अपने सांख्यिकी और मशीन लर्निंग टूलबॉक्स में DBSCAN का कार्यान्वयन सम्मिलित किया है।
-* [[ mlpack ]] में डुअल-ट्री रेंज सर्च तकनीकों के साथ त्वरित डीबीएससीएएन का कार्यान्वयन शामिल है।
+* [[ mlpack ]] में डुअल-ट्री रेंज सर्च तकनीकों के साथ त्वरित DBSCAN का कार्यान्वयन सम्मिलित है।
-* [[PostGIS]] में ST_ClusterDBSCAN शामिल है - DBSCAN का 2D कार्यान्वयन जो R-ट्री इंडेक्स का उपयोग करता है। कोई भी ज्यामिति प्रकार समर्थित है, उदा. प्वाइंट, लाइनस्ट्रिंग, बहुभुज, आदि।
+* [[PostGIS]] में ST_ClusterDBSCAN सम्मिलित है - DBSCAN का 2D कार्यान्वयन जो R-ट्री इंडेक्स का उपयोग करता है। कोई भी ज्यामिति प्रकार समर्थित है, उदा. प्वाइंट, लाइनस्ट्रिंग, बहुभुज, आदि।
-* [[आर (प्रोग्रामिंग भाषा)]] में पैकेज [https://cran.r-project.org/package=dbscan dbscan] और [https://cran.r-project.org/package=fpc fpc] में DBSCAN का कार्यान्वयन शामिल है। . दोनों पैकेज दूरी मैट्रिक्स के माध्यम से मनमाने ढंग से दूरी के कार्यों का समर्थन करते हैं। पैकेज एफपीसी में इंडेक्स समर्थन नहीं है (और इस प्रकार इसमें द्विघात रनटाइम और मेमोरी जटिलता है) और आर दुभाषिया के कारण यह धीमा है। पैकेज dbscan k-d पेड़ों (केवल यूक्लिडियन दूरी के लिए) का उपयोग करके तेज़ C++ कार्यान्वयन प्रदान करता है और इसमें DBSCAN*, HDBSCAN*, OPTICS, OPTICSXi और अन्य संबंधित तरीकों का कार्यान्वयन भी शामिल है।
+* [[आर (प्रोग्रामिंग भाषा)]] में पैकेज [https://cran.r-project.org/package=dbscan dbscan] और [https://cran.r-project.org/package=fpc fpc] में DBSCAN का कार्यान्वयन सम्मिलित है। दोनों पैकेज दूरी मैट्रिक्स के माध्यम से यादृच्छिक ढंग से दूरी के कार्यों का समर्थन करते हैं। पैकेज एफपीसी में इंडेक्स समर्थन नहीं है (और इस प्रकार इसमें द्विघात रनटाइम और मेमोरी जटिलता है) और आर दुभाषिया के कारण यह धीमा है। पैकेज dbscan k-d trees (केवल यूक्लिडियन दूरी के लिए) का उपयोग करके तेज़ C++ कार्यान्वयन प्रदान करता है और इसमें DBSCAN*, HDBSCAN*, OPTICS, OPTICSXi और अन्य संबंधित तरीकों का कार्यान्वयन भी सम्मिलित है।
-* [[स्किकिट-लर्न]] में मनमानी [[मिन्कोव्स्की दूरी]] के लिए डीबीएससीएएन का पायथन कार्यान्वयन शामिल है, जिसे [[के-डी पेड़]]ों और बॉल पेड़ों का उपयोग करके त्वरित किया जा सकता है लेकिन जो सबसे खराब स्थिति वाली द्विघात मेमोरी का उपयोग करता है। एक [https://github.com/scikit-learn-contrib/hdbscan scikit-learn में योगदान] HDBSCAN* एल्गोरिदम का कार्यान्वयन प्रदान करता है।
+* [[स्किकिट-लर्न]] में यादृच्छिक [[मिन्कोव्स्की दूरी]] के लिए DBSCAN का पायथन कार्यान्वयन सम्मिलित है, जिसे  [[के-डी पेड़|k-d trees]] और बॉल ट्री का उपयोग करके त्वरित किया जा सकता है लेकिन जो सबसे खराब स्थिति वाली द्विघात मेमोरी का उपयोग करता है। एक [https://github.com/scikit-learn-contrib/hdbscan scikit-learn में योगदान] HDBSCAN* एल्गोरिदम का कार्यान्वयन प्रदान करता है।
-* [https://github.com/annoviko/pyclustering pyclustering] लाइब्रेरी में केवल यूक्लिडियन दूरी के साथ-साथ ऑप्टिक्स एल्गोरिदम के लिए DBSCAN का पायथन और C++ कार्यान्वयन शामिल है।
+* [https://github.com/annoviko/pyclustering pyclustering] लाइब्रेरी में केवल यूक्लिडियन दूरी के साथ-साथ ऑप्टिक्स एल्गोरिदम के लिए DBSCAN का पायथन और C++ कार्यान्वयन सम्मिलित है।
-* [http://www.philippe-fournier-viger.com/spmf/ SPMF] में केवल यूक्लिडियन दूरी के लिए k-d ट्री समर्थन के साथ DBSCAN एल्गोरिथ्म का कार्यान्वयन शामिल है।
+* [http://www.philippe-fournier-viger.com/spmf/ SPMF] में केवल यूक्लिडियन दूरी के लिए k-d ट्री समर्थन के साथ DBSCAN एल्गोरिथ्म का कार्यान्वयन सम्मिलित है।
-* वीका (मशीन लर्निंग) में (नवीनतम संस्करणों में एक वैकल्पिक पैकेज के रूप में) डीबीएससीएएन का एक बुनियादी कार्यान्वयन शामिल है जो द्विघात समय और रैखिक मेमोरी में चलता है।
+* वीका (मशीन लर्निंग) में (नवीनतम संस्करणों में एक वैकल्पिक पैकेज के रूप में) DBSCAN का एक बुनियादी कार्यान्वयन सम्मिलित है जो द्विघात समय और रैखिक मेमोरी में चलता है।
-* [https://docs.rs/linfa-clustering/latest/linfa_clustering/struct.Dbscan.html linfa] में रस्ट (प्रोग्रामिंग भाषा) के लिए DBSCAN का कार्यान्वयन शामिल है।
+* [https://docs.rs/linfa-clustering/latest/linfa_clustering/struct.Dbscan.html linfa] में रस्ट (प्रोग्रामिंग भाषा) के लिए DBSCAN का कार्यान्वयन सम्मिलित है।
-<!-- -->
-<!-- before adding yet another implementation, verify that it is of notability. Wikipedia is not a collection of links! -->

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 13:05, 3 August 2023

Contents

इतिहास

प्रारंभिक

एल्गोरिदम

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

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

जटिलता

फायदे

नुकसान

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

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

एक्सटेंशन

उपलब्धता

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 13:05, 3 August 2023

इतिहास

प्रारंभिक

एल्गोरिदम

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

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

जटिलता

फायदे

नुकसान

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

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

एक्सटेंशन

उपलब्धता

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories