การวิเคราะห์คลัสเตอร์เป็นสาขาหนึ่งของสถิติที่ได้รับการศึกษาอย่างกว้างขวางเป็นเวลาหลายปี ประโยชน์ของการใช้เทคนิคนี้คือสามารถค้นพบโครงสร้างหรือคลัสเตอร์ที่น่าสนใจได้โดยตรงจากข้อมูลโดยไม่ต้องใช้ความรู้พื้นฐานใดๆ เช่น ลำดับชั้นของแนวคิด
อัลกอริธึมการจัดกลุ่มที่ใช้ในสถิติ เช่น PAM หรือ CLARA ได้รับการรายงานว่าไม่มีประสิทธิภาพจากมุมมองของความซับซ้อนในการคำนวณ ตามข้อกังวลด้านประสิทธิภาพ อัลกอริทึมใหม่ที่เรียกว่า CLARANS (Clustering Large Applications ตาม Randomized Search) ได้รับการพัฒนาสำหรับการวิเคราะห์คลัสเตอร์
PAM (การแบ่งพาร์ติชันรอบ Medoids) − สมมติว่ามีวัตถุ n รายการ PAM จะค้นหากลุ่ม k โดยการค้นหาวัตถุที่เป็นตัวแทนสำหรับแต่ละคลัสเตอร์ก่อน ตัวแทนดังกล่าวซึ่งเป็นศูนย์กลางของกระจุกดาวเรียกว่า medoid
หลังจากเลือก k medoids อัลกอริธึมจะพยายามสร้างตัวเลือกที่ดีที่สุดซ้ำ ๆ ของ medoids เพื่อวิเคราะห์คู่ของอ็อบเจกต์ที่เป็นไปได้ทั้งหมด โดยที่ออบเจกต์หนึ่งเป็น medoid และอีกอันไม่ใช่ การวัดคุณภาพการจัดกลุ่มจะถูกคำนวณสำหรับแต่ละชุดค่าผสมดังกล่าว
ตัวเลือกที่ดีของคะแนนในการวนซ้ำหนึ่งครั้งจะถูกเลือกให้เป็น medoids สำหรับการวนซ้ำต่อไปนี้ ค่าใช้จ่ายในการทำซ้ำครั้งเดียวคือ O(k(n−k) 2 ) . ดังนั้นจึงไม่มีประสิทธิภาพในการคำนวณสำหรับค่า n และ k จำนวนมาก
CLARA (การจัดกลุ่มแอปพลิเคชันขนาดใหญ่) − ความแตกต่างระหว่างอัลกอริธึม PAM และ CLARA คืออัลกอริธึมต่อไปนี้อิงจากการสุ่มตัวอย่าง มีการเลือกข้อมูลจริงเพียงส่วนเล็ก ๆ เป็นตัวแทนของข้อมูลและเลือก medoids จากตัวอย่างนี้โดยใช้ PAM
แนวคิดก็คือถ้าตัวอย่างถูกเลือกในลักษณะสุ่มอย่างเป็นธรรม ก็จะแสดงถึงชุดข้อมูลทั้งหมดอย่างถูกต้อง ดังนั้นวัตถุที่เป็นตัวแทน (medoids) ที่เลือกจะคล้ายคลึงกันราวกับว่าเลือกจากชุดข้อมูลทั้งหมด
คลาร่าดึงตัวอย่างหลายตัวอย่างและส่งออกกลุ่มที่ดีจากตัวอย่างเหล่านี้ CLARA สามารถจัดการกับชุดข้อมูลที่สูงกว่า PAM ความซับซ้อนของการวนซ้ำแต่ละครั้งจะกลายเป็น O(kS 2 +k(n−k)) โดยที่ S คือขนาดของตัวอย่าง
CLARANS (จัดกลุ่มแอปพลิเคชันขนาดใหญ่ตามการค้นหาแบบสุ่ม) − อัลกอริทึมของ CLARANS รวมทั้ง PAM และ CLARA โดยการค้นหาเฉพาะชุดย่อยของชุดข้อมูลและไม่ได้จำกัดตัวเองกับกลุ่มตัวอย่างบางส่วนในช่วงเวลาที่กำหนด แม้ว่า CLARA จะมีตัวอย่างคงที่ในแต่ละขั้นตอนของการค้นหา CLARANS จะสุ่มตัวอย่างด้วยการสุ่มในทุกขั้นตอนของการค้นหา
ขั้นตอนการจัดกลุ่มสามารถนำเสนอเป็นการค้นหากราฟโดยที่แต่ละโหนดเป็นวิธีแก้ปัญหาที่เป็นไปได้ เช่น ชุดของ k medoids การจัดกลุ่มที่ได้รับหลังจากแทนที่ Medoid ตัวเดียวเรียกว่า Neighbor of Clustering ปัจจุบัน
