डीबीएससीएएन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 41: | Line 41: | ||
=== मूल क्वेरी-आधारित एल्गोरिदम === | === मूल क्वेरी-आधारित एल्गोरिदम === | ||
DBSCAN को दो मापदंडों | 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 का उपयोग किसी भी दूरी | DBSCAN का उपयोग किसी भी दूरी फलन के साथ किया जा सकता है<ref name="dbscan" /><ref name="tods" />(साथ ही समानता कार्य या अन्य विधेय)।<ref name=":0" /> इसलिए दूरी फलन (dist) को एक अतिरिक्त पैरामीटर के रूप में देखा जा सकता है। | ||
एल्गोरिथ्म को [[छद्मकोड]] में इस प्रकार व्यक्त किया जा सकता है:<ref name="tods" /> | एल्गोरिथ्म को [[छद्मकोड|स्यूडोकोड]] में इस प्रकार व्यक्त किया जा सकता है:<ref name="tods" /> | ||
DBSCAN(DB, distFunc, eps, minPts) { | DBSCAN(DB, distFunc, eps, minPts) { | ||
| Line 84: | Line 84: | ||
} | } | ||
=== | === अमूर्त एल्गोरिथ्म === | ||
DBSCAN एल्गोरिथ्म को निम्नलिखित चरणों में संक्षेपित किया जा सकता है:<ref name="tods" /> | DBSCAN एल्गोरिथ्म को निम्नलिखित चरणों में संक्षेपित किया जा सकता है:<ref name="tods" /> | ||
# प्रत्येक बिंदु के ε ( | # प्रत्येक बिंदु के ε (eps) लघु भाग में बिंदु ढूंढें, और इससे अधिक वाले मुख्य बिंदुओं {{not a typo|minPts}} लघु भागियों की पहचान करें। | ||
# सभी गैर-कोर बिंदुओं को अनदेखा करते हुए, | # सभी गैर-कोर बिंदुओं को अनदेखा करते हुए, लघु भागी ग्राफ़ पर मुख्य बिंदुओं के [[कनेक्टेड घटक (ग्राफ़ सिद्धांत)]] को ढूंढें। | ||
# यदि क्लस्टर एक ε ( | # यदि क्लस्टर एक ε (eps) लघु भागी है, तो प्रत्येक गैर-कोर बिंदु को पास के क्लस्टर में निर्दिष्ट करें, अन्यथा इसे शोर के लिए निर्दिष्ट करें। | ||
इसके सरल कार्यान्वयन के लिए चरण 1 में | इसके सरल कार्यान्वयन के लिए चरण 1 में लघु भाग को संग्रहीत करने की आवश्यकता होती है, इस प्रकार पर्याप्त मेमोरी की आवश्यकता होती है। मूल DBSCAN एल्गोरिदम को एक समय में एक बिंदु के लिए इन चरणों को निष्पादित करने की आवश्यकता नहीं होती है। | ||
==जटिलता== | ==जटिलता== | ||
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>- ''n'' = (''n''²-''n'')/2 दूरी मैट्रिक्स के आकार के ऊपरी त्रिकोण को दूरी पुनर्गणना से बचने के लिए सामग्रीकृत किया जा सकता है, लेकिन इसके लिए {{math|O(''n''²)}} मेमोरी की आवश्यकता है, जबकि DBSCAN के गैर-मैट्रिक्स आधारित कार्यान्वयन के लिए केवल {{math|O(''n'')}} मेमोरी आवश्यकता होती है। | ||
[[File:DBSCAN-density-data.svg|thumb|DBSCAN गैर-रैखिक रूप से अलग करने योग्य क्लस्टर ढूंढ सकता है। इस डेटासेट को k-मीन्स या गॉसियन मिक्सचर EM क्लस्टरिंग के साथ पर्याप्त रूप से क्लस्टर नहीं किया जा सकता है।]] | [[File:DBSCAN-density-data.svg|thumb|DBSCAN गैर-रैखिक रूप से अलग करने योग्य क्लस्टर ढूंढ सकता है। इस डेटासेट को k-मीन्स या गॉसियन मिक्सचर EM क्लस्टरिंग के साथ पर्याप्त रूप से क्लस्टर नहीं किया जा सकता है।]] | ||
| Line 101: | Line 101: | ||
==फायदे== | ==फायदे== | ||
# DBSCAN को [[K-मतलब एल्गोरिदम | # DBSCAN को [[K-मतलब एल्गोरिदम|k-means]] के विपरीत, डेटा में क्लस्टर की संख्या को प्राथमिकता से निर्दिष्ट करने की आवश्यकता नहीं होती है। | ||
# DBSCAN | # DBSCAN याट्टीच्छक आकार के क्लस्टर ढूंढ सकता है। यह एक ऐसे क्लस्टर को भी ढूंढ सकता है जो पूरी तरह से एक अलग क्लस्टर से घिरा हुआ है (लेकिन उससे जुड़ा नहीं है)। MinPts पैरामीटर के कारण, तथाकथित एकल-लिंक प्रभाव (विभिन्न समूहों को बिंदुओं की एक पतली रेखा से जोड़ा जाना) कम हो जाता है। | ||
# DBSCAN में शोर की अवधारणा है, और यह विसंगति का पता लगाने में सक्षम है। | # DBSCAN में शोर की अवधारणा है, और यह विसंगति का पता लगाने में सक्षम है। | ||
# DBSCAN को केवल दो मापदंडों की आवश्यकता होती है और यह डेटाबेस में बिंदुओं के क्रम के प्रति अधिकतर असंवेदनशील होता है। ( | # DBSCAN को केवल दो मापदंडों की आवश्यकता होती है और यह डेटाबेस में बिंदुओं के क्रम के प्रति अधिकतर असंवेदनशील होता है। (यद्यपि, यदि बिंदुओं का क्रम बदल जाता है, तो दो अलग-अलग समूहों के किनारे पर बैठे बिंदु क्लस्टर सदस्यता को स्वैप कर सकते हैं, और क्लस्टर असाइनमेंट केवल समरूपता तक अद्वितीय है।) | ||
# DBSCAN को ऐसे डेटाबेस के साथ उपयोग के लिए डिज़ाइन किया गया है जो क्षेत्र के प्रश्नों को तेज़ कर सकता है, उदाहरण के लिए R* | # DBSCAN को ऐसे डेटाबेस के साथ उपयोग के लिए डिज़ाइन किया गया है जो क्षेत्र के प्रश्नों को तेज़ कर सकता है, उदाहरण के लिए R* रेखा का उपयोग करना है। | ||
# पैरामीटर {{not a typo|minPts}} और ε को एक डोमेन विशेषज्ञ द्वारा सेट किया जा सकता है, यदि डेटा अच्छी तरह से समझा गया हो। | # पैरामीटर {{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 पूरी तरह से नियतात्मक नहीं है: सीमा बिंदु जो एक से अधिक क्लस्टर से पहुंच योग्य हैं, डेटा संसाधित होने के क्रम के आधार पर किसी भी क्लस्टर का हिस्सा हो सकते हैं। अधिकांश डेटा सेट और डोमेन के लिए, यह स्थिति अक्सर उत्पन्न नहीं होती है और क्लस्टरिंग परिणाम पर इसका बहुत कम प्रभाव पड़ता है:<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> | # 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}} | प्रत्येक डेटा माइनिंग कार्य में मापदंडों की समस्या होती है। प्रत्येक पैरामीटर विशिष्ट तरीकों से एल्गोरिदम को प्रभावित करता है। 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}} को डेटा सेट में आयाम डी की संख्या से प्राप्त किया जा सकता है{{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 द्वारा उत्पादित सरल डेटा विभाजन के बजाय एक पदानुक्रमित क्लस्टरिंग उत्पन्न करेगा। | ऑप्टिक्स एल्गोरिदम को 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> | डीबीएससीएएन का वर्णक्रमीय कार्यान्वयन कनेक्टेड घटक (ग्राफ सिद्धांत) के निर्धारण के तुच्छ मामले में वर्णक्रमीय क्लस्टरिंग से संबंधित है - बिना किनारों के कटे हुए इष्टतम क्लस्टर।<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 | | issue = 2 | ||
| s2cid = 445002 | | 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> उन्हीं लेखकों द्वारा मनमाने | }}</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]] जैसे सबस्पेस क्लस्टरिंग एल्गोरिदम के हिस्से के रूप में भी किया जाता है। एचडीबीएसकैन<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> | ||
Revision as of 12:48, 2 August 2023
| Part of a series on |
| Machine learning and data mining |
|---|
 |