클러스터링은 모든 sample과, sample이 속한 클러스터의 중심 간의 거리의 합을 최소로 한다.
그러나 찾아낸 클러스터가 항상 의미를 가지는 것은 아니다.
그렇기 때문에 클러스터링 후에 클러스터링이 잘 이루어졌는지 평가를 하여야 한다.
사실 이에 대한 것은 위키에 잘 나와있으니, 이런 글보다 위키를 먼저 읽어보는 것을 권한다.
평가의 방법은 크게 내부 평가방법과 외부 평가방법이 있다.
뭔가 어렵게 말했는데, 그냥 Ground Truth(Golden Standard)의 유무에 따른 차이이다.
클러스터링에 대한 판단기준이 있다면, 그 판단기준과 클러스터링 결과를 비교하면 될 것이고
그게 아니라면 수식에 의존하여 클러스터를 평가해야 할 것이다.
필자의 연구분야에서는 G.T.가 없는 경우가 대부분이다.
그러므로 이 글에서는 G.T.가 없는 상황에서의 클러스터링 평가방법을 다룬다.
클러스터의 내부 평가방법
클러스터링이 잘 되었는지 판단하기 위해서는 당연히 클러스터링의 정의를 끌고와야한다.
클러스터가 잘 묶였다는 것은 한마디로, 클러스터 내부는 잘 응집되어있으며 클러스터 간엔 잘 퍼져있다는 것이다.
소개할 세 평가방법은 모두 이 아이디어에 기반한다.
한편, 이러한 평가방법들은 거리라는 측도만을 사용한다는 점에서 신뢰성이 높진 않다.
(그러나 G.T.가 없는 이상 이런 방법이라도 감지덕지하며 써야한다)
수식은 귀찮은 관계로 모두 Wikipedia에서 긁어왔다.
일반적으로 클러스터링을 설명할 땐 가시성때문에 좌표평면계를 이용한다.
하지만 이 글에서는 각 sample들간의 거리행렬을 이용하였다.
거리행렬(Dissimilarity Matrix)이란 N개의 sample들간의 거리를 계산하여 NxN의 행렬을 만든 것이다.
이 행렬은 대각성분을 기준으로 대칭인 행렬(Redundant Matrix)이기 때문에 보통 압축행렬(Condensed Matrix) 형태로 많이 표현된다.
이 글에서 사용된 코드는 개발편의를 위해 모두 condensed matrix를 인자로 받아 redundant matrix로 변환하여 사용한다.
Energy
우선은 에너지
클러스터링 알고리즘의 Loss를 의미한다
당연하게도 Energy를 통한 비교는 동일한 데이터를 사용했을 때만 가능하다.
이런 까닭에 Energy는 클러스터링 평가 척도로는 사용하지 않는다.
그러나 동일한 데이터를 다룰 때에는 여전히 유효한 척도이다.
Energy는 낮을 수록 좋으며 (엔트로피)
Energy가 낮다는 것은 비교적으로 클러스터 간 거리가 멀고, 클러스터 내부의 거리합이 작다는 것을 의미한다.
필자는 클러스터의 중심을 Mean이 아닌 Median으로 설정했다.
다음 코드는 Python에서 Median을 이용해 Energy를 구하는 코드이다.
정말 별거 없다.
def calculate_energy(cls, condensed_dist_mat: np.array, center_index: np.array, group_index: np.array) -> float:
dist = squareform(condensed_dist_mat)
# Calculate Energy
total_energy = 0
cluster_len = len(center_index)
for cluster_index in range(cluster_len):
# Find Nodes
node_indexes_in_cluster = [x for x in range(len(group_index)) if group_index[x] == cluster_index]
# Calculate Energy
energy = sum([dist[node_index][center_index[cluster_index]] for node_index in node_indexes_in_cluster])
total_energy += energy
return total_energy
Dunn Index
수식에서 볼 수 있듯이,
분자에서는 클러스터간 최소거리를, 분모에서는 클러스터 내부의 최대거리를 사용한다.
이렇게되면 DI가 높을수록 클러스터링이 잘 되었다고 평가할 수 있게 된다.
다만 이 경우 outlier값이 최솟값이나 최댓값으로 선정되었을 때 index 자체가 왜곡된다는 문제가 있다.
def calculate_dunn(cls, condensed_dist_mat: np.array, center_index: np.array, group_index: np.array) -> float:
dist = squareform(condensed_dist_mat)
cluster_len = len(center_index)
min_inter_cluster_dist = math.inf
max_intra_cluster_dist = 0
# Get the minimum value of inter-cluster distance
for cluster_index_i in range(cluster_len):
for cluster_index_j in range(cluster_index_i+1, cluster_len):
if dist[center_index[cluster_index_i]][center_index[cluster_index_j]] < min_inter_cluster_dist:
min_inter_cluster_dist = dist[center_index[cluster_index_i]][center_index[cluster_index_j]]
# Get the maximum value of intra-cluster distance
for cluster_index_i in range(cluster_len):
node_indexes_in_cluster = [x for x in range(len(group_index)) if group_index[x] == cluster_index_i]
coherent_energy = sum([dist[node_index][center_index[cluster_index_i]] for node_index in node_indexes_in_cluster])
if coherent_energy > max_intra_cluster_dist:
max_intra_cluster_dist = coherent_energy
return min_inter_cluster_dist / max_intra_cluster_dist
Davies-Bouldin Index
S는 클러스터 내의 분산정도, M은 클러스터 간의 분리정도를 나타낸다.
단순히 S는 표준편차, M은 클러스터 간 거리로 생각하면 된다.
분자는 클러스터 내부의 분산 정도를, 분모는 클러스터 간의 거리를 사용하니
결국 Dunn Index와 정반대의 결과를 갖게 된다.
다시말해 DBI가 낮을수록 클러스터링이 잘 되었다고 평가할 수 있게 된다.
이 지표의 직관적인 설명은 각 클러스터별로 가장 ‘클러스터 내부의 응집력이 낮고, 클러스터간 거리가 짧은’ 클러스터 짝을 찾아 평균을 낸 것이다.
minimax와 같은 개념이라 생각하면 된다. 각 케이스의 최악(max)들 중 가장 나은 것(min)을 선택한다는 것이다.
그러나 이 경우 개인적으로 의문이 드는 점은, 두 클러스터 간의 분리정도(M)로 거리를 사용할 때 값이 중복된다는 점이다.
거리라는 것은 quasi-metric이 아닌 이상 기본적으로 교환법칙(symmetry)이 성립되는 metric인데 이렇게 되면 절반가량의 연산이 중복된다.
아마 quasi-metric에 대해서도 커버할 수 있도록 이런 식으로 metric을 정한게 아닐까 싶은데, sample 수가 커지면 연산을 어떻게 감당할지 모르겠다.
def calculate_dbi(cls, condensed_dist_mat: np.array, center_index: np.array, group_index: np.array) -> float:
# Initialize
dist_mat = squareform(condensed_dist_mat)
# Calculate DBI
goodput_list = []
for cluster_index_i in range(len(center_index)):
max_goodput = 0
# Calculate Si
group_member_i = [i for i, group in enumerate(group_index) if group == cluster_index_i]
avg_i = sum([dist_mat[center_index[cluster_index_i]][x] for x in group_member_i]) / len(group_member_i)
for cluster_index_j in range(len(center_index)):
if cluster_index_i == cluster_index_j:
continue
# Calculate Sj
group_member_j = [i for i, group in enumerate(group_index) if group == cluster_index_j]
avg_j = sum([dist_mat[center_index[cluster_index_j]][x] for x in group_member_j]) / len(group_member_j)
# Calculate Mij
dist_ij = dist_mat[center_index[cluster_index_i]][center_index[cluster_index_j]]
# Calculate Goodput
goodput = (avg_i + avg_j) / dist_ij
if goodput > max_goodput:
max_goodput = goodput
goodput_list.append(max_goodput)
dbi = sum(goodput_list) / len(center_index)
return dbi
Silhouette Coefficient
python의 scipy 패키지에서 유일하게 제공하는 클러스터 평가 척도이다.
왠진 모르겠다. 가장 구현하기 귀찮아서 그런게 아닐까?
우선 a(i)와 b(i)를 정의한다.
다시 말해 a(i)는 클러스터 i에 대한 응집도를, b(i)는 클러스터 i와 다른 클러스터간의 최소거리를 나타낸다.
재밌는 점은 다른 클러스터링 척도와 달리, a(i)에서 사용하는 평균에 DoF(자유도) 개념을 사용했다는 것과
b(i)에서 사용하는 클러스터간 최소거리를 클러스터 중심간 거리가 아니라, 클러스터 중심과 다른 클러스터에 속한 점들과의 거리로 사용했다는 점이다.
s(i)의 수식을 통해 b(i)>>a(i)일 때 s(i)가 b(i)/b(i)가 되어 1이 됨을 알 수 있다.
다시 말해 클러스터 간 거리가 클 수록 s(i)가 커진다는 것이다.
결과적으로 Silhouette Coefficient는 1에 가까울수록 클러스터링이 잘 된것으로 평가된다.
def calculate_silhouette(cls, condensed_dist_mat: np.array, center_index: np.array, group_index: np.array) -> float:
# Initialize
dist_mat = squareform(condensed_dist_mat)
s = []
for cluster_index in range(len(center_index)):
node_indexes_in_cluster = [x for x in range(len(group_index)) if group_index[x] == cluster_index]
if len(node_indexes_in_cluster) == 1:
s.append(0.)
continue
# Calculate a(i)
ai = 1. / (len(node_indexes_in_cluster) - 1) * sum([dist_mat[center_index[cluster_index]][node_index] for node_index in node_indexes_in_cluster])
# Calculate b(i)
bi = []
for other_cluster_index in range(len(center_index)):
if cluster_index == other_cluster_index:
continue
node_indexes_in_other_cluster = [x for x in range(len(group_index)) if group_index[x] == other_cluster_index]
bi.append(1. / len(node_indexes_in_other_cluster) * sum(dist_mat[center_index[cluster_index]][other_node_index]
for other_node_index in node_indexes_in_other_cluster))
bi = min(bi)
# Calculate s(i)
s.append((bi - ai) / max(ai, bi))
return np.mean(s)