읽기일기

패턴 인식 (6) 질적 분류


패턴인식, 오일석 지음/교보문고

6. 질적 분류

세상엔 많은 데이터가 있지만 그 특성과 표현 방식은 매우 다르다. 정수 또는 실수로 표현할 수 있는 것들은 양적으로(quantitatively) 표시한 계량(metric) 데이터를 가진다. 하지만 그 외에도 사물 또는 개념을 질적으로(qualitatively) 구분한 비계량(nonmetric) 데이터도 있다.

베이시언 분류기, 신경망, SVM은 모두 계량 데이터에 적용이 가능한 분류기들이다. 샘플은 d차원 특징 공간에서 점으로 표시되고 점들간 거리 개념이 바탕에 깔려있다. 이에 반해 비계량 데이터는 양적 개념을 가지지 않으므로, 여러 구간으로 구분하고 편의상 구간에 정수로 일련 번호를 붙인다. 하지만 이들 정수간의 거리를 따지는 것은 합당하지 않다. 양이라는 데이터가 없기 때문이다.

이 장에서는 비계량 데이터를 어떻게 분류할 것인지를 이야기해볼 것이다. 이러한 분류기를 질적 분류기(qualitative classifier)라고 부를 것이다.

6.1 결정 트리

6.2.1 원리

결정 트리는 스무고개 놀이와 비슷하다. 하지만 사람이 지능적으로 적절한 질문을 만드는데 비해 결정 트리는 컴퓨터가 자동으로 질문을 만들어야 한다. 주어져 있는 것은 훈련 집합 $ X = \{ (x_1, t_1, \dots, (x_N, t_N) \} $ 이다. 이를 이용하여 최적의 분류 성능을 갖는 결정 트리를 만들도록 학습시켜야 하는 것이다. 이를 위하여 고려해야할 사항은 다음과 같다.

  1. 노드에서 몇 개의 가지로 나눌 것인가?
  2. 각 노드의 질문을 어떻게 만들 것인가?
  3. 언제 멈출 것인가?
  4. 잎 노드를 어느 부류에 할당할 것인가?

결정 트리는 많은 경우 이진 트리를 사용한다. 잎이 아닌 노드에는 예/아니오를 판단할 수 있는 질문이 들어있으며, 잎 노드에 도달할 때 까지 순환적으로(recursively) 질문에 대하여 이동을 반복한다. 잎 노드에 도달하면 x를 그 잎 노드에 해당하는 부류로 분류한다.

6.1.2 노드에서의 질문

잎이 아닌 노드 T에서는 왼쪽 자식 노드나 오른쪽 자식 노드로 분기하는데 그것은 노드 T에 해당하는 질문에 따라 결정된다. 이 질문이 참이 되면 왼쪽으로, 거짓이면 오른쪽으로 이동하게 된다. 이것을 노드에 분기라 부른다. 노드의 질문은 $ x_i = \alpha$로 나타내는데, $x_i$는 특징 벡터 x를 구성하는 i번째 특징이고 $\alpha$는 그것이 가질 수 있는 값 중 하나이다. 특징이 d개가 있고, 그들이 평균 n개의 값을 가진다면 총 dn개의 후보 질문을 생각할 수 있을 것이다. 이들 중 어느 것을 사용해야 가장 좋을까? 모든 후보를 평가하여 가장 좋은 것을 고르는 낱낱 탐색(exhaustive search)를 사용하면 된다.

노드의 분기를 통해 부류를 판단해야 하므로 가능한 한 분기된 좌, 우의 자식 노드에는 동질의 샘플이 담기는 것이 좋다. 이러한 동질성을 측정해 주는 기준이 불순도(impurity)이다. 이 불순도는 여러 방법으로 정의할 수 있는데 그 중 대표적인 것이 엔트로피(entropy)를 사용한 정의이다.

$$im(T) = - \sum_{i=1}^M P(w_i | T) \log_2 p(w_i | T)$$

여기서 $ P(w_i | T) $는 T노드에서 $w_i$ 부류가 발생할 확률을 나타낸다. 엔트로피는 어느 부류 하나의 확률이 1이고 나머지는 모두 0일 때 0이다. 이때가 불순도가 0으로 제일 낮은 경우이다.

다른 측정 방법은 지니 불순도(Gini impurity)이다. 이 식은 어느 부류가 1의 확률을 갖는 경우 최소값 0을 갖는다.

$$im(T) = 1 - \sum_{i=1}^N P(w_i | T)^2$$

마지막으로 오분류 불순도(misclassification impurity)가 있다.

$$im(T) = 1 - \max_i P(W_i | T)$$

불순도는 하나의 노드를 대상으로 측정한다. 따라서 최적의 질문을 찾기 위해서는 불순도의 감소량을 정의하고 감소량이 최대가 되는 질문을 고르면 될것이다.

$$\Delta im(T) = im(T) - \frac{|X_\text{Tleft}|}{|X_T|} im(T_\text{left}) - \frac{|X_\text{Tright}|}{|X_T|} im(T_\text{right})$$

또다른 불순도 감소량을 계산하는 방법으로 투잉 기준(twoing criteria)라는 것도 있다.

$$\Delta im(T) = \frac{|X_\text{Tleft}|}{|X_T|} \frac{|X_\text{Tright}|}{|X_T|} (\sum_{i=1}^M)$$

만약 특징이 계량적인 경우엔 정확한 값이 아니라 가장 인접한 부류를 사용하는 등의 방법으로 변경해서 사용할 수 있다.

이제 후보 질문 중 가장 불순도 감소량이 큰 질문을 노드에 할당하는 식으로 트리를 생성해 나가면 된다.

6.1.3 학습 알고리즘

이진 트리와 관련된 알고리즘은 대부분 순환 함수로 작성된다. 앞에서 설명한 방법을 사용하여 후보 질문은 생성하고 그둘 중 가장 좋은 것을 고른다. 그 후 자식 노드를 생성할 필요가 있는 지 검사한다. 이 때 사용하는 조건이 멈춤 조건이며, 멈춤 조건을 만족하면 그 노드를 잎 노드로 만들고 적절한 부류를 할당한다. 그렇지 않으면 자식 노드를 생성하고 노드 생성을 계속한다.

멈춤 조건으로 사용되는 조건은 아래와 같은 것들이 있다. 이러한 조건을 and 또는 or로 결합하여 사용하는 것이 보통이다.

  1. 불순도가 0이다.
  2. $ X_T $의 샘플 개수가 임계값 이하이다.
  3. 결정한 질문의 불순도 감소량이 임계값 이하이다.

조건 1만으로 멈춤을 결정하면 과적합(overfitting)이 발생할 수 있으나 2나 3에서 임계값을 너무 크게 하면 설익은 수렴(premature convergence)에 도달할 수도 있어 적절한 임계값의 사용이 필요하다.

6.1.4 특성

  1. 결정 트리는 계량 값 뿐만 아니라 비계량 특징도 다룰 수 있고 이 둘이 혼합되어있는 패턴도 다룰 수 있다.
  2. 트리의 분류 경로를 조사하여 결과의 해석이 가능하다.
  3. 인식 작업이 빠르다.
  4. 트리의 크기를 줄이기 위해 가지치기(pruning) 방법을 사용할 수 있다. 충분히 큰 트리를 만든 뒤, 밑에서부터 잎 노드를 합치는 연산을 수행한다.
  5. 불안정성(instability)을 보이기도 한다. 한두개의 샘플이 바뀌었는데 전체 크기 모양이 변하는 현상이 나타나기도 한다.
  6. 결정 트리의 학습 알고리즘은 욕심 알고리즘(greedy algorithm)이다.
  7. 노드의 질문이 꼭 하나의 특징만을 사용하지 않아도 된다.
  8. 손실 특징을 다루기가 다른 분류기에 비해 쉽다. 대기 분리(surrogate split)을 두어 특징이 손실되었을 경우 대기 분류리를 이용하여 분리할 수 있다.

6.2 CART, ID3, C4.5

CART, ID3, C4.5는 모두 결정 트리를 활용한 대표적인 시스템이다. 각기 다른 그룹에서 개발되었기 때문에 불순도 측정 방식, 가지치기 방식, 실수를 다루는 방식 등의 측면에서 어떤 방법을 채택하였느냐에 따라 차이가 있다.

6.3 스트링 인식기

어떤 응용분야세너는 패턴을 가변 길이의 스트링으로 표시한다. 이러한 표현은 길이가 가변적이기 때문에 통상적인 거리 측정 방법을 적용할 수가 없다. 새로운 거리를 적용하더라도 특징 그 자체를 이용하는 SVM이나 신경망 같은 프로그램은 사용이 불가능하고 k-NN이나 군집화 같은 그 거리만으로 작동되는 알고리즘만이 사용 가능하다.

6.3.1 교정 거리

패턴이 기호의 열로 표현되는 경우 이 열을 스트링(string)이라고 부른다. 패턴이 스트링으로 표현되는 상황은 두 가지 독특한 특성이 있다. 하나는 특지잉 유한 개수의 이산 값을 갖는 비계량 데이터라는 점이고 다른 하나는 길이가 가변적일 수 있다는 것이다. 이동 궤적으로 동(E),서(W),남(S),북(N)을 스트링으로 표시한다고 하면, EESSSWWWW와 EESSWWWW는 길이는 다르지만 유사도가 높은 패턴이 될 것이다.

또 다른 예는 DNA의 염기 서열이나, 필기 인식에서의 궤적의 체인 코드(chain code)가 잇다. 체인 코드는 패턴의 궤적을 0~7사이의 8방향으로 표시한다. 데스크톱 PC나 PDA의 입력된 패턴들은 궤적이 길이가 다를 수밖에 없기 때문에 가변 길이의 스트링 간의 거리 또는 유사도를 측정하는 방법을 사용한다. 그렇다면 가변 길이의 스트링 간 거리를 어떻게 측정할 것인가?

측정을 위한 알고리즘 중 하나로 교정 거리(edit)라는 것이 잇다. 이는 두 스트링의 길이가 다르기 때문에 기호를 대치한다거나 삽입, 또는 삭제를 통해 교정을 거친 후 거리를 계산하기 때문에 그런 이름이 붙었다.

교정 거리에는 사용하는 연산에 따라 여러가지가 있는데, 많이 알려진 것으로 Levenshtein거리와 이를 확장한 Damerau-Levenshtein 거리가 있다.

6.3.2 Levenshtein 거리

거리 계산에 참여할 샘플 두 개를 $ x = x_1 x_2 \dots x_c $$ y=y_1 y_2 \dots y_r $로 표기하자. x와 y의 길이는 각각 c, r 이다.

Levenshtein 거리는 삽입(insertion), 삭제(deletion) 그리고 대치(substitution)의 세가지 연산을 사용한다. 그리고 각 연산을 수행하려면 서로 다른 비용이 필요하다. 예를 들어 $ x= \text{revgniaton} $이고 $ y= \text{recognition}$ 이라고 하자.

  1. 삽입 : $x_8$ 다음에 $y_9$를 삽입하여 $x= \text{revgniation}$ 으로 만든다.
  2. 삭제 : $x_7$을 삭제하여 $x=\text{revgniton}$로 만든다.
  3. 대치 ; $ x_3$$y_3$으로 대치하여 $x=\text{recgniaton}$으로 만든다.

이제 어떻게 하면 최소의 비굥으로 x에서 y로 변환을 할 수 있는지를 찾는다면, 그것을 둘간의 거리로 생각할 수 있다.

모든 경우를 다 나열하고 그 중 최적의 것을 선택하는 낱낱 탐색(exhaustive search)를 사용할 수도 있지만 계산 시간이 너무 많이 걸린다. 이 문제를 효율적으로 풀기 위해 Levenshtein은 크기가 $ (r+1)*(c+1) $인 2차원 배열 D[r][c]를 사용하였다. 배열의 내부에는 교정 연산의 비용을 채워넣었다. 알고리즘은 크게 초기화 단계, 전방 계산 단계, 교정 연산을 찾기 위한 역 추적 단계로 구성된다. 구체적으로 알고리즘을 살펴보자.

먼저 크기가 (r+1 * c+1)인 배열 D를 생성한다. 이 배열의 각 요소는 (0, 0)에서부터 그 지점까지의 최단 경로의 거리를 기록한다. 예를 들면 앞의 예에서 D[2][5] 위치의 값은 x의 부분 스트링 revgn을 y의 부분 스트링 re로 변환하는데 드는 비용을 나타낸다. 이 경로 표의 값은 (0, 0) = 0에서 출발하여 인접한 요소들로 진행하며 채워 나간다.

주변의 값을 이용하여 현재 위치의 값은 최적 원리(optimality principle)에 따라 계산이 된다.

  • 최적 원리 : (0, 0)에서 (j, i)까지의 최단 거리는 (j, i-1)까지의 최단 거리에 (j, i-1) → (j, i) 의 이동 비용을 더한 값, (j-1, i)까지의 최단 거리에 (j-1, i) → (j, i)의 이동 비용을 더한 값, (j-1, i-1)까지의 최단 거리에 (j-1, i-1) → (j, i)의 이동 비용을 더한 값 중에 가장 작은 값과 같다.

수식으로 나타내면 아래와 같다.

$$D[j][i] = \min(D[j-1],[i] + 1, D[j][i-1]+1, D[j-1][i-1]+ \text{scost})$$

이 때, $ x_i = y_i $이면 scost = 0, 그렇지 않으면 1이다.

이 수식을 이용하여 (0, 0)부터 행 혹은 열 우선으로 배열을 채워나간다. 배열을 채우면서 가장 적은 값을 가지는 값을 선택하여 배열에 써가며 어떤 연산이 선택되었는지도 기록한다.

이러한 과정을 계속하여 표를 채우면, 마지막 요소 D[r][c]에는 우리가 원하는 답이 들어있다.

이러한 알고리증믄 동적 프로그래밍(dynamic programming)의 일종이다. 동적 프로그래밍의 핵심 중 하나는 중복 계산을 피하는 것인데 이를 위해 2차원 배열을 활용한 것이다. 이 알고리즘의 특성을 살펴보자.

  1. 앞에서 설명한 알고리즘은 삽입, 삭제, 대치의 비용이 1로 고정되어있으나, 이들을 서로 다르게 하거나 기호 별로 다른 비용을 부여할 수도 있다.
  2. 삽입과 삭제 비용이 같으면 두 샘플을 바꾸어도 같은 결과를 갖는다.
  3. 대치라는 한가지 교정 연산만 사용하면 해밍 거리가 된다.
  4. 삽입과 삭제 연산만 사용하면 최장 공통 부분 스트링(longest common substring, LCS) 문제가 된다.
  5. r * c의 계산을 하여야 하므로 계산 복잡도는 $\Theta(rc) $이다.

6.3.3 Damerau-Levenshtein 거리

Damerau는 Levenshtein이 사용한 연산에 인접한 두 기호의 교환(exchange)을 추가하였다. 이는 철자 오류를 교정하는 데 유용하게 사용된다. 알고리즘은 이전의 Levenshtein과 거의 같다. 단지 어느 연산을 사용할 것인지 선택할 때, 교환 연산이 성립하는지를 검사하고, 성립한다면 3가지 기본 연산과 비교하여 가장 작은 것을 선택한다는 점만 다르다.


Add a Comment Trackback