나의 큰 O는 log x야

(이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949) 하나의 단어를 형태소로 쪼개다보면 일치하는 패턴이 여러개 등장하는 경우가 많습니다. 예를 들어 '디자인하여' 라는 어절을 쪼개보면디자인하여 => 디자인 + 하 + 아가 되는데, 각각의 덩어리에 일치하는 형태소 목록은 다음과 같아요. 디자인 하 아 디자인/NNG 하/VV 아/EC 하/XSV 아/EF 하/XSA 아/IC 하/NNG ... '하'와 '아'의 경우 일치하는 녀석들이 더 많지만 여기서는 설명의 단순화를 위해 위와 같다고 하겠습니다.이 경우 조합 가능한 모든 경우의 수는 12가지가 되겠죠. 하지만 디자인하여는 디자인/NNG + 하/XSV + 아/EC로 분석되는게 맞습니다. 그러..

프로그래밍/NLP 2017. 3. 26. 22:01

어쩌다 형태소 분석기를 개발하게 되었는지는 이전 글에 친절히 설명했고, 이번 글에서는 처음 개발하며 겪었던 문제를 소개합니다. 제일 처음 구현한 것은 아호코라식(Aho Corasick) 알고리즘이었습니다. Trie를 구성해 문자열 내에 포함되는 패턴을 빠르게 찾아내는 알고리즘이지요. 이름만 들으면 굉장히 어려울 것 같지만 다행히도 슬라이드세어에 한국어로 된 친절한 프레젠테이션이 있어서 https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm 이걸 보며 쉽게 구현할 수 있었습니다. (이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949) 한글처리 알고리즘 코딩하기한국어 처리를 위해서 가장..

프로그래밍/NLP 2017. 3. 26. 22:01

2월 말부터 갑자기 시작한 일이 있는데, 한국어 형태소 분석기를 직접 만들어 보는 일이었습니다. 처음에는 과연 할 수 있을까 싶기도 해서 블로그에 기록을 안 남기고 조용히 진행하고 있었습니다. 근데 기록을 남기지 않으니 시간이 갈 수록 헤매게 되는거 같아서 어느 정도 틀이 잡힌 시점에서 차곡차곡 기록을 남겨가며 프로젝트를 진행하기로 결심했습니다. (이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949) 뜬금없이 왜 형태소 분석기를..?형태소 분석기를 만드는 삽질을 하게 된 이유를 구구절절히 풀자면 길어질거 같아서 짧게 정리하도록 할게요. 시작은 작년 초에 만들었던 KorpuSQL(http://bab2min.tistory.com/473) 이..

프로그래밍/NLP 2017. 3. 26. 21:55

대량의 구조화된 데이터에서 새로운 사실을 발견해내는 것을 데이터 마이닝(Data Mining)이라고 합니다. 데이터 한 두 개가 있을때에는 보이지 않던 사실이 데이터가 많이 모이게 되면 보이게 된다는 것인데요, 정보 기술의 발달로 축적되는 데이터가 증가하면서 데이터 마이닝에 대한 관심도 크게 증가했습니다. 사실 거창하게 이야기했지만 데이터 마이닝의 주 목적은 패턴 발견입니다. 우리가 점 하나를 가지고는 그 점이 가지는 의미르 알 수 없지만, 무수히 많은 점이 모이게 되면 전체적인 경향을 볼 수가 있잖아요. 데이터 마이닝도 마찬가지입니다. 데이터가 적을때에는 보이지 않던 패턴이 그 양이 늘어나면 보이게 됩니다. 그래서 사실 데이터 마이닝은 통계적 기법을 많이 활용합니다. 통계의 역할이 많은 양의 관측 데이..

그냥 공부 2017. 3. 24. 19:14

앞서 중심성, 결집계수에 대해서 다뤄보았으니, 이제 네트워크 이론에서 두 노드가 얼마나 유사한지를 계산하는 방법에 대해서 논해봅니다. 어떻게 두 노드가 유사한지를 판단할 수 있을까요? 가장 간단한 방법으로는 두 노드의 이웃이 얼마나 겹치는지를 살펴볼 수 있겠죠. 만약 모든 이웃이 겹친다면 두 노드는 아예 똑같은 노드, 겹치는 이웃이 하나도 없다면 전혀 다른 노드라고 봐도 되겠죠? 구조적 등위성(Structural Equivalence)앞서 설명한 겹치는 이웃의 수를 보고 유사도를 판단하는 방법을 구조적 등위성이라고 합니다. SNS를 예시로 설명하자면, 친구가 겹치는 사람이 많을 수록 유사한 유저라고 본다는 것이죠. (N(i)는 노드 i의 이웃 노드들의 집합)이때 i와 j의 단순 유사도는 i의 이웃 집합과..

그냥 공부 2017. 3. 20. 21:05

앞서서 네트워크 상에서 어떤 노드가 중요한지를 알아보는 중심성을 살펴봤는데, 이번에는 네트워크가 얼마나 똘똘 뭉쳐있는지를 알려주는 '결집계수(Clustering Coefficient)'에 대해서 살펴보도록 합시다. 결집계수는 추이성(Transitivity)을 기반으로 합니다. 이는 A->B이고 B->C이면 A->C가 되는 성질을 말합니다. 수학에서 부등호나 등호 같은 경우가 추이성을 가지는 관계지요. 문제는 네트워크 그래프의 노드들은 항상 추이성을 가지지 않을 수도 있다는 것에 있습니다. A가 B와 연결되고, B가 C와 연결되어있다고 하더라도, A가 C와 반드시 연결되지 않을수도 있기 때문이죠. 뭉쳐있는 정도를 얘기하다가 추이성을 꺼낸 이유는, 우리가 노드들이 똘똘 뭉쳐있다는 것을 "추이성" 가지고 정의..

그냥 공부 2017. 3. 17. 13:44

스팀 게임평이 양이 적어서 감성사전을 구축하기 어렵다고 판단하여 네이버 영화 평점을 수집하는 일을 수행했었는데요, 이 역시 수집만 하고 다음 단계로 넘어가지 않았기에 방치해두기 아까운 코드, 공유해드립니다. 앞의 글과 마찬가지로 Python3로 작성되었으며, 실행을 위해서 BeautifulSoup 라이브러리가 필요합니다.import urllib import urllib.request import urllib.parse import bs4 import re import os import time from concurrent.futures import ThreadPoolExecutor def deleteTag(x): return re.sub("]*>", "", x) def getComments(code): ..

프로그래밍 2017. 3. 17. 01:03

작년에 게임과 관련된 한국어 감성분석 사전을 만들어볼까 하는 생각에 Steam에 등록된 한국어 게임평들을 모두 긁어온 적이 있었는데요, 결론부터 밝히자면 그 수가 적어서 유의미한 분석을 할 수는 없었습니다. 그래서 당분간 묵혀두었는데, 기껏 짜놓은 코드 하드 속에서 용량만 차지하게 냅두느니, 먼지 털고 올려두면 누군가에게 도움이 될 수 있지 않을까 하는 생각에 공유하기로 마음 먹었습니다. Python3 기반의 코드이고, 간단하므로 크게 설명할 건덕지는 없을듯합니다. BeautifulSoup 라이브러리가 필요합니다. import urllib import urllib.request import urllib.parse import bs4 import re import os from concurrent.futu..

프로그래밍 2017. 3. 17. 00:56