ROCK ย่อมาจาก Robust Clustering โดยใช้ลิงก์ เป็นอัลกอริธึมการจัดกลุ่มแบบลำดับชั้นที่วิเคราะห์แนวคิดของลิงก์ (จำนวนเพื่อนบ้านทั่วไปในสองอ็อบเจ็กต์) สำหรับข้อมูลที่มีแอตทริบิวต์หมวดหมู่ แสดงว่าข้อมูลระยะทางดังกล่าวไม่สามารถนำไปสู่คลัสเตอร์คุณภาพสูงเมื่อจัดกลุ่มข้อมูลหมวดหมู่
นอกจากนี้ อัลกอริธึมการทำคลัสเตอร์ส่วนใหญ่สร้างเฉพาะความคล้ายคลึงกันระหว่างจุดต่างๆ เมื่อทำคลัสเตอร์ กล่าวคือ ในแต่ละขั้นตอน จุดที่รวมกันเป็นคลัสเตอร์เดียว วิธีการ "แปลเป็นภาษาท้องถิ่น" นี้มีแนวโน้มที่จะเกิดข้อผิดพลาด ตัวอย่างเช่น คลัสเตอร์ที่แตกต่างกันสองคลัสเตอร์สามารถมีจุดหรือค่าผิดปกติที่อยู่ใกล้เคียงได้สองสามจุด ดังนั้น การอาศัยความคล้ายคลึงกันระหว่างจุดต่างๆ เพื่อสร้างการตัดสินใจแบบคลัสเตอร์ สามารถสร้างคลัสเตอร์ทั้งสองที่จะรวมกันได้
ROCK ใช้วิธีการที่เป็นสากลมากขึ้นในการจัดกลุ่มโดยปฏิบัติต่อย่านใกล้เคียงที่มีจุดคู่เดียว หากจุดสองจุดที่คล้ายคลึงกันมีย่านใกล้เคียงเหมือนกัน จุดสองจุดนั้นน่าจะอยู่ในกระจุกที่คล้ายกันและสามารถนำมารวมกันได้
มีสองจุด pi และ pj , เป็นเพื่อนบ้านถ้า sim(pi , pj ) ≥ θ โดยที่ sim เป็นฟังก์ชันความคล้ายคลึงกัน และ θ คือขีดจำกัดที่ผู้ใช้กำหนด สามารถเลือกซิมเป็นเมตริกระยะทาง หรือแม้กระทั่งไม่เมตริกที่ถูกทำให้เป็นมาตรฐาน โดยค่าของซิมจะอยู่ระหว่าง 0 และ 1 โดยค่าที่สูงกว่าแสดงว่าคะแนนเท่ากันมากกว่า
จำนวนการเชื่อมต่อระหว่าง pi และ pj แสดงเป็นจำนวนเพื่อนบ้านร่วมกันระหว่าง pi และ pj . หากจำนวนลิงก์ระหว่างจุดสองจุดสูง ก็มีแนวโน้มว่าจะอยู่ในคลัสเตอร์ที่คล้ายคลึงกัน ด้วยการจัดการจุดข้อมูลที่อยู่ใกล้เคียงในความสัมพันธ์ระหว่างกลุ่มจุดแต่ละกลุ่ม ROCK มีประสิทธิภาพมากกว่าวิธีการจัดกลุ่มมาตรฐานที่กำหนดเป้าหมายเฉพาะจุดที่มีความคล้ายคลึงกัน
ตัวอย่างของข้อมูลรวมถึงแอตทริบิวต์ที่เป็นหมวดหมู่คือข้อมูลตะกร้าสินค้าของตลาด ข้อมูลดังกล่าวรวมถึงฐานข้อมูลของธุรกรรม โดยแต่ละรายการคือกลุ่มของรายการ ธุรกรรมจะได้รับการจัดการข้อมูลด้วยแอตทริบิวต์บูลีน โดยแต่ละรายการจะสอดคล้องกับรายการเดียว รวมถึงขนมปังหรือชีส
ในข้อมูลสำหรับธุรกรรม คุณลักษณะที่สอดคล้องกับรายการนั้นถูกต้อง หากธุรกรรมรวมรายการนั้น มิฉะนั้นจะเป็นเท็จ มีชุดข้อมูลหลายชุดที่มีแอตทริบิวต์หมวดหมู่ที่สามารถจัดการได้ในลักษณะเดียวกัน เงื่อนไขเพื่อนบ้านและลิงก์ของ ROCK เหมือนกันระหว่าง "คะแนน" หรือธุรกรรมสองรายการ Ti และ Tj , แสดงด้วยสัมประสิทธิ์ Jaccard เป็น
$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \cup T_{j}|}}$ $
ROCK สร้างกราฟเบาบางจากเมทริกซ์ความคล้ายคลึงของข้อมูลที่กำหนดโดยใช้เกณฑ์ความคล้ายคลึงกันและวิธีการของเพื่อนบ้านที่ใช้ร่วมกัน สามารถใช้การจัดกลุ่มตามลำดับชั้นแบบรวมกลุ่มบนกราฟแบบกระจาย การวัดความดีสามารถคำนวณการจัดกลุ่มได้ สามารถใช้การสุ่มตัวอย่างเพื่อขยายได้ถึงชุดข้อมูลสูง
ความซับซ้อนของเวลาที่แย่ที่สุดของ ROCK คือ O(n 2 + นาโนเมตรม มa + n 2 บันทึกn ) โดยที่ mm และ ma จำนวนเพื่อนบ้านสูงสุดและเฉลี่ยตามลำดับคือ และ n คือจำนวนวัตถุ
