Automatic Topic Extraction from Temporal Text Streams

Abstract

As social media services such as Twitter and Facebook are gaining popularity, the amount of information from these services is explosively growing. Most of them use temporal text stream to facilitate distribution of a huge volume of content they publish. Dynamic text stream is defined as a temporarily ordered set of documents published by a web site over time in order to facilitate syndication of content. In this context, many users subscribe to the streams to acquire up-to-date information through information aggregation and sharing services, and real-time search engines also increasingly utilize the streams to promptly find recent web content when it is produced.

Compared to web pages, temporal text stream is a time-varying document since it continually publishes entries on some specific topics. In addition, it is a structured document that consists of several data elements such as title and description. In this thesis, we investigate a problem of extracting topics from the streams, considering the temporal and structural characteristics of temporal text stream.

Specifically, the first part of the thesis considers a problem of identifying a feature set created from data elements constituting temporal text stream, with the aim of improving effectiveness of extracting persistent topics over the stream while at the same time reducing computational cost. With structural nature of the stream, it is necessary to investigate which data elements need to be selected to define a feature set for topic extraction. Furthermore, the temporal characteristic of the stream raises a problem of determining how many entries need to be considered for topic extraction.

The second part of the thesis addresses a problem of detecting topics of persistent interests from a temporal text stream over time, considering its temporal characteristics. After defining three unique properties of the persistent topics, a graph-based topic extraction model using scoring functions to measure the properties is proposed.

Finally, a novel automatic tagging model to detect informative terms from short entries of the temporal text stream is proposed following the framework of supervised approach. Traditional frequency-based term features are redefined so that they can address the properties of the entries created under the length limitation, and sequential dependencies between successive terms in an entry is considered. In addition, the proposed automatic tagging approach incorporates behavioral patterns by which users put informative terms into their entries. The thesis concludes with a discussion on potential extensions of this work.

최근 정보 배포 및 획득 수단으로 주목받고 있는 동적 텍스트 스트림 (temporal text streams)은 엔트리 (entry)들이 시간 순서상으로 정렬된 구조화된 문서이다. 또한, 각 스트림과 엔트리는 제목 (title)과 본문 (description)로 이루어진다. 본 연구에서는 피드 (feed)와 같은 동적 텍스트 스트림으로부터 개별 엔트리 또는 스트림 수준의 토픽을 자동으로 추출하기 위한 모델을 연구한다. 일반적인 웹 페이지와는 구별되는, 스트림이 가지고 있는 시간 및 구조적 특성 (characteristic)은 자동 토픽 추출 문제를 어렵게 만든다. 이에 본 연구에서는 스트림에서 토픽들이 갖는 특징 (feature)들을 조사하고, 이러한 특징들을 이용하는 자동 토픽 모델을 제안하고자 한다. 특히, 글자 수의 제한이 있는 엔트리들을 발행하는 마이크로블로그 (microblog) 서비스에서 발행하는 스트림을 대상으로 연구할 것이다.

최근 웹 상에서 피드와 같은 스트림을 통해 정보를 발행하는 정보 생성 주체들과, 피드를 구독함으로써 정보를 효과적으로 획득하려는 사용자들이 급격히 증가하고 있다. 특히, 트위터 (Twitter)와 페이스북 (Facebook)과 같은 소셜 미디어 (social media) 서비스를 통해 많은 사용자들이 스트림 형태로 컨텐츠를 배포하고, 반대로 다른 사용자의 스트림을 구독하여 정보를 획득하고 있다. 이러한 흐름에서 스트림으로부터 토픽 추출은 스트림 및 엔트리 검색, 스트림 추천, 상황 인식 광고 등과 같은 다양한 스트림 기반의 서비스들에 응용될 수 있다.

일반적인 웹 페이지 (web page)에서 토픽을 나타내는 키워드 (keyword)를 추출하는 문제는 그동안 많은 문헌에서 연구되어 왔다. 많은 연구에서 정적인 (static) 웹 페이지에서 키워드들만이 갖는 특징들을 탐색했으며, 이러한 특징들을 활용하여 비지도 (unsupervised) 또는 지도 학습 (supervised learning) 기반의 다양한 모델들을 제안해 왔다. 최근에는 트위터나 페이스북에서 생성되는 스트림들로부터 키워드를 추출하는 연구도 활발히 수행되고 있다. 그러나, 이러한 연구들은 정적인 문서에서 키워드를 추출하는 기존 모델들의 프레임웍 (framework)에서 제안됨으로 인해, 스트림이 다수의 엔트리들로 구성된 구조화된 문서라는 독특한 특성들을 충분히 고려하지 않고 스트림을 하나의 정적인 문서로 간주하는 가정에서 토픽을 추출한다. 더구나, 글자 수 제한이라는 마이크로블로그의 엔트리의 주요 특성을 고려하지 않았다. 본 논문에서는 위와 같은 스트림의 특성들을 고려하여 스트림 수준에서의 키워드들을 추출하기 위해서는 얼마나 많은 엔트리들이 필요하며, 어떠한 구성 요소들을 선택해야 하는지 연구한다. 또한, 짧은 엔트리에서의 키워드를 추출하기 위한 새로운 특징들을 제안하고자 한다. 끝으로, 엔트리 수준에서의 토픽 (이하 엔트리 토픽)과 장시간에 걸쳐 형성되는 스트림 수준의 토픽 (Persistent Topic, 이하 스트림 토픽)을 자동으로 추출하기 위해 스트림의 특성들을 고려하는 모델들을 제안하고자 한다.

앞서 설명한 바와 같이, 스트림은 복수의 엔트리들이 시간 순서상으로 정렬되어 있고, 각 스트림과 엔트리는 제목과 본문을 구성 요소로 갖는 구조화된 문서이다. 따라서, 스트림 토픽을 추출하기 위해서는 몇 개의 엔트리가 필요하며, 스트림와 엔트리의 제목 및 본문 중 어떤 구성 요소가 도움이 되는지에 대한 연구는 필수적이다. 이에, 본 연구에서는 다양한 엔트리 개수 및 구성 요소의 조합들을 대상으로 support vector machine (SVM)와 같은 지도 학습 기법을 이용하여 엔트리 개수와 구성 요소의 최적 조합을 탐색하고자 한다. 또한, 엔트리 토픽을 추출하는데 있어, 전통적 document term frequency와 inverse document frequency 기반의 특징들과는 별도로 글자수 제한이라는 특성을 고려하기 위한 스트림 수준의 새로운 특징들도 제안하고자 한다. 또한, 제안된 각 수준별 토픽의 특징들을 이용하여, 엔트리 토픽과 스트림 토픽을 추출하기 위한 모델들을 각각 연구한다. 첫 번째, 엔트리내에서 이웃 단어들간 상호 의존성 (dependency)과 사용자들의 작성 유형 (composition pattern)을 반영한 엔트리 토픽 추출 모델을 제안한다. 두 번째, 스트림 토픽 추출 모델을 위해서, 많은 데이터 분석을 통해 스트림 토픽의 독특한 특성들을 확인하고, graph-ranking 알고리즘 기반의 모델을 활용하기 위해서, 단어들간의 관계 특성들을 측정하는 scoring function들을 제안한다. 결과적으로, 단어들은 vertex를, 단어들간 관계 점수 (association score)는 edge를 구성함으로써 하나의 그래프를 형성하게 되고, 그래프를 대상으로 상호 강화 (mutual reinforcement) 방법을 적용하여 각 단어별 점수를 최종적으로 산출하게 된다.

요컨대, 본 논문에서는 최신의 정보 배포 및 획득 기술인 텍스트 스트림이라는 시간적, 구조적으로 독특한 특성의 문서에서 토픽을 추출하기 위해서 필요한 키워드들의 특징들을 기존의 정적인 웹 페이지 키워드들의 특징들과는 다르게 정의한다. 구체적으로, 최근 주목받고 있는 마이크로블로그의 엔트리내 키워드를 효과적으로 구별하기 위해서 새로운 특징들을 제안하고, 스트림 수준의 토픽을 추출하기에 적정한 엔트리들의 개수와 필요한 구성 요소를 확인한다. 이러한 토픽들의 특징들은 비단 토픽 추출 뿐 아니라, 의견 분석 (sentimental analysis) 등과 같은 텍스트 스트림을 대상으로 하는 다양한 모델 연구에서 시발점이 될 수 있을 것이다. 또한, 실제로 복수의 작성 유형들에 의해서 엔트리들이 작성되지만, 각 스트림별로 해당되는 작성 유형을 확인할 수 없어 모델에 반영할 수 없었던 기존 연구 결과들과는 달리, 본 연구에서는 작성 유형을 잠재 특징 (latent feature)으로 고려하여 복수의 분류 함수 (discriminant function)들을 갖는 엔트리 토픽 추출 모델을 제안한다. 이와 같은 접근법은 잠재 특징에 따른 다양한 분류 함수들이 필요하다고 판단되지만, 분류 함수를 구분하는 잠재 특징을 확인할 수 없는 다양한 문제에 적용가능할 것이다.