[Data Mining] 14. Clustering - Evaluation / Interpretation

Evaluation of Clustering Results

1. External Index

1) Rand Index

external criterial에 따라 clustering을 평가하는 것.

erternal criterial U = {u1, u2, ..., u4}

result of clustering V = {v1, v2, ..., v4}

U의 각 군집에 있는 pair가 V에 있는지 체크한다.

Rand Index = a+d / a + b + c + d

전체 pair 의 수에서 잘 군집시킨 경우(a + d)의 비율

(예제)

ex. U = {(1, 2), (3, 4, 5), (6, 7)} vs.  V = {(1, 2, 6), (3, 5), (4, 7)}

Pairs in U = {(1, 2), (3, 4), (3, 5), (4, 5), (6, 7)}

Pair in V = {(1, 2), (1, 6)), (2, 6), (3, 5), (4, 7)}

a = 2 {(1, 2), (3, 5)} : U에도 있고 V에도 있는 pair

b = 3 {(3, 4), (4, 5), (6, 7)} : U에는 있는데 V에는 없는 pair

c = 3 {(1, 6), (2, 6), (4, 7)} : V에는 있는데 U에는 없는 pair

d = 13 : U에도 없고 V에도 없는 pair

           1, 2, 3, 4, 5, 6, 7로 만들 수 있는 모든 페어 수 = 7 * 6 / 2

2) Adjusted Rand index

Rand index의 d때문에 rand index가 다소 크게 측정되는 경향이 있다. 

기준점이 있었으면 좋겠다. 예를 들어 0.5보다 크면 random 군집보다 성능이 좋다고 말 하고 싶다. 그래서 아래의 수식을 사용하면 아래와 같은 특징을 가진다.

-1 ~ 1의 값을 가진다.

b, c가 0이면 1이 나온다.

ad = bc : RIadj = 0

...

RIadj를 통상 더 많이 쓴다.

예제를 보면 그 특징을 더 실감나게 느낄 수 있다.

U = {(1, 2, 3, 4), (5, 6, 7), (8, 9, 10)}

V = {(1, 2, 5, 8), (3, 6, 9), (4, 7, 10)}

위 경우를 보면 군집을 잘 못 시켰다.

a = 1, b = 11, c = 11, d = 22

RI = 0.511

RIads = -0.25

그런데 두 index를 비교해보면 RI는 0.511이다. 그런데 이 값을 보고 군집이 잘 이뤄졌는지를 파악하기가 쉽지가 않다.

반면 RIadj는 -0.25다. RIadj는 0을 기준으로 한다.  

RIadj = 0 : 50% 확률로 군집에 성공시킬 경우(random)

그렇기 때문에 RIadj가 음수라는 것은 random하게 군집시킨 것 보다 못하다는 결론을 낼 수 있다.

Internal Index

사실 군집을 한 많은 경우는 label이 없다. 즉, 군집결과와 대조할 solution이 없다.

그래서 아래의 특성을 가지고 군집을 평가하고자 한다.

compactness : 군집 내 객체가 얼마나 유사한가

connectedness : 주변 객체를 얼마나 잘 grouping 했는가

Spatial Separation : 다른 특성이 있는 객체가 다른 군집으로 배정됐는가

1) DI index by Dunn(1973)

DI는 최소 separation과 최대 compactness의 비율이다. 클 수록 좋다.

분자(separation) : A군집, B군집 객체들 간 거리 중 최소값 (클 수록 군집이 잘 된 것)

분모(compactness) : 군집 내에서 객체들 간 거리 중 최대값 (작을 수록 군집이 잘 된 것)

2) CH index by Calinski and Harabasz(1974)

DI와 동일하게 separation과 compactness의 비율인데, 수식이 좀 다르다.

separation : 전체 군집들 centroid의 중심을 C라고 했을 때, 각 군집의 centroid(Ci)와 C간의 거리의 합인데, 각 군집의 객체수로 가중 평균 한 것.

compactness : 군집 내에서 군집의 중심과 객체간 거리의 합 (작을 수록 조whgdma)

3) BI index by Brock et al. (2008)

BI는 penalty의 합인데, 작을 수록 좋다.

v는 penalty function이다. xi와 가장 가까운 객체 zi를 찾아보고 만약 xi와 같은 군집이면 0, 군집이 아니면 1/j만큼의 penalty를 가진다. 멀리 떨어진 객체는 penalty를 적게 가져가고, 가까운 객체는 크게 큰 penalty를 가진다.

4) Silhouettes by Kaufman and Rousseeuw (1990)

모든 객체에 대해 s(i)가 계산된다. s(i)가 1에 가까울 수록 그 객체는 군집을 잘 이룬 것

a(i) : 선택된 객체(x)의 군집 내에서 x객체와 다른 객체들과으 거리 평균
b(i) : x객체와 다른 군집에 있는 객체들과의 거리 중 최소값

최종 평가는 모든 silhouette의 평균이다. 

예제)

군집1이 확실히 군집을 잘 이룬것 같아 보인다.

DI는 클수록 좋은데 군집 1을 더 좋다고 판단했다.

BI는 작을수록 좋은데 군집 1을 더 좋다고 판단했다.

ASW는 1에 가까울 수록 좋은데 군집 1을 더 좋다고 판단했다.

객체별로 silhouette값도 구했는데, 군집의 중심에서 떨어진 객체들의 silhouette 값이 낮은 것을 볼 수 있다. (= 확실히 1번 군집이라고 말하긴 애매함을 숫자로 표현한 개념)

Interpretation of cluster result

clustering의 해석 방법는 기본적인 방법은 아래와 같다.

클러스터간의 평균

시각화 도우

factor analysis

군집에 이름을 부가

군집별로 각 변수들의 평균을 구하고 그 값을 군집별로 비교할 수 있다.

그리고 각 클러스터에 이름을 부가하면 그 군집이 의미를 가지기 시작한다.

그 외에도 Visualizeation method도 있다. 다만 대부분의 문제가 고차원을 다루는 만큼 표현이 쉽지가 앖다. 그래서 차원 축소기법을 적용하기도 한다.

가장 기본적인 가시화 방법은 scatter plot으로 모든 독립변수들간 조합으로 그려보는 것이다.

다른 방법으로 Parallel Coordinate Chart에서 3개의 군집이 잘 나눠지는 것을 확인할 수도 있다.

비슷한 개념으로 Error Bar를 그려서 각 클러스터의 error가 얼마나 겹치는지를 확인할 수도 있다.

다만, 변수가 많아지면 위 방법처럼 직관적으로 가시화 하기는 쉽지않다. 그래서 아래와 같이 선형/비선형 차원변형을 통해서 가시화 하기도 한다. 선형 차원변형 몇개에 대해서만 알아보자.

앞서 변수선택법에서 배웠던 PCA(Principal Component Analysis)를 통해 주 성분을 구해서 다차원 문제를 작은 차원으로 변형할 수 있다. 

그 외에도 t-SNE(최근에 각광 받고 있음), ... 등이 있는데 이런게 있다 정도 참고만 하자.