Bilinear map(쌍선형사상, 겹선형사상)

공대생의 팁 2018.04.28 16:01

 Bilinear map(쌍선형사상, 겹선형사상)이란 2개의 vector space(선형 사상)에서 또다른 세 번째 vector space를 만들기 위해 결합하는 함수이다.


 A,B,C를 아벨군(abelian group, 가환군:곱셈의 교환법칙이 성립하는 군)이고 A×B를 곱집합(cartesian product group)이라 하였을 때,  A와 B의 곱집합인 C로의 bilinear map은 다음과 같이 나타낼 수 있다.



  : A×B→C


 위의 bilinear map 함수는 아래와 같은 관계를 만족한다.



 일 때










출저 : https://ncatlab.org/nlab/show/bilinear+map

Borel set(보렐 집합)

공대생의 팁 2018.03.10 00:47

 Borel set(보렐 집합)에 대해 자세히 알기 위해서는 σ-algebra(시그마 대수)에 대한 개념을 정확히 알아야 할 필요가 있습니다. σ-algebra(시그마 대수)에 대한 내용은 아래 글을 참고해 주시길 바랍니다.


http://elecs.tistory.com/253


 Open set을 포함한 실수 R의 부분집합의 모든 σ-algebra(시그마 대수)의 교집합을 Borel σ-algebra라 합니다. 그리고 이러한 Borel σ-algebra를 모은 집합을 Borel set(보렐 집합)이라 합니다. Borel σ-algebra는 전체 Open set을 포함하는 모든 σ-algebra를 포함하고 있습니다. 즉 Boral set은 가산집합(measurable)이라 할 수 있습니다.


Theorem. The collection M of measurable sets is a σ-algebra that contains the σ-algebra B of Borel sets. Each interval, each open set, each closed set, each set, and each set is measurable


이때 는 Open sets의 countable collection의 교집합이고, 는 Closed sets의 countable collection의 합집합이다.



참고 문헌 :  H.L. Royden, 2010, 『Real Analysis』, 4th edition.

σ-algebra(sigma algebra, 시그마 대수)

공대생의 팁 2018.03.07 23:47


 σ-algebra(시그마 대수 또는 σ-field)는 결과에 대한 부분적인 지식 상태의 수학적 모델입니다.


 확률공간(Ω,Σ,P)가 있을 때 집합 Ω를 "확률 실험"의 가능한 결과의 집합아라고 할 수 있습니다. 수학적으로 Ω를 하나의 집합으로, ω를 원소로서 이를 "sample space"라 합니다.


 예를 들어 Σ가 σ-algebra(시그마 대수)이고, A∈Ω일 때 ω∈A인지 아닌지에 상관없이 A∈Σ 라고 할 수 있습니다.


 집합족 F가 아래의 조건을 만족할 경우 반환(semiring)이라 합니다.

 •Φ∈F.(Φ는 공집합)

 •If A, B∈F, then A ∩ B∈F.

 •If A, B∈F, then there exists a collection of sets , such that .

 (A\B all elements of A not in B)


 집합족 F가 아래의 조건을 만족할 경우 대수(algebra)이라 합니다.

 •Φ∈F.

 •If  , then  (F is closed under complementation).

 •If , then  (F is closed under finite unions).


 σ-algebra(시그마 대수) F가 아래의 조건과 같을 경우 Ω의 부분집합 ω의 집합이라 합니다.

 •Φ∈F.

 • If , then 

 • If , then .


 위의 조건을 보았을 때 집합 E={{Φ},{a},{b},{c},{a,,b},{b,c},{a,c},{a,b,c}}는 대수(algebra)이면서  σ-algebra(시그마 대수)라 할 수 있겠습니다.


  σ-algebra(시그마 대수)는 대수의 부분집합으로서 모든  σ-algebra(시그마 대수)는 대수라 할 수 있으나 그 반대는 성립하지 않습니다.

 σ-algebra(시그마 대수)는 무한번이 아닌 가산번의 합집합과 교집합에서 성립한다. 즉 σ-algebra(시그마 대수)는 유한번의 합집합과 교집합에서 닫혀있음(closed under finite unions)을 알 수 있다.


참고자료 : http://hanmaths.tistory.com/36

Firefox에서 플러그인을 사용해 크로스도메인 문제 해결방법

공대생의 팁 2018.01.19 23:52


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


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


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


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


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


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



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



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



[선형대수]Dominant Eigenvalue

공대생의 팁 2018.01.18 14:52

 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(특이점)

공대생의 팁 2017.11.27 20:33

 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에서 특정한 변수만 최적화하는 방법(How to train particular variable in Tensorflow)

공대생의 팁 2017.11.26 16:15


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
y_ = tf.placeholder(tf.float32, shape=[None, 9])
y_add = tf.placeholder(tf.float32, shape=[None, 10])
 
# Output layer(first)
W_fc2 = tf.Variable(tf.truncated_normal([5009], stddev=0.1))
b_fc2 = tf.Variable(tf.constant(0.1, shape=[9]))
y_hat=tf.nn.softmax(tf.matmul(h_fc1, W_fc2) + b_fc2)
 
# Output layer(additional)
W_fc3 = tf.Variable(tf.truncated_normal([50010], stddev=0.1))
b_fc3 = tf.Variable(tf.constant(0.1, shape=[10]))
y_hat2=tf.nn.softmax(tf.matmul(h_fc1, W_fc3) + b_fc3)
 
# Train and Evaluate the Model
cross_entropy = - tf.reduce_sum(y_*tf.log(y_hat))
train_step = tf.train.AdamOptimizer(1e-4).minimize(cross_entropy)
 
# Addition layer train
cross_entropy2 = -tf.reduce_sum(y_add*tf.log(y_hat2))
add_train = tf.train.AdamOptimizer(1e-4).minimize(cross_entropy2, var_list=[W_fc3, b_fc3])
cs


 위 소스코드를 살펴보았을 때 두 개의 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 [] 형식으로 변수들을 입력해두면 해당 변수만 훈련되는 것을 직접 확인하실 수 있습니다.


PIXLR 사용시 텍스트(글자)입력 및 저장이 되지 않을 때

공대생의 팁 2016.09.18 22:35

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


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



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


http://www.pixlr.com



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


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


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



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



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



 


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




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


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

자신의 리눅스에 설치된 폰트(글꼴) 검색 및 확인하는 방법

공대생의 팁 2016.09.15 23:43

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


$ fc-list


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


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


$ fc-list :lang=ko


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


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


$ fc-list | grep "폰트명"


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

Windows 10에서 SSL이 적용된 사이트 접속이 되지 않을 때 해결방법

공대생의 팁 2016.02.29 23:32

 최신버전인 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키를 누릅니다.



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



  • 감사합니다 2016.08.10 10:15 ADDR 수정/삭제 답글

    감사합니다...덕분에 중요한 일이 있어서 처리했어야 하는데 사이트에 접속되지 않아서 고민하고 있다가 이 글을 보고 해결되었습니다...

    유익한 글 정말 감사드립니다!

  • dd 2016.11.17 10:43 ADDR 수정/삭제 답글

    정말 감사합니다ㅠㅠㅠㅠㅠㅠㅠㅠㅠ
    SSL을 체크해야 되는 거였군요. 큰 도움되었습니당

우분투 커널 업데이트 후 VirtualBox가 제대로 동작되지 않을 때 해결방법(버전 5.0.14 이후)

공대생의 팁 2016.01.21 16:44

 리눅스 환경에서 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 알고리즘 응용(Minimum Cut)

공대생의 팁 2016.01.01 23:56

 지난 포스팅에서 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 알고리즘에 대한 자세한 사항은 다음 포스팅에서 이어가도록 하겠습니다.

  • hakim 2016.04.14 00:11 ADDR 수정/삭제 답글

    정말 잘 읽었습니다.
    영어논문 읽으면서 공부하기 어려웠는데,
    이해가 정말 잘되었습니다!
    normalized 기대돼요!

  • 진도 2016.12.06 20:13 ADDR 수정/삭제 답글

    Normalized Cut 부탁드려요