트리의 순회


트리의 순회에는 3가지 방법이 존재한다.





1. 전위 순회


F->B->A->D->C->E->G->I->H


살펴보자면 Root 노드부터 왼쪽->오른쪽으로 탐색을 시작한다.


F를 방문 한 뒤, 왼쪽 자식인 B를 방문한다.

B의 왼쪽 자식인 A를 방문한 뒤, A는 자식이 없으므로 B의 오른쪽 자식 D를 방문한다.

D의 왼쪽 자식인 C를 방문 한 뒤, C는 자식이 없으므로 E로 넘어간다. E도 자식이 없으므로 

Root의 왼쪽 자식을 탐색한다.


2. 중위 순회


A->B->C->D->E->F->G->H->I


왼쪽 -> Root -> 오른쪽으로 탐색을 진행한다.


Root인 F의 왼쪽 자식인 B에는 또 왼쪽 자식이 존재하므로 A를 방문한다. 

A는 자식이 없으므로 A의 부모인 B를 방문. B의 오른쪽 자식인 D에는 왼쪽 자식 C가 존재한다.

C는 자식이 없으므로 C를 방문한 뒤, 부모인 D를 방문, 다음 E를 방문한다.

-반복


3. 후위 순회


A->C->E->D->B->H->I->G->F


왼쪽 -> 오른쪽 -> Root로 탐색을 진행한다.


귀찮다. 안적을래.



'Algorithm' 카테고리의 다른 글

자료구조. 최소힙, 최대힙, 힙정렬  (0) 2018.03.19
자료구조 트리. Tree  (0) 2018.02.21
자료구조. 스택(stack)과 큐(queue)  (0) 2018.02.20
자료구조. Linked List  (0) 2018.02.18
Horner's role  (0) 2017.03.15

CNN ( Convolution Neural Network )




합성곱을 사용한 신경망이다.



처리과정을 이미지로 확인해보자.


복잡해 보인다.


간략하게 설명을 하자면


Input으로 특정 이미지가 들어와서 Convolution Layer를 거쳐 Pooling Layer를 지난다. 


Convolution Layer, Pooling Layer를 Feature Map Cycle이라 생각 했다.


그 이유는 해당 Layer를 지나면 Feature를 탐색하기 때문인데.. 해당 과정에 대한 이해를 해보자.




Convolution Layer


Convolution = 합성 곱


뭐랑 뭐를 합성 곱 시키는가?

합성 곱을 하면 뭐가 되는가?


위의 질문에 대한 대답을 아래에 적을 건데.. 사실 다 이해를 못해서 나중에 추가적인 설명을 붙일 거다.


합성 곱은 Input Image 혹은 Pooling Layer를 거친 Data에 Filter(Weight)를 합성 곱을 시켜준다.


출처 : http://deeplearning.stanford.edu/wiki/index.php/Feature_extraction_using_convolution


하나의 Filter를 가지고 Image를 합성 곱 시켜주므로써 Feature를 찾아내는데 보통 Filter는 3*3, 4*4로 이루어진다.

( 물론 개발하는 사람의 마음대로 filter를 조절할 수 있지만 효과적인 filter는 3*3, 4*4라 알려져 있다. )


또한 하나의 Filter로는 하나의 Feature map밖에 나오지 않기에, Filter는 여러 개를 사용하여 여러 개의 Feature map을 만든다.


Stride라는 Hyper-Paramter가 존재하는데 Stride는 filter가 몇칸을 이동할지 결정해주는 paramter이다.

위의 이미지에서는 Stride가 1인 경우이고, Stride가 2라면 (0,0)을 시작으로 다음 칸은 (0,1)이 아닌 (0,2)에서 합성 곱을 진행하는 것이다.


Stride는 작을 수록 Feature map을 잘 만들 수 있을까 하는 의문이 든다. 한번 테스트 해봐야 할 것 같다.




Feature Map은 원본 이미지보다 크기가 작아지기 때문에 연산을 위해 원본 이미지의 크기에 맞춰 줘야한다.

원본 이미지 크기만큼 빈 공간을 0으로 채워주는데 이 과정을 Padding이라고 한다.


출처 : https://www.analyticsvidhya.com/blog/2016/04/deep-learning-computer-vision-introduction-convolution-neural-networks/





Pooling Layer


이 과정은 Feature를 강조하기 위해 만들어진 층인데 N*N 크기의 영역을 1*1 크기로 확 줄여버린다.

Pooling은 3가지 방법이 있는데 Max, Avg, Min 이 있다.

N*N 크기의 영역에서 가장 큰 값, 혹은 해당 영역의 평균 값, 가장 작은 값을 골라서 1*1 크기로 압축 시킨다.


출처 : https://stackoverflow.com/questions/44287965/trying-to-confirm-average-pooling-is-equal-to-dropping-high-frequency-fourier-co






위의 Layer가 Feature Map을 생성하는 과정이다.


Filter가 여러 개이므로 Feature Map도 여러 개가 나온다.


이제 여기서 Classification을 해야되는데, FC Layer를 이용한다.

( FC Layer(fully Connection Layer)는 Dense Layer라고 불리기도 한다. )


FC Layer(Dense Layer)를 거치면 최종 Output이 나오는데 이를 softmax 를 이용해 Classification 하면 된다.



트리. Tree


자료구조에서 트리는 나무를 거꾸로 표현한 것 처럼 생겼다고 해서 트리라고 이름이 지어졌다.


트리는 뿌리(root)인 노드를 Level 1로 지칭하며 시작하며 뿌리 노드를 기준으로

자식 노드를 연결시켜 가지처럼 뻗어나가는 구조이다.


트리는 여러가지 종류가 있는데 대표적으로 Binary Tree, Normal Tree가 있다.

여기서 Binary Tree는 탐색, 힙 등 광범위하게 사용된다.




배우기 전에 용어를 정리해보자.


Root, 뿌리.


뿌리(Root)는 트리의 최상위에 존재하는 노드이며 Level은 1로 고정이다.

위 Tree에서 시초가 되는 '2'노드가 Root, 뿌리 노드이다.

(위 그림에서 '2'노드가 두번 나오는데, 가장 상위에 있는게 뿌리 노드이다.)



Child, 자식


Child, 자식노드는 어떠한 노드에 종속되어 있는 노드로

뿌리 노드를 기준으로 자식노드는 '7', '5'노드이다.



Parant, 부모


Parant, 부모노드는 자기 자신 노드 아래에 자식 노드가 있다면

해당 노드는 부모 노드가 된다.

예를 들어 '9' 노드의 부모는 '5'이다.


* 같은 부모를 가진 노드의 집합을 형제 노드라고도 칭한다.


Degree, 차수


Degree, 차수는 해당 노드에 연결된 자식 노드의 개수를 뜻한다.

트리에서 가장 큰 차수가 트리의 차수가 된다.



Level(Depth), 깊이, 레벨


Level, 혹은 Depth은 트리의 깊이 혹은 레벨을 뜻 한다.

위 그림에서는 최대 4 Level 혹은 4 Depth을 가지고 있다. 

트리의 최상 지점부터 1Level, 1 Depth으로 시작한다.


Height, 높이


트리에서 최대 Level 혹은 Depth을 의미한다.

해당 트리는 4의 높이를 가진다.


'Algorithm' 카테고리의 다른 글

자료구조. 최소힙, 최대힙, 힙정렬  (0) 2018.03.19
자료구조. 순회(전위 중위 후위)  (0) 2018.03.19
자료구조. 스택(stack)과 큐(queue)  (0) 2018.02.20
자료구조. Linked List  (0) 2018.02.18
Horner's role  (0) 2017.03.15

+ Recent posts