분할 알고리즘의 두 가지 유형
데이터 군집화에 활용되는 분할(partitional) 알고리즘은 크게 K-평균(K-means) 군집화와 최근접 이웃(Nearest Neighbour) 알고리즘, 두 가지로 나눌 수 있습니다.
1. K-평균(K-means) 군집화
K-평균 군집화는 가장 널리 사용되는 대표적인 분할 알고리즘입니다. 데이터셋의 각 데이터를 새롭게 형성된 클러스터 중 하나에만 재할당하며, 각 레코드(데이터 포인트)는 거리 또는 유사도 측정 기준을 바탕으로 가장 가까운 클러스터에 배치됩니다.
K-평균 군집화는 다음과 같은 단계로 진행됩니다.
- K개의 초기 클러스터 중심(centroid)인 c1, c2, c3 … ck를 선택합니다.
- 각 인스턴스 x를 x에 가장 가까운 중심을 가진 클러스터에 할당합니다.
- 각 클러스터에 대해 해당 클러스터에 포함된 요소들을 기준으로 중심을 다시 계산합니다.
- 수렴이 완료될 때까지 위 과정을 반복합니다.
- 객체(데이터 포인트)를 K개의 클러스터로 분리합니다.
- 클러스터 중심(centroid)은 해당 클러스터 내 모든 데이터 포인트의 평균값으로 정의됩니다.
- 거리 함수를 사용하여 각 점을 가장 가까운 중심을 가진 클러스터에 할당합니다.
평균값의 초기 설정은 임의로 지정됩니다. 무작위로 할당할 수도 있고, 첫 k개 입력 항목의 값을 그대로 활용할 수도 있습니다. 수렴 판단 기준은 일반적으로 제곱 오차(squared error)를 사용하지만 반드시 그래야 하는 것은 아닙니다. 예를 들어 데이터가 서로 다른 클러스터에 배정되는 방식으로 종료 조건을 정할 수도 있으며, 고정된 반복 횟수만큼 실행한 후 종료하는 방법도 있습니다. 수렴이 이루어지지 않더라도 알고리즘이 확실히 멈출 수 있도록 최대 반복 횟수를 지정하는 것이 좋습니다.
K-평균 알고리즘
입력
D = {t1, t2, … tn} // 요소 집합
k // 원하는 클러스터 수출력
K // 클러스터 집합
K-평균 알고리즘의 절차는 다음과 같습니다.
- 평균 m1, m2, … mk의 초기값을 할당합니다.
- 반복: 각 항목 ti를 가장 가까운 평균을 가진 클러스터에 할당합니다.
- 각 클러스터의 새로운 평균을 계산합니다.
- 수렴 기준이 충족될 때까지 위 과정을 반복합니다.
2. 최근접 이웃(Nearest Neighbour) 알고리즘
최근접 이웃 알고리즘은 단일 연결(single link) 기법과 유사한 방식의 알고리즘입니다. 이 순차적(serial) 알고리즘에서는 항목들이 현재 존재하는 클러스터 중 가장 가까운 곳으로 반복적으로 통합됩니다. 또한 임계값(threshold) t를 통해 항목을 기존 클러스터에 삽입할지, 아니면 새로운 클러스터를 생성할지를 결정합니다.
최근접 이웃 알고리즘
입력
D = {t1, t2, … tn} // 요소 집합
A // 요소 간 거리를 나타내는 인접 행렬출력
K // 클러스터 집합
최근접 이웃 알고리즘의 의사코드는 다음과 같습니다.
K1 = {t1};
K = {K1};
k = 1;
for i = 2 to n do
dis{ti, tm}이 가장 작은 클러스터 Km의 tm을 찾음;
if dis{ti, tm} ≤ t then
Km = Km ∪ ti
else
k = k + 1;
Kk = {ti}