이번 글에서는 자료구조의 일종인 이진탐색트리(Binary Search Tree)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님, 그리고 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 기본으로 하되 중위순회 등 요소를 제가 추가하였습니다. 그럼 시작하겠습니다.

concepts

이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종입니다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐습니다.

예컨대 이진탐색의 경우 탐색에 소요되는 계산복잡성은 $O(\log{n})$으로 빠르지만 자료 입력, 삭제가 불가능합니다. 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 $O(1)$로 효율적이지만 탐색하는 데에는 $O(n)$의 계산복잡성이 발생합니다. 두 마리 토끼를 잡아보자는 것이 이진탐색트리의 목적입니다.

이진탐색트리는 다음과 같은 속성을 지니며 아래 그림과 같습니다.

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 중복된 노드가 없어야 한다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

이진탐색트리를 순회할 때는 중위순회(inorder) 방식을 씁니다. (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회) 이렇게 하면 이진탐색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있습니다. 다음 예시와 같습니다.

중위순회 : 1, 3, 5, 7, 8, 10

한편 트리 순회와 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

operations

이진탐색트리의 핵심 연산은 검색(retreive), 삽입(insert), 삭제(delete) 세 가지입니다. 이밖에 이진탐색트리 생성(create), 이진탐색트리 삭제(destroy), 해당 이진탐색트리가 비어 있는지 확인(isEmpty), 트리순회(tree traverse) 등의 연산이 있습니다. 파이썬 코드는 다음과 같습니다.

class Node:
    def __init__(self, val):
        self.val = val
        self.leftChild = None
        self.rightChild = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def setRoot(self, val):
        self.root = Node(val)

retreive/find

아래 이진탐색트리에서 10을 탐색(retreive, search)한다고 가정해 봅시다. 이진탐색트리는 부모노드가 왼쪽 자식노드보다 크거나 같고, 오른쪽 자식노드보다 작거나 같다는 점에 착안하면 효율적인 탐색이 가능합니다.

우선 루트노드(7)와 10을 비교합니다. 10은 7보다 큽니다. 따라서 왼쪽 서브트리(1, 3, 5)는 고려할 필요가 없습니다. 탐색공간이 대폭 줄어든다는 얘기입니다. 이번엔 오른쪽 서브트리의 루트노드(8)과 10을 비교합니다. 10은 8보다 큽니다. 따라서 오른쪽 서브트리의 루트노드(10)과 10을 비교합니다. 원하는 값을 찾았습니다.

요컨대 10을 탐색할 때 비교하는 값은 다음과 같습니다.

7, 8, 10

이번엔 4를 탐색해보겠습니다. 위와 같은 방식으로 4를 탐색할 때 비교하는 값은 다음과 같습니다.

7, 3, 5

하지만 5까지 비교했는데도 원하는 값(4)을 찾지 못했습니다. 그 다음은 5의 왼쪽 서브트리를 비교할 차례인데 5는 트리의 잎새노드(leaf node)여서 서브트리가 존재하지 않습니다. 이 경우 ‘값을 찾지 못했다’고 반환하고 탐색을 종료합니다.

이진탐색트리의 탐색 연산에 소요되는 계산복잡성은 트리의 높이(루트노드-잎새노드에 이르는 엣지 수의 최대값)가 $h$일 때 $O(h)$가 됩니다. 최악의 경우 잎새노드까지 탐색해야 하기 때문입니다. 이 때 $h$번 비교 연산을 수행합니다.

파이썬 코드는 다음과 같습니다.

    def find(self, val):
        if (self.findNode(self.root, val) is False):
            return False
        else:
            return True

    def findNode(self, currentNode, val):
        if (currentNode is None):
            return False
        elif (val == currentNode.val):
            return currentNode
        elif (val < currentNode.val):
            return self.findNode(currentNode.leftChild, val)
        else:
            return self.findNode(currentNode.rightChild, val)

insert

이번엔 삽입 연산을 살펴 보겠습니다. 새로운 데이터는 트리의 잎새노드에 붙입니다. 예컨대 탐색 예시에서 제시한 트리에 4를 추가한다고 가정해 봅시다. 아래와 같습니다.

그런데 위 트리에서 7과 3사이에 4를 추가해도 이진탐색트리의 속성이 깨지지 않음을 확인할 수 있습니다. 하지만 이진탐색트리가 커질 경우 이렇게 트리의 중간에 새 데이터를 삽입하게 되면 서브트리의 속성이 깨질 수 있기 때문에 삽입 연산은 반드시 잎새노드에서 이뤄지게 됩니다.

이진탐색트리의 가장 왼쪽 잎새노드는 해당 트리의 최소값, 제일 오른쪽 잎새노드는 최대값이 됩니다. 만약 위 트리에서 100을 추가하려고 한다면 제일 오른쪽 잎새노드의 오른쪽 자식노드를 만들고 여기에 붙이면 됩니다.

이진탐색트리의 삽입 연산에 소요되는 계산복잡성은 트리의 높이(루트노드-잎새노드에 이르는 엣지 수의 최대값)가 $h$일 때 $O(h)$가 됩니다. 삽입할 위치의 잎새노드까지 찾아 내려가는 데 $h$번 비교를 해야 하기 때문입니다. 물론 탐색 연산과 비교해 삽입이라는 계산이 추가되긴 하나, 연결리스트 삽입의 계산복잡성은 $O(1)$이므로 무시할 만한 수준입니다.

파이썬 코드는 다음과 같습니다.

    def insert(self, val):
        if (self.root is None):
            self.setRoot(val)
        else:
            self.insertNode(self.root, val)

    def insertNode(self, currentNode, val):
        if (val <= currentNode.val):
            if (currentNode.leftChild):
                self.insertNode(currentNode.leftChild, val)
            else:
                currentNode.leftChild = Node(val)
        elif (val > currentNode.val):
            if (currentNode.rightChild):
                self.insertNode(currentNode.rightChild, val)
            else:
                currentNode.rightChild = Node(val)

delete

삭제 연산은 탐색, 삽입보다는 약간 복잡합니다. 삭제 결과로 자칫 이진탐색트리의 속성이 깨질 수 있기 때문입니다. 가능한 세 가지 경우의 수를 모두 따져보겠습니다. 먼저 삭제할 노드에 자식노드가 없는 경우(case 1)입니다. 이 케이스라면 해당 노드(아래 예시에서 42)를 그냥 없애기만 하면 됩니다. 다음과 같습니다.

이번엔 삭제할 노드에 자식노드가 하나 있는 경우(case 2)입니다. 이 케이스라면 해당 노드를 지우고, 해당 노드의 자식노드와 부모노드를 연결해주면 됩니다. 아래 트리에서 20을 삭제한다고 칩시다.

20을 루트노드로 하는 서브트리의 모든 값은 20의 부모노드인 30보다 작거나 같습니다. 이진탐색트리의 속성 때문입니다. 따라서 20을 지우고, 20의 하나뿐인 자식노드(25)와 부모노드(30)를 연결해도 이진탐색트리의 속성이 깨지지 않는 걸 확인할 수 있습니다.

마지막으로 삭제할 노드에 자식노드가 두 개 있는 경우(case 3)를 살펴보겠습니다. 아래 트리에서 16을 삭제해야 한다고 칩시다. 그런데 기존처럼 16을 무작정 지우게 되면 13의 위치가 애매해집니다. 계산복잡성을 줄이기 위해서는 트리의 요소값들을 크게 바꾸지 않고 원하는 값(16)만 삭제할 수록 좋은데, 아무래도 새로운 방법을 고민해 봐야 할 것 같습니다.

이해를 돕기 위해 16을 삭제하기 전 위 트리 각 요소를 중위순회 방식(왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회)으로 읽어보겠습니다. 다음과 같이 정렬된 순으로 나타나 이진탐색트리 속성을 만족하고 있음을 확인할 수 있습니다.

4, 10, 13, 16, 20, 22, 25, 28, 30, 42

이 리스트와 예시 그림을 보면 16의 왼쪽 서브트리에 속한 모든 값은 16보다 작고, 오른쪽 서브트리에 속한 모든 값은 16보다 큰 것을 확인할 수 있습니다. 특히 13을 predecessor(삭제 대상 노드의 왼쪽 서브트리 가운데 최대값), 20을 successor(삭제 대상 노드의 오른쪽 서브트리 가운데 최소값)라고 합니다. 트리를 중위순회 방식으로 늘여뜨려 표시하면 16 바로 앞에 13이 있고, 바로 뒤에 20이 있기 때문에 각각 이런 이름이 붙은 것 같습니다.

따라서 아래와 같이 삭제할 노드인 16 위치에 20을 복사해 놓고, 기존 20 위치에 있던 노드를 삭제하게 되면 정렬된 순서를 유지(=이진탐색트리 속성을 만족)하면서도 원하는 결과를 얻을 수 있게 됩니다. 이는 위 그림에서도 확인할 수 있습니다. (물론 16 위치에 predecessor인 13을 놓고, 기존 13 위치에 있던 노드를 삭제해도 원하는 결과를 얻을 수 있습니다)

4, 10, 13, 16 20, 20, 22, 25, 28, 30, 42

이진탐색트리 구조상 successor(삭제 대상 노드의 오른쪽 서브트리의 최소값)는 자식노드가 하나이거나, 하나도 존재하지 않습니다. 각각 살펴보면 다음과 같습니다.

• successor의 자식노드가 하나인 케이스 : 위 예시 그림과 같습니다. 삭제 대상 노드의 오른쪽 서브트리가 30을 루트노드로 하는 트리일 때, 이 트리의 맨 왼쪽 노드인 20은 하나의 자식노드(25)를 갖습니다.
• successor의 자식노드가 존재하지 않는 케이스 : 삭제 대상 노드의 오른쪽 서브트리가 아래 그림과 같을 때에는 successor는 자식노드를 가지지 않습니다.

마찬가지로 왼쪽 서브트리의 맨 오른쪽 노드인 predecessor 또한 자식노드가 하나이거나, 하나도 존재하지 않습니다. 따라서 자식노드가 두 개인 경우(case 3)에는 다음과 같이 삽입 연산을 수행하면 됩니다(successor 기준).

1. 삭제 대상 노드의 오른쪽 서브트리를 찾는다.
2. successor(1에서 찾은 서브트리의 최소값) 노드를 찾는다.
3. 2에서 찾은 successor의 값을 삭제 대상 노드에 복사한다.
4. successor 노드를 삭제한다.

4번 successor 노드를 삭제하는 과정은 case 1나 case2에 해당합니다. 이미 언급했듯이 successor는 자식노드가 하나이거나, 하나도 존재하지 않기 때문입니다.

이번엔 삽입연산의 계산복잡성을 따져 보겠습니다. Big-O notation으로는 최악의 케이스를 고려해야 하므로 가장 연산량이 많은 case 3(삭제 대상 노드의 자식노드가 두 개인 경우)이 분석 대상입니다.

트리의 높이가 $h$이고 삭제대상 노드의 레벨이 $d$라고 가정해 보겠습니다. 1번 과정에서는 $d$번의 비교 연산이 필요합니다. 2번 successor 노드를 찾기 위해서는 삭제 대상 노드의 서브트리 높이($h-d$)에 해당하는 비교 연산을 수행해야 합니다. 3번 4번은 복사하고 삭제하는 과정으로 상수시간이 걸려 무시할 만 합니다. 종합적으로 따지면 $O(d+h-d)$, 즉 $O(h)$가 됩니다.

traverse

이진탐색트리의 중위순회 파이썬 코드는 다음과 같습니다.

    def traverse(self):
        return self.traverseNode(self.root)

    def traverseNode(self, currentNode):
        result = []
        if (currentNode.leftChild is not None):
            result.extend(self.traverseNode(currentNode.leftChild))
        if (currentNode is not None):
            result.extend([currentNode.val])
        if (currentNode.rightChild is not None):
            result.extend(self.traverseNode(currentNode.rightChild))
        return result

한계점

이진탐색트리 핵심 연산인 탐색, 삽입, 삭제의 계산복잡성은 모두 $O(h)$입니다. 트리의 높이에 의해 수행시간이 결정되는 구조입니다. 그러나 트리가 다음과 같은 경우 문제가 됩니다.

위 그림의 경우 노드 수는 적은 편인데 높이가 4나 됩니다. 균형이 안 맞기 때문입니다. 극단적으로는 $n$개의 노드가 크기 순으로 일렬로 늘어뜨려져 높이 또한 $n$이 되는 경우도 이진트리탐색에 해당합니다. 결과적으로 이진탐색트리의 계산복잡성은 $O(n)$이라는 얘기입니다.

이래가지고서는 탐색 속도가 $O(\log{n})$으로 빠른 이진탐색을 계승했다고 보기 어렵습니다. 이 때문에 트리의 입력, 삭제 단계에 트리 전체의 균형을 맞추는 이진탐색트리의 일종인 AVL Tree가 제안되었습니다.

이번 글에서는 다양한 분야에서 널리 쓰이고 있는 자료구조인 트리(tree)와 트리의 일종인 이진트리(binary tree)에 대해 살펴보도록 하겠습니다. 힙 정렬이 뭔지 알아보려면 여러가지 개념을 먼저 익혀두어야 하는데요. 차근차근 살펴 보겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concepts

트리는 그 모양이 뒤집어 놓은 나무와 같다고 해서 이런 이름이 붙었습니다. 예컨대 다음 그림과 같습니다.

위 그림에서 검정색 동그라미를 노드(node)라고 합니다. 보통 데이터가 여기에 담깁니다. 노드와 노드 사이를 이어주는 선을 엣지(edge)라고 합니다. 노드와의 관계를 표시합니다.

경로(path)란 엣지로 연결된, 즉 인접한 노드들로 이뤄진 시퀀스(sequence)를 가리킵니다. 경로의 길이(length)는 경로에 속한 엣지의 수를 나타냅니다.

트리의 높이(height)는 루트노드에서 말단노드에 이르는 가장 긴 경로의 엣지 수를 가리킵니다. 트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부릅니다.

잎새노드(leaf node)란 자식노드가 없는 노드입니다. internal node란 잎새노드를 제외한 노드를 나타냅니다. 루트노드(root node)란 부모노드가 없는 노드를 가리킵니다.

트리의 속성 중 가장 중요한 것이 ‘루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다’는 것입니다. 이 속성 때문에 트리는 다음 성질을 만족합니다.

• 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
• 회로(cycle)가 존재하지 않는다.
• 모든 노드는 서로 연결되어 있다.
• 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
• 엣지(edge)의 수 |$E$| 는 노드의 수 |$V$|에서 1을 뺀 것과 같다.

다음 두 예시는 트리가 아닙니다. 회로가 존재하기 때문입니다.

다음 예시는 트리가 아닙니다. 회로가 존재하지는 않지만 1에서 4로 가는 경로가 유일하지 않아서입니다.

다음 예시 또한 트리가 아닙니다. 연결되지 않은 노드가 존재하기 때문입니다.

Binary tree

이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다. 이진트리에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있습니다.

정이진트리는 다음 그림과 같습니다. 모든 레벨에서 노드들이 꽉 채워진(=잎새노드를 제외한 모든 노드가 자식노드를 2개 가짐) 이진트리입니다.

위 정이진트리에서 레벨에 따른 노드의 숫자는 다음 표와 같습니다.

정이진트리의 노드수가 $n$개라면 잎새노드의 수는 $n/2$를 올림한 숫자가 됩니다. 위 그림 예시를 기준으로 하면 총 31개의 노드가 있는데 이 가운데 잎새노드는 31/2를 올림한 16개입니다.

완전이진트리는 다음 그림과 같습니다. 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리입니다.

정이진트리와 완전이진트리는 다음처럼 1차원 배열(array)로도 표현이 가능합니다.

어떤 노드의 인덱스를 index, 왼쪽 자식노드의 인덱스를 left_index, 오른쪽 자식노드의 인덱스를 right_index로 선언하면 다음과 같은 관계를 지닙니다. 이를 파이썬 코드로 구현하면 다음과 같습니다.

left_index = 2 * index + 1
right_index = 2 * index + 2

균형이진트리는 다음 그림과 같습니다. 모든 잎새노드의 깊이 차이가 많아야 1인 트리를 가리킵니다. 균형이진트리는 예측 가능한 깊이(predictable depth)를 가지며, 노드가 $n$개인 균형이진트리의 깊이는 $\log{n}$을 내림한 값이 됩니다.

깊이 말고 left subtree와 right subtree의 노드 수를 기준으로 균형이진트리를 정의하는 경우도 있다고 합니다. 힙 정렬과 이진탐색트리는 모두 이진트리를 기반으로 만들어진 기법입니다. 힙 정렬은 이곳, 이진탐색트리는 이곳을 참고하시면 좋을 것 같습니다.

tree traversal

트리순회(tree traversal)란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다. 하나도 빠뜨리지 않고, 정확히 한번만 중복없이 방문해야 하는데요. 노드를 방문하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 세 가지로 나뉩니다. 아래 트리를 예시로 각 방법 간 차이를 비교해 보겠습니다.

preorder

루트 노드에서 시작해서 노드-왼쪽 서브트리-오른쪽 서브트리 순으로 순회하는 방식입니다. 깊이우선순회(depth-first traversal)라고도 합니다. 위 예시 트리에 전위순회 방식을 적용하면 다음과 같습니다.

1, 2, 4, 5, 3

inorder

루트 노드에서 시작해서 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식입니다. 대칭순회(symmetric traversal)라고도 합니다. 위 예시 트리를 중위순회 방식을 적용하면 다음과 같습니다.

4, 2, 5, 1, 3

postorder

루트 노드에서 시작해서 왼쪽 서브트리-오른쪽 서브트리-노드 순으로 순회하는 방식입니다. 위 예시 트리를 후위순회 방식을 적용하면 다음과 같습니다.

4, 5, 2, 3, 1

예시 : 사칙연산

예컨대 다음과 같은 식을 계산해야 한다고 칩시다.

• $(A+B)×(C+D)+2$

이를 후위표기법으로 바꿔서 다시 쓰면 다음과 같습니다. 후위표기법은 이곳을 참고하시면 좋을 것 같습니다.

• $AB+CD+×2+$

컴퓨터가 사칙연산을 수행할 때 이진트리를 쓰면 편리합니다. 아래 그림을 볼까요?

위 이진트리를 후위순회 방식으로 읽어 보겠습니다. 이는 정확히 후위표기법과 일치합니다.

A, B, +, C, D, +, ×, 2, +

위 이진트리를 전위순회 방식으로 읽어 보겠습니다. 다음과 같습니다.

+, ×, +, A, B, +, C, D, 2

이는 함수명(인자) 형태의 함수호출과 동일합니다. 예컨대 + 기호를 add 함수, ×를 multiply 함수라고 생각해 보죠. 그러면 위와 같은 시퀀스는 다음과 같이 수행됩니다.

add(multiply(add(A, B), add(C, D)), 2)

이번 글에서는 머신러닝의 다양한 분야에서 폭넓게 응용되고 있는 선형대수학의 기본 개념인 사영(projection)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 강필성 교수님, 역시 같은 대학의 김성범, 한성원 교수님 강의와 위키피디아 등의 자료를 제 나름대로 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

벡터의 내적과 사영

벡터 $b$를 벡터 $a$에 사영한 결과($x$)는 아래 그림과 같습니다.

벡터 덧셈의 기하학적 성질을 이용해 위 그림에서 정보를 얻어낼 수 있는데요. 벡터 $b$를 빗변으로 하는 직각삼각형의 밑변은 벡터 $x$, 높이는 $b-x$가 될 겁니다(밑변과 높이를 더하면 빗변에 해당하는 $b$가 됨).

서로 직교하는 벡터의 내적은 0이 되므로 스칼라 $p$는 아래와 같이 구할 수 있게 됩니다.

[{ (\overrightarrow { b } -\overrightarrow {x}) }^{ T }\overrightarrow { a } =0\{ (\overrightarrow { b } -p\overrightarrow { a } ) }^{ T }\overrightarrow { a } =0\ { \overrightarrow { b } }^{ T }\overrightarrow { a } -p{ \overrightarrow { a } }^{ T }\overrightarrow { a } =0\ p=\frac { { \overrightarrow { b } }^{ T }\overrightarrow { a } }{ { \overrightarrow { a } }^{ T }\overrightarrow { a } }]

그런데 여기에서 벡터 $a$가 유닛벡터($a^Ta=1$)라면 $p$는 $b^Ta$, 즉 벡터 $a$와 $b$의 내적만으로도 그 값을 구할 수 있게 됩니다. 다시 말해 벡터의 내적과 사영이 깊은 관련을 맺고 있다는 얘기입니다. 이 때문에 ‘어떤 특정 축(벡터)에 다른 벡터를 사영’하는 것과 ‘두 벡터를 내적’한다는 표현이 거의 같은 의미로 널리 쓰이는 듯합니다.

projection operator

사영을 3차원으로 확장해 생각해 보겠습니다. 다음 그림과 같습니다.

3차원 벡터 $u$를, 벡터 $v_1$과 $v_2$가 만드는 2차원 평면 공간에 사영시킨 결과는 $w$가 됩니다. 여기에서 사영 기능을 하는 3×3 크기의 정방행렬(projection operator) $P$를 가정해봅시다. 다시 말해 임의의 3차원 벡터 $u$에 $P$를 내적해주기만 하면 2차원 평면에 사영이 된다고 치자는 것입니다.

[P\cdot \overrightarrow { u } =\overrightarrow { w }]

그럼 여기에서 $P$의 속성을 간단히 알아보겠습니다. 정의에 의해 다음 식이 성립합니다. 단 아래 식에서 $P$와 벡터 $w$의 내적이 다시 $w$가 되는 이유는 $P$는 임의의 3차원 벡터를 $v1$과 $v2$가 만드는 2차원 평면 공간에 사영시키는 역할을 하는데, $w$는 이미 $v1$과 $v2$가 만드는 2차원 평면 공간에 있기 때문입니다.

[P\cdot \left( P\cdot \overrightarrow { u } \right) =P\cdot \overrightarrow { w } =\overrightarrow { w } =P\cdot \overrightarrow { u }]

위 식을 간단하게 정리하면 다음과 같습니다. 다시 말해 $P$는 멱등행렬(idempotent matrix, $P^2=P$)입니다.

[P\cdot \left( P\cdot \overrightarrow { u } \right) =P\cdot \overrightarrow { u } \ \left( { P }^{ 2 }-P \right) \overrightarrow { u } =0\ { P }^{ 2 }=P]

만약 $P$가 대칭행렬(symmetric matrix, $P^T=P$)이라고 가정해 봅시다. 그리고 나서 위 그림에서 직각삼각형의 밑변($w$)과 높이($u-w$)를 내적해 보는 것입니다. 다음과 같이 수식을 전개할 수 있습니다.

[\begin{align} { \left( { \overrightarrow { u } }-\overrightarrow { w } \right) }^{ T }{ \overrightarrow { w } }=&{ \left( { \overrightarrow { u } }-P\overrightarrow { u } \right) }^{ T }{ \left( P\overrightarrow { u } \right) }\ =&\left( { { \overrightarrow { u } }^{ T } }-{ \overrightarrow { u } }^{ T }{ P }^{ T } \right) { \left( P\overrightarrow { u } \right) }\ =&{ { \overrightarrow { u } }^{ T } }P\overrightarrow { u } -{ \overrightarrow { u } }^{ T }{ P }^{ T }P\overrightarrow { u } \ =&{ { \overrightarrow { u } }^{ T } }P\overrightarrow { u } -{ \overrightarrow { u } }^{ T }P\overrightarrow { u } \ =&0 \end{align}]

$P$가 멱등행렬이고 대칭행렬일 경우 해당 $P$는 orthogonal projection operator가 된다고 합니다.

선형회귀와 사영

$n$개 데이터가 있고 $x$의 변수가 $p$개 일 때 선형회귀 모델은 다음과 같이 나타낼 수 있습니다.

[\overrightarrow { Y } ={ \beta }{ 0 }\overrightarrow { 1 } +{ \beta }{ 1 }\overrightarrow { X_{ 1 } } +…+{ \beta }{ p }\overrightarrow { X{ P } } +\overrightarrow { \varepsilon } \ \overrightarrow { Y } =X\overrightarrow { \beta } +\overrightarrow { \varepsilon }]

선형회귀의 목적함수는 오차제곱합(sum of least square)이며 이를 최소로 하는 파라메터 $β$를 찾는 것이 모델의 학습이 되겠습니다. 식을 전개해서 정리하면 다음과 같습니다. (네번째 줄에서 두번째, 세번째 항은 스칼라값이므로 transpose를 취해주어도 같은 값을 지니기 때문에 하나로 합쳐줍니다)

[\begin{align} f\left( \overrightarrow { \beta } \right) =&{ \overrightarrow { \varepsilon } }^{ T }\overrightarrow { \varepsilon } \ =&{ \left( \overrightarrow { Y } -X\overrightarrow { \beta } \right) }^{ T }\left( \overrightarrow { Y } -X\overrightarrow { \beta } \right) \ =&\left( { \overrightarrow { Y } }^{ T }-{ \overrightarrow { \beta } }^{ T }{ X }^{ T } \right) \left( \overrightarrow { Y } -X\overrightarrow { \beta } \right) \ =&{ \overrightarrow { Y } }^{ T }\overrightarrow { Y } -{ \overrightarrow { Y } }^{ T }X\overrightarrow { \beta } -{ \overrightarrow { \beta } }^{ T }{ X }^{ T }\overrightarrow { Y } +{ \overrightarrow { \beta } }^{ T }{ X }^{ T }X\overrightarrow { \beta } \ =&{ \overrightarrow { Y } }^{ T }\overrightarrow { Y } -2{ \overrightarrow { \beta } }^{ T }{ X }^{ T }\overrightarrow { Y } +{ \overrightarrow { \beta } }^{ T }{ X }^{ T }X\overrightarrow { \beta } \end{align}]

위 식은 우리의 관심인 $β$에 대해 2차식의 형태를 가지므로 $β$에 대해 미분한 식이 0이 되는 지점에서 최소값을 가집니다. 이를 식으로 쓰면 다음과 같습니다.

[\begin{align} \frac { \partial f\left( \overrightarrow { \beta } \right) }{ \partial \overrightarrow { \beta } } =&{ \overrightarrow { Y } }^{ T }\overrightarrow { Y } -2{ \overrightarrow { \beta } }^{ T }{ X }^{ T }\overrightarrow { Y } +{ \overrightarrow { \beta } }^{ T }{ X }^{ T }X\overrightarrow { \beta } \ =-&2{ X }^{ T }\overrightarrow { Y } +2{ X }^{ T }X\overrightarrow { \beta } =0 \ \ \therefore &\overrightarrow { \hat{\beta} } ={ \left( { X }^{ T }X \right) }^{ -1 }{ X }^{ T }\overrightarrow { Y } \\Rightarrow \hat { Y } &=X\overrightarrow { \hat { \beta } } =X{ \left( { X }^{ T }X \right) }^{ -1 }{ X }^{ T }\overrightarrow { Y } \end{align}]

위 식에서 $X(X^TX)^{-1}X^T$를 $H$로 치환해 보겠습니다. 이 $H$가 대칭행렬인지 여부를 따져보니 대칭행렬임을 확인할 수 있습니다.

[\begin{align} { H }^{ T }=&{ \left{ { X\left( { X }^{ T }X \right) }^{ -1 }{ X }^{ T } \right} }^{ T }\ =&X\left{ { \left( { X }^{ T }X \right) }^{ -1 } \right} ^{ T }{ X }^{ T }\ =&X\left{ { \left( { X }^{ T }X \right) }^{ T } \right} ^{ -1 }{ X }^{ T }\ =&X\left( { X }^{ T }X \right) ^{ -1 }{ X }^{ T }=H \end{align}]

이번엔 $H$가 멱등행렬인지를 따져봤습니다. 멱등행렬임을 확인할 수 있습니다.

[\begin{align} HH=&{ X\left( { X }^{ T }X \right) }^{ -1 }{ X }^{ T }\cdot { X\left( { X }^{ T }X \right) }^{ -1 }{ X }^{ T }\ =&{ X\left( { X }^{ T }X \right) }^{ -1 }I{ X }^{ T }=H \end{align}]

따라서 $H$는 orthogonal projection operator가 됩니다. 이를 그림으로 도식화하면 다음과 같습니다. 다시 말해 $H$는 정답 벡터 $Y$를 ‘(학습 결과물인)선형식’이라는 기저에 사영하는 역할을 수행한다는 것입니다.

테일러 급수 전개와 사영

예컨대 3차원 벡터를 2차원 평면에 사영했을 경우에 벡터의 세 요소값들 가운데 하나는 특정 숫자로 고정되게 됩니다. 이를 통해 기저 2개로도 해당 벡터를 표현할 수가 있게 되죠. 이것이 바로 차원축소(dimensionality reduction)입니다.

그런데 테일러 급수 전개도 사영, 그리고 차원축소 개념과 연관지어 생각해볼 수 있다고 합니다. 테일러급수 전개는 함수값을 다음과 같이 무한합으로 표시하는 걸 가리킵니다.

[\begin{align} f\left( t \right) =&f\left( 0 \right) +f’\left( 0 \right) \cdot t+f’‘\left( 0 \right) \cdot \frac { { t }^{ 2 } }{ 2! } +f’’‘\left( 0 \right) \cdot \frac { { t }^{ 3 } }{ 3! } +…\ =&f\left( 0 \right) +\sum _{ k=1 }^{ \infty }{ f^{ \left( k \right) }\left( 0 \right) } \cdot \frac { { t }^{ k } }{ k! } \end{align}]

그런데 $f(t)$를 테일러 급수 전개식의 $n$번째 항까지만 써서 근사할 수 있습니다. $f(t)$를 일종의 벡터로 본다면, 테일러 급수 전개식의 각 항을 벡터의 요소값으로 봐도 큰 무리가 없을 것입니다. $n$번째 항까지만 써서 $f(t)$를 근사하는 경우 무한차원의 함수공간에 존재하는 벡터 $f(t)$를 $n$차원의 함수공간으로 사영했다고 보는 해석도 가능하다는 것이죠. 다음 그림과 같습니다.

이번 글에서는 여러 가지 정렬 알고리즘을 비교, 분석해 보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

비교표

알고리즘별 특징을 한 눈에 보기 쉽게 정리한 표는 다음과 같습니다. 아래 표에서 complexity는 average case를 기준으로 한 계산복잡성입니다.

• 버블정렬(Bubble sort) : 주어진 배열의 마지막 위치에 있는 요소를, 정렬되지 않은 직전 요소부터 첫 요소에 이르기까지 비교해 정렬 순서가 맞지 않은 모든 case에 대해 요소 위치를 바꿔줌. 이를 요소 수만큼 반복. 가장 간단하지만 비효율적인 알고리즘.
• 선택정렬(Selection Sort) : 요소 위치 변경 횟수를 줄여 버블정렬을 일부 개선한 알고리즘. 정렬 순서가 맞지 않으면 무조건 자리를 바꿔줬던 버블정렬과 달리, 1회 iteration마다 최소값(혹은 최대값)을 찾고 단 한번만 해당 요소 위치를 바꿔줌.
• 삽입정렬(insertion sort) : 모든 요소에 대해 앞에서부터 차례대로 이미 정렬된 배열(sorted list)과 비교하여 sorted list 내 자신의 위치를 찾아 삽입함으로써 정렬을 완성, 입력데이터가 이미 정렬된 상태라면 $O(n)$의 빠른 속도를 보이지만 그렇지 않은 경우 다른 기법을 적용하는 것이 나음.
• 쉘정렬(shell sort) : 정렬되지 않은 배열의 경우 비효율적인 삽입정렬을 개선한 기법. 주어진 배열의 일정 간격(gap)만큼의 요소들에 대해 삽입정렬을 반복 수행.
• 합병정렬(merge sort) : 리스트를 잘게 쪼갠 뒤 둘씩 크기를 비교해 정렬하고 분리된 리스트를 재귀적으로 합쳐서 정렬을 완성, 분할된 리스트를 저장해둘 공간이 필요해 메모리 소모량이 큰 편
• 힙정렬(heap sort) : 모든 노드가 힙 속성(각 노드의 값이 자신의 자식노드 값보다 큰 이진트리)을 만족하도록 재귀적으로 트리 구조를 만들어 정렬을 완성
• 퀵정렬(quick sort) : 피봇값을 기준으로 피봇 앞에는 피봇보다 작은 값, 뒤에는 큰 값이 오도록 하여 리스트를 분할하고, 분할된 두 개 리스트 각각에 재귀적으로 이 과정을 반복해 정렬을 완성. 합병정렬과 달리 주어진 배열을 임의로 나누지 않기 때문에 대개는 효율적이지만, 피봇값이 잘못 선택되면 $O(n^2)$이 될 수도 있음.
• 카운팅정렬(counting sort) : 입력값의 빈도를 세어서 이를 결과리스트의 인덱스로 활용, 입력리스트의 요소값을 해당하는 결과리스트 인덱스 위치에 채워 넣는 방식으로 정렬을 완성, 입력리스트의 최대값($k$)이 커지면 복잡도가 크게 높아짐
• 래딕스정렬(radix sort) : 입력값의 자릿수($d$) 각각에 대해 카운팅정렬을 적용해 카운팅정렬의 단점 보완, 예컨대 10진법으로 표현된 입력값에 래딕스정렬을 적용하면 $k$값이 9로 작아짐
• 버킷정렬(bucket sort) : 데이터 개수만큼의 버킷을 두어 데이터를 나누고 버킷별로 정렬한 후 합쳐 정렬을 완성, 데이터 분포가 균등할 경우 계산복잡성을 낮출 수 있으나 그 반대의 경우 효과를 기대하기 어려울 수 있음

In-Place

입력리스트 내부에서 정렬이 이뤄지는 경우를 가리킵니다. 반대는 정렬 도중에 별도 저장공간을 필요로 하는 경우입니다. 합병정렬의 경우 입력리스트를 분할해 이를 정렬하고 다시 합치는 과정에서 분할된 리스트를 별도로 저장해 두어야 합니다. 카운팅정렬과 래딕스정렬은 입력값의 빈도를 세어서 저장해 두는 변수, 결과리스트를 저장해 둘 변수가 필요합니다. 버킷정렬은 버킷이라는 변수를 만들 공간이 있어야 합니다.

Stable

Stable이란 같은 값의 위치가 정렬 과정에서 뒤바뀌지 않는 것을 뜻합니다. 아래 그림과 같습니다(위키피디아).

힙정렬은 이진트리를 배열 형태로 표현해 정렬을 수행하는 과정에서 입력값의 위치가 바뀔 수 있습니다. 퀵정렬 또한 피봇을 기준으로 각 요소값들이 좌우로 이동할 수 있어 위치가 바뀔 수 있습니다.

comparison

값을 비교하는 정렬 알고리즘을 comparison sort라고 합니다. comparison sort 계산복잡성의 하한은 $O(n\log{n})$입니다. 카운팅정렬의 경우 값을 비교하지 않고도 정렬을 수행할 수 있어 comparson sort가 아닙니다. 래딕스정렬은 카운팅정렬을 기본으로 사용합니다. 버킷정렬의 경우 각 버킷에 대해 어떤 정렬 알고리즘을 쓰느냐에 따라 comparison 유무가 달라질 수 있습니다.

이번 글에서는 버킷 정렬(Bucket sort) 알고리즘을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고로 하였습니다. 그럼 시작하겠습니다.

concepts

값을 비교하여 정렬하는 기법인 comparison sort의 계산복잡성은 최소 $O(n\log{n})$입니다. 버킷 정렬은 분석 대상 데이터의 분포 특성을 활용해 계산복잡성을 $O(n)$ 수준으로 개선시키려는 것을 목적으로 하고 있습니다. 버킷 정렬은 데이터가 특정 범위 내에 확률적으로 균등하게 분포한다고 가정할 수 있을 때 적용할 만한 기법입니다. 이해를 돕기 위해 다음 그림을 보겠습니다.

위와 같이 10개의 데이터 $A$가 주어졌을 때 같은 크기의 버킷 $B$를 만듭니다. 만약 $A$의 분포가 균등하다면 각 버킷에는 1~2개의 요소만 속해 있을 것입니다. 이렇게 1~2개 값들만 있는 버킷 하나를 정렬하는 데 필요한 계산복잡성은 $O(1)$이 될 것이고, 이 작업을 $n$개 버킷에 모두 수행한다고 하면 전체적인 계산복잡성은 $O(n)$이 될 것입니다. 이것이 바로 버킷 정렬이 노리는 바입니다.

버킷 정렬의 구체적인 프로세스는 다음과 같습니다.

• 데이터 $n$개가 주어졌을 때 데이터의 범위를 $n$개로 나누고 이에 해당하는 $n$개의 버킷을 만든다.
• 각각의 데이터를 해당하는 버킷에 집어 넣는다. (C 등에서는 연결리스트를 사용하며 새로운 데이터는 연결리스트의 head에 insert한다)
• 버킷별로 정렬한다.
• 이를 전체적으로 합친다.

파이썬 구현

파이썬으로 구현한 버킷 정렬 코드는 다음과 같습니다. 버킷을 중첩 리스트로 구현했고, 각 버킷별로 정렬할 때 퀵 정렬을 적용했습니다.

def bucket_sort(seq):
    # make buckets
    buckets =  [[] for _ in range(len(seq))]
    # assign values
    for value in seq:
        bucket_index = value * len(seq) // (max(seq) + 1)
        buckets[bucket_index].append(value)
    # sort & merge
    sorted_list = []
    for bucket in buckets:
        sorted_list.extend(quick_sort(bucket))
    return sorted_list

def quick_sort(ARRAY):
    ARRAY_LENGTH = len(ARRAY)
    if( ARRAY_LENGTH <= 1):
        return ARRAY
    else:
        PIVOT = ARRAY[0]
        GREATER = [ element for element in ARRAY[1:] if element > PIVOT ]
        LESSER = [ element for element in ARRAY[1:] if element <= PIVOT ]
        return quick_sort(LESSER) + [PIVOT] + quick_sort(GREATER)