최근 개인 용도로 간단하게 정보를 조회하는 사이트를 구축하고 있었습니다만 희안하게도 특정 주소로 JSON을 사용해 값을 얻으려 하면 계속 에러가나 나오는 문제를 계속 겪고 있었습니다. 대체 다른 사이트에서는 잘 되던 JSON이 왜 특정 사이트에서는 되지 않는 것일까요?

 생각보다 답은 간단했습니다. 최근 거의 대부분의 브라우저는 크로스도메인(Cross domain) 정책으로 정보를 불러오는 사이트와 정보를 보내는 사이트의 주소가 다를 경우 이를 차단하는 방식입니다. 즉, 크로스도메인 문제가 생길 경우 상대의 사이트에서 JSON을 비롯한 대체적인 정보를 수신할 수 없는 상황이 벌어지는 것입니다.

 개발자의 입장에서는 이를 해결하기 위해 ajax등을 사용하여 이 문제를 해결하는 방법이 있습니다. 그러나 이를 구현하려면 서버 부분도 함께 문제를 해결해야 하기 때문에 저같이 간단한 사이트를 만드는 경우에는 그다지 좋은 방법은 아닐것입니다.

 단지 개인 목적의 사이트를 개발하고 있는데 크로스도메인 문제로 인해 원하는 결과를 얻지 못하는 분들이라면 브라우저에서 제공하는 플러그인을 통해 이를 해결할 수 있습니다.

 Firefox에서는 이 이슈를 해결할 수 있도록 크로스도메인 기능을 제한하는 플러그인을 사용하실 수 있습니다.

https://addons.mozilla.org/ko/firefox/addon/cross-domain-cors/?src=search

 이 플러그인을 설치하면 Firefox 브라우저 우측 상단에 아래와 같이 아이콘이 생성됩니다.

 이 아이콘을 클릭하면 크로스도메인 관련 기능이 제한되어 JSON등 외부 사이트를 통해 자료를 얻어올 수 있게 됩니다.

 Dominant eigenvalue란 대각행렬(Diagonal Matrix)에서 나타나는 eigenvalues(고유값들)중 가장 큰 값, 즉 eigenvecotr에서 가장 큰 영향을 주는 벡터의 고유값을 의미한다고 볼 수 있습니다.

 Markov chain에서 Diagonal matrix를 n회 곱하게 되는데 diagonal matrix D의 dominant eigenvalue인 λ1가 1일 경우 나머지 eigenvalue는 1보다 작으며 n을 무한번 곱하게 되면 λ1을 제외한 모든 eigen value의 값은 0에 수렴하게 된다.

출저 : Steven J.Leon, Linear Algebra with Applications, Pearson, 2015

 Regular Point에 대해 알기 위해서는 Singular Point에 대해 제대로 알아야 할 필요가 있습니다.

EX) 미분방정식 x' = f(x), 그리고 이 식과 연계된 dynamical system φ(t,x)가 위상공간 Ω 상에 존재할 때 Point x에 대해 나타내고자 할 때

Singular Point - x ∈ Ω이고 f(x) = 0일 때 모든 t ∈ R 일 때 φ(t,x) = x인 점

Regular Point - x ∈ Ω이고 해당 x가 Singular Point에 포함되지 않을 때

 즉, Regular Point는 특정한 공간 내에서 특정한 점을 나타내는 특이점(Singular point)를 제외한 모든 점이라는 것을 알 수 있습니다. 위의 조건을 통해 아래의 예제를 알 수 있습니다.

EX) 기울기 벡터 ∇h1(x*), ... ,∇hm(x*) 가 linearly independent(선형 독립)일 때, h1(x*)=0, ... , hm(x*)=0를 만족하는 x*는 regular point이다.

 이는 x*가 각 함수를 0으로 만들지만 각 함수의 미분함수인 기울기 벡터의 값이 각 함수의 값에 영향을 주고 있지 않기 때문에 해당 구간을 regular point라고 말할 수 있는 것입니다.

 최근 Tensorflow를 공부하면서 강화학습을 공부하고 있습니다. 오랜만에 Python을 다루는 것이기도 하며 인공신경망 기반의 인공지능도 구현할 수 있어 간단한 인공지능도 구현해보기도 합니다.

 이번 포스팅에서는 train을 하는 과정에서 특정한 변수만을 사용하여 조건을 minimize 하는 방법에 대해 알아보도록 하겠습니다.

 다음은 특정 Neural Network의 Output을 구현하는 과정을 나타낸 것입니다. 첫 번째 Output에서는 모든 Variable들을 훈련시키고 이후 새로운 Output을 구현하여 해당 Output layer만 minimize를 적용해보는 과정을 살펴볼 것입니다.

 위 소스코드를 살펴보았을 때 두 개의 cross_entropy를 구현하였습니다. 첫 번째 output layer는 구현된 Neural Network 전체를 대상으로 최적화를 수행함으로 Optimizer 함수에서 cross_entropy를 변수로 하여 값을 구현합니다.

 다음으로 구현되는 cross_entropy2는 새로운 Output layer를 구현하여 기존의 output layer를 대체하게 됩니다. 이 때 기존에 구현된 Neural Network는 그대로 사용한 채 새로운 Output layer를 대상으로 Minimize를 수행하고자 합니다. 이 Optimizer 함수에서 cross_entropy2 변수 뿐 아니라 var_list 변수에 특정 변수만 최적화 시킬 수 있도록 설정할 수 있습니다. 이 때 해당 변수명을 list [] 형식으로 변수들을 입력해두면 해당 변수만 훈련되는 것을 직접 확인하실 수 있습니다.

 자신이 직접 찍은 사진이나 인터넷에 짤을 올리기 위해 여러분들께서는 어떤 프로그램을 사용하여 이미지를 편집하시나요? 흔히 뽀샵질이라 부르는 Adobe사의 '포토샵'을 사용하여 이미지를 편집하시는 분들 계시리라 생각됩니다.

 하지만 포토샵은 상업용 소프트웨어이기 때문에 개인이 사용하기엔 너무나 많은 비용이 필요한데다 이미지 보정용으로 쓰기엔 포토샵은 너무나 많은 기능을 가지고 있기 때문에 가성비를 따졌을 때에도 터무니없이 비싼 도구입니다. 특히 최신 버전의 포토샵은 2016년 9월 기준 한달에 5만원이라는 많은 비용이 들어갑니다.

 그렇다면 우리들같이 포토샵의 기본 기능만 쓰는 사람들도 피눈물을 흘려가며 포토샵을 구매해야 하는 걸까요? Forutnately, 흔히 AutoCAD로 잘 알려진 Autodesk사에서 Web기반의 이미지 에디터인 PIXLR을 무료로 제공하고 있습니다. 사용 방법은 단지 자신의 컴퓨터에 설치된 웹브라우저와 최신 버전의 flash player만 설치되면 누구나 사용할 수 있다는 점이지요. 아래 주소만 기억하신다면 포토샵에서 사용하던 기능들을 충분히 활용할 수 있습니다.

http://www.pixlr.com

  이런 편리하고 합리적인 PIXLR을 사용하던 도중 몇몇분들의 경우 다음과 같은 이상현상이 발생하는 경우가 있는 것으로 보입니다.

1. Text 입력이 되지 않는다.

 PIXLR에서도 너무나 당연하게도 텍스트 입력을 지원합니다. 'A'로 표시된 버튼을 눌러 텍스트 레이어를 추가할 수 있으나 몇몇 브라우저의 경우 아래와 같이 그저 빈 화면만 나타나는 경우가 있습니다.

  위 화면에서 보시는 바와 같이 오른쪽에 레이어들이 계속 추가됨을 볼 수 있으나 텍스트를 입력할 수 있는 창이 전허 나타나지 않아 텍스트를 입력할 수 있는 시도조차 하지 못합니다.

  심지어 저장을 시도하려 해도 위와 같은 경고창만 연속으로 보일 뿐 저장조차 되지 않는 현상이 지속됩니다.

 위와 같은 현상이 발생되는 가장 근본적인 이유는 자신의 웹브라우저가 Private 모드를 사용하는 경우 입니다. 이 모드에서는 PIXLR이 제대로 지원되지 않는 현상이 나타나고 있으며 이를 해결하기 위해 브라우저를 일반 모드로 접속하거나 자신의 브라우저 설정에서 Private 모드를 기본모드에서 해제해주셔야 합니다.

브라우저의 일반 모드를 통하 PIXLR에 접속하면 위에서 보시는 바와 같이 텍스트를 설정할 수 있는 창이 나타납니다.

 또한 일반모드에서는 위에서 보시는 바와 같이 저장 또한 문제없이 순조롭게 진행됨을 확인하실 수 있습니다.

 새로운 폰트를 설치하신 후 리눅스(혹은 우분투)에 설치된 폰트가 제대로 적용되었는지 확인해 보기 위해 다음과 같은 명령어를 입력해줍니다.

$ fc-list

 제 컴퓨터의 환경에서 위의 명령어를 입력시 다음과 같은 결과가 나타납니다.

 만약 자신이 새로 설치한 한글 폰트를 찾는 경우 다음과 같이 명령어를 입력해주시면 됩니다.

$ fc-list :lang=ko

 위 명령어를 입력시 아래와 같이 한글 글꼴만 표시되는 것을 확인하실 수 있습니다.

 만약 자신이 찾고자 하는 폰트가 있는 경우 다음과 같이 검색을 할 수 있습니다.

$ fc-list | grep "폰트명"

 위 화면은 "$ fc-list | grep 바탕"으로 명령어 입력시 나타나는 결과입니다. 위 과정을 통해 자신의 컴퓨터에 설치된 글꼴을 알아보도록 합시다!

 최신버전인 Windows 10을 사용할 때 마다 Windows 7에서 발전된 기능들이 신기하면서도 바로 익숙해질 수 있어 참 좋습니다. 다만, 국내의 인터넷 환경에서는 아직까지도 Windows 10에서는 접속이 원활하지 않는 사이트들이 종종 등장합니다. 특히 기존 SSL 보안 방식을 적용하는 사이트들의 경우 메인 페이지 조차 뜨지 못하는 모양입니다.

 운전면허를 발급할 일이 있어 도로교통공단 홈페이지 'e-운전면허(http://dls.koroad.or.kr)'에 접속하였더니 아래와 같은 화면이 저를 반겨주고 있는 것입니다.

 최신 버전의 Chorme의 경우 SSL이 적용된 페이지에 접속되지 않고 위와 같이 에러 화면이 나타납니다.

"해당 웹페이지를 사용할 수 없음" "ERR_SSL_VERSION_OR_CIPHER_MISMATCH"

 물론 최신 버전의 파이어폭스에서 또한 이와 유사한 화면을 만나볼 수 있습니다.

"연결이 안전하지 않음" "ssl_error_no_cypher_overlap"

 그렇다면 과연 Internet Explorer로는 메인 페이지라도 확인할 수 있을까요?

 "이 페이지를 표시할 수 없습니다." "[고급] 설정에서 TLS 1.0, TLS 1.1 및 TLS 1.2를 켠 다음 다시 연결해 보십시오. 이 오류가 지속되면 이 사이트에서 지원되지 않는 프로토콜을 사용하는 것일 수 있습니다. 사이트 관리자에게 문의하십시오.

 최신 버전의 Internet Explorer에서 또한 일반 설정으로는 SSL 보안이 적용되어 있는 페이지를 바로 보실 수 없습니다. Windows 10에서 부터는 SSL 보안이 적용된 웹페이지에 접속하기 위해서는 설정을 변경해야 할 필요가 있습니다.

 먼저 설정 버튼(톱니바퀴)를 클릭하신 후, 인터넷옵션(O)를 클릭합니다.

 '고급'탭을 선택하신 후 'SSL 2.0 사용' 또는 'SSL 3.0 사용'을 체크하신 후 새로고침 버튼을 누르거나 F5키를 누릅니다.

 설정이 제대로 되었다면 아래와 같이 메인 페이지가 웹브라우저에 나타나는 것을 확인하실 수 있습니다.

 리눅스 환경에서 VirtualBox를 사용할 때 가장 불편한 점 중 하나는 리눅스 커널 이미지를 업데이트할 때 마다 VirtualBox를 다시 컴파일 해야 하는 경우이지요. 그런데 업데이트를 하던 도중에도 종종 VirtualBox를 실행한 후 경고문으로 나오는 명령어를 입력해도 컴파일이 진행되지 않는 경우가 종종 발생합니다.

 이전 포스팅에서 기존의 명령어로 컴파일이 수행되지 않을 때 해결방법으로 제시하였던 명령어가 아래와 같았습니다.

# sudo /sbin/rcvboxdrv setup

그런데 이번에는 아래와 같은 에러가 나타나는 것을 보았습니다.

 위와 같이 나올 경우 아래의 명령어를 입력하시면 해결하실 수 있습니다.

$ sudo /usr/lib/virtualbox/vboxdrv.sh setup

위 명령어를 수행한 후 VirtualBox가 정상적으로 동작하는 것을 확인하실 수 있습니다.

출저 : http://unix.stackexchange.com/questions/255519/virtualbox-kernel-module-installing-issue

 지난 포스팅에서 Spectral Clustering Algorithm(스펙트럼 군집화 알고리즘)의 정의와 원리에 대해 설명을 하였습니다. 이번 포스팅에서는 Spectral Cluster로 분류된 그래프 자료를 통해 각각의 집단 그룹으로 나누어주는 알고리즘인 Minimum cut에 대해 알아보도록 하겠습니다.

 본 포스팅에서는 이전 포스팅에서 설명하였던 Spectral Clustering 알고리즘을 숙지하고 이를 통해 구하게 되는 유사도 행렬(Affinity Matrix)를 알고 있다는 전제하에 설명할 것입니다. Spectral Clustering에 대해 자세히 알고자 하시는 분께서는 아래 포스팅을 참고해 주시길 바랍니다.

Spectral Clustering Algorithm(스펙트럼 군집화 알고리즘)

http://elecs.tistory.com/167

 지난 포스팅에서 다루었던 각 Cluster 그래프를 한 번 더 보도록 합시다.

 위 그래프는 같은 Cluster에 속한 데이터끼리는 굵은 선으로, 서로 다른 Cluser에 속한 데이터끼리는 가느다란 선으로 표시되어 있습니다. 위 데이터를 Spectral Clustering을 통해 Affinity Matrix로 각 데이터 사이의 유사값을 구함으로서 각 Cluster가 서로 구분될 수 있도록 수치화 하였습니다.

 각 데이터간의 유사도를 표현한 Affinity Matrix를 가지고 위 데이터를 명확하게 나눌 수 있는 방법은 존재할까요? Minimum cut 알고리즘은 주어진 데이터 사이의 유사도 값 중 가장 작은 값으로 각 Cluster 그룹을 나누어주는 기능을 합니다. 위의 그래프를 보았을 때 가느다란 선으로 연결된 데이터 사이를 나누게 되면 각 그룹이 뚜렷다게 구분되는 것을 보실 수 있습니다.

 예시를 통해 자세히 알아보도록 하겠습니다. 아래는 데이터 사이의 선분 vertex 사이에 유사값을 부여한 그래프입니다.

 직관상으로 보았을 때 Minimum cut 알고리즘을 적용하게 된다면 유사도 1과 2로 되어있는 부분을 나누면 두 개의 Cluster로 분별될 수 있다는 것을 직감하실 수 있습니다. 아래는 위의 그림에 Minimum cut을 적용한 그림입니다.

 위 그림대로 각 Cluster 사이의 vertex를 자름으로서 두 개의 Cluster로 분류된 것을 확인할 수 있습니다. 이를 식으로 구현하기 위해서는 어떻게 진행하게 될까요? Minimum Cut 알고리즘은 다음과 같은 해법을 제시합니다.

 아래 식에서 A와 B는 2개의 Cluster를 말하며, w는 Affinity Matrix(유사도 행렬)의 요소 중 하나입니다.

 위 식의 결과값은 두 cluster를 나눌 때 잘리는 부분의 유사값 w를 모두 합한 값입니다. 즉 결과값은 두 Cluster로 분리하기 위해 자르는 유사값의 총 합이 최소가 될 경우 위 식이 성립된다는 것을 알 수 있습니다.

 위 식을 증명하는 방법을 알아보겠습니다. 이전 포스팅(Spectral Clustering 알고리즘)에서 서로 다른 Cluster를 분류할 때 다음 두 조건을 만족해야 한다고 하였습니다.

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

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

 위 조건을 식으로 나타내면 다음과 같습니다.

 위의 식을 설명하자면 각 Cluster 그룹 A와 B에 속하는 affinity matrix 요소의 값을 모두 더한 후 A와 B 사이를 연결하는 affinity matrix 요소의 값을 모두 더한 값의 2배를 뺀 결과값이 최대가 되는 경우를 나타낸 것입니다. 위 식을 응용하면 아래와 같은 식을 만들 수 있습니다.

 위 식은 affinity matrix 내의 모든 값들을 더한 후 이를 위에서 구했던 식을 뺀 값이 최소가 되는 경우를 식으로 표현한 것입니다. 위 식이 maximum이 되는 값을 찾는 경우이므로 아래의 식은 minimum이 된다는 것을 유추할 수 있습니다.

 유도한 식을 구하기 위해 이를 실제 Affinity Matrix 행렬을 통해 설명해보겠습니다. 아래는 Affinity Matrix인 W를 나타냅니다.

 위의 모든 행렬요소의 값을 구합니다. 이는 아래의 과정을 나타내는 것입니다.

 다음으로 각 행렬 내에서 같은 Cluster 그룹에 속하는 요소들을 모두 더합니다.

위에서 붉은 색으로 강조한 부분을 모두 더합니다. 이는 아래의 과정을 나타낸 것입니다.

끝으로 각 행렬 내에서 다른 Cluster 그룹끼리 연결된 요소들의 값을 모두 더합니다.

 위에서 파란 색으로 강조한 부분을 모두 더합니다. 이는 아래의 과정을 나타낸 것입니다.

 위 과정의 계산을 모두 수행하게 되면 최종값은 붉은 색으로 강조한 부분이 빠지고 파란 색으로 강조한 부분이 두드러지게 됨을 알 수 있습니다. 즉, 각 Cluster 사이에서 cut 되는 부분에 해당되는 요소값이 남는다는 것을 알 수 있습니다. 즉 위의 식은 아래와 같은 원리의 값이 됨을 알 수 있습니다.

 그렇다면 주어진 Affinity Matrix 값을 사용하여 어떻게 최소값을 구할 수 있을까요? 이전 포스팅에서 설명드렸던 고유벡터를 사용하면 행렬의 minimum값을 구할 수 있습니다. 그럼 위 Affinity Matrix를 사용하여 고유벡터를 구하는 과정을 보겠습니다.

 위 식에서 주어진 각 값을 행렬 D와 W로 나누어봅니다. 이때 행렬 D는 대각행렬(Diagonal Matrix)로서 각 대각행렬의 행은 Affinity Matrix의 같은 행 내의 모든 값의 합을 나타냅니다. 아래는 이를 정의한 내용입니다.

 위에서 구한 행렬 (D-W) 행렬의 최소값은 아래의 식과 같이 고유벡터 x를 구함으로서 알 수 있습니다.

이 때 나오게 되는 고유벡터에서 2번째로 작은 고유벡터를 통해 Minimum Cut를 구할 수 있습니다. 이는 이전 포스팅에서 언급한 바와 같이 1번째로 작은 고유벡터를 사용할 경우 각 Cluster 그룹의 분리가 눈에 띄게 나타나지 않기 때문입니다.

 지금까지 Minimun Cut을 사용하여 Spectral Cluster 알고리즘을 나타내는 과정을 살펴보았습니다. 그런데 우리가 지금까지 언급하였던 Minimun Cut 알고리즘에는 단점이 하나 존재합니다. Minimum Cut의 경우 무조건 최소값을 찾는 과정을 거치기 때문에 우리들이 바라는 바와 같이 각 Cluster 그룹이 나누어지지 않는 경우가 발생하는데 아래는 그러한 사례 중 하나를 나타낸다.

 이상적인 방향으로 보았을 때 위의 경우처럼 다른 색깔로 분류된 Cluster 그룹끼리 나누어 지는 것이 맞으나 실제로는 이보다 더 작은 최소값을 갖고 있는 부분에서 나누어지는 것을 볼 수 있습니다. 이처럼 우리의 의도적으로 알고리즘이 적용되지 않는 이유는 Outliar와 같이 해당 cluster에서 다소 거리가 있는 부분에 있는 데이터가 있어 이 부분이 의도치않게 나누어져서 하나의 Cluster가 분류되지 않고 쪼개져 버리는 것을 보실 수 있습니다.

 이러한 Minimum Cut을 대체하게 된 것이 바로 Normalized Cut입니다. Normalized Cut 알고리즘에 대한 자세한 사항은 다음 포스팅에서 이어가도록 하겠습니다.

 오늘날은 인터넷을 통해 수많은 정보를 얻을 수 있는 빅데이터 시대에 도래하였습니다. 정보의 양이 매우 방대하다 보니 데이터 하나 하나 마다 개별로 의미를 찾아보기 보다는 전체 데이터의 특성을 분류하여 의미를 찾기 위해 사용되는 정교한 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일 수정

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

 리눅스를 사용하는 여러분들께서 최상단 폴더인 root 파일을 수정하실 때 어떻게 하시는지요? 가장 쉬운 방법으로 vi가 있을 것입니다. GUI가 없는 server 버전의 리눅스에서는 vi만이 거의 유일한 editor 수단으로 활용되고 있다고 봐도 무방할 정도로 vi는 linux 사용자에게 있어 뗄레야 뗄 수 없는 프로그램이지요. 하지만 vi의 최대 단점으로 일일히 단축 명령어를 이용해야 하다 보니 초보자가 사용하기에는 직관적이지 못해 사용하기가 상당히 불편하다는 점이 있습니다.

 물론 GUI 환경의 Desktop 버전을 사용하는 분이시라면 gedit라는 vi보다는 매우 편한 편집기가 있어 상당히 애용하다시피 하는데 막상 gedit로 루트 상단에 있는 파일을 수정할 수 없다는 치명적인 단점이 있습니다. 이 녀석을 마치 sudo 권한으로 root 상태에서 작업을 수행할 수 있다면 참 편할텐데 말이지요...

 정말 다행이게도 gedit를 root 권한을 사용하여 파일을 수정할 수 있는 방법이 존재합니다. 바로 gksu 명령어를 사용하는 방법입니다! 일반적으로 Terminal에서 root 권한을 얻어서 실행되는 프로그램의 경우 sudo를 사용합니다만 gui를 기반으로 하는 프로그램의 경우 gksu를 사용하면 마치 sudo와 같이 root 권한을 부여하여 root 파일을 수정할 수 있도록 권한이 설정됩니다.

$ gksu gedit &

 위와 같은 명령어를 수행하면 gedit를 root 모드에서 수행하는 것이 가능하여 최상단 / 에 있는 파일들을 자유롭게 수정할 수 있게 됩니다!

 리눅스(우분투) 운영체제에서 가상머신인 VirtualBox를 사용하다가 Kernel 업데이트 중 시스템 상에 영향을 주는 업데이트를 수행하게 되면 재부팅 이후 Virtualbox가 정상적으로 동작하지 않는 경우가 종종 발생합니다. 특히 아래와 같은 팝업과 동시에 아래의 명령어를 입력하라는 안내가 친절하게 뜨곤 하지요.

$sudo /sbin/vboxconfig

물론 위의 경우가 발생하였을 때 바로 Terminal을 실행한 후 명령어를 입력하면 리눅스 커널이 해당 부분을 다시 컴파일 하여 정상적으로 동작할 수 있도록 해줍니다. 그런데 VirtualBox가 5.08버전에서부터는 이 명령어를 입력해도 동작이 되지 않는 경우가 종종 발생합니다.

 VirtualBox 5.08 버전 이후의 경우 이러한 경우가 나타나는 것으로 알려져 있는데 이 경우 아래의 명령어를 입력하면 다시 말끔하게 해결할 수 있다.

$ sudo /sbin/rcvboxdrv setup