ROCK là viết tắt của Robust Clustering using links (Cụm hóa mạnh mẽ sử dụng liên kết). Đây là thuật toán cụm hóa phân cấp phân tích khái niệm links (số lượng láng giềng chung giữa hai đối tượng) cho dữ liệu với thuộc tính phân loại. Nó cho thấy dữ liệu khoảng cách không thể dẫn đến cụm chất lượng cao khi cụm hóa thông tin phân loại.
Hơn nữa, hầu hết thuật toán cụm hóa chỉ xem xét độ tương đồng giữa điểm khi cụm hóa, tức là mỗi bước, các điểm được kết hợp thành một cụm đơn. Phương pháp "địa phương hóa" này dễ dẫn đến lỗi. Ví dụ, hai cụm riêng biệt có thể có vài điểm hoặc giá trị ngoại lai gần nhau; do đó, dựa trên độ tương đồng điểm để quyết định cụm hóa có thể khiến hai cụm bị hợp nhất.
ROCK采取 một phương pháp toàn cầu hơn cho cụm hóa bằng cách xem xét lân cận của các cặp điểm đơn lẻ. Hai điểm tương tự cũng có cùng lân cận, do đó hai điểm đó có khả năng thuộc cùng cụm và có thể kết hợp.
Hai điểm pᵢ và pⱼ là láng giềng nếu sim(pᵢ, pⱼ) ≥ θ, với sim là hàm tương đồng và θ là ngưỡng do người dùng chỉ định. Có thể chọn sim là phép đo khoảng cách hoặc phi phép đo được chuẩn hóa để giá trị rơi giữa 0 và 1, giá trị cao hơn biểu thị điểm tương tự hơn.
Số liên kết giữa pᵢ và pⱼ được biểu diễn như số láng giềng chung giữa pᵢ và pⱼ. Nếu số liên kết giữa hai điểm cao, khả năng chúng thuộc cùng cụm càng lớn. Bằng cách xem xét các điểm dữ liệu láng giềng trong mối quan hệ giữa các nhóm điểm đơn lẻ, ROCK mạnh mẽ hơn các phương pháp cụm hóa tiêu chuẩn chỉ tập trung vào độ tương đồng điểm.
Ví dụ dữ liệu bao gồm thuộc tính phân loại là thông tin giỏ hàng thị trường. Dữ liệu này bao gồm cơ sở dữ liệu giao dịch, mỗi giao dịch là nhóm mặt hàng. Giao dịch được coi như dữ liệu với thuộc tính Boolean, mỗi thuộc tính tương ứng một mặt hàng đơn, như bánh mì hoặc phô mai.
Trong dữ liệu giao dịch, thuộc tính tương ứng mặt hàng là đúng nếu giao dịch chứa mặt hàng; ngược lại là sai. Nhiều tập dữ liệu với thuộc tính phân loại có thể xử lý tương tự. Định nghĩa láng giềng và liên kết của ROCK giữa hai "điểm" hoặc giao dịch Tᵢ và Tⱼ được biểu diễn bằng hệ số Jaccard:
sim(Tᵢ, Tⱼ) = |Tᵢ ∩ Tⱼ| / |Tᵢ ∪ Tⱼ|
ROCK trước tạo đồ thị thưa từ ma trận tương đồng dữ liệu cho trước dùng ngưỡng tương đồng và phương pháp láng giềng chung. Nó thực hiện cụm hóa phân cấp凝聚 trên đồ thị thưa. Thước đo goodness có thể tính cụm hóa. Lấy mẫu ngẫu nhiên có thể dùng để mở rộng cho tập dữ liệu lớn.
Độ phức tạp thời gian worst-case của ROCK là O(n² + n·mₘ·mₐ + n²·log n) với mₘ và mₐ là số láng giềng tối đa và trung bình, n là số đối tượng.