청킹기반특징추출을통한문서분류시스템의성능향상 Improving text classification systems through chunking-based feature extraction 이아람 (Aram Lee) *, 김한준 (Han-joon Kim) ** chigaya06@gmail.com, khj@uos.ac.kr 초록 기계학습을이용하는자동문서분류시스템은분류모델의구성을위해서개별적인단어 (word) 를특징 (feature) 으로사용한다. 그래서중의성또는모호성을가지는단어는분류모델의성능을저하시키는요인으로작용한다. 문서분류의성능을높이는방법중의하나는분류모델의특징으로사용되는단어가가질수있는중의성을제거하는것이다. 본논문에서는청킹 (chunking) 기술을이용하여분류모델을개선하는방안을제시한다. 청킹이란자연어처리기법중의하나로서정보를의미있는단위로묶어주는기술이다. 청킹을통하여단어가가지는중의성을최소화하여자동분류에도움이되는특징을만들어낼수있다. 청킹을통해생성된새로운특징집합에서문헌빈도수를기준으로최적의특징을선정하고, 선정된최적의특징집합을이용하여다음의세가지방법으로분류모델을개선하였다. (1) 학습할문서집합에서의선정된특징들의출현빈도수를높여주거나, (2) 테스트집합에서선정된특징을가진문서를찾아특징의출현빈도수를높여주는방법, (3) 테스트집합의일부로사전분류를실행하여분류의오류정보를얻어점진적으로학습모델을개선하는방법을사용하였다.. 1. 서론 초고속인터넷의빠른보급과스마트폰의 대중화로인터넷은문서정보가넘쳐나고 있다. 블로그 (blog), 뉴스등과같은온라인문서들이꾸준한증가추세를보임에따라자동문서분류시스템은스팸메일분류, 사용자의선호도를고려한뉴스기사의분류등다양한분야에서응용되고있다. 본연구는 2010 년정보 ( 교육과학기술부 ) 의재원으로한국연구재단의기초연구사업지원을받아수행되었음. ( 과제번호 : 2010-0025212) * 서울시립대학교전자전기컴퓨터공학과석사과정 ** 서울시립대학교전자전기컴퓨터공학부부교수
최근의자동문서분류기법은주로기계학습 (machine learning) 기술을사용한다. 기계학습방식은분류를위해학습문서집합으로부터각카테고리에출현하는특징집합을주요인자로하여문서를분류할수있는모델을만든다. 대표적인관련알고리즘은나이브베이즈 (Naïve Bayes)[1], 지지벡터머신 (Support Vector Machine)[2] 등을포함한다. 특히나이브베이즈알고리즘은분류모델의단순성에비하여성능이우수한편으로평가되어자동문서분류시스템의개발을위해자주활용되고있다. 일반적인기계학습에기반을둔문서분류알고리즘에서분류성능에영향을미치는문제들중우리가주목할것은특징선택 (feature selection) 의문제이다. 특징선택은 차원의저주 (curse of dimensionality) 라고불리는문제를해결하기위한방법으로제시되었다. 차원의저주란문서의수가증가할수록특징이라고불리는단어 (word) 또는용어 (term) 의수가지수적으로증가하는문제를말하며, 특징선택이란이러한특징들중에서카테고리를가장잘표현할수있는일부특징을추출하는과정을말한다. 일반적으로문서들은단어들의다중집합 (multi-set 또는 bag) 으로부터추출된특징들로표현되며, 모든문서에대한특징들로구성된특징공간 (feature space) 은결국수많은단어들이모인어휘 (vocabulary) 를구성하게된다. 따라서문서분류의성능을향상시키기위해서는특징선택을통해서특징공간을줄이고왜곡된특징들을삭제하는과정이필수적이다.[3] 자동문서분류에있어서본연구가주목하는이슈는문서내의특정단어가여러의미를갖는경우에올바른분류를하지못하는 중의성문제이다. 중의성을갖는단어는문맥의앞뒤내용을파악해야만그정확한의미를가려낼수있다. 만약한단어가어떤단어와일정수준이상빈번하게공기 (cooccurrence) 하면, 그단어들은서로연관이있는단어라할수있다.[4] 이러한공기관계를활용하기위해본논문에서는자연어처리기법의하나인청킹 (chunking) 기술을이용하여문서내의단어가가지는중의성을최소화하는특징확장방법을제안하고자한다. 청킹은주변의단어와공기관계를고려할수있다. 본논문의구성은다음과같다. 우선 2장에서자연어처리기법의하나인청킹에대하여살펴보고, 3장에서는청킹을이용한분류모델을개선하는방안을제안한다. 4 장에서는실험결과를제시하고 5장에서는결론과이후연구에대한향방을제시한다. 2. 배경연구 2.1 청크 (Chunk) 청크 (Chunk) 란, 언어학적으로본다면말모듬이라는뜻으로언어학습자가한번에하나의단위처럼배울수있는어구를뜻한다. 심리학에서는기억대상이되는자극이나정보를서로의미있게연결시키거나묶는것을지칭한다. 또한청킹 (chunking) 은정보를의미있게묶어청크를만드는과정을뜻한다. 본연구에서는의미있는단어를결합하여새로운특징을만드는과정을청킹이라정의한다. 주어진학습문서집합에중의성을나타내는단어들에대하여청킹과정을수행함으로써분류모델의구성에도움이되는특징을추출하고자한다.
2.2 청킹 (Chunking) 예를들어, data mining 이라는용어를통해청킹을설명하겠다. data 라는단어는정보처리나컴퓨터분야외의넓은범위에서사용되고있는단어이다. 그리고 mining 이란단어는사전적의미로 채광, 발굴 등의의미를갖는다. data mining ( 일반단어 ) datamining ( 청크특징 ) 하지만 data와 mining이함께쓰인 datamining 이라는용어는컴퓨터과학의한분야를가리키는용어가된다. 본논문에서는이와같이단어가가지는의미의범위를좁혀중의성과모호성을최소화하는과정을청킹이라정의하고, 청킹을통하여얻어진 datamining 과같은단어를청크특징이라고하겠다. 3. 청킹기반특징추출과분류모델의개선중의적인의미로인하여광범위하게사용되는일반단어에비하여청크특징은상대적으로그사용범위가좁다. 그만큼의미를강화한다는의미로, 분류에있어서좋은기준점이될수있을것이다. 이장점을이용하여분류정확도를향상시키고자청크특징의출현빈도수에변환을주어분류모델을개선하였다. 3.1 중의성해소를위한청크특징추출영어문장의경우에그문장의의미 ( 주제 ) 를가장잘표현하는품사는명사이다. 명사는다른품사들과달리해당단어가연속적으로연결되어도문법상문제가없으며, 명사만의나열만으로도의미를나타낼수있다. 이러한이유로명사를서로연결시켜의미를가질수있는정보가될수있다. 본연구에서는청킹과정을통해연속적명사군을찾아냄으로써중의성을가지는명사특징을제거하고자한다. 본연구에서는명사군의청킹과정은세단계를거친다. 첫번째는문장을구 (phrase) 단위로나눈다. 이중명사를포함하고있는명사구만추려낸다. 두번째단계에서는명사구내에서품사를구분한다. 마지막으로단어사이에명사외의다른품사가존재하지않으며 2회이상명사가연속되는단어를결합하여청크특징을만든다. 사용할수있는청크특징은두종류가있다. 하나의카테고리에서만나타나는청크특징과여러카테고리에서나타나는청크특징이다. 전자의경우하나의카테고리에서만나타나기때문에카테고리를대표하는특징이될수있다. 후자의경우 1~2개정도로적은수의카테고리에서확연히높은문헌빈도수를보이는청크특징이카테고리의특징을보일수있을것이다. 3.2 주요청크특징의추출사실모든청크특징이문서분류에서유용하게사용되는것은아니다. 희귀한단어, 즉출현빈도수가매우적은단어의경우좋은분류모델의구성에방해가된다. 이러한방해요소를배제하기위하여적정수준이상의출현빈도수를보이는특징을골라내야한다.. 단어의출현빈도수를측정하는방법은두가지가있다. 하나는단어가출현하는문서의수를의미하는문헌빈도수 (document frequency) 이고, 다른하나는
문서의수와관계없이한문서내의단어의출현횟수를의미하는단어빈도수 (term frequency) 이다. 카테고리의구분없이문헌빈도수가높은단어는모든카테고리에서자주출현함을의미함으로해당단어가특징으로작용하지못한다. 그러나하나의카테고리안에서만특정단어의문헌빈도수가높다면, 해당단어는그카테고리에서는폭넓게쓰이고있지만다른카테고리에서는사용되지않는다것을의미한다. 그러므로문헌빈도수를계산할때카테고리별로나누어서계산한다. 학습할문서집합의적어도하나이상의카테고리에서일정비율이상의문헌빈도수를보임으로써문서분류시영향력있는중요한청크특징을 SCF(Significant Chunk Feature) 라명명하겠다. 본연구에서는 SCF를이용하여학습모델을개선할것이다. 3.3 출현빈도수의확대청크특징은일반적으로쓰이는단어들중에서도몇가지조건을만족하는단어들을모아만들어지기때문에청크특징이아닌일반단어에비하여그출현빈도수가적다. 이부분을보완하기위해출현빈도수를의도적으로늘려주는방식을취할수있다. 출현빈도수를높이기위해학습할문서집합에해당되는 SCF을추가로넣어학습한다. 실험에서사용되는 SCF는아래와같이두가지로구분하여정의한다. single_class_feature : 하나의카테고리에만출현하는청크특징 multi_class_feature : 여러카테고리에출현하는청크특징 Only_feature는하나의카테고리에서만등장하는 SCF를이용한다. Multi_feature는여러카테고리에서등장하지만 1-2개의카테고리에서확연히높은문헌빈도수를가지는 SCF를이용한다. 위에서설명한두가지방법은편의상아래와같이구분된실험을적용한다. SCF_one : 해당 SCF를 1회씩만추가 SCF_ratio : 문헌빈도수비율만큼추가구체적으로 SCF_one 방법은해당 SCF 를 1회씩만추가하는것으로추가되는특징의수가가장적은보수적인접근법이다. SCF_ratio 방법은문헌빈도수비율에따라추가하는것이다. 해당 SCF의문헌빈도수를주어진문서집합에서의문헌빈도수최소값으로나누어그횟수만큼추가한다. 3.4 주요청크특징기준의문서검색을통한분류모델개선청크특징은그수가일반적으로사용되는단어들보다출현빈도수가적다. 이것은분류대상이되는문서들에서도마찬가지이다. 이문제를극복하기위해테스트집합의청크특징의출현빈도수를높여주고자한다. 테스트집합에서 SCF를가진문서를검색한다. 검색된문서에해당문서가가지고있는 SCF를 1회추가하여준다. 학습할문서집합이아닌분류할문서에직접추가하여준다. 3.5 점진적학습기법을이용한분류모델개선이번절에서는분류모델의개선을위해추출된 SCF을활용한점진적학습 (incremental learning) 기법을제시한다.
알고리즘 : 점진적학습기법을이용한분류모델개선입력 : 분류모델 m P i, i번째선분류집합 ep i, i번째선분류집합오분류정보 T, 테스트집합출력 : 개선된모델 m BEGIN 1 while( P i < T *0.5) { 2 while( accuracy(m (P i ) accuracy(m(p i-1 )> 0) { 3 // m(p i ) : m으로 P i 를분류함을의미 4 ep i = m(p i ) 5 // ep i : P i 의오분류정보 6 m = learning(m+ep i ) 7 // m+ep i 을학습하여 m 을생성 8 } 9 P i+1 = P i S 10 // S = T의부분집합 11 // S < T *0.1 12 } 13 개선된분류모델 m 획득 END < 그림 1> 점진적학습알고리즘우선은테스트집합의일부로선분류집합을구성한다. 점진적으로모델을개선해나갈것이기때문에최초의선분류집합의크기는작을수록좋다. < 그림 1> 의 4 처럼, 선분류집합 P를분류모델 m으로분류하여오분류된문서에대한정보를얻는다. 그다음으로 < 그림1> 6을진행한다. 이과정은기존의학습모델에오분류된문서가가진 SCF를추가하고, 다시학습하여개선된분류모델 m 을만드는과정을보여준다. < 그림 1> 의 2에서처럼선분류집합 P를분류했을때그결과에대한정확도의변화가 0 또는 0에가깝다면, < 그림 1> 의 9를 수행하여선분류집합 P의크기를늘리고, 앞의과정인 < 그림 1> 2-8을반복한다. 증가된선분류집합 P의크기가테스트집합 T의 50% 보다커지면모든반복과정을종료한다. 가장마지막으로생성된분류모델 m 은점진적학습을통해개선된분류모델이다. 4. 실험 4.1 실험환경 제안한기법의성능을평가하기위하여 20Newsgroup 을이용한실험을실시하였다. 20Newsgroup는문서분류의성능을평가하기위해일반적으로많이사용되는문서집합이다. 20개의카테고리를갖는 19,997개의기사로구성되어있으며, 카테고리간에문서들이비교적균형있게분포되어있다. 단어의품사구분을위하여 Illinois pos Tagger와 Illinois Chunker[5] 를사용하였다. 전체문서의 70% 를학습을위해사용하였고, 나머지 30% 는분류성능을평가하는데사용하였다. 분류는나이브베이지안 (Naïve Bayseian) 문서분류기의하나인 Mallet 시스템 [6] 을이용하였다. 분류의성능은각문서가속할카테고리를얼마나정확하게분류하는가를기준으로평가하였다. 4.2 실험결과 < 표 1>, < 표 2>, < 표 3> 에서기준기법이라함은실험에사용되는문서에청킹을적용하여청크특징을가지고는있는상태로, 제안한실험들은적용되지않은것을뜻한다. 기준기법을기준정확도로설정하고제안한실험들의성능비교에사용하였
다. 표1은 SCF 중 single_class_feature를이용하여출현빈도수를확대해준실험결과이다. 보는바와같이 SCF_one의경우약간의성능향상을보였으나, SCF_ratio의결과처럼특징을추가하는횟수가늘어날수록성능은떨어졌다. 표2는테스트집합에서 SCF를가진문서를검색하여 SCF를추가하여주는방법에대한실험결과이다. SCF를 1회만추가하였을경우약 1% 의분류정확도상승을보였으나 SCF의추가횟수가늘어날수록성능이떨어졌다. 표3 은선분류를통하여점진적학습을진행하여개선된분류모델을얻어내는실험의결과이다. SCF와일반단어를오분류정보로이용하였을경우가 SCF만을이용한경우보다미미하지만좋은성능을보였다. 대부분의실험에서괄목할만한분류성능의향상은보이지못하였다. 하지만 SCF를기준으로테스트문서집합에서문서를검색을통한분류모델의개선방법은자동분류시스템의성능향상가능성을보여주었다. < 표 1> SCF의출현빈도수확대를통한분류모델개선 ( 단, single_class_feature) 실험분류정확도기준기법 78.08 SCF_one 78.13 SCF_ratio 75.51 < 표 2> SCF 기준의문서검색을통한분류모델개선실험분류정확도기준기법 78.08 SCF 1회추가 79.24 < 표 3> 선분류를통한점진적모델개선 실험 분류정확도 기준기법 78.08 SCF만추가 78.45 SCF와일반단어추가 78.47 일반단어만추가 77.98 5. 결론 기존의나이브베이지안분류방법은통계적수치만을고려하기때문에단어가가지는중의성으로인하여분류성능에영향을받았다. 본연구에서는청킹을통하여단어가가지는중의성을최소화하는청크특징을만들고이를이용하여분류모델을개선하고자하였다. 청크특징중분류시스템에영향을줄수있을것이라예상되는특징들을추출하고분류모델개선에이용하였다. 본실험에서의성능향상은미미하였으나 20Newsgroup 문서집합에대한실험을통하여, 제안기법의가능성을볼수있었다. 향후, 특징추출과활용방법을확장하는연구를진행하여자동문서분류시스템의성능을향상시킬수있도록연구를진행할것이다. 참고문헌 [1] T.M. Mitchell, Bayesian Learning, Machine Learning, McGraw-Hill, pp.154-200, 1997. [2] T. Joachims, Text Categorization with Support Vector Machines: Learning with Many Relevant Features, Proceedings of the 10 th European Conference on Machine
Learning (ECML 98), pp137-142, 1998. [3] 김한준, 장재영, 점진적특징가중치기법을이용한나이브베이즈문서분류기의성능개선, 정보처리학회논문지 B 제15-B권제5호, 2008. [4] Wilks, Y., Fass, D. Guo, C., McDonald, J. Plate T., and Slator, B. Providing machine tractable dictionary tools., Machine Translation, 5, pp99-154, 1990. [5] Illinois chunker, University of Illinois at urbana champaign Congnitve Computation Group, http://cogcomp.cs.illinois.edu/ [6] Mallet (MAchine Learning for LanguagE Toolkit), http://mallet.cs.umass.edu/