[카테고리:] Python

이 글의 원문은 https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_ml/py_kmeans/py_kmeans_understanding/py_kmeans_understanding.html 입니다.

이 글은 K-Means 클러스터링에 대한 개념을 예를 통해 설명합니다.

티셔츠를 만다는 어떤 회사가 있다고 합시다. 이 회사는 새로운 티셔츠를 만들어 시장에 뿌리려고 합니다. 분명이 이 회사는 모든 사람들이 만족하는 다양한 티셔츠 사이즈를 생산해야 합니다. 그래서 이 회사는 사람들의 키와 몸무게의 데이터를 수집해서 아래처럼 그래프로 표현 했습니다.

회사는 모든 사이즈에 대한 티셔츠를 만들 수는 없습니다. 대신에 작은 사이즈, 중간 사이즈, 큰 사이즈와 같이 3가지 사이즈를 만들고 모든 사람이 이 셋 중에 하나를 골라 만족하기를 기대합니다. 사람들을 이 3개의 그룹으로 나누는 것은 K-Means 클러스터링을 통해 가능하며, 이 알고리즘은 모든 사람들이 만족할 수 있는 최적의 3가지 사이즈를 산출해 낼 것입니다. 3가지로 부족하다면 4개로 그룹을 나눌 것이고.. 계속 만족할 만한 개수의 그룹으로 늘려나갈 수 있습니다. 아래 그럼처럼요.

자, 이제 이 K-Means 클러스터링의 알고리즘을 알아 봅시다. 그림을 통해 단계별로 설명하겠습니다.

아래와 같은 데이터셋을 살펴봅시다. 이 데이터셋을 앞서 언급한 티셔츠 데이터라고 할 수 있습니다. 이 데이터를 2개의 그룹으로 군집화(Clustering)해 봅시다.

1단계

무작위로 2개의 중심점을 선택합니다. 이 중심점은 C1과 C2라고 합시다. (그냥 데이터 셋중 2개를 잡아서 그 2개가 C1, C2라고 해도 됩니다)

2단계

데이터셋을 구성하는 각각의 모든 포인트와 C1, C2 사이의 거리를 계산합니다. 만약 해당 포인트(테스트 데이터)가 C1에 더 가깝다면, 그 포인트에 ‘0’이라는 라벨을 붙입니다. 만약 C2에 더 가깝다면 ‘1’이라는 라벨을 붙이구요. (더 많은 중심점이 있다면 ‘2’, ‘3’ 등등이 되겠죠) 우리의 경우, ‘0’ 라벨은 빨간색으로, ‘1’ 라벨은 파란색으로 표시했습니다. 이 단계를 통해 아래와 같은 이미지를 얻을 수 있습니다.

3단계

파란색 포인트 전체와 빨간색 포인트 전체에 대한 각각의 평균을 계산하고 이 평균을 새로운 중심점으로 갱신합니다. 즉 C1과 C2는 새롭게 계산된 중심점으로 이동되겠죠. 그리고 2단계를 다시 수행합니다. 그럼 다음과 같은 결과가 얻어집니다.

2단계와 3단계를 반복하는데, 중심점 C1과 C2가 더 이상 변경되지 않을 때까지 반복합니다. (또는 반복 회수의 제한을 두던지.. 중심점의 변경시 이동 거리에 대한 기준 등을 만족할때까지 반복할 수도 있습니다.) 반복이 멈추게 되면, 중심점과 이들 중심점과 연관된 포인트 간의 거리의 합이 최소가 됩니다. 간단이 말해, 와 사이의 거리합이 최소입니다.

최종 결과는 아래와 같게 됩니다.

바로 이것이 K-Means 클러스터링에 대한 직관적인 이해이며, K-Means의 최상위 개념입니다. 여기에 다양한 변종과 응용이 추가됩니다. 예를들어 초기 중심점을 어떻게 결정하여 알고리즘의 속도를 향상시킬까 하는 등의 고민이 필요합니다.

이 글의 원문은 https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_ml/py_svm/py_svm_opencv/py_svm_opencv.html 입니다.

이 글은 kNN 대신 SVM를 사용한 OCR 기능을 OpenCV로 구현하는 예제에 대한 설명입니다.

kNN에서는 특징 벡터(Feature Vector)로써 픽셀의 밝기(Intensity)를 사용했습니다. 이번에는 특징 벡터로써 HOF(Histogram of Oriented Gradients)를 사용하도록 하겠습니다.

HOG를 찾기 전에, 먼저 이미지의 Moments(정확히는 Second Order Moments)를 사용해 기울어진 이미지를 보정합니다. 먼저 deskew() 함수를 정의할텐데, 이 함수는 숫자 이미지를 읽어 기울어진 모양을 바로 잡습니다. 아래는 deskew() 함수입니다.

SZ=20

affine_flags = cv2.WARP_INVERSE_MAP|cv2.INTER_LINEAR

def deskew(img):
    m = cv2.moments(img)
    if abs(m['mu02']) < 1e-2:
        return img.copy()
    skew = m['mu11']/m['mu02']
    M = np.float32([[1, skew, -0.5*SZ*skew], [0, 1, 0]])
    img = cv2.warpAffine(img,M,(SZ, SZ),flags=affine_flags)
    return img

아래의 이미지는 숫자 0에 대한 입력 이미지(왼쪽)를 deskew 함수에 적용한 결과(오른쪽)입니다.

다음은 각 셀의 HOG 디스크립터를 찾는 것입니다. 이를 위해, X축과 Y축 방향으로 각 셀의 Sobel 결과를 얻습니다. 그리고는 이 결과에 대한 각 픽셀에서 그레디언트(Gradient)의 크기와 방향을 얻습니다. 이 그레디언트는 16개의 정수값으로 변환합니다. 이 이미지를 4개의 부분 사각형으로 분할합니다. 각각의 부분 사각형에 대해, 이들의 크기값을 가지는 가중치 방향(16 Bins)의 히스토그램을 계산합니다. 그러면 각각의 부분 사각형을 통해 16개의 값을 가진 벡터가 생성됩니다. 4개의 각 벡터(4개의 부분 사각형)를 합치면 64개의 값을 갖는 특징 벡터를 얻게 됩니다. 이 특징 벡터를 훈련 데이터로 사용합니다. 아래의 코드는 지금까지의 설명에 대한 코드입니다.

bin_n = 16 # Number of bins

def hog(img):
    gx = cv2.Sobel(img, cv2.CV_32F, 1, 0)
    gy = cv2.Sobel(img, cv2.CV_32F, 0, 1)
    mag, ang = cv2.cartToPolar(gx, gy)
    bins = np.int32(bin_n*ang/(2*np.pi))    # quantizing binvalues in (0...16)
    bin_cells = bins[:10,:10], bins[10:,:10], bins[:10,10:], bins[10:,10:]
    mag_cells = mag[:10,:10], mag[10:,:10], mag[:10,10:], mag[10:,10:]
    hists = [np.bincount(b.ravel(), m.ravel(), bin_n) for b, m in zip(bin_cells, mag_cells)]
    hist = np.hstack(hists)     # hist is a 64 bit vector
    return hist

마지막으로, 이전 경우에서처럼, 숫자가 쓰여진 큰 이미지를 각 셀로 조각냅니다. 각 문자에 대해, 250개의 셀은 훈련 데이터로.. 나머지는 시험 테이터로 사용할 것입니다. 아래는 이에 대한 설명과 앞서 언급한 2개의 함수 모두를 합한 전체 코드입니다.

import cv2
import numpy as np

SZ=20

affine_flags = cv2.WARP_INVERSE_MAP|cv2.INTER_LINEAR

def deskew(img):
    m = cv2.moments(img)
    if abs(m['mu02']) < 1e-2:
        return img.copy()
    skew = m['mu11']/m['mu02']
    M = np.float32([[1, skew, -0.5*SZ*skew], [0, 1, 0]])
    img = cv2.warpAffine(img,M,(SZ, SZ),flags=affine_flags)
    return img

bin_n = 16 # Number of bins

def hog(img):
    gx = cv2.Sobel(img, cv2.CV_32F, 1, 0)
    gy = cv2.Sobel(img, cv2.CV_32F, 0, 1)
    mag, ang = cv2.cartToPolar(gx, gy)
    bins = np.int32(bin_n*ang/(2*np.pi))    # quantizing binvalues in (0...16)
    bin_cells = bins[:10,:10], bins[10:,:10], bins[:10,10:], bins[10:,10:]
    mag_cells = mag[:10,:10], mag[10:,:10], mag[:10,10:], mag[10:,10:]
    hists = [np.bincount(b.ravel(), m.ravel(), bin_n) for b, m in zip(bin_cells, mag_cells)]
    hist = np.hstack(hists)     # hist is a 64 bit vector
    return hist

img = cv2.imread('./data/digits.png',0)

cells = [np.hsplit(row,100) for row in np.vsplit(img,50)]

# First half is trainData, remaining is testData
train_cells = [ i[:50] for i in cells ]
test_cells = [ i[50:] for i in cells]

###### Now training ########################
deskewed = [list(map(deskew,row)) for row in train_cells]
hogdata = [list(map(hog,row)) for row in deskewed]
trainData = np.float32(hogdata).reshape(-1,64)
responses = np.repeat(np.arange(10),250)[:,np.newaxis]

svm = cv2.ml.SVM_create()
svm.setKernel(cv2.ml.SVM_LINEAR)
svm.setType(cv2.ml.SVM_C_SVC)
svm.setC(2.67)
svm.setGamma(5.383)

svm.train(trainData, cv2.ml.ROW_SAMPLE, responses)
svm.save('svm_data.dat')

###### Now testing ########################
deskewed = [list(map(deskew,row)) for row in test_cells]
hogdata = [list(map(hog,row)) for row in deskewed]
testData = np.float32(hogdata).reshape(-1,bin_n*4)
result = svm.predict(testData)[1]

####### Check Accuracy ########################
mask = result==responses
correct = np.count_nonzero(mask)
print(correct*100.0/result.size)

결과는 93.8로써 인식 성공률입니다. kNN에서의 인식률은 91.76였는데.. 그보다 더 나은 인식률을 보이고 있습니다.

이 글의 원문은 https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_ml/py_svm/py_svm_basics/py_svm_basics.html 입니다.

선형으로 분리될 수 있는 데이터

빨간색과 파란색에 대한 두 종류의 데이터에 대한 아래의 그림을 봅시다. kNN에서는, 테스트 데이터에 대해서, 훈련을 위한 전체 데이터와의 거리를 측정하여 최소 거리를 가지는 것 하나를 구했습니다. 이는 훈련 데이터 전체를 저장하고 모든 거리를 구해야 하므로 메모리를 많이 활용하고, 계산 시간도 많이 소요됩니다. 그러나 아래의 이미지처럼 주어진 데이터에 대해도 이처럼 많은 자원이 필요할까요?

생각을 바꿔서, 두 영역으로 데이터를 분리하는 어떤 선, 가 있습니다. 새로운 시험 데이터 가 있다면, 이를 에 대입해서, 이면 파란색 그룹에 속하고, 그렇지 않다면 빨간색 그룹에 속한다고 할 수 있습니다. 이러한 선을 결정 경계(Decsion Boundary)라고 부를 수 있습니다. 이는 매우 단순하며 메모리 효율성이 높습니다. 직선(또는 더 높은 차원에서는 평면)으로 두 영역으로 나눌 수 있는 이러한 데이터를 선형으로 나눠질 수 있다라고 합니다.

위의 이미지에서, 이러한 선은 매우 많습니다. 이 중 어떤 선을 선택해야 할까요? 매우 직관적으로, 모든 데이터로부터 가능한 멀리 떨어져 통과하는 선이라고 할 수 있습니다. 왜냐면, 입력 데이터에 잡음이 있을 수 있기 때문입니다. 이런 선은 분류 정확도에 영향을 줘서는 안됩니다. 가정 멀리 떨어진 선을 사용하는 것은 잡음에 대해 더 강하다는 의미입니다. 그래서 SVM(Support Vector Machines)이란 이러한 작선(또는 평면)을 얻는 것입니다. 아래의 그림에서 굷은 선이 바로 그 것입니다.

결정 경계(Decision Boundary)을 찾기 위해서는 훈련 데이터(Training Data)가 필요합니다. 그렇다면 전체 훈련 데이터가 필요할까요? 단지 상대 그룹과 가까운 것들만으로도 충분합니다. 위의 그림에서는 하나의 파란색 원과 두개의 빨간색 사각형이면 충분합니다. 바로 이 데이터를 지지 벡터(Support Vectors)라고 하며, 이 데이터를 통과하는 선들을 지지 평면(Support Planes)이라고 합니다. 이 것은 결정 경계를 구하는데 충분한 기반이 됩니다.

가장 멋진 지지 평면을 찾기 위한 수학적인 모델을 생각해 봅시다. 예를 들어서, 파란색 데이터는 로 나타낼 수 있는 반면, 빨간색 데이터는 로 나타낼 수 있습니다. 는 가중치 벡터(Weight Vector)()이며, 는 픽쳐 벡터(Feature Vector)()입니다. 는 편향(Bias)입니다. 가중치 벡터는 분리 경계의 방향을 결정하며, 편향은 위치를 결정합니다. 결정 경계는 이러한 평면 사이의 중앙을 지나는 것으로 정의될 수 있고, 로 표현할 수 있습니다. 지지 벡터에서 결정 경계 사이의 최소한의 거리는 로 주어집니다. 이 거리의 2배가 위 그림에서의 빈공간(Margin)이며, 이 빈공간이 최대화되어야 합니다. 예를들어, 아래와 같은 제약조건을 가지는 새로운 함수 를 최소화할 필요가 있습니다.

위의 식에서 는 인 각 군(class)의 라벨입니다.

비선형으로 분리할 수 있는 데이터

직선으로 분리할 수 없는 어떤 데이터를 생각해 봅시다. 예를 들어서, ‘X’가 -3과 +3이고 ‘O’가 -1과 +1인 1차원 데이터 말입니다. 이 데이터는 선형으로 분리될 수 없음이 명백합니다. 그렇지만 이러한 문제를 해결할 수 있는 방법이 존재합니다. 이 데이터를 함수를 통해 ‘X’는 9가 되고, ‘O’는 1이 되어 선형으로 분리되어 집니다.

반면에 1차원 데이터를 2차원 데이터로 변환할 수 있습니다. 함수를 이용해 ‘X’는 (-3,9)와 (3,9)가 되고 ‘O’는 (-1,1)과 (1,1)이 되며, 이는 선형으로 분리됩니다. 요약하면, 낮은 차원 공간에서의 비선형으로 분리되어지는 데이터는 더 높은 차원 공간에서는 선형으로 분리될 수 있는 더 많은 가능성이 있습니다.

일반적으로 D>d일때, d차원 공간에서의 포인트들이 D-차원 공간으로 맵핑될때 선형으로 분리될 가능성이 높아집니다. 여기에 낮은 차원으로 입력된 (피쳐;feature) 공간에서의 계산으로 높은 차원 (커널;kernel) 공간에서 내적(dot product)를 계산하는데 도움이 되는 방법이 존재합니다. 다음의 예로 설명해 보겠습니다.

2차원 공간에서 2개의 포인트(, )를 생각해 봅시다. 를 2차원에서 3차원 공간으로 맵핑하는 함수라고 할때 아래와 같습니다.

커널 함수 를 아래와 같이 정의하면, 이 함수는 두 포인트 사이의 내적(dot product)입니다.

이는, 3차원 공간에서의 내적은 2차원 공간에서의 내적의 제곱이라는 의미입니다. 이를 더 높은 차원의 공간에서 적용할 수 있습니다. 그래서 더 낮은 차원에서의 데이터를 그대로 더 높은 차원으로 계산할 수 있습니다. 일단 이렇게 맵핑되면, 더 높은 차원의 공간에서의 데이터를 얻을 수 있습니다.

지금까지의 모든 개념에 덧붙여, 여기에는 잘못된 분류에 대한 문제가 존재합니다. 그래서 단순히 최대 빈공간(Margin)을 갖는 결정 경계(Decision Boundary)를 찾는 것만으로는 충분하지 않습니다. 잘못된 분류에 대한 문제도 함께 고려해야 합니다. 때때로, 더 나은 분류를 제공하는 더 작은 빈공간을 갖는 결정공간이 존재할 수 있습니다. 어째거나, 최대한의 빈공간을 가지면서 더 적은 분류 오류를 제공하는 결정 경계를 찾아야만합니다. 최소화된 기준은 다음과 같습니다.

아래 그림이 이러한 개념을 나타냅니다. 훈련 데이터의 각 샘플에 대해서, 새로운 파라메터 가 정의됩니다. 이 파라메터는 훈련 데이터와 수정된 결정 영역 사이의 거리입니다. 여기에는 잘못된 분류가 없는데, 지지 평면에 샘플 데이터가 옳바르게 떨어지고, 거리는 0입니다.

이제 새로운 최적화된 문제는 다음과 같습니다.

위의 식에서 인자 C는 어떻게 정해야 할까요? 이에 대한 대답은 시험 데이터가 어떻게 분포되었느냐에 따라 결정된다입니다. 비록 일반화된 방법은 없지만 다음과 같은 규칙을 따르면 좋습니다.

• 큰 C 값은 분류에 대한 작은 오차를 제공하지만 빈공간(Margin)이 더 작아지게 된다. 최적화의 목표가 인자의 최소화에 있으므로, 약간의 분류 오차가 허용된다.
• 작은 C 값은 더 큰 빈공간을 제공하지만 분류 시 더 많은 오차가 존재한다. 큰 빈공간을 가지는 평면을 찾는 것에 더 중요한 목표이므로 최소화는 고려되지 않는 경우이다.