Cluster Analysis เป็นสาขาของสถิติที่ศึกษามาหลายปี ความได้เปรียบของเทคนิคนี้คือโครงสร้างหรือ Clusters ที่น่าสนใจสามารถค้นพบได้โดยตรงจากข้อมูลโดยไม่ใช้ Background Knowledge ใดๆ เช่น Concept Hierarchy
Clustering Algorithms ที่ใช้ในสถิติ เช่น PAM หรือ CLARA รายงานว่าไม่มีประสิทธิภาพจากมุมมอง Computational Complexity ตาม Efficiency Concern อัลกอริทึมใหม่ชื่อ CLARANS (Clustering Large Applications based upon Randomized Search) ถูกพัฒนาสำหรับ Cluster Analysis
PAM (Partitioning around Medoids)
สมมติว่ามี n Objects PAM หา k Clusters โดยหา Representative Object สำหรับแต่ละ Cluster ก่อน Representative นี้ซึ่งเป็นจุดที่ตั้งอยู่กลางใน Cluster เรียกว่า Medoid
หลังเลือก k Medoids Algorithm พยายามสร้าง Best Choice ของ Medoids ซ้ำๆ โดยวิเคราะห์ All Feasible Pairs ของ Objects ที่ Object หนึ่งเป็น Medoid และอีกตัวไม่ใช่ Clustering Quality Measure คำนวณสำหรับแต่ละ Combination
Good Choice ของ Points ใน Iteration หนึ่ง ถูกเลือกเป็น Medoids สำหรับ Iteration ถัดไป Cost ของ Single Iteration คือ O(k(n−k)2) จึง Computationally Inefficient สำหรับค่า n และ k ที่ใหญ่
CLARA (Clustering Large Applications)
ความแตกต่างระหว่าง PAM และ CLARA คือ CLARA พิงพึ่ง Sampling มีเพียง Small Portion ของ Real Data ถูกเลือกเป็น Representative ของข้อมูล และ Medoids ถูกเลือกจาก Sample นี้โดยใช้ PAM
แนวคิดคือ หาก Sample ถูกเลือกในลักษณะ Random อย่างสมเหตุสมผล แล้วมันจะ Represent Whole Dataset อย่างถูกต้อง และ Representative Objects (Medoids) ที่เลือก จะเหมือนกับที่เลือกจาก Whole Dataset
CLARA ดึง Several Samples และ Output Best Clustering จาก Samples เหล่านี้ CLARA จัดการ Dataset ใหญ่กว่า PAM ได้ Complexity ของแต่ละ Iteration กลายเป็น O(kS2 + k(n−k)) โดย S คือ Sample Size
CLARANS (Clustering Large Applications based upon RANdomized Search)
CLARANS Algorithm รวม PAM และ CLARA โดยค้นหาเพียง Subset ของ Dataset และไม่ Constraint ตนเองไปที่ Sample ใดๆ ในเวลาใดเวลาหนึ่ง ในขณะที่ CLARA มี Constant Sample ที่แต่ละ Phase ของการค้นหา CLARANS ดึง Sample ด้วย Randomness บางอย่างในทุก Phase ของการค้นหา
Clustering Phase สามารถนำเสนอเป็นการค้นหา Graph ที่แต่ละ Node เป็น Possible Solution คือ Set ของ k Medoids Clustering ที่ได้หลัง Replace Single Medoid เรียกว่า Neighbor ของ Current Clustering
