일반적으로 안드로이드 운영체제를 Build 할 때 거의 대부분의 경우 Ubuntu 환경에서 수행됩니다. AOSP 공식 홈페이지에서도 Ubuntu를 권장하고 있는 바이기도 합니다.

 그래도 혹여나 하는 마음에 Fedora 운영체제에서 안드로이드를 Build 해보는 과정에 대해 포스팅을 해보고자 합니다. 같은 RPM 패키지를 사용하는 Redhat이나 OpenSUSE에서도 이 포스팅의 내용을 적용할 수 있으리라 생각합니다.

Build Version    : Android 6.0.1(Marshmellow)

OS             : Fedora 23 (Twenty Three) 64-bit

JDK Version     : OpenJDK 1.7.0

1. 빌드하고자 하는 AOSP 소스코드를 다운로드 받습니다. 관련 내용에 대해 자세히 알아보고자 하시는 분은 아래 포스팅을 참조해 주기길 바랍니다.

http://elecs.tistory.com/56

$ mkdir ~/bin

$ export PATH=$PATH:~/bin

$ curl https://storage.googleapis.com/git-repo-downloads/repo > ~/bin/repo

$ chmod a+x ~/bin/reop

$ mkdir ~/aosp 

$ cd ~/aosp

$ repo init -u https://android.googlesource.com/platform/manifest -b android-6.0.1_r1

$ repo sync -j4

 위 과정까지 마치셨다면 아래와 같이 aosp 폴더에 소스코드 다운로드 된 것을 확인하실 수 있습니다.

2. 다운로드한 안드로이드 소스코드를 컴파일할 수 있는 환경을 설정합니다. Marshmellow(6.0) 버전의 경우 OpenJDK 1.7.0을 설치해야 합니다. Oracle JDK로 컴파일을 시도하려 해도 시작하기 전에 컴파일이 중단되어버립니다. Fedora의 경우 dnf를 통해서는 최신 버전의 자바만 지원해주기 때문에 사용자가 직접 OpenJDK를 설치해야 합니다. 설치 방법은 아래의 포스팅을 참조해 주시기 바랍니다.

Fedora에 이전 버전의 OpenJDK 설치하기(Install OpenJDK 7 in Fedora 23)

http://elecs.tistory.com/166

만약 설치한 이후에도 해당 버전이 적용되어 있지 않았을 경우 아래의 명령어를 통해 직접 설치해줍시다.

# alternatives --install /usr/bin/java java /usr/lib/jvm/java-1.7.0-openjdk/bin/java 1

# alternatives --install /usr/bin/javac javac /usr/lib/jvm/java-1.7.0-openjdk/bin/javac 1

# alternatives --install /usr/bin/javadoc javadoc /usr/lib/jvm/java-1.7.0-openjdk/bin/javadoc 1

3. dnf를 통해 안드로이드를 빌드하기 위해 필요한 패키지를 설치합니다. 

# dnf install bison gcc xorg-x11-fonts-Type1 libpng15 

4. 이제 다운로드 받은 소스코드를 build 하기 위한 준비과정을 진행해 보도록 하겠습니다. 먼저 build 환경을 초기화합니다.

$ ~/aosp

$ source build/envsetup.sh

$ lunch

 안드로이드 6.0.1 버전 기준으로 build 환경은 다음과 같이 나타납니다.

 여기서 자신이 build 하고자 하는 환경을 선택합니다. 본 포스팅의 경우 Android Studio를 통한 에뮬레이터에서의 실행을 목표로 함으로 1번 혹은 14번을 선택합니다. 혹시 자신이 build 하고자 하는 환경에 대한 설정을 알고 싶으신 분은 아래의 포스팅을 참조해 주시기 바랍니다.

안드로이드 프레임워크 프로그래밍(3) [NEXUS5에 소스 빌드하기]

http://elecs.tistory.com/59

5. 이제 build를 해보도록 합니다.

$ make update-api && make -j4

아래와 같은 결과가 나왔다면 Fedora 운영체제 환경에서 안드로이드 이미지를 빌드하는 데에 성공한 겁니다!

 보통 거의 대부분의 프로그램들의 경우 입문자들을 위한 'Hello, World!' 예제들이 제공되어서 해당 프로그램의 이용 방법들을 이해하는 것이 용이한 편인데 이번에 공부하게 된 하둡의 경우 맵리듀스의 특성 때문에 Hello World 예제를 제공하는 것이 애매하지 않았나 싶습니다. 그 만큼 하둡 입문자들에게 있어서 맵리듀스의 원리를 체감하는게 힘들것이라 생각합니다.

 마침 하둡 예제를 찾아보던 도중 맵리듀스의 원리를 쉽게 이해할 수 있는 예제를 알게 되어 이렇게 소개합니다. 여러분들도 열심히 보시면서 이해할 수 있는 기회가 되었으면 합니다!

- 개발 환경

언어 : Java

IDE : VI

JDK 버전 : 1.7.0_91

운영체제 : Ubuntu 14.04

Hadoop 버전 : 2.6.0

Protoc 버전 : 2.5.0

실행 환경 : Terminal(우분투)

 1. Hadoop의 분산 실행 방식인 Map Reduce

 위 그림은 Hadoop의 Map Reduce 방식을 이미지로 도식화한 모습입니다. 먼저 Hadoop을 통해 빅데이터가 입력되면 데이텨의 내부는 입력 Split으로 잘게 분리가 된 후 Mapper를 통해 (Key, Value) 쌍으로 묶여서 각 노드로 보내집니다. 이 때 노드로 분배되는 과정은 각 Key의 Hash값을 기준으로 하여 각 Node 내에 있는 Task Container에게 전송됩니다. 이 때 각 Container는 같은 값을 가진 Key끼리 보내지므로 각 Key별로 같은 값을 계산하는 값을 전송할 수 있는 것입니다.

 (Key, Value)쌍은 각 같은 Key 끼리 Reduce로 전송되어지며 Reduce를 통해 설정이 완료되면 Result로 보내지면서 Hadoop의 hdfs 파일시스템에 저장됩니다.

 2. 행렬곱(Matrix Multiplication)의 원리

 행렬곱이란 이름 그대로 두 개의 행렬을 곱해 하나의 새로운 행렬을 구하는 것을 의미합니다. 행렬곱은 선행하는 행렬의 Row와 후행하는 행렬의 Column 내의 각 성분들의 곱을 합하는 것으로 값을 구합니다. 쉬운 예를 구하기 위해 아래와 같이 행렬 A와 B가 있다고 합시다.

  행렬 A는 i×j 행렬이며 행렬 B는 j×k 행렬입니다. 두 행렬의 행렬곱은 A×B로 나타낼 수 있으며 A의 Row와 B의 Column에 해당하는 요소 각각의 곱의 덧셈을 구하는 것이 행렬곱을 구하는 공식입니다. 이 때, A의 j에 해당하는 Row의 개수와 B의 j에 해당하는 Column의 개수가 일치해야 행렬곱이 성립됩니다..

 위의 행렬 A×B의 결과 값은 아래와 같이 표현할 수 있겠습니다.

 행렬곱 A×B의 최종 결과는 A의 Column 개수인 i와 B의 Row 개수인 k의 조합인 i×k 행렬로 나타납니다.

참고자료 : 위키백과

https://ko.wikipedia.org/wiki/%ED%96%89%EB%A0%AC_%EA%B3%B1%EC%85%88

 3. 행렬곱의 Map Reduce 구현

  Hadoop의 분산 방식을 활용하여 행렬곱의 결과로 나오는 행렬의 각 요소에 대한 계산을 Map Reduce로 분산하여 계산해보도록 합니다.입력값은 아래와 같이 주어졌다고 가정합니다.

/hadoop-matrix-multiplication/MapInput.txt

 주어진 입력값의 각 줄을 살펴보았을 때 첫 번째 값은 해당 행렬값이 A인지 B인지를 알려주는 값이고 두 번째는 column값, 세 번째는 row값, 네 번째는 해당 요소의 값을 나타냅니다. 즉 A는 2×5 행렬이고 B는 5×3 행렬이며 행렬곱 A×B은 2×3 행렬이 됩니다. 즉, 행렬곱 A×B를 구하기 위해 필요한 Key의 개수는 행렬곱 A×B의 요소의 개수인 2×3=6이라 할 수 있겠습니다.

 행렬곱 연산이 적용된 Map Reduce는 아래와 같이 그림으로 나타낼 수 있겠습니다.

Hadoop으로 입력된 행렬 데이터는 Map을 거치기 전에 입력 split으로 분리되어 각각의 Mapping 과정을 거치게 됩니다. 여기서 빨갛게 표시한 부분이 Key이고 그 뒤의 값이 Value입니다. Map을 거친 행렬의 각 요소는 각 노드 내의 Task Container에 들어가게 되어 Reduce 단계에서 행렬곱 연산을 수행하게 됩니다. 이 때 Map 단계에서 밑줄친 4개의 (Key, Value) 쌍이 Reduce에 넘어와서 서로의 값이 계산되고 있는 것을 보실 수 있습니다. 연산을 마치게 되면 hdfs 파일시스템에 지정된 폴더에 결과를 저장합니다.

 4. 프로그램 구현

 이제 행렬곱을 구현한 Hadoop 예제를 보도록 하겠습니다. 이 과정에 들어가기 앞서 Terminal 환경에서 Hadoop 프로그램을 컴파일 하는 환경을 구축하는 방법을 알아야 합니다. 아래 그 간단한 예제를 포스팅한 내용을 참조해 주시기 바랍니다.

[Hadoop] pom.xml로 maven 컴파일하기

http://elecs.tistory.com/163

 위의 예제를 참고하시면서 아래 행렬곱 분산 처리 프로그램 소스코드를 보시면 대략적인 동작 원리를 이해하실 수 있을 것입니다.

/hadoop-matrix-multiplication/src/main/java/elecs/tistory/com/MatrixMultiplication.java

 위 행렬곱 분산 연산 예제를 실행하면 아래와 같은 결과값이 나옵니다. 각 행렬값 요소의 위치는 변경될 수 있습니다.

출저 : http://magpiehall.com/one-step-matrix-multiplication-with-hadoop/

 오늘날은 인터넷을 통해 수많은 정보를 얻을 수 있는 빅데이터 시대에 도래하였습니다. 정보의 양이 매우 방대하다 보니 데이터 하나 하나 마다 개별로 의미를 찾아보기 보다는 전체 데이터의 특성을 분류하여 의미를 찾기 위해 사용되는 정교한 Clustering(군집화) 알고리즘이 필요하게 되었습니다.

 Clustering 알고리즘의 핵심은 주어진 데이터들을 유사한 특성을 가진 데이터들끼리 분류하여 이를 하나의 같은 그룹으로 만들어 주는 기능입니다. 이러한 Clustering 알고리즘의 특성 덕분에 빅데이터 내의 수많은 정보들을 특정한 카테고리나 클래스로 분류할 수 있는 것이지요.

 본 포스팅에서는 이러한 Clustering 알고리즘 중 하나인 Spectral Clustering 알고리즘에 대해 알아보도록 하겠습니다.

1. Data Clustering(자료 군집화)

  초기에 주어지는 데이터는 단순히 자신이 가지고 있는 정보를 그저 나열하고 있는 모습을 띄고 있습니다. 이를 하나의 그룹으로 분류하기 위해 서로 유사한 데이터끼리 묶어주는 작업을 하는 것이 Clustering 알고리즘의 목적입니다.

 위의 그림에서 보시는 바와 같이 단순히 나열되어 있던 각 데이터들이 유사한 3개의 그룹으로 나누어지게 된 것을 보실 수 있습니다. 여기서 유사하다는 것은 점 사이의 거리로 나타냅니다. 즉, 서로 가까운 점들끼리 묶어보니 3개의 그룹이 만들어지게 된 것이지요.

 그렇다면 이러한 클러스터링 알고리즘은 어떠한 방식이 있는 것일까요?

 각 그룹을 분류하는 Clustering 알고리즘은 2가지 접근 방법이 있습니다. 하나는 매개변수 모델 기반 방식(Parametric Model-based)과 그래프 기반 방식(Graph-based) 방식이 있습니다. 매개변수 모델 기반 방식의 경우 말 그대로 주어진 데이터를 가지고 임의의 그룹 중심점을 찾은 다음 반복적으로 그룹의 중심점을 찾아가는 과정입니다. k-Means 알고리즘이 이를 사용한 알고리즘으로서, 반복적인 연산을 통해 결과를 얻어냅니다.

 위의 그림과 같이 거리상으로 떨어져있는 2개의 그룹이 존재한다고 하였을 때 임의의 중심점 2개를 잡은 후 해당 점에서 가까운 데이터들을 그룹으로 만든 후 새로 만들어진 그룹 내의 중심점을 잡고, 다시 만든 중심점에서 가까운 데이터들을 그룹으로 만드는 방식을 반복하다 보면 위의 그림과 같이 한 점으로 수렴하게 됩니다. 이러한 매개변수 모델 기반 방식의 최대 단점은 결과가 항상 일정하지 않으며 가끔씩 잘못된 그룹으로 분류되는 경우가 발생할 수 있다는 점입니다.

 그래프 기반 방식은 각 데이터의 점들과 다른 점 사이에 선을 긋고 두 데이터 사이의 유사도에 따라 비중을 부여하는 방식입니다. 그래프 기반 방식에 따르면 두 데이터의 유사점이 많으면 비중을 키우고, 유사점이 낮으면 비중을 낮추는 식으로 하여 이를 기준으로 별개의 그룹으로 나누는 방식입니다. 이 방식을 사용하면 매개변수 모델 기반 방식보다 비교적으로 결과값이 거의 일정하게 나온다는 장점이 있습니다. 두 그룹으로 나누는 데 사용하는 방식으로는 Minimum cut과 Normalized cut이 있습니다.

2. Segmentation by Graph Partitioning(그래프 클러스터링)

 설명하기에 앞서 Spectral Clustering을 간단하게 설명해주는 동영상을 참고해봅시다. 바로 이해하기 어려우시겠지만 영상으로 한 번 보는 것이 이어서 설명하는 데에 도움이 될 것입니다.

 위 동영상을 시청하셧다면 이제 설명을 해드리도록 하겠습니다. 아래와 같이 9개의 점들이 3개의 그룹을 이루고 있는 데이터가 있다고 가정해봅니다.

 이제 Spectral Clustering 알고리즘을 사용하여 위 그림의 데이터들을 Graph로 표현해보도록 하겠습니다. 이들을 그래프로 나타나기 위해서는 유사도 행렬(Affinity Matrix)를 통해 이를 표현해야 합니다.

 아래의 그림은 위 데이터를 유사도 행렬(Affinity Matrix)로 표현한 것입니다. 각 색깔에 맞추어 유사도 행렬을 만든 점을 주목해 주시길 바랍니다.

 이제 적용된 유사도 행렬에서 처럼 위 데이터를 그래프로 나타내봅니다. 색깔로 칠해진 부분은 1로 굵은 선으로, 색깔이 칠해지지 않은 부분은 0으로 가느다란 선으로 표시합니다.

 어떤가요? 위와 같이 각 데이터를 그래프로 표현하니 눈에띄게 구분이 되고 있는 것을 알 수 있습니다.

 지금까지 우리의 시각에서 판단해서 Spectral Clustering 알고리즘을 수행하였습니다. 그렇다면 컴퓨터를 통해 이를 직접 구현하려면 어떠한 방식으로 해야할까요? 각 데이터의 유사도를 사람처럼 판단해서 위와 같은 그래프로 표현할 수 있는 방법은 있는걸까요?

3.Affinity Matrix(유사도 행렬 만들기)

 두 데이터의 유사도가 높을수록 최대한 높은 값을 가지게 하고 반대로 유사도가 낮을수록 최대한 0에 가깝게 값을 만든다면 위의 유사도 행렬(Affinity Matrix)과 비슷한 모양의 행렬이 만들어 질 수 있으리라 생각됩니다. 이를 위해 가우시안 커널 σ을 사용하는데 그 공식은 아래와 같습니다. 이 때 w는 데이터 i, j 사이의 선, σ는 커널의 폭, x는 데이터 i, j의 거리 정보로서 두 데이터 i, j 사이의 거리를 나타낸다 볼 수 있겠습니다.

 이 식에서 가장 중요한 부분은 바로 σ입니다. σ는 각 데이터의 거리간격 w의 결과에 지대한 영향을 미치는 변수로 적절한 값으로 이를 설정하여주면 각 그룹 사이의 간격을 적당하게 구분시켜줄 수 있게 됩니다.  아래의 표는 σ의 크기에 따른 유사도 값 w의 크기의 변화를 나타낸 것입니다.

 위의 그래프에서 볼 수 있는 바와 같이 σ의 값이 작을수록 각 그룹을 세분하게 나누어줄 수 있으나 자칫하면 같은 그룹에 속하는 데이터 사이의 간격이 조금이라도 멀어지면 w값(affinity)이 급격하게 줄어드는 것을 보실 수 있습니다. 반면, σ의 값이 클수록 다소 멀리 떨어져 있는 같은 그룹 내의 데이터를 포함시킬 수 있으나 자칫하면 비교적 거리가 가까운 다른 그룹의 데이터까지 포함해버리는 경우가 발생하게 됩니다. 아래 Reference에 따르면 σ의 값을 각 데이터 i와 j의 주변 점에서 (2d+1)번째로 가까운 점 사이의 거리를 σ로 사용할 경우 최적의 값을 구할 수 있다고 소개하고 있습니다. 이 때 d는 데이터의 차원을 의미합니다. 데이터가 제공하는 정보가 1개라면 3번째로, 2개라면 5번째, 3개라면 7번째로 가까운 점 사이의 거리를 사용해 각 σi와 σj를 구하면 적합한 값 w를 얻을 수 있을 것입니다.

4. Spectral Clustering 구현하기

 다음과 같은 데이터가 입력값으로 주어졌다고 가정해 봅시다.

 위 입력값을 직관적인 관점에서 3개의 cluster로 구분한다면 (1,2), (3,4), (5,6)이 될 것으로 기대할 수 있습니다.

 위 데이터를 Affinity Matrix로 나타내면 다음과 같습니다. 여기서 가우시안 커널 σ은 임의로 설정된 값으로 하여 데이터가 충분히 구분될 수 있도록 하였습니다.

 주어진 데이터는 총 6개이므로 6X6 크기의 Affinity Matrix가 만들어집니다. 각 행렬의 i열은 위 입력 데이터의 i번째 줄의 데이터를 의미합니다. 자신의 데이터 사이의 거리는 1이며 자신에게 가까운 값일수록 1에 가깝고 멀어질수록 0으로 수렴하고 있는 것을 보실 수 있습니다. 위 데이터를 기준으로 본다면 0.5 이상의 값은 1로, 0.5 이해의 값은 0으로 한다면 위에서 설명하였던 이상적인 Affinity Matrix가 그려지는 것을 알 수 있습니다.

 위와 같이 주어진 Affinity Matrix를 사용하여 Spectral Clustering을 구현해봅시다. Spectral Clustering을 구현함에 있어서의 기준은 다음과 같습니다.

1. 같은 Cluster 내의 요소끼리의 유사도는 큰 값을 갖는다.

2. 다른 Cluster에 속한 요소끼리의 유사도는 작은 값을 갖는다.

 이를 구하기 위해서는 위에서 구한 Affinity Matrix 값 W의 값이 최대로 나오는 Vector 행렬을 구해야 합니다. W와 행렬곱을 하였을 때 최대값이 나오게 하는 벡터를 고유벡터(eigenvector)라 칭합니다. 고유벡터에 대해 알기 위해서는 대학 학부 수준의 선형대수에 대한 기초적인 지식이 있어야 이해할 수 있습니다. 고유벡터에 대해 자세히 알고 싶으신 분은 아래의 블로그 포스팅을 참조하시면 이해하는 데에 도움이 될 것입니다.

고유값과 고유벡터[다크 프로그래머]

http://darkpgmr.tistory.com/105

 Affinity Matrix 값 W의 고유벡터를 구하면 아래와 같은 값이 도출됩니다. 

 고유벡터의 열(Column) 부분을 보시면 값이 서로 구분되고 있는 것을 보실 수 있습니다. 일반적으로 1번째 Column은 구분이 모호하기 때문에 2번째 Column부터 사용하게 됩니다.

  k 개의 그룹 cluster가 존재할 때 이들을 분별하기 위해서는 Affinity Matrix의 고유벡터의 2번째부터 k번째 column 부분만 보고 분별을 하게 됩니다. 즉 위의 예제의 경우 3개의 cluster로 구분되고 있으니 2,3번째 column만 사용하면 되겠습니다. 이 경우 첫 번째 cluster인 (1,2) 그룹의 경우 (-0.5, -0.3)으로, (3,4) 그룹의 경우 ( 0, 0.5), (5,6) 그룹의 경우 (0.5, -0.3)으로 뚜렷이 구분되고 있음을 확인하실 수 있습니다. 이를 이미지로 표현하면 다음과 같다 볼 수 있겠습니다.

 위에서 보시는 바와 같이 각 그룹이 고유벡터 내의 성분대로 분류하면 뚜렷하게 분류가 되는 것을 확인하실 수 있습니다.

 고유벡터값을 토대로 Spectral Clustering을 구현하는 알고리즘으로는 Minimum Cut과 Normalized Cut을 사용하게 되는데요 위 알고리즘은 다음 포스팅에서 이어서 설명을 하도록 하겠습니다.

Spectral Cluster 알고리즘 응용(Minimum Cut)

http://elecs.tistory.com/169

- Reference

허경용, 김광백, 우영운 (2008), "스펙트럼 군집화에서 블록 대각 형태의 유사도 행렬 구성", 한국멀티미디어학회논문지, 11(9), 1302-1309.

http://www.dbpia.co.kr/Article/NODE01605020

※2020년 8월 5일 수정

기존의 유튜브 영상이 나오지 않아 새로운 영상으로 변경하였습니다.