[Hierarchical Clustering] ROCK - using Links

ROCK

RObust Clustering using linKs

 

특징

• Categorical data에 대해서도 clustering 할 수 있다.
• Proximity를 계산하기 위해 link의 개념을 사용한다.
• Distance-based가 아니다.

 

---

Jaccard Coefficient

Categorical data에 주로 사용되는 measure이다.

 

Jaccard coefficient-based similarity function

$Sim(T_1, T_2) = \frac{|T_1 \cap T_2|}{|T_1 \cup T_2|}$

 

예를 들어, $T_1 = \{a, b, c \}, T_2 = \{ c, d, e \}$의 jacard coefficient-based similarity는

$Sum(T_1, T_2) = \frac{ | \{ c \} | }{|\{ a, b, c, d, e \}|} = \frac{1}{5} = 0.2$이다.

 

문제점

reasonable해 보이지만 실제로는 그렇지 않다.

같은 cluster 내의 transaction 과의 similarity보다도 다른 cluster 내 transaction과의 similarity이 더 높은 현상이 발생한다.

 

 

---

Link Measure

Link는 두 object 간 공통된 neightbor의 수이다.

 

같은 cluster 내의 object 간 similarity가 다른 cluster의 object와의 similarity보다 높게 나타난다.

 

예시