| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 | 31 |
- 우리들교회
- openCV
- 딥러닝
- c++
- 김양재 목사
- MongoDB
- No SQL
- 주일설교
- Statistics
- 몽고디비
- 김양재 목사님
- 빅데이터
- 빅 데이타
- 확률
- data science
- 빅데이타
- Artificial Intelligence
- nodeJS
- 인공지능
- 통계
- Deep learning
- 김양재
- 빅 데이터
- Big Data
- WebGL
- probability
- 데이터 과학
- Machine Learning
- R
- node.js
- Today
- Total
Scientific Computing & Data Science
[Artificial Intelligence / Machine Learning] 자기조직화맵 구현하기 본문
[Artificial Intelligence / Machine Learning] 자기조직화맵 구현하기
cinema4dr12 2017. 3. 26. 20:29Written by Geol Choi |
이번 포스팅에서는 자기조직화맵(Self-Organising Map; SOM)에 대하여 기본 이론, 특성, R을 이용한 구현하는 방법에 대하여 알아보도록 하겠습니다.
이론적 배경
SOM 또는 SOFM(Self-Organising Feature Map)은 인공신경망(Artificial Neural Network; ANN)의 한 종류로서 기본 개념은 1980년대 핀란드 교수인 Teuvo Kohonen이 제안한 Kohonen Network에 근간을 두고 있습니다.
SOM이 ANN의 한 종류이기는 하지만 "표준" ANN과는 구별되는 몇가지 특징들이 있습니다. 그 차이는 다음과 같습니다:
(1) 표준 ANN은 연속적인 레이어들로 구성되는 반면, SOM은 신경(Neuron)의 2차원 그리드로 구성됩니다.
(2) 표준 ANN은 에러를 수정하는 방향으로 학습을 하는 반면, SOM은 경쟁학습(Competitive Learning)을 실행합니다.
(3) SOM은 비지도학습(Unsupervised Learning) 문제를 다룹니다.
SOM을 구성하는 구성요소(Components)는 노드(Nodes) 또는 뉴런(Neurons)이며, 맵(Map)은 일반적으로 사각형태의 그리드(Grid)이지만 육각형(Hexagonal) 형태를 갖기도합니다.
그렇다면 SOM를 활용하여 무엇을 할 수 있을까요?
1. 구조 탐색 (Finding a Structure)
SOM은 데이터의 특징들을 파악하여 유사 데이터를 군집화(Clustering)하는 문제에 적용할 수 있습니다. 가령, 온라인 쇼핑몰에서 유사한 소비 성향을 가진 고객들을 분류한는 일이 그것입니다. 사실 SOM은 고차원적인 데이터세트(Dataset)를 저차원적인 맵- 가령 2D 그리드 -에 맵핑하여 표현하는 것인데, 이를 통해 SOM은 입력 데이터를 유사한 그룹으로 분류할 수 있습니다.
2. 차원 축소 (Dimension Reduction)
차원 축소는 구조 탐색과 일맥상통하는 얘기인데, 결국 구조 탐색을 위한 차원 축소를 하는 것입니다. 축소하려는 차원이 반드시 2차원일 필요는 없지만 인간이 시각적으로 한 눈에 인식할 수 있는 차원이 2차원이기에 통상 2차원으로 맵핑하여 그룹화 된 결과를 표현하고자 하는 것입니다.
3. 시각화 (Visualisation)
군집화 된 결과를 2D로 보여준다면 유사한 패턴을 가장 쉽게 이해할 수 있을 것입니다. 3차원 이상이 되면 결과를 보여주기가 까다로워질 것입니다.
알고리즘
SOM의 알고리즘은 여타 DNN과 마찬가지로 학습 모드(Training Mode)와 맵핑 모드(Mapping Mode)로 크게 나눌 수 있습니다:
학습 모드: 입력 데이터를 이용하여 맵을 생성.
맵핑 모드: 새로운 입력 벡터를 분류(Classification).
뉴런 또는 노드 v에 대한 현재 프로세스 i의 Weight Vector, \(\mathbf{W}_v \) 의 업데이트 식은 다음과 같습니다:
\(\mathbf{W}_{v}(i+1) \leftarrow \mathbf{W}_{v}(i) + \alpha(s) \cdot \theta(u,v,i) \cdot (\mathbf{D}(t) - \mathbf{W}_{v}(i))\)
여기서,
i: 현재 프로그레스(Progress 또는 Iteration)
t: 입력 데이터세트 D의 타겟 입력 데이터 벡터의 인덱스
D(t): 타겟 입력 데이터 벡터
v: 맵(Map)의 노드(뉴런) 인덱스
Wv: 노드 v의 현재 프로그레스의 Weight Vector
u: 맵의 BMU(Best Matching Unit)의 인덱스
θ(u,v,i): 영향력 함수(Neighborhood Function)
α(s): 현재 프로그레스에서의 학습률(Learning Rate)
위에서 언급한 BMU는 입력 데이터로부터 랜덤하게 선택된 Vector와 가장 유사한 Weight Vector를 의미하며, SOM의 핵심 개념 중 하나입니다.
또한, 현재 프로그레스 인덱스 i에 대한 학습률의 업데이트 식은 다음과 같습니다:
\( \alpha(i) = \alpha_{0} \ \mathrm{exp}\begin{pmatrix} \frac{-i}{\mathrm{niterations}} \end{pmatrix} \)
여기서,
α0: 학습률 초기값
i: 현재 프로그레스 인덱스
niterations: 총 반복 횟수
예를 들어, \( \alpha_{0}=0.01 \), niterations = 4000 이면, 프로그레스 i에 따른 α의 값의 변화는 다음과 같은 양상을 갖습니다.
영향력 함수(Neighborhood Function)는 일정 반경 범위 내에 적용되며, 이 반경 r도 마찬가지로 현재 프로그레스 인덱스 i에 대한 업데이트도 학습률의 업데이트와 유사합니다:
\( r \leftarrow r_{0} \ \mathrm{exp}{\begin{pmatrix} \frac{-i}{\mathrm{tc}} \end{pmatrix} } \)
여기서,
r: 영향력 함수의 반경
r0: 영향력 함수의 반경 초기값
tc: 시간 상수(Time Constant)
통상 영향력 함수의 반경 초기값 r0는 Network Dimension(Height & Width) 중 큰 값의 절반으로 정합니다. 즉, r0 = max(Height, Width) / 2로 합니다.
영향력 함수, θ(u,v,i)는
θ(u,v,i)\( = \ \mathrm{exp}{\begin{pmatrix} \frac{-d(u,v,i)}{2r(i)^2} \end{pmatrix}} \)
d는 현재 프로그레스 i에서의 두 노드 u, v 간의 거리입니다. 시간 상수 tc는 다음과 같이 정의됩니다:
\( \mathrm{tc} = \frac{\mathrm{niterations}}{\mathrm{log}{(r_0)}} \)
만약 r0 = 5, tc = 2400 이라면, 프로그레스에 따른 r값의 변화는 다음과 같습니다.
전체적인 알고리즘은 다음과 같습니다:
1. 맵의 노드들(Weight Vectors)을 랜덤하게 배치시킨다.
2. 입력 데이터(입력 Vector) D(t)를 랜덤으로 하나 선택한다.
3. 맵에서 각 노드(뉴런)를 비교하여 BMU를 찾아낸다 (BMU의 값 및 위치(x, y)).
4. 현재 프로그레스 i에 대하여 영향력 함수 r과 학습률 α를 업데이트 한다.
5. 현재 프로그레스 i에서의 Weight Vector를 업데이트 한다:
\( \mathbf{W}_{v}(i+1) \leftarrow \mathbf{W}_{v}(i) + \alpha(s) \cdot \theta(u,v,i) \cdot \mathbf{D}(t) - \mathbf{W}_{v}(i) \)
6. 2번 과정으로 돌아가 정의된 총 반복횟수 만큼 반복한다.
구현(Implementation)
이제 R 코드로 위의 알고리즘을 따라 SOM을 구현해 보도록 하되, 이해를 돕기 위하여 8개의 컬러(R, G, B)를 갖는 입력 데이터에 대하여 10×10 크기의 컬러맵을 임의로 생성하고, 이 맵 내에서 비슷한 컬러를 갖는 요소끼리 군집화(Clustering)하는 Color Visualisation 예제에 대해 다루어 보도록 하겠습니다.
1. 라이브러리 로딩 및 결과 이미지 저장 경로 생성
본 예제에서 컬러 맵을 출력하고 저장하기 위해 R의 패키지 라이브러리인 imager를 불러옵니다:
R CODE:
if (! ("imager" %in% rownames(installed.packages()))) { utils::install.packages("imager") } base::library(imager)
또한, Iteration이 진행됨에 따라 Color Visualisation의 결과 이미지를 저장할 디렉터리를 하나 생성합니다:
R CODE:
# creates image output directory for saving visualisation images mainDir <- "./" subDir <- "output" ifelse(!base::dir.exists(base::file.path(mainDir, subDir)), base::dir.create(base::file.path(mainDir, subDir)), FALSE)
위의 코드에서 base::dir.exists()는 해당 경로가 존재하는지를 판단하는 것이며, base::dir.create()는 해당 디렉터리를 생성하는 함수입니다.
2. 입력 데이터세트 정의
8개의 3채널(R, G, B) 컬러 성분을 raw_data로 정의한다. raw_data의 행(Row)은 순서대로 R, G, B 채널을 의미하며, 각 열(Column)은 각각 하나의 컬러를 의미합니다:
R CODE:
# 8 colours as initial test set raw_data <- base::matrix(base::c(1, 0, 0), nrow = 1, ncol = 3) raw_data <- base::rbind(raw_data, base::c(0, 1, 0)) raw_data <- base::rbind(raw_data, base::c(0, 0.5, 0.25)) raw_data <- base::rbind(raw_data, base::c(0, 0, 1)) raw_data <- base::rbind(raw_data, base::c(0, 0, 0.5)) raw_data <- base::rbind(raw_data, base::c(1, 1, 0.2)) raw_data <- base::rbind(raw_data, base::c(1, 0.4, 0.25)) raw_data <- base::rbind(raw_data, base::c(1, 0, 1)) raw_data <- raw_data * 255.0 raw_data <- base::t(raw_data)
> raw_data
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,] 255 0 0.00 0 0.0 255 255.00 255
[2,] 0 255 127.50 0 0.0 255 102.00 0
[3,] 0 0 63.75 255 127.5 51 63.75 2553. 네트워크 및 파라미터 정의
네트워크는 노드(또는 뉴런)의 집합이며 이들은 DNN의 Weight라고 생각하면 되겠습니다. 네트워크의 차원을 10×10 크기로 하고 0으로 초기화합니다:
R CODE:
network_dimensions <- base::matrix(0L, nrow = 10, ncol = 10)
또한, 학습을 위한 총 계산 반복횟수(Iterations)는 4000회로 정하고, 초기 학습률(\(\alpha\))은 0.01로 하였습니다.
R CODE:
n_iterations <- 4000 init_learning_rate <- 0.01 # initial neighbourhood radius init_radius <- base::max(dim(network_dimensions)) / 2.0 # time constant decay parameter time_constant <- n_iterations / base::log(init_radius)
초기 영향력 반경(init_radius)과 초기 시간 상수(time_constant)의 값은 앞서 알고리즘 섹션에서 언급한 바 있습니다. 참고로 이러한 Hyperparameter들의 값을 정하는 명확한 규칙은 없습니다.
또한, 코딩 편의를 위해 raw_data의 차원을 별도의 변수에 저장하였습니다.
R CODE:
# dimension of raw_data m <- base::nrow(raw_data) n <- base::ncol(raw_data)
4. 정규화(Normalisation)
일반적으로 각 Feature에 대한 값의 범위는 각각 다르다. 어떤 경우에는 Order of Magnitude의 차이가 날 수도 있는데 이 경우 특정 Feature가 결과에 지배적(Dominant)일 수 있으므로 각 Feature의 값을 정규화해야 합니다. 통상 정규화는 각 Feature 별로 최대, 최소값을 취하여 전체 값들이 특정 범위 안에 들도록 합니다.
Color Visualisation 예에서는 0 ~ 255 분포의 R, G, B 값을 0.0 ~ 1.0 범위 안에 들 수 있도록 최대값으로 나눕니다. 또한 R, G, B의 범위는 모두 동일하므로 Feature 별로 정규화하지 않고 전체적으로 정규화합니다 (특정 Feature가 지배적인 경우는 Feature 별로 각각 정규화합니다).
R CODE:
# if True, assume all data on common scale # if False, normalise to [0 1] range along each column normalise_by_column <- FALSE new_data = raw_data # check if data needs to be normalised if(normalise_data) { if(normalise_by_column) { # normalise along each column base::sapply(X = 1:base::ncol(new_data), FUN = function(x) { col_max <- base::max(new_data[,x]) new_data[,x] <<- new_data[,x] / col_max } ) } else { # normalise entire dataset new_data <- raw_data / base::max(new_data) } }
normalise_data은 정규화 여부를 결정하는 불리언(Boolean) 변수(또는 플래그)이며, normalise_by_column는 각 Column 별(또는 Feature 별)로 정규화할 것인지에 대한 여부를 결정하는 변수입니다.
base::sapply()는 각 Column 별로 정규화 오퍼레이션을 적용하기 위해 사용한 함수이며, FUN() 함수에서 <-- 가 사용되었는데, 이는 변수의 스코프(Scope)와 관련된 것으로 base::sapply() 함수 내에서 new_data 값을 업데이트 하기 위함입니다.
5. 네트워크 초기화
네트워크(Weights) 값을 Uniform Distribution으로 0.0과 1.0 사이의 랜덤 값으로 초기화합니다:
R CODE:
# setup random weights between 0 and 1 # weight matrix needs to be one m-dimensional vector for each neuron in the SOM net <- base::array(0, base::c(base::nrow(network_dimensions), base::ncol(network_dimensions), m)) base::sapply(X = 1:3, FUN = function(x) { tmp <- stats::runif(base::nrow(network_dimensions) * base::ncol(network_dimensions)) net[,,x] <<- base::as.array(base::matrix(tmp, nrow = base::nrow(network_dimensions), ncol = base::ncol(network_dimensions))) })
6. 반복 계산을 통한 클러스터링
이제 모든 값을 정규화 및 초기화하는 등 반복 계산을 위한 준비를 마쳤습니다. 아래의 계산은 n_iterations 만큼 반복됩니다:
R CODE:
cnt <- 0 for(i in 1:n_iterations) { # SOM algorithm 연산 수행 }
cnt는 매 반복 계산마다 이미지를 저장하면 계산 부담이 크므로 특정 반복 횟수 간격으로 저장할 수 있도록 현재의 반복 계산 횟수를 저장하는 변수입니다.
반복 계산 코드는, 위의 알고리즘 섹션에서 언급한 바와 같이 진행됩니다:
(1) 랜덤으로 학습 데이터 선택
n개의 학습 데이터(R, G, B로 구성된 벡터)로부터 1개를 랜덤으로 추출하여 training 변수에 저장합니다:
R CODE:
# select a training example at random training <- new_data[,base::sample(x = 1:n, size = 1)]
(2) BMU 탐색
선택된 학습 데이터(벡터)에 가장 근접한 BMU(Best Matching Unit)을 맵에서 탐색합니다:
R CODE:
# find its Best Matching Unit tmp <- find_bmu(training, net, m) bmu <- tmp[[1]] bmu_idx <- tmp[[2]]
여기서 find_bmu()는 BMU를 탐색하는 함수이며 다음과 같이 정의됩니다:
R CODE:
############################################################################## # Find Best Matching Unit ############################################################################## find_bmu <- function(training, net, m) { bmu_idx <- base::c(0, 0) # set the initial minimum distance to a huge number min_dist <- .Machine$integer.max # calculate the high-dimensional distance between each neuron and the input for(x in 1:base::nrow(net)) { for(y in 1:base::ncol(net)) { w <- net[x, y, ] # don't bother with actual Euclidean distance, to avoid expensive sqrt operation sq_dist <- base::sum((w - training)^2) if(sq_dist < min_dist) { min_dist <- sq_dist bmu_idx <- base::c(x, y) } } } # get vector corresponding to bmu_idx bmu <- net[bmu_idx[1], bmu_idx[2], ] # return the (bmu, bmu_idx) tuple return(base::list(bmu, bmu_idx)) }
BMU 탐색 시 유클리드 거리(Euclidean Distance) 식 - 정확히는 Euclidean Distance는 아니지만 최소값을 찾는 것이므로 상관없음 - 을 이용하였습니다. 탐색된 BMU에 대하여 BMU의 값(bmu)과 인덱스(bmu_idx)를 저장합니다.
(3) SOM 파라미터 업데이트
영향력 반경(r)과 학습률(\(\alpha\))을 업데이트 합니다:
R CODE:
# decay the SOM parameters r = decay_radius(init_radius, i, time_constant) l = decay_learning_rate(init_learning_rate, i, n_iterations)
decay_radius() 함수와 decay_learning_rate() 함수는 다음과 같습니다:
R CODE:
############################################################################## # Decay Radius ############################################################################## decay_radius <- function(initial_radius, i, time_constant) { return(initial_radius * base::exp(-i / time_constant)) }
R CODE:
############################################################################## # Decay Learning Rate ############################################################################## decay_learning_rate <- function(initial_learning_rate, i, n_iterations) { return(initial_learning_rate * base::exp(-i / n_iterations)) }
(4) Weight Vector 업데이트
현재 프로그레스 i에서 선택된 BMU에 대하여 영향력 반경(r) 내에 속하는 맵 내의 요소들에 대하여 Weight Vector를 업데이트 합니다:
R CODE:
# now we know the BMU, update its weight vector to move closer to input # and move its neighbours in 2-D space closer # by a factor proportional to their 2-D distance from the BMU for(x in 1:base::nrow(net)) { for(y in 1:base::ncol(net)) { w <- net[x, y, ] # get the 2-D distance (again, not the actual Euclidean distance) w_dist <- base::sum((base::c(x, y) - bmu_idx)^2) # if the distance is within the current neighbourhood radius if(w_dist <= r^2) { # calculate the degree of influence (based on the 2-D distance) influence <- calculate_influence(w_dist, r) # now update the neuron's weight using the formula: # new w = old w + (learning rate * influence * delta) # where delta = input vector (training) - old w new_w <- w + (l * influence * (training - w)) # commit the new weight net[x, y, ] = new_w } } }
calculate_influence() 함수는 영향력 계수 \(\theta(u,v,i)\)를 계산하는 함수입니다:
R CODE:
############################################################################## # Calculate Influence ############################################################################## calculate_influence <- function(distance, radius) { return(base::exp(-distance / (2 * (radius^2)))) }
(5) 결과 이미지 생성 및 저장
현재 Iteration을 표시하고, 매 50회 반복 횟수마다 현재의 Weight Map(net)을 imger 라이브러리 패키지를 이용하여 이미지로 생성하고 이를 저장합니다.
R CODE:
base::cat("\nIterations: ", i) # plot every 50th iteration if((i %% 50) == 0) { cnt <- cnt + 1 img <- imager::as.cimg(net) # save image imgName <- base::sprintf("%s%s/image_%04d.png", mainDir, subDir, cnt) imager::save.image(img, imgName) }
앞의 과정들(1. 랜덤으로 학습 데이터 선택)을 지정된 반복 횟수 만큼 반복합니다.
결과
앞의 코드를 이용하여 저장된 결과 이미지는 다음과 같습니다.
전체 소스 코드
마지막으로 전체 소스 코드를 수록하고 본 포스팅을 마무리 하겠습니다.
SOM.R
