N-gram 알고리즘 기초

<만들면서 배우는 기계 학습> - 1. N-gram

greentec.egloos.com/2795831

오다카 토모히로의 <만들면서 배우는 기계 학습>을 읽었다. 빅데이터 처리에 대한 간단한 기술들을 C언어 실습 예제로 알기 쉽게 풀어 설명한 책이다.

예 전부터 관심이 있어서 계속 공부해 온 분야이긴 한데, 이 책은 정말 내용을 쉽게 잘 써놓았다. 도표도 적재적소에 사용되었고 소스도 적절하다. 이 책에 나와 있는 프로그램 중 일부를 AS 3.0으로 구현해 보는 것이 도움이 될 것 같아서 오늘부터 한번 시작해보려고 한다.

오늘의 주제 : N-gram

N-gram이란 간단하게 말해서 입력한 문자열을 N개의 기준 단위로 절단하는 방법이다. 예를 들어 "Here is a dog" 라는 문장을 문자 절단 단위의 3-gram으로 만든다면, 

"Her", "ere", "re_", "e_i", "_is", "is_", "s_a", "_a_", "a_d", "_do", "dog" 로 만들 수 있다. 

같은 작업을 단어 단위의 2-gram으로 만든다면,

"Here is", "is a", "a dog" 가 된다.

이렇게 만든 다음 나오는 빈도를 분석할 수도 있고, 검색어 엔진에서 키워드를 뽑아내는 용도로도 쓰이고, 음성 인식에서도 쓰인다고 한다. 여러 모로 중요한 기법이니 한번쯤 구현해보는 게 좋을 것 같다.

프로그램의 순서도는 이렇게 된다.

1. 문자열 로드

2. N-gram 만들기

3. N-gram 을 출현빈도 순으로 출력

너무 간단한 것 같다. 2를 조금만 확대해 보자.

2-1. N-gram에서 공백 등 제거

2-2. Array에 1단위의 N-gram을 집어 넣기

2-3. N단위의 N-gram을 Object의 키로 만들면서 중복 체크하고, 빈도 기록

2-1은 인터넷에 올라와 있는 정규표현식을 사용했다. 소스는 아래와 같다.

private function trim( s:String ):String

{

return s.replace( /^([\s|\t|\n]+)?(.*)([\s|\t|\n]+)?$/gm, "$2" );

}

자...자세한 설명은 생략한다. 

정규표현식 책을 사놓고 한번 보긴 했는데, 아직 저 정도로 멋진 식을 만들 수 있을 정도는 아니라서 인터넷 검색을 이용했다. 

만약 2-1의 과정을 거치지 않으면 개행문자(\n) 등이 그대로 남아 있어서 중간에 개행문자가 포함된 N-gram 따위가 생성된다.

2-2는 Array에 1단위의 N-gram을 집어넣는 것인데, 여기서는 단어 단위로 사용했다. 소스는 다음과 같이 간단하다.

var NgramOriginalArray:Array = [];

NgramOriginalArray = originalTxt.split(" ");

NgramOriginalArray라는 Array를 생성하고 공백문자(" ") 단위로 자른 것을 바로 Array에 집어 넣었다. 

이 경우 Array에 그대로 단어들이 쏙쏙 들어가게 된다. 예를 들어,

NgramOriginalArray = "Here is a dog".split(" "); 

의 결과는 

trace(NgramOriginalArray[0]); // Here

trace(NgramOriginalArray[1]); // is

trace(NgramOriginalArray[2]); // a

trace(NgramOriginalArray[3]); // dog

이렇게 되는 것이다.

마지막으로 2-3에서는 일전에 쿠폰 번호 생성기를 만들 때 사용했던 Object의 key를 이용한 중복 체크 방법을 사용했다. 

(http://greentec.egloos.com/2752233)

소스는 다음과 같다.

for (i = 0; i < NgramOriginalArray.length - 1; i += 1)

{

singleGram = NgramOriginalArray[i] + " " + NgramOriginalArray[i+1];

if (NgramObject.hasOwnProperty(singleGram) == true)

{

NgramObject[singleGram] += 1;

}

else

{

NgramObject[singleGram] = 1;

}

}

for 문은 다들 알 것이라고 생각한다. 프로그램 언어에서 쓰이는 대표적인 반복문이다.

현재는 단어 단위의 2-gram을 사용할 것이므로 singleGram이라는 String에 두 단어를 공백문자로 결합한 것을 넣었다.

그 리고 if (NgramObject.hasOwnProperty(singleGram) == true) 여기서 NgramObject라는 Object에 singleGram이라는 key가 있는지 검사한다. 있으면 그 키 값에 출현값을 하나 더해주고, 없으면 키를 생성하고 출현값을 1로 지정해준다.

좀 쉽게 설명하면 "Here is a dog"에서 

i=0일 때 singleGram=Here is 이고, 

NgramObject에는 Here is라는 키가 없으므로 생성하고 출현값을 1로 지정.

i=1일 때 singleGram=is a 이고,

NgramObject에는 is a라는 키가 없으므로 생성하고 출현값을 1로 지정.

i=2일 때 singleGram=a dog 이고,

NgramObject에는 a dog라는 키가 없으므로 생성하고 출현값을 1로 지정.

즉 NgramObject는 다음과 같이 된다.

NgramObject = { "Here is" : 1, "is a" : 1, "a dog" : 1 }

그 다음 빈도 순으로 출력하는 것은 2-3에서 만든 Object를 가지고 Array를 만든 다음 Sort하면 된다. 

www.gutenberg.org에 올라온 오즈의 마법사<The Wonderful Wizard of Oz> 에서 단어 단위의 2-gram을 추출해서 상위 50개를 뽑아 본 결과는 다음과 같다.

of the : 312

to the : 161

said the : 144

and the : 127

in the : 121

 The : 105

the Tin : 93

 But : 66

the Scarecrow : 63

I am : 53

the Lion : 53

in a : 53

for the : 51

the Wicked : 51

Tin Woodman : 51

was a : 49

asked the : 48

at the : 48

back to : 48

Wicked Witch : 46

did not : 45

into the : 43

the little : 43

a great : 43

to be : 41

the Emerald : 40

all the : 40

came to : 40

answered the : 37

by the : 36

 It : 36

he was : 36

the Scarecrow, : 36

on the : 36

I shall : 35

 I : 35

to see : 34

 They : 34

out of : 33

they were : 33

with a : 33

through the : 33

 So : 32

she was : 31

 She : 31

the Woodman : 30

with the : 30

 Then : 30

from the : 30

the Great : 30

주 인공들 이름이 군데군데 보이고, 특이한 것은 도로시가 보이지 않는데 아마 도로시 이름이 주어 한 단어로 나오기 때문인 것으로 사료된다. 그만큼 다양한 동사를 썼다는 이야기가 되겠다(소설이니까 당연한 얘기이겠지만). 참고로 Dorothy 단어 자체는 369번 쓰였다.

이상 N-gram의 구현에 대해서 알아보았다.

다음 글에서는 아나그램(anagram)에 대해서 알아볼 예정이다. 아나그램이란 한 단어의 철자를 분해해 다른 단어로 만드는 놀이인데, 이것을 영어 사전(단어 목록)을 읽은 다음에 코드로 자동화시켜서 찾아낼 예정이다.

아나그램 코드를 만들어서 찾아본 것들 중 흥미있는 것을 몇 가지 소개하며 이번 글을 마친다.

programer,reprogram

importunate,permutation

revolute,truelove

negativism,timesaving

steelworker,teleworkers

algorithms,logarithms

corpses,process

gussman,samsung

cocaine,oceanic

harpists,starship

coexist,exotics

그럼 이만 (--)//


출처 : http://greentec.egloos.com/viewer/2795831