기계 학습에 사용되는 데이터 구조가 다른 소프트웨어 개발 영역에서 사용되는 구조와 크게 다르지 않다. 그러나 많은 문제의 크기와 난이도 때문에 기본에 대한 확실한 이해가 필요하고, 기계 학습은 매우 수학적 분야이기 때문에 데이터 구조를 사용하여 수학적 문제를 해결하는 방법을 고민해야 할 경우가 많은 것 같다.
자주 고민하는 문제가 아니기에 기본적인 자료구조에 대해 정리해본다.
1. Array(배열)
배열이 기계 학습에서 가장 중요한 데이터 구조라고 말할 수 있다. 배열은 가장 유용하고 강력한 수학적 도구인 선형대수에 사용되기 때문이다. 가장 일반적인 유형은 벡터 및 행렬에 해당하는 1 차원 및 2 차원 구조지만, 때때로 3 차원 또는 4 차원 같은 다차원 배열을 사용하는 경우가 많다.
기계학습에서 행렬 연산을 위해서는 다양한 라이브러리와 데이터 유형 그리고 언어들 중 사용할 도구를 선택해야한다. Matlab, IDL(Interactive Data Language) 및 Numpy 확장이있는 Python과 같은 많은 프로그래밍 언어는 주로 벡터와 행렬 연산을 위해 설계되었다.
배열은 실제 데이터의 값과, 배열에 할당된 공간의 크기 그리고 배열이 데이터를 저장하고 있는 실제 크기를 갖는다. 배열의 실제 크기가 할당된 공간의 크기를 넘어가면 새로운 공간(기존X2)이 새로 할당되지만 원래 저장된 데이터는 삭제된다. 하지만 배열은 데이터 저장 속도가 빠르고 매우 유연한 데이터 구조이다.
2. Linked List
Linked List는 개별적인 저장 공간을 갖는 여러 노드로 구성된다. 각 노드는 데이터 값과 다음 노드에 대한 포인터 값을 갖는다. Linked List는 쉽게 데이터를 연결하거나 분리할 수 있으며, 새로운 노드는 머리 또는 꼬리에 추가할 수 있는 유연한 데이터 구조를 갖는다.
하지만 원하는 값을 찾기 위해 많은 노드를 검색해야하기 때문에 속도가 느리다는 단점을 가진다. Linked List는 주로 길이가 가변적인 목록이 필요한 경우에 사용하지만 Access 속도가 느린 단점때문에 List가 완성되면 고정길이의 배열로 변환하여 사용하는게 일반적이다.
3. Binary Tree(이진트리)
Binary Tree는 Linked List와 유사한 데이터 구조이다. 차이점은 앞의 노드가 2개의 뒷 노드에 대한 포인터 값을 갖기 때문에 Tree 구조를 갖는다는 것이다. Parent(부모)와 Child(자식) 노드로 구성되며, 자식노드의 값은 부모노드의 값 보다 항상 작다. 또한 같은 자식노드라면 왼쪽의 자식노드가 오른쪽의 자식노드 보다 작은 값을 갖는다.
Binary Tree 역시 배열로 변환이 가능하며, 노드 정렬을 위해 사용된다.
4. Heap
Heap은 List(Tree)와 다르게 수평적 순서가 아닌 수직적 순서를 갖는 계층적 데이터 구조이다. 부모는 항상 두 자식보다 큰 값을 갖는다. 수직적인 데이터 구조이기 때문에 새로운 요소를 추가하거나, 기존 요소를 삭제하게 되면 다른 요소와의 순위 비교를 통해 전체 구조가 변경된다.
트리 구조와 달리 대부분의 힙은 단순히 암시적 요소간의 관계로 배열에 저장된다.
5. Stack(스택)
FILO(First in, Last Out) 가 특징인 데이터 수직 구조다. 즉 새로운 요소는 기존의 요소 위에 쌓이고, 제거 시 가장 최 상위의 요소가 제거된다. 즉 스택 내 데이터는 가장 최근에 싸인 요소가 제거되는 특징이 있다. 따라서 스택 내 다른 요소에 Access하기 위해서는 위 요소들을 Pop off 해야 한다.
6. Queue(큐)
FIFO(First in, First Out) 가 특징인 데이터 수직 구조이며, 요소의 추가는 스택과 동일하나 데이터 접근은 큐에 가장 먼저 쌓인 요소부터 가능한 특징을 가진다. (실시간 프로그래밍에서 많이 사용하는 자료구조임)
7. Set(집합)
집합은 요소 간 순서가 없고, 중복되지 않는 데이터 집합 구조이다. 즉 집합 내 존재하는 요소를 추가할 경우 기존 집합은 변경되지 않는다. (기계학습에서 주로 다루는 자료구조임)
8. Associative Arrays (Key-Value 쌍 배열)
키와 값을 쌍으로 만든 요소들의 관계형 데이터 구조이다. 값은 키를 통해서만 접근가능한 특징이 있다. 순서가 필요없는 데이터 집합의 경우 Associative Arrays로 구성해서 사용하는 경우가 많은데, 구조 자체가 1차원의 배열이기 때문에 주로 다차원 배열을 데이터 구조로 사용하는 기계학습에서는 잘 사용하지 않는 듯 하다.
이외에도 다양한 자료구조가 있지만 기본 개념을 정리하는 것으로는 이정도면 될 것 같다.
