<30302DB8F1C2F7BFDC2E687770>

Transcription

1 Journal of the Korea Institute of Information and Communication Engineering 하둡과의미특징을이용한문서요약 김철원 * Document Summarization using Semantic Feature and Hadoop Chul-Won Kim * Department of Computer Engineering, Honam University, Gwangju , Korea 요약 본논문은하둡기반의분산병렬처리에의한문서의의미특징을추출하고, 추출된의미특징을이용하여문서를요약하는새로운방법을제안한다. 제안된방법은문서요약에비음수분해된문서의의미특징을이용함으로써문서의내부구조를잘표현할수있다. 또한하둡을이용하여빅데이터의문서를요약할수있다. 실험결과제안방법이단일컴퓨터환경에서처리할수없는대용량의문서를요약할수있음을보인다. ABSTRACT In this paper, we proposes a new document summarization method using the extracted semantic feature which the semantic feature is extracted by distributed parallel processing based Hadoop. The proposed method can well represent the inherent structure of documents using the semantic feature by the non-negative matrix factorization (NMF). In addition, it can summarize the big data document using Hadoop. The experimental results demonstrate that the proposed method can summarize the big data document which a single computer can not summarize those. 키워드 : 문서요약, 의미특징, 하둡, 분산병렬처리 Key word : Document summarization, semantic feature, Hadoop, distributed parallel processing 접수일자 : 심사완료일자 : 게재확정일자 : * Corresponding Author Chul-Won Kim ( cwkim@honam.am.kr,Tel: ) Department of Computer Engineering,Honam University,Gwangju ,Korea Open Access print ISSN: online ISSN: This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License( by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited. Copyright C The Korea Institute of Information and Communication Engineering.

2 Ⅰ. 서론 Ⅱ. 관련연구 통신기기의발전은사용자들로하여금인터넷상의정보를더욱쉽게접근할수있게하고있으며, 이로인하여인터넷상의정보증가를더욱가속화시키고있다. 또한인터넷사용이가능한소형통신기기들의보급증가는대용량의인터넷정보를소형통신기기의화면에효율적으로표시할수있는정보요약기술에대한필요성을증가시키기고있다. 인터넷정보의요약기술은검색엔진의요약문인스니핏, 정보추출, 텍스트마이닝, 질의응답분야등에서다양한통계적방법론을사용하여요약의정확률을향상시키기위해연구되어왔다. 그러나기존연구는단일코어또는단일컴퓨터상황에서수행되기때문에, 현재와같인폭발적으로증가하는인터넷및소셜네트워크서비스등의대량의정보에대한신속한요약요구를처리할수없는상황에직면하고있다. 즉, 지금까지정보요약에관한연구는다양한통계적방법론을이용하여요약정보의성능향상에목적을두고수행되어높은수준의요약율을보여주고있다. 그렇지만대부분의문서요약연구가정확률에맞추어져있어대용량의자료에대한요약속도또는요약의처리율에대한연구를미흡한실정이다. 본연구는대용량의문서로부터정보를요약할수있는문서요약방법을연구한다. 제안방법은대용량의문서를전처리하여하둡 [1] 에분산저장하고, 분산저장된자료로부터문서의의미특징을병렬처리하여추출하며, 추출된의미특징을이용하여문서를요약한다. 제안방법은 PC(personal computer, 개인용컴퓨터 ) 로구성된하둡기반의노드에대량의문서자료를저장함으로써단일 PC에처리할수없는대용량의문서를요약할수있는장점을갖는다. 하둡은분산파일시스템 (distribution file system) 과분산컴퓨팅을위한맵리듀스 (MapReduce) 를포함하여개발된분산병렬처리시스템이다 [1]. 본논문의구성은다음과같다. 2장에서는관련연구로문서요약과하둡프레임워크에대하여알아본다. 3 장에서는제안방법인문서요약방법을, 제4장에서는실험및평가에대해기술한다. 마지막으로제5장에서는결론을맺는다 문서요약다음은본논문의제안방법과관련된최근의문서요약연구들이다. Nastase는위키피디아와워드넷의외부지식과확장활동에의한주제기반다중문서요약방법을제안하였다. 이들의방법은외부지식을이용하여사용자의질의를확장하였으며, 확장된질의와관련된문서를문법적으로연결된용어의그래프로표현하여문서를요약하였다 [2]. Ramanathan외저자들은언어에독립적인단일문서요약방법을제안하였다. 이들의방법은문서의문장과위키피디아의의미적개념과일치시켜문서를요약한다 [3]. Ye와저자들은위키피디아기반으로새로운문서개념격자를이용한문서요약방법을제안하였다. 이들이제안한방법은문장간의연관관계를얻기위하여위키피디아의내부연결에의한위키피디아개념을소개하였으며, 위키개념과비텍스트특징을이용하여확장된문서개념격자모델 (extended document concept lattice model) 을제안하였다 [4]. Gong외저자들은위키피디아를이용한요약시스템을제안하였다. 이들이제안한방법은위키피디아의개념을인식한후에, 개념에가중치를주고특징을개산하여요약문을생성한다 [5]. 위키피디아를이용한문서요약방법은문서요약하기전에대량의위피키디아자료를전처리하거나학습함으로써많은자원을소모해야하는문제를가지고있다. Sanderson은문서상의중요한문장과사용자가확장한질의를이용하여문서를요약방법을제안하였다 [6]. Tombros와 Sanderson은문서의형식에포함된정보인제목, 주제, 용어의빈도정보, 질의등을점수화하여서사용자가보조정보로활용할수있는문서요약방법을제안하였다 [7]. Varadarajan과 Hristidis는질의와가장관련이높은문장과의미연관을이용하여서문서로부터추출된복합주제를적용하여서질의에특화된문서요약방법을제안하였다 [8] 하둡프레임워크하둡프레임워크 (hadoop framework) 는응용프로그램들에게대용량의데이터를처리하게할수있도록지원하는분산프레임워크이다. 하둡은아파치프로젝트의하나로분산파일시스템 (HDFS: hadoop distributed 2156

3 하둡과의미특징을이용한문서요약 file system) 과맵리듀스 (MapReduce) 를포함하고있다. HDFS는낮은성능의컴퓨터에도대용량의데이터를처리할수있도록지원하는파일시스템으로고가용성 (fault-tolerant) 을제공하고있다 [1]. HDFS는하나의마스터노드와여러개의슬레이브노드로구성된다. 마스터노드는파일시스템네임스페이스를관리하고클라이언트에의한파일접근을통제하는단일네임노드로구성된다. 각슬레이브노드는저장장치를관리하는데이터노드가있다. HDFS는파일을하나또는그이상의블록으로분할하여데이터노드에저장한다. 네임노드는파일과디렉토리의열기, 닫기, 이름변경과같은파일시스템의네임스페이스동작을수행하고데이터노드의블록일치검사하여판단한다. 데이터노드는네임노드의지시로블록생성, 삭제, 복제를수행한다 [1]. 맵리듀스는분산및병렬로대용량의자료를효율적으로관리하기위하여 HDFS를기반으로개발되었다. 맵리듀스는병렬처리, 고가용성, 데이터분산및로드밸런싱등을지원한다. 맵리듀스는맵 (map) 과리듀스 (reduce) 의합성어로맵함수와리듀스함수의조합으로분산병렬응용프로그램을지원한다. 맵리듀스는데이터를 {key, value} 의쌍으로만들어분산병렬처리가가능하도록지원한다. 맵은사용자정의자료구조이며, 입력데이터에서 {key, value} 쌍으로구성된중간데이터를만들어리듀스에전달한다. 리듀스함수는 key 값을이용하여 value 값을합쳐출력한다 [1]. Ⅲ. 제안방법본논문에서는분산병렬처리기반의문서요약방법을제안한다. 제안방법은전처리, 분산병렬의미특징추출, 문서요약단계로구성된다. 전처리단계에서는문서를하둡에용어문장빈도행렬을분산저장하고, 분산병렬의미특징추출단계에서는분산저장된용어문장빈도행렬을병렬로비음수행렬하여의미특징을추출한다. 마지막요약단계에서는계산된의미특징을이용하여문서를요약한다. 다음그림1은제안된하둡기반의문서요약방법의개요이다. 그림 1. 하둡기반의문서요약방법정보 Fig. 1 Document summarization method based on Hadoop 3.1. 전처리일반적으로문서요약을위한전처리는문서집합에불용어를제거하고, 용어의어근을추출하여용어문장빈도행렬을생성한다. 그러나본논문의전처리단계는문서요약에분산병렬처리가가능하도록고려해야한다. 이를위해서본논문에서는다음과같이문서집합을전처리하여용어문장빈도행렬을하둡에분산저장한다. 첫째, 문서집합을문장집합으로분해한다. 둘째, 문장집합을머하우의문서벡터를만드는도구를이용하여용어문장빈도행렬을만든다. 즉, 머하우 (Mahout)[9] 도구인 SequenceFileFromDirectory 클래스의 seqdirectory와 SparseVectorFromSequenceFiles 클래스의 seq2sparse를이용한다. SequenceFileFrom Directory는디렉토리에속한문장집합을 SequenceFile 형식으로표현한중간단계의문서를생성한다. Sparse VectorFromSequenceFiles는 SequenceFile 형식의문서를용어문장빈도행렬로변환한다. 다음표1은두가지도구를이용하여용어문장빈도행렬을구성하는예제를보여준다. 표 1. 머하우를이용한용어문장빈도행렬생성 Table. 1 Construction of term-sentence frequency matrix using mahout bin/mahout seqdirectory -c UTF-8 -i summary/term/ -o term-seqfiles // summary 디렉토리의문장집합인 term 파일일중간파일인 term-seqfiles로변호나 bin/mahout seq2sparse -i term-seqfile/ -o term-vectors -ow // term-seqfiles 파일을용어문장빈도행렬인 term-vectors 파일로변환 2157

4 표1의도구를이용하여용어문장빈도행렬을생성하면하둡에는 df, tf, tfidf, dictionary, tokenizedsentences 등의값이각각의디렉토리에분산저장된다. 여기서저장되는값들은다음과같다. df에는문장의빈도수, tf에는용어의빈도수, tfidf는 tf와 df를이용한가중치벡터문서, dictionary에는용어와숫자로된 ID와매핑내용, tokenized-sentences는문장을개별단어로쪼개어저장된다 분산병렬의미특징추출문서요약은문서를대표할수있는중요한특징을나타내는의미특징 (semantic feature) 을이용함으로써요약의질을높일수있다. 주로이용되는문서의내부특징을추출하는방법으로는비음수행렬분해, 주성분분석등이있으며비음수행렬분해가가장의미있는특징을추출하는것으로알려져있다. 그러나이들방법은문서내부에잠재되어있는고유한특징 (inherent feature) 을행렬분해하여추출함으로써문서의양이많아질수록계산량이많아져의미특징추출이제한되는문제점을가지고있다. 본논문은문서양의증가시의미특징추출이제한되는문제를해결하기위해하둡을이용하여비음수행렬분해가분산병렬처리에의해계산이가능하도록제안한다. 비음수행렬분해알고리즘은다음과같이계산된다. 문장집합이 k개의의미특징벡터로구성된다고가정할때, 행렬 A를식 (2) 의목적함수가최소값을갖도록식 (3) 을반복하여서식 (1) 과같이비음수의미특징행렬 (NSFM, non-negative semantic feature matrix) W 와비음수의미변수행렬 (NSFM, non-negative variable matrix) H로분해한다 [10]. (1) (2) 여기서행렬 A는 m n개의원소로구성되는행렬이며, 행렬 W 는 m k개의원소로구성되고, 행렬 H는 k n 개의원소로구성된다., (3) 여기서 H T 는 H의전치행렬이고, W T 는 W의전치행렬이다. 본논문에서는비음수행렬분해를하둡을이용하여분산병렬로계산하기위하여 Liu이가제안한맵리듀스 (MapReduce) 방법을이용한다. Liu의방법 [11] 은식 (3) 을 3계의단계로분해하여맵과리듀스로구성한다. 즉다음표2와같이맵과리듀스로분해하는단계를요약할수있다. 표 2. Liu 의맵리듀스를이용한비음수행렬분해방법 Table. 2 Liu's NMF method using MapReduce 단계 를 Map 과 를 Map 과 를 Map과 Reduce로분해계산 를 Map 과 를 Map 과 를 Map과 Reduce로분해계산 3.3. 문서요약비음수행렬분해에의해추출된의미특징행렬의의미는다음과같다. 의미특징행렬 W는문장집합에포함된용어들에문장집합에잠재되어있는특징을값 (value) 로표현한것이며, 의미변수행렬 H는문장집합에서각각의문장이잠재되어있는특징을값으로표현된다. 또한의미특징행렬 W의각각의값들은의미변수행렬 H의각각열벡터에대한가중치의의미를갖는다. 이러한문장집합과의미특징행렬간의특성을이용하여문서를요약할수있다. 본장에서는사용자의질의와의미특징행렬 W와코사인유사도를식 (4) 를이용하여계산하고유사도가가장높은의미특징열벡터를찾는다. 찾은의미특징열벡터에일치하는의미변수행렬 H의행벡터에서가장높은값을갖는의미특징을선택한다. 선택된의미특징과일치하는문장을요약문으로추출한다. 2158

5 하둡과의미특징을이용한문서요약 (4) 표 4. 실험결과환경 Table. 4 Experiment results 여기서 W *j 는의미특징행렬 W의 j번째열벡터를나타내고, q는사용자의질의를나타낸다 [12]. 구분 100MB 500MB 1GB 10GB 20GB 단일환경 181 분 4 노드환경 21 분 67 분 123 분 732 분 1632 분 Ⅳ. 실험및평가 Ⅴ. 결론 본논문에서제안한방법의성능평가하기위한자료를야후 ( 에서수집하여용량별로만들었다. 평가방법은용량별수집자료를사용자의 500개질의를이용하여 500개의요약문을생성하는시간을단일환경과 4개의노드를분산병렬간에비교하여평가하였다. 다음표 3은실험에사용된컴퓨터환경을나타낸다. 표 3. 실험환경 Table. 3 Experiment environment 구분단일환경 4 노드환경 하드웨어 i3 CPU * 1 8 GB RAM 1 TB HDD i3 CPU * 4 8 GB RAM * 4 1 TB HDD * 4 운영제체 CentOS 6.3 CentOS 6.3 기타 - 하둡 본논문에서는분산병렬처리기반의문서요약방법을제안하였다. 제안방법은전처리된문서를하둡에용어문장빈도행렬을분산저장하고, 분산병렬로의미특징을추출하여사용자자의질의와가장잘부합되는문장으로요약한다. 본논문은다음과같은장점을갖는다. 문서요약에의미특징을이용하여사용자가원하는요약문장을추출함으로써요약문의질을높였다. 또한 4 대의 PC기반의하둡클러스터를이용하여대용량의자료를분산병렬처리함으로써단일환경에서처리할수없는대량의문서들을처리할수있게했다. 본논문의연구결과는검색엔진의스니핏추출, 정보추출, 인터넷대용량자료의요약분석, 소셜네트워크서비스대용량자료의요약분석, 소형인터넷단말기의정보요약제공등기타대용량자료를요약하는분야에활용할수있다. 앞으로추가연구로는현재실험환경상 4대의노드만을이용하였으나, 추가노드환경을구성하여다양설정에따른최적화연구가필요하다. 다음표4는실험결과를나타낸다. 여기서용어문장빈도행렬의비음수행렬분해시생성되는의미특징행렬의크기를결정하는의미특징 k의개수는 200으로고정한다. 의미특징의개수가늘어날수록계산량이기하급수로늘어난다. 표4의실험결과를보면단일환경시 100MB이상의자료는거의계산이안되는것을볼수있다. 이것은문서요약의비음수행렬분해에사용되는메모리의크기가 RAM의크기를초과하기때문에거의계산이불가능한것을알수있다. 그러나 4대의컴퓨터를하둡상에서분산병렬처리에의한문서요약의비음수행렬계산시저장자료의크기에따라서시간은증가하나문서가요약됨을알수있다. 감사의글이논문은 2013년도호남대학교학술연구비지원을받아연구되었음 REFERENCES [ 1 ] T. White, Hadoop: The Definitive Guide, 3th ed. O'Reilly Media,

6 [ 2 ] V. Nastase, "Topic-Driven Multi-Document Summarization with Encyclopedic Knowledge and Spreading Activation," in Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Honolulu, Hawaii, USA, pp , [ 3 ] K. Ramanathan, Y. Sankarasubramaniam, N. Mathur, A. Gupta, "Document Summarization using Wikipedia", in Proceedings of the First International Conference on HCI, Japan, [ 4 ] S. Ye, T. S. Chua, J. Lu, "Summarization Definition from Wikipedia", in Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, Singapore, pp , [ 5 ] S. Gong, Y. Qu, S. Tian, "Summarization using Wikipedia", in Proceedings of Text Analysis Conference 2010, Gaithersburg, Maryland, USA, [ 6 ] M., Sanderson, "Accurate user directed summarization from existing tools", in Proceeding of the international conference on information and knowledge management, Bethesda, Maryland, USA, pp.45-51, [ 7 ] A., Tombros, M., Sanderson, "Advantages of Query Biased summaries in Information Retrieval", in Proceeding of ACM Special Interest Group on Information Retrieval, pp.2-10, Melbourne, Australia, [ 8 ] R., Varadarajan, V., Hristidis, "A System for Query Specific Document Summarization", in Proceeding of the International Conference on Information and Knowledge Management, Arlington, Virginia, USA, pp , [ 9 ] S. Owen, R. Anil, T. Dunning, E. Friedman, Mahout in Action, Manning Publiications, [10] D. D. Lee, H. S. Seung, "Algorithms for non-negative matrix factorization," In Advances in Neural Information Processing Systems, vol. 13, pp , Aug [11] C. Liu, H. C. Yang, J. Fan, L. W. He, Y. M. Wang, "Distributed Nonnegative Matrix Factorization for Web-Scale Dyadic Data Analysis on MapReduce," in Proceeding of the International World Wide Web Conferene Comittee, USA, pp.1-10, [12] B. Y. Ricardo, Berthier, R. N., Moden Information Retrieval, ACM Press 김철원 (Chul-won Kim) 1997 년광운대학교 ( 공학박사 ) 1988 년 ~ 현재호남대학교컴퓨터공학과교수 관심분야 : XML 응용, 멀티미디어정보검색, 멀티미디어정보처리및응용 2160