อัลกอริธึมการแบ่งพาร์ติชัน k-medoids แบบคลาสสิก เช่น PAM ทำงานอย่างมีประสิทธิภาพสำหรับชุดข้อมูลขนาดเล็ก แต่ไม่สามารถปรับขยายได้ดีสำหรับชุดข้อมูลขนาดใหญ่ สามารถใช้จัดการกับชุดข้อมูลที่สูงกว่า ซึ่งใช้วิธีสุ่มตัวอย่างที่เรียกว่า CLARA (Clustering Large Applications)
แนวทางเบื้องหลังของคลาร่ามีดังนี้ หากเลือกตัวอย่างในลักษณะสุ่มอย่างเป็นธรรม จะต้องกำหนดชุดข้อมูลดั้งเดิมอย่างใกล้ชิด วัตถุตัวแทน (medoids) ที่เลือกจะคล้ายกับวัตถุที่ถูกเลือกจากชุดข้อมูลทั้งหมด CLARA ดึงตัวอย่างชุดข้อมูลหลายชุด ใช้ PAM กับแต่ละตัวอย่าง และส่งคืนการจัดกลุ่มที่ดีที่สุดเป็นเอาต์พุต
ประสิทธิภาพของคลาร่าขึ้นอยู่กับขนาดกลุ่มตัวอย่าง เป็นที่สังเกตว่า PAM ค้นหา k medoid ที่ดีที่สุดระหว่างชุดข้อมูลที่กำหนด ในขณะที่ CLARA ค้นหา k medoids ที่ดีที่สุดระหว่างตัวอย่างที่เลือกของชุดข้อมูล มีการเสนออัลกอริธึมประเภท k-medoids ที่รู้จักกันในชื่อ CLARANS (Clustering Large Applications ขึ้นอยู่กับ RANdomized Search) สามารถเชื่อมต่อวิธีการสุ่มตัวอย่างกับ PAM แม้ว่าคลาร่าจะมีตัวอย่างตายตัวในทุกขั้นตอนของการค้นหา แต่คลารานส์จะสุ่มตัวอย่างด้วยการสุ่มในทุกขั้นตอนของการค้นหา
ขั้นตอนการจัดกลุ่มสามารถดูเป็นการค้นหาผ่านกราฟ โดยที่แต่ละโหนดเป็นวิธีแก้ปัญหาที่น่าจะเป็นไปได้ (ชุดของ k medoids) โหนดสองโหนดเป็นเพื่อนบ้าน (โดยเฉพาะอย่างยิ่ง เชื่อมโยงด้วยส่วนโค้งในกราฟ) หากชุดของโหนดต่างกันโดยวัตถุเพียงชิ้นเดียว แต่ละโหนดสามารถกำหนดต้นทุนที่แสดงโดยความแตกต่างทั้งหมดระหว่างแต่ละออบเจ็กต์กับค่ากลางของคลัสเตอร์
ในแต่ละขั้นตอน PAM จะกำหนดเพื่อนบ้านทั้งหมดของโหนดล่าสุดในการค้นหาโซลูชันต้นทุนขั้นต่ำ โหนดล่าสุดจะถูกแทนที่โดยเพื่อนบ้านด้วยต้นทุนที่ลดลงอย่างมาก เนื่องจาก CLARA ดำเนินการกับตัวอย่างของชุดข้อมูลทั้งหมด จึงกำหนดเพื่อนบ้านน้อยกว่าและจำกัดการค้นหาเฉพาะกราฟย่อยที่เล็กกว่ากราฟเริ่มต้น
CLARANS ได้รับการทดสอบแล้วว่ามีประสิทธิภาพมากกว่าทั้ง PAM และ CLARA สามารถใช้เพื่อค้นหาจำนวนกลุ่มที่ "เป็นธรรมชาติ" ที่สุดโดยใช้สัมประสิทธิ์ภาพเงาซึ่งเป็นคุณสมบัติของวัตถุที่กำหนดว่าวัตถุจะนำไปใช้กับคลัสเตอร์จริง ๆ มากน้อยเพียงใด คลารันส์ยังช่วยให้ค้นพบค่าผิดปกติได้อีกด้วย
ความซับซ้อนในการคำนวณของคลารันส์คือ O(n 2 ) โดยที่ n คือจำนวนวัตถุ นอกจากนี้ คุณภาพการจัดกลุ่มจะขึ้นอยู่กับวิธีการสุ่มตัวอย่างที่ใช้ ความสามารถของ CLARANS ในการจัดการกับออบเจ็กต์ข้อมูลที่อยู่ในดิสก์สามารถปรับปรุงได้ด้วยการมุ่งเน้นที่วิธีการที่สำรวจโครงสร้างข้อมูลเชิงพื้นที่ ซึ่งรวมถึง R*-trees
