PAM जैसे क्लासिक k-मेडॉइड्स पार्टीशनिंग एल्गोरिदम छोटे डेटा सेट के लिए कुशलता से काम करते हैं लेकिन विशाल डेटा सेट के लिए अच्छी तरह से स्केल नहीं करते। उच्च डेटा सेट से निपटने के लिए, CLARA (क्लस्टरिंग लार्ज एप्लिकेशन) नामक एक सैंपलिंग-आधारित विधि का उपयोग किया जा सकता है।
CLARA के पीछे का दृष्टिकोण इस प्रकार है: यदि नमूना काफी यादृच्छिक तरीके से चुना जाता है, तो यह मूल डेटा सेट को करीब से परिभाषित करना चाहिए। चुने गए प्रतिनिधि ऑब्जेक्ट (मेडॉइड्स) उनसे समान होंगे जो पूरे डेटा सेट से चुने गए होते। CLARA डेटा सेट के कई नमूने खींचता है, प्रत्येक नमूने पर PAM लागू करता है, और अपने सर्वश्रेष्ठ क्लस्टरिंग को आउटपुट के रूप में लौटाता है।
CLARA का प्रदर्शन नमूना आकार पर आधारित है। यह देखा गया है कि PAM दिए गए डेटा सेट के बीच सर्वश्रेष्ठ k मेडॉइड्स की खोज करता है, जबकि CLARA डेटा सेट के चयनित नमूनों के बीच सर्वश्रेष्ठ k मेडॉइड्स की खोज करता है। CLARANS (क्लस्टरिंग लार्ज एप्लिकेशन डिपेंड्स अपॉन रैंडमाइज्ड सर्च) नामक एक k-मेडॉइड्स प्रकार का एल्गोरिदम प्रस्तावित किया गया था। यह PAM के साथ सैंपलिंग विधियों को जोड़ता है। जबकि CLARA में खोज के हर चरण में एक निश्चित नमूना होता है, CLARANS खोज के हर चरण में कुछ यादृच्छिकता के साथ एक नमूना खींचता है।
क्लस्टरिंग प्रक्रिया को एक ग्राफ के माध्यम से खोज के रूप में देखा जा सकता है, जहां प्रत्येक नोड एक संभावित समाधान (k मेडॉइड्स का एक सेट) है। दो नोड पड़ोसी हैं (विशेष रूप से, ग्राफ में एक चाप द्वारा जुड़े हुए) यदि उनके सेट केवल एक ऑब्जेक्ट द्वारा भिन्न होते हैं। प्रत्येक नोड को एक लागत दी जा सकती है जो प्रत्येक ऑब्जेक्ट और उसके क्लस्टर के मेडॉइड के बीच कुल असमानता द्वारा दर्शाई जाती है।
प्रत्येक चरण में, PAM अपनी खोज में नवीनतम नोड के सभी पड़ोसियों को न्यूनतम लागत समाधान के लिए निर्धारित करता है। नवीनतम नोड को तब लागत में सबसे बड़े अवरोही वाले पड़ोसी द्वारा प्रतिस्थापित किया जाता है। क्योंकि CLARA पूरे डेटा सेट के नमूने पर काम करती है, यह कम पड़ोसियों को निर्धारित करती है और खोज को उप-ग्राफ तक सीमित करती है जो प्रारंभिक ग्राफ से छोटे होते हैं।
CLARANS को प्रायोगिक रूप से PAM और CLARA दोनों की तुलना में अधिक कुशल दिखाया गया है। इसका उपयोग सिल्हूट गुणांक का उपयोग करके सबसे "प्राकृतिक" संख्या में क्लस्टर खोजने के लिए किया जा सकता है - एक ऑब्जेक्ट की संपत्ति जो परिभाषित करती है कि ऑब्जेक्ट वास्तव में क्लस्टर पर कितना लागू होता है। CLARANS आउटलेयर की खोज की भी अनुमति देता है।
CLARANS की कम्प्यूटेशनल जटिलता O(n²) है जहां n ऑब्जेक्ट की संख्या है। इसके अलावा, इसकी क्लस्टरिंग गुणवत्ता उपयोग की गई सैंपलिंग विधि पर आधारित है। CLARANS की डिस्क पर रहने वाले डेटा ऑब्जेक्ट को प्रबंधित करने की क्षमता को स्थानिक डेटा संरचनाओं का पता लगाने वाली विधियों पर ध्यान केंद्रित करके और बेहतर बनाया जा सकता है, जिसमें R*-ट्री शामिल हैं।
