나의 큰 O는 log x야

작년에 토픽 모델링이라는 개념을 접하고 깜짝 놀랐어요. 그냥 적당한 크기의 문헌들을 넣어주면 거기에서 적절하게 컴퓨터가 연관된 단어들을 묶어서 주제 분포를 만들어주고, 문헌별로 주제가 얼만큼 포함되었는지 계산해주는게 너무 신기했기 때문이었습니다. 그래서 도대체 어떻게 이런걸 해내는지 궁금해서 LDA(Latent Dirichlet Allocation, 잠재 디리클레 할당)와 관련된 논문을 찾아봤는데 수학 실력이 부족해서 제대로 이해하지 못했다는 슬픈 소식이...그래서 LDA 이론을 이해하기 위해 작년부터 먼길을 돌고돌아 이러저러한 수학/통계적 기초를 찾아다녔는데, 마침내 드디어 빛을 찾은듯합니다. 그래서 간신히 찾은 빛을 오래오래 간직하고자 이렇게 블로그에 정리하게 되었습니다! LDA를 이루는 이론적 기초..

그냥 공부 2017. 4. 20. 16:07

이 글은 A Heidarian, 2016, A Hybrid Geometric Approach for Measuring Similarity Level Among Documents and Document Clustering 논문의 내용과 이를 정리하고 구현한 깃헙의 코드(https://github.com/taki0112/Vector_Similarity)를 바탕으로 작성되었습니다. 문헌들 사이의 유사도를 계산하기 위해서 흔히 사용되는 방법은 문헌에 등장하는 색인어(단어)의 빈도를 파악하여 TF-IDF 등의 가중치를 반영하여 벡터화하는 것입니다. 일단 문헌이 벡터로 표현되게 되면 여러가지 수학적 기법을 통해 벡터 간 유사도를 계산할 수 있죠. 그 중 대표적으로 사용되는 것에는 코사인 유사도와 유클리드 유사도 등..

그냥 공부 2017. 4. 14. 17:46

앞서서 네트워크 이론의 기본적인 개념들을 설명했으니, 실제로 우리 주변에서 찾아볼 수 있는 네트워크들에서 어떤 현상이 일어나는지 살펴보도록 하지요. 실제 세계 네트워크의 성질랜덤 네트워크와 다르게 실제 세상의 네트워크들은 빈익빈 부익부 현상이 있습니다. 즉 다른 녀석들과 많이 연결된 애들이 전체 연결의 대부분을 차지하고, 조금 연결된 녀석들이 엄청나게 많습니다. 마치 20%가 80%의 돈을 가져가고, 나머지 80%가 20%의 돈을 가져가는것처럼 말이죠. 파레토의 법칙이라고도 불리는 이런 현상을 Power-law 분포(멱법칙)라고 합니다. 또한 결집계수(Clustering Coefficient)도 굉장히 높은 편입니다. 즉 내 친구의 친구도 내 친구인 경우가 많다는 거죠. 랜덤으로 그래프를 생성하면 이런일..

그냥 공부 2017. 4. 5. 15:57

대량의 구조화된 데이터에서 새로운 사실을 발견해내는 것을 데이터 마이닝(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

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

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

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

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