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

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

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

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

${\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 का मान अच्छे परिणाम दे सकता है), या विभिन्न एल्गोरिदम द्वारा जो ढलान, घुटने का पता लगाने, या स्थानीय मैक्सिमा द्वारा घाटियों का पता लगाने का प्रयास करते हैं। इस तरह से प्राप्त क्लस्टरिंग आमतौर पर पदानुक्रमित क्लस्टरिंग होती है, और इसे एकल DBSCAN रन द्वारा प्राप्त नहीं किया जा सकता है।

जटिलता

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

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

एक्सटेंशन

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

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

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

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

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

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

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

उपलब्धता

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

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

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