[BOJ 15636] Linear Algebra and Group

머신러닝 및 데이터 다루기 연습문제로 딱이야~

머릿말

이걸 노가다로 풀어야하나 고민하던 문제입니다. 하지만 최근에 머신러닝과 파이썬을 공부하고 있으니 예제로 적당해보여 풀어봤습니다.

@veydpz 님의 좋은 풀이가 있긴하지만 참고할 곳이 많이 없어 이렇게 포스팅합니다.

editorial

문제 본문

BOJ 15636 : Linear Algebra and Group

Linear Algebra and Group

승원이는 배경지식 없이는 못 푸는 문제를 만들기 위해 “선형대수와 군”(이인석, 개정판)을 읽고 있었다. 하지만 승원이도 이 책을 이해하지 못하고 있기 때문에, 배경지식이 필요한 문제 대신 책이 없는 사람들이 못 풀 문제를 만들기로 했다.

책 앞표지의 그림에 있는 모든 숫자(0~9)들의 합을 구하시오.

입력

이 문제의 입력은 없다.

출력

그림에 있는 모든 숫자의 합을 출력한다. 그림 밖의 숫자들은 포함되지 않는다.

문제 풀이

기본적인 아이디어

공식 풀이를 보기전에 문제에 대한 풀이는 기본적으로 3가지 방법을 생각해보았다.

1. 직접 세기
2. MNIST를 이용한 판별
3. 색으로 분류

1은 너무 컴공틱하지 못하고, 2번과 3번 중에 고민이었다. 하지만 2번의 경우에는 MNIST 예제에서 모델을 가져와야하고, 훈련에도 시간이 걸리니 3번 방법으로 선택하였다.

이미지 다운로드

이부분은 수동으로 했다. 정해에서 알려준 고화질 사진을 대충 크기에 맞게 잘라 보았다.

(손으로 해도 비슷한 시간에 나왔겠다.)

이제 이 이미지를 파이썬으로 되는대로 많이 처리해보자.

사용된 모듈들

파이썬으로 데이터를 다루는 건 아직 익숙하지 않아 어려웠다.

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
from mpl_toolkits.mplot3d import Axes3D

from sklearn.cluster import KMeans
from PIL import Image

import shutil
import os

크게는 배열 처리, 그래프 및 이미지 처리, 파일 입출력 정도로 나눌 수 있다.

이미지 자르기

우선 이 이미지를 한칸에 숫자가 1개가 들어오도록 하는 것이 목표다. 그래서 손으로 세기 싫어서 이분 탐색처럼 반복해서 29 by 50 임을 알 수 있었다.

이미지를 잘라서 개별로 저장하는 것은 PIL 모듈에서 Image를 사용하여 잘랐다.

os.makedirs()로 디렉터리를 만들고, Image.open()으로 png파일을 연다.

그리고 img.crop()을 이용해서 파일을 다 자른다. 각 파일의 이름은 0번부터 1449번까지로 이름을 지정했다.

# 이미지 파싱하기 : 29 * 50 사이즈
def image_crop( file_name , save_path):
    os.makedirs(os.path.join("./nums"))
    img = Image.open( file_name )
    (img_w, img_h) = img.size

    # 자를 개수 지정
    range_h = 29
    range_w = 50
    # 개당 사이즈
    grid_h = (img_h/range_h)
    grid_w = (img_w/range_w)

    # 이미지 저장하기
    idx = 0
    for h in range(range_h):
        for w in range(range_w):
            bbox = (w*grid_w, h*grid_h, (w+1)*(grid_w), (h+1)*(grid_h))
            crop_img = img.crop(bbox)
            fname = "{}.png".format("{0:04}".format(idx))
            save_name = save_path + fname
            crop_img.save(save_name)
            idx += 1
    return idx

다음 함수를 이용해서 파일이 정확하게 1칸에 숫자 1개씩으로 매칭되는 지 체크하면서 파일을 돌려보았다.

그래프로 확인하기 2D

이렇게 잘린 이미지를 어떻게 활용할 것인가가 문제였다. 이때의 고민은 이 정도로 정리할 수 있다.

• 이미지를 어떤식으로 뽑아낼 것인가 : numpy, pandas 알못
• 어떤식으로 산점도를 그릴 것인가. : matplotlib 알못
• 산점도가 안나오면 어쩌지 였다. : 머신러닝으로 뭐 해본적없음

2개 이상의 축을 사용하여 그래프를 산점도로 그려보면 군집이 잘 잡힐 것이라 가정했다. 가장 걱정이 된 부분은 3과 4의 분류였다. 두 수 모두 노란색 베이스에 화질이 그렇게 좋지 못해 어떤식으로 자료를 선택해야하는 가 고민이었다.

이미지에 대한 정보는 2가지로 선택할 수 있다.

• background RGB mean value
• background RGB max value

각각의 숫자는 검정색이고 비슷한 크기를 지니고 있어 평균으로 하면 색이 잘 분류될 것이라고 생각했다. png파일은 numpy로 바꾸면 rgba 채널을 가진다. 여기서 a는 alpha 채널로 색에 큰 영향을 주지 못하기 때문에 제외했다. 그렇다면 각각 background의 rgb값 중 2개의 값으로 그래프를 그리면 분류가 될 것이라고 가정했다. (왜냐면 3차원 그래프는 그려본적이 없으므로..)

하지만 그래프를 그려보니 군집이 9개 밖에 안나왔다… 그래서 MNIST로 할까 생각하다 3D를 도전해보았다.

그래프로 확인하기 3D

그래서 결국은 3D 그래프를 그리기로 했다. 거기다가 평균 색을 각 포인트에 줘서 그리면 보기 좋지 않을까라고 생각했다.

def clustering(cnt):
    # r, g, b = x, y, z
    x = np.array([])
    y = np.array([])
    z = np.array([])
    C = np.array([]) # color info

    # 반복문으로 각 사진 정보 추출
    for i in range(cnt):
        file_path = './nums/{}.png'.format("{0:04}".format(i))
        jpg_img_arr = mpimg.imread(file_path) # mpimg로 np.array로 변환하여 읽을 수 있다.
        jpg_img_arr = jpg_img_arr[3:-3, 3:-3,] # 보다 검정(테두리)값을 지우므로 노이즈 줄임
        x = np.append(x,np.mean(jpg_img_arr[:,:,0])) # R
        y = np.append(y,np.mean(jpg_img_arr[:,:,1])) # G
        z = np.append(z,np.mean(jpg_img_arr[:,:,2])) # B
        C = np.append(C,[np.mean(jpg_img_arr[:,:,0]), np.mean(jpg_img_arr[:,:,1]), np.mean(jpg_img_arr[:,:,2])]) # RGB

    C = C.reshape(1450, 3)

    # 이미지 그리기
    fig = plt.figure()
    ax = fig.add_subplot(111,projection='3d')
    ax.scatter(x,y,z, c = C)
    plt.draw()
    fig.savefig('visualize_data.png', dpi = 100)

열심히 구글링 결과 다음과 같은 그래프를 그릴 수 있었다. 생각보다 군집이 너무 잘 분류되어 있었고, 이제 이를 어떤식으로 분류할까 생각해보자.

비지도학습 : K means 알고리즘

현재 가지고 있는 데이터는 문제 데이터밖에 없으므로 비지도 학습을 구현해볼 기회였다. 다음과 같이 군집이 잘 이루어진 데이터셋에서는 K-means 알고리즘이 잘 적용될 것으로 예상했다. 그렇기에 위의 함수에서 연장하여 다음과 같은 코드를 추가하여 군집을 분류했다.

    df = pd.DataFrame(columns=('r','g','b')) # kmeans를 하기 위한 전처리
    # numpy.array to pandas.DataFrame
    idx = 0
    for c in C:
        df.loc[idx] = c
        idx += 1
    data_points = df.values
    # kmeans algorithm in sklearn.cluster
    kmeans = KMeans(n_clusters=10).fit(data_points)

    # 분류용 디레터리 만들기
    for i in range(10):
        os.makedirs(os.path.join("./nums/{}".format(i)))

    cnt_num = [0]*10 # 개수 저장

    # 클러스터링 별로 파일 이동
    for i in range(cnt) :
        cnt_num[kmeans.labels_[i]] +=1
        file_name = '{}.png'.format("{0:04}".format(i))
        src = './nums/'
        dir = './nums/{}/'.format(kmeans.labels_[i])
        shutil.move(src+file_name, dir+file_name)

    print(cnt_num) # 각 군집 개수 출력

각 디렉토리 별로 분류를 한 이유는 개수 재확인 및 잘못된 값 체크를 하기 위함이었다.

전체 코드 및 결과물

전체 코드는 다음과 같다. 100줄도 안되는 코드다.

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import shutil
import os
from sklearn.cluster import KMeans
from mpl_toolkits.mplot3d import Axes3D
from PIL import Image


# 이미지 파싱하기 : 29 * 50 사이즈
def image_crop( file_name , save_path):
    os.makedirs(os.path.join("./nums"))
    img = Image.open( file_name )
    (img_w, img_h) = img.size

    # 자를 개수 지정
    range_h = 29
    range_w = 50
    # 개당 사이즈
    grid_h = (img_h/range_h)
    grid_w = (img_w/range_w)

    # 이미지 저장하기
    idx = 0
    for h in range(range_h):
        for w in range(range_w):
            bbox = (w*grid_w, h*grid_h, (w+1)*(grid_w), (h+1)*(grid_h))
            crop_img = img.crop(bbox)
            fname = "{}.png".format("{0:04}".format(idx))
            save_name = save_path + fname
            crop_img.save(save_name)
            idx += 1
    return idx

# 이미지 중앙 부분 np.array로 변환
def clustering(cnt):
    x = np.array([])
    y = np.array([])
    z = np.array([])
    C = np.array([]) # color 입히기
    for i in range(cnt):
        file_path = './nums/{}.png'.format("{0:04}".format(i))
        jpg_img_arr = mpimg.imread(file_path)
        jpg_img_arr = jpg_img_arr[3:-3, 3:-3,] # 테두리 자르기
        x = np.append(x,np.mean(jpg_img_arr[:,:,0]))
        y = np.append(y,np.mean(jpg_img_arr[:,:,1]))
        z = np.append(z,np.mean(jpg_img_arr[:,:,2]))
        C = np.append(C,[np.mean(jpg_img_arr[:,:,0]), np.mean(jpg_img_arr[:,:,1]), np.mean(jpg_img_arr[:,:,2])])

    C = C.reshape(1450, 3)
    fig = plt.figure()
    ax = fig.add_subplot(111,projection='3d')
    ax.scatter(x,y,z, c = C)
    plt.draw()
    fig.savefig('visualize_data.png', dpi = 100)

    df = pd.DataFrame(columns=('r','g','b'))
    idx = 0
    for c in C:
        df.loc[idx] = c
        idx += 1
    data_points = df.values
    kmeans = KMeans(n_clusters=10).fit(data_points)

    # 디레터리 만들기
    for i in range(10):
        os.makedirs(os.path.join("./nums/{}".format(i)))

    cnt_num = [0]*10
    print(len(kmeans.labels_))
    # 클러스터링 별로 파일 이동
    for i in range(cnt) :
        cnt_num[kmeans.labels_[i]] +=1
        file_name = '{}.png'.format("{0:04}".format(i))
        src = './nums/'
        dir = './nums/{}/'.format(kmeans.labels_[i])
        shutil.move(src+file_name, dir+file_name)
    print(cnt_num)

if __name__ == '__main__':
    cnt = image_crop('sample.png', './nums/') # file_name과 save_path
    clustering(cnt)

그 결과 다음과 같은 결과를 얻을 수 있었다. 다음은 결과 예시이다.

분류 0번과 7번 파일 결과

마지막

이제는 각 파일별로 어떤 숫자이고, 잘못된 데이터를 찾으면 된다. 잘못된 데이터는 없었고, 계산결과 정답이었다.

실수로 한 번 틀렸는데, 코드를 여러번 돌리면서 이전 파일을 삭제하지 않아 숫자 폴더에 1개씩 데이터가 더 들어갔다. 그래서 첫 제출에 45를 빼서 제출하니 정답이었다.

맺음말

문제를 풀며 데이터 처리하는 능력이 조금은 향상된 것 같다. 요즘 다시 BOJ에 한 문제씩 푸는데 재밌다. 좀 더 연습하고 캐글 예시들도 풀어봐야겠다.

출처 : BOJ 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음