[ 독후감 ] 코드 없는 알고리즘과 데이터 구조를 읽고..

📍 [ 독후감 ] 코드 없는 알고리즘과 데이터 구조를 읽고..

✏️ 서론

이 책은 한 줄의 코드도 사용하지 않고 그림과 간결한 문장을 통해 데이터 구조와 알고리즘을 다룬 책이다. 그렇기 때문에 타 개발 관련 서적보다 빠르게 읽을 수 있었다. 독서 기간은 23.3.10부터 23.3.20이고 총 224페이지다. 데이터 구조와 알고리즘의 기본적인 내용들을 나열한 책이기 때문에 기존에 알고 있던 내용을 리마인드 하자는 의도로 읽었다. 그중 기억에 남는 내용을 본론에 작성해보려고 한다.

✏️ 본론

군집화 알고리즘

군집화 알고리즘은 분류 시스템과 머신러닝 시스템에서 널리 사용되며, 이 책에서는 구현상의 수학적 세부 사항 없이 단순한 수학 개념만 사용하여 군집화 알고리즘의 원리를 살펴본다. K-평균(K-means) 알고리즘은 인공지능과 머신러닝에 대한 관심이 높아지는 요즘 주목받고 있는 중요한 알고리즘이다.

 

데이터 구조의 특정 속성(예를 들면 이질성)을 사용하여 데이터를 분류하는 *그래프 군집화(graph clustering)에 사용된다. (여기서 말하는 그래프는 데이터 구조가 아니라, n차원 좌표계를 뜻한다.) 이때 데이터를 분류하여 관련된 요소끼리 묶는 동작을 군집화(clustering)라고 한다.

 

K-평균 알고리즘을 이해하려면 데이터 군집의 유형을 나누는 방법을 알 필요가 있다. 데이터 군집화의 두 가지 종류로 계층형(hierarchical) 군집화와 분할형(partitioning) 군집화가 있다. 그림 9-1은 계층형 군집화의 예를 보여준다. (실전에서의 계층형 군집화 다이어그램은 일반적으로 이보다 더 복잡하다.)

 

 

문자로 표시된 각 노드는 하나의 데이터 요소를 뜻한다. 그리고 다이어그램에서 유사한 노드들은 원으로 묶여 있다. 계층형 군집 내 노드들은 유사한 데이터 집단 사이의 관계를 보여준다. 다음 예는 분할형 군집화이다.

 

 

K-평균 알고리즘은 센트로이드(centroid)라는 분할형 군집의 중심점을 할당한다. 각 노드는 가장 인접한 센트로이드를 중심으로 군집을 형성한다. 따라서 프로그래밍 언어나 유사 코드로 K-평균 알고리즘을 구현할 때는 알고리즘이 처리할 군집의 개수인 K값을 미리 지정해야 한다.

 

728x90

K-평균 알고리즘

K-평균 알고리즘은 일반적으로 센트로이드를 무작위로 선택한다. 그리고 비슷한 데이터끼리 얼마나 가까이 있는지를 판단하는 개념인 유클리드 거리(euclidean distance)라는 수학적 속성에 근거하여 센트로이드에 인접한 노드들을 군집의 요소로 선택한다. 지금부터는 알고리즘을 단계별로 실행해가며 동작을 이해해 보자. K값을 2로 설정(K=2)하고, 그림 9-4와 같이 그래프에 데이터 요소가 있다고 가정한다.

 

 

이 그래프에는 2개의 센트로이드가 있으며 하나는 삼각형, 다른 하나는 사각형으로 표시한다. K-평균 알고리즘은 삼각형 덴트로이드에 더 가까운 데이터 요소와 사각형 센트로이드에 더 가까운 데이터 요소를 결정한다. 이를 위해 알고리즘은 각 데이터 요소의 유클리드 거리를 계산한다. 그 결과 그림9-5와 같이 가상의 선을 기준으로 그래프를 분할할 수 있다. 선의 위쪽에 위치한 모든 데이터 요소는 사각형 센트로이드에 더 가깝고, 선의 오른쪽에 위치한 모든 데이터 요소는 삼각형 센트로이드에 더 가깝다.

 

 

센트로이드에 데이터 요소를 할당하고 나면 할당된 데이터 요소 중심으로 센트로이드의 위치를 다시 계산한다. 결과적으로 센트로이드는 그림 9-6과 같이 각 군집에 속한 모든 데이터요소의 '평균'위치로 재설정된다.

 

 

센트로이드를 재설정하고 나면 새로운 위치를 기준으로 앞의 과정을 반복한다. 이는 센트로이드가 더 이상 이동하지 않을 때까지 수행된다. 즉, K-평균 알고리즘은 n차원 좌표계에서 유클리드 거리를 기반으로 K개의 평균을 찾는 알고리즘이다. (참고로 K-평균 알고리즘은 분류 시스템뿐 아니라, 머신러닝의 비지도 학습(unsupervised learning)시스템에서도 사용된다는 것을 기억하자.)

 

K-최근접 이웃 알고리즘

K-최근접 이웃 (K-nearest neighbor, KNN)알고리즘은 최신 컴퓨터 과학의 강력한 도구이며, 특히 머신러닝에서 중요한 역할을 한다. 보통 데이터를 분류하는 능력이 뛰어나다고 알려져 있다. 지금부터 한 가지 예를 통해 복잡한 수학적 개념 없이 K-최근접 이웃 알고리즘을 간략히 설명한다. 도형을 원형 또는 사각형으로 분류하는 분류 시스템을 상상해 보자. 그림 9-7과 같이 도형 데이터 요소를 그래프에 배치한다. 모양에 따라 그래프상의 위치가 구분된 것을 확인할 수 있다.

 

 

그림 9-8과 같이 새로운 도형 하나를 그래프에 추가해보자.

 

 

새로운 도형이 사각형인지 원형인지 어떻게 결정할 수 있을까? K-최근접 이웃 알고리즘에서 K값은 분류 과정에서 고려할 최근접 이웃의 개수다. 여기에서는 일단 K값이 5라고 가정하자. K=5이므로 새로운 도형의 모양은 그림 9-9와 같이 최근접 이웃 5개를 고려해서 정해준다.

 

 

K값이 5인 분류 과정에서는 3개의 사각형과 2개의 원형이 새로운 도형의 최근접 이웃이다. 최근접 이웃 5개 중 절반을 넘는 3개가 사각형이므로 새로운 도형은 사각형으로 분류된다. 이것이 K-최근접 이웃 알고리즘이 분류를 수행하는 방법이다.

✏️ 결론

본론에서 설명한 군집화 알고리즘 이외에도 하드웨어 관련 내용(회로, 트랜지스터, 논리 게이트 등..)과 스케줄링 알고리즘(인터럽트와 서비스 루틴, 작업 제어 블록, 커널, 프로세스 등..)도 설명해주고 있었다.

 

흐려져가던 알고리즘의 기억을 오랜만에 상기할 수 있도록 도와준 책이었다. 데이터 구조와 알고리즘을 간략하게 훑어보거나, 기술면접을 준비하거나, CS지식에 입문하고 싶은 분들에게 추천해주고 싶은 책이다.