स्वचालित क्लस्टरिंग एल्गोरिदम

From Vigyanwiki
Revision as of 10:08, 2 August 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

स्वचालित क्लस्टरिंग एल्गोरिदम ऐसे एल्गोरिदम हैं जो डेटा समूह के पूर्व ज्ञान के बिना क्लस्टरिंग कर सकते हैं। इस प्रकार अन्य क्लस्टर विश्लेषण विधियों के विपरीत, स्वचालित क्लस्टरिंग एल्गोरिदम ध्वनि और बाहरी बिंदुओं की उपस्थिति में भी क्लस्टर की इष्टतम संख्या निर्धारित कर सकते हैं।[1]

केन्द्रक आधारित

n वस्तुओं के एक समूह को देखते हुए, सेंट्रोइड-आधारित एल्गोरिदम एक असमानता फलन के आधार पर k विभाजन बनाते हैं, इस प्रकार जैसे कि k≤n। इस प्रकार के एल्गोरिदम को प्रयुक्त करने में एक बड़ी समस्या बिना लेबल वाले डेटा के लिए क्लस्टर की उचित संख्या निर्धारित करना है। इसलिए, क्लस्टरिंग विश्लेषण में अधिकांश शोध प्रक्रिया के स्वचालन पर केंद्रित है।

K-मीन्स क्लस्टरिंग एल्गोरिदम में k का स्वचालित चयन‚ सबसे अधिक उपयोग किए जाने वाले सेंट्रोइड-आधारित क्लस्टरिंग एल्गोरिदम में से एक, अभी भी मशीन लर्निंग में एक बड़ी समस्या है। इस प्रकार इस समस्या का सबसे स्वीकृत समाधान एल्बो विधि (क्लस्टरिंग) है। इसमें मानों की एक श्रृंखला के साथ डेटा समूह पर के-मीन्स क्लस्टरिंग चलाना, प्रत्येक के लिए वर्ग त्रुटियों के योग की गणना करना और उन्हें एक लाइन चार्ट में प्लॉट करना सम्मिलित है। इस प्रकार यदि चार्ट एक भुजा की तरह दिखता है, तब k का सबसे अच्छा मान "कोहनी" पर होगा।[2]

एक अन्य विधि जो क्लस्टर की इष्टतम संख्या को स्वचालित रूप से चुनने के लिए के-मीन्स एल्गोरिदम को संशोधित करती है वह जी-मीन्स एल्गोरिदम है। इस प्रकार इसे इस परिकल्पना से विकसित किया गया था कि डेटा का एक उपसमूह गाऊसी वितरण का अनुसरण करता है। इस प्रकार, k को तब तक बढ़ाया जाता है जब तक कि प्रत्येक k-साधन केंद्र का डेटा गॉसियन न हो जाए। इस एल्गोरिदम को एक पैरामीटर के रूप में केवल मानक सांख्यिकीय महत्व स्तर की आवश्यकता होती है और यह डेटा के सहप्रसरण के लिए सीमा निर्धारित नहीं करता है।[3]

कनेक्टिविटी-आधारित (पदानुक्रमित क्लस्टरिंग)

कनेक्टिविटी-आधारित क्लस्टरिंग या पदानुक्रमित क्लस्टरिंग इस विचार पर आधारित है कि वस्तुओं में दूर की तुलना में पास की अन्य वस्तुओं के साथ अधिक समानताएं होती हैं। इसलिए, इस प्रकार के एल्गोरिदम से उत्पन्न क्लस्टर विश्लेषण की गई वस्तुओं के मध्य की दूरी का परिणाम होंगे।

पदानुक्रमित मॉडल या तब विभाजनकारी हो सकते हैं, जहां विभाजन उपलब्ध संपूर्ण डेटा समूह से बनाए जाते हैं, या एकत्रित होते हैं, जहां प्रत्येक विभाजन एक ही ऑब्जेक्ट से प्रारंभ होता है और समूह में अतिरिक्त ऑब्जेक्ट जोड़े जाते हैं।[4] इस प्रकार यद्यपि पदानुक्रमित क्लस्टरिंग में किसी भी वैध मीट्रिक को परिभाषित दूरी के रूप में उपयोग करने की अनुमति देने का लाभ है, यह डेटा समूह में ध्वनि और उतार-चढ़ाव के प्रति संवेदनशील है और इसे स्वचालित करना अधिक कठिन है।

उपस्तिथ पदानुक्रमित क्लस्टरिंग एल्गोरिदम को उत्तम बनाने और स्वचालित करने के लिए तरीके विकसित किए गए हैं[5] इस प्रकार जैसे एकल लिंकेज पदानुक्रमित क्लस्टर विश्लेषण (एचसीए) का एक स्वचालित संस्करण हैं। यह कम्प्यूटरीकृत पद्धति अपनी सफलता को एक आत्मनिर्भर बाह्य कटौती दृष्टिकोण पर आधारित करती है जिसके पश्चात् एक वर्णनात्मक फलन का निर्माण होता है जो प्राकृतिक समूहों को परिभाषित करने की अनुमति देता है। छोड़ी गई वस्तुओं को भी इन समूहों को सौंपा जा सकता है। इस प्रकार मूलतः, किसी को प्राकृतिक समूहों की पहचान करने के लिए बाहरी मापदंडों का सहारा लेने की आवश्यकता नहीं है। इस प्रकार एचसीए से एकत्रित जानकारी, स्वचालित और विश्वसनीय, प्राकृतिक समूहों की संख्या और संबंधित पृथक्करण के साथ एक डेंड्रोग्राम में फिर से प्रारंभ की जा सकती है, यह विकल्प मौलिक एचसीए में नहीं पाया जाता है। इस पद्धति में निम्नलिखित दो चरण सम्मिलित हैं: आउटलेर्स को हटाया जा रहा है (यह अनेक फ़िल्टरिंग अनुप्रयोगों में प्रयुक्त होता है) और एक वैकल्पिक वर्गीकरण जो वस्तुओं के पूरे समूह के साथ क्लस्टर का विस्तार करने की अनुमति देता है।[6]

बीआईआरसीएच (पदानुक्रम का उपयोग करके संतुलित पुनरावृत्त कम करना और क्लस्टरिंग) एक एल्गोरिदम है जिसका उपयोग बड़े डेटा-समूह के लिए कनेक्टिविटी-आधारित क्लस्टरिंग करने के लिए किया जाता है।[7] इस प्रकार इसे सबसे तेज़ क्लस्टरिंग एल्गोरिदम में से एक माना जाता है, किन्तु यह सीमित है क्योंकि इसमें इनपुट के रूप में क्लस्टर की संख्या की आवश्यकता होती है। इसलिए, बीआईआरसीएच पर आधारित नए एल्गोरिदम विकसित किए गए हैं जिनमें शुरुआत से ही क्लस्टर गिनती प्रदान करने की आवश्यकता नहीं है, किन्तु यह क्लस्टर की गुणवत्ता और गति को निरंतर रखता है। मुख्य संशोधन बीआईआरसीएच के अंतिम चरण को हटाना है, जहां उपयोगकर्ता को क्लस्टर गिनती इनपुट करना था, और डेटा से थ्रेशोल्ड पैरामीटर को अनुकूलित करके, बाकी एल्गोरिदम में सुधार करना है, जिसे ट्री-बीआईआरसीएच कहा जाता है। इस प्रकार परिणामी एल्गोरिदम में, थ्रेशोल्ड पैरामीटर की गणना अधिकतम क्लस्टर त्रिज्या और क्लस्टर के मध्य न्यूनतम दूरी से की जाती है, जिसे अधिकांशतः जाना जाता है। इस प्रकार यह विधि हजारों समूहों के डेटा समूह के लिए कारगर सिद्ध हुई। यदि उस राशि से आगे जाने पर, एक सुपरक्लस्टर विभाजन समस्या प्रस्तुत की जाती है। इसके लिए, एमडीबी-बिर्च जैसे अन्य एल्गोरिदम विकसित किए गए हैं, जो अपेक्षाकृत उच्च गति के साथ सुपर क्लस्टर विभाजन को कम करता है।[8]

घनत्व-आधारित

विभाजन और पदानुक्रमित तरीकों के विपरीत, घनत्व-आधारित क्लस्टरिंग एल्गोरिदम केवल गोले ही नहीं, किंतु किसी भी मनमाने आकार के क्लस्टर ढूंढने में सक्षम हैं।

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

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

समूहों की पहचान करने के लिए डेटा घनत्व के स्वचालन में, अनुसंधान को कृत्रिम रूप से एल्गोरिदम उत्पन्न करने पर भी ध्यान केंद्रित किया गया है। उदाहरण के लिए, वितरण एल्गोरिदम का अनुमान निर्देशित अचक्रीय ग्राफ (डीएजी) द्वारा वैध एल्गोरिदम की पीढ़ी की गारंटी देता है, जिसमें नोड्स प्रक्रियाओं (बिल्डिंग ब्लॉक) का प्रतिनिधित्व करते हैं और किनारे दो नोड्स के मध्य संभावित निष्पादन अनुक्रमों का प्रतिनिधित्व करते हैं। इस प्रकार बिल्डिंग ब्लॉक्स ईडीए की वर्णमाला या, दूसरे शब्दों में, किसी भी उत्पन्न एल्गोरिदम को निर्धारित करते हैं। इस प्रकार प्रायोगिक परिणामों में कृत्रिम रूप से उत्पन्न क्लस्टरिंग एल्गोरिदम की तुलना डीबीएससीएएन, एक मैनुअल एल्गोरिदम से की जाती है।[11]

संदर्भ

  1. Outlier
  2. "के-मीन्स क्लस्टरिंग के लिए क्लस्टर की इष्टतम संख्या निर्धारित करने के लिए कोहनी विधि का उपयोग करना". bl.ocks.org. Retrieved 2018-11-12.
  3. Hamerly, Greg; Elkan, Charles (9 December 2003). Sebastian Thrun; Lawrence K Saul; Bernhard H Schölkopf (eds.). k को k-साधनों में सीखना (PDF). Proceedings of the 16th International Conference on Neural Information Processing Systems (in English). Whistler, British Columbia, Canada: MIT Press. pp. 281–288. Archived from the original (PDF) on 16 October 2022. Retrieved 3 November 2022.{{cite conference}}: CS1 maint: date and year (link)
  4. "Introducing Clustering II: Clustering Algorithms - GameAnalytics". GameAnalytics (in English). 2014-05-20. Retrieved 2018-11-06.
  5. Almeida, J.A.S.; Barbosa, L.M.S.; Pais, A.A.C.C.; Formosinho, S.J. (June 2007). "Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering" (PDF). Chemometrics and Intelligent Laboratory Systems (in English). Elsevier. 87 (2): 208–217. doi:10.1016/j.chemolab.2007.01.005. hdl:10316/5042. Retrieved 3 November 2022.
  6. Almeida, J.A.S.; Barbosa, L.M.S.; Pais, A.A.C.C.; Formosinho, S.J. (2007-06-15). "Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering" (PDF). Chemometrics and Intelligent Laboratory Systems (in English). 87 (2): 208–217. doi:10.1016/j.chemolab.2007.01.005. hdl:10316/5042. ISSN 0169-7439.
  7. Zhang, Tian; Ramakrishnan, Raghu; Livny, Miron; Zhang, Tian; Ramakrishnan, Raghu; Livny, Miron (1996-06-01). "BIRCH: an efficient data clustering method for very large databases, BIRCH: an efficient data clustering method for very large databases". ACM SIGMOD Record. 25 (2): 103, 103–114, 114. doi:10.1145/235968.233324. ISSN 0163-5808.
  8. Lorbeer, Boris; Kosareva, Ana; Deva, Bersant; Softić, Dženan; Ruppel, Peter; Küpper, Axel (2018-03-01). "क्लस्टरिंग एल्गोरिथम BIRCH पर बदलाव". Big Data Research (in English). 11: 44–53. doi:10.1016/j.bdr.2017.09.002. ISSN 2214-5796.
  9. "How Density-based Clustering works—ArcGIS Pro | ArcGIS Desktop". pro.arcgis.com (in English). Retrieved 2018-11-05.
  10. "स्थानीय घनत्व क्लस्टरिंग के आधार पर क्लस्टर केंद्रों की स्वचालित पहचान के लिए एक एल्गोरिदम - आईईईई सम्मेलन प्रकाशन" (in English). doi:10.1109/CCDC.2017.7978726. S2CID 23267464. {{cite journal}}: Cite journal requires |journal= (help)
  11. "AutoClustering: An estimation of distribution algorithm for the automatic generation of clustering algorithms - IEEE Conference Publication" (in English). doi:10.1109/CEC.2012.6252874. {{cite journal}}: Cite journal requires |journal= (help)