238 정보과학회논문지 : 데이타베이스제 39 권제 4 호 (2012.8) 텍스트랭크알고리즘을이용한사용자타임라인요약기법 (A User Timeline Summarization Technique using TextRank Algorithm) 안인석 김현우 김형주 (In Seok An) (Hyunwoo Kim) (Hyoung-Joo Kim) 요약디지털기기가광범위하게보급되면서 information stream 이정보인지의보편적인수단으로활용되고있다. 트위터는 140 자미만의단문을서비스하는마이크로블로깅서비스로가장인기있는소셜미디어서비스이다. 시간이지남에따라트위터사용자들은구독하는정보의양이많아진다. 결국너무많은정보를받게되어사용자가정보를모두확인할수없는상태가된다. 본연구에서는텍스트랭크알고리즘이라는자연어처리기법을이용하여트위터타임라인에서일어나는정보과다현상을해결하는연구를진행하였다. 타임라인을이루고있는트윗들을그래프로모델링한후, 그래프기반의랭킹알고리즘을적용하여정점의스코어를얻고, 그스코어를기반으로산봉우리개념을그래프에적용하여타임라인을요약하였다. 본연구에서제안한텍스트랭크를이용한타임라인요약방법이기존의빈도수기반요약방법보다효과적으로타임라인을요약할수있음을실험을통하여확인하였다. 키워드 : 트위터, 타임라인, 요약, 자연어처리, 키워드 Abstract As digital device has come into wide use, information streams have recently emerged as a popular means of information awareness. Twitter is one of the most popular micro-blogging service and social media with a limit of 140 characters. If a user follows Twitter accounts continuously, the user may subscribe information more than the user can process. In this paper, we apply TextRank algorithm to alleviate information overload in Twitter user s timeline. After modeling user timeline as a graph, we apply graph-based ranking algorithm to the graph of timeline. Based on the score of each vertex, we apply concept of summit to summarizing user timeline. The experimental results show that proposed method summarizes user timeline more effectively than existing method that rely mainly on frequency based method. Key words : Twitter, Timeline, Summarization, NLP, Keyword 이논문은 2011년도정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된연구임 (No. 020110030812). 본연구는 BK-21 정보기술사업단의연구결과로수행되었음 비회원 : 서울대학교컴퓨터공학부 isan@idb.snu.ac.kr hwkim@idb.snu.ac.kr (Corresponding author 임 ) 종신회원 : 서울대학교컴퓨터공학부교수 hjk@snu.ac.kr 논문접수 : 2012년 1월 4일심사완료 : 2012년 3월 22일 CopyrightC2012 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 데이타베이스제39권제4호 (2012.8) 1. 서론최근 information stream이정보인지의보편적인수단으로활용되고있다. Information stream이란트위터, 페이스북, 구글리더혹은다른 RSS 리더어플리케이션처럼웹 2.0 정보공급원의최신업데이트를받아볼수있는응용을말한다. 웹 2.0 기술의발달과모바일기기의광범위한보급으로수많은컨텐츠들이온라인상에쏟아져나오고있다. 지난 10년간생성된데이터보다최근 2년간생성된데이터의양이훨씬많으며, 2011년한해에만 1.8ZB의디지털정보가쏟아져나왔으며이수치는점점더늘어날것으로예상되고있다 [1]. 그결과 information stream을이용하여정보를소비하는사용자들은자신이구독하는사용자가늘어남에따라기
텍스트랭크알고리즘을이용한사용자타임라인요약기법 239 하급수적으로늘어나는정보량을모두처리할수없게되는정보과다현상 (information overload) 을겪게된다. 따라서대용량정보들을사람이처리할수있는정보량이하로요약해주는기술이필요하게된다. 트위터는트윗이라는 140자이하의단문을발행할수있는마이크로블로깅서비스이다. 트위터에서사용자들은팔로우관계를형성하여다른사용자의트윗을구독할수있다. 트위터는 2006년 3월서비스를시작한이래로꾸준히사용자가늘었으며 2011년 3월 1억 7 천 5백만명의사용자를보유하고있고, 하루평균 46만명의새로운사용자가꾸준히유입되고있다. 소셜미디어에서상대적으로뒤쳐졌던대한민국도최근트위터사용자가폭발적으로늘고있다. 2011년 11월현재대한민국을지역기반으로하고있는사용자의숫자가약 497만명으로집계되고있으며그숫자는빠르게늘고있다. 국내에서트위터의영향력도갈수록늘어나고있다. 이렇게트위터사용자가늘어남에따라트위터상에유통되는트윗의양도폭발적으로늘어나게된다. 사용자는점점더많은사용자를팔로잉하게되고, 점점더많은양의트윗을구독하게된다. 그렇게되면사용자의타임라인은점점더많은수의트윗들로채워지게되고, 결국사용자가처리할수있는한계량을넘어서게된다. 트위터에서도실시간트렌드라는기능을제공하여선택된지역에서활발하게전달되고있는트윗들의주제를보여주고있다. 하지만아직대한민국은대상지역에포함되지않고있으며실시간트렌드는사용자의타임라인이아니라사용자가살고있는지역전체에서유통되고있는거시적인주제를의미하기때문에사용자개개인의관심사와부합하지않는다. 따라서본논문에서는트위터전체가아니라사용자개개인의타임라인을이루고있는트윗들을대상으로키워드를추출하여정보과다문제를해결하는기법을연구하였다. 본논문의구성은다음과같다. 2장에서트위터상의정보를다루는연구들에대해살펴보고, 3장에서텍스트랭크알고리즘에대해서상세히다룬다. 4장에서는트위터환경에맞게텍스트랭크알고리즘을적용하여주제를뽑아내는시스템을제안하며, 5장에서해당시스템의성능을평가하는실험방법과평가에대해설명한다. 마지막으로 6장에서는본논문에서제안한키워드추출방법에대한결론과향후연구에대해서언급한다. 2. 관련연구트위터가기존의매스미디어를대체하는소셜미디어로써의기능을갖게되면서트위터상에유통되는정보를다루는연구들이활발히이루어지고있다. 기존의소셜네트워크라는측면의트위터와소설미디어라는측 면의트위터의특성을비교하여미디어로써트위터의특징을설명하는연구가진행되었다 [2]. 미디어로써트위터와모바일디바이스의특징인위치정보를결합하여특정지역에서어떤뉴스가발생하였는지알려주는 TwitterStand 라는시스템도연구되었다 [3]. 트위터의가장큰특징은실시간정보전달에있다. [4] 에서는트위터상에유통되고있는실시간트윗들을분석하여검색엔진의성능을향상시켰다. 사용자가검색쿼리를입력했을때, Twinner라는시스템이쿼리가트위터에서실시간으로논의되고있는주제인지판단하여, 검색의도가뉴스검색인지판단한뒤, 뉴스일경우검색쿼리를확장하여보다정확한결과를보여주도록도와준다. 트위터의이런강력한정보전달능력은때로잘못된루머의전파를야기한다. [5] 에서는트위터상에유통되는트윗들중에서정보성트윗만을판별하는시스템을제안하였다. 뉴스와관련된트윗을수작업으로분류한다음, 해당뉴스트윗의신뢰도를평가하였다. 트윗들을기술할수있는여러가지특성들을정의하고, 이들을이용해기계학습프로세스를이용해자동으로트윗의신뢰도를평가해주는연구를하였다. 다수의트윗에서하나의커다란토픽을추출해내는시스템도제안되었다. [6] 는수많은트윗들을분석하여사용자가질의한쿼리와같이사용된키워드그리고관련된트윗들을분류해서보여준다. [7] 은텍스트랭크알고리즘을이용하여트위터사용자를가장잘표현할수있는태그를추출하는기법에대하여연구하였다. 3. 텍스트랭크알고리즘 Kleinberg[8] 가제안한 HITS 알고리즘이나 Sergey Brin과 Larry Page가제안한구글의 PageRank 알고리즘 [9] 같은그래프기반랭킹알고리즘은소셜네트워크, 웹의링크구조, 논문의인용네트워크등의분석에다방면으로사용되어왔다. 그래프기반의랭킹알고리즘은네트워크상에서각정점의중요도를결정하는일련의작업을말한다. 그래프기반의랭킹알고리즘으로그래프네트워크에서가장핵심적인혹은가장중요한정점들을뽑아낼수있다. 텍스트랭크알고리즘 [10] 은그래프기반랭크알고리즘을자연어처리에응용한기법이다. 텍스트를그래프로모델링한뒤그래프기반랭킹알고리즘을적용한후, 핵심적인정점을추출해내는방법을사용하였다. 본논문에서는키워드추출이라는자연어처리응용을수행하기위하여텍스트랭크알고리즘을키워드추출에맞도록정의하였다. 3.1 텍스트의그래프모델링텍스트랭크알고리즘을이용하여키워드를추출하기위해서는분석할텍스트를그래프로모델링해야한다.
240 정보과학회논문지 : 데이타베이스제 39 권제 4 호 (2012.8) 우선, 그래프를구성할정점을결정한다. 키워드추출작업에적합한정점의단위는명사이다. 따라서주어진텍스트의형태소를분석하여명사를추출해낸후해당명사들을이용하여그래프를구성한다. 이때색인어로서의미가없는불용어들을제거하면성능향상에도움이된다. 이와같은과정에서그래프에포함될정점들이결정되면정점들사이의관계를이용해서간선을그리는단계로넘어간다. 가장간단한방법으로동시출현 (cooccurrence) 관계를이용해서간선을생성할수있다. 크기가 N인윈도우안에두토큰이등장한다면두토큰사이에동시출현관계가있다고할수있다. 이때, 동시출현빈도수가간선의가중치가될수있다. 따라서두키워드사이의가중치는등장하는횟수가되므로자주등장두키워드사이의관계는가중치로모델링하여의미를나타내도록하였다. 3.2 그래프기반랭킹알고리즘적용주어진텍스트로부터생성된그래프에그래프기반랭킹알고리즘을적용하여각정점의스코어를얻어낸다. 이때, 적용할그래프기반랭크알고리즘은페이지랭크알고리즘을이용한다. (1) V i 는그래프상의 i 번째정점을의미하며, PR(V i) 는페이지랭크알고리즘에의해얻어진정점 V i 의스코어를의미한다. In (V j) 는정점 V i 를가리키는이웃정점의집합을의미하며, Out (V i) 는정점 V i 가가리키는이웃정점의집합을의미한다. 마지막으로 d 는 damping factor 값으로랜덤서퍼모델 (random surfer model) 을반영하기위한값이다. 3.1절에의해생성된그래프는무방향성가중치그래프이다. 하지만식 (1) 에서볼수있듯이페이지랭크알고리즘은가중치가없는방향성그래프에적용할수있도록고안된알고리즘이다. 따라서페이지랭크알고리즘을무방향성가중치그래프에맞도록변형시켜야한다. 우선무방향성그래프의경우하나의무방향성간선을두개의왕복하는방향성간선으로생각하면쉽게변형이가능하다. 가중치를고려하기위해 [11] 에서는페이지랭크알고리즘을다음과같이가중치그래프에맞도록변형시켰다. (2) w jj 는정점 V i 와정점 V j 사이에존재하는간선의가중치를의미한다. 실제구현을할때, damping factor 인 d의값은 0.85를기본으로사용한다. 이식으로그래프를이루고있는모든정점에대하여스코어를반복해서계산한다. 이반복적인계산은모든정점의스코어의 변동폭이특정범위이내로수렴할때까지계속된다. 그래프기반의랭크알고리즘을이용하여얻어진정점의스코어를기준으로내림차순정렬을하여상위 K개를뽑게되면해당정점이텍스트를가장잘설명할수있는키워드가된다. 3.3 텍스트랭크알고리즘의장점여러자연어처리응용중에텍스트랭크알고리즘만이갖는장점이있다. 첫번째로텍스트랭크알고리즘은별도의학습데이터가필요하지않은 unsupervised learning 알고리즘이다. 많은경우학습데이터를얻을수없거나얻어진학습데이터의정확도가떨어진다. 이런경우 unsupervised learning 알고리즘인텍스트랭크알고리즘이유용하게쓰인다. 특히트위터와같이최신정보위주의텍스트의경우더욱 unsupervised learning 알고리즘의사용이타당하다. 두번째로모듈화된구성에있다. 텍스트랭크알고리즘은그래프로모델링하는모듈, 그래프기반랭킹알고리즘을적용하는모듈, 알고리즘에의해얻어진스코어를기반으로적절한정점을추출해내는모듈로이루어져있다. 따라서각모듈을수행하고자하는자연어처리작업의특성에맞게수정하거나대체할수있다. 텍스트랭크알고리즘의가장큰장점은작업에따라적절하게적용할수있는유연성에있다. 4. 텍스트랭크알고리즘을이용한타임라인요약본논문에서는텍스트랭크알고리즘을트위터의타임라인을구성하고있는트윗들의키워드를추출하는응용에사용한다. 트위터에서유통되고있는트윗들의주제는매우빠르게변하고있다. 어제의주제와오늘의주제가다르고나날이발행되는트윗의수는늘어나고있기때문에현재논의되고있는주제를파악하기가점점더어려워지고있다. 트위터에서도이런문제를인지하여실시간트렌드라는기능을제공하고있지만실시간트렌드는개인의관심사를반영하지못하고있다. 따라서실시간트렌드와유사한기능을개인의관심사가반영된타임라인에적용을한다면트위터전역에대한실시간트렌드에비해서개인에게유용한정보를줄수있다. 본연구에서제안하는타임라인요약과정은총 6단계를거치게된다. 사용자개인의타임라인을수집하는 Collect tweets 단계를거쳐, 정보성트윗을걸러내는 Filtering 단계, 걸러진트윗을이용하여그래프로모델링하는 Graph Modeling 단계, 모델링된그래프에페이지랭크알고리즘을적용하여스코어를구하는 Graph-based Rank Algorithm 단계, 구해진스코어를기반으로토픽키워드와하위키워드를추출하는
텍스트랭크알고리즘을이용한사용자타임라인요약기법 241 Extract Topic Keyword 단계, 마지막으로구해낸키워드들을이용해서키워드에해당하는트윗들을분류하는 Categorizing tweets 단계를거치게된다. 4.1 트윗수집 & 필터링단계본연구의분석대상은트위터전체데이터가아니라한트위터사용자개인의타임라인이다. 사용자의타임라인을이루고있는트윗들을가져오기위해트위터에서제공하는 open API를이용한다. 트위터상에유통되고있는트윗들을수집하여분류해본결과 29.5% 의트윗이뉴스정보를담고있었고, 34.9% 의트윗이일상적인대화를담고있는것으로나타났다 [5]. 대화를담고있는트윗의경우, 개인의일상을담고있는경우가많아트렌드를반영하지못한다. 따라서타임라인을정리하는본논문의분석대상에서제외하였다. 비정보성트윗을걸러내기위하여트윗의 4가지특성을이용하였다. URL을포함한트윗의경우정보성트윗을가능성이높다. 트윗된트윗역시정보성트윗일가능성이높다. 답글의경우비정보성트윗일가능성이높다. 이벤트, 경품 같은특정키워드가들어있는트윗의경우트렌드보다이벤트적인성격이강해비정보성트윗일가능성이높다. 이 4가지특성을이용하여분석에포함될트윗들을필터링하여정확도를높였다. 4.2 그래프모델링단계텍스트랭크알고리즘을적용하기위하여필터링된정보성트윗을이용하여타임라인그래프를구축한다. 4.2.1 정점의선택텍스트를그래프로모델링하고자할때, 우선정점으로어떤단위를사용할것인가를정해야한다. 본논문에서는타임라인을이루고있는핵심키워드를뽑아내는작업을하게되므로명사를정점으로취하게된다. 텍스트에서명사를추출해내는과정을위해형태소분석기로 Lucene KoreanAnalyzer라는 Java 기반의오픈프로젝트라이브러리를사용하였다 [12]. 4.2.2 간선의선택텍스트에서명사를추출하여단어사이의동시출현관계를이용하여간선을만든다. 이때, 함께등장하는빈도수를가중치로설정한다. 예를들어, 스티브잡스 와 애플 이라는단어가함께등장한횟수가 10이고, 스티브잡스 와 겨울 이라는단어가한번함께등장했다고하자. 가중치를고려하지않는다면시스템의전반적인정확도가떨어지게된다. 따라서보다많은횟수의동시출현관계가있다면그빈도수를가중치로두어, 두단어사이의관련된정도를고려하도록하였다. 4.2.3 전체타임라인에대한그래프모델링타임라인을정리하기위해서는각트윗에대한그래프를하나의커다란타임라인그래프로통합할필요가 있다. 타임라인그래프를만들때타임라인을이루고있는각트윗을그래프로모델링하고, 트윗들의정점과간선들의합집합을구하면타임라인전체에대한그래프를얻을수있다. 간선의가중치의경우합집합을구하는과정에서모두합한다. 예를들어트윗 1에서정점 A와정점 B사이간선의가중치가 3이고, 트윗 2에서정점 A와정점 B사이간선의가중치가 2라고할때, 타임라인그래프로통합하는과정에서정점 A와정점 B사이간선의가중치는 5가된다. 이렇게하여타임라인전반에걸쳐빈번히동시출현관계가있는단어사이의관련된정도를더중요하게모델링할수있다. 4.3 그래프기반랭크알고리즘의적용 4.2 절에서모델링한그래프는가중치를가지고있는무방향성그래프이다. 따라서이그래프에적용할페이지랭크알고리즘은식 (1) 이아닌가중치그래프로적용할수있도록변형된식 (2) 를사용한다. 4.4 타임라인키워드추출페이지랭크알고리즘을적용하여얻은스코어를기반으로타임라인을형성하고있는트윗의키워드를추출하게된다. 4.4.1 스코어기반추출우선가장단순한방식으로그래프전체정점의집합을스코어를기준으로내림차순정렬하여스코어가높은순으로상위 K개의키워드를뽑아내는방법이있다. 이방법을이용하게되면, 텍스트를이루고있는주요키워드를 K개뽑을수있다. 이방법은주로텍스트가단일주제로이루어져있을경우높은정확도를갖게된다. 트위터사용자는독자로서의역할과필자로서의역할을갖게되는데 [13], 필자로서의트위터사용자는일관된주제의트윗을발행하는경향이있다. 하지만독자로서의트위터사용자는다양한주제를구독하는경향이있다. 따라서트위터타임라인의경우일관된주제를다루고있지않아스코어를기준으로상위 K개를추출할경우전체내용중주요주제에대한키워드만중복되어추출된다. 그렇기때문에스코어를기준으로상위 K개를추출하는방법이외의다른방법을도입할필요가생긴다. 4.4.2 산봉우리개념을이용한키워드추출방법본논문에서는산봉우리개념을그래프에적용하여추출되는키워드의편향성을제거하는방법을제안하였다. 지도를들여다보면, 산의지형을논할때, 산의여러지점중에주변보다높은지역을 xx봉 이라고하여중요하게생각한다. 이봉우리를기준으로주변지역을말하게된다. 이개념을스코어가매겨진그래프에적용을해보면그래프에서도주변보다스코어가높은정점에의미를두어토픽레이블로하고, 주변을이루고있는
242 정보과학회논문지 : 데이타베이스제 39 권제 4 호 (2012.8) 정점이토픽레이블을부가설명하는하위키워드가된다고할수있다. 이개념을이용하면타임라인에서비슷한주제를나타내고있는키워드들은모두핵심키워드의하위키워드로모여묶이게된다. 따라서상위 K 개안의중복을줄일수있고, 중요하지만숨겨져있던비주류주제들에대한키워드가수면위로떠오르게된다. 표 1에산봉우리개념을적용한알고리즘을간략하게기술하였다. 표 1 산봉우리개념을이용한핵심키워드추출 Input : Graph G and score of their vertices Output : List of keywords and their sub keywords 1: K = number of keywords to extract 2: L = List of vertices 3: P = List of keywords 4: for 1 < n < K 5: store the vertex that has highest core to T 6: add T to L 7: delete T from G 8: while L is not empty 9: Fetch one vertex from L 10: Add the vertex to T s sub keyword list 11: Delete the vertex from L 12: Fetch that vertex s neighbors 13: If(neighbors has lower score than the vertex) then 14: Add that neighbors to L 15: Delete that neighbors from G 16: End if 17: End while 18: End for 4.5 트윗분류타임라인을이루고있는핵심키워드 K개를뽑은뒤마지막으로각키워드에해당하는트윗을분류하는작업을거치게된다. 트윗의분류는간단히토픽레이블혹은하위키워드의등장여부로결정하게된다. 예를들어토픽레이블이 애플 이고하위키워드가 아이폰, 아이패드 일때, 애플이라는토픽에해당하는트윗으로 애플, 아이폰 혹은 아이패드 가들어있는트윗이분류된다. 이과정을위해트윗들을그래프로모델링하는과정에서각트윗에트윗번호를부여하고그번호와트윗이담고있는명사를기반으로역색인 (inverted index) 을구축하여이용하였다. 5. 성능평가 이장에서는산봉우리개념을응용한타임라인정리기법의성능을측정하기위한실험의환경및실험방법, 실험결과를분석한다. 가장단순하고널리이용되고있는키워드추출방법인빈도수기반의방식과본연구에서제안한텍스트랭크기반에산봉우리개념을 더한방식을비교하여성능을평가한다. 5.1 실험환경및데이터실험에사용할데이터수집을위해실험용트위터계정을생성하였다. 표2에서볼수있듯이실험용트위터계정은총 47개의트위터를팔로잉하고있으며팔로잉대상은트위터상에서주요정보공급원역할을하고있는각분야의주요언론, 정치인, 평론가, 유명블로거등으로구성되어있다. 이 47개의계정들이발행하는트윗의개수는하루평균 800개이상이고, 다양한주제를다루고있다. 실험에사용된데이터는 2011년 11월 25일하루동안테스트계정의타임라인에서수집된 764개의트윗으로진행을하였다. 분석에사용된시스템은 Intel Core i7 2.93Hz의 CPU와 8GB의메모리사이즈를갖는 Windows 7 Professional K 64bit 운영체제를갖는다. 표 2 실험용계정이팔로잉하고있는트위터목록 주요언론 정치인 기타 매일경제, 아이비타임즈, 컨슈머타임스, Daily Asiaeconomy, Fudzilla, 전자신문, 스포츠한국, 스포츠조선 Baseball, 엑스포츠뉴스, SBS, 피디수첩, 미디어다음, MBC, 매일경제뉴스속보국, 프레시안, 오마이뉴스, The Korea Times, 조선일보, 연합뉴스, EBS, KBS, 파이낸셜뉴스, 미디어오늘, 블로터닷넷, 시사인, 한겨례, 경향신문, 지디넷코리아, 동아일보, 중앙일보, 중앙일보편집국, 임종인, 김종철, 조승수, 정동영, 유시민, 김문수, 안희정, 심상정, 광파리, 이해완기자, IT수다떨기, 주진우기자, 이상호기자, 탁현민, 고재열기자, 5.1.1 모델링방법사용자의타임라인을그래프로모델링하는과정에서 unigram과 bigram으로나누어평가하였다. Unigram의경우하나의단어가정점이되고, 동시출현의윈도우크기는 2가된다. Bigram의경우연속되는두개의단어가정점이되고, 동시출현윈도우사이즈는 3으로하였다. 5.2 성능평가기준타임라인의요약이얼마나잘되었는지성능을평가하기위하여정보포함범위 (coverage), 토픽간유사도, 토픽내일관도의총 3가지평가기준을정하였다. 5.2.1 정보포함범위최상위 K개의토픽을추출하였을때, 그에해당하는트윗을분류하게된다. 이때, 상위 K개의토픽이얼마나많은트윗을분류하는지커버리지를평가하게된다. 정확도가같은알고리즘이라할때, 커버리지가더높은쪽이더많은트윗을분류할수있다는뜻이다. 5.2.2 토픽간유사도타임라인을이루고있는 K개의토픽들을뽑은후 K
텍스트랭크알고리즘을이용한사용자타임라인요약기법 243 그림 1 각주제별토픽벡터생성 개의토픽들이얼마나잘분포되었는지평가해야한다. 이를위해서각토픽에분류된트윗의명사를추출하여그림 1에서볼수있는것처럼토픽벡터를만든다. 이때, 트윗을이루고있는명사들이토픽벡터의성분이된다. 벡터를이루고있는성분의값은출현비율에따라결정된다. 이방법을이용하면공통적으로많이등장하는단어의경우성분값이높아해당토픽을더잘설명한다고할수있고, 우연히쓰인단어의경우성분값이작아지기때문에영향력이핵심단어에비해떨어지게된다. 이렇게상위 K개의토픽에대해토픽벡터를생성한다음, 각토픽이다루는주제가얼마나유사한지코사인유사도를이용하여측정하게된다. K번째토픽의유사도는기존의 K-1개의토픽벡터와 K 번째토픽벡터사이의코사인유사도를모두구해가장큰값으로한다. 5.2.3 토픽내일관도잘된요약은토픽간분배정도뿐만아니라분류된트윗들이일관된주제를다루고있어야한다. 트윗의일관도를측정하기위하여마찬가지로토픽벡터를사용하였다. 각토픽의토픽벡터를구성한다음각트윗의명사를벡터로구성하여토픽벡터와의코사인유사도를구한다. 각토픽의주제내일관도는모든트윗에대해이런과정을거친후얻어진값을평균내어측정하였다. 이때, 트윗의명사벡터는각트윗을이루고있는명사들을성분으로하고값은일괄적으로 1로한다. 토픽벡터의경우평균의성격이강하므로이를이용하여각트윗들이얼마나평균에가까운주제를다루고있는지주제의분산정도를알수있다. 5.3 실험결과앞의절에서설명한기준을이용하여본연구에서제안한텍스트랭크를이용한방법과빈도수기반방법의성능을평가, 분석하였다. 실험결과의 graph는그래프기반알고리즘, freq는빈수기반알고리즘을의미한다. Uni는 unigram의경우, bi는 bigram의경우를의미한다. 예를들어 Graph-Uni의결과는 graph 기반알고리즘을 unigram으로적용한결과이다. 5.3.1 정보포함범위 그림 2 분류방법에따른커버리지그림 2에서볼수있듯이커버리지의경우 unigram 의경우와 bigram의경우모두빈도수기반의방법보다그래프기반의방법이높았다. 따라서같은숫자의트윗을요약하는데에필요한키워드의개수가빈도수기반의방법이그래프기반의방법보다더많으며정확도가비슷하다고할때, 요약능력이그래프기반의방법이더뛰어나다고할수있다. Bigram과 unigram의경우 unigram을이용한방법이커버리지가더높았다. 이를해석하면, bigram으로그래프를모델링한경우주제를더작은여러개의주제로나누게되어상위 K개의키워드가포함할수있는트윗의개수가적어지게되는것이다. 5.3.2 토픽간유사도토픽의분배정도를나타내는토픽간유사도의경우그래프기반의방식이더고르게주제를분류하는것으로나타났다. 상위 K개의토픽들의유사도값을 5.2.2 절에서정의한방법에따라구한뒤, 평균을내어 K의값이늘어남에따라변화추이를구해보았다. 그결과그림 3에서볼수있듯이빈도수기반의방식으로키워드를뽑았을때, 중복되는주제에대한토픽이더많이뽑혀유사도가그래프기반의유사도보다 2배이상높게나타났다. 따라서그래프기반의방식이좀더주제를고르게뽑아내는것으로볼수있다. 그림 3 분류방법에따른토픽간유사도 5.3.3 토픽내일관도그림 4를보면주제내일관도의경우대체로빈도수
244 정보과학회논문지 : 데이타베이스제 39 권제 4 호 (2012.8) 키워드벡터가아닌키워드의시맨틱을이용할수있는방식으로하였다면본연구의방식과빈도수기반방식의차이는더줄어들것이다. 7. 결론및향후연구 그림 4 분류방법에따른토픽내일관도기반의방법이그래프기반의방법보다높은일관도를가진다는것을알수있다. 이는주제내일관도의정의에따른현상으로빈도수기반의경우무조건하나이상의키워드가모든트윗에포함되어있어기본적으로일관도가높게나온다. 하지만 K가늘어날수록그래프기반의방법의유사도역시증가하여상위 20개의토픽을뽑았을때, 일관도는빈도수기반의방법과그래프기반의방법에서크게차이가나지않았다. 특히 bigram 의경우빈도수기반의방법과그래프기반의방법사이에일관도차이가거의없었다. 6. 논의사항세가지기준으로빈도수기반의방식과본연구에서제안하는방법을평가한결과본연구에서제안한방법이더높은성능을갖는것으로나타났다. 정보의포함범위측면에서분석을해보면, 빈도수기반의방식은키워드하나가포함된트윗들을포함하지만, 본연구에서제안한방식은하나의키워드와그키워드에연결된하위키워드들을포함한트윗들을골라온다. 따라서하나의토픽이포함할수있는양은하나의키워드로트윗을가져오는빈도수기반의방식보다여러개의키워드로트윗을가져오는본연구의방식이더뛰어난것으로나타났다. 토픽간유사도의경우얼마나주제를잘분류했는지를측정할수있다. 트위터의특성상한가지주제가이슈화되면비슷한주제를다루는키워드들이많이등장하게된다. 반면본연구에서제안한방식은비슷한주제를다루고있는키워드를하나의덩어리로합쳐서다루기때문에분류된주제들이더잘분배되어있을수있는것이다. 토픽내유사도는빈도수기반의방식이다소높은것으로나타났다. 빈도수기반의방식은하나의키워드로트윗을가져온반면본연구에서제안한방식은하나의토픽키워드와여러하위키워드를이용해서가져왔기때문에빈도수기반의방식이토픽내의유사도가높을수밖에없다. 만약토픽내유사도측정방식을단순 본연구에서는트위터의타임라인에서문제가되고있는정보과다현상을해결하기위한타임라인요약기법을제안하였다. 텍스트랭크알고리즘을사용하여트위터의타임라인을정리하고비슷한키워드들을하나로묶어주는산봉우리개념이적용된알고리즘을제안하였으며, 가장널리이용되는트렌딩토픽추출방법인빈도수기반의방법과성능을비교하였다. 또한그래프로모델링하는데있어서 unigram과 bigram의성능차이를비교해보았다. 실험결과에서볼수있듯이본연구에서제안한텍스트랭크알고리즘과산봉우리개념을적용한타임라인요약기법은가장널리사용되고있는빈도수기반의방법에비해서향상된성능을보였다. Unigram과 bigram을비교한결과 unigram의경우커버리지는높았지만토픽간유사도와토픽내일관도의경우 bigram 이훨씬더좋은성능을보였다. 이는 bigram의경우주제를좀더세분화하여모델링하기때문으로보인다. 향후연구로, 본연구에서제안한모델에의미론적인요소가가미된다면더정확한요약을할수있을것이다. 추가적으로온톨로지를이용한다면단어가가지고있는의미를보다정확하게사용할수있을것이다. 온톨로지정보를시스템에통합하여동의어를효과적으로처리한다면좀더뛰어난성능을보일수있을것이다. 또한, unigram과 bigram의두가지그래프모델링방법을효과적으로함께사용한다면 bigram의장점인높은정확도와 unigram의장점인커버리지를가질수있을것이다. 참고문헌 [ 1 ] http://www.bloter.net/archives/83805 [2] H. Kwak, C. Lee, H. park, S. Moon, "What is Twitter, a Social Network or a News Media?" Proc. of the 19th International World Wide Web Conference, 2010. [3] J. Sankaranarayanan, H. Samet, B. Teitlery, M. Lieberman, J. Sperling, "TwitterStand: News in Tweets," Proc. of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2009. [4] S. Abrol, L. Khan, "Twinner: Understanding News Queries with Geo-contents using Twitter," Proc. of the 6th Workshop on Geographic Information Retrieval, 2010.
텍스트랭크알고리즘을이용한사용자타임라인요약기법 245 [5] C. Castillo, M. Mendoza, B. Poblete, "nformation Credibility on Twitter," Proc. of the 20th International World Wide Web Conference, 2011. [6] B. O Connor, M. Krieger, D. Ahn, "TweetMotif: Exploratory Search and Topic Summarization for Twitter," Proc. of the International AAAI Conference on Weblogs and Social Media, 2010. [7] W. Wu, B. Zhang, M. Ostendorf, "Automatic Generation of Personalized Annotation Tags for Twitter Users," Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2010. [8] J. Kleinberg, "Authoritative Sources in a Hyperlinked Environment," Journal of the ACM, 1999. [9] S. Brin, L. Page, "The Anatomy of a Large-scale Hypertextual Web Search Engine," Computer Networks and ISDN Systems, 1998. [10] R. Mihalcea and P. Tarau, "TextRank: Brigning Order into Texts," Proc. of EMNLP and the Conference on Empirical Methods in Natural Language Processing, 2004. [11] R. Mihalcea, "Graph-based Ranking Algorithms for Setence Extraction Applied to Text Summarization," Proc. of the ACL on Interactive poster and demonstration sessions, 2004. [12] cafe.naver.com/korlucene [13] M. Welch, U. Schonfeld, D. He, J. Cho, "Topical Semantics of Twitter Links," Proc. of the fourth ACM International Conference on Web Search and Data Mining, 2011. 김형주 1982년서울대학교전산학과 ( 학사 ). 1985년 Univ. of Texas at Austin( 석사 ). 1988년 Univ. of Texas at Austin( 박사 ). 1988년 ~1990년 Georgia Institute of Technology( 부교수 ). 1991년~현재서울대학교컴퓨터공학부교수. 관심분야는데이타베이스, XML, 시맨틱웹, 온톨로지 안인석 2010 년단국대학교전자컴퓨터공학부 ( 학사 ). 2012 년서울대학교컴퓨터공학부 ( 석사 ) 2012 년 ~ 현재티베로재직중. 관심분야는데이터베이스, 소셜네트워크, 시맨틱웹, 스토리지시스템 김현우 2007 년 KAIST 전산학과 ( 학사 ). 2007 년 ~ 현재서울대학교컴퓨터공학부석박통합과정재학중. 관심분야는추천, 태깅, 데이터베이스