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

'''शोर के साथ अनुप्रयोगों की घनत्व-आधारित स्थानिक क्लस्टरिंग (डीबीएससीएएन)''' 1996 में [[ मार्टिन एस्तेर | मार्टिन एस्तेर]], [[हंस पीटर क्रिएगेल]], जोर्ग सैंडर और ज़ियाओवेई जू द्वारा प्रस्तावित [[डेटा क्लस्टरिंग]] एल्गोरिदम है।<ref name="dbscan">{{Cite conference

}}</ref> यह एक घनत्व-आधारित क्लस्टरिंग गैर-पैरामेट्रिक एल्गोरिथ्म है: किसी स्थान में बिंदुओं का एक सेट दिया जाता है, यह उन बिंदुओं को एक साथ समूहित करता है जो बारीकी से एक साथ पैक किए जाते हैं (किनारे के पास कई निश्चित-त्रिज्या वाले बिंदु), अंकन बाहरी बिंदुओं के रूप में जो कम घनत्व वाले क्षेत्रों में अकेले स्थित हैं (जिनके निकटतम किनारे बहुत दूर हैं)। DBSCAN सबसे सामान्य और सबसे अधिक उद्धृत क्लस्टरिंग एल्गोरिदम में से एक है।<ref>{{cite web |url=http://academic.research.microsoft.com/CSDirectory/paper_category_7.htm |title=Microsoft Academic Search: Papers |access-date=2010-04-18 |url-status=dead |archive-url=https://web.archive.org/web/20100421170848/http://academic.research.microsoft.com/CSDirectory/paper_category_7.htm |archive-date=April 21, 2010 }} Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24.</ref>

2014 में, अग्रणी डेटा माइनिंग कॉन्फ्रेंस, ACM [[SIGKDD]] में एल्गोरिदम को टेस्ट ऑफ टाइम अवार्ड (सिद्धांत और व्यवहार में पर्याप्त ध्यान प्राप्त करने वाले एल्गोरिदम को दिया जाने वाला पुरस्कार) से सम्मानित किया गया था।<ref>{{cite web|url=http://www.kdd.org/News/view/2014-sigkdd-test-of-time-award|date=2014-08-18|access-date=2016-07-27|title=2014 SIGKDD Test of Time Award|publisher=[[Association for Computing Machinery|ACM]] SIGKDD}}</ref> {{As of|2020|July}}, अनुवर्ती पेपर DBSCAN को फिर से देखा जा सकता है: आपको DBSCAN का उपयोग क्यों और कैसे करना चाहिए (अभी भी)<ref name="tods" /> प्रतिष्ठित [[डेटाबेस सिस्टम पर एसीएम लेनदेन|डेटाबेस सिस्टम पर एसीएम ट्रांजैक्शंस]] (टीओडीएस) दैनिकी के 8 सबसे अधिक डाउनलोड किए गए लेखों की सूची में दिखाई देता है।<ref>{{Cite web|title=टोड्स होम|url=https://dl.acm.org/journal/tods#pane-cc36fa1b-c28c-425f-9325-f853cff8882901|access-date=2020-07-16|website=tods.acm.org|publisher=[[Association for Computing Machinery]]|language=en}}</ref>

1972 में, रॉबर्ट एफ. लिंग ने <ref name=":1">{{Cite journal|last=Ling|first=R. F.|date=1972-01-01|title=के-क्लस्टर के सिद्धांत और निर्माण पर|url=https://academic.oup.com/comjnl/article/15/4/326/351493|journal=The Computer Journal|language=en|volume=15|issue=4|pages=326–332|doi=10.1093/comjnl/15.4.326|issn=0010-4620|doi-access=free}}</ref> [[कंप्यूटर जर्नल]] में k-क्लस्टर्स के सिद्धांत और निर्माण में O(n³) की अनुमानित रनटाइम जटिलता के साथ एक निकट से संबंधित एल्गोरिथ्म प्रकाशित किया।<ref name=":1" /> DBSCAN में O(n²) की सबसे खराब स्थिति है, और DBSCAN का डेटाबेस-उन्मुख रेंज-क्वेरी फॉर्मूलेशन सूचकांक त्वरण की अनुमति देता है। सीमा बिंदुओं को संभालने में एल्गोरिदम थोड़ा भिन्न हैं।

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

* िसी भी अन्य बिंदु से न पहुंच सकने वाले सभी बिंदु आउटलेयर या शोर बिंदु हैं।

[[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}}. घनत्व-संबद्धता सममित है।

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 का उपयोग किसी भी दूरी फ़ंक्शन के साथ किया जा सकता है<ref name="dbscan" /><ref name="tods" />(साथ ही समानता कार्य या अन्य विधेय)।<ref name=":0" />इसलिए दूरी फ़ंक्शन (dist) को एक अतिरिक्त पैरामीटर के रूप में देखा जा सकता है।

एल्गोरिथ्म को [[छद्मकोड]] में इस प्रकार व्यक्त किया जा सकता है:<ref name="tods" />

     सी:= 0 /*क्लस्टर काउंटर*/

     डेटाबेस डीबी में 'प्रत्येक' बिंदु पी के लिए {

         'यदि' लेबल (पी) ≠ अपरिभाषित 'तब' '[[जारी रखें (कीवर्ड)]]' /* पहले आंतरिक लूप में संसाधित */

         पड़ोसी एन:= रेंजक्वेरी(डीबी, डिस्टफनक, पी, ईपीएस) /*पड़ोसी खोजें*/

         'अगर' |एन| < {{not a typo|minPts}} फिर { ''/* घनत्व जांच */''

             लेबल(पी) := शोर ''/* शोर के रूप में लेबल करें */''

             जारी रखना

         सी := सी + 1 ''/* अगला क्लस्टर लेबल */''

         लेबल(पी) := सी ''/* लेबल प्रारंभिक बिंदु */''

         सीडसेट एस := एन \ {पी} ''/* पड़ोसियों का विस्तार करने के लिए */''

         S में प्रत्येक बिंदु Q के लिए { ''/* प्रत्येक बीज बिंदु Q को संसाधित करें */''

             यदि लेबल (क्यू) = शोर है तो लेबल (क्यू) := सी ''/* शोर को सीमा बिंदु पर बदलें */''

             यदि लेबल (क्यू) ≠ अपरिभाषित है तो जारी रखें ''/* पहले संसाधित (उदाहरण के लिए, सीमा बिंदु) */''

             लेबल(क्यू) := सी ''/* लेबल पड़ोसी */''

             पड़ोसी एन := रेंजक्वेरी(डीबी, डिस्टफनक, क्यू, ईपीएस) ''/*पड़ोसी खोजें */''

             यदि |एन| ≥ {{not a typo|minPts}} फिर { ''/* घनत्व जांच (यदि क्यू एक मुख्य बिंदु है) */''

                 एस := एस ∪ एन ''/* बीज सेट में नए पड़ोसी जोड़ें */''

रेंजक्वेरी(DB, distFunc, Q, eps) {

     पड़ोसी एन := खाली सूची

     डेटाबेस DB में प्रत्येक बिंदु P के लिए { ''/* डेटाबेस में सभी बिंदुओं को स्कैन करें */''

         यदि distFunc(Q, P) ≤ eps तो { ''/* दूरी की गणना करें और epsilon जांचें */''

             एन := एन ∪ {पी} ''/* परिणाम में जोड़ें */''

     वापसी एन

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

DBSCAN एल्गोरिथ्म को निम्नलिखित चरणों में संक्षेपित किया जा सकता है:<ref name="tods" />

# प्रत्येक बिंदु के ε (ईपीएस) पड़ोस में बिंदु ढूंढें, और इससे अधिक वाले मुख्य बिंदुओं की पहचान करें {{not a typo|minPts}} पड़ोसियों।

# सभी गैर-कोर बिंदुओं को अनदेखा करते हुए, पड़ोसी ग्राफ़ पर मुख्य बिंदुओं के [[कनेक्टेड घटक (ग्राफ़ सिद्धांत)]] को ढूंढें।

# यदि क्लस्टर एक ε (ईपीएस) पड़ोसी है, तो प्रत्येक गैर-कोर बिंदु को पास के क्लस्टर में निर्दिष्ट करें, अन्यथा इसे शोर के लिए निर्दिष्ट करें।

इसके सरल कार्यान्वयन के लिए चरण 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'')}} याद।

[[File:DBSCAN-density-data.svg|thumb|DBSCAN गैर-रैखिक रूप से अलग करने योग्य क्लस्टर ढूंढ सकता है। इस डेटासेट को k-मीन्स या गॉसियन मिक्सचर EM क्लस्टरिंग के साथ पर्याप्त रूप से क्लस्टर नहीं किया जा सकता है।]]

# DBSCAN को [[K-मतलब एल्गोरिदम]]|k-मीन्स के विपरीत, डेटा में क्लस्टर की संख्या को प्राथमिकता से निर्दिष्ट करने की आवश्यकता नहीं होती है।

# DBSCAN मनमाने आकार के क्लस्टर ढूंढ सकता है। यह एक ऐसे क्लस्टर को भी ढूंढ सकता है जो पूरी तरह से एक अलग क्लस्टर से घिरा हुआ है (लेकिन उससे जुड़ा नहीं है)। MinPts पैरामीटर के कारण, तथाकथित सिंगल-लिंक प्रभाव (विभिन्न समूहों को बिंदुओं की एक पतली रेखा से जोड़ा जाना) कम हो जाता है।

# DBSCAN में शोर की अवधारणा है, और यह विसंगति का पता लगाने में सक्षम है।

# DBSCAN को केवल दो मापदंडों की आवश्यकता होती है और यह डेटाबेस में बिंदुओं के क्रम के प्रति अधिकतर असंवेदनशील होता है। (हालाँकि, यदि बिंदुओं का क्रम बदल जाता है, तो दो अलग-अलग समूहों के किनारे पर बैठे बिंदु क्लस्टर सदस्यता को स्वैप कर सकते हैं, और क्लस्टर असाइनमेंट केवल समरूपता तक अद्वितीय है।)

# DBSCAN को ऐसे डेटाबेस के साथ उपयोग के लिए डिज़ाइन किया गया है जो क्षेत्र के प्रश्नों को तेज़ कर सकता है, उदाहरण के लिए R* वृक्ष का उपयोग करना।

# 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,ε) फ़ंक्शन में प्रयुक्त मीट्रिक (गणित) पर निर्भर करती है। उपयोग की जाने वाली सबसे सामान्य दूरी मीट्रिक [[यूक्लिडियन दूरी]] है। विशेष रूप से उच्च-आयामी डेटा | उच्च-आयामी डेटा को क्लस्टर करने के लिए, इस मीट्रिक को तथाकथित आयामीता #दूरी कार्यों के अभिशाप के कारण लगभग बेकार बना दिया जा सकता है, जिससे ε के लिए उचित मान ढूंढना मुश्किल हो जाता है। हालाँकि, यह प्रभाव यूक्लिडियन दूरी पर आधारित किसी अन्य एल्गोरिदम में भी मौजूद है।