ISSN 2383-6318(Print) / ISSN 2383-6326(Online) KIISE Transactions on Computing Practices, Vol 20, No 10, pp 549-554, 2014 10 http //dx doi org/10 5626/KTCP 2014 20 10 549 불균형데이터처리를위한과표본화기반앙상블학습기법 (Oversampling-Based Ensemble Learning Methods for Imbalanced Data) 김경민 장하영 장병탁 (Kyung Min Kim) (Ha Young Jang) (Byoung Tak Zhang) 요약필기체낱글자인식을위해서사용되는데이터는일반적으로다수의사용자들로부터수집된자연언어문장들을이용하기때문에해당언어의언어적특성에따라서낱글자의종류별개수차이가매우큰특징이있다. 일반적인기계학습문제에서학습데이터의불균형문제는성능을저하시키는중요한요인으로작용하지만, 필기체인식에서는데이터자체의높은분산과비슷한모양의낱글자등이성능저하의주요인이라생각하기때문에이를크게고려하지않고있다. 본논문에서는이러한데이터의불균형문제를고려하여필기체인식기의성능을향상시킬수있는과표본화기반의앙상블학습기법을제안한다. 제안한방법은데이터의불균형문제를고려하지않은방법보다전체적으로향상된성능을보일뿐만아니라데이터의개수가부족한낱글자들의분류성능에있어서도향상된결과를보여준다. 키워드 : 앙상블, 필기체인식, 불균형데이터, 표본화기법 Abstract Handwritten character recognition data is usually imbalanced because it is collected from the natural language sentences written by different writers. The imbalanced data can cause seriously negative effect on the performance of most of machine learning algorithms. But this problem is typically ignored in handwritten character recognition, because it is considered that most of difficulties in handwritten character recognition is caused by the high variance in data set and similar shapes between characters. We propose the oversampling based ensemble learning methods to solve imbalanced data problem in handwritten character recognition and to improve the recognition accuracy. Also we show that proposed method achieved improvements in recognition accuracy of minor classes as well as overall recognition accuracy empirically. Keywords: ensemble method, handwritten character recognition, imbalanced data, sampling method 본연구는삼성전자와한국연구재단의지원 (NRF 2010 0017734) 을일부받았음 논문수정 : 2014년 9월 3일 이논문은제40회추계학술발표회에서 불균형데이터처리를위한과표본화기반 (Revised 3 September 2014) 앙상블학습기법 의제목으로발표된논문을확장한것임 심사완료 : 2014년 9월 9일 학생회원 : 서울대학교컴퓨터공학과 (Accepted 9 September 2014) kmkim@bi snu ac kr CopyrightC2014 한국정보과학회 개인목적이나교육목적인경우, 이저작물 hyjang@bi snu ac kr 의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다이때, 종신회원 : 서울대학교컴퓨터공학과교수 (Seoul National Univ ) 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시 btzhang@bi snu ac kr (Corresponding author 임 ) 명시해야합니다이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다 논문접수 : 2014년 1월 23일 정보과학회컴퓨팅의실제논문지제20권제10호 (2014 10) (Received 23 January 2014)
550 정보과학회컴퓨팅의실제논문지제 20 권제 10 호 (2014.10) 1 서론일반적인기계학습기법들은학습데이터가범주별로비슷한비율로구성되어있다고가정하고학습을진행하게된다. 그러나많은실세계문제들이불균형데이터 (imbalanced data) 문제에속하게되고이러한경우소수범주에속한데이터들은다수범주에속한데이터보다잘못분류될가능성이높다 [1]. 이러한부작용 (side effect) 은기계학습알고리즘의설계특성상각범주의상대적인분포를고려하는대신전반적인성능을최적화시키려하기때문에발생하는것으로결정트리 (decision tree) 나다층퍼셉트론 (multilayer perceptron) 과같은분류기에서흔히나타난다 [1,2]. 필기체인식의경우도언어적특성에따라서범주별 ( 글자별 ) 데이터의비율이크게다른전형적인불균형데이터문제로볼수가있다. 예를들면자주쓰여지는알파벳인 a, o, i, e와같은소문자는학습데이터에서차지하는빈도가높은반면, Y, N, L과같은대문자는자주사용되지않아학습데이터에서차지하는빈도가낮다. 이와같이데이터의분포가불균형한상태에서학습을진행하게되면인식기는훈련데이터에서차지하는빈도가높은데이터에과적응 (overfitting) 하게되는문제가발생하게된다. 그러나필기체인식의경우이러한데이터불균형문제보다데이터자체의높은분산과유사한모양의글자들간의분류문제등이전체적인성능에더큰영향을미친다고알려져있기때문에데이터의불균형문제를크게고려하지않는다. 그러나높은빈도의데이터에대한과적응은학습초기에모델의성능을빨리향상시키는데에는효율적일수있지만, 일정정도이상의성능을보이는모델에서는결국최종적인성능향상의장애요인으로작용할수밖에없다. 이러한문제점을해결하기위해서본논문에서는과표본화에기반한앙상블학습기법을제안하고, 이를이용한필기체인식기의성능향상을실험적으로보여주었다. 본논문의구성은다음과같다. 2장에서는과표본화기반의앙상블학습기법을제안하고 3장에서는실험결과를제시한다. 이후 4장에서는결론을맺고향후연구방향을모색한다. 2 불균형데이터처리를위한앙상블기법 2 1 과표본화기법과표본화는샘플링기법의한방법으로소수범주의집합 S minor 에서무작위로데이터를추출하여집합 E 를만들고이를기존집합 S 에더하는과정으로이뤄진다. 이러한과정을거쳐 S minor 의데이터개수는 E 만큼증가하게되고집합 S 의범주분포는그에따라조절이 된다 [3]. 이방법은모든데이터를사용할수있다는장점이있는반면, 데이터의수를증가시켜계산에필요한시간이커지거나복제되는데이터에분류기가과적응할수있다는단점이있다. 데이터를단순복제하는대신지능적으로과표본화기법을사용한대표적연구로 Chawla가제안한 Syn thetic Minority Oversampling Technique(SMOTE) 가있다 [4]. SMOTE는기존에있는데이터를복제하는대신소수범주의데이터들을서로보간하여새로운인공적인데이터를합성하였다. 이기법은먼저 k 근접이웃 (k nearest neighbor) 알고리즘을사용해소수범주의데이터들과가장가까운데이터들을찾은뒤새로합성된데이터가그성향을반영하도록하였다. Hui Han은 SMOTE를수정한기법인 borderline SMOTE(BSM) 을제안했다 [5]. SMOTE가소수범주의모든데이터를대상으로기법을적용했던반면, BSM은범주의결정영역 (decision region) 에있는데이터들에만기법을적용시켰다. SMOTE 계열외에다른과표본화기법으로는 ADA SYN(Adaptive Synthetic Sampling) 이있다. ADASYN 은데이터들의밀도분포인 Γ 를계산하여범주마다다른양의데이터를합성했다 [6]. 다양한표본화기법들의성능을비교해본결과이러한지능적인기법들을사용한 [4,5] 보다오히려단순복제를사용한과표본화기법이더좋은분류성능을내는경우가많다는연구결과도있다 [7]. 또한 [7] 은분류기의성능을높이기위해서는표본화가매우중요한요소중하나임을확인하였다. 2 2 언더샘플링기법언더샘플링기법은다수범주의집합 S major 에서무작위로데이터를추출하여 E < S 를만족하는집합 E 를만든뒤이를기존집합 S 에서제거하는방식으로이뤄진다. 언더샘플링결과집합 S 의크기는집합E의크기, E 만큼줄어들게된다. 언더샘플링기법은데이터의크기가매우클때효과적이지만데이터의일부를버림으로써정보가손실된다는단점이있다. 과표본화기법과관련된연구와마찬가지로지능적으로언더샘플링기법을사용한연구들이있다. 대표적인예로 EasyEnsemble과 BalanceCascade가있는데두기법의목적은정보손실의단점을해소하기위한것이다 [8]. EasyEnsemble은다수범주 S major 에서부분집합 N 1, N 2,, N T 를독립적으로샘플링한뒤 N i 와소수범주 S minor 를학습한분류기 H i 를 T 개만들어결과를취합한다. EasyEnsemble가무감독학습방식을통해제거할다수범주집합의데이터를탐색하는반면, Balance Cascade에서는감독학습방식을취한다. BalanceCascade
불균형데이터처리를위한과표본화기반앙상블학습기법 551 는 S major 에서부분집합 N 1 을우선한번샘플링하여 N 1 과 S minor 를학습한분류기 H 1 을만들고 x S major 인 x 가 H 1 에의해정확하게분류되면 x 는충분히많다고판단하여 x 를 S major 에서제거한다. 이과정을 T 번순차반복하여마지막으로하나의분류기 H 가만들어지게된다. 다른방식의언더샘플링기법으로는 one sided selection (OSS) 가있다. OSS에서는 S major 의데이터를 4개의그룹 ( 노이즈데이터, 범주경계선근처데이터, 중복된데이터, 안전한데이터 ) 으로나누고 S major 에서노이즈데이터, 범주경계선근처데이터, 중복된데이터가제거된부분집합 E 를만들었다. 이를 S minor 와더해집합 N, N ={E S minor} 을학습하였다 [9]. 2 3 앙상블기법앙상블은각각다양한가설공간에서약분류기 H 1, H 2,, H n 을만든뒤이들의결과를조합해하나의강분류기를만드는기법이다. 앙상블기법에는대표적으로배깅 (Bagging, Bootstrap Aggregating) 과부스팅 (Boo sting) 이있다. 배깅은 Breiman이제안한기법으로결정트리나신경망과같은기본모델의분산을줄이는기법이다 [10]. 배깅의진행과정은다음과같다. 훈련데이터에서 k개의부분집합을무작위로복원추출한뒤각각의부분집합을결정트리나신경망과같은기본모델로학습하여 k개의약분류기를만든다. 그리고이들의결과를취합하여하나의강분류기의결과를낸다. Adaptive Boost(w, m) For each i = 1,...,N Initialize w = 1 / N For each t = 1,2,...,T Classify (x, y) with classifier f ( x) { 1,1} and w err = t n i= 1 i wi( y f( x)) i i t i n i= 1 t w 1 errt ct = log( ) err i Update w = w exp( c I( y f ( x ))) i i t i t i Construct a strong classifier sign( cf( x)) t T t t i= 1 (x, y) : labeled data w : weight vector N :# of labled data T :# of iteration 그림 1 Adaptive Boost Fig. 1 Adaptive Boost i 부스팅은 Schapire와 Freund에의한제안되었다 [11]. 배깅이병렬적인앙상블기법인반면에부스팅은순차적인앙상블기법이다. 부스팅에서는각데이터인스턴스마다가중치를갖는다. 인스턴스가높은가중치를가질수록학습된분류기에더많은영향을준다. 각단계 t 마다가중치 w t 와주어진데이터에의해분류기 f t 가만들어지고 f t 의오차 err t 에따라가중치벡터 w 는조정된다. 인스턴스가잘못분류될수록가중치는증가한다. 마지막 T 단계에서는 T 개의약분류기들의결과를조합해하나의강분류기가만들어지게되고결과취합방식은각약분류기의성능의함수로나타나게된다. 부스팅기법의한예로 AdaBoost(Adaptive Boost) 의알고리즘이그림 1에나타나있다. 본논문에서제안한과표본화기반앙상블기법은일반적인부스팅기법에서각각의데이터인스턴스들이갖는가중치를범주별데이터의개수에기반하여표본화를통해결정하는변형된부스팅기법이라고생각할수있으며, 앙상블모델의구축과정이일반적인부스팅기법과는다르게배깅에기반한병렬적인앙상블기법이라는특징을가지고있다. 2 4 과표본화기반앙상블학습기법불균형데이터를사용한학습과정에서는일반적으로관측수가많은범주의데이터가지배적인영향을미치기때문에학습된모델의성능저하가발생하게된다. 이를해결하기위해사용하는과표본화기법의경우에는데이터의불균형정도에따라서표본화된데이터크기의급격한증가로인해학습에어려움이발생한다는문제점과함께표본화된데이터의분포가원래데이터의분포와달라진다는문제점이있다. 이를해결하기위해서본논문에서는과표본화에기반한앙상블학습기법을제안하였다. 제안한방법은각각의범주에서동일한횟수만큼복원추출하여만들어진전체데이터의부분집합들을이용하여앙상블모델을구축함으로써기존의과표본화기법에서발생할수있는복제된데이터에대한과적응문제의해결이가능하다. 또한과표본화로인한전체데이터의크기증가로인한학습시간의증가문제도앙상블모델을이용함으로써해결이가능하게된다 [12]. 또한앙상블모델의구축을위하여전체데이터의부분집합을생성하는과정은언더샘플링 (undersampling) 의경우와유사하게다수범주의데이터일부만을사용하지만, 이를이용하여학습된약분류기들의조합으로앙상블모델을구축하기때문에전체모델의관점에서는모든데이터를사용한것과같은효과를얻을수있어언더샘플링과정에서흔히발생하는데이터의정보손실문제가발생하지않는다. 즉, 제안된방법론은언더샘플링된데이터의앙상블로
552 정보과학회컴퓨팅의실제논문지제 20 권제 10 호 (2014.10) Oversampling_Based_Ensemble_Learning(T,L,M) For each m = 1,2,...,M T = Oversampling(T,N) m h = L (T ) m b m Return h (x)= argmax I(h (x)= y) fin y Y m m Oversampling(T,N) S = φ For each class in T For i = 1,2,...,N r = random_integer(1,n) Add T[r] to S Return S T : original training set N :# of sampling M :# of base models to be learned L b : base model learning algorithm I(A) : indicator function that returns 1 if event A is true and 0 otherwise M b 그림 3 훈련데이터 a의예 Fig. 3 Examples of character a 그림 2 과표본화기반앙상블학습기법 Fig. 2 Oversampling Based Ensemble Learning 과표본화를구현함으로써언더샘플링에서발생하는데이터의손실을피할수있을뿐만아니라과표본화로인해서발생하는과적응이나학습시간의증가등과같은학습의어려움도피할수있는방법으로샘플링기법과앙상블기법의결합으로인하여기존의샘플링기법들이가지고있는단점을극복하고장점만을이용할수있도록하였다. 제안한방법론의수행과정이그림 2 에나타나있다. 3 실험및결과 3 1 데이터제안한방법론의성능을평가하기위해다수의사용자로부터수집된 238,450개의필기체데이터를훈련데이터로사용하여실험을진행하였다. 훈련데이터의범주는모두 50개로소문자알파벳 26개와대문자알파벳 16개, 숫자 8개이다. 대문자의개수가소문자의개수보다적은이유는인식과정에서대문자와소문자의모양이같은 C, K, O, P, S, U, V, W, X, Z를소문자로간주하여인식했기때문이고숫자 0과 1도소문자 o와 l 로간주하여인식했다. 일부훈련데이터의예가그림 3 에나와있다. 그림 3과같은원시자료 (raw data) 로부터획의필기순서에따른온라인특징 256차원을추출하였고글자를구성하는획 (x,y) 좌표벡터에따라오프라인특징 377차원을추출하여인식기의학습에사용하였다. 그림 4 데이터가개수가가장많은낱글자 10개와가장적은낱글자 10개 Fig. 4 10 most frequent characters and 10 most rare characters in training data set 범주당평균데이터개수는 4,769개이고데이터를가장많이포함하고있는범주상위 10개와가장포함하고있는범주하위 10개가그림 4에나타나있다. 테스트데이터로 9만여개의 UNIPEN Train R01 /V07 데이터가사용되었다 [13]. 3 2 실험결과본논문에서제안하는과표본화기반앙상블학습기법의성능을측정하기위해제안한방법으로학습한모델의성능과전체데이터를 6등분한뒤앙상블을적용한모델의성능, 전체데이터를한번에학습한기본모델의성능을비교해보았다. 학습을위한분류기는인공신경
불균형데이터처리를위한과표본화기반앙상블학습기법 553 표 1 각분류기의정확도 Table 1 Accuracy of each classifier (a) Overall accuracy of each classifier Base Model Bagging Oversampling Based Ensemble Method 77.564 80.42 81.79 (b) Accuracy on 10 most frequent characters Class Base Model Bagging Oversampling Based Ensemble Method L 61.63 85.05 76.36 H 88.20 79.83 88.00 I 78.27 47.62 82.74 R 76.02 91.59 78.81 S 95.42 98.85 97.07 n 76.99 70.19 61.57 t 84.42 93.62 85.91 o 89.27 92.19 88.39 a 87.97 90.70 80.18 e 94.04 95.13 92.76 (c) Accuracy on 10 most rare characters Class Base Model Bagging Oversampling Based Ensemble Method 2 47.84 56.34 57.01 3 85.33 90.83 97.15 9 30.89 43.52 51.29 7 42.83 50.58 64.32 6 67.76 83.85 81.93 5 50.82 51.75 66.68 8 46.06 60.29 74.91 4 50.03 68.51 78.22 Y 28.05 30.17 39.64 N 71.13 69.74 80.44 망을이용하였고, 앙상블모델은배깅을이용하였다. 표 1의 (a) 에서볼수있듯이과표본화기반앙상블학습기법을적용했을때 N = 1000, M=6인경우, 분류기의평균정확도는 81.79% 였고배깅을이용한앙상블모델이나기본모델에비해서성능이향상되었음을확인할수있었다. 특히표 1의 (c) 에서나타나듯이기본모델은전반적인성능을최적화하기위해데이터개수가적은범주에대한성능을희생시킨반면, 제안한기법에서는그러한성능희생없이전반적인성능이개선되었다. 또한하위 10개낱글자에대한배깅의성능과도비교해보았을때제시한기법이배깅보다데이터개수가적은범주에대한정보손실이더적다는점을알수있었다. 그림 5 약분류기개수에따른정확도 Fig. 5 Accuracy of the different number of weak learners 과표본화기반앙상블기법에서약분류기의개수가추가됨에따라서보여지는성능변화가그림 5에나타나있다. 실험결과로부터학습의초기에급격한성능향상을보이다가학습이진행됨에따라서성능이수렴하는경향을보이고, 또한전체데이터의절반만을이용하여학습이진행된성능이전체데이터를이용하여학습한신경망단일분류기의경우에크게뒤지지않음을확인할수있다. 이러한결과로부터제안한방법론이학습초기에문제공간을효율적으로탐색하여빠른성능향상을보임과동시에, 최종적으로는훈련데이터에있는정보들을빠짐없이잘활용하고있다고판단할수있다. 4 결론및향후연구 본논문에서는필기체데이터에서데이터의분포가불균형한문제를해결하기위해과표본화기반앙상블학습기법을제안하였다. 이기법을적용한결과데이터에서개수가부족한낱글자들의분류성능을올릴수있었고전체적인평균분류성능도향상될수있음을확인하였다. 제안한방법론은앙상블모델을이용한과표본화기법을구현함으로써표본화기법들간의단점을배제한체각각의장점만을구현할수있는기법으로써필기체인식문제만이아닌다양한불균형데이터에적용이가능할것으로예상된다. References [1] S. Ertekin, J. Huang, L. Bottou, L. Giles, "Learning on the border: active learning in imbalanced data classification," Proc. of ACM conference on Confer ence on Information and Knowledge Management, pp. 127 136, 2007. [2] A. Estabrooks, T. Jo, and N. Japkowicz, "A mul tiple resampling method for learning from imbalanced data sets," Computational Intelligence, Vol. 20, No. 1, pp. 18 36, 2004. [3] H. He, and E. A. Garcia, "Learning from Imba lanced Data," IEEE Transactions on knowledge
554 정보과학회컴퓨팅의실제논문지제 20 권제 10 호 (2014.10) and data engineering, Vol. 21, No. 9, pp. 1236 1284, 2009. [4] N. V. Chawla, L. O. Hall, K. W. Bowyer, and W. P. Kegelmeyer, "Smote: Synthetic minority oversam pling technique," Journal of Artificial Intelligence Research, Vol. 16, pp. 321 357, 2002. [5] H. Han, W. Wang, B. Mao, "Borderlinesmote: A new over sampling method in imbalanced data sets learning," Proc. of International Conference on Intelligent Computing, pp. 878 887, 2005. [6] H. He, Y. Bai, E.A. Garcia, S. Li, "ADASYN: Adaptive Synthetic Sampling Approach for Imba lanced Learning," Proc. of International Joint Con ference on Neural Networks, pp. 1322 1328, 2008. [7] J. V. Hulse, T. M. Khoshgoftaar, A. Napolitano, "Experimental perspectives on learning from imba lanced data," Proc. of International Conference on Machine Learning, pp. 935 942, 2007. [8] X. Y. Liu, J. Wu, Z. H. Zhou, "Exploratory Under Sampling for Class Imbalance Learning," Proc. of International Conference on Data Mining, pp. 965 969, 2006. [9] M. Kubat, S. Matwin, "Addressing the Curse of Imbalanced Training Sets: One Sided Selection," Proc. of International Conference on Machine Lear ning, pp. 179 186, 1997. [10] L. Breiman, "Bagging predictors," Machine Learning, Vol. 24, No. 2, pp. 123 140, 1996. [11] Y. Freund and R. E. Schapire, "A decision theoretic generalization of on line learning and an application to boosting," Journal of Computer and System Sci ences, Vol. 55, No. 1. pp. 119 139, 1997. [12] T. J. Kim, H. Y. Jang, J. W. Park, S. T. Hwang, B. T. Zhang, "Ensemble Methods with increasing data for online handwriting recognition," Proc. of the KIISE Korea Computer Congress 2013, pp. 1396 1398, 2013. [13] I. Guyon, L. Schomaker, R. Plamondon, M. Liberman, S. Janet, "UNIPEN project of on line data exchange and recognizer benchmarks," Proc. of International Conferences on Pattern Recognition, pp. 29 33, 1994. 김경민 2013 년홍익대학교컴퓨터공학과학사 2013 년 ~ 현재서울대학교컴퓨터공학부석박사통합과정. 관심분야는기계학습, Com putational Intelligence, 멀터미디어마이닝, 인지과학 장하영 2002 년연세대학교컴퓨터과학과공학사 2004 년서울대학교컴퓨터공학과공학석사. 2004 년현재서울대학교컴퓨터공학부박사과정. 관심분야는기계학습, 진화연산, 확률그래프모델 장병탁 1986 년서울대컴퓨터공학과학사. 1988 년서울대컴퓨터공학과석사. 1992 년독일 Bonn 대학교컴퓨터과학박사. 1992 년 ~1995 년독일국립정보기술연구소 (GMD, 현 Fraunhofer Institutes) 연구원. 1997 년 ~ 현재서울대컴퓨터공학부교수및인지과학, 뇌과학, 생물정보학협동과정겸임교수. 2003 년 ~ 2004 년 MIT 인공지능연구소 (CSAIL) 및뇌인지과학과 (BCS) 객원교수. 2007 년 ~2008 년삼성종합기술연구원 (SAIT) 객원교수. 현재서울대인지과학연구소소장, Applied Intelligence, BioSystems, Journal of Cognitive Science 등국제저널편집위원. 관심분야는바이오지능, 인지기계학습, 분자진화컴퓨팅기반뇌인지정보처리모델링