본문 바로가기
지능형시스템/머신러닝

[머신러닝] - 자기조직화지도(Self-Organizing Map, SOM)

by CHML 2016. 1. 5.
1. 개요

대뇌피질의 시각피질의 학습 과정을 모델화한 인공신경망으로써 자율 학습에 의한 클러스터링을 수행하는 알고리즘이다.


2. 용어 정의

클러스터링(clustering): 데이터의 유사성에 기초하여 데이터를 몇몇의 그룹으로 분류하는 기법

입력층(input layer): 입력 벡터를 입력받는 층

경쟁층(competitive layer): 입력 벡터의 특성에 따라 입력 벡터가 한 점으로 클러스터링 되는 층

가중치(weight): 인공신경망에서 가중치는 각 입력 값에 대한 입력 값의 중요도를 값을 말함

노드(node): 경쟁층에서 입력 벡터들이 서로의 유사성에 의해 모이는 하나의 영역



3. 알고리즘 구조

자기조직화지도 인공신경망 기법중에서 가장 단순한 알고리즘 중 하나이다. 알고리즘에서 입력 벡터와 경쟁층 노드간의 거리를 나타내는 \({D}_{ij}\)와 노드의 가중치를 수정하는 연산은 항목 4에 따로 설명한다. 자기조직화지도에서 알고리즘을 실행하거나 종료하기 위해서는 현재 입력 벡터와 현재 반복 횟수, 두 개의 값을 유지해야 한다. 자기조직화지도 알고리즘은 아래와 같다.


1) 가중치 행렬 각 원소의 값을 임의의 0보다 크고 1보다 작은 값으로 초기화

2-1) 입력 벡터와 경쟁층에 존재하는 $j$개의 노드에 대해 입력 벡터와 노드 간의 거리 $D_{ij}$를 계산

2-2) 현재 입력 벡터와 $D_{ij}$값이 가장 작은 경쟁층의 노드를 선택

2-3) 해당 노드의 가중치와 이웃 노드의 가중치를 수정

5) 현재 입력 벡터가 마지막 입력 벡터라면 다음 과정으로 이동하고, 그렇지 않다면 과정 2로 돌아간다

6-1) 현재 반복 횟수가 최대 반복 횟수라면 알고리즘을 종료

6-2) 현재 반복 횟수가 최대 반복 횟수가 아니면 현재 입력 벡터를 처음 입력 벡터로 설정하고 과정 2로 돌아간다



4. 연산 정의

입력 벡터와 노드 간의 $D_{ij}$는 아래와 같이 정의된다.


 


위의 수식에서 $n$은 입력 벡터의 크기, $w_{ij}$는 가중치 테이블에서 $i$행 $j$열의 값을 나타낸다. 그리고 가중치와 뺄셈 연산을 하는 $x_{i}$는 입력 벡터의 $i$번째 값을 뜻한다.


경쟁층의 노드를 선택한 다음 해당 노드의 가중치를 수정하는 연산은 아래와 같다.



위의 식에서 \({w}_{ij}(new)\)는 새로운 가중치\({w}_{ij}(old)\)는 이전 가중치를 뜻한다. 그리고 우변의 두번째 항에 있는 $a(t)$는 학습률을 나타내며, 알고리즘을 설계할 때 정하는 값으로 알고리즘이 반복될 수록 값이 작아진다.


5. 예제

4개의 입력 벡터를 2개의 그룹으로 클러스터링하는 자기조직화지도(SOM)을 설계한다. 자기조직화지도에 입력되는 4개의 입력 벡터는 아래와 같다.

(1, 0, 0, 1)

(0, 0, 1, 1)

(0, 1, 0, 1)

(0, 0, 1, 0)


입력 벡터를 2개의 그룹으로 클러스터링 하므로 경쟁층 노드의 수는 2이다. 자기조직화지도의 최대 반복 횟수는 10,000번으로 설정한다. 초기 학습률은 0.6으로 설정하고, 한번의 연산이 끝나면 학습률은 이전 학습률의 0.4배로 변경한다. 따라서 다음 단계의 학습률은 아래와 같이 계산된다.


경쟁층의 노드의 수가 2개 뿐이기 때문에 이웃 노드의 개념은 없다고 가정한다. 출력층 노드의 수가 많은 자기조직화지도에서는 가중치가 수정되는 노드의 이웃 노드도 같이 가중치를 수정해준다.


1) 초기 가중치 행렬 초기화

입력 벡터의 크기가 4이고 출력층 노드의 수가 2이므로 가중치 행렬의 크기는 4 X 2이다. 가중치 행렬 각 원소의 값은 0 ~ 1 범위에 있는 임의의 값으로 초기화한다. 임의의 값으로 초기화한 가중치 행렬은 아래와 같다고 가정한다.



2) 입력 벡터와 경쟁층 노드의 거리 계산 및 가중치 수정

입력 벡터와 경쟁층 노드의 거리를 계산하는 식은 아래와 같다.



2-1) 첫 번째 입력 벡터 (1, 0, 0, 1)에 대해 연산



그러므로 첫 번째 입력 벡터는 경쟁층의 첫 번째 노드와 가장 가깝다. 경쟁층의 첫 번째 노드가 선택되었으므로, 첫 번째 노드에 대한 가중치를 수정한다.

새로운 가중치는 아래와 같이 계산된다.



예를 들어 경쟁층 첫 번째 노드의 현재 두 번째 가중치인 0.3은 아래와 같은 식에 의해 0.12로 변경된다.



위의 식에서 0.6은 앞에서 설정한 학습률이다. 이러한 방식으로 경쟁층 첫 번째 노드의 가중치를 모두 수정하면 가중치 테이블은 아래와 같이 변경된다.



2-2) 두 번째 입력 벡터 (0, 0, 1, 1)에 대해 연산


그러므로 두 번째 입력 벡터는 경쟁층의 두 번째 노드와 가장 가깝다. 경쟁층의 두 번째 노드가 선택되었으므로, 두 번째 노드에 대한 가중치를 수정한다. 수정된 가중치 행렬은 아래와 같다.



2-3) 세 번째 입력 벡터 (0, 1, 0, 1)에 대해 연산


그러므로 경쟁층의 두 번째 노드를 선택하고, 두 번째 노드에 대한 가중치를 수정한다.



2-4) 네 번째 입력 벡터 (0, 0, 1, 0)에 대해 연산


그러므로 경쟁층의 두 번째 노드를 선택하고, 두 번째 노드에 대한 가중치를 수정한다.



3) 최대 반복 횟수 검사

최대 반복 횟수만큼 입력 벡터에 대한 연산을 수행했으면 알고리즘을 종료하고, 그렇지 않으면 과정 4로 이동한다. 현재까지 입력 벡터에 대한 연산을 총 1회 수행했으므로, 최대 반복 횟수인 10,000번 보다 적다. 그러므로 과정 4로 이동한다.


4) 현재 입력 벡터를 첫 번째 입력 벡터로 수정

모든 입력 벡터에 대한 연산을 수행했으므로, 현재 입력 벡터는 네 번째 입력 벡터이다.최대 반복 횟수만큼 반복하지 않았으므로, 과정 5로 이동하고 학습률을 수정한 다음 과정 2로 돌아간다. 그 다음 첫 번째 입력 벡터부터 다시 입력 벡터와 경쟁층 노드의 거리를 계산하고, 각 노드의 가중치를 수정한다. 그러므로 입력 벡터에 대한 연산을 반복하기 위해 현재 입력 벡터를 첫 번째 입력 벡터로 재설정하고, 과정 5로 이동한다.


5) 학습률 수정

학습률을 아래와 같은 방법으로 수정한다.



그러므로 학습률은 0.6에서 0.24로 수정된다. 그 다음 과정 2로 이동하여 입력 벡터에 대한 연산을 반복한다.


* 과정 5에서 과정 2로 이동할 때, 현재까지 계산한 가중치 행렬은 그대로 유지한다.

* 초기 학습률과 학습률의 감소 비율은 알고리즘을 설계할 때, 직관적으로 설정하는 값이다.

* 초기 학습률과 학습률의 감소 비율을 이론적으로 설정하고 싶다면, 퍼지이론(Fuzzy theory)를 참조하면 된다.