बाधाओं के साथ क्लस्टरिंग के तरीके क्या हैं?

बाधाओं के साथ क्लस्टरिंग के तरीके

विशिष्ट बाधाओं को संभालने के लिए विभिन्न तकनीकों की आवश्यकता होती है। कठिन और नरम बाधाओं को संभालने के सामान्य सिद्धांत निम्नलिखित हैं:

कठिन बाधाओं को संभालना (Handling Hard Constraints)

कठिन बाधाओं को संभालने की एक सामान्य विधि क्लस्टर असाइनमेंट प्रक्रिया में बाधाओं को सख्ती से मानना है। एक डेटा सेट और उदाहरणों पर बाधाओं के एक समूह (यानी, मस्ट-लिंक या कैनॉट-लिंक बाधाएं) दिए जाने पर, हम k-मीन्स दृष्टिकोण को ऐसी बाधाओं को पूरा करने के लिए कैसे विकसित कर सकते हैं? COP-kmeans एल्गोरिदम निम्नानुसार काम करता है:

मस्ट-लिंक बाधाओं के लिए सुपर इंस्टेंस उत्पन्न करना

यह मस्ट-लिंक बाधाओं के संक्रामक समापन की गणना कर सकता है। इसलिए, सभी मस्ट-लिंक बाधाओं को एक समतुल्य संबंध माना जाता है। समापन वस्तुओं के एक या कई उपसमूह प्रदान करता है जहां एक उपसमूह में कुछ वस्तुओं को एक क्लस्टर को सौंपा जाना चाहिए।

ऐसे उपसमूह को परिभाषित करने के लिए, यह उपसमूह में कुछ वस्तुओं को माध्य से बदल सकता है। सुपर इंस्टेंस भी एक वजन उत्पन्न करता है, जो उन वस्तुओं की संख्या है जो इसे परिभाषित करती हैं। इस प्रक्रिया के बाद, मस्ट-लिंक बाधाएं लगातार संतुष्ट होती हैं।

संशोधित k-मीन्स क्लस्टरिंग संचालन

k-मीन्स में, एक वस्तु को निकटतम केंद्र को सौंपा जाता है। कैनॉट-लिंक बाधाओं का सम्मान करने के लिए, यह k-मीन्स में केंद्र असाइनमेंट प्रक्रिया को निकटतम व्यवहार्य केंद्र असाइनमेंट में बदल देता है।

जब वस्तुओं को क्रमिक रूप से केंद्रों को सौंपा जाता है, तो प्रत्येक चरण में यह सुनिश्चित कर सकता है कि अब तक के असाइनमेंट किसी भी कैनॉट-लिंक बाधाओं को बाधित नहीं करते हैं। एक वस्तु को निकटतम केंद्र को सौंपा जाता है ताकि असाइनमेंट कुछ कैनॉट-लिंक बाधाओं का सम्मान करे।

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

नरम बाधाओं को संभालना (Handling Soft Constraints)

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

एक डेटा सेट और उदाहरणों पर नरम बाधाओं के एक सेट को देखते हुए, CVQE (कंस्ट्रेन्ड वेक्टर क्वांटाइजेशन एरर) एल्गोरिदम रणनीति k-मीन्स क्लस्टरिंग जबकि बाधा उल्लंघन दंड लागू करता है। CVQE में उपयोग किया जाने वाला उद्देश्य फ़ंक्शन k-मीन्स में उपयोग की जाने वाली दूरी का योग है, जिसे बाधा उल्लंघन दंड द्वारा संशोधित किया गया है, जिनकी गणना निम्नानुसार की जाती है:

मस्ट-लिंक उल्लंघन का दंड

यदि वस्तुओं x और y पर एक मस्ट-लिंक बाधा है, लेकिन उन्हें दो अलग-अलग केंद्रों, c₁ और c₂ को सौंपा गया है, तो बाधा का उल्लंघन होता है। परिणामस्वरूप, dist(c₁, c₂), c₁ और c₂ के बीच की दूरी, उद्देश्य फ़ंक्शन में दंड के रूप में जोड़ी जाती है।

कैनॉट-लिंक उल्लंघन का दंड

यदि वस्तुओं x और y पर एक कैनॉट-लिंक बाधा है, लेकिन उन्हें एक सामान्य केंद्र, c, को सौंपा गया है, तो बाधा का उल्लंघन होता है। दूरी, dist(c, c'), c और c' के बीच, उद्देश्य फ़ंक्शन में दंड के रूप में जोड़ी जाती है।