ROCK là viết tắt của Robust Clustering sử dụng liên kết. Nó là một thuật toán phân cụm phân cấp phân tích khái niệm liên kết (số lượng lân cận chung giữa hai đối tượng) cho dữ liệu có thuộc tính phân loại. Nó hiển thị rằng dữ liệu khoảng cách như vậy không thể dẫn đến các cụm chất lượng cao khi phân nhóm thông tin phân loại.
Hơn nữa, hầu hết các thuật toán phân cụm chỉ tạo ra sự giống nhau giữa các điểm khi phân nhóm, tức là ở mỗi bước, các điểm được kết hợp thành một cụm duy nhất. Phương pháp "bản địa hóa" này dễ xảy ra lỗi. Ví dụ, hai cụm riêng biệt có thể có một vài điểm hoặc ngoại lệ ở gần nhau; do đó, dựa vào sự giống nhau giữa các điểm để tạo ra các quyết định phân cụm có thể tạo ra hai cụm được kết hợp.
ROCK sử dụng một phương pháp toàn cục hơn để phân cụm bằng cách xử lý các vùng lân cận của các cặp điểm đơn lẻ. Nếu hai điểm tương tự cũng có cùng vùng lân cận, thì hai điểm có thể thuộc về cụm tương tự và do đó có thể được kết hợp với nhau.
Có hai điểm, p i và p j , là hàng xóm nếu sim (p i , p j ) ≥ θ, trong đó sim là hàm tương tự và θ là ngưỡng do người dùng chỉ định. Nó có thể chọn sim làm thước đo khoảng cách hoặc thậm chí là phi số được chuẩn hóa để các giá trị của nó nằm trong khoảng 0 và 1, với các giá trị cao hơn biểu thị rằng các điểm giống nhau hơn.
Số lượng kết nối giữa p i và p j được biểu thị bằng số lượng láng giềng chung giữa p i và p j . Nếu số lượng liên kết giữa hai điểm cao, thì nhiều khả năng chúng thuộc về cụm tương tự. Bằng cách xử lý các điểm dữ liệu lân cận trong mối quan hệ giữa các nhóm điểm riêng lẻ, ROCK mạnh hơn các phương pháp phân nhóm tiêu chuẩn chỉ nhắm mục tiêu vào điểm giống nhau.
Một ví dụ của dữ liệu bao gồm các thuộc tính phân loại là thông tin về giỏ thị trường. Dữ liệu này bao gồm một cơ sở dữ liệu về các giao dịch, trong đó mỗi giao dịch là một nhóm các mục. Các giao dịch là dữ liệu được xử lý với các thuộc tính Boolean, mỗi thuộc tính tương ứng với một mặt hàng, bao gồm cả bánh mì hoặc pho mát.
Trong dữ liệu cho một giao dịch, thuộc tính tương ứng với một mặt hàng là chính xác nếu giao dịch bao gồm mặt hàng đó; nếu không, nó là sai. Có một số tập dữ liệu với các thuộc tính phân loại có thể được quản lý theo cùng một cách. Các điều khoản về hàng xóm và liên kết của ROCK giống nhau giữa hai "điểm" hoặc giao dịch, T i và T j , được biểu thị bằng hệ số Jaccard là
$$ \ mathrm {sim (T_ {i}, T_ {j}) =\ frac {| T_ {i} \ cap T_ {j} |} {| T_ {i} \ cup T_ {j} |}} $ $
Đầu tiên ROCK tạo ra một đồ thị thưa thớt từ một ma trận tương tự dữ liệu nhất định sử dụng ngưỡng tương tự và cách tiếp cận của những người hàng xóm được chia sẻ. Nó có thể thực hiện phân cụm phân cấp tích tụ trên biểu đồ thưa thớt. Một biện pháp tốt có thể tính toán phân cụm. Lấy mẫu ngẫu nhiên có thể được sử dụng để mở rộng quy mô lên các tập dữ liệu cao.
Độ phức tạp thời gian trong trường hợp xấu nhất của ROCK là O (n 2 + nm m m a + n 2 log n ) nơi m m và m a theo đó, số lượng hàng xóm tối đa và trung bình là và n là số lượng đối tượng.