ROCK은 링크를 사용하는 강력한 클러스터링을 나타냅니다. 범주형 속성을 가진 데이터에 대한 링크 개념(두 객체 간의 공통 이웃 수)을 분석하는 계층적 클러스터링 알고리즘입니다. 이러한 거리 데이터는 범주형 정보를 클러스터링할 때 고품질 클러스터로 이어질 수 없음을 나타냅니다.
또한 대부분의 클러스터링 알고리즘은 클러스터링할 때 포인트 간의 유사성만 생성합니다. 즉, 각 단계에서 포인트가 단일 클러스터로 결합됩니다. 이 "현지화된" 방법은 버그가 발생하기 쉽습니다. 예를 들어, 두 개의 개별 클러스터에는 가까운 몇 개의 점이나 이상값이 있을 수 있습니다. 따라서 클러스터링 결정을 생성하기 위해 포인트 간의 유사성에 의존하면 결합할 두 클러스터를 생성할 수 있습니다.
ROCK은 단일 점 쌍의 이웃을 처리하여 클러스터링에 보다 전역적인 방법을 사용합니다. 두 개의 유사한 점에도 동일한 이웃이 있는 경우 두 점은 유사한 클러스터에 속할 가능성이 있으므로 결합될 수 있습니다.
두 개의 점이 있습니다. pi 및 pj , sim(pi인 경우 이웃입니다. , pj ) ≥ θ, 여기서 sim은 유사성 함수이고 θ는 사용자 지정 임계값입니다. 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 입니다. + nmm ma + n 2 로그n ) 여기서 mm 그리고 ma 따라서 이웃의 최대 및 평균 수는 이고 n은 개체 수입니다.