패턴 인식 (10) 군집화
 패턴인식, 오일석 지음/교보문고 |
10. 군집화
적절한 방식으로 특징 벡터 간의 거리를 정의할 수 있다면 유사한 샘플들을 모아 하나의 그룹으로 간주할 수 잇다. 이러한 그룹을 군집(cluster)이라 하고 이러한 작업을 군집화(clustering)라 한다. 군집화를 구현하기 위해서는 적절한 거리 척도가 있어야 하며, 유사한 샘플들을 같은 군집으로 만들어 주는 적절한 알고리즘이 있어야 한다.
군집화도 일종의 학습으로 볼 수 있다. 하지만 군집화와 학습 사이에 두드러진 차이가 있는데, 분류 학습에서는 샘플의 부류 정보가 주어졌지만 군집화에서는 부류 정보가 주어지는 것이 아니라 그것을 찾아내야 한다. 심지어 부류의 개수가 몇 개인지 정확히 모르는 경우도 많다. 따라서 군집화가 부류 발견(class discovery)을 한다고 말하기도 한다.
샘플의 부류 정보가 주어진 상황에서의 학습을 지도 학습(supurvised learning)이라 하고 그렇지 않은 학습을 비지도 학습(unsupervised learning)이라 부른다. 비지도 학습을 군집화로 축소하여 바라보거나 또는 종종 같은 작업으로 간주하기도 한다.
부류 정보가 주어지는 분류 문제에서는 학습된 분류기의 성능이 명확하다. 부류 정보가 있기 때문에 인식 결과가 맞는지에 대한 측정이 확실하고 그것의 통계가 인식률이 된다. 하지만 군집화에서는 그렇지 못하다. 이에 대한 평가는 주관적일 수밖에 없다. 시스템의 입장에서는 사용하는 거리 척도와 알고리즘에 따라 다른 결과를 생성할 수밖에 없다. 따라서 응용에 대한 충분한 지식과 이해를 바탕으로 결과를 평가해야 한다.
10.0 정의
군집화는 그 응용 범위가 매우 넓고 개념과 방법론이 매우 다양하다. 또한 요구 조건에 따라 주관이 개입되는 것이 불가피 하다. 일반적으로 받아들여지는 정의는 아래와 같다.
군집화란?
샘플 집합 $ X = \{ x_1, \dots, x_N \} $ 이 주어졋다고 하자. $x_i$는 i번째 샘플로 d차원 특징 벡터 $x_i = (x_{i1}, \dots, x_{id}) $로 표현한다. 이 입력에 대해 아래 조건을 만족하는 k개의 군집으로 구성되는 군집 해(clustering colution) $ C = \{ c_1, \dots, c_k \} $를 찾아라. 보통 군집의 개수 k는 N에 비해 매우 작다. 상황에 따라 k가 주어지는 경우도 있다.
- 모든 군집이 하나 이상의 샘플을 갖도록 한다.
- 모든 샘플이 하나의 군집에 포함되도록 한다.
이렇게 정의된 군집화에서는 샘플이 단 하나의 군집에 속하게 되는데 이러한 군집화를 경성 군집화(hard clustering)이라 부를 수도 있다. 어떤 응용에서는 샘플이 두 군집 중간에 위치하는 상황을 다루기 위하여 연성 군집화(soft clustering) 또는 퍼지 군집화를 사용하기도 한다. 이때는 샘플마다 소속 정도를 나타내는 변수를 사용한다. 소속 변수 $m_{ij}$는 $x_i$가 $c_j$에 속할 정도를 나타낸다. 각 소속 변수는 1보다 클 수 없으며 한 샘플의 소속 변수를 모두 더하면 1이 된다. 여기서는 경성 군집화만 다루기로 한다.
N개의 샘플이 주어진 상황에서 서로 다른 군집 해의 수를 세기 위해서는 Stirling 수를 활용하면 된다. Stirling 수는 N개의 객체를 k개의 그룹으로 나누는 경우의 수이다. Stirling 수는 다음과 같이 순환식(recurrence relation)으로 정의한다.
$$S(N, k) = S(N-1, k-1) + k S(N-1, k) \\
S(N, 1) = 1 \\
S(N, N) = 1$$
10.2 거리와 유사도
군집화가 추구하는 본질적인 목표는 같은 군집 내의 샘플은 서로 가깝고 다른 군집에 속한 샘플 사이의 거리는 멀게하는 것이다. 따라서 군집화에서 거리 개념은 매우 중요하고 어떤 계산 방법을 사용하느냐에 따라 군집화 결과는 달라진다. 거리(distance)와 유사도(similarity)는 반대 개념이고 하나를 알면 다른 것은 쉽게 계산할 수 있다.
10.2.1 특징 값의 종류
특징은 그들이 갖는 값의 특성에 따라 다음처럼 구분할 수 있다. 먼저 양적(quantitative) 특징인지 질적(qualitative) 특징인지를 구분한다. 질적 특징은 순서(ordinal) 값과 순서를 갖지 않는 명칭(nominal) 값으로 구분할 수 있다. 이들은 거리 개념의 유무에 따라 구분할 수도 있는데, 수량 값과 순서 값은 거리 개념을 가지지만 명칭 값은 거리 개념이 없다. 따라서 명칭 값을 갖는 특징은 적절한 방법을 사용하여 다른 표현으로 변환한 후에 거리 계산에 참여해야 한다.
실제 응용에서는 특징 벡터가 위의 특성이 혼합된 형태가 대부분이다. 따라서 적절한 특징 전처리ㅏ 필요할 수 있다. 거리 개념이 없는 명칭 값 특지응ㄴ 다른 표현으로 바꾸어야 한다. 또한 특징의 값 범위가 다른 것에 비해 아주 크면 거리 계산에서 그것이 주도하게 되므로 크기 정규화를 해 주어야 한다. 또한 군집화에서도 특징 선택이 필요하다.
10.2.2 거리와 유사도 측정
가장 널리 쓰이는 거리 척도는 Minkowski 거리이다.
$$d_{ij} = ( \sum_{k=1}^d | x_{ik} - x_{jk} |^p)^{1/p}$$
이 식에서 p를 변화시켜 여러가지 척도를 만들 수 있다. 가장 널리 사용되는 것은 p=2의 유클리이던 거러이다. p=1로 하면 도시 블록 거리(city block distance), 또는 맨하탄 거리(Manhattan distance)가 된다.
어떤 상황에서는 두 점간의 거리 계산에서 그들이 속한 분포를 고려하는 것이 합리적일 수 있다. 이때는 분산이 큰 특징에게 작은 가중치를 곱해 주는 것이 적절하다. 이런 원리에 따라 정의된 거리를 마할라노비스 거리라 한다.
모든 특징이 0 또는 1을 갖는 이진 특징 벡터라면 해밍 거리(hamming distance)가 있다. 두 이진 벡터의 해밍 거리는 서로 다른 비트의 개수로 정의된다.
거리 $d_{ij}$를 유사도 $s_{ij}$로 변환할 수 있다. 거리가 가질 수 있는 최대값이 $d_{max}$라면 $ s_{ij} = d_{max} - d_{ij} $로 계산하면 된다.
다음과 같은 방법으로 유사도를 계산할 수도 있다.
$$s_{ij} = \cos \theta \frac{x_i^T x_j}{||x_i||||x_j||}$$
이 유사도는 0이 아닌 두 벡터간에 정의되는데 코사인 유사도라 부른다.
이진 특징 벡터의 유사도는 다음의 두 방법을 사용할 수도 있다.
$$s_{ij} = \frac{n_{00} + n_{11}}{n_{00} + n_{11} + n_{01} + n_{10}}$$
$$s_{ij} = \frac{n_{11}}{n_{11} + n_{01} + n_{10}}$$
여기서 $n_{01}$는 $x_i$는 0이고 $x_j$는 1인 특징의 개수이다. 첫번째 방법은 0과 1을 동등하게 취급하고 두번째는 1을 더 중요하게 생각한다.
반대의 방법으로 $d_{ij} = s_{max} - s_{ij} $을 이용하여 유사도를 거리로 변환할 수도 있다.
지금까지 언급한 여러 거리와 유사도는 어느 것이 다른 것보다 우월하다는 말을 할 수가 없다. 상황에 따라 어느 것은 적절하고 다른 것은 부적절할 수 있다.
10.2.3 점 집합을 위한 거리
군집화 과정에서는 점과 점 집합 또는 두 개의 점 집합 사이의 거리가 필요한 경우도 있다. 여기에서 점 집합은 군집을 뜻한다. 점 $x_i$와 군집 $c_j$간의 거리를 $D(x_i, c_j)$ 두 개의 군집 $c_i $와 $c_j$간의 거리를 $D(c_i, c_j)$로 표기하자.
점과 군집 사이의 거리
세 가지 거리 계산 방법을 사용할 수 있다. 편의상 $c_j$에 속한 샘플을 $y_k$로 표기하고 두 점 $x_i $와 $y_k$ 사이의 거리는 $d_{ik}$로 표기한다. $|c_j|$는 $c_j$에 속한 샘플의 개수를 뜻한다.
$$D_{max}(x_i, c_j) = \max_{y_k \in c_j} d_{ik}$$
$$D_{min}(x_i, c_j) = \min_{y_k \in c_j} d_{ik}$$
$$D_{ave}(x_i, c_j) = \frac{1}{|c_j|} \sum_{y_k \in c_j} d_{ik}$$
$D_{max}$는 가장 먼 것을, $D_{min}$은 가장 가까운 점을 취하는 것이다. 따라서 이 둘은 외톨이(outlier)에 민감할 수밖에 없다. $D_{ave}$는 평균을 취하므로 이런 사왛ㅇ에 덜 민감한 장점이 있다.
위의 방법은 거리 계산에 모든 샘플이 참여한다. 이와 달리 $c_j$의 대표를 뽑아 놓고 그것과 $x_i$ 사이의 거리를 이용하는 방법도 있다. $c_j$의 대표는 점일 수도 있고 선이나 면일 수도 있다. 여기서는 점인 경우만 다룬다. $y_{mean}$은 $c_j$를 대표하는 점이고 $d_{i, mean}$은 두 점 $x_i$와 $y_{mean}$ 사이의 거리를 말한다.
$$D_{mean} (x_i, c_j) = d_{i, mean}$$
$$y_{mean} = \frac{1}{|c_j|} \sum_{y_k \in c_j} y_k$$
여기서는 모든 점의 평균을 구하여 그것을 대표 점으로 삼았다. 또 다른 방법은 $c_j$에 속하는 샘플 중 하나를 대표로 선택하는 것이다. 이렇게 선택된 대표를 $y_{rep}$로 표기하자. 이 대표 점은 다른 샘플들과 가급적 가까워야 하므로 median 값을 사용하도록 하자.
두 군집 사이의 거리
두 개 군집 간의 거리 $D(c_i, c_j)$도 비슷한 방식으로 구할 수 잇다. 여기서는 다섯 가지 계산 방법을 알아보자.
$$D_{max} (c_i, c_j ) = \max_{x_k \in c_i, y_l \in c_j} d_{kl}$$
$$D_{min} (c_i, c_j ) = \min_{x_k \in c_i, y_l \in c_j} d_{kl}$$
$$D_{ave} (c_i, c_j ) = \frac{1}{|c_i| |c_j|} \sum_{x_k \in c_i} \sum_{y_l \in c_j} d_{kl}$$
$$D_{mean}(c_i, c_j) = d_{mean1, mean2}$$
$$D_{rep}(c_i, c_j) = d_{rep1, rep2}$$
마찬가지로 두 군집 사이의 거리를 유사도로 변환하여 사용할 수 있다.
10.2.4 동적 거리
어떤 상황에서는 샘플마다 특징 벡터의 차원이 다를 수 있다. 이런 상황에서는 동적 거리를 정의하고 그것을 사용해야 한다. 동적 거리는 교정 거리 계산 방법을 사용하여, Levenshtein 거리 또는 Damerau-Levenshtein 거리 중에서 선택하면 된다.
10.3 군집화 알고리즘의 분류
군집이 계층을 형성하는지 아닌지, 그래프 자료구조를 사용하는지, 비용 함수를 지정하고 그것을 최적화 하는지, 신경망 학습 알고리즘을 사용하는지, 효율적 공간 탐색 연산을 사용하느냐 등과 같이 알고리즘이 사용하는 기본적인 연산에 따라 구분할 수 있다. 또한 시간 복잡도에 따라 데이터의 규모에 따라서도 구분 지을 수도 있다.
패턴 인식 분야에서 군집화처럼 주관이 많이 개입하는 문제도 드물다. 군집화는 정답이 정해져 있지 않기 때문이다. 다양한 상황 모두를 만족시키는 알고리즘은 불가능하다. 따라서 자신이 사용하는 알고리즘의 성질에 대한 이해가 매우 중요하다.
Jain의 분류 체계를 확장하여 4가지로 분류하여보자.
- 계층 군집화 알고리즘 : 군집의 계층을 형성하다. 그 결과를 덴드로그램이라는 트리로 표현할 수 있다. 계층 형성이라는 독특한 특성으로 인해 보통 하나의 알고리즘 군으로 구분된다.
- 분할 군집화 알고리즘 : 계층을 형성하지 않고 하나의 군집 결과만을 출력한다. 주로 샘플을 군집에 배정하는 연산을 사용한다.
- 신경망 알고리즘 : SOM이나 ART같은 알고리즘은 아키텍처와 학습 알고리즘을 갖는다는 독특한 성질에 하나의 알고리즘 군으로 구분된다.
- 통계적 탐색 알고리즘 ; 유전 알고리즘과 시뮬레이티드 어닐링이 있는데 난수를 발생시켜 확률적인 의사 결정을 한다는 독특한 성질을 지니고 있다. 이들은 최적 점을 피하고 공간을 효율적으로 탐색하여 전역 최적 점에 매우 근접한 해를 찾는 것을 목표로 한다.
10.4 계층 군집화
10.4.1 응집 계층 알고리즘
군집 해 $ C_2 $의 모든 군집 $ c_{2i} $가 다른 군집 해 $C_1$에 속한 군집의 부분 집합일 때 $C_2 $는 $C_1$에 포함된다고 말한다. 게층 군집화 알고리즘은 이러한 포함 관계를 군집화 결과로 출력한다. 계층 군집화(hierarchical clustering) 알고리즘에는 작은 군집들에서 출발하여 이를 모아 나가는 응집(agglomerative) 방식과 큰 군집에서 출발하여 이들을 나누어 나가는 분열(divisive) 방식이 잇다.
- $ C_0 = \{ c_1 = \{x_1 \}, \dots \} $ // 각 샘플이 하나의 군집
- for(t=1 to N-1)
- $C_{t-1}$의 모든 군집 쌍$(c_i, c_j)$을 조사하여 아래를 만족하는 쌍 $(c_p, c_q)$를 찾아라.
$ D(c_p, c_q) = \min_{c_i, c_j \in C_{i-1}} D(c_i, c_j) $ - $c_r = c_p \cup c_q $ // 두 군집을 하나로 합쳐라
- $C_t = (C_{t-1} - c_p - c_q) \cup c_r $ // 두 군집을 제거하고 새로운 군집을 추가하라.
- $C_{t-1}$의 모든 군집 쌍$(c_i, c_j)$을 조사하여 아래를 만족하는 쌍 $(c_p, c_q)$를 찾아라.
위 알고리즘은 응집 계층 군집화 알고리즘이다. 출력은 군집화 결과를 트리 형태로 표현한 덴드로그램(dendrogram)이다.
$D_{min} $대신 $D_{max}$ 또는 $D_{ave}$를 사용하면 결과 또한 달라진다. 따라서 min을 사용하면 단일 연결(single linkage), max를 사용하면 완전 연결(complete linkage) 알고리즘, ave를 사용하면 평균 연결(average linkage) 알고리즘이라 부른다.
거리 대신 유사도를 사용할 수도 있다. 거리 D 대신 유사도 S로 바꾸고 min 대신 max를 사용하면 된다. 거리를 사용할 때는 짧은 쌍을 찾았지만 유사도에서는 큰 쌍을 찾아야 한다.
세가지 고려해야 할 부분이 잇다. 첫번째는 적절한 군집의 개수를 어떻게 알아낼 것인가로 사용자가 미리 정해주는 방식과 알고리즘의 자동으로 찾는 방식이 있다. 두번째는 외톨이(outlier) 또는 잡음에 대한 민감성과 관련된다. 한번 어느 군집에 외톨이 또는 잡음이 포함되면 계속적으로 거리 계산을 주도해 버릴 수 있다. 세번째는 시간 복잡도이다.
10.4.2 분열 계층 알고리즘
- $ C_0 = \{ c_1 \dots \} $ // 모든 샘플이 하나의 군집이 되도록 초기화
- for (t=1 to N-1)
- for ( $C_{t-1}$의 모든 군집 $c_i$에 대하여)
- $c_i$의 모든 이진 분할 중에 거리가 가장 먼것을 찾아라.
- 앞에서 찾은 t개의 이진 분할을 비교하여 가장 먼 거리를 가진 군집 $c_q$를 찾고 그것의 이진 분할을 $c_q^1, c_q^2$라 한다.
- $C_t = (C_{t-1} - c_q) \cap \{ c_q^1, c_q^2 \} $ // $c_q$를 제거하고 두 개의 새로운 군집을 추가
- for ( $C_{t-1}$의 모든 군집 $c_i$에 대하여)
하나의 큰 군집에서 출발하여 매 루프마다 한 개의 군집을 선정하여 이를 두 개로 나눈다. 따라서 루프를 돌 때마다 군집의 개수가 하나씩 많아 지고 마지막에는 하나의 샘플이 하나의 군집을 형성한다. 이러한 과정을 하향(top-down) 방법이라 할 수 있다. 반면에 10.4.1의 응집 계층 알고리즘은 상향(bottom-up)으로 볼 수 있다.
10.5 분할 군집화
분할 군집화(partitional clustering) 방법은 계층을 만ㄴ들지 않고 하나의 군집 해를 만들어 준다. 이 접근 방법에는 사용하는 방법에 따라 아주 다양한 알고리즘이 잇다. 예를들면 샘플을 순차적으로 군집에 할당하는 순차 알고리즘, 초기 분할을 가지고 출발하여 계속 개선해 나가는 k-means 알고리즘, 그래프 표현을 만들고 그것을 분할해 나가는 MST 알고리즘, 가우시언 분포를 추정하고 그것에서 군집을 찾는 GMM 알고리즘 등이 있다. 대부분은 미리 군집의 개수 k를 알려주어야 한다. 일반적으로 10.4절의 계층 군집화보다 빠르기 때문에 대용량 데이터에 이용되고 있다.
10.5.1 순차 알고리즘
처음에는 한개의 군집에서 출발하여 샘플을 차례로 살펴보다가 가장 가까운 군집까지의 거리가 임계값보다 작으면 그 군집에 속하는 것으로 간주하고 그 군집에 넣는다. 그렇지 않으면 샘플이 새로운 군집을 형성한다.
이 알고리즘은 군집의 개수 k를 자동으로 찾아준다. 하지만 그 대신 임계 값을 지정해 주어야 하는데 이 역시 추정하기가 어렵다. 또한 샘플을 어떤 순서로 처리하느냐에 따라 결과가 달라진다. 이러한 성질을 순서에 민감하다(order sensitive) 또는 순서 의존적(order dependent)라 말한다. 한가지 방법은 군집 개수의 상한을 매개변수로 지정해주는 것이다.
10.5.2 k-means 알고리즘
가장 인기가 높고 널리 쓰이는 군집화 알고리즘이다. 이 알고리즘은 군집의 개수 k를 지정해 주어야 한다. 우선 군집의 중심을 초기화한다. 이 초기화 작업은 최종적으로 얻을 군집 해에 크게 영향을 미친다. 이제 샘플 각각에 대해 k개의 군집 중심 중에 가장 가까운 것을 찾아 그것에 배정한다. 그 결과 모든 샘플의 각자 하나의 군집에 속하게 된다. 그 후, 각 군집의 중심을 그것에 속한 샘플의 평균으로 대치한다. 이러한 과정을 반복하는데 군집 배정의 결과가 이전 루프에서와 같다면 그때 멈춘다.
군집을 초기화하는 방법 중 하나는, 샘플 중 k개를 선정하여 초기화하는 방법이 있다. 임의로 선정하거나 처음 k개를 선정하기도 한다. 또는 다른 알고리즘을 수행하여 개략적인 군집 해를 만들고 각 군집에서 대표를 하나씩 뽑아 해결할 수도 있다.
종료 조건은 군집의 배정에 변화가 없을 때 종료하면 된다.
다음 식은 샘플들이 군집 중심에서 얼마나 밀집해 있는 지를 측정해준다.
$$J(Z, U) = \sum_{i=1}^N \sum_{j=1}^k u_{ji} ||x_i - z_j||^2$$
Z는 k개의 군집 중심을 나타내고, U는 $u_{ji}$로 구성되는 행렬인데, $x_i$가 $z_j$에 배정되어있으면 1, 그렇지 않으면 0의 요소를 갖는다. 위 식은 제곱 오류(squared error)로 볼 수 있다.
결국 k-means 알고리즘은 이 식을 비용함수로 하여 이것을 줄여나가는 내리막 경사법(gradient descent method)의 일종이다. 따라서 항상 지역 최소 점을 찾는다는 것이 증명되어잇다. 하지만 내리막 경사법의 한계인 초기 점에 민감한 특성을 그대로 이어받게 되고 지역 최적 점에 빠지는 한계를 안고 있다.
시간을 더 쓸 수 있다면 다중 시작(multi-start) 알고리즘으로 전역 최적 해에 보다 가까운 군집 해를 구할 수 있다. 이 알고리즘의 아이디어는 서로 다른 초기 군집 중심을 가지고 k-means를 여러 번 수행하고, 그렇게 얻은 군집 해 중에 품질이 가장 좋은 것을 취한다는 것이다.
k-means의 두드러진 장점 중 하나는 빠르다는 것이다. 하지만 외톨이에 민감하다. 외톨이에 민감한 문제를 해결하기 위해 나온 변형이 k-medoids이다. 이 방법은 샘플의 평균을 구하는 것이 아니라 그 샘플들 중 하나를 대표로 삼고 그것을 군집 중심으로 한다. 대표 샘플은 다른 샘플까지의 거리의 합이 최소가 되는 것을 찾으면 된다.
특징 벡터가 명칭 값이나 순서 값을 가지고 있어 평균하여 얻은 실수가 의미를 가지지 못하는 경우가 있다. 이런 샘플들은 k-means를 사용할 수 없다.
10.5.3 모델 기반 알고리즘
모델 기반(model-based) 군집화 방법은 통계적인 모델을 추정하고 그 결과를 이용하여 군집 해를 구한다는 면에서 이전의 것들과 차별성을 갖는다.
일반적으로는 어떠한 확률 모델이라도 사용할 수 있지만 가장 다루기 쉬운 가우시언 모델을 주로 사용한다. 가우시언 모델 방법에서는 샘플 집합 X가 k개의 가우시안 $G_j = N(u_j, \Sigma_j), 1 \leq j \leq k $ 의 혼합으로부터 발생하였다고 가정한다. 만약 k개의 가우시언을 모두 알고 있다면 샘플 $x_i$는 베이시언 규칙으로 군집 $c_q$에 배정하면 된다.
문제는 가우시언을 모른다는 점이다. 따라서 샘플로부터 $G_j$를 추정해 내야 한다. 여기에는 앞에서 배운 EM알고리즘을 사용할 수 잇다.
10.6 신경망
앞에서 다룬 퍼셉트론과 다층 퍼셉트론은 군집화가 아니라 분류 문제를 푸는 도구엿다. 다시 말해 비지도 학습이 아니라 지도 학습을 사용한다. 여기에서는 비지도 학습에 해당하는 군집화를 풀어야 하는데 이런 목적으로 개발된 신경망 중 대표적인 것으로 SOM과 ART가 있다.
신경망은 학습과 군집 과정이 분리되어 있다. 따라서 신경망은 다른 군집화 알고리즘이 가지지 못하는 독특한 장점을 가진다. 다른 알고리즘은 군집화를 마친 후 새로운 샘플이 들어오면 이것을 기존 샘플에 합쳐 군집화를 처음부터 다시 해야 한다. 하지만 신경망은 학습된 신경망으로 그 샘플만 군집 배정을 해주면 된다. 특히 ART는 안정성이 뛰어나 새로운 패턴이 계속 발생하는 온라인 상황에 적합하다.
10.6.1 자기 조직화 맵
군집화는 샘플의 상호 비교를 통하여 스스로 군집을 조직해 내야 하는 것이다. 이런 목적으로 개발된 신경망이 자기 조직화 맵(self-organizing map, SOM)이다. 이것은 Kohonen이 개발했기 때문에 Kohonen 네트워크라고도 부른다.
SOM은 기본적으로 경쟁 학습(competitive learning)을 사용한다. 하나의 샘플이 입력되면 여러 개의 대표 벡터가 경쟁하는데 샘플에 가장 가까운 대표 벡터가 승자가 되어 그 샘플을 취한다. 승자는 그 샘플에 적응하는 방향으로 벡터 값을 조금 변화시킨다. 따라서 이 학습은 승자 독식(winner-take-all) 전략을 사용한다고 표현하기도 한다.
SOM은 두개의 층으로 구성된다. 입력층은 d차원 특징 벡터를 입력으로 받기 위해 d개의 노드를 갖는다. 경쟁 층은 m개의 노드로 구성되는데 이들 노드가 군집을 형성하기 위해 서로 경쟁한다. 최종적으로 군집을 형성한 노드도 있고 그렇지 못한 노드도 생긴다. 따라서 m은 군집을 형성할 수 있는 최대 개수고, 그 중 군집을 형성한 노드만 모아 최종 군집 해로 삼으면 된다. 모든 입력 노드와 경쟁 노드는 에지로 연결되어있다. 입력 노드 i와 경쟁 노드 j를 연결하는 에지는 가중치를 갖는데 이것을 $w_{ij}$로 표현한다.
경쟁 층의 노드는 이웃을 갖는데 이웃의 반경을 뜻하는 매개변수로 r을 갖는다.
SOM에서는 노드 $y_j$로 들어오는 d개의 가중치의 역할이 매우 중요하다. 이들 가중치를 벡터로 보고 $w_j = (w_{1j}, \dots, w_{dj})^T$로 표시하자. 샘플 x가 입력되면 m개의 가중치 벡터가 서로 경쟁하는데 그둘 중 x에 가장 가까운 벡터가 증자가 된다. 이때 승자를 결정하기 위해서 가중치 벡터와 샘플 벡터 간의 거리를 이용한다. 경쟁의 결과 q번째 벡터가 승자라 하면 $w_q$는 x에 적응하기 위해 자신의 값을 변화시킨다. 이 변화가 학습에 해당한다. 거리 계산은 보통 유클리디언 거리를 사용한다. 또는 $w_j$와 x를 크기가 1인 정규 벡터로 만들고 그들의 내적을 구해 그것을 유사도로 사용할 수도 있다.
학습 규칙은 간단하다.
$$w_{new} = w_{old} + \rho (x - w_{old})$$
여기서 $\rho$는 학습률이다. 이 규칙은 이전 가중치를 x에 가깝게 만드는 역할을 한다. 결국 가중치 벡터는 그 노드에 배정된 샘플을 대표하는 역할을 하게 된다.
MLP와 마찬가지로 전체 샘플에 대하여 여러 세대(epoch)에 걸쳐 학습을 한 뒤, 학습된 SOM으로 분류를 하면 된다.
10.6.2 ART
SOM이 사용하는 경쟁 학습은 안정성(stability)이 떨어진다. 샘플이 특정 군집에 한번 배정되면 이후 세대에도 그 군집에 계속 머물 가능성이 있다. 학습이 계속됨에 따라 가중치 벡터가 x로부터 다시 멀어질 수 있는 것이다. 그렇다고 배정된 샘플을 기억하려고 학습률을 소극적으로 하면 새로운 샘플을 받아들일 수 없다. 이러한 정도를 유연성(plasticity)라고 한다. SOM은 유언성은 좋은데 안정성이 낮다고 할 수 있다. 경쟁 학습에서 안정성과 유연성은 길항 관계를 갖는데 이를 안정성과 유연성의 딜레마(stability-plasticity dilemma)라 부른다.
적응 공명 이론(adaptive resonance theory, ART) 신경망은 그 두가지를 조화롭게 추구하려는 동기에서 개발되었다. ART는 이진 입력을 다루는 ART1과 연속 값을 다룰 수 있는 ART2가 있으며 그외에도 여러 변종이 있다. 여기서는 ART1만 살펴본다.
ART1의 아키텍처가 SOM과 다른 점 중 하나는 상향 가중치 b와 하향 가중치 t의 두 종류가 있다는 점이다. 가중치 b는 SOM의 w와 마찬가지로 승자를 결정하는데 사용된다. SOM에서는 승자가 결정되면 w를 갱신하여 곧바로 샘플에 적용하지만 ART에서는 가중치 t를 이용하여 검증 과정을 거친다. 즉 공명이 일어나야만 승자 노드를 승자로 취급하고 그렇지 않으면 그 노드를 불능화(inhibit)시킨다.
입력 노드 $z_i$와 경쟁 노드 $y_i$ 사이에는 상향(bottom-up) 에지 $b_{ij}$와 하향(top-down) 에지 $t_{ji}$가 존재한다. 따라서 노드 $y_j$의 입장에서 보면 다음과 같은 두 종류의 가중치 벡터가 있다.
- 상향 가중치 벡터 $b_j = (b_{1j}, \dots, b_{dj})^T$
- 하향 가중치 벡터 $t_j = (t_{j1}, \dots, t_{jd})^T$
입력 샘플은 맨 아래에서 네트워크로 입력된다. 입력 층에는 다른 벡터 $z = (z_1, \dots, z_d)^T$가 있는데 ART1에서는 원래 입력값 x와 그것이 변형된 값 z를 모두 사용한다.
SOM과 마찬가지로 샘플을 네트워크에 입력하고, 유사도를 계산하여 승자 노드를 찾는다. 다음 하향 가중치 벡터를 곱하여 z를 갱신한다. 다음 $\frac{one(z)}{one(x)}$ ($one()$은 벡터에서 1을 갖는 수)를 계산하여 경계 변수(vigilance paramter) $\tau$를 넘지 못하면 승자 노드 q를 불능화 시킨다. $\tau$를 넘으면 승자 노드로 간주하고 상향 가중치와 하향 가중치를 갱신한다. 승자노드가 하나도 없다면 입력 벡터를 적절히 처리해준다.
10.7 통계적 탐색
앞에서 살펴본 통계적 탐색 알고리즘(시뮬레이티드 어닐링과 유전 알고리즘)은 특징 선택 뿐 아니라 최적화 문제 등 어떤 것에 대해서도 적용이 가능하다. 군집도 최적화 문제이므로 이들을 사용할 수 있다. 통계적 탐색은 알고리즘 수행 중에 난수를 사용하는데, 난수가 의사 결정에 참여함으로써 해에 임의성을 부여한다. 따라서 임의성을 적절히 제어해야한다.
통계적 탐색 알고리즘을 적용하기 위해서는 비용 함수를 어떻게 정의할 것인지와 해를 어떻게 표현할 것인지의 두 가지를 고려해야 한다. 비용 함수는 k-means에서 사용한 제곱 오류를 사용하면 된다. 해는 다음의 두 방법을 사용할 수 있다.
- $Z=(z_1, \dots, z_k) $
- $Z=(\#,z_1,z_2,\#,\#,z_3,\#,\#) $
두번째 방법은 군집 개수를 가변적으로 할 수 있는 표현이다.
10.7.1 시뮬레이티드 어닐링
난수를 발생시키거나 샘플을 임의로 선택하여 초기 군집 해를 생성한다. 다음 현재 해를 변형시키면서 새로운 해를 생성한다. 이러한 연산을 교란(perturbation)이라 부른다. 변형시키는 방법은 가우시안 분포로부터 만든 잡음을 더하거나 임의의 샘플을 몇개 선택하여 그들을 다른 군집에 배정시킬 수도 있다. 새로 만든 해가 우수하면 그것을 새로운 해로 사용한다. 시간이 지남에 따라 변형시키는 정도의 파라미터인 온도 T를 낮추어 간다.
10.7.2 유전 알고리즘
유전 알고리즘을 설계하기 위해서는 해 표현, 선택, 교차, 변이, 대치를 고려해야 한다. 이 중 선택과 대치는 11장에서 제시하는 일반적인 연산을 사용하면 된다.
교차 연산은 두 부모 해를 가지고 자식 해를 만드는데 자식은 부모와 달라지지만 특성을 이어받아야 한다. 군집화에서는 일 점 교차를 많이 사용한다. 해를 염색체(chromosome)이라 부르고 염색체를 구성하는 각각의 자리를 유전자(gene)이라 부른다. 교차 연산은 [1, m-1] 사이의 난수를 발생시켜 자름 선을 결정하고 그 위치를 기준으로 앞 부분은 첫번째 부모, 뒤 부분은 두번째 부모로부터 복사한다.
교차 연산을 마치면 자식 해에 변이 연산을 가해야 한다. 변이 연산은 유전자 하나를 임의로 선택하여 그것에 작은 난수를 더하면 된다.
해 표현 방법으로는 앞에서 사용한 두 가지 표현 이외에 $ Z=(z_1, \dots, z_N) $으로 샘플의 속한 군집을 벡터로 표현하는 방법도 있다. 이 방법은 샘플이 많을 때 염색체가 아주 커진다는 단점이 있으며 교차와 변이 연산을 정의하기가 까다롭다.
유전 알고리즘의 장점 중 하나는 다른 알고리즘과 협력하도록 변형하는 것이 비교적 쉽다는 것이다. 이러한 방식을 혼성 유전 알고리즘(hybrid genetic algorithm)이라 부른다. 쉬운 예로 유전 알고리즘이 가진 해를 k-means을 이용하여 지역 최적점으로 수렴시킨 후 이들에 교차와 변이 연산을 가하는 것이다. 유전 알고리즘과 k-means가 협력하여 보다 품질이 좋은 해를 구하려는 것이다.