View source for प्रकाशिकी एल्गोरिथ्म

{{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
 |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
 | year = 1999
 | pages = 49–60
 | conference = ACM SIGMOD international conference on Management of data
 | publisher = [[ACM Press]]
 | citeseerx = 10.1.1.129.6542
 }}</ref>इसकी मूल विचारधारा [[DBSCAN|डीबीएससीएएन]] के समान है<ref>{{Cite conference
 |author=Martin Ester
 |author-link=Martin Ester
 |author2=Hans-Peter Kriegel |author2-link=Hans-Peter Kriegel |author3=Jörg Sander |author4=Xiaowei Xu
 | title = A density-based algorithm for discovering clusters in large spatial databases with noise
 |  pages = 226–231
 |editor=Evangelos Simoudis |editor2=Jiawei Han |editor3=Usama M. Fayyad
 | conference = Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96)
 | publisher = [[AAAI Press]]
 | year = 1996
 | isbn = 1-57735-004-9 
 | citeseerx = 10.1.1.71.1980
 }}</ref>,परंतु यह डीबीएससीएएन की एक प्रमुख कमियों में से एक को पता करता है: भिन्न घनत्व वाले डेटा में मायने रखने वाले क्लस्टर्स का पता लगाने की समस्या होती हैं।इसके लिए, डेटाबेस के बिंदुओं ऐसे क्रमबद्ध किया जाता हैं कि जो स्थानिक रूप से निकटतम बिंदु होते हैं, वे क्रमबद्धीकरण में पड़ोसी बन जाते हैं।इसके अतिरिक्त, प्रत्येक बिंदु के लिए एक विशेष दूरी संग्रहीत की जाती है जो एक क्लस्टर के लिए स्वीकार्य घनत्व को प्रतिनिधित करती है, क्योंकी दोनों बिंदु एक ही क्लस्टर का हिस्सा बनें रहे। यह एक [[डेंड्रोग्राम]] के रूप में प्रतिष्ठित किया जाता है।

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

:<math>\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}</math>
अगर {{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;}} उन समूहों के घनत्व को कम करने के लिए पैरामीटर की आवश्यकता होती है जो अब दिलचस्प नहीं हैं, और एल्गोरिदम को गति देने के लिए।

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

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

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

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

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

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

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

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

दृश्य निरीक्षण के बाद एक्स-अक्ष पर एक सीमा का चयन करके, वाई-अक्ष पर एक सीमा का चयन करके इस प्लॉट से क्लस्टर निकालना मैन्युअल रूप से किया जा सकता है (नतीजा तब डीबीएससीएएन क्लस्टरिंग परिणाम के समान होता है) <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> डेटा सेट के लिए उचित रूप से चुना जाना चाहिए।

==एक्सटेंशन==
ऑप्टिक्स-ऑफ<ref>{{Cite book
 |author=Markus M. Breunig |author2=Hans-Peter Kriegel |author2-link=Hans-Peter Kriegel |author3=Raymond T. Ng |author4=Jörg Sander
 | chapter = OPTICS-OF: Identifying Local Outliers
 | pages = 262–270
 | title = Principles of Data Mining and Knowledge Discovery
 | volume = 1704
 | publisher = [[Springer-Verlag]]
 | year = 1999
 | isbn = 978-3-540-66490-1 
 | doi = 10.1007/b72280
 | 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> ऑप्टिक्स पर आधारित एक विसंगति का पता लगाने वाला एल्गोरिदम है। मुख्य उपयोग एक अलग आउटलायर डिटेक्शन विधि का उपयोग करने की तुलना में कम लागत पर ऑप्टिक्स के मौजूदा रन से आउटलेर्स का निष्कर्षण है। [[स्थानीय बाह्य कारक]] का बेहतर ज्ञात संस्करण उन्हीं अवधारणाओं पर आधारित है।

डेली-क्लू,<ref>{{cite conference
 | last1 = Achtert | first1 = Elke
 | last2 = Böhm | first2 = Christian
 | last3 = Kröger | first3 = Peer
 | editor1-last = Ng | editor1-first = Wee Keong
 | editor2-last = Kitsuregawa | editor2-first = Masaru
 | editor3-last = Li | editor3-first = Jianzhong
 | editor4-last = Chang | editor4-first = Kuiyu
 | contribution = DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking
 | doi = 10.1007/11731139_16
 | pages = 119–128
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | 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> पैरामीटर और ऑप्टिक्स की तुलना में प्रदर्शन में सुधार की पेशकश।

हायएससी<ref>{{cite conference
 | last1 = Achtert | first1 = Elke
 | last2 = Böhm | first2 = Christian
 | last3 = Kriegel | first3 = Hans{-}Peter
 | last4 = Kröger | first4 = Peer
 | last5 = Müller{-}Gorman | first5 = Ina
 | last6 = Zimek | first6 = Arthur
 | editor1-last = Fürnkranz | editor1-first = Johannes
 | editor2-last = Scheffer | editor2-first = Tobias
 | editor3-last = Spiliopoulou | editor3-first = Myra
 | contribution = Finding Hierarchies of Subspace Clusters
 | doi = 10.1007/11871637_42
 | pages = 446–453
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = 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
 | volume = 4213
 | year = 2006| doi-access = free
 }}</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
 | last1 = Achtert | first1 = Elke
 | last2 = Böhm | first2 = Christian
 | last3 = Kriegel | first3 = Hans{-}Peter
 | last4 = Kröger | first4 = Peer
 | last5 = Müller{-}Gorman | first5 = Ina
 | last6 = Zimek | first6 = Arthur
 | editor1-last = Ramamohanarao | editor1-first = Kotagiri
 | editor2-last = Krishna | editor2-first = P. Radha
 | editor3-last = Mohania | editor3-first = Mukesh K.
 | editor4-last = Nantajeewarawat | editor4-first = Ekawit
 | contribution = Detection and Visualization of Subspace Cluster Hierarchies
 | doi = 10.1007/978-3-540-71703-4_15
 | pages = 152–163
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | 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 पर एक सुधार है जो अधिक जटिल पदानुक्रम पा सकता है।

फोप्टिक्स<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]] में उपलब्ध हैं (कई दूरी के कार्यों के लिए सूचकांक त्वरण के साथ, और ξ निष्कर्षण विधि का उपयोग करके स्वचालित क्लस्टर निष्कर्षण के साथ)। अन्य जावा कार्यान्वयन में [[वेका (मशीन लर्निंग)]] एक्सटेंशन (ξ क्लस्टर निष्कर्षण के लिए कोई समर्थन नहीं) शामिल है।

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

ऑप्टिक्स का पायथन कार्यान्वयन [https://pyclustering.github.io/ PyClustering] लाइब्रेरी और [[स्किकिट-लर्न]] में उपलब्ध है। Hडीबीएससीएएन* [https://hdbscan.readthedocs.io/ hdbscan] लाइब्रेरी में उपलब्ध है।

==संदर्भ==
{{Reflist}}
[[Category: क्लस्टर विश्लेषण एल्गोरिदम]] 



[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]