एक विभाजन क्लस्टरिंग विधि वांछनीय है क्योंकि यह सेट और उनके क्लस्टर केंद्रों के बीच की दूरी को कम करती है। यदि यह k- साधन विधि चुन सकता है, तो बाधाओं के अस्तित्व को देखते हुए एक क्लस्टर केंद्र उपलब्ध नहीं हो सकता है।
उदाहरण के लिए, क्लस्टर एक झील के केंद्र में हो सकता है। दूसरे शब्दों में, k-medoids विधि एक केंद्र के रूप में क्लस्टर के अंदर एक वस्तु का चयन करती है और इस प्रकार गारंटी देती है कि कोई समस्या प्रकट नहीं हो सकती है।
हर बार एक नया मेडॉइड चुना जाता है, प्रत्येक वस्तु और उसके नए चयनित क्लस्टर केंद्र के बीच की दूरी को पुनर्गणना करना पड़ता है। क्योंकि दो वस्तुओं के बीच बाधाएँ हो सकती हैं, दो वस्तुओं के बीच की दूरी ज्यामितीय गणनाओं (जैसे, त्रिकोणासन को शामिल करके) द्वारा निकाली जा सकती है।
यदि बड़ी संख्या में वस्तुओं और बाधाओं को समाहित किया जाता है, तो कम्प्यूटेशनल लागत अधिक हो सकती है। बाधाओं की समस्या के क्लस्टरिंग को एक ग्राफिकल विवरण का उपयोग करके परिभाषित किया जा सकता है। सबसे पहले, एक बिंदु, p, एक अन्य बिंदु, q, क्षेत्र में R से स्पष्ट है, यदि सीधी रेखा p और q से सटे कुछ बाधाओं को नहीं काटती है।
एक दृश्यता ग्राफ ग्राफ़ है, वी जी =(वी, ई), बाधाओं के प्रत्येक शीर्ष सहित वी और दो नोड्स में एक समकक्ष नोड है, v1 और वी<उप>2 , V में E में एक किनारे से जोड़ दिया जाता है यदि और केवल तभी जब उनके द्वारा परिभाषित समतुल्य शीर्ष एक दूसरे को दिखाई देते हैं।
मान लीजिए VG' =(V', E') V' में दो अतिरिक्त बिंदु, p और q डालकर, VG से उत्पन्न एक दृश्यता ग्राफ है। E' में V0 में दो बिंदुओं को जोड़ने वाला एक किनारा शामिल है यदि दो बिंदु संयुक्त रूप से दिखाई दे रहे हैं।
इसका उपयोग वस्तुओं या बिंदुओं के किसी भी दो सेट के बीच दूरी गणना की लागत को कम करने के लिए किया जा सकता है, कई प्रीप्रोसेसिंग और अनुकूलन दृष्टिकोण का उपयोग किया जा सकता है। एक दृष्टिकोण समूह बिंदु है जो सूक्ष्म समूहों में एक साथ निकट हैं। इसे पहले क्षेत्र R को त्रिभुजों में त्रिभुज करके, और फिर समान त्रिभुज में आस-पास के बिंदुओं को माइक्रोक्लस्टर में जोड़कर, BIRCH या DBSCAN के समान दृष्टिकोण का उपयोग करके पूरा किया जा सकता है।
एकल बिंदुओं के बजाय माइक्रोक्लस्टर को संसाधित करके, पूर्ण गणना कम हो जाती है। उसके बाद, दो प्रकार के जॉइन इंडेक्स बनाने के लिए प्रीकंप्यूटेशन लागू किया जा सकता है जो सबसे छोटे पथों की गणना पर निर्भर करता है -
-
VV सूचकांक, कुछ जोड़ी बाधाओं के लिए।
-
माइक्रोक्लस्टर और बाधा शीर्ष की कुछ जोड़ी के लिए एमवी सूचकांक। यह सूचकांक को सुविधाजनक बना सकता है और समग्र प्रदर्शन को और अधिक अनुकूलित करने में मदद करता है।
इस तरह के प्रीकंप्यूटेशन और अनुकूलन के साथ, किन्हीं दो बिंदुओं के बीच की दूरी (माइक्रोक्लस्टर के ग्रैन्युलैरिटी दृष्टिकोण पर) की प्रभावी ढंग से गणना की जा सकती है। इसलिए, क्लस्टरिंग प्रक्रिया को एक विशिष्ट प्रभावी k-medoids एल्गोरिदम के समान तरीके से कार्यान्वित किया जा सकता है, जिसमें CLARANS भी शामिल है, और विशाल डेटा सेट के लिए सर्वोत्तम क्लस्टरिंग गुणवत्ता प्राप्त कर सकता है।