🤸 👩‍👩‍👦‍👦 🤛🏻 न्यूमेरिकल डेटा स्पेस क्लस्टरिंग एल्गोरिदम का अवलोकन ‼️ 🌀 🕊️

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

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

विभाजन के तरीके

तरीकों के इस परिवार के सबसे प्रसिद्ध प्रतिनिधि हैं k- साधन [1] और k-medoids [2] एल्गोरिदम। वे इनपुट पैरामीटर k लेते हैं और डेटा स्पेस को k क्लस्टर में विभाजित करते हैं जैसे कि समान क्लस्टर की वस्तुओं के बीच समानता अधिकतम होती है, और विभिन्न समूहों की वस्तुओं के बीच न्यूनतम होती है। समानता को केंद्र के विचाराधीन वस्तु से दूरी के रूप में क्लस्टर के कुछ केंद्र के संबंध में मापा जाता है। इन विधियों के बीच मुख्य अंतर क्लस्टर केंद्र निर्धारित करने के तरीके से है।

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

क्लस्टरिंग के परिणाम पर अंतरिक्ष के शोर और पृथक बिंदुओं के प्रभाव को कम करने के लिए, k- साधनों के विपरीत, k-medoids एल्गोरिथ्म, क्लस्टर के केंद्र का प्रतिनिधित्व करने के लिए बड़े पैमाने पर केंद्र का उपयोग नहीं करता है, लेकिन एक प्रतिनिधि वस्तु - क्लस्टर में वस्तुओं में से एक है। जैसे कि k- साधन विधि में, पहले, k प्रतिनिधि वस्तुओं को मनमाने ढंग से चुना जाता है। शेष वस्तुओं में से प्रत्येक को निकटतम प्रतिनिधि ऑब्जेक्ट के साथ एक क्लस्टर में संयुक्त किया गया है। फिर, प्रत्येक प्रतिनिधि ऑब्जेक्ट के लिए पुनरावृत्त रूप से, इसे डेटा स्थान के एक मनमाने ढंग से गैर-प्रतिनिधि ऑब्जेक्ट द्वारा बदल दिया जाता है। प्रतिस्थापन प्रक्रिया तब तक जारी रहती है जब तक कि परिणामी समूहों की गुणवत्ता में सुधार नहीं होता है। क्लस्टरिंग की गुणवत्ता प्रत्येक ऑब्जेक्ट और संबंधित क्लस्टर के प्रतिनिधि ऑब्जेक्ट के बीच विचलन के योग से निर्धारित होती है, जिसे विधि कम से कम करना चाहती है। अर्थात्, पुनरावृत्तियों तब तक जारी रहती है जब तक कि प्रत्येक क्लस्टर में इसका प्रतिनिधि ऑब्जेक्ट एक हनीओइड नहीं बन जाता है - ऑब्जेक्ट क्लस्टर के केंद्र के सबसे करीब है। बड़ी मात्रा में डेटा को संसाधित करने के लिए एल्गोरिथ्म अच्छा नहीं है, लेकिन क्लैरस एल्गोरिथ्म [3] के-मेडोइड्स विधि का अनुपालन करता है। CLARANS पर आधारित बहुआयामी रिक्त स्थान को क्लस्टर करने के लिए, PROCLUS एल्गोरिथ्म का निर्माण किया गया था [4]।

पदानुक्रमित तरीके

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

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

घनत्व की विधियाँ

समूहों को वस्तुओं के उच्च घनत्व वाले डेटा स्पेस के क्षेत्र के रूप में माना जाता है, जो वस्तुओं के कम घनत्व वाले क्षेत्रों से विभाजित होते हैं।

DBSCAN एल्गोरिथ्म [7] पहले घनत्व क्लस्टरिंग एल्गोरिदम में से एक है। यह एल्गोरिथ्म कई परिभाषाओं पर आधारित है:

किसी वस्तु का An-पड़ोस किसी वस्तु के त्रिज्या of का पड़ोस है।
एक रूट ऑब्जेक्ट एक ऐसी वस्तु है जिसका contains- पड़ोस में कम से कम न्यूनतम न्यूनतम संख्या में ऑब्जेक्ट होते हैं।
यदि ऑब्जेक्ट p- पड़ोस में q और q के मूल ऑब्जेक्ट है, तो ऑब्जेक्ट p से एक ऑब्जेक्ट पी सीधे कसकर पहुंच योग्य है।
किसी ऑब्जेक्ट p को दिए गए given और MinPts के लिए q से कसकर उपलब्ध किया जा सकता है यदि कोई ऑब्जेक्ट p ₁ , ..., p _n , जहाँ p ₁ = q और p _n = p मौजूद है, तो p _{i i} +1 p से कसकर पहुंच योग्य है। 1 ≤ i ≤ n ।
ऑब्जेक्ट p दिए गए p और MinPts के लिए ऑब्जेक्ट q से कसकर जुड़ा हुआ है यदि कोई ऑब्जेक्ट o मौजूद है जैसे p और q कसकर o से पहुंच योग्य हैं ।

समूहों के लिए खोज करने के लिए, DBSCAN एल्गोरिथ्म प्रत्येक वस्तु के of-पड़ोस की जांच करता है। यदि p के the- पड़ोस में MinPts से अधिक अंक हैं, तो रूट ऑब्जेक्ट p के साथ एक नया क्लस्टर बनाया जाता है। DBSCAN फिर पुनरावृत्त वस्तुओं को सीधे जड़ वस्तुओं से कसकर इकट्ठा करता है, जिससे कई कसकर पुन: प्राप्त करने वाले समूहों का मिलन हो सकता है। जब कोई भी नया ऑब्जेक्ट किसी क्लस्टर में नहीं जोड़ा जा सकता है तो प्रक्रिया समाप्त हो जाती है।

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

नेटवर्क के तरीके

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

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

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

मॉडल के तरीके

इस परिवार के तरीके बताते हैं कि डेटा स्पेस में क्लस्टर के कुछ गणितीय मॉडल हैं और इस मॉडल और उपलब्ध डेटा की समानता को अधिकतम करना चाहते हैं। अक्सर, गणितीय आंकड़ों के उपकरण का उपयोग किया जाता है।

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

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

वैचारिक क्लस्टरिंग

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

COBWEB एल्गोरिथ्म [12] वृद्धिशील वैचारिक क्लस्टरिंग का एक शास्त्रीय तरीका है। यह वर्गीकरण के पेड़ के रूप में एक श्रेणीबद्ध क्लस्टरिंग बनाता है: इस पेड़ के प्रत्येक नोड में एक अवधारणा होती है और इस अवधारणा का एक संभाव्य विवरण होता है, जिसमें यह संभावना शामिल होती है कि यह अवधारणा इस नोड के रूप और सशर्त संभावनाओं से संबंधित है: P (A _i = v _ij C _k )। जहां A _i = v _ij एक विशेषता-मूल्य जोड़ी है, C _k एक अवधारणा वर्ग है।
वर्गीकरण पेड़ के एक निश्चित स्तर पर स्थित नोड्स को एक टुकड़ा कहा जाता है। एल्गोरिथ्म वर्गीकरण श्रेणी के पेड़ का निर्माण करने के लिए श्रेणी की उपयोगिता कहे जाने वाले मूल्यांकन के एक हेयुरिस्टिक माप का उपयोग करता है - इस ज्ञान के बिना मूल्यों के बारे में सही मान्यताओं की अपेक्षित संख्या के सापेक्ष एक निश्चित श्रेणी के ज्ञान के साथ विशेषता मूल्यों के बारे में सही मान्यताओं की अपेक्षित संख्या में वृद्धि। वर्गीकरण ट्री में एक नई वस्तु को एम्बेड करने के लिए, COBWEB एल्गोरिथ्म "सर्वश्रेष्ठ" नोड की तलाश में पूरे पेड़ का पता लगाता है जिसमें यह ऑब्जेक्ट है। एक नोड का विकल्प प्रत्येक नोड में ऑब्जेक्ट को रखने और परिणामी स्लाइस की श्रेणी की उपयोगिता की गणना करने पर आधारित है। श्रेणी की उपयोगिता की गणना उस स्थिति के लिए भी की जाती है जब ऑब्जेक्ट एक नए बनाए गए नोड से संबंधित होता है। परिणामस्वरूप, ऑब्जेक्ट नोड को संदर्भित करता है जिसके लिए श्रेणी की उपयोगिता अधिक होती है।
हालाँकि, COBWEB की कई सीमाएँ हैं। सबसे पहले, वह सुझाव देता है कि विभिन्न विशेषताओं के मूल्यों के संभाव्यता वितरण सांख्यिकीय रूप से एक दूसरे से स्वतंत्र हैं। हालांकि, यह धारणा हमेशा सच नहीं होती है, क्योंकि अक्सर विशेषता मूल्यों के बीच संबंध होता है। दूसरे, समूहों का संभावित प्रतिनिधित्व उन्हें अद्यतन करने के लिए बहुत मुश्किल बनाता है, खासकर जब विशेषताओं में बड़ी संख्या में संभावित मूल्य होते हैं। ऐसा इसलिए है क्योंकि एल्गोरिथ्म की जटिलता न केवल विशेषताओं की संख्या पर निर्भर करती है, बल्कि संभावित मूल्यों की संख्या पर भी निर्भर करती है।

न्यूमेरिकल डेटा स्पेस क्लस्टरिंग एल्गोरिदम का अवलोकन