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

Latest revision as of 13:16, 3 August 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 ऑप्टिक्स(DB, ε, MinPts) is
    for each point p of DB do

        p.reachability-distance = UNDEFINED
    for each unprocessed point p of DB do
        N = getNeighbors(p, ε)
        mark p as processed
        output p to the ordered list
        if core-distance(p, ε, MinPts) != UNDEFINED then
            Seeds = empty priority queue
            update(N, p, Seeds, ε, MinPts)
            for each next q in Seeds do
                 N' = getNeighbors(q, ε)
                 mark q as processedरें
                 output q to the ordered list
                 if core-distance(q, ε, MinPts) != UNDEFINED do
                    update(N', q, Seeds, ε, MinPts)

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

function update(N, p, Seeds, ε, MinPts) is
    coredist = core-distance(p, ε, MinPts)
    for each o in N
        if o is not processed then
            new-reach-dist = max(coredist, dist(p,o))
            if o.reachability-distance == UNDEFINED then // o is not in Seeds
                o.reachability-distance = new-reach-dist
                Seeds.insert(o, new-reach-dist)
            else               // o in Seeds, check for improvement
                if new-reach-dist < o.reachability-distance then
                    o.reachability-distance = new-reach-dist
                    Seeds.move-up(o, new-reach-dist)

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

क्लस्टर्स को निकालना

रीचैबिलिटी-प्लॉट (एक विशेष प्रकार का डेंड्रोग्राम) का उपयोग करके,

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

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

इस प्लॉट से क्लस्टर्स को निकालने के लिए, इसे विज़ुअल निरीक्षण के उपरांत x-अक्ष पर रेंज का चयन करके हाथ से किया जा सकता है, y-अक्ष पर एक थ्रेशोल्ड चयन करके (परिणाम फिर एक डीबीएससीएएन क्लस्टरिंग परिणाम के समान होता है जिसमें एक समान $\varepsilon$ और मिनिप्ट्स,मापदंड होते हैं; यहां एक 0.1 की मान अच्छे परिणाम देने के लिए उत्तम सिद्ध हो सकती है), या विभिन्न एल्गोरिदम्स द्वारा जो धरा, घुटन डिटेक्शन या स्थानिक अधिकतमों के माध्यम से वैलीज़ का पता लगाने का प्रयास करते हैं। इस तरह प्राप्त किए गए क्लस्टरिंग सामान्यतः वृद्धिकीय होते हैं, और इन्हें एकल डीबीएससीएएन चलने से प्राप्त नहीं किया जा सकता हैं।

जटिलता

डीबीएससीएएन की तरह, ऑप्टिक्स भी प्रत्येक बिंदु को एक बार प्रोसेस करता है और इस प्रोसेसिंग के दौरान एक ε-पड़ोसी क्वेरी का निष्पादन करता है। यदि किसी स्थानिक सूचकांक के साथ ε-पड़ोसी क्वेरी को $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] हाईएससी पर एक सुधार है जो अधिक जटिल पदानुक्रम पा सकता है।

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

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

उपलब्धता

ओप्टिक्स, ओप्टिक्स-ओएफ, डीली-क्लू, हिस्क, हिको और डिश के जावा अनुमानित कार्यनीतियों के विभिन्न प्रस्तावनाएँ ईएलकी डेटा माइनिंग फ्रेमवर्क में उपलब्ध हैं (जिनमें कई दूरी फंक्शनों के लिए इंडेक्स त्वरण और जिएक्स निकासी विधि का स्वचालित क्लस्टर निकालने का समर्थन किया गया है)। अन्य जावा प्रस्तावनाएँ में वेका एक्सटेंशन सम्मिलित है (जिसमें जिएक्स क्लस्टर निकासी के लिए समर्थन नहीं है)।

आर पैकेज "dbscan" में ऑप्टिक्स का एक C++ प्रस्तावना सम्मिलित है (जिसमें रस्त्रीय डीबीस्कैन जैसे और जिएक्स क्लस्टर निकासी दोनों हैं) जिसमें केवल यूक्लिड दूरी के लिए इंडेक्स त्वरण के लिए के-डी ट्री का उपयोग होता है।

ऑप्टिक्स के पायथन अनुमानित कार्यनीतियाँ पायथन में पाइक्लस्टरिंग और स्किकिट-लर्न पुस्तकालय में उपलब्ध हैं। एचडीबीएसकैन* एचडीबीएसकैन पुस्तकालय में उपलब्ध है।

संदर्भ

↑ 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 2: / Line 2: @@
 {{Machine learning|Clustering}}
+समूहिंग संरचना की पहचान करने के लिए क्रम बिंदु ('''ओप्टिक्स''') एक ऐसा '''एल्गोरिदम''' है जो स्थानिक डेटा में घनत्व-आधारित<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 11: / Line 10: @@
   | publisher = [[ACM Press]]
   | citeseerx = 10.1.1.129.6542
-  }}</ref>इसकी मूल विचारधारा [[DBSCAN|डीबीएससीएएन]] के समान है<ref>{{Cite conference
+  }}</ref> इसकी मूल विचारधारा [[DBSCAN|डीबीएससीएएन]] के समान है<ref>{{Cite conference
   |author=Martin Ester
   |author-link=Martin Ester
@@ Line 23: / Line 22: @@
   | isbn = 1-57735-004-9
   | citeseerx = 10.1.1.71.1980
-  }}</ref>,परंतु यह डीबीएससीएएन की एक प्रमुख कमियों में से एक को पता करता है: भिन्न घनत्व वाले डेटा में मायने रखने वाले क्लस्टर्स का पता लगाने की समस्या होती हैं।इसके लिए, डेटाबेस के बिंदुओं ऐसे क्रमबद्ध किया जाता हैं कि जो स्थानिक रूप से निकटतम बिंदु होते हैं, वे क्रमबद्धीकरण में पड़ोसी बन जाते हैं।इसके अतिरिक्त, प्रत्येक बिंदु के लिए एक विशेष दूरी संग्रहीत की जाती है जो एक क्लस्टर के लिए स्वीकार्य घनत्व को प्रतिनिधित करती है, क्योंकी दोनों बिंदु एक ही क्लस्टर का हिस्सा बनें रहे। यह एक [[डेंड्रोग्राम]] के रूप में प्रतिष्ठित किया जाता है।
+  }}</ref>,परंतु यह डीबीएससीएएन की एक प्रमुख कमियों में से एक को पता करता है: भिन्न घनत्व वाले डेटा में मायने रखने वाले समूह्स का पता लगाने की समस्या होती हैं।इसके लिए, डेटाबेस के बिंदुओं ऐसे क्रमबद्ध किया जाता हैं कि जो स्थानिक रूप से निकटतम बिंदु होते हैं, वे क्रमबद्धीकरण में पड़ोसी बन जाते हैं।इसके अतिरिक्त, प्रत्येक बिंदु के लिए एक विशेष दूरी संग्रहीत की जाती है जो एक समूह के लिए स्वीकार्य घनत्व को प्रतिनिधित करती है, क्योंकी दोनों बिंदु एक ही समूह का हिस्सा बनें रहे। यह एक [[डेंड्रोग्राम]] के रूप में प्रतिष्ठित किया जाता है।
-==बुनियादी विचार==
-डीबीएससीएएन की तरह, ऑप्टिक्स को दो मापदंडों की आवश्यकता होती है: {{mvar|&epsilon;}}, जो विचार करने योग्य अधिकतम दूरी (त्रिज्या) का वर्णन करता है,
-डीबीएससीएएन की तरह, ऑप्टिक्स को दो पैरामीटरों की आवश्यकता होती है: ε, जो अधिकतम दूरी (रेडियस) का वर्णन करता है जिसे ध्यान में लेने के लिए, और मिनिप्ट्स, जो क्लस्टर बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है।
-और {{mvar|मिनिप्ट्स,}}, एक क्लस्टर बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है। एक बिंदु {{mvar|p}} यदि कम से कम एक मुख्य बिंदु है {{mvar|मिनिप्ट्स,}} इसके अंदर अंक पाए जाते हैं {{mvar|&epsilon;}}-अड़ोस-पड़ोस <math>N_\varepsilon(p)</math> (बिंदु सहित {{mvar|p}} अपने आप)। डीबीएससीएएन के विपरीत, ऑप्टिक्स उन बिंदुओं पर भी विचार करता है जो अधिक सघनता से भरे क्लस्टर का हिस्सा हैं, इसलिए प्रत्येक बिंदु को एक मुख्य दूरी सौंपी जाती है जो दूरी का वर्णन करती है {{mvar|मिनिप्ट्स,}}वां निकटतम बिंदु:
-<!-- beware of line lengths for small screens -->
+==मूलभूत विचार==
+डीबीएससीएएन की तरह, ऑप्टिक्स को दो मापदंडों की आवश्यकता होती है: ε, जो अधिकतम दूरी (रेडियस) का वर्णन करता है जिसे ध्यान में लेने के लिए, और {{mvar|मिनिप्ट्स,}}, जो समूह बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है।एक बिंदु p एक मुख्य बिंदु होता है अगर उसके ε-पड़ोस <math>N_\varepsilon(p)</math> में न्यूनतम से न्यूनतम {{mvar|मिनिप्ट्स,}} बिंदु पाए जाते हैं। डीबीएससीएएन के विपरीत, ऑप्टिक्स उन बिंदुओं पर भी विचार करता है जो अधिक सघनता से भरे समूह का हिस्सा हैं, इसलिए प्रत्येक बिंदु को एक मुख्य दूरी सौंपी जाती है जो  {{mvar|मिनिप्ट्स,}}वां निकटतम बिंदु के लिए दूरी का वर्णन करती है:
 :<math>\text{core-dist}_\mathit{\varepsilon,MinPts}(p)=
 \begin{cases}
@@ Line 39: / Line 31: @@
 \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}} की कोर दूरी होती हैं, जो भी बड़ी होती है।
-<!-- beware of line lengths for small screens -->
 :<math>\text{reachability-dist}_\mathit{\varepsilon,MinPts}(o,p) =
 \begin{cases}
@@ Line 47: / Line 38: @@
 \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''' ऑप्टिक्स(DB, ε, MinPts) '''is'''
-      DB के प्रत्येक बिंदु p के लिए करें
+      '''for each''' point p of DB '''do'''
-         पी.पहुँच योग्यता-दूरी = अपरिभाषित
-     डीबी के प्रत्येक असंसाधित बिंदु पी के लिए करें
-         एन = गेटनेबर्स(पी, ε)
-         पी को संसाधित के रूप में चिह्नित करें
-         आदेशित सूची में आउटपुट पी
-         यदि कोर-दूरी(p, ε, MinPts) != तब अपरिभाषित
-             बीज = खाली प्राथमिकता कतार
-             अद्यतन(एन, पी, बीज, ε, MinPts)
-             बीजों में प्रत्येक अगले q के लिए करें
-                 एन' = गेटनेबर्स(क्यू, ε)
-                 q को संसाधित के रूप में चिह्नित करें
-                 आदेशित सूची में आउटपुट q
-                 यदि कोर-दूरी(q, ε, MinPts) != अपरिभाषित करें
-                     अद्यतन(एन', क्यू, बीज, ε, MinPts)
-अपडेट() में, प्राथमिकता कतार सीड्स को इसके साथ अपडेट किया जाता है <math>\varepsilon</math>-के पड़ोस <math>p</math> और <math>q</math>, क्रमश:
+         p.reachability-distance = UNDEFINED
+     '''for each''' unprocessed point p of DB '''do'''
+         N = getNeighbors(p, ε)
+         mark p as processed
+         output p to the ordered list
+         '''if''' core-distance(p, ε, MinPts) != UNDEFINED '''then'''
+             Seeds = empty priority queue
+             update(N, p, Seeds, ε, MinPts)
+             '''for each''' next q in Seeds '''do'''
+                  N' = getNeighbors(q, ε)
+                  mark q as processedरें
+                  output q to the ordered list
+                  '''if''' core-distance(q, ε, MinPts) != UNDEFINED '''do'''
+                     update(N', q, Seeds, ε, MinPts)
+अपडेट() के दौरान, प्राथमिकता कतार (प्रायोरिटी क्यू) "सीड्स" को <math>p</math> और <math>q</math> के <math>\varepsilon</math>-पड़ोस में से अपडेट किया जाता है:
-  फ़ंक्शन अद्यतन(एन, पी, बीज, ε, MinPts) है
+  '''function''' update(N, p, Seeds, ε, MinPts) '''is'''
-      कोरेडिस्ट = कोर-दूरी(p, ε, MinPts)
+      coredist = core-distance(p, ε, MinPts)
-      एन में प्रत्येक ओ के लिए
+      '''for each''' o in N
-          यदि ओ संसाधित नहीं है तो
+          '''if''' o is not processed '''then'''
-              न्यू-रीच-डिस्ट = अधिकतम(कोरेडिस्ट, डिस्ट्रिक्ट(पी,ओ))
+              new-reach-dist = max(coredist, dist(p,o))
-              यदि o.reachability-distance == अपरिभाषित है तो // o बीजों में नहीं है
+              '''if''' o.reachability-distance == UNDEFINED '''then''' // o is not in Seeds
-                  ओ.पहुँच योग्यता-दूरी = नई-पहुँच-दूरी
+                  o.reachability-distance = new-reach-dist
-                  बीज.डालें(ओ, न्यू-पहुंच-जिला)
+                  Seeds.insert(o, new-reach-dist)
-              अन्यथा // ओ बीज में, सुधार की जांच करें
+              '''else'''               // o in Seeds, check for improvement
-                  यदि new-reach-dist <o.reachability-distance तब
+                  '''if''' new-reach-dist < o.reachability-distance '''then'''
-                      ओ.पहुँच योग्यता-दूरी = नई-पहुँच-दूरी
+                      o.reachability-distance = new-reach-dist
-                      बीज.मूव-अप(ओ, न्यू-रीच-डिस्ट्रिक्ट)
+                      Seeds.move-up(o, new-reach-dist)
 इसलिए ऑप्टिक्स एक विशेष क्रम में बिंदुओं को आउटपुट करता है, जो उनकी सबसे छोटी रीचैबिलिटी दूरी के साथ एनोटेट होता है (मूल एल्गोरिदम में, कोर दूरी भी निर्यात की जाती है,परंतु आगे की प्रक्रिया के लिए इसकी आवश्यकता नहीं है)।
-==गुच्छों को निकालना==
+==क्लस्टर्स को निकालना==
-[[File:OPTICS.svg]]रीचैबिलिटी-प्लॉट (एक विशेष प्रकार का डेंड्रोग्राम) का उपयोग करके, समूहों की पदानुक्रमित संरचना आसानी से प्राप्त की जा सकती है। यह एक 2डी प्लॉट है, जिसमें एक्स-अक्ष पर ऑप्टिक्स द्वारा संसाधित बिंदुओं का क्रम और वाई-अक्ष पर पहुंच दूरी है। चूंकि क्लस्टर से संबंधित बिंदुओं की उनके निकटतम पड़ोसी से कम पहुंच दूरी होती है, इसलिए क्लस्टर पहुंच योग्य प्लॉट में घाटियों के रूप में दिखाई देते हैं। घाटी जितनी गहरी होगी, समूह उतना ही सघन होगा।
+[[File:OPTICS.svg]]रीचैबिलिटी-प्लॉट (एक विशेष प्रकार का डेंड्रोग्राम) का उपयोग करके,
+रीचेबिलिटी प्लॉट का उपयोग करके (एक विशेष प्रकार के डेन्ड्रोग्राम), क्लस्टर्स के वृद्धिकीय संरचना को आसानी से प्राप्त किया जा सकता है। यह एक 2D प्लॉट है, जिसमें ऑप्टिक्स द्वारा प्रसंस्कृत किए जाने वाले बिंदुओं के क्रमबद्धीकरण को x-अक्ष पर और रीचेबिलिटी दूरी को y-अक्ष पर दर्शाया जाता है। क्योंकि क्लस्टर्स में सम्मिलित बिंदुओं के पास उनके निकटतम पड़ोसी तक की दूरी बहुत न्यूनतम होती है, इसलिए रीचेबिलिटी प्लॉट में क्लस्टर्स वैलीज़ के रूप में प्रकट होते हैं। जितनी गहरी वैली, उतना ही घना या समृद्ध क्लस्टर होता है।
-उपरोक्त छवि इस अवधारणा को दर्शाती है। इसके ऊपरी बाएँ क्षेत्र में, एक सिंथेटिक उदाहरण डेटा सेट दिखाया गया है। ऊपरी दायाँ भाग ऑप्टिक्स द्वारा निर्मित फैले हुए वृक्ष की कल्पना करता है, और निचला भाग ऑप्टिक्स द्वारा गणना की गई रीचैबिलिटी प्लॉट को दर्शाता है। इस प्लॉट में रंग लेबल हैं, और एल्गोरिथम द्वारा गणना नहीं की जाती हैं;परंतु यह अच्छी तरह से दिखाई देता है कि प्लॉट में घाटियाँ उपरोक्त डेटा सेट में समूहों से कैसे मेल खाती हैं। इस छवि में पीले बिंदुओं को शोर माना जाता है, और उनकी पहुंच योग्य प्लॉट में कोई घाटी नहीं पाई जाती है। पदानुक्रमित परिणाम में सर्वव्यापी सभी डेटा क्लस्टर को छोड़कर, उन्हें आमतौर पर क्लस्टरों को नहीं सौंपा जाता है।
+ऊपर दिए गए चित्र में इस संकेत का वर्णन है। इसमें ऊपर के बाएं कोने में, एक सिंथेटिक उदाहरण डेटा सेट दर्शाया गया है। ऊपर के दाएं हिस्से में, ऑप्टिक्स द्वारा उत्पन्न किया गया स्पैनिंग ट्री का दृश्य दर्शाया गया है, और नीचे का हिस्सा ऑप्टिक्स द्वारा गणना किए गए रीचेबिलिटी प्लॉट को दिखाता है। इस प्लॉट में रंग स्तर हैं, और इन्हें एल्गोरिदम द्वारा नहीं गणा गया है; लेकिन यह अच्छी तरह से दिखाता है कि प्लॉट में वैलीज़ किस तरह से ऊपर वाले डेटा सेट के क्लस्टर्स के साथ संबंधित होते हैं। इस चित्र में पीले बिंदुओं को नॉइज़ माना जाता है, और उनके रीचेबिलिटी प्लॉट में कोई वैली नहीं मिलती हैं। उन्हें सामान्यतः क्लस्टर्स के साथ संलग्न नहीं किया जाता है, केवल एक व्यावसायिक परिणाम में सर्वव्यापी "सभी डेटा" क्लस्टर के साथ नही जोड़ा जाता हैं।
-दृश्य निरीक्षण के बाद एक्स-अक्ष पर एक सीमा का चयन करके, वाई-अक्ष पर एक सीमा का चयन करके इस प्लॉट से क्लस्टर निकालना मैन्युअल रूप से किया जा सकता है (नतीजा तब डीबीएससीएएन क्लस्टरिंग परिणाम के समान होता है) <math>\varepsilon</math> और {{not a typo|minPts}} पैरामीटर; यहां 0.1 का मान अच्छे परिणाम दे सकता है), या विभिन्न एल्गोरिदम द्वारा जो ढलान, घुटने का पता लगाने, या स्थानीय मैक्सिमा द्वारा घाटियों का पता लगाने का प्रयास करते हैं। इस तरह से प्राप्त क्लस्टरिंग आमतौर पर [[पदानुक्रमित क्लस्टरिंग]] होती है, और इसे एकल डीबीएससीएएन रन द्वारा प्राप्त नहीं किया जा सकता है।
+इस प्लॉट से क्लस्टर्स को निकालने के लिए, इसे विज़ुअल निरीक्षण के उपरांत x-अक्ष पर रेंज का चयन करके हाथ से किया जा सकता है, y-अक्ष पर एक थ्रेशोल्ड चयन करके (परिणाम फिर एक डीबीएससीएएन क्लस्टरिंग परिणाम के समान होता है जिसमें एक समान <math>\varepsilon</math> और {{not a typo|मिनिप्ट्स,}}मापदंड होते हैं; यहां एक 0.1 की मान अच्छे परिणाम देने के लिए उत्तम सिद्ध हो सकती है), या विभिन्न एल्गोरिदम्स द्वारा जो धरा, घुटन डिटेक्शन या स्थानिक अधिकतमों के माध्यम से वैलीज़ का पता लगाने का प्रयास करते हैं। इस तरह प्राप्त किए गए क्लस्टरिंग सामान्यतः [[पदानुक्रमित क्लस्टरिंग|वृद्धिकीय]] होते हैं, और इन्हें एकल डीबीएससीएएन चलने से प्राप्त नहीं किया जा सकता हैं।
 ==जटिलता==
-डीबीएससीएएन की तरह, ऑप्टिक्स प्रत्येक बिंदु को एक बार संसाधित करता है, और पड़ोसियों के पास एक निश्चित-त्रिज्या निष्पादित करता है<math>\varepsilon</math>-इस प्रसंस्करण के दौरान पड़ोस की क्वेरी। एक [[स्थानिक सूचकांक]] दिया गया है जो पड़ोस की क्वेरी प्रदान करता है <math>O(\log n)</math> रनटाइम, का समग्र रनटाइम <math>O(n \cdot \log n)</math> प्राप्त होना। मूल ऑप्टिक्स पेपर के लेखक डीबीएससीएएन की तुलना में 1.6 के वास्तविक निरंतर मंदी कारक की रिपोर्ट करते हैं। ध्यान दें कि का मूल्य <math>\varepsilon</math> एल्गोरिथम की लागत पर भारी प्रभाव पड़ सकता है, क्योंकि बहुत बड़ा मूल्य पड़ोस की क्वेरी की लागत को रैखिक जटिलता तक बढ़ा सकता है।
+डीबीएससीएएन की तरह, ऑप्टिक्स भी प्रत्येक बिंदु को एक बार प्रोसेस करता है और इस प्रोसेसिंग के दौरान एक ε-पड़ोसी क्वेरी का निष्पादन करता है। यदि किसी [[स्थानिक सूचकांक]]  के साथ ε-पड़ोसी क्वेरी को <math>O(\log n)</math> रनटाइम में निष्पादित किया जा सकता है, तो कुल रनटाइम <math>O(n \cdot \log n)</math> प्राप्त होता है। मूल ऑप्टिक्स पेपर के लेखकों ने रिपोर्ट किया है कि डीबीएससीएएन के तुलना में एक वास्तविक निरंतर मंदी गणकांश का अनुमानित कायम संक्रमण फैक्टर 1.6 है।  ध्यान दें कि का मूल्य <math>\varepsilon</math> एल्गोरिथम की लागत पर भारी प्रभाव पड़ सकता है, क्योंकि अधिकतम मान किसी पड़ोसी क्वेरी की लागत को रैखिक संज्ञानात्मकता तक उठा सकता है।
 विशेष रूप से, चुनना <math>\varepsilon > \max_{x,y} d(x,y)</math> (डेटा सेट में अधिकतम दूरी से अधिक) संभव है,परंतु द्विघात जटिलता की ओर ले जाता है, क्योंकि प्रत्येक पड़ोस क्वेरी पूर्ण डेटा सेट लौटाती है। यहां तक कि जब कोई स्थानिक सूचकांक उपलब्ध नहीं होता है, तब भी ढेर के प्रबंधन में अतिरिक्त लागत आती है। इसलिए, <math>\varepsilon</math> डेटा सेट के लिए उचित रूप से चुना जाना चाहिए।
@@ Line 115: / Line 108: @@
   | chapter-url = http://springerlink.metapress.com/content/76bx6413gqb4tvta/
 | series = Lecture Notes in Computer Science
-  |s2cid=27352458 |url=https://lirias.kuleuven.be/handle/123456789/125270 }}</ref> ऑप्टिक्स पर आधारित एक विसंगति का पता लगाने वाला एल्गोरिदम है। मुख्य उपयोग एक अलग आउटलायर डिटेक्शन विधि का उपयोग करने की तुलना में कम लागत पर ऑप्टिक्स के मौजूदा रन से आउटलेर्स का निष्कर्षण है। [[स्थानीय बाह्य कारक]] का बेहतर ज्ञात संस्करण उन्हीं अवधारणाओं पर आधारित है।
+  |s2cid=27352458 |url=https://lirias.kuleuven.be/handle/123456789/125270 }}</ref> ऑप्टिक्स पर आधारित एक विसंगति का पता लगाने वाला एल्गोरिदम है। मुख्य उपयोग एक अलग आउटलायर डिटेक्शन विधि का उपयोग करने की तुलना में कम लागत पर ऑप्टिक्स के उपस्रथितन से आउटलेर्स का निष्कर्षण है। [[स्थानीय बाह्य कारक]] का बेहतर ज्ञात संस्करण उन्हीं अवधारणाओं पर आधारित है।
 डेली-क्लू,<ref>{{cite conference
@@ Line 132: / Line 125: @@
   | 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 152: / Line 145: @@
   | 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 167: @@
   | title = 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
   | volume = 4443
-  | year = 2007}}</ref> HiSC पर एक सुधार है जो अधिक जटिल पदानुक्रम पा सकता है।
+  | year = 2007}}</ref> हाईएससी पर एक सुधार है जो अधिक जटिल पदानुक्रम पा सकता है।
-फोप्टिक्स<ref>{{Cite journal | last1 = Schneider | first1 = Johannes | last2 = Vlachos | first2 = Michail | year = 2013 | title = यादृच्छिक अनुमानों के माध्यम से तेज़ पैरामीटर रहित घनत्व-आधारित क्लस्टरिंग| journal = 22nd ACM International Conference on Information and Knowledge Management(CIKM) }}</ref> यादृच्छिक अनुमानों का उपयोग करके तेज़ कार्यान्वयन है।
+फोप्टिक्स<ref>{{Cite journal | last1 = Schneider | first1 = Johannes | last2 = Vlachos | first2 = Michail | year = 2013 | title = यादृच्छिक अनुमानों के माध्यम से तेज़ पैरामीटर रहित घनत्व-आधारित क्लस्टरिंग| journal = 22nd ACM International Conference on Information and Knowledge Management(CIKM) }}</ref> यादृच्छिक अनुमानों का उपयोग करके तेज़ कार्यान्वयन करता है।
 एचडीबीएसकैन*<ref>{{cite journal|last1=Campello|first1=Ricardo J. G. B.|last2=Moulavi|first2=Davoud|last3=Zimek|first3=Arthur|last4=Sander|first4=Jörg|title=डेटा क्लस्टरिंग, विज़ुअलाइज़ेशन और आउटलायर डिटेक्शन के लिए पदानुक्रमित घनत्व अनुमान|journal=ACM Transactions on Knowledge Discovery from Data|date=22 July 2015|volume=10|issue=1|pages=1–51|doi=10.1145/2733381|s2cid=2887636 }}</ref> डीबीएससीएएन के परिशोधन पर आधारित है, जो समूहों से सीमा-बिंदुओं को बाहर करता है और इस प्रकार हार्टिगन द्वारा घनत्व-स्तरों की मूल परिभाषा का अधिक सख्ती से पालन करता है।<ref>{{cite book|author=J.A. Hartigan|title=क्लस्टरिंग एल्गोरिदम|publisher=John Wiley & Sons|year=1975}}</ref>
 ==उपलब्धता==
-OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO और DiSH के जावा कार्यान्वयन [[ELKI]] में उपलब्ध हैं (कई दूरी के कार्यों के लिए सूचकांक त्वरण के साथ, और ξ निष्कर्षण विधि का उपयोग करके स्वचालित क्लस्टर निष्कर्षण के साथ)। अन्य जावा कार्यान्वयन में [[वेका (मशीन लर्निंग)]] एक्सटेंशन (ξ क्लस्टर निष्कर्षण के लिए कोई समर्थन नहीं) शामिल है।
+ओप्टिक्स, ओप्टिक्स-ओएफ, डीली-क्लू, हिस्क, हिको और डिश के जावा अनुमानित कार्यनीतियों के विभिन्न प्रस्तावनाएँ [[ELKI|ईएलकी]] डेटा माइनिंग फ्रेमवर्क में उपलब्ध हैं (जिनमें कई दूरी फंक्शनों के लिए इंडेक्स त्वरण और जिएक्स निकासी विधि का स्वचालित क्लस्टर निकालने का समर्थन किया गया है)। अन्य जावा प्रस्तावनाएँ में [[वेका (मशीन लर्निंग)|वेका]] एक्सटेंशन सम्मिलित है (जिसमें जिएक्स क्लस्टर निकासी के लिए समर्थन नहीं है)।
-[[GNU R]] पैकेज dbscan में केवल यूक्लिडियन दूरी के लिए सूचकांक त्वरण के लिए k-d ट्री का उपयोग करके OPTICS (पारंपरिक dbscan-जैसे और ξ क्लस्टर निष्कर्षण दोनों के साथ) का C++ कार्यान्वयन शामिल है।
+[[GNU R|आर पैकेज]] "dbscan" में ऑप्टिक्स का एक C++ प्रस्तावना सम्मिलित है (जिसमें रस्त्रीय डीबीस्कैन जैसे और जिएक्स क्लस्टर निकासी दोनों हैं) जिसमें केवल यूक्लिड दूरी के लिए इंडेक्स त्वरण के लिए के-डी ट्री का उपयोग होता है।
-ऑप्टिक्स का पायथन कार्यान्वयन [https://pyclustering.github.io/ PyClustering] लाइब्रेरी और [[स्किकिट-लर्न]] में उपलब्ध है। Hडीबीएससीएएन* [https://hdbscan.readthedocs.io/ hdbscan] लाइब्रेरी में उपलब्ध है।
+ऑप्टिक्स के पायथन अनुमानित कार्यनीतियाँ पायथन में [https://pyclustering.github.io/ पाइक्लस्टरिंग]  और [[स्किकिट-लर्न]] पुस्तकालय में उपलब्ध हैं। एचडीबीएसकैन* एचडीबीएसकैन पुस्तकालय में उपलब्ध है।
 ==संदर्भ==
 {{Reflist}}
-[[Category: क्लस्टर विश्लेषण एल्गोरिदम]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 10/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:क्लस्टर विश्लेषण एल्गोरिदम]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 13:16, 3 August 2023

Contents

मूलभूत विचार

स्यूडोकोड

क्लस्टर्स को निकालना

जटिलता

एक्सटेंशन

उपलब्धता

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 13:16, 3 August 2023

मूलभूत विचार

स्यूडोकोड

क्लस्टर्स को निकालना

जटिलता

एक्सटेंशन

उपलब्धता

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories