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

Revision as of 08:30, 25 July 2023

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

बुनियादी विचार

डीबीएससीएएन की तरह, ऑप्टिक्स को दो मापदंडों की आवश्यकता होती है: $ε$ , जो विचार करने योग्य अधिकतम दूरी (त्रिज्या) का वर्णन करता है,

डीबीएससीएएन की तरह, ऑप्टिक्स को दो पैरामीटरों की आवश्यकता होती है: ε, जो अधिकतम दूरी (रेडियस) का वर्णन करता है जिसे ध्यान में लेने के लिए, और मिनिप्ट्स, जो क्लस्टर बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है।

और $मिनिप्ट्स,$ , एक क्लस्टर बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है। एक बिंदु $p$ यदि कम से कम एक मुख्य बिंदु है $मिनिप्ट्स,$ इसके अंदर अंक पाए जाते हैं $ε$ -अड़ोस-पड़ोस $N_{\varepsilon }(p)$ (बिंदु सहित $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$ एक ही क्लस्टर से संबंधित हैं।

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

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

छद्मकोड

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

फ़ंक्शन ऑप्टिक्स(DB, ε, MinPts) है
    DB के प्रत्येक बिंदु p के लिए करें
        पी.पहुँच योग्यता-दूरी = अपरिभाषित
    डीबी के प्रत्येक असंसाधित बिंदु पी के लिए करें
        एन = गेटनेबर्स(पी, ε)
        पी को संसाधित के रूप में चिह्नित करें
        आदेशित सूची में आउटपुट पी
        यदि कोर-दूरी(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 1: / Line 1: @@
 {{Short description|Algorithm for finding density based clusters in spatial data}}
 {{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 9: / Line 11: @@
   | publisher = [[ACM Press]]
   | citeseerx = 10.1.1.129.6542
-  }}</ref>
+  }}</ref>इसकी मूल विचारधारा [[DBSCAN|डीबीएससीएएन]] के समान है<ref>{{Cite conference
-इसका मूल विचार [[DBSCAN]] के समान है,<ref>{{Cite conference
   |author=Martin Ester
   |author-link=Martin Ester
@@ Line 22: / Line 23: @@
   | isbn = 1-57735-004-9
   | citeseerx = 10.1.1.71.1980
-  }}</ref> लेकिन यह DBSCAN की प्रमुख कमजोरियों में से एक को संबोधित करता है: विभिन्न घनत्व के डेटा में सार्थक समूहों का पता लगाने की समस्या। ऐसा करने के लिए, डेटाबेस के बिंदुओं को (रैखिक रूप से) इस तरह क्रमबद्ध किया जाता है कि स्थानिक रूप से निकटतम बिंदु क्रम में पड़ोसी बन जाते हैं। इसके अतिरिक्त, प्रत्येक बिंदु के लिए एक विशेष दूरी संग्रहीत की जाती है जो उस घनत्व का प्रतिनिधित्व करती है जिसे क्लस्टर के लिए स्वीकार किया जाना चाहिए ताकि दोनों बिंदु एक ही क्लस्टर से संबंधित हों। इसे [[डेंड्रोग्राम]] के रूप में दर्शाया गया है।
+  }}</ref>,परंतु यह डीबीएससीएएन की एक प्रमुख कमियों में से एक को पता करता है: भिन्न घनत्व वाले डेटा में मायने रखने वाले क्लस्टर्स का पता लगाने की समस्या होती हैं।इसके लिए, डेटाबेस के बिंदुओं ऐसे क्रमबद्ध किया जाता हैं कि जो स्थानिक रूप से निकटतम बिंदु होते हैं, वे क्रमबद्धीकरण में पड़ोसी बन जाते हैं।इसके अतिरिक्त, प्रत्येक बिंदु के लिए एक विशेष दूरी संग्रहीत की जाती है जो एक क्लस्टर के लिए स्वीकार्य घनत्व को प्रतिनिधित करती है, क्योंकी दोनों बिंदु एक ही क्लस्टर का हिस्सा बनें रहे। यह एक [[डेंड्रोग्राम]] के रूप में प्रतिष्ठित किया जाता है।
 ==बुनियादी विचार==
-DBSCAN की तरह, ऑप्टिक्स को दो मापदंडों की आवश्यकता होती है: {{mvar|&epsilon;}}, जो विचार करने योग्य अधिकतम दूरी (त्रिज्या) का वर्णन करता है, और {{mvar|MinPts}}, एक क्लस्टर बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है। एक बिंदु {{mvar|p}} यदि कम से कम एक मुख्य बिंदु है {{mvar|MinPts}} इसके अंदर अंक पाए जाते हैं {{mvar|&epsilon;}}-अड़ोस-पड़ोस <math>N_\varepsilon(p)</math> (बिंदु सहित {{mvar|p}} अपने आप)। डीबीएससीएएन के विपरीत, ऑप्टिक्स उन बिंदुओं पर भी विचार करता है जो अधिक सघनता से भरे क्लस्टर का हिस्सा हैं, इसलिए प्रत्येक बिंदु को एक मुख्य दूरी सौंपी जाती है जो दूरी का वर्णन करती है {{mvar|MinPts}}वां निकटतम बिंदु:
+डीबीएससीएएन की तरह, ऑप्टिक्स को दो मापदंडों की आवश्यकता होती है: {{mvar|&epsilon;}}, जो विचार करने योग्य अधिकतम दूरी (त्रिज्या) का वर्णन करता है,
+डीबीएससीएएन की तरह, ऑप्टिक्स को दो पैरामीटरों की आवश्यकता होती है: ε, जो अधिकतम दूरी (रेडियस) का वर्णन करता है जिसे ध्यान में लेने के लिए, और मिनिप्ट्स, जो क्लस्टर बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है।
+और {{mvar|मिनिप्ट्स,}}, एक क्लस्टर बनाने के लिए आवश्यक बिंदुओं की संख्या का वर्णन करता है। एक बिंदु {{mvar|p}} यदि कम से कम एक मुख्य बिंदु है {{mvar|मिनिप्ट्स,}} इसके अंदर अंक पाए जाते हैं {{mvar|&epsilon;}}-अड़ोस-पड़ोस <math>N_\varepsilon(p)</math> (बिंदु सहित {{mvar|p}} अपने आप)। डीबीएससीएएन के विपरीत, ऑप्टिक्स उन बिंदुओं पर भी विचार करता है जो अधिक सघनता से भरे क्लस्टर का हिस्सा हैं, इसलिए प्रत्येक बिंदु को एक मुख्य दूरी सौंपी जाती है जो दूरी का वर्णन करती है {{mvar|मिनिप्ट्स,}}वां निकटतम बिंदु:
 <!-- beware of line lengths for small screens -->
@@ Line 43: / Line 49: @@
 अगर {{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;}} उन समूहों के घनत्व को कम करने के लिए पैरामीटर की आवश्यकता होती है जो अब दिलचस्प नहीं हैं, और एल्गोरिदम को गति देने के लिए।
+यदि कोई पर्याप्त सघन क्लस्टर नहीं है (w.r.t.) तो कोर-दूरी और रीचैबिलिटी-दूरी दोनों अपरिभाषित हैं। {{mvar|&epsilon;}}) उपलब्ध है। पर्याप्त रूप से बड़ा दिया गया {{mvar|&epsilon;}}, ऐसा कभी नहीं होता,परंतु फिर हर {{mvar|&epsilon;}}-नेबरहुड क्वेरी संपूर्ण डेटाबेस लौटाती है, जिसके परिणामस्वरूप <math>O(n^2)</math> रनटाइम. इसलिए {{mvar|&epsilon;}} उन समूहों के घनत्व को कम करने के लिए पैरामीटर की आवश्यकता होती है जो अब दिलचस्प नहीं हैं, और एल्गोरिदम को गति देने के लिए।
 पैरामीटर {{mvar|&epsilon;}} सच कहूँ तो, आवश्यक नहीं है। इसे बस अधिकतम संभव मान पर सेट किया जा सकता है। हालाँकि, जब कोई स्थानिक सूचकांक उपलब्ध होता है, तो यह जटिलता के संबंध में एक व्यावहारिक भूमिका निभाता है। इस पैरामीटर को हटाकर ऑप्टिक्स को डीबीएससीएएन से कम से कम केवल अधिकतम मूल्य देने की सीमा तक सार निकाला जाता है।
 ==छद्मकोड==
-ऑप्टिक्स का मूल दृष्टिकोण डीबीएससीएएन के समान है, लेकिन एक सेट में ज्ञात, लेकिन अब तक असंसाधित क्लस्टर सदस्यों को बनाए रखने के बजाय, उन्हें [[प्राथमिकता कतार]] में बनाए रखा जाता है (उदाहरण के लिए अनुक्रमित हीप (डेटा संरचना) का उपयोग करना)।
+ऑप्टिक्स का मूल दृष्टिकोण डीबीएससीएएन के समान है,परंतु एक सेट में ज्ञात,परंतु अब तक असंसाधित क्लस्टर सदस्यों को बनाए रखने के बजाय, उन्हें [[प्राथमिकता कतार]] में बनाए रखा जाता है (उदाहरण के लिए अनुक्रमित हीप (डेटा संरचना) का उपयोग करना)।
   फ़ंक्शन ऑप्टिक्स(DB, ε, MinPts) है
@@ Line 82: / Line 88: @@
                       बीज.मूव-अप(ओ, न्यू-रीच-डिस्ट्रिक्ट)
-इसलिए ऑप्टिक्स एक विशेष क्रम में बिंदुओं को आउटपुट करता है, जो उनकी सबसे छोटी रीचैबिलिटी दूरी के साथ एनोटेट होता है (मूल एल्गोरिदम में, कोर दूरी भी निर्यात की जाती है, लेकिन आगे की प्रक्रिया के लिए इसकी आवश्यकता नहीं है)।
+इसलिए ऑप्टिक्स एक विशेष क्रम में बिंदुओं को आउटपुट करता है, जो उनकी सबसे छोटी रीचैबिलिटी दूरी के साथ एनोटेट होता है (मूल एल्गोरिदम में, कोर दूरी भी निर्यात की जाती है,परंतु आगे की प्रक्रिया के लिए इसकी आवश्यकता नहीं है)।
 ==गुच्छों को निकालना==
 [[File:OPTICS.svg]]रीचैबिलिटी-प्लॉट (एक विशेष प्रकार का डेंड्रोग्राम) का उपयोग करके, समूहों की पदानुक्रमित संरचना आसानी से प्राप्त की जा सकती है। यह एक 2डी प्लॉट है, जिसमें एक्स-अक्ष पर ऑप्टिक्स द्वारा संसाधित बिंदुओं का क्रम और वाई-अक्ष पर पहुंच दूरी है। चूंकि क्लस्टर से संबंधित बिंदुओं की उनके निकटतम पड़ोसी से कम पहुंच दूरी होती है, इसलिए क्लस्टर पहुंच योग्य प्लॉट में घाटियों के रूप में दिखाई देते हैं। घाटी जितनी गहरी होगी, समूह उतना ही सघन होगा।
-उपरोक्त छवि इस अवधारणा को दर्शाती है। इसके ऊपरी बाएँ क्षेत्र में, एक सिंथेटिक उदाहरण डेटा सेट दिखाया गया है। ऊपरी दायाँ भाग ऑप्टिक्स द्वारा निर्मित फैले हुए वृक्ष की कल्पना करता है, और निचला भाग ऑप्टिक्स द्वारा गणना की गई रीचैबिलिटी प्लॉट को दर्शाता है। इस प्लॉट में रंग लेबल हैं, और एल्गोरिथम द्वारा गणना नहीं की जाती हैं; लेकिन यह अच्छी तरह से दिखाई देता है कि प्लॉट में घाटियाँ उपरोक्त डेटा सेट में समूहों से कैसे मेल खाती हैं। इस छवि में पीले बिंदुओं को शोर माना जाता है, और उनकी पहुंच योग्य प्लॉट में कोई घाटी नहीं पाई जाती है। पदानुक्रमित परिणाम में सर्वव्यापी सभी डेटा क्लस्टर को छोड़कर, उन्हें आमतौर पर क्लस्टरों को नहीं सौंपा जाता है।
+उपरोक्त छवि इस अवधारणा को दर्शाती है। इसके ऊपरी बाएँ क्षेत्र में, एक सिंथेटिक उदाहरण डेटा सेट दिखाया गया है। ऊपरी दायाँ भाग ऑप्टिक्स द्वारा निर्मित फैले हुए वृक्ष की कल्पना करता है, और निचला भाग ऑप्टिक्स द्वारा गणना की गई रीचैबिलिटी प्लॉट को दर्शाता है। इस प्लॉट में रंग लेबल हैं, और एल्गोरिथम द्वारा गणना नहीं की जाती हैं;परंतु यह अच्छी तरह से दिखाई देता है कि प्लॉट में घाटियाँ उपरोक्त डेटा सेट में समूहों से कैसे मेल खाती हैं। इस छवि में पीले बिंदुओं को शोर माना जाता है, और उनकी पहुंच योग्य प्लॉट में कोई घाटी नहीं पाई जाती है। पदानुक्रमित परिणाम में सर्वव्यापी सभी डेटा क्लस्टर को छोड़कर, उन्हें आमतौर पर क्लस्टरों को नहीं सौंपा जाता है।
-दृश्य निरीक्षण के बाद एक्स-अक्ष पर एक सीमा का चयन करके, वाई-अक्ष पर एक सीमा का चयन करके इस प्लॉट से क्लस्टर निकालना मैन्युअल रूप से किया जा सकता है (नतीजा तब डीबीएससीएएन क्लस्टरिंग परिणाम के समान होता है) <math>\varepsilon</math> और {{not a typo|minPts}} पैरामीटर; यहां 0.1 का मान अच्छे परिणाम दे सकता है), या विभिन्न एल्गोरिदम द्वारा जो ढलान, घुटने का पता लगाने, या स्थानीय मैक्सिमा द्वारा घाटियों का पता लगाने का प्रयास करते हैं। इस तरह से प्राप्त क्लस्टरिंग आमतौर पर [[पदानुक्रमित क्लस्टरिंग]] होती है, और इसे एकल DBSCAN रन द्वारा प्राप्त नहीं किया जा सकता है।
+दृश्य निरीक्षण के बाद एक्स-अक्ष पर एक सीमा का चयन करके, वाई-अक्ष पर एक सीमा का चयन करके इस प्लॉट से क्लस्टर निकालना मैन्युअल रूप से किया जा सकता है (नतीजा तब डीबीएससीएएन क्लस्टरिंग परिणाम के समान होता है) <math>\varepsilon</math> और {{not a typo|minPts}} पैरामीटर; यहां 0.1 का मान अच्छे परिणाम दे सकता है), या विभिन्न एल्गोरिदम द्वारा जो ढलान, घुटने का पता लगाने, या स्थानीय मैक्सिमा द्वारा घाटियों का पता लगाने का प्रयास करते हैं। इस तरह से प्राप्त क्लस्टरिंग आमतौर पर [[पदानुक्रमित क्लस्टरिंग]] होती है, और इसे एकल डीबीएससीएएन रन द्वारा प्राप्त नहीं किया जा सकता है।
 ==जटिलता==
 डीबीएससीएएन की तरह, ऑप्टिक्स प्रत्येक बिंदु को एक बार संसाधित करता है, और पड़ोसियों के पास एक निश्चित-त्रिज्या निष्पादित करता है<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> डेटा सेट के लिए उचित रूप से चुना जाना चाहिए।
+विशेष रूप से, चुनना <math>\varepsilon > \max_{x,y} d(x,y)</math> (डेटा सेट में अधिकतम दूरी से अधिक) संभव है,परंतु द्विघात जटिलता की ओर ले जाता है, क्योंकि प्रत्येक पड़ोस क्वेरी पूर्ण डेटा सेट लौटाती है। यहां तक कि जब कोई स्थानिक सूचकांक उपलब्ध नहीं होता है, तब भी ढेर के प्रबंधन में अतिरिक्त लागत आती है। इसलिए, <math>\varepsilon</math> डेटा सेट के लिए उचित रूप से चुना जाना चाहिए।
 ==एक्सटेंशन==
@@ Line 172: / Line 178: @@
 फोप्टिक्स<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> DBSCAN के परिशोधन पर आधारित है, जो समूहों से सीमा-बिंदुओं को बाहर करता है और इस प्रकार हार्टिगन द्वारा घनत्व-स्तरों की मूल परिभाषा का अधिक सख्ती से पालन करता है।<ref>{{cite book|author=J.A. Hartigan|title=क्लस्टरिंग एल्गोरिदम|publisher=John Wiley & Sons|year=1975}}</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>
@@ Line 180: / Line 186: @@
 [[GNU R]] पैकेज dbscan में केवल यूक्लिडियन दूरी के लिए सूचकांक त्वरण के लिए k-d ट्री का उपयोग करके OPTICS (पारंपरिक dbscan-जैसे और ξ क्लस्टर निष्कर्षण दोनों के साथ) का C++ कार्यान्वयन शामिल है।
-ऑप्टिक्स का पायथन कार्यान्वयन [https://pyclustering.github.io/ PyClustering] लाइब्रेरी और [[स्किकिट-लर्न]] में उपलब्ध है। HDBSCAN* [https://hdbscan.readthedocs.io/ hdbscan] लाइब्रेरी में उपलब्ध है।
+ऑप्टिक्स का पायथन कार्यान्वयन [https://pyclustering.github.io/ PyClustering] लाइब्रेरी और [[स्किकिट-लर्न]] में उपलब्ध है। Hडीबीएससीएएन* [https://hdbscan.readthedocs.io/ hdbscan] लाइब्रेरी में उपलब्ध है।
 ==संदर्भ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 08:30, 25 July 2023

Contents

बुनियादी विचार

छद्मकोड

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

जटिलता

एक्सटेंशन

उपलब्धता

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 08:30, 25 July 2023

बुनियादी विचार

छद्मकोड

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

जटिलता

एक्सटेंशन

उपलब्धता

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories