[Python] Segmented Least Squares를 이용해 구간 나누기

최소제곱법(Least Square Approximation)은 데이터를 근사하는 모형을 찾는데 흔히 사용하는 방법입니다. 참값과 근사값의 오차의 제곱합이 최소가 되게한다고 해서 최소제곱법이라고 부르지요. 대표적인 사례가 선형회귀입니다. 두 변수가 가지는 관계를 좌표평면 상에 늘어놓고, 데이터의 분포를 최대한 잘 근사하는 직선을 찾는 일입니다. 그 형태가 간단하고 닫힌 해가 알려져 있어서 통계학에서는 기초 중의 기초로 널리 쓰이고 있습니다.

근데 때로는 전체 데이터의 분포가 하나의 직선으로 표현하기에 어려운 경우도 있습니다. 이 경우 선형이 아닌 좀 더 복잡한 모형을 사용하는 방법을 쓸 수도 있고, 선형 모형 여러개를 결합하여 데이터를 표현하는 방법을 쓸 수도 있습니다.

(왼쪽은 비선형 모형을 사용하는 경우, 오른쪽은 선형 모형 2개를 결합하는 경우)

오늘의 주제는 오른쪽과 같이 복잡한 형태를 쪼개어 직선 여러 개로 표현하는 기법에 대한 것입니다.

Segmented Least Squares Problem

위와 같이 임의의 데이터에 대해 이를 최대한 잘 근사하는 직선의 조합을 찾는 문제를 Segmented Least Squares Problem이라고 합니다. 이 때 전체 데이터를 쪼개는 개수에는 제한을 두지 않습니다. 즉 위의 그림의 경우 2개로 쪼갠것이지만, 필요에 따라 더 많이 쪼갤수도 있고 더 적게 쪼갤수도 있겠죠. 물론 당연히 더 잘게 쪼갤수록 더 정확하게 근사가 가능할테니 너무 많이 쪼갤 경우에는 페널티를 주어야 합니다. 이를 염두해두면서 이 문제를 조금더 수학적으로 정밀하게 써보도록 하겠습니다.

x1 <= x2 <= ... <= xN 으로 순서대로 정렬된 P = {(x1, y1), (x2, y2), ... (xN, yN)}가 있고, P의 부분집합 S(a,b) = {(xi, yi) | a <= i < b}에 대한 근사 오차를 Err(S(a,b))라고 하자. 이 때 전체 오차 ∑i {Err(S(ti, ti+1)) + C}를 최소로 하는 L개의 분할지점 t1 < t2 < ... < tL 을 찾으시오. (단, t1 = x1, tL = xN)

여기서 C는 분할에 대한 페널티 값입니다. 전체 분할의 개수가 늘어날수록 전체 오차에 합쳐지는 C값이 많아지므로, 분할을 키우지 못하게 막습니다. 따라서 C값이 클수록 적게 분할하게 되고, C값이 작을수록 많이 분할하게 되겠죠. 복잡해 보이는 이 문제는 다행히도 동적 프로그래밍(Dynamic Programming)을 이용하여 다항시간 내에 풀 수 있습니다.

동적 프로그래밍을 이용한 풀이

동적 프로그래밍이란 이름은 참 거창하지만, 사실 이 기법은 단순히 이전 값을 저장해두고 다시 사용하겠다는 개념일 뿐입니다. 우리가 원하는 최소 전체 오차를 Opt라고 정의하면 다음과 같은 식이 성립합니다.

Opt( {} ) = 0

Opt(S(1, u)) = min 0<= i < u{ Opt(S(1, i)) + Err(S(i+1, u)) + C }

먼저 당연하게도 공집합에 대해서는 그 최소 오차값은 0입니다. 그리고 1~u까지의 데이터를 포함하는 집합에 대한 오차는, 1~i까지의 데이터에 대한 최소 오차에 나머지 i+1~u까지의 데이터에 대한 오차, 그리고 분할 페널티 값인 C를 합한 값으로 계산할 수 있습니다. i가 몇이냐에 따라 그 값이 바뀔텐데 모든 가능한 i에 대해 계산을 실시하고 가장 작은 값을 Opt(S(1, u))로 정의하면 최소 오차를 구할 수 있겠죠.

따라서 u = 1에서부터 시작하여 전체 데이터의 개수인 N까지 키워가며 Opt를 계산하면 전체 데이터 집합에 대한 최소 오차값을 구할 수 있습니다. 참 쉽죠?

기출 변형..! 글자 크기에 따라 단락을 구분해라!

OCR을 수행하다 보면 한 문서 내에서도 글자 크기가 다 다른 경우를 만날수가 있습니다. 지금 보고 계신 이 문서만 하더라도 헤드라인이 나오고 그 다음에는 작은 글자들이 반복되다가 또 다른 헤드라인이 나오는 것을 볼 수 있습니다. 이 연속된 행들을 동질적인 녀석들끼리 묶어서 단락을 구분지어주려면 어떻게 해야할까요?

문서가 디지털로 깔끔하게 정리되어 있지 못하여 OCR을 수행하는 경우 각 글자마다 그 높이값이 다 다르게 측정됩니다. 10pt로 쓴 글일지라도 9.8pt, 10.1pt, 10.5pt ... 와 같이 측정되는 일이 비재합니다. 따라서 단순히 값이 같은 경우만 한 단락으로 묶기에는 어려운 경우가 많죠.

이 경우 위에서 설명했던 Segmented Least Squares 풀이법을 활용할 수 있습니다. 단 데이터가 (x, y) 형태의 평면 상의 점이 아니라 (n, x)처럼 행 번호와 해당 행의 글자 크기로 표현되는 식이죠. 그리고 이 때 Err는 해당 집합 내의 글자 크기들의 평균으로부터의 오차 제곱합으로 정의할 수 있습니다.

간단하네요! 그럼 바로 Python3 코드로 구현해보도록 하겠습니다.

import numpy as np arr = [12.1, 12.7, 12.0, 10, 10.1, 9.8, 9.9, 13.1, 9.8, 9.9, 10.0] def segmentLS(arr, C): arr = np.array(arr) err = np.zeros((len(arr), len(arr))) opt = np.zeros(len(arr) + 1) slicePoint = [()] * (len(arr) + 1) # Err 을 먼저 계산하여 저장해둔다 for j in range(len(arr)): for i in range(j): err[i, j] = np.std(arr[i:j + 1]) ** 2 * (j+1-i) # 그 후 Opt를 차례대로 계산해나간다 for j in range(1, len(arr) + 1): opt[j], minP = min((err[i, j - 1] + C + opt[i], i) for i in range(j)) # slicePoint에는 분할지점을 저장해둔다 slicePoint[j] = slicePoint[minP] + (minP,) final = slicePoint[-1] + (len(arr),) # 최소 오차값과 분할된 리스트를 함께 반환한다 return opt[-1], [list(arr[a:b]) for a, b in zip(final[:-1], final[1:])] print(*segmentLS(arr, 10)) # 27.3872 [[12.1, 12.7, 12.0, 10.0, 10.1, 9.8, 9.9, 13.1, 9.8, 9.9, 10.0]] print(*segmentLS(arr, 1)) # 4.35666 [[12.1, 12.7, 12.0], [10.0, 10.1, 9.8, 9.9], [13.1], [9.8, 9.9, 10.0]] print(*segmentLS(arr, 0.1)) # 0.669999 [[12.1], [12.7], [12.0], [10.0, 10.1, 9.8, 9.9], [13.1], [9.8, 9.9, 10.0]]

십 여 줄의 코드로 간단하게 구현되었습니다. (역시 간단한 실험 돌려볼때는 파이썬만한게 없죠)

보시면 입력 데이터는 [12.1, 12.7, 12.0, 10, 10.1, 9.8, 9.9, 13.1, 9.8, 9.9, 10.0]으로, 처음에는 12와 같이 큰 값이 3개 연속 등장하다가, 그 다음에는 비교적 작은 값이 4개, 그리고 다시 큰값 1개, 다시 작은값 3개가 등장하고 있습니다. C값을 적절하게 잘 부여할 경우, 이 차이를 반영하여 전체 데이터셋을 4개로 분할해줄 수 있습니다.

본 테스트에서는 C=10일때는 전체를 하나로 묶어 버렸고, C=1일때는 우리의 예상대로 4단계로 분할했습니다. 마지막으로 C=0.1일때는 과도하게 많이 분할해버렸구요. 

실제로 이 기법을 통해서 OCR된 문서에서 글자 크기가 달라지는 줄을 찾아서 단락을 구분해줄 수 있었습니다. (사실 단순히 글자 크기만 사용해서는 원하는것처럼 깔끔한 결과가 나오진 않았는데요, 다른 자질들을 좀더 이용하도록 다른 방법도 찾아봐야겠습니다.)

참고 문헌

https://kartikkukreja.wordpress.com/2013/10/21/segmented-least-squares-problem/ SLS 문제에 대해서 설명이 깔끔하게 잘 되어있는 블로그입니다.