레이블이 Project인 게시물을 표시합니다. 모든 게시물 표시
레이블이 Project인 게시물을 표시합니다. 모든 게시물 표시

월요일, 9월 18, 2017

[Python] 텍스트 분류하기 (Text Classification)

월요일, 9월 18, 2017
1. 개요
이 글에서는 Python을 사용해서 문서의 내용 혹은 주제를 분류(Classification)하는 토이 프로젝트를 진행하는 것을 목표로 한다. 심화적인 내용보다는 기본적인 내용을 다루고, 이를 어떻게 개선하고 확장할 수 있는지 살펴볼 것이다.
우선 분류를 수행하기 위해서는 특정 정보를 바탕으로 학습된 모델이 필요하다. 이 프로젝트에서는 CNN의 기사들을 주제별로 크롤링(Crawling)한 뒤, 기사 전문과 그에 대한 라벨(주제)를 한 쌍으로 묶어서 트레이닝 데이터로 활용한다. 이를 통해 학습을 진행하고 특정 텍스트를 테스트 데이터로 제공했을 때 해당 텍스트가 어떤 주제에 속하는지 분류해주는 모델을 만든다. 여러가지 방법 중에서도 가장 대표적인 벡터 공간 모델(Vector Space Model)의 개념을 활용하도록 한다.

2. 트레이닝 데이터 준비
Python으로 CNN의 기사들을 크롤링해보자. 준비물로는 Python 모듈로 제공되는 Beautiful Soup, urllib, NLTK이다. 이 세 가지 모듈의 설치와 관련된 내용은 다른 포스트에서 다루도록 하겠다. 대략적으로 말하자면 Beautiful Soup와 urllib은 웹사이트로부터 데이터를 쉽게 크롤링하기 위한 도구이고, NLTK는 자연어처리와 관련된 다양한 전처리를 하기 위한 도구이다.
크롤링에 앞서 데이터를 긁어올 웹페이지가 어떠한 구조로 되어 있는지 확인할 필요가 있다. Chrome 브라우저를 통해 CNN의 웹페이지(http://edition.cnn.com)에 접속하여 특정 기사를 클릭한 뒤, F12를 눌러서 개발자 도구를 활성화하면 웹페이지의 구조를 확인할 수 있다.
이 프로젝트에서 필요한 것은 헤드라인과 본문의 텍스트 데이터뿐이므로, 이 부분들만 크롤링하도록 한다. 첫 단락은 p태그로 묶여 있고, 두 번째 단락부터 본문 끝까지는 div태그로 묶여있음에 유의해야 한다. 특정 기사의 URL로부터 헤드라인과 본문의 텍스트 데이터를 크롤링하여 문자열로 반환하는 것은 다음과 같이 Python 코드로 쉽게 구현할 수 있다.
import bs4
import urllib.request
htmlData = urllib.request.urlopen(inputurl)
bs = bs4.BeautifulSoup(htmlData, 'lxml')
bodies = bs.findAll('h1', 'pg-headline')
bodies += bs.findAll('p', 'zn-body__paragraph')
bodies += bs.findAll('div', 'zn-body__paragraph')
inputstr = ""
for body in bodies:
    inputstr += (body.getText() + " ")
이 코드는 문자열 타입의 URL(inputurl)을 받아 크롤링 결과물을 문자열(inputstr)로 만들어준다.
이를 통해 여러 기사들을 분류별로 나누어 파일로 저장해놓자. 우선 Entertainment, Golf, Politics 세 가지 주제에 대해 폴더를 만들어놓고, 각각의 폴더 안에 해당 주제에 대한 기사들을 20여개 정도 저장하였다. 문자열을 파일에 출력하는 것은 위의 코드와 Python에 기본으로 내장된 파일 입출력 관련 함수들(open, write 등)을 사용하여 간단히 구현하면 된다.

3. 분류 모델 준비
분류 모델은 다양한 방법으로 설계할 수 있다. 자연어처리의 영역에서 소개하는 여러 복잡한 방법들이 존재하지만, 우선 이 글에서는 가장 기초적이면서 대표적인 코사인 유사도(Cosine Similarity)를 활용하도록 한다. 위키피디아에 따르면 코사인 유사도의 정의는 다음과 같다.
코사인 유사도(― 類似度, 영어: cosine similarity)는 내적공간의 두 벡터간 각도의 코사인값을 이용하여 측정된 벡터간의 유사한 정도를 의미한다. 각도가 0°일 때의 코사인값은 1이며, 다른 모든 각도의 코사인값은 1보다 작다. 따라서 이 값은 벡터의 크기가 아닌 방향의 유사도를 판단하는 목적으로 사용되며, 두 벡터의 방향이 완전히 같을 경우 1, 90°의 각을 이룰 경우 0, 180°로 완전히 반대 방향인 경우 -1의 값을 갖는다.
그리고 두 벡터 A, B의 코사인 유사도를 구하는 공식은 다음과 같다.
즉, A와 B를 내적한 뒤 두 벡터의 길이의 곱으로 나눠주면 된다. 이는 NumPy를 사용한다면 Python 코드로 간단하게 구현할 수 있다.
import numpy
def cosSimilarity(A, B):
    multi = (A.dot(B))
    x = math.sqrt(A.dot(A))
    y = math.sqrt(B.dot(B))
    result = multi / (x * y)
    return result
그렇다면 이제 남은 것은 각각의 기사를 벡터화(Vectorization)하는 것이다. 물론 이 벡터화를 위한 방법론도 정말 다양하고 활발한 연구가 진행되고 있지만, 자세한 내용은 뒤에서 다루도록 하고 이 프로젝트에서는 가장 기초적인 방법부터 사용해보도록 하자.

우선 첫 번째로 할 일은 크롤링을 통해 수집한 기사들을 한 번씩 훑으면서, 사용된 모든 단어의 목록을 만드는 것이다. 이를 이후에는 편의상 Vocabulary라고 하겠다. 이 Vocabulary는 일종의 자료구조이며, 만족해야 할 조건은 트레이닝 데이터에 사용된 모든 단어를 중복없이 하나씩 포함해야 한다는 것이다. 그리고 각각의 단어들은 인덱싱을 통해 쉽게 접근할 수 있어야 한다. 예를 들어, "I love you"라는 트레이닝 데이터로부터 Vocabulary를 생성한다면, 다음과 같은 형태로 단어들이 저장될 것이다.
0: I
1: Love
2: You
간단히 1차원 배열로도 구현할 수 있으나, 이 Vocabulary라는 개념 자체가 자연어처리에서 널리 활용되는 개념이기 때문에 확장성을 고려하여 해싱(Hashing)을 사용한 자료구조로 만들도록 하자. 해싱을 적절히 사용한다면, Vocabulary에 저장된 단어에 대해 인덱스로도 접근이 가능한 동시에 단어 자체로도 접근이 가능하여 강력한 검색 기능을 탑재하게 된다.
이러한 조건들을 만족하는 Vocabulary 클래스를 만들어보자.
import numpy as np
# Set of vocabularies with indices
class Vocabulary:
    def __init__(self):
        self.vector = {}
    def add(self, tokens):
        for token in tokens:
            if token not in self.vector and not token.isspace() and token != '':
                self.vector[token] = len(self.vector)
    def indexOf(self, vocab):
        return self.vector[vocab]
    def size(self):
        return len(self.vector)
    def at(self, i): # get ith word in the vector
        return list(self.vector)[i]
    # vectorize = dict -> numpy.array
    def vectorize(self, word):
        v = [0 for i in range(self.size())]
        if word in self.vector:
            v[self.indexOf(word)] = 1
        else:
            print("<ERROR> Word \'" + word + "\' Not Found")
        return np.array(v)
    def save(self, filename):
        f = open(filename, 'w', encoding='utf-8')
        for word in self.vector:
            f.write(word + '\n')
        f.close()
    def load(self, filename):
        f = open(filename, 'r', encoding='utf-8')
        lines = f.readlines()
        bow = [i[:-1] for i in lines]
        self.add(bow)
        f.close()
    def __str__(self):
        s = "Vocabulary("
        for word in self.vector:
            s += (str(self.vector[word]) + ": " + word + ", ")
        if self.size() != 0:
            s = s[:-2]
        s += ")"
        return s
코드를 살펴보면 알겠지만, Python에서 기본적으로 제공하는 Dictionary 자료구조가 Hash Set과 동일한 역할을 해주기 때문에 이를 기본으로 하되, index를 통해 접근할 수 있도록 at()과 indexOf()같은 함수들을 구현해 두었다.

4. 분류 모델 학습
모든 준비가 완료되었으므로 실제 모델을 학습하는 것만 남았다. 먼저 앞서 구현한 Vocabulary 클래스를 통해 트레이닝 데이터로 준비한 60개의 문서에 대해 Vocabulary를 생성해야 한다. 이 Vocabulary를 활용하여 각 문서에 나타나는 단어들의 빈도수를 체크하고, 이를 바탕으로 문서 자체를 벡터화하여 분류 기준을 마련할 것이다. 즉, 문서 하나를 벡터 공간 내에서 하나의 점으로 표현하는 Vector Space Model의 개념을 따르는 것이다.

그런데, 한 가지 주의할 사항이 있다. 문서에서 단어들을 어떻게 뽑아낼 것인가? 띄어쓰기(공백 문자)를 기준으로 끊어서 하나의 단어라고 할 수도 있을 것이다. 하지만, 이러한 방법을 채택할 경우 다음과 같은 문장으로부터 어떤 단어를 얻게 될까?
나는 사과를 좋아하는데, 영희는 사과만 싫어한다.
정답은 ["나는", "사과를", "좋아하는데,", "영희는", "사과만", "싫어한다."]이다. 우선 쉼표나 온점같은 특수문자가 단어에 포함된다. 이는 문서의 의미를 이해하는데 꼭 필요한 정보라고는 할 수 없다. 그리고 상식적으로 "사과"라는 단어가 이 문장의 키워드 중 하나라고 여길 수 있는데, 이것이 하나의 단어로 뽑히는 것이 아니라 "사과를", 그리고 "사과만" 두 가지 형태로 나타나게 된다. 앞선 경우와 마찬가지로 우리말의 조사는 큰 의미를 반영하지 않는다. 게다가 단어의 빈도수를 측정할 때 문제를 야기할 소지가 있다. "사과"와 관련된 문서를 찾기 위해 "사과"라는 단어가 가장 많이 포함된 문서를 찾으려고 하는데, 모든 문서 내에 "사과를", "사과만"이라는 단어만 잔뜩 포함되어 있다면 정상적인 시스템이라고 할 수 없지 않는가. 따라서 이러한 불필요한 요소들을 제거할 필요성이 있다.

이를 위해 트레이닝 데이터로부터 Vocabulary를 형성하기 전에 전처리를 수행해주도록 하자. 앞서 언급했던 여러가지 불필요한 요소들을 Stop Words라고 부르고, 우리말의 조사나 영어의 복수형에 붙는 s 등을 없앤 어간을 Stem이라고 한다. 이들을 처리하기 위한 유용한 툴이 NLTK 라이브러리에 전부 구현되어 있다. 필요한 부분에 가져다 쓰기만 하면 된다.

크롤링을 통해 긁어온 문자열을 Input으로 받아서 Stop Words를 제거하고 Stem만 남겨주는 preprocess() 함수를 구현하자.
import nltk
from nltk.corpus import stopwords

# preprocess = str -> nltk.Text
def preprocess(inputstr):
    inputstr = inputstr.lower()
    tokens = nltk.word_tokenize(inputstr)
    stpwrds = set(stopwords.words('english'))
    tokens = [i for i in tokens if i not in stpwrds and i.isalpha()]
    stemmer = nltk.stem.porter.PorterStemmer()
    stems = [stemmer.stem(i) for i in tokens]
    text = nltk.Text(stems)
    return text
중간에 PorterStemmer()라는 것은 Stem을 만들어주는 여러가지 방법 중 Porter Stemming Algorithm을 사용한다는 뜻이다. 이외에도 여러가지 방법들이 있고, 함수로 구현되어 있으니 관심이 있다면 직접 검색해보길 권한다.

이제 이 전처리를 수행한 뒤 모든 트레이닝 데이터에 대해 Vocabulary에 단어들을 수집하면 된다. preprocess() 함수는 nltk.Text 타입의 객체를 반환하는데, 이 객체의 내부 함수인  vocab() 함수를 호출하면 단어로 이루어진 리스트(List) 자료구조를 반환한다.

다음과 같은 방식으로 코드를 작성하면 된다. x_training_file이라는 파일 안에는 트레이닝 데이터로 활용하고자 하는 문서 중 주제가 x에 해당하는 문서들의 URL이 20개 저장되어 있다고 가정한다. 그리고 getTextFromURL() 함수는 2에서 설명한 방식대로 URL을 Input으로 받아 문자열을 Output으로 반환하는 함수이다.
myvoc = Vocabulary()
f = open(PATH_TRAINING_DATA + golf_training_file)
lines = f.readlines()
for line in lines:
    tmp = getTextFromURL(line)
    bow = preprocess(tmp)
    myvoc.add(bow)
f.close()
이러한 방식으로 모든 트레이닝 데이터에 대해 단어를 수집하면 된다. Vocabulary가 완성되었다면, 본격적으로 Vocabulary 클래스의 vectorize() 함수를 통해 단어 하나를 One-hot Encoding 방식으로 벡터화할 수 있다.
myvoc.vectorize("apple")
이를 활용하여 한 문서에 존재하는 모든 단어들을 벡터로 만들고, 그 벡터들을 전부 더하도록 하자. 그렇다면 문서 하나가 하나의 벡터가 되는데, 쉽게 생각하면 이 벡터는 문서 하나에 나타나는 단어들의 빈도수를 표현하게 되는 것이다. One-hot Encoding 방식으로 단어가 벡터화되었기 때문에 같은 단어가 여러 번 나타날 경우, 해당 단어의 인덱스에 해당하는 벡터의 원소만 증가하게 된다.
이 개념을 통해 트레이닝 데이터셋의 모든 문서들을 각각 벡터로 만들고, 주제별로 평균을 내도록 하자. 이 평균값이 해당 주제에 대한 대표 벡터이자 분류 기준이라고 보면 된다. 참고로 이 글에서는 Cosine Similarity를 사용하기 때문에, 평균을 구하지 않고 각 벡터들의 합만 구해도 된다. 벡터의 방향성이 얼마나 유사한지를 판단하는 방법이라 벡터의 길이는 상관이 없기 때문이다.

Entertainment, Golf, Politics 세 가지 주제에 대해 각각 벡터를 하나씩 얻었다면, 분류 모델이 완성된 것이다. 이를 통해 특정 문서에 대한 분류를 수행하기 위해서는 문서를 벡터화하는 과정을 동일하게 진행한 뒤, 해당 벡터를 준비된 세 가지 벡터들과 각각 비교하여 가장 Cosine Similarity가 높은 주제로 분류를 하면 된다. 주의할 점은, 학습 모델을 만들 때 사용한 Vocabulary를 그대로 사용해야 한다는 것이다. 그래야 특정 단어가 학습 모델에 맞게 제대로 벡터화되기 때문이다.

굉장히 간단하고 기초적인 모델이지만, 직접 분류를 해보면 꽤 의도한 대로 결과가 나오는 것을 확인할 수 있다. 실제 실험을 진행한 뒤 Matplotlib와 같은 라이브러리를 통해 시각화를 했더니 다음과 같은 결과가 나타났다.
Entertainment, Golf, Politics 세 가지 주제에 대해 각각 하나씩의 임의의 CNN 기사를 크롤링하여 분류를 한 결과 세 가지 경우 모두 정답을 도출했다.

5. 향후 발전방향
이 기초적인 프로젝트를 개선하고 확장하면 더욱 높은 성능을 기대할 수 있다. 이를 위해서 어떠한 점들을 개선해야 하는지 몇 가지 살펴보도록 하겠다.

우선, 각 벡터 사이의 유사도를 측정하는데 있어서 Cosine Similarity 이외에 자카드 유사도(Jaccard Similarity)를 구하는 방법도 많이 쓰인다. 두 방법 중 한 가지를 선택하거나, 둘을 적절히 조합하여 유사도를 측정하는 방식을 쓸 수도 있다. 모델을 설계하는 단계에서 입맛대로 사용하면 된다.

또한 Vocabulary를 생성하는 과정에서 Stop Word들을 제거하거나 Stemmer를 사용함에 있어서 과연 무조건적인 Stop Words의 배제가 바람직한 것인지, 특정 Stemmer의 성능이 어떠한 경우에 좋은지 등 추가적으로 고려할 요소들이 많다.

사실, 가장 중요한 부분은 바로 문서, 단어를 벡터화하는 방식이다. 이 글에서는 그저 단어들의 빈도수를 도출해서 그것들을 합한 것에 지나지 않지만, 실제 정보 검색 분야나 자연어처리 분야에서는 Doc2Vec, Word2Vec 등 머신러닝 기반의 다양한 벡터화 방법론이나 TF-IDF처럼 문서와 관련하여 각 단어의 중요도에 대해 고려하는 통계적 기법들이 널리 활용되고 있다. 특히 TF-IDF는 각 문서의 주제와 직결되는 중요한 단어들이 무엇인지 고려해준다는 점에서, 앞서 언급했던 Stop Word의 존재에 대한 걱정거리를 어느정도 덜어주기도 한다.

이러한 다양한 방법들을 적절히 조합하고 적용하면 더욱더 강력한 텍스트 분류 모델이 완성될 것이다. 이 글의 토이 프로젝트를 통해 가장 기본적인 요소들에 대해 학습하고, 향후 개선과 확장을 통해 고도의 분류 시스템을 설계하는 단계까지 나아가도록 하자.

6. References
https://ko.wikipedia.org/wiki/%EC%BD%94%EC%82%AC%EC%9D%B8_%EC%9C%A0%EC%82%AC%EB%8F%84

일요일, 9월 11, 2016

System Project: CPU Scheduling Simulator

일요일, 9월 11, 2016

1. Introduction
2016년 1학기 운영체제 수업에서 텀프로젝트로 진행했던 CPU Scheduling Simulator이다. 프로세스의 생명주기를 실제와 유사하게 표현하였고, 다양한 스케줄링 알고리즘들을 구현하여 각각의 알고리즘마다 어떤식으로 스케줄링이 이루어지며, 성능은 어떤지 비교분석을 해준다.
원활한 시뮬레이션을 위해 프로세스마다 CPU Burst Time을 예측할 수 있다는 전제를 바탕으로 하며, 조금 더 현실에 가깝게 하기 위해 I/O 작업을 수행하는 프로세스도 구현하였고, 역시 I/O 작업을 수행하는데 걸리는 시간도 예측할 수 있다고 전제하였다.
시뮬레이션을 하기 위한 프로세스의 갯수와, 그 중에서 I/O 작업을 수행할 프로세스의 갯수를 사용자로부터 입력받아서 여러 알고리즘들을 통해 시뮬레이션한 결과를 출력해준다.

2. Demo

3. 개발 환경
Ubuntu 16.04 LTS 환경에서 C언어로 작성하였으며, 컴파일러는 gcc 5.4.0 버전을 사용하였다. 콘솔 기반의 프로그램이기 때문에 입력과 출력이 모두 콘솔상에서 이루어진다.

4. 구현 알고리즘
FCFS (First Come First Served)
- 가장 먼저 Job Queue에 도착한 프로세스가 가장 먼저 수행되는 알고리즘이다.

SJF (Shortest Job First)
- CPU Burst Time이 가장 적게 남은 프로세스가 먼저 수행되는 알고리즘이다. Preemptive와 Non-preemptive 방식 총 두 가지로 구현하였다.

Priority
- 미리 설정된 Priority값을 기준으로 프로세스의 수행 순서를 결정해주는 알고리즘이다. 이 프로그램에서는 Priority값이 낮은 프로세스가 더 우선권을 가진다. SJF 알고리즘과 마찬가지로 Preemptive와 Non-preemtive 방식 두 가지를 모두 구현하였다.

Round Robin
- 시스템에 설정된 Time Quantum을 기준으로 일정 시간마다 수행될 프로세스를 변경해주는 방식이다. Time Quantum이 만약 무한대라면, 특정 프로세스가 먼저 리소스를 점거할 경우 종료가 될 때까지 다른 프로세스들이 수행되지 않기 때문에, FCFS 방식과 동일해진다.

LIF (Longest I/O First)
- I/O 작업을 수행하는 시간이 긴 프로세스가 후반부에 스케줄링될 경우 CPU의 유휴상태가 발생할 확률이 높아진다는 점에 착안하여 가장 I/O Burst Time이 큰 프로세스부터 우선적으로 스케줄링해주는 방식이다. Preemptive / Non-preemptive 방식 둘 다 구현하였다.

LISC (Longest I/O & Shortest CPU First)
- LIF가 CPU Burst Time을 고려해주지 않는다는 단점을 보완하여 CPU Burst Time도 스케줄링에 반영한 알고리즘이다. Preemptive / Non-preemptive 방식 둘 다 구현하였다.

5. 사용법
Github에서 실행파일(CPUScheduler)을 다운받아서 콘솔에서 실행시키면 된다. 이때 인자로 두 개의 정수를 넘겨주어야 하는데, 첫 번째는 전체 프로세스의 갯수, 두 번째는 그중에서 I/O 작업을 수행할 프로세스의 갯수이다. I/O 작업을 수행할 프로세스가 전체 프로세스의 수보다 많을 경우 실행되지 않는다. 나머지 여러 속성들은 프로그램 내에서 자동으로 임의적으로 설정된다.
출력되는 내용이 비교적 긴 편이기 때문에 외부 파일에 출력내용을 저장해서 보는 것을 추천한다. 예를 들어 다음과 같이 콘솔창에 입력하면 된다.
./CPUScheduler 10 3 >> result.txt

6. Source Code
자세한 사항은 Github에서 확인할 수 있다. 전체 소스코드와 실행파일 및 보고서가 포함되어 있다.
https://github.com/arkainoh/CPU-Scheduling-Simulator

토요일, 9월 10, 2016

Web Project: dragonit

토요일, 9월 10, 2016

1. Introduction
dragonit은 HTML5의 Drag and Drop API를 활용한 Front end 프로젝트이다. 정적인 웹페이지를 벗어나, 좀 더 어플리케이션에 가깝도록 interactive한 UI/UX를 어떻게 제공할 수 있을지에 대한 고민에서 시작되었다.

기존의 웹 앱에서 레이아웃을 제작할 때는 html과 css를 통한 Front end 작업을 많이 하는데, 특히 이미지같은 요소들을 추가할 때 위치나 크기 설정이 마음처럼 되지 않는다.

이미지 출처: http://www.telerik.com/blogs/styling-forms-like-a-pro-with-kendo-ui
이러한 불편을 해소하기 위해 dragonit은 javascript를 활용하여 사용자가 직접 이미지를 제어할 수 있도록 도와준다. 마우스 드래그를 통해 이미지의 위치와 크기를 손쉽게 설정할 수 있고, Drag and Drop 기능을 통해 외부 파일을 간단히 업로드할 수도 있다. 필요에 따라서는 삭제도 자유자재로 할 수 있다.

현재 이미지 파일에 대한 구현이 되어있으며, 추후에 텍스트 파일에 대한 지원도 추가할 예정이다. Chrome에서 잘 동작하는 것을 확인했으나, IE나 Firefox, Safari 등 다른 브라우저에 대해서는 아직 별도의 지원을 하고 있지 않다.

2. 사용법
크게 '선택(select), 이동(move), 제거(delete)' 3가지의 버튼을 사용할 수 있다.
선택 버튼을 누르면 영역을 선택할 수 있게 되는데, 선택된 영역에 "DragOnIt !"이라는 메시지가 나타나고 사용자는 이 영역에 외부 파일을 드래그 & 드롭하여 이미지를 표시할 수 있다.
이동 버튼은 toggle 형식이다. 버튼을 누르면 이동 기능이 활성화되고, 다시 한 번 누르면 기능이 해제되는 방식이다. 이동 기능이 활성화된 동안은 화면 위의 빈 영역 혹은 이미지들을 자유자재로 이동시킬 수 있다.
제거 버튼도 역시 toggle 방식이다. 제거 기능이 활성화된 상태로 화면 위의 빈 영역 혹은 이미지들을 클릭하면 즉시 제거된다.

소스 코드는 Github에서 볼 수 있으며, 설치 방법도 자세히 작성해두었다.
Github에서 dragonit.js 파일을 다운받아서 자신의 프로젝트에 포함시킨 뒤 다음 소스코드만 추가해주면 간단하게 dragonit을 사용할 수 있다.
<body>
    <div class="dragonit"></div>
    <button type="button" class="dragonit_select">select</button>
    <button type="button" class="dragonit_move">move</button>
    <button type="button" class="dragonit_delete">delete</button>
 
    Your code here
    <script src="dragonit.js"></script>
</body>
여기서 <div class="dragonit"></div>는 <body> 태그의 시작 부분에 두어야 잔 버그들이 없다. 아래쪽에 두게 되면 이미지가 영역 선택이 되면서 귀찮아진다.
그리고 <script src="dragonit.js"></script>는 되도록이면 <body> 태그의 끝부분에 두는 것이 좋다.
버튼의 경우엔 <input> 태그를 사용하든 <button> 태그를 사용하든 상관없다. 다만 <input> 태그의 경우 type을 button으로 설정하기만 하면 된다. 세 종류의 버튼은 간단히 dragonit_select, dragonit_move, dragonit_delete 클래스만 추가해주면 사용이 가능하다. 이때 Bootstrap을 쓰지 않는다면, css를 통해 active 클래스에 대한 style 정의를 해두는 것이 좋다. 버튼을 토글할 때 가시적으로 확인을 할 수 있도록 도와준다. 예를 들어, 이런식으로 설정하면 된다.
<style>
    .active { background-color: red; }
</style>

3. Demo

4. Source Code
더욱 자세한 설명과 소스 코드는 Github를 통해 확인할 수 있다.

월요일, 8월 08, 2016

Web Project: KUSM

월요일, 8월 08, 2016

1. Introduction
KUSM은 Korea University Sports Matching Service에서 약자로 따온 이름이다. 말그대로 고려대학교 학생들이 손쉽게 스포츠경기에 대한 상호작용을 하도록 돕는 웹서비스이다.

사실 실질적으로 매치를 해주는 기능은 없다. 단, 한 마디로 이 서비스를 요약하자면,
"고려대학교 녹지운동장 예약현황에 대한 정보 제공 + 커뮤니티 서비스 (SNS)" 이다.

기본적으로 c9.io라는 IDE와 Ruby on Rails라는 프레임웍 위에서 작업을 하였으며, Devise, Nokogiri, Fullcalendar 등의 gem 사용 및 여러 데이터베이스 모델링 기법들을 적용해보았다.

2. 문제 인식
다음 사진은 실제 고려대학교에서 운영중인 학교시설 예약 사이트이다.


이렇게 하나의 큰 달력(?)이 뜨고 예약불가/예약완료/훈련 등의 상태를 표현해준다. 그런데, 이렇게 표현을 할 경우 누가 언제 예약을 했는지 한눈에 알아보기가 힘들다.
설상가상으로, 예약완료라는 푸른 부분을 클릭하면 다음과 같은 팝업이 뜬다.


승인/승인거부로 나뉘는 것은, 같은 타임슬롯에 대해 여러 팀이 예약 신청을 했을 경우 예약에 성공한 팀과 실패한 팀을 나눈 것이다. 따라서 사실상 승인거부상태인 데이터는 거의 필요가 없는 데이터이다.

그리고 한 가지 더 주목할 점은, 바로 모임명이다. 체육시설을 사용하는 주체들은 대부분 동아리 단위이다. 그런데, 고려대학교의 시설 예약 시스템에서는 다음과 같은 제약사항이 존재하기 때문에 하나의 동아리에서, 예를 들어 로스쿨축구부라는 동아리에서 여러 타임슬롯에 최대한 많이 예약을 하고 싶을 경우, 여러 명의 회원들을 동원해서 각기 다른 명칭의 모임명(ex. 로스쿨축구부1, 로스쿨축구부2, 로스쿨축구부짱, 로스쿨축구부최고, ...)을 사용해야 하는 것이다. 이는 현실적으로 동아리라는 체계와 괴리가 생기는 부분이다.


만약, 로스쿨축구부의 동아리장이 특정 달에 예약성공한 모든 타임슬롯을 찾아보고자 한다면, 일일이 각기 다른 명칭과 예약신청인으로 등록된 예약정보를 확인해야 한다.

3. 문제 해결
이러한 불편함들을 해소하기 위해 승인완료된 예약정보를 한 눈에 정리해서 볼 수 있도록 간편하게 구성하였다. 로그인을 하였을 때 메인페이지의 모습이다.


웹 크롤링 구현, 게시판 시스템 구현
Nokogiri를 통해 실제 고려대학교 예약 사이트로부터 데이터를 크롤링해서 다음 예약 일정에 대해서 공지사항으로 알려주고, 오늘의 일정들을 쭉 나열해준다.
각각의 타임슬롯을 클릭하면 슬라이드처럼 내려오면서 나타나는 관련된 게시글들을 볼 수 있으며, 게시글을 작성할 수도 있다. 이때 카테고리로, 팀 또는 용병 둘 중 한 가지를 선택할 수 있으며, 해당 타임슬롯에 잡힌 팀에 용병으로 축구경기를 뛰고 싶다거나, 예약은 당장 잡아놨는데 야구경기를 할 다른 동아리 팀이 필요하거나 할 때 활용할 수 있도록 하였다. 그리고, 작성된 게시글들은 가장 최근에 작성된 게시글을 선두로 정렬되어 우측에 표현되도록 하였다. 타임슬롯이 아니라 게시글만 따로 모아서 보고싶다면, 상단의 게시판 탭을 사용하면 된다. 각 게시물에 또한 댓글을 작성할 수 있게 해두어서 커뮤니케이션 측면을 좀 더 강화했다.
1:N, M:N 등 DB간의 관계를 다채롭게 정의해둔 결과물이다.

검색기능 구현
중앙에는 검색바를 제공해서 원하는 자료를 찾아볼 수 있으며, Datepicker를 통해 달력의 날짜를 클릭하면 해당 날짜의 예약현황을 불러오는 기능도 구현해두었다.

문자열 그룹핑 알고리즘 구현
그리고 자세히 보면, 예약현황 리스트에 예약팀, 소속팀이라는 두 개의 팀 정보가 있는데, 여기서 예약팀이 바로 앞서 봤던 모임명에 해당한다.
문제인식 단계에서 하나의 동아리라는 주체가 여러 개의 모임명으로 분해됨에 따른 괴리를 최소화하기 위해서 서버단에서 내부적으로 알고리즘을 돌려서 모임명의 문자열이 비슷한 것들끼리 그룹화를 하였다. 즉, 실제 동아리 이름을 추측해내는 것이다.

이 알고리즘을 구현하는데 있어서 Jaccard Index 등 여러 개념들을 살펴보았는데, 개발 시간이 제한되어 있었을 뿐만 아니라, 그다지 어려운 개념은 필요할 것 같지 않아서 그냥 데이터셋에 오버핏(?)된 방법을 사용하였다.

대부분 모임명의 이름을 자신의 동아리이름ㅇㅇ123 이런식으로 짓기 때문에, 생각보다 간단하게 로직을 구성하였다. 우선 미래에 데이터의 수가 많아질 것을 대비해서, 실제 동아리명에 영향을 주지 않는 것들 (숫자와 특수문자, 혹은 "FC"같은 단어들)를 제거한 뒤 알파벳을 모두 소문자로 만들었다. 그러면 벌써부터 겹치는 데이터가 발생하게 된다. (ex. "축구부#1", "축구부^2" => "축구부")
따라서 이 데이터들을 Unique 조건을 만족하는 Relation으로 만들어버리면 데이터의 수가 대략 60~70% 정도로 줄게 된다.
이 유니크한 문자열들을 쭉 정렬하면, 직관적으로 비슷한 모임명끼리 뭉치게 된다. Linear하게 검사를 해서, 바로 옆에 위치한 문자열들끼리 유사성 검사를 진행한다.
만약 서로 공유하는 문자가 연속적으로 2개 이상 나타나면, 해당 공유된 문자열을 "후보"라는 자료구조에 저장해둔다.
과정을 마친 뒤 "후보"를 살펴보면 거의 대부분은 실제 동아리 이름이 나타나는 것을 확인할 수 있다. 이 중 육안으로 동아리 이름이 확실하게 아닌 것들은 제거하고, 수정사항이 있으면 약간의 수정을 한다.
최종적으로 정제된 "후보" 자료구조를 서버에 전달해주면, "후보"에 저장된 동아리명과 유사한 이름을 가진 모임이 자동으로 해당 동아리에 소속되도록 업데이트된다.

이러한 과정을 통해서, '내 정보' 페이지로 가면 회원가입을 할 때 입력해두었던 소속팀의 예약현황을 한 눈에 알아볼 수 있다.


동아리 회원 중 누가 예약 성공을 많이 했는지, 많이 못했는지 등을 보고 꾸지람(?)을 하기에도 안성맞춤이다.

기타
이외에도, Devise를 통한 회원 계정 관리 체계를 구성하고, Fullcalendar를 통해 주간/월간 일정을 한 눈에 알아볼 수 있도록 좀 더 시각적인 효과를 주었다.


4. Source Code
전체 코드는 Github에 올려두었다. 버전관리, 협업용으로 사용한 것이 아니라 단순 파일 업로드용으로 사용한 것이기 때문에 다소 커밋이 지저분하고 브랜치의 사용이 아주 정직(?)하다.
https://github.com/arkainoh/KUSM

일요일, 8월 07, 2016

AI Project: Connect4

일요일, 8월 07, 2016

2016년 1학기 인공지능 수업에서 프로젝트로 진행했었던 Connect4 게임 인공지능이다. 제출한 데모 버전에 버그 픽스, 기능 추가, UI 개선 등의 과정을 거쳐서 나름 완성에 가까운(?) 버전으로 업그레이드했다.

1. Connect4란 무엇인가
https://en.wikipedia.org/wiki/Connect_Four
Connect4는 한국에서는 생소한 게임이지만, 기본적인 룰은 5목과 유사한 "4목"이라고 할 수 있다. 돌 네 개를 수직, 수평 혹은 대각선으로 일렬로 놓으면 이기는 간단한 게임이다. 그런데 특징은 아무데나 원하는 곳에 돌을 둘 수 있는 것이 아니라 세로줄 중 하나를 선택해서 Stack처럼 아래에서부터 채워야 한다는 것이다. 따라서 생각보다 수읽기가 까다롭다.
게임판은 8x8 또는 7x6으로 두 가지 종류가 있는데, 해당 프로젝트에서는 7x6 보드를 사용하였다.


인공지능은 하, 중, 상의 난이도로 나누었는데, 상의 난이도를 기준으로 하면 대략 10수 앞 정도를 내다보고 수를 둔다고 생각하면 된다. 판에 놓인 돌의 수가 많아질수록 내다보는 수도 점점 증가한다.

2. Demo

3. 개발 환경
Eclipse Java EE IDE for Web Developers.
Version: Mars.2 Release (4.5.2)
Java 언어를 사용하여 개발하였다. IDE로는 이클립스를 사용하였다.
GUI는 복습 겸 awt를 통해 구현하였다. Swing을 사용하지 않아서 꽤나 시간을 많이 잡아먹었다.

4. 구현 알고리즘
Minimax Algorithm + Alpha-beta Pruning (Game Tree)
https://en.wikipedia.org/wiki/Minimax
https://en.wikipedia.org/wiki/Alpha-beta_pruning

5. Heuristic Function
Winning Line의 수를 세는 것을 바탕으로 스코어링을 했다. 일렬로 놓이는 돌의 개수가 많을수록 높은 점수를 얻으며, 가능한 모든 Line에 대한 점수를 합산하여 다음 수를 두는 데 반영하였다.


6. Source Code
자세한 사항은 Github에서 확인할 수 있다. 전체 소스코드와 실행파일(.jar) 및 보고서가 포함되어 있다.
https://github.com/arkainoh/Connect4

jar 파일을 실행하려면, 해당 파일이 있는 위치에서 터미널을 열고 다음 커맨드를 입력하면 된다. 컴퓨터에 Java가 설치되어 있고, 환경변수 설정이 완료된 상태여야 한다.
java -jar Connect4AI.jar