Chameleon เป็นอัลกอริธึมการจัดกลุ่มแบบลำดับชั้นที่ใช้การสร้างแบบจำลองแบบไดนามิกเพื่อตัดสินความคล้ายคลึงกันระหว่างคู่ของคลัสเตอร์ มีการเปลี่ยนแปลงโดยอิงจากจุดอ่อนที่สังเกตได้ของอัลกอริธึมการจัดกลุ่มแบบลำดับชั้น 2 แบบ เช่น ROCK และ CURE
ROCK และการออกแบบที่เกี่ยวข้องจะเน้นที่การเชื่อมต่อระหว่างคลัสเตอร์ ในขณะที่ละเลยข้อมูลเกี่ยวกับความใกล้ชิดของคลัสเตอร์ CURE และการออกแบบที่เกี่ยวข้องพิจารณาความใกล้ชิดของคลัสเตอร์ แต่ละเลยการเชื่อมต่อระหว่างกันของคลัสเตอร์ ใน Chameleon ความคล้ายคลึงของคลัสเตอร์ได้รับการประเมินโดยขึ้นอยู่กับว่าวัตถุที่เชื่อมต่อกันเป็นอย่างดีภายในคลัสเตอร์และระยะใกล้ของคลัสเตอร์ โดยเฉพาะอย่างยิ่ง คลัสเตอร์ 2 กลุ่มจะรวมกันหากการเชื่อมต่อระหว่างกันสูงและอยู่ใกล้กัน
ไม่ได้อิงตามโมเดลคงที่ที่ผู้ใช้จัดหา และสามารถปรับให้เข้ากับคุณลักษณะภายในของคลัสเตอร์ที่รวมกันได้โดยอัตโนมัติ กระบวนการผสานสนับสนุนการค้นพบคลัสเตอร์ที่เป็นธรรมชาติและเป็นเนื้อเดียวกัน และใช้สำหรับข้อมูลทุกประเภทโดยพิจารณาจากฟังก์ชันความคล้ายคลึงกันที่สามารถกำหนดได้
Chameleon ต้องการเทคนิคกราฟ k-nearest-neighbor เพื่อสร้างกราฟแบบเบาบาง โดยที่จุดยอดแต่ละจุดของกราฟกำหนดวัตถุข้อมูล และมีจุดยอดระหว่างจุดยอดสองจุด (วัตถุ) หากวัตถุหนึ่งอยู่ระหว่าง k-วัตถุที่คล้ายคลึงกันมากที่สุด ขอบมีน้ำหนักเพื่อสะท้อนความคล้ายคลึงกันระหว่างวัตถุ
Chameleon ใช้อัลกอริธึมการแบ่งส่วนกราฟเพื่อแบ่ง k-nearest-neighborgraph ออกเป็นคลัสเตอร์ย่อยที่ค่อนข้างเล็กจำนวนมาก สามารถใช้อัลกอริธึมการจัดกลุ่มแบบ agglomerativehierarchical ที่รวมกลุ่มย่อยซ้ำ ๆ ตามความคล้ายคลึงกัน มันสามารถระบุคู่ของคลัสเตอร์ย่อยที่คล้ายกันมากที่สุด โดยคำนึงถึงทั้งการเชื่อมต่อระหว่างกันและความใกล้ชิดของคลัสเตอร์
กราฟ k-nearest-neighbor รวบรวมวิธีการของพื้นที่ใกล้เคียงแบบไดนามิก:รัศมีพื้นที่ใกล้เคียงของวัตถุถูกกำหนดโดยความหนาแน่นของภูมิภาคที่วัตถุนั้นอาศัยอยู่ ในพื้นที่หนาแน่น พื้นที่ใกล้เคียงจะแสดงอย่างหวุดหวิด ในภูมิภาค asparse มีการแสดงอย่างกว้างขวางมากขึ้น
อิทธิพลนี้ส่งผลให้คลัสเตอร์เป็นธรรมชาติมากขึ้น เมื่อเทียบกับวิธีการที่อิงตามความหนาแน่น เช่น DBSCAN ที่ใช้พื้นที่ใกล้เคียงทั่วโลกแทน นอกจากนี้ ความหนาแน่นของพื้นที่จะถูกบันทึกเป็นน้ำหนักของขอบ โดยเฉพาะอย่างยิ่ง ขอบของบริเวณที่หนาแน่นมักจะมีน้ำหนักมากกว่าขอบของบริเวณที่เบาบาง
อัลกอริธึมการแบ่งพาร์ติชั่นกราฟจะแบ่งพาร์ติชั่นกราฟ k-nearest-neighbor เพื่อให้ขอบตัดเล็กลง นั่นคือ คลัสเตอร์ C ถูกแบ่งออกเป็น sub-clustersCi และ Cj เพื่อลดน้ำหนักของขอบที่สามารถตัดได้ควร C แบ่งเป็น Ci และ Cj . การตัดขอบถูกระบุ EC (Ci , Cj )และกำหนดการเชื่อมต่อระหว่างคลัสเตอร์ Ci และ Cj .
