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