Hierarchical Agglomerate Clustering(HAC) - 포켓몬 군집화
Hierarchical Agglomerate Clustering(HAC) 이용해서 서로 다른 특성을 공유하는 Pokemon들을 군집으로 묶어보자.
‘Pokemon.csv’는 온라인에서 손쉽게 구할 수 있다.
이 프로젝트는 군집화(Clustering)의 개념을 숙지하고 있다는 전제로 수행한다.
Code
[Notice] download here
데이터셋 관찰
- Columns: Attack, Sp. Atk, Speed, Defense, Sp. Def, and HP
라이브러리 불러오기
from scipy.cluster.hierarchy import dendrogram, linkage
import csv
import math
import numpy.linalg as LA
import numpy as np
import matplotlib.pyplot as plt
데이터 불러오기
def load_data(filepath):
pokemons = []
with open(filepath, encoding="utf-8") as csvfile:
reader = csv.DictReader(csvfile) # 사전 형태로 csv 데이터를 가져온다
for row in reader:
dic = dict()
dic["#"] = row['#']
dic["Name"] = row['Name']
dic["Type 1"] = row['Type 1']
dic["Type 2"] = row['Type 2']
dic["Total"] = row['Total']
dic["HP"] = row['HP']
dic["Attack"] = row['Attack']
dic["Defense"] = row['Defense']
dic["Sp. Atk"] = row['Sp. Atk']
dic["Sp. Def"] = row['Sp. Def']
dic["Speed"] = row['Speed']
dic["Generation"] = row['Generation']
dic["Legendary"] = row['Legendary']
pokemons.append(dic)
return pokemons # 리스트 형태로 반환
데이터 전처리
def calc_features(row):
return np.array([int(row["Attack"]), int(row["Sp. Atk"]), int(row["Speed"]), int(row["Defense"]), int(row["Sp. Def"]), int(row["HP"])], dtype='int64')
포켓몬 데이터셋에는 범주형 데이터가 존재한다.
따라서, 수치형과 범주형 데이터 type을 지정하고, 손쉬운 연산을 위해 최종 출력을 numpy 배열의 형태로 반환하자.
거리 계산 함수
def get_min_distance(min, tmp):
if min[2] >= tmp[2]:
if min[2] == tmp[2]:
# equal first index ith
if min[0] >= tmp[0]:
if min[0] == tmp[0]:
# equal second index jth
if min[1] >= tmp[1]:
# share same pokemon stat
min = tmp
else:
min = tmp
else:
min = tmp
return min
유클리드 거리를 사용해서 ‘Complete-linkage(완전 연결)’ 기법으로 군집간 거리를 계산한다.
Complete-linkage(완전 연결) 이외에도 Average linkage 등 여러 방법으로 군집간 거리를 계산할 수 있다.
보다 자세한 내용은 여기를 참조하자.
군집 합치기(Merge)
HAC는 군집들을 합쳐가면서 계층적 군집화를 진행한다.
하기 코드는 군집을 합치기 위한 함수이다.
보다 자세한 이해는 각 코드 옆 주석을 참고하자.
def merge_distance(cluster_dict):
length = len(cluster_dict)
min = [np.inf, np.inf, np.inf] # default to inf for replacement
# iterate through cluster list (i.e., [1 2 3] --> (1, 2), (1, 3), (2, 3))
for i in range(length):
if str(type(cluster_dict[i])).find('int') != -1:
continue # already clustered
for j in range(1, length - i):
if str(type(cluster_dict[i + j])).find('int') != -1:
continue # already clusterd
tfst = 'tuple' in str(type(cluster_dict[i]))
tsnd = 'tuple' in str(type(cluster_dict[i+j]))
# check if multiple pokemons in cluster or not
if tfst and tsnd:
# multiple pokemons in both
distances = max_dist = []
cluster_list1 = list(cluster_dict[i])
cluster_list2 = list(cluster_dict[i + j])
# complete-linkage
for c1 in cluster_list1:
for c2 in cluster_list2:
tmp = [i, i + j, LA.norm(c1 - c2)]
distances.append(tmp)
dist = np.array(distances).T[2] # get distances only
# get index of max distance
max_idx = np.argmax(dist) # complete-linkage
max_dist = distances[max_idx]
min = get_min_distance(min, max_dist)
elif tfst and not tsnd:
# multiple pokemons in first cluster
distances = max_dist = []
cluster_list = list(cluster_dict[i])
# complete-linkage
for c in cluster_list:
tmp = [i, i + j, LA.norm(c - cluster_dict[i + j])]
distances.append(tmp)
dist = np.array(distances).T[2] # get distances only
max_idx = np.argmax(dist) # get index of max distance
max_dist = distances[max_idx]
min = get_min_distance(min, max_dist)
elif not tfst and tsnd:
# multiple pokemons in second cluster
distances = max_dist = []
cluster_list = list(cluster_dict[i + j])
# complete-linkage
for c in cluster_list:
tmp = [i, i + j, LA.norm(cluster_dict[i] - c)]
distances.append(tmp)
dist = np.array(distances).T[2] # get distances only
max_idx = np.argmax(dist) # get index of max distance
max_dist = distances[max_idx]
min = get_min_distance(min, max_dist)
else:
# single pokemon in both
tmp = [
i, i + j, LA.norm(cluster_dict[i] - cluster_dict[i + j])]
min = get_min_distance(min, tmp)
return min
상기 코드는 존재하는 군집 리스트 중에서 가장 가까운 거리의 군집 두 개를 찾는다.
여기서 군집 간 거리는 ‘complete-linkage’ 방법에 근거한다.
이러한 맥락에서, 주목할 점은 ‘max_idx = np.argmax(dist)’ 여기이다.
우리는 완전 연결 방법에 기반해서 군집 간 거리를 구하고 서로 가장 가까이 위치한 군집들을 하나의 군집으로 통합한다.
완전 연결은 서로 다른 군집에 포함된 데이터들의 거리가 가장 먼 값을 군집의 거리로 채택한다.
이를 위해, ‘np.argmax’를 사용해서 군집 간 거리를 도출하고, ‘get_min_distance(min, max_dist)’를 통해서 가장 가까운 거리에 위치한 군집을 찾아 해당 군집과 하나로 합쳐진다.
이 외 코드는 천천히 읽어보면 충분히 이해 가능한 부분들이다.
HAC
이제 HAC 계산에 필요한 모든 함수들을 만들었으니, HAC를 구축해보자!
이 단계에서는 가장 가까운 거리의 군집 두 개를 찾아서 하나의 군집으로 통합하는 과정이 진핸된다.
각 코드 옆에 주석을 달았으니 참조하며 읽어보자.
def hac(features):
flen = len(features)
# (n-1) x 4 array
res = np.zeros((flen-1, 4))
# track clusters
cluster_dict = dict()
for i in range(flen):
cluster_dict[i] = features[i]
# compute complete-linkage
count = flen
for r in range(flen - 1):
# get minimum distance indices
indices = merge_distance(cluster_dict)
# clusters to be merged
c1 = cluster_dict[indices[0]]
c2 = cluster_dict[indices[1]]
# check if multiple pokemons in cluster or not
# if tuple, then multiple pokemons, otherwise single pokemon
tfst = str(type(c1)).find('tuple')
tsnd = str(type(c2)).find('tuple')
l1 = l2 = []
if tfst == -1 and tsnd == -1:
# single pokemon
l1 = [c1]
l2 = [c2]
else:
# multiple pokemons
if tfst != -1:
l1 = list(c1)
else:
l1 = [c1]
if tsnd != -1:
l2 = list(c2)
else:
l2 = [c2]
# merge clusters
ncluster = tuple(np.append(l1, l2, axis=0))
fst_idx = indices[0]
snd_idx = indices[1]
# update output
res[r][0] = fst_idx # index of first cluster
res[r][1] = snd_idx # index of seoncd cluster
res[r][2] = indices[2] # distance
res[r][3] = len(ncluster) # num of elements in cluster
# add into cluster list
cluster_dict[count] = ncluster
count += 1
# remove from cluster list
cluster_dict[fst_idx] = -1
cluster_dict[snd_idx] = -1
return res
결과 확인
HAC를 시각화 하는 방법으로 ‘dendrogram‘이라는 함수를 자주 사용한다.
def imshow_hac(Z):
plt.figure()
dn = dendrogram(Z)
plt.show()
for n in range(2, 21):
Z = hac([calc_features(feature) for feature in load_data('Pokemon.csv')][:n])
imshow_hac(Z)
군집 몇 개를 합칠 것인지 그 숫자를 인풋으로 부여한다.
[군집 2개]
[군집 3개]
[군집 4개]
…
댓글남기기