이번 포스트에서는 K-means 라고 하는 군집화 알고리즘을 텐서플로우에서 테스트해볼 것이다. K-means 알고리즘은 데이터를 유사한 것끼리 자동으로 그룹화할 때 사용하는 유명한 알고리즘이다. 알고리즘의 결과는 중심(centroid)이라고 부르는 K 개의 점으로 각기 다른 군집의 중심점을 나타내고 데이터들은 K 개의 군집 중 하나에만 속할 수 있다. 한 군집 내의 모든 데이터들은 다른 군집의 중심보다 자기 군집의 중심과 가깝다.
군집을 구성할 때 모든 경우에 대해 오차함수를 최소화하려면 NP-hard 문제가 되어 계산하기 곤란하므로 휴리스틱(heuristics) 방법을 사용하여 로컬 최소값에 빠르게 수렴하도록 한다. 널리 사용되는 방법 중 하나는 반복 개선(iterative refinement)기법이다.
반복개선 기법은 크게 3단계로 나눠진다.
1) 0단계(초기) : K개 중심의 초기 집합을 결정
2) 1단계(할당) : 각 데이터를 가장 가까운 군집에 할당
3) 2단계(업데이트) : 각 그룹에 대해 새로운 중심을 계산
예제에서는 초기 중심을 데이터 중에서 임의로 선택할 것이다.
업데이트의 경우 일반적으로 군집 내 데이터의 변화가 없으면 알고리즘이 수렴되었다고 간주한다.
휴리스틱 기법을 이용하므로 결과가 최적이라는 보장은 없다는 것을 유의해야 한다.
----------------------- Clustering source code ---------------------------
# 샘플데이터 생성
import numpy as np
num_points = 2000
vectors_set = []
for i in range(num_points):
if np.random.random() > 0.5:
vectors_set.append([np.random.normal(0.0, 0.9),
np.random.normal(0.0, 0.9)])
else:
vectors_set.append([np.random.normal(3.0, 0.5),
np.random.normal(1.0, 0.5)])
# matplotlib 기반으로하는 seaborn 시각화 패키지 , 데이터 조작 패키지 pandas
# seaborn 은 Anaconda 에서 conda install seaborn 명령으로 설치
# pandas 는 pip install pandas 명령으로 설치
import matplotlib.pyplot as plt
import pandas as pd
import seaborn as sns
df = pd.DataFrame({"x": [v[0] for v in vectors_set],
"y": [v[1] for v in vectors_set]})
sns.lmplot("x", "y", data=df, fit_reg=False, size=6)
plt.show()
# K-means 구현
# 4개의 군집으로 그룹화
import tensorflow as tf
# 모든 데이터를 상수 텐서로 옮김
vectors = tf.constant(vectors_set)
# 초기 단계 : 중심 k(4)개를 입력데이터에서 무작위로 선택
k = 4
centroides = tf.Variable(tf.slice(tf.random_shuffle(vectors),[0,0],[k,-1]))
# vector.get_shape(), centroides.get_shape()
# 위 주석으로 각 텐서의 구조를 확인해볼 수 있음
expanded_vectors = tf.expand_dims(vectors, 0)
expanded_centroides = tf.expand_dims(centroides, 1)
# 할당 단계 : 유클리드 제곱거리 사용
diff = tf.sub(expanded_vectors, expanded_centroides)
sqr = tf.square(diff)
distances = tf.reduce_sum(sqr, 2)
assignments = tf.argmin(distances,0)
# 업데이트 : 새로운 중심 계산
means = tf.concat(0,
[tf.reduce_mean(
tf.gather(vectors,
tf.reshape(
tf.where(tf.equal(assignments, c))
,[1, -1])
)
, reduction_indices=[1]) for c in range(k)])
update_centroides = tf.assign(centroides, means)
init_op = tf.initialize_all_variables()
sess = tf.Session()
sess.run(init_op)
for step in range(100):
_, centroid_values, assignment_values = sess.run([update_centroides, centroides, assignments])
# assignment_values 텐서의 결과를 확인
data = {"x": [], "y": [], "cluster": []}
for i in range(len(assignment_values)):
data["x"].append(vectors_set[i][0])
data["y"].append(vectors_set[i][1])
data["cluster"].append(assignment_values[i])
df = pd.DataFrame(data)
sns.lmplot("x", "y", data=df, fit_reg=False, size=6, hue="cluster", legend=False)
plt.show()
----------------------- Clustering source code ---------------------------
업데이트 단계 (각 군집에 속한 점들의 평균 계산) 코드 해석
means = tf.concat(0,
[tf.reduce_mean(
tf.gather(vectors,
tf.reshape(
tf.where(tf.equal(assignments, c))
,[1, -1])
)
, reduction_indices=[1]) for c in range(k)])
괄호 안쪽부터 차레로 보면
1. equal 함수를 사용하여 assignment 텐서의 각 원소 위치를 True 로 표시하는 불리언 텐서( Dimension(2000) ) 를 만듭니다.
2. where 함수를 사용하여 매개변수 텐서의 True 로 표시된 위치를 가지는 텐서 ( Dimension(2000) * Dimension(1) ) 를 만듭니다.
3. reshape 함수를 사용하여 c 군집에 속한 vectors 텐서의 포인트들의 인덱스로 구성된 텐서 ( Dimension(1) * Dimension(2000) )를 만듭니다.
4. gather 함수를 사용하여 c 군집을 이루는 점들의 좌표를 모은 텐서 ( Dimension(1) * Dimension(2000) * Dimension(2) )를 만듭니다.
5. reduce_mean 함수를 사용하여 c 군집에 속한 모든 점의 평균 값을 가진 텐서 ( Dimension(1) * Dimension(2) )를 만듭니다.
샘플 데이터 ( 2000 sample dots )
군집화 결과 clustering result
