Classic K-medoids Partitioning Algorithm เช่น PAM ทำงาน Efficient สำหรับ Small Data Sets แต่ไม่ Scale Well สำหรับ Huge Data Sets เพื่อ Deal กับ Larger Data Sets Sampling-based Method เรียกว่า CLARA (Clustering Large Applications) ใช้ได้
Idea ของ CLARA: ถ้า Sample ถูกเลือกแบบ Fairly Random มันต้อง Represent Original Data Set ใกล้เคียง Representative Objects (Medoids) ที่เลือกจะคล้ายกับที่เลือกจาก Entire Data Set CLARA Draw Several Samples ของ Data Set Apply PAM บนแต่ละ Sample และ Return Best Clustering เป็น Output
Performance ของ CLARA ขึ้นอยู่กับ Sample Size สังเกตว่า PAM Search Best K Medoids ระหว่าง Given Data Set ในขณะที่ CLARA Search Best K Medoids ระหว่าง Selected Samples K-medoids Type Algorithm เรียกว่า CLARANS (Clustering Large Applications based on RANdomized Search) ถูก Propose เชื่อม Sampling Methods กับ PAM ในขณะที่ CLARA มี Fixed Sample ทุก Stage CLARANS Draw Sample ด้วย Randomness ในทุก Phase ของ Search
Clustering Procedure มองเป็น Search ผ่าน Graph โดยแต่ละ Node = Potential Solution (Set of K Medoids) 2 Nodes เป็น Neighbors (Linked by Arc) ถ้า Sets ต่างกันแค่ 1 Object แต่ละ Node Assign Cost = Total Dissimilarity ระหว่างแต่ละ Object และ Medoid ของ Cluster
ทุก Step PAM Examine All Neighbors ของ Current Node ใน Search สำหรับ Minimum Cost Solution Current Node แล้ว Replace ด้วย Neighbor ที่มี Greatest Descent ใน Costs เพราะ CLARA Operates บน Sample มัน Examine Fewer Neighbors และ Restrict Search ให้ Subgraphs ที่เล็กกว่า Initial Graph
CLARANS แสดงด้วย Experiment ว่า Efficient กว่า PAM และ CLARAN ทั้งคู่ สามารถใช้หา Most "Natural" Number of Clusters ใช้ Silhouette Coefficient Property ของ Object ที่ Define ว่า Object Apply ต่อ Cluster ได้แค่ไหน CLARANS ยัง Allow Discovery ของ Outliers
Computational Complexity ของ CLARANS คือ O(n2) โดย n = จำนวน Objects นอกจากนี้ Clustering Quality ขึ้นอยู่กับ Sampling Method ที่ใช้ ความสามารถของ CLARANS จัดการ Data Objects ที่ Reside on Disk สามารถ Improve เพิ่มเติมได้โดย Focus บน Methods ที่ Explore Spatial Data Structures เช่น R*-trees
