나의 큰 O는 log x야

세상의 많은 관계들을 수학적으로 나타내는데에는 그래프만큼 강력한 도구도 없습니다. 관계의 주체가 되는 행위자들은 Node로, 관계들은 Node사이를 연결하는 Edge로 나타낼 수 있기 때문이죠. 이렇게 주변에서 찾아볼 수 있는 관계를 수학적인 형태의 Graph로 바꾸면 여러 가지가 가능해지는데, 그 중 대표적인것이 중심성(Centrality) 계산입니다. 중심성은 그래프 상에서 어떤 Node가 가장 중요한지를 살피는 척도인데요, 여태까지 막연하게 여러가지 계산법이 있을거라고 생각은 했지만, 실제로 공부는 해보지 않았었네요. 그래서 이번에 Social Media Mining을 공부하면서 관련 이론을 정리해보려고 합니다. (다음 내용은 Zafarani, R., Abbash, M.A., & Liu, H, 20..

그냥 공부 2017. 3. 15. 16:50

블로그를 만든지가 10년차가 되어가는데, 생각해보니 블로그 제목을 정하고 그 뜻을 설명해본적이 한 번도 없는듯 합니다. 짧게나마 제목이 이렇게 지어지게 된 경위를 소개하자면, 블로그를 처음 시작할 당시에 미약하게 컴퓨터를 공부하고 있었고, 또 그와 별개로 이라는 책을 읽고 있었습니다. 알고리즘 같은걸 제대로 이해하고 있지는 못할때여서 맨날 프로그래밍 커뮤니티에서 시간복잡도가 어떻니 하는 얘기가 나와도 전혀 이해하지 못하고 눈팅만하고 있었지요. 그러던 와중에 리만 가설 책 한 부분에서 소수의 갯수와 로그 적분 함수의 오차를 얘기하면서 빅O 노테이션을 설명해주었습니다. 친절하게 잘 풀어서 설명해준 교양서적 덕분에 고등학생의 머리로도 잘 이해할 수 있었고, 거기서 빅 O 노테이션을 이해하자, 시간 복잡도 문제..

적분史 2017. 3. 10. 03:22

훌륭한 알고리즘이라고 꼭 다 복잡하거나 이해하기 어려운건 아닙니다. 오히려 정말 단순한 절차로 큰일을 해내는게 진짜 훌륭한 알고리즘이라고 할 수 있을텐데요, TextRank (또는 PageRank)가 바로 그런 알고리즘인듯 합니다. 구글을 만든 알고리즘으로 널리 알려진 페이지 랭크는 매우 단순한 반복 계산을 통해서 각 페이지의 중요도를 매깁니다. 알고나면 단순한 알고리즘이지만 처음 이를 고안해내기는 정말 어려웠을 겁니다. 여기서는 간략하게 페이지 랭크 알고리즘을 소개하면서, 이를 텍스트에 응용한 텍스트 랭크를 설명하도록 하겠습니다. PageRank 소개페이지 랭크는 각각의 페이지를 정점(Node)으로, 페이지와 페이지를 연결하는 링크를 간선(Edge)으로하여 만들어진 그래프를 대상으로 하는 알고리즘입니다..

그냥 공부 2017. 2. 20. 21:49

관련어를 추출하는데에 있어서 점별 상호정보량(http://bab2min.tistory.com/546)만큼 간단하면서도 훌륭한 방법은 많지 않습니다. 그래서 관련어 추출 방법들을 비교할 때 있어서 기준치로 쓰이기에 좋지요. 그래서 여기 저기 코드에서 상호정보량 계산 클래스를 자주 만들어 쓰다보니깐, 하나로 잘 만들어놔서 두고두고 재활용해야겠다는 생각이 들었습니다. 간결하면서도 아름다운 파이썬 코-드 class PMICalc: def __init__(self, **kargs): self.window = kargs.get('window', 5) self.minNum = kargs.get('minNum', 5) self.dictCount = {} self.dictBiCount = {} self.searchPai..

프로그래밍 2017. 2. 14. 18:12

두 텍스트 간의 유사도를 산출하는 고전적인 방법에는 텍스트 내의 단어 빈도를 가지고 벡터를 구축하여, 벡터 간 코사인 유사도를 구하는 것이 있습니다. 이 방법의 장점은 다른 어떤 언어학적 기법을 도입하지 않아도 (기껏해야 Stemming 정도만 하면 충분하죠) 단어 빈도만 세어서 꽤나 훌륭한 결과를 얻을 수 있다는 것입니다. 그런데 이런 통계적인 방법이 통하려면 해당 텍스트가 충분히 길어야한다는 조건이 필요하죠. 그렇지 않을 경우 텍스트로부터 만들어진 벡터가 희소(sparsity)하게 되어, 좋은 결과를 얻을 수 없게 됩니다. 그렇기 때문에 짧은 텍스트에 대해서는 조금 다른 방법이 필요하게 됩니다. 이 글에서는 W Song, 2007, Question Similarity Calculation for FA..

그냥 공부 2017. 2. 9. 16:07

단어 의미 판별(Word-sense Disambiguation)이라는 작업이 있습니다. "가다"라는 동사를 예로 들어보죠. "집에 간다"는 문장에서 가다는 움직이는 것을 의미합니다. 반면 "저 세상으로 가셨다"는 문장에서는 죽었음을 뜻합니다. 이렇듯 같은 단어라도 맥락에 따라 사용되는 의미가 다르기에 보통 사전에 보통 1,2,3...번으로 세부 의미를 나눠서 뜻풀이를 합니다. 사전 이용자들은 사전을 살펴볼때 단어의 세부 의미 1번에 가장 자주 쓰이는 의미가 들어가 있기를 기대합니다. 그렇기에 세부 의미를 판별해서 어떤 세부 의미가 가장 자주 쓰이고 주된 의미인지 판별하는 작업이 사전 편찬 작업에서 중요하다 할 수 있겠습니다. 이 글에서는 D McCarthyr, 2004, Finding Predominan..

그냥 공부 2017. 2. 7. 18:30

C++ 컨퍼런스라는게 있는줄도 몰랐는데, 2014년부터 모던 C++ 애호가(?)들을 위한 컨퍼런스가 매년 개최되고 있었더군요. 한동안 C++로부터 관심이 멀어져있었는데, 컨퍼런스 내용을 보니 C++사랑이 듬뿍듬뿍 솟아오르는 것 같은 느낌입니다. 컨퍼런스 홈페이지는 https://cppcon.org/ 이고, 컨퍼런스 자료들은 모두 GitHub에 친절하게 올라가 있더라구요. 16년도 컨퍼런스 프레젠테이션들을 조금 살펴봤는데, 모던 C++의 발전 방향과 활용, 유용한 테크닉 등 여러 방면에 대해 다루고 있어서, C++를 공부하는 사람이라면 정말 많은 것을 배워갈 수 있을 거 같네요. 시간이 없어 다 읽어보지는 못했지만, 틈틈히 읽어보려고 합니다. 끝.

프로그래밍 2017. 2. 5. 15:38

불과 10여 년 전까지만 해도 대학생 과 커뮤니티 100 중 99는 싸이월드 클럽을 사용했습니다. 과연 싸이월드의 전성기라고 할 수 있었죠. 하지만 시대가 변해 SNS가 등장하고 싸이월드가 망하면서 싸이클럽 역시 쇠락의 길로 접어들었습니다. 지금은 대부분의 대학생 커뮤니티가 페이스북을 기반으로 하고 있다고 알고있으며, 일부 카페를 사용한다고 하는데요, 페이스북 그룹의 특징 상 게시물을 카테고리화해서 분류하기가 어렵고, 과거 자료를 열람하는 것이 매우 불편합니다. 그래서 과 커뮤니티를 네이버 카페로 옮기기로 했습니다.싸이월드 클럽 크롤러문제는 02년부터 최근까지 10년 넘게 축적된 싸이클럽의 데이터를 어떻게 카페로 옮길 것인가! 였습니다. 만 개가 넘는 게시물을 어떻게 손으로 직접 옮길수는 없고, 프로그램..

적분史 2017. 1. 28. 03:33