प्रकाशिकी एल्गोरिथ्म: Difference between revisions

Revision as of 16:57, 25 July 2023

समूहिंग संरचना की पहचान करने के लिए क्रम बिंदु (ओप्टिक्स) एक ऐसा एल्गोरिदम है जो स्थानिक डेटा में घनत्व-आधारित^[1] समूह को खोजने के लिए उपयोगी है।यह एल्गोरिदम मिहाएल एंकर्स्ट, मार्कस एम. ब्रेयुनिग, हंस पीटर क्रिएगेल , और जोर्ग सैंडर द्वारा प्रस्तुत किया गया था।^[2]इसकी मूल विचारधारा डीबीएससीएएन के समान है^[3],परंतु यह डीबीएससीएएन की एक प्रमुख कमियों में से एक को पता करता है: भिन्न घनत्व वाले डेटा में मायने रखने वाले समूह्स का पता लगाने की समस्या होती हैं।इसके लिए, डेटाबेस के बिंदुओं ऐसे क्रमबद्ध किया जाता हैं कि जो स्थानिक रूप से निकटतम बिंदु होते हैं, वे क्रमबद्धीकरण में पड़ोसी बन जाते हैं।इसके अतिरिक्त, प्रत्येक बिंदु के लिए एक विशेष दूरी संग्रहीत की जाती है जो एक समूह के लिए स्वीकार्य घनत्व को प्रतिनिधित करती है, क्योंकी दोनों बिंदु एक ही समूह का हिस्सा बनें रहे। यह एक डेंड्रोग्राम के रूप में प्रतिष्ठित किया जाता है।

मूलभूत विचार

डीबीएससीएएन की तरह, ऑप्टिक्स को दो मापदंडों की आवश्यकता होती है: ε, जो अधिकतम दूरी (रेडियस) का वर्णन करता है जिसे ध्यान में लेने के लिए, और $मिनिप्ट्स,$ , जो समूह बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है।एक बिंदु p एक मुख्य बिंदु होता है अगर उसके ε-पड़ोस $N_{\varepsilon }(p)$ में न्यूनतम से न्यूनतम $मिनिप्ट्स,$ बिंदु पाए जाते हैं। डीबीएससीएएन के विपरीत, ऑप्टिक्स उन बिंदुओं पर भी विचार करता है जो अधिक सघनता से भरे समूह का हिस्सा हैं, इसलिए प्रत्येक बिंदु को एक मुख्य दूरी सौंपी जाती है जो $मिनिप्ट्स,$ वां निकटतम बिंदु के लिए दूरी का वर्णन करती है:

{\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th smallest distance in }}N_{\varepsilon }(p)&{\text{otherwise}}\end{cases}}

एक दूसरे बिंदु $o$ के रीचेबिलिटी-दूरी को एक बिंदु $p$ से या तो $o$ और $p$ के मध्य की दूरी होती है, या $p$ की कोर दूरी होती हैं, जो भी बड़ी होती है।

{\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p,o))&{\text{otherwise}}\end{cases}}

अगर $p$ और $o$ निकटतम पड़ोसी हैं, तो यही $\varepsilon '<\varepsilon$ हमें मान लेना चाहिए कि $p$ और $o$ एक ही क्लस्टर का हिस्सा हैं।

यदि कोई पर्याप्त घनत्व वाला क्लस्टर (ε के संदर्भ में) उपलब्ध नहीं होता है, तो कोर दूरी और रीचेबिलिटी-दूरी अवर्णनीय होती हैं। पर्याप्त बड़े ε के लिए, यह कभी नहीं होता है, परंतु तब हर ε-नेबरहुड क्वेरी संपूर्ण डेटाबेस लौटाती है, जिससे $O(n^{2})$ रनटाइम होता है। इसलिए, ε मापदंड को उपयोग करके उन क्लस्टर्स के घनत्व को कम करने की आवश्यकता होती है जो अब और रुचिकर नहीं हैं, और एल्गोरिदम को तेजी से चलाने के लिए यह आवश्यक हैं।

यदि सख्त अर्थ में कहें, मापदंड ε आवश्यक नहीं है। यह सरल रूप से अधिकतम संभव मान पर सेट किया जा सकता है। यद्यपि, जब एक स्थानिक सूचकांक उपलब्ध होता है, तो यह जटिलता के संबंध में एक व्यावहारिक भूमिका निभाता है। ऑप्टिक्स को डीबीएससीएएन से पृथक होता है इस मापदंड को हटाकर, न्यूनतम से न्यूनतम एक्सटेंट तक, जहां केवल अधिकतम मान को देने की आवश्यकता होती है।

स्यूडोकोड

ऑप्टिक्स का मूल दृष्टिकोण डीबीएससीएएन के समान है, परंतु इसके स्थान पर जाने माने, परंतु अभी तक अप्रसंस्कृत क्लस्टर सदस्यों को एक सेट में रखने की अतिरिक्त, उन्हें प्राथमिकता कतार में रखा जाता है।

function OPTICS(DB, ε, MinPts) is
    for each point p of DB do

        p.reachability-distance = UNDEFINED
    डीबी के प्रत्येक असंसाधित बिंदु पी के लिए करें
        एन = गेटनेबर्स(पी, ε)
        पी को संसाधित के रूप में चिह्नित करें
        आदेशित सूची में आउटपुट पी
        यदि कोर-दूरी(p, ε, MinPts) != तब अपरिभाषित
            बीज = खाली प्राथमिकता कतार
            अद्यतन(एन, पी, बीज, ε, MinPts)
            बीजों में प्रत्येक अगले q के लिए करें
                एन' = गेटनेबर्स(क्यू, ε)
                q को संसाधित के रूप में चिह्नित करें
                आदेशित सूची में आउटपुट q
                यदि कोर-दूरी(q, ε, MinPts) != अपरिभाषित करें
                    अद्यतन(एन', क्यू, बीज, ε, MinPts)

अपडेट() में, प्राथमिकता कतार सीड्स को इसके साथ अपडेट किया जाता है $\varepsilon$ -के पड़ोस $p$ और $q$ , क्रमश:

फ़ंक्शन अद्यतन(एन, पी, बीज, ε, MinPts) है
    कोरेडिस्ट = कोर-दूरी(p, ε, MinPts)
    एन में प्रत्येक ओ के लिए
        यदि ओ संसाधित नहीं है तो
            न्यू-रीच-डिस्ट = अधिकतम(कोरेडिस्ट, डिस्ट्रिक्ट(पी,ओ))
            यदि o.reachability-distance == अपरिभाषित है तो // o बीजों में नहीं है
                ओ.पहुँच योग्यता-दूरी = नई-पहुँच-दूरी
                बीज.डालें(ओ, न्यू-पहुंच-जिला)
            अन्यथा // ओ बीज में, सुधार की जांच करें
                यदि new-reach-dist <o.reachability-distance तब
                    ओ.पहुँच योग्यता-दूरी = नई-पहुँच-दूरी
                    बीज.मूव-अप(ओ, न्यू-रीच-डिस्ट्रिक्ट)

इसलिए ऑप्टिक्स एक विशेष क्रम में बिंदुओं को आउटपुट करता है, जो उनकी सबसे छोटी रीचैबिलिटी दूरी के साथ एनोटेट होता है (मूल एल्गोरिदम में, कोर दूरी भी निर्यात की जाती है,परंतु आगे की प्रक्रिया के लिए इसकी आवश्यकता नहीं है)।

गुच्छों को निकालना

रीचैबिलिटी-प्लॉट (एक विशेष प्रकार का डेंड्रोग्राम) का उपयोग करके, समूहों की पदानुक्रमित संरचना आसानी से प्राप्त की जा सकती है। यह एक 2डी प्लॉट है, जिसमें एक्स-अक्ष पर ऑप्टिक्स द्वारा संसाधित बिंदुओं का क्रम और वाई-अक्ष पर पहुंच दूरी है। चूंकि समूह से संबंधित बिंदुओं की उनके निकटतम पड़ोसी से कम पहुंच दूरी होती है, इसलिए समूह पहुंच योग्य प्लॉट में घाटियों के रूप में दिखाई देते हैं। घाटी जितनी गहरी होगी, समूह उतना ही सघन होगा।

उपरोक्त छवि इस अवधारणा को दर्शाती है। इसके ऊपरी बाएँ क्षेत्र में, एक सिंथेटिक उदाहरण डेटा सेट दिखाया गया है। ऊपरी दायाँ भाग ऑप्टिक्स द्वारा निर्मित फैले हुए वृक्ष की कल्पना करता है, और निचला भाग ऑप्टिक्स द्वारा गणना की गई रीचैबिलिटी प्लॉट को दर्शाता है। इस प्लॉट में रंग लेबल हैं, और एल्गोरिथम द्वारा गणना नहीं की जाती हैं;परंतु यह अच्छी तरह से दिखाई देता है कि प्लॉट में घाटियाँ उपरोक्त डेटा सेट में समूहों से कैसे मेल खाती हैं। इस छवि में पीले बिंदुओं को शोर माना जाता है, और उनकी पहुंच योग्य प्लॉट में कोई घाटी नहीं पाई जाती है। पदानुक्रमित परिणाम में सर्वव्यापी सभी डेटा समूह को छोड़कर, उन्हें आमतौर पर समूहों को नहीं सौंपा जाता है।

दृश्य निरीक्षण के बाद एक्स-अक्ष पर एक सीमा का चयन करके, वाई-अक्ष पर एक सीमा का चयन करके इस प्लॉट से समूह निकालना मैन्युअल रूप से किया जा सकता है (नतीजा तब डीबीएससीएएन समूहिंग परिणाम के समान होता है) $\varepsilon$ और minPts मापदंड; यहां 0.1 का मान अच्छे परिणाम दे सकता है), या विभिन्न एल्गोरिदम द्वारा जो ढलान, घुटने का पता लगाने, या स्थानीय मैक्सिमा द्वारा घाटियों का पता लगाने का प्रयास करते हैं। इस तरह से प्राप्त समूहिंग आमतौर पर पदानुक्रमित समूहिंग होती है, और इसे एकल डीबीएससीएएन रन द्वारा प्राप्त नहीं किया जा सकता है।

जटिलता

डीबीएससीएएन की तरह, ऑप्टिक्स प्रत्येक बिंदु को एक बार संसाधित करता है, और पड़ोसियों के पास एक निश्चित-त्रिज्या निष्पादित करता है $\varepsilon$ -इस प्रसंस्करण के दौरान पड़ोस की क्वेरी। एक स्थानिक सूचकांक दिया गया है जो पड़ोस की क्वेरी प्रदान करता है $O(\log n)$ रनटाइम, का समग्र रनटाइम $O(n\cdot \log n)$ प्राप्त होना। मूल ऑप्टिक्स पेपर के लेखक डीबीएससीएएन की तुलना में 1.6 के वास्तविक निरंतर मंदी कारक की रिपोर्ट करते हैं। ध्यान दें कि का मूल्य $\varepsilon$ एल्गोरिथम की लागत पर भारी प्रभाव पड़ सकता है, क्योंकि बहुत बड़ा मूल्य पड़ोस की क्वेरी की लागत को रैखिक जटिलता तक बढ़ा सकता है।

विशेष रूप से, चुनना $\varepsilon >\max _{x,y}d(x,y)$ (डेटा सेट में अधिकतम दूरी से अधिक) संभव है,परंतु द्विघात जटिलता की ओर ले जाता है, क्योंकि प्रत्येक पड़ोस क्वेरी पूर्ण डेटा सेट लौटाती है। यहां तक कि जब कोई स्थानिक सूचकांक उपलब्ध नहीं होता है, तब भी ढेर के प्रबंधन में अतिरिक्त लागत आती है। इसलिए, $\varepsilon$ डेटा सेट के लिए उचित रूप से चुना जाना चाहिए।

एक्सटेंशन

ऑप्टिक्स-ऑफ^[4] ऑप्टिक्स पर आधारित एक विसंगति का पता लगाने वाला एल्गोरिदम है। मुख्य उपयोग एक अलग आउटलायर डिटेक्शन विधि का उपयोग करने की तुलना में कम लागत पर ऑप्टिक्स के मौजूदा रन से आउटलेर्स का निष्कर्षण है। स्थानीय बाह्य कारक का बेहतर ज्ञात संस्करण उन्हीं अवधारणाओं पर आधारित है।

डेली-क्लू,^[5] डेंसिटी-लिंक-समूहिंग सिंगल-लिंकेज समूहिंग और ऑप्टिक्स के विचारों को जोड़ती है, जिससे $\varepsilon$ मापदंड और ऑप्टिक्स की तुलना में प्रदर्शन में सुधार की पेशकश।

हायएससी^[6] ऑप्टिक्स पर आधारित एक पदानुक्रमित उप-स्थान समूहिंग (अक्ष-समानांतर) विधि है।

हाईसीओ^[7] ऑप्टिक्स पर आधारित एक पदानुक्रमित सहसंबंध समूहिंग एल्गोरिदम है।

व्यंजन^[8] HiSC पर एक सुधार है जो अधिक जटिल पदानुक्रम पा सकता है।

फोप्टिक्स^[9] यादृच्छिक अनुमानों का उपयोग करके तेज़ कार्यान्वयन है।

एचडीबीएसकैन*^[10] डीबीएससीएएन के परिशोधन पर आधारित है, जो समूहों से सीमा-बिंदुओं को बाहर करता है और इस प्रकार हार्टिगन द्वारा घनत्व-स्तरों की मूल परिभाषा का अधिक सख्ती से पालन करता है।^[11]

उपलब्धता

OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO और DiSH के जावा कार्यान्वयन ELKI में उपलब्ध हैं (कई दूरी के कार्यों के लिए सूचकांक त्वरण के साथ, और ξ निष्कर्षण विधि का उपयोग करके स्वचालित समूह निष्कर्षण के साथ)। अन्य जावा कार्यान्वयन में वेका (मशीन लर्निंग) एक्सटेंशन (ξ समूह निष्कर्षण के लिए कोई समर्थन नहीं) शामिल है।

GNU R पैकेज dbscan में केवल यूक्लिडियन दूरी के लिए सूचकांक त्वरण के लिए k-d ट्री का उपयोग करके OPTICS (पारंपरिक dbscan-जैसे और ξ समूह निष्कर्षण दोनों के साथ) का C++ कार्यान्वयन शामिल है।

ऑप्टिक्स का पायथन कार्यान्वयन PyClustering लाइब्रेरी और स्किकिट-लर्न में उपलब्ध है। Hडीबीएससीएएन* hdbscan लाइब्रेरी में उपलब्ध है।

संदर्भ

↑ Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (May 2011). "घनत्व-आधारित क्लस्टरिंग". Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30. S2CID 36920706.
↑ Mihael Ankerst; Markus M. Breunig; Hans-Peter Kriegel; Jörg Sander (1999). OPTICS: Ordering Points To Identify the Clustering Structure. ACM SIGMOD international conference on Management of data. ACM Press. pp. 49–60. CiteSeerX 10.1.1.129.6542.
↑ Martin Ester; Hans-Peter Kriegel; Jörg Sander; Xiaowei Xu (1996). Evangelos Simoudis; Jiawei Han; Usama M. Fayyad (eds.). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. CiteSeerX 10.1.1.71.1980. ISBN 1-57735-004-9.
↑ Markus M. Breunig; Hans-Peter Kriegel; Raymond T. Ng; Jörg Sander (1999). "OPTICS-OF: Identifying Local Outliers". Principles of Data Mining and Knowledge Discovery. Lecture Notes in Computer Science. Vol. 1704. Springer-Verlag. pp. 262–270. doi:10.1007/b72280. ISBN 978-3-540-66490-1. S2CID 27352458.
↑ Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". In Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 3918. Springer. pp. 119–128. doi:10.1007/11731139_16.
↑ Achtert, Elke; Böhm, Christian; Kriegel, Hans{-}Peter; Kröger, Peer; Müller{-}Gorman, Ina; Zimek, Arthur (2006). "Finding Hierarchies of Subspace Clusters". In Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Knowledge Discovery in Databases: PKDD 2006, 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4213. Springer. pp. 446–453. doi:10.1007/11871637_42.
↑ Achtert, E.; Böhm, C.; Kröger, P.; Zimek, A. (2006). सहसंबंध समूहों के खनन पदानुक्रम. pp. 119–128. CiteSeerX 10.1.1.707.7872. doi:10.1109/SSDBM.2006.35. ISBN 978-0-7695-2590-7. S2CID 2679909. {{cite book}}: |journal= ignored (help)
↑ Achtert, Elke; Böhm, Christian; Kriegel, Hans{-}Peter; Kröger, Peer; Müller{-}Gorman, Ina; Zimek, Arthur (2007). "Detection and Visualization of Subspace Cluster Hierarchies". In Ramamohanarao, Kotagiri; Krishna, P. Radha; Mohania, Mukesh K.; Nantajeewarawat, Ekawit (eds.). Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9-12, 2007, Proceedings. Lecture Notes in Computer Science. Vol. 4443. Springer. pp. 152–163. doi:10.1007/978-3-540-71703-4_15.
↑ Schneider, Johannes; Vlachos, Michail (2013). "यादृच्छिक अनुमानों के माध्यम से तेज़ पैरामीटर रहित घनत्व-आधारित क्लस्टरिंग". 22nd ACM International Conference on Information and Knowledge Management(CIKM).
↑ Campello, Ricardo J. G. B.; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg (22 July 2015). "डेटा क्लस्टरिंग, विज़ुअलाइज़ेशन और आउटलायर डिटेक्शन के लिए पदानुक्रमित घनत्व अनुमान". ACM Transactions on Knowledge Discovery from Data. 10 (1): 1–51. doi:10.1145/2733381. S2CID 2887636.
↑ J.A. Hartigan (1975). क्लस्टरिंग एल्गोरिदम. John Wiley & Sons.

[1] Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (May 2011). "घनत्व-आधारित क्लस्टरिंग". Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30. S2CID 36920706.

[:0-2] Mihael Ankerst; Markus M. Breunig; Hans-Peter Kriegel; Jörg Sander (1999). OPTICS: Ordering Points To Identify the Clustering Structure. ACM SIGMOD international conference on Management of data. ACM Press. pp. 49–60. CiteSeerX 10.1.1.129.6542.

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

[4] Markus M. Breunig; Hans-Peter Kriegel; Raymond T. Ng; Jörg Sander (1999). "OPTICS-OF: Identifying Local Outliers". Principles of Data Mining and Knowledge Discovery. Lecture Notes in Computer Science. Vol. 1704. Springer-Verlag. pp. 262–270. doi:10.1007/b72280. ISBN 978-3-540-66490-1. S2CID 27352458.

[5] Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". In Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 3918. Springer. pp. 119–128. doi:10.1007/11731139_16.

[6] Achtert, Elke; Böhm, Christian; Kriegel, Hans{-}Peter; Kröger, Peer; Müller{-}Gorman, Ina; Zimek, Arthur (2006). "Finding Hierarchies of Subspace Clusters". In Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Knowledge Discovery in Databases: PKDD 2006, 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4213. Springer. pp. 446–453. doi:10.1007/11871637_42.

[7] Achtert, E.; Böhm, C.; Kröger, P.; Zimek, A. (2006). सहसंबंध समूहों के खनन पदानुक्रम. pp. 119–128. CiteSeerX 10.1.1.707.7872. doi:10.1109/SSDBM.2006.35. ISBN 978-0-7695-2590-7. S2CID 2679909. {{cite book}}: |journal= ignored (help)

[8] Achtert, Elke; Böhm, Christian; Kriegel, Hans{-}Peter; Kröger, Peer; Müller{-}Gorman, Ina; Zimek, Arthur (2007). "Detection and Visualization of Subspace Cluster Hierarchies". In Ramamohanarao, Kotagiri; Krishna, P. Radha; Mohania, Mukesh K.; Nantajeewarawat, Ekawit (eds.). Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9-12, 2007, Proceedings. Lecture Notes in Computer Science. Vol. 4443. Springer. pp. 152–163. doi:10.1007/978-3-540-71703-4_15.

[9] Schneider, Johannes; Vlachos, Michail (2013). "यादृच्छिक अनुमानों के माध्यम से तेज़ पैरामीटर रहित घनत्व-आधारित क्लस्टरिंग". 22nd ACM International Conference on Information and Knowledge Management(CIKM).

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

[11] J.A. Hartigan (1975). क्लस्टरिंग एल्गोरिदम. John Wiley & Sons.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 3: / Line 3: @@
-क्लस्टरिंग संरचना की पहचान करने के लिए क्रम बिंदु (ओप्टिक्स) एक ऐसा एल्गोरिदम है जो स्थानिक डेटा में घनत्व-आधारित<ref>{{cite journal|last1=Kriegel|first1=Hans-Peter|last2=Kröger|first2=Peer|last3=Sander|first3=Jörg|last4=Zimek|first4=Arthur|title=घनत्व-आधारित क्लस्टरिंग|journal=Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery|date=May 2011|volume=1|issue=3|pages=231–240|doi=10.1002/widm.30|s2cid=36920706 |url=https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b}}</ref>  [[क्लस्टर विश्लेषण|क्लस्टर]] को खोजने के लिए उपयोगी है।यह एल्गोरिदम मिहाएल एंकर्स्ट, मार्कस एम. ब्रेयुनिग, [[हंस पीटर क्रिएगेल]] , और जोर्ग सैंडर द्वारा प्रस्तुत किया गया था।<ref name=":0">{{Cite conference
+समूहिंग संरचना की पहचान करने के लिए क्रम बिंदु (ओप्टिक्स) एक ऐसा एल्गोरिदम है जो स्थानिक डेटा में घनत्व-आधारित<ref>{{cite journal|last1=Kriegel|first1=Hans-Peter|last2=Kröger|first2=Peer|last3=Sander|first3=Jörg|last4=Zimek|first4=Arthur|title=घनत्व-आधारित क्लस्टरिंग|journal=Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery|date=May 2011|volume=1|issue=3|pages=231–240|doi=10.1002/widm.30|s2cid=36920706 |url=https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b}}</ref>  [[क्लस्टर विश्लेषण|समूह]] को खोजने के लिए उपयोगी है।यह एल्गोरिदम मिहाएल एंकर्स्ट, मार्कस एम. ब्रेयुनिग, [[हंस पीटर क्रिएगेल]] , और जोर्ग सैंडर द्वारा प्रस्तुत किया गया था।<ref name=":0">{{Cite conference
   |author=Mihael Ankerst |author2=Markus M. Breunig |author3=Hans-Peter Kriegel |author3-link=Hans-Peter Kriegel |author4=Jörg Sander
   | title = OPTICS: Ordering Points To Identify the Clustering Structure
@@ Line 23: / Line 23: @@
   | isbn = 1-57735-004-9
   | citeseerx = 10.1.1.71.1980
-  }}</ref>,परंतु यह डीबीएससीएएन की एक प्रमुख कमियों में से एक को पता करता है: भिन्न घनत्व वाले डेटा में मायने रखने वाले क्लस्टर्स का पता लगाने की समस्या होती हैं।इसके लिए, डेटाबेस के बिंदुओं ऐसे क्रमबद्ध किया जाता हैं कि जो स्थानिक रूप से निकटतम बिंदु होते हैं, वे क्रमबद्धीकरण में पड़ोसी बन जाते हैं।इसके अतिरिक्त, प्रत्येक बिंदु के लिए एक विशेष दूरी संग्रहीत की जाती है जो एक क्लस्टर के लिए स्वीकार्य घनत्व को प्रतिनिधित करती है, क्योंकी दोनों बिंदु एक ही क्लस्टर का हिस्सा बनें रहे। यह एक [[डेंड्रोग्राम]] के रूप में प्रतिष्ठित किया जाता है।
+  }}</ref>,परंतु यह डीबीएससीएएन की एक प्रमुख कमियों में से एक को पता करता है: भिन्न घनत्व वाले डेटा में मायने रखने वाले समूह्स का पता लगाने की समस्या होती हैं।इसके लिए, डेटाबेस के बिंदुओं ऐसे क्रमबद्ध किया जाता हैं कि जो स्थानिक रूप से निकटतम बिंदु होते हैं, वे क्रमबद्धीकरण में पड़ोसी बन जाते हैं।इसके अतिरिक्त, प्रत्येक बिंदु के लिए एक विशेष दूरी संग्रहीत की जाती है जो एक समूह के लिए स्वीकार्य घनत्व को प्रतिनिधित करती है, क्योंकी दोनों बिंदु एक ही समूह का हिस्सा बनें रहे। यह एक [[डेंड्रोग्राम]] के रूप में प्रतिष्ठित किया जाता है।
 ==मूलभूत विचार==
-डीबीएससीएएन की तरह, ऑप्टिक्स को दो मापदंडों की आवश्यकता होती है: ε, जो अधिकतम दूरी (रेडियस) का वर्णन करता है जिसे ध्यान में लेने के लिए, और {{mvar|मिनिप्ट्स,}}, जो क्लस्टर बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है।एक बिंदु p एक मुख्य बिंदु होता है अगर उसके ε-पड़ोस <math>N_\varepsilon(p)</math> में न्यूनतम से न्यूनतम {{mvar|मिनिप्ट्स,}} बिंदु पाए जाते हैं। डीबीएससीएएन के विपरीत, ऑप्टिक्स उन बिंदुओं पर भी विचार करता है जो अधिक सघनता से भरे क्लस्टर का हिस्सा हैं, इसलिए प्रत्येक बिंदु को एक मुख्य दूरी सौंपी जाती है जो  {{mvar|मिनिप्ट्स,}}वां निकटतम बिंदु के लिए दूरी का वर्णन करती है:
+डीबीएससीएएन की तरह, ऑप्टिक्स को दो मापदंडों की आवश्यकता होती है: ε, जो अधिकतम दूरी (रेडियस) का वर्णन करता है जिसे ध्यान में लेने के लिए, और {{mvar|मिनिप्ट्स,}}, जो समूह बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है।एक बिंदु p एक मुख्य बिंदु होता है अगर उसके ε-पड़ोस <math>N_\varepsilon(p)</math> में न्यूनतम से न्यूनतम {{mvar|मिनिप्ट्स,}} बिंदु पाए जाते हैं। डीबीएससीएएन के विपरीत, ऑप्टिक्स उन बिंदुओं पर भी विचार करता है जो अधिक सघनता से भरे समूह का हिस्सा हैं, इसलिए प्रत्येक बिंदु को एक मुख्य दूरी सौंपी जाती है जो  {{mvar|मिनिप्ट्स,}}वां निकटतम बिंदु के लिए दूरी का वर्णन करती है:
 :<math>\text{core-dist}_\mathit{\varepsilon,MinPts}(p)=
 \begin{cases}
@@ Line 32: / Line 32: @@
 \mathit{MinPts}\text{-th smallest distance in } N_\varepsilon(p) & \text{otherwise}
 \end{cases}</math>
-दूसरे बिंदु की पहुंच-योग्यता-दूरी {{mvar|o}} एक बिंदु से {{mvar|p}} या तो मध्य की दूरी है {{mvar|o}} और {{mvar|p}}, या की मूल दूरी {{mvar|p}}, जो भी बड़ा हो:
+एक दूसरे बिंदु {{mvar|o}} के रीचेबिलिटी-दूरी को एक बिंदु {{mvar|p}} से या तो {{mvar|o}} और {{mvar|p}} के मध्य की दूरी होती है, या {{mvar|p}} की कोर दूरी होती हैं, जो भी बड़ी होती है।
 :<math>\text{reachability-dist}_\mathit{\varepsilon,MinPts}(o,p) =
@@ Line 39: / Line 39: @@
 \max(\text{core-dist}_\mathit{\varepsilon,MinPts}(p), \text{dist}(p,o)) & \text{otherwise}
 \end{cases}</math>
-अगर {{mvar|p}} और {{mvar|o}} निकटतम पड़ोसी हैं, यह है <math>\varepsilon' < \varepsilon</math> हमें यह मानने की जरूरत है {{mvar|p}} और {{mvar|o}} एक ही क्लस्टर से संबंधित हैं।
+अगर {{mvar|p}} और {{mvar|o}} निकटतम पड़ोसी हैं, तो यही <math>\varepsilon' < \varepsilon</math> हमें मान लेना चाहिए कि {{mvar|p}} और {{mvar|o}} एक ही क्लस्टर का हिस्सा हैं।
-यदि कोई पर्याप्त सघन क्लस्टर नहीं है (w.r.t.) तो कोर-दूरी और रीचैबिलिटी-दूरी दोनों अपरिभाषित हैं। {{mvar|&epsilon;}}) उपलब्ध है। पर्याप्त रूप से बड़ा दिया गया {{mvar|&epsilon;}}, ऐसा कभी नहीं होता,परंतु फिर हर {{mvar|&epsilon;}}-नेबरहुड क्वेरी संपूर्ण डेटाबेस लौटाती है, जिसके परिणामस्वरूप <math>O(n^2)</math> रनटाइम. इसलिए {{mvar|&epsilon;}} उन समूहों के घनत्व को कम करने के लिए पैरामीटर की आवश्यकता होती है जो अब दिलचस्प नहीं हैं, और एल्गोरिदम को गति देने के लिए।
+यदि कोई पर्याप्त घनत्व वाला क्लस्टर (ε के संदर्भ में) उपलब्ध नहीं होता है, तो कोर दूरी और रीचेबिलिटी-दूरी अवर्णनीय होती हैं। पर्याप्त बड़े ε के लिए, यह कभी नहीं होता है, परंतु तब हर ε-नेबरहुड क्वेरी संपूर्ण डेटाबेस लौटाती है, जिससे <math>O(n^2)</math> रनटाइम होता है। इसलिए, ε मापदंड को उपयोग करके उन क्लस्टर्स के घनत्व को कम करने की आवश्यकता होती है जो अब और रुचिकर नहीं हैं, और एल्गोरिदम को तेजी से चलाने के लिए यह आवश्यक हैं।
-पैरामीटर {{mvar|&epsilon;}} सच कहूँ तो, आवश्यक नहीं है। इसे बस अधिकतम संभव मान पर सेट किया जा सकता है। हालाँकि, जब कोई स्थानिक सूचकांक उपलब्ध होता है, तो यह जटिलता के संबंध में एक व्यावहारिक भूमिका निभाता है। इस पैरामीटर को हटाकर ऑप्टिक्स को डीबीएससीएएन से कम से कम केवल अधिकतम मूल्य देने की सीमा तक सार निकाला जाता है।
+यदि सख्त अर्थ में कहें, मापदंड ε आवश्यक नहीं है। यह सरल रूप से अधिकतम संभव मान पर सेट किया जा सकता है। यद्यपि, जब एक स्थानिक सूचकांक उपलब्ध होता है, तो यह जटिलता के संबंध में एक व्यावहारिक भूमिका निभाता है। ऑप्टिक्स को डीबीएससीएएन से पृथक होता है इस मापदंड को हटाकर, न्यूनतम से न्यूनतम एक्सटेंट तक, जहां केवल अधिकतम मान को देने की आवश्यकता होती है।
-==छद्मकोड==
+==स्यूडोकोड ==
-ऑप्टिक्स का मूल दृष्टिकोण डीबीएससीएएन के समान है,परंतु एक सेट में ज्ञात,परंतु अब तक असंसाधित क्लस्टर सदस्यों को बनाए रखने के बजाय, उन्हें [[प्राथमिकता कतार]] में बनाए रखा जाता है (उदाहरण के लिए अनुक्रमित हीप (डेटा संरचना) का उपयोग करना)।
+ऑप्टिक्स का मूल दृष्टिकोण डीबीएससीएएन के समान है, परंतु इसके स्थान पर जाने माने, परंतु अभी तक अप्रसंस्कृत क्लस्टर सदस्यों को एक सेट में रखने की अतिरिक्त, उन्हें [[प्राथमिकता कतार]] में रखा जाता है।
-  फ़ंक्शन ऑप्टिक्स(DB, ε, MinPts) है
+  '''function''' OPTICS(DB, ε, MinPts) '''is'''
-      DB के प्रत्येक बिंदु p के लिए करें
+      '''for each''' point p of DB '''do'''
-          पी.पहुँच योग्यता-दूरी = अपरिभाषित
+          p.reachability-distance = UNDEFINED
       डीबी के प्रत्येक असंसाधित बिंदु पी के लिए करें
           एन = गेटनेबर्स(पी, ε)
@@ Line 64: / Line 65: @@
                   यदि कोर-दूरी(q, ε, MinPts) != अपरिभाषित करें
                       अद्यतन(एन', क्यू, बीज, ε, MinPts)
 अपडेट() में, प्राथमिकता कतार सीड्स को इसके साथ अपडेट किया जाता है <math>\varepsilon</math>-के पड़ोस <math>p</math> और <math>q</math>, क्रमश:
@@ Line 83: / Line 83: @@
 ==गुच्छों को निकालना==
-[[File:OPTICS.svg]]रीचैबिलिटी-प्लॉट (एक विशेष प्रकार का डेंड्रोग्राम) का उपयोग करके, समूहों की पदानुक्रमित संरचना आसानी से प्राप्त की जा सकती है। यह एक 2डी प्लॉट है, जिसमें एक्स-अक्ष पर ऑप्टिक्स द्वारा संसाधित बिंदुओं का क्रम और वाई-अक्ष पर पहुंच दूरी है। चूंकि क्लस्टर से संबंधित बिंदुओं की उनके निकटतम पड़ोसी से कम पहुंच दूरी होती है, इसलिए क्लस्टर पहुंच योग्य प्लॉट में घाटियों के रूप में दिखाई देते हैं। घाटी जितनी गहरी होगी, समूह उतना ही सघन होगा।
+[[File:OPTICS.svg]]रीचैबिलिटी-प्लॉट (एक विशेष प्रकार का डेंड्रोग्राम) का उपयोग करके, समूहों की पदानुक्रमित संरचना आसानी से प्राप्त की जा सकती है। यह एक 2डी प्लॉट है, जिसमें एक्स-अक्ष पर ऑप्टिक्स द्वारा संसाधित बिंदुओं का क्रम और वाई-अक्ष पर पहुंच दूरी है। चूंकि समूह से संबंधित बिंदुओं की उनके निकटतम पड़ोसी से कम पहुंच दूरी होती है, इसलिए समूह पहुंच योग्य प्लॉट में घाटियों के रूप में दिखाई देते हैं। घाटी जितनी गहरी होगी, समूह उतना ही सघन होगा।
-उपरोक्त छवि इस अवधारणा को दर्शाती है। इसके ऊपरी बाएँ क्षेत्र में, एक सिंथेटिक उदाहरण डेटा सेट दिखाया गया है। ऊपरी दायाँ भाग ऑप्टिक्स द्वारा निर्मित फैले हुए वृक्ष की कल्पना करता है, और निचला भाग ऑप्टिक्स द्वारा गणना की गई रीचैबिलिटी प्लॉट को दर्शाता है। इस प्लॉट में रंग लेबल हैं, और एल्गोरिथम द्वारा गणना नहीं की जाती हैं;परंतु यह अच्छी तरह से दिखाई देता है कि प्लॉट में घाटियाँ उपरोक्त डेटा सेट में समूहों से कैसे मेल खाती हैं। इस छवि में पीले बिंदुओं को शोर माना जाता है, और उनकी पहुंच योग्य प्लॉट में कोई घाटी नहीं पाई जाती है। पदानुक्रमित परिणाम में सर्वव्यापी सभी डेटा क्लस्टर को छोड़कर, उन्हें आमतौर पर क्लस्टरों को नहीं सौंपा जाता है।
+उपरोक्त छवि इस अवधारणा को दर्शाती है। इसके ऊपरी बाएँ क्षेत्र में, एक सिंथेटिक उदाहरण डेटा सेट दिखाया गया है। ऊपरी दायाँ भाग ऑप्टिक्स द्वारा निर्मित फैले हुए वृक्ष की कल्पना करता है, और निचला भाग ऑप्टिक्स द्वारा गणना की गई रीचैबिलिटी प्लॉट को दर्शाता है। इस प्लॉट में रंग लेबल हैं, और एल्गोरिथम द्वारा गणना नहीं की जाती हैं;परंतु यह अच्छी तरह से दिखाई देता है कि प्लॉट में घाटियाँ उपरोक्त डेटा सेट में समूहों से कैसे मेल खाती हैं। इस छवि में पीले बिंदुओं को शोर माना जाता है, और उनकी पहुंच योग्य प्लॉट में कोई घाटी नहीं पाई जाती है। पदानुक्रमित परिणाम में सर्वव्यापी सभी डेटा समूह को छोड़कर, उन्हें आमतौर पर समूहों को नहीं सौंपा जाता है।
-दृश्य निरीक्षण के बाद एक्स-अक्ष पर एक सीमा का चयन करके, वाई-अक्ष पर एक सीमा का चयन करके इस प्लॉट से क्लस्टर निकालना मैन्युअल रूप से किया जा सकता है (नतीजा तब डीबीएससीएएन क्लस्टरिंग परिणाम के समान होता है) <math>\varepsilon</math> और {{not a typo|minPts}} पैरामीटर; यहां 0.1 का मान अच्छे परिणाम दे सकता है), या विभिन्न एल्गोरिदम द्वारा जो ढलान, घुटने का पता लगाने, या स्थानीय मैक्सिमा द्वारा घाटियों का पता लगाने का प्रयास करते हैं। इस तरह से प्राप्त क्लस्टरिंग आमतौर पर [[पदानुक्रमित क्लस्टरिंग]] होती है, और इसे एकल डीबीएससीएएन रन द्वारा प्राप्त नहीं किया जा सकता है।
+दृश्य निरीक्षण के बाद एक्स-अक्ष पर एक सीमा का चयन करके, वाई-अक्ष पर एक सीमा का चयन करके इस प्लॉट से समूह निकालना मैन्युअल रूप से किया जा सकता है (नतीजा तब डीबीएससीएएन समूहिंग परिणाम के समान होता है) <math>\varepsilon</math> और {{not a typo|minPts}} मापदंड; यहां 0.1 का मान अच्छे परिणाम दे सकता है), या विभिन्न एल्गोरिदम द्वारा जो ढलान, घुटने का पता लगाने, या स्थानीय मैक्सिमा द्वारा घाटियों का पता लगाने का प्रयास करते हैं। इस तरह से प्राप्त समूहिंग आमतौर पर [[पदानुक्रमित क्लस्टरिंग|पदानुक्रमित समूहिंग]] होती है, और इसे एकल डीबीएससीएएन रन द्वारा प्राप्त नहीं किया जा सकता है।
 ==जटिलता==
@@ Line 124: / Line 124: @@
   | title = Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings
   | volume = 3918
-  | year = 2006}}</ref> डेंसिटी-लिंक-क्लस्टरिंग [[सिंगल-लिंकेज क्लस्टरिंग]] और ऑप्टिक्स के विचारों को जोड़ती है, जिससे <math>\varepsilon</math> पैरामीटर और ऑप्टिक्स की तुलना में प्रदर्शन में सुधार की पेशकश।
+  | year = 2006}}</ref> डेंसिटी-लिंक-समूहिंग [[सिंगल-लिंकेज क्लस्टरिंग|सिंगल-लिंकेज समूहिंग]] और ऑप्टिक्स के विचारों को जोड़ती है, जिससे <math>\varepsilon</math> मापदंड और ऑप्टिक्स की तुलना में प्रदर्शन में सुधार की पेशकश।
 हायएससी<ref>{{cite conference
@@ Line 144: / Line 144: @@
   | volume = 4213
   | year = 2006| doi-access = free
-  }}</ref> ऑप्टिक्स पर आधारित एक पदानुक्रमित [[उप-स्थान क्लस्टरिंग]] (अक्ष-समानांतर) विधि है।
+  }}</ref> ऑप्टिक्स पर आधारित एक पदानुक्रमित [[उप-स्थान क्लस्टरिंग|उप-स्थान समूहिंग]] (अक्ष-समानांतर) विधि है।
-हाईसीओ<ref>{{Cite book| doi = 10.1109/SSDBM.2006.35| isbn = 978-0-7695-2590-7| title = सहसंबंध समूहों के खनन पदानुक्रम| year = 2006| last1 = Achtert | first1 = E.| last2 = Böhm | first2 = C.| last3 = Kröger | first3 = P.| last4 = Zimek | first4 = A.| pages = 119–128| journal = Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM)| citeseerx = 10.1.1.707.7872| s2cid = 2679909}}</ref> ऑप्टिक्स पर आधारित एक पदानुक्रमित [[सहसंबंध क्लस्टरिंग]] एल्गोरिदम है।
+हाईसीओ<ref>{{Cite book| doi = 10.1109/SSDBM.2006.35| isbn = 978-0-7695-2590-7| title = सहसंबंध समूहों के खनन पदानुक्रम| year = 2006| last1 = Achtert | first1 = E.| last2 = Böhm | first2 = C.| last3 = Kröger | first3 = P.| last4 = Zimek | first4 = A.| pages = 119–128| journal = Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM)| citeseerx = 10.1.1.707.7872| s2cid = 2679909}}</ref> ऑप्टिक्स पर आधारित एक पदानुक्रमित [[सहसंबंध क्लस्टरिंग|सहसंबंध समूहिंग]] एल्गोरिदम है।
 व्यंजन<ref>{{cite conference
@@ Line 174: / Line 174: @@
 ==उपलब्धता==
-OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO और DiSH के जावा कार्यान्वयन [[ELKI]] में उपलब्ध हैं (कई दूरी के कार्यों के लिए सूचकांक त्वरण के साथ, और ξ निष्कर्षण विधि का उपयोग करके स्वचालित क्लस्टर निष्कर्षण के साथ)। अन्य जावा कार्यान्वयन में [[वेका (मशीन लर्निंग)]] एक्सटेंशन (ξ क्लस्टर निष्कर्षण के लिए कोई समर्थन नहीं) शामिल है।
+OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO और DiSH के जावा कार्यान्वयन [[ELKI]] में उपलब्ध हैं (कई दूरी के कार्यों के लिए सूचकांक त्वरण के साथ, और ξ निष्कर्षण विधि का उपयोग करके स्वचालित समूह निष्कर्षण के साथ)। अन्य जावा कार्यान्वयन में [[वेका (मशीन लर्निंग)]] एक्सटेंशन (ξ समूह निष्कर्षण के लिए कोई समर्थन नहीं) शामिल है।
-[[GNU R]] पैकेज dbscan में केवल यूक्लिडियन दूरी के लिए सूचकांक त्वरण के लिए k-d ट्री का उपयोग करके OPTICS (पारंपरिक dbscan-जैसे और ξ क्लस्टर निष्कर्षण दोनों के साथ) का C++ कार्यान्वयन शामिल है।
+[[GNU R]] पैकेज dbscan में केवल यूक्लिडियन दूरी के लिए सूचकांक त्वरण के लिए k-d ट्री का उपयोग करके OPTICS (पारंपरिक dbscan-जैसे और ξ समूह निष्कर्षण दोनों के साथ) का C++ कार्यान्वयन शामिल है।
 ऑप्टिक्स का पायथन कार्यान्वयन [https://pyclustering.github.io/ PyClustering] लाइब्रेरी और [[स्किकिट-लर्न]] में उपलब्ध है। Hडीबीएससीएएन* [https://hdbscan.readthedocs.io/ hdbscan] लाइब्रेरी में उपलब्ध है।

Anonymous

Search

प्रकाशिकी एल्गोरिथ्म: Difference between revisions

Namespaces

More

Page actions

Revision as of 16:57, 25 July 2023

Contents

मूलभूत विचार

स्यूडोकोड

गुच्छों को निकालना

जटिलता

एक्सटेंशन

उपलब्धता

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

प्रकाशिकी एल्गोरिथ्म: Difference between revisions

Revision as of 16:57, 25 July 2023

मूलभूत विचार

स्यूडोकोड

गुच्छों को निकालना

जटिलता

एक्सटेंशन

उपलब्धता

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories