k- 최근접템플릿기반다중분류기결합방법 45 k- 최근접템플릿기반다중분류기결합방법 (ultple Classfer Fuso etho base o k-nearest Teplates 민준기 조성배 (Ju-K (Sug-Bae Cho 요약본논문에서는다중분류기를효과적으로결합하기위하여 k- 최근접템플릿방법을제안한다. 이는하나의클래스를여러개의템플릿으로모델링하기위하여분류기의출력값을기반으로각클래별학습샘플들을여러개의하위클래스로분해하고, 각하위클래스별분류기출력값의평균을계산하여지역화된템플릿을생성한다. 그뒤평가샘플과각템플릿간의거리를계산하고, k 개의최근접템플릿들중가장많은비율을차지하는클래스로평가샘플을분류한다. 본논문에서는클래스분해를위해 C-eas 클러스터링알고리즘을이용하였으며, k 값은주어진데이타셋의클래스내밀집도와클래스간분리도에따라자동으로결정하였다. 제안하는방법은각클래스별로여러개의모델을사용하며, 이들중가장유사한하나의모델과매칭하는대신 k 개의모델을참조하기때문에안정적이고높은분류성능을획득할수있다. 본논문에서는 UCI 와 EENA 데이타베이스를이용한실험을통해제안하는방법이기존의결합방법들에비해우수한분류성능을보임을확인하였다. 키워드 : 분류기결합, 지역화된템플릿, C-eas 클러스터링 Abstrat I ths paper, the k-earest teplates etho s propose to obe ultple lassfers effetvely. Frst, the etho eoposes trag saples of eah lass to several sublasses base o the 이논문은지식경제부를통해 IITA 에서지원받았음 (IITA-2008-(C090-080-00 이논문은제34회추계학술대회에서 k-최근접템플릿기반다중분류기결합방법 의제목으로발표된논문을확장한것임 학생회원 : 연세대학교컴퓨터과학과 loolke@slab.yose.a.kr 종신회원 : 연세대학교컴퓨터과학과교수 sbho@s.yose.a.kr 논문접수 : 2008년 월 0일심사완료 : 2008년 3월 24일 Copyrght@2008 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제4권제4호 (2008.6 outputs of lassfers to represet a lass as ultple oels, a estates a loalze teplate by averagg the outputs for eah sublass. The staes betwee a test saple a teplates are the alulate. astl the test saple s assge to the lass that s ost frequetly represete aog the k ost slar teplates. I ths paper, C-eas lusterg algorth s use as the eoposto etho, a k s autoatally hose aorg to the tra-lass opatess a ter-lass separato of a gve ata set. Se the propose etho uses ultple oels per lass a refers to k oels rather tha athes wth the ost slar oe, t oul obta stable a hgh auray. I ths paper, experets o UCI a EENA atabase showe that the propose etho perfore better tha ovetoal fuso ethos. Key wors : Classfer Fuso, oalze Teplate, C-eas Clusterg. 서론 다중분류기의결합은높고안정적인분류성능을얻기위한방법으로패턴인식분야에서많이연구되어왔다 []. 분류기결합방법은크게추가학습이필요한것과추가학습이필요없는것으로나눌수있다. 추가학습이필요없는방법중가장널리사용되는것으로는투표기반 (AJ, 최대값선택 (AX, 최소값선택 (IN, 평균선택 (AVG 등이있으며 [2], 추가학습이필요한방법중대표적인것으로는결정템플릿 (, Deso Teplates 과 BKS(Behavor Kowlege Spae 가있다 [3]. 이외에도여러개의분류기를생성한뒤예측된분류결과에따라분류기를선택하는방법도연구되고있다 [4]. 앞에서소개한결합방법들중결정템플릿은클래스별학습샘플에대한분류기의출력벡터들의중심을해당클래스의분류모형으로사용하는방법으로, 높은분류성능을보이며분류기선택방법과혼합되어사용되기도하였다 [4]. 그러나이방법은클래스를하나의템플릿으로모델링하기때문에데이타의특징을정교하게표현하는데어려움이있다. 이를해결하기위해클러스터링알고리즘을이용하여여러개의국부화된템플릿을생성하는다중결정템플릿 (us 방법이제안되었지만, 이는하나의템플릿만을참조함으로써클러스터링결과에민감할수있다 [5]. 본논문에서는다중결정템플릿의분류성능과안정성을높인 k-최근접템플릿방법을제안한다. 이방법은데이타셋의클래스내밀집도와클래스간분리도에따라다중결정템플릿에서참조할템플릿의수인 k값을자동으로결정하며, 이를통해오류클러스터의영향을
452 정보과학회논문지 : 컴퓨팅의실제및레터제 4 권제 4 호 (2008.6 줄인다. 본논문에서는다양한데이타셋을이용한실험을통해제안하는방법의성능을검증하였다. 2. 관련연구 2. C-eas 알고리즘 C-eas( 또는 k-eas 알고리즘은샘플과클러스터중심간의거리 I를최소화하는 C개의클러스터를탐색하는반복적알고리즘이다 [6]. 데이타셋의샘플수를 이라하고, 번째클러스터의중심을 z 라하였을때 I 는일반적으로다음과같이계산한다. 3. k-최근접템플릿기반분류기결합결정템플릿방법은클래스를하나의템플릿으로축약하여모델링하기때문에다양한특징정보가손실된다. 본장에서는클래스를여러개의하위클래스로분해한뒤 k개의템플릿을참조하여분류성능과안정성을높인 k-최근접템플릿기반분류기결합방법에대해설명한다. 그림 은제안하는방법의전체흐름도를나타낸다. I = C = = 2 u, x z ( 식 ( 에서 u, 는분할행렬 (Partto atrx 의 (, 번째원소를나타내는것으로, 샘플 x 가클러스터가 에속한경우 이고그외에는 0의값을갖는다. C- eas알고리즘은데이타공간상에서임의로 C개의점을선택한뒤이를중심으로클러스터를분할한다. 각클러스터의중심은소속샘플들의중심점으로갱신되며, 중심의이동이거의없어질때까지이과정을반복한다. 이방법은지역해에빠질수있다는단점이있지만알고리즘이간단하면서좋은성능을보이고, 또한클러스터수의선택이용이해널리사용된다. 2.2 결정템플릿결정템플릿은 Kuheva[3] 가제안한분류기결합방법으로, 학습데이타에대한분류기의출력값을행렬형식의결정프로파일로구성한다. 클래스문제에대해 개의분류기를사용할때, 번째학습샘플 x (=,, 의결정프로파일 DP(x 는다음과같다., ( x DP( x =,( x z ( x,, ( x ( x (2 식 (2 의 z(x 는 y번째분류기의클래스 z에대한출력값을의미한다. 결정프로파일이생성되면, 식 (3 과식 (4 를이용하여클래스 에대한템플릿 을계산한다. (, = (, = ( z (, (3 (, ( = u ( x u (4 = 분류시에는평가샘플의결정프로파일과각클래스의템플릿을유클리드거리등과같은유사도계산방법을사용하여비교한뒤, 가장유사한템플릿의레이블로샘플의클래스를결정한다. 그림 다중결정템플릿의생성및 k-최근접템플릿기반분류 3. 다중결정템플릿의생성먼저개별분류기를학습하고, 동일한학습데이타로부터얻은분류기들의출력값을 2.2절의식 (2 의결정프로파일로구성한다. 각클래스의결정프로파일을 C-eas 알고리즘을이용하여클러스터링하고, 다음식을이용하여 번째클러스터의지역화된템플릿 를계산한다 [5]. = (, (, ( = u, z ( x = = (, (,, (5 ( u (6
k- 최근접템플릿기반다중분류기결합방법 453 식 (6 에서 u, 는샘플 x 가클래스 의 번째클러스터에소속되어있는경우 이고그외에는 0의값을갖는다. 본논문에서는클러스터의수를데이타셋에상관없이 C=20으로고정시켰다. 3.2 k-최근접템플릿기반분류평가샘플의결정프로파일과템플릿들간의유사도를계산한뒤, 가장유사한 k개의템플릿들중가장많은비율을차지하는레이블로샘플을분류한다. 본논문에서는유클리드거리식을이용하여유사도를계산하였다. 이방법은 k-최근접이웃 (k-nearest Neghbor 분류방법과마찬가지로 k값에영향을많이받는다. 최적의 k 값은데이타셋에의존적이기때문에제안하는방법에서는클래스내밀집도 (Itra-lass opatess 와클래스간분리도 (Iter-lass separato 를분석하여 k 값을결정한다. 데이타셋의밀도분석은주로클러스터링알고리즘의정당성지표 (Valy ex 에사용되는방법으로, 본논문에서는식 (7 과식 (8 을이용하여클래스내밀집도 IC와클래스간분리도 IS를계산하였다 [7]. IC = E E IS =, E = u x z (7 = = z z j,ax (8 j=,..., k값은식 (9 와같이간단한규칙에의해결정되며, 임계값인 t IC 와 t IS 는실험을통해각각.5와 2로결정하였다. f k = C / 2 f 4. 실험및결과 4. 실험환경 IC t IC > t IC IC a IS t a IS > t 본논문에서는패턴인식분야에서널리사용되는 UCI 와 EENA 데이타베이스중 0개의데이타셋을대상으로실험을수행하였다 ( 표. 본논문에서는결합을위한개별분류기로신경망을사용하였으며, 학습율과모멘텀은각각 0.5와 0.9로설정하였다. 신경망내부노드들간의초기연결강도는 -0.5~0.5 사이의임의값으로초기화하였으며, 각신경망은 Baggg을이용하여학습하였다. 신경망의은닉노드 (He oe 수와세대수는 [] 의연구와동일한기준으로다음과같이결정하였다. 우선은닉노드는최소 5개가되도록하였으며, 하나의클래스당혹은 0개의특징당최소하나의은닉노드를갖도록하였다. 세대수는데이타셋의샘플수가 250개이하인경우 60~ 80세대, 샘플수가 250~500개인경우 40세대, 샘플수가 500개이상인경우 20~40세대로설정하였다 ( 표 2. IS IS (9 데이타셋 표 실험에사용된데이타셋 샘플수 특징수 클래스수 출처 Breast-aer (Br 683 9 2 UCI Ioosphere (Io 35 34 2 UCI Irs (Ir 50 4 3 UCI Satellte (Sa 6435 36 6 UCI Segetato (Se 230 9 7 UCI Soar (So 208 60 2 UCI Phoee (Ph 5404 5 2 EENA Texture (Te 5500 40 EENA Clous (Cl 5000 2 2 EENA Coetr (Co 2500 2 2 EENA 표 2 신경망파라메터 데이타셋 은닉노드수 세대수 Breast-aer (Br 5 20 Ioosphere (Io 0 40 Irs (Ir 5 80 Satellte (Sa 5 30 Segetato (Se 5 20 Soar (So 0 60 Phoee (Ph 5 30 Texture (Te 20 40 Clous (Cl 5 20 Coetr (Co 5 20 본논문에서사용할신경망의수는기존의분류기결합방법인 AJ, IN, AX, AVG를이용한실험을통해결정하였다. 그림 2와같이사용하는신경망의수가 0개이상이되면결합을통해얻을수있는성능의향상정도가줄어드는것을확인하였으며, 따라서본논문의이후실험에서는 [] 의연구와마찬가지로신경망의수를 25개로고정하였다. 그림 2 결합하는신경망수에따른분류성능 ( 모든데이타셋에대한실험결과의평균
454 정보과학회논문지 : 컴퓨팅의실제및레터제 4 권제 4 호 (2008.6 4.2 분류성능평가결합방법별성능을비교하기위하여각데이타에대해 0-fol ross valato실험을수행하였다. 표 3과표 4 는각각실험결과의오분류율과표준편차를나타낸다. 결합방법중오라클 (ORA 은분류기들중하나라도맞게분류하면전체가맞았다고보는방법으로, 데이타셋의최대가능분류율을의미한다. 제안하는방법인 k- 최근접템플릿방법의경우 3.2절의식 (9 에의해 Ioosphere, Soar, Phoee, Clous, Coetr의 5가지데이타셋의경우 k=, 나머지의경우는 k=c/2=0으로 k값이선택되었다. 표 3에서굵게표시된숫자는각데이타셋의최소오분류율을나타내는것으로 ( 오라클제외, 실험결과제안하는방법이가장많은수인 6개의데이타셋에서최고분류율을보였으며, 그외의데이타셋에서도높은성능을나타냈다. us( 다중결정템플릿 은두번째로좋은성능을보였으며, 기존결합방법들중에서는평균선택 (AVG 방법이좋은성능을나타냈다. 그림 3은전체데이타셋에대한평균오분류율과표준편차를보여준다. 그림과같이제안하는방법이다른방법에비해가장높은성능을보였으며, ( 결정템플 표 3 모든데이타셋에대한결합방법별오분류율 AJ IN AX AVG u s 제안하는방법 ORA Br 3.09 2.94 2.94 2.94 2.79 4.56 2.79.32 Io 0.00 9.5 8.86 0.00 0.00 7.72 7.72.72 Ir 3.33 3.33 4.00 2.67 2.67 4.67 3.33.33 Sa 0.56.20.25 0.42 0.64.38 0.37 2.44 Se 5.89 6.36 5.58 5.54 5.54 3.77 5.4.7 So 4.50 9.00 7.50 4.00 4.50 6.00 6.00 2.00 Ph 9.82 9.74 9.74 9.67 9.6 9.35 9.35 6.89 Te 0.3 0.44 0.42 0.33 0.33 0.36 0.33 0.04 Cl 20.54 20.70 20.70 20.64 20.42 8.0 8.0 5.30 Co 2.28 2.44 2.44 2.6 2.04.24.24 0.00 표 4 모든데이타셋에대한결합방법별표준편차 AJ IN AX AVG u s 제안하는방법 ORA Br.62.55.70.83.76 2.0.83.76 Io 5.43 5.8 5.30 5.43 5.43 4.48 4.48 2.76 Ir 4.7 4.7 4.66 4.66 4.66 5.49 4.7 2.8 Sa.24 0.9 0.99 0.98.4.34 0.99 0.5 Se.85 2.6.9.7.67.42.48 0.54 So 6.43 8.43 9.20 6.58 6.43 7.75 7.75 3.50 Ph.53.62.62.35.50.76.76.20 Te 0.5 0.23 0.29 0.5 0.5 0.2 0.5 0.08 Cl 2.47 2.5 2.50 2.45 2.52.66.66 3.66 Co.6.5.5 0.76 0.8 0.6 0.65 0.00 그림 3 결합방법별모든데이타셋에대한평균오분류율과표준편차 표 5 제안하는방법과의 t검정을통한성능통계적유의수준분석결과 결합방법 AVG us p값 p<0.02 p<0.002 p<0.007 릿 과 AVG( 평균선택방법 은비슷한성능을보였다. us의경우분류성능은 와비슷하였으나, 클러스터링결과에영향을받기때문에표준편차가높게나타났다. 표 5는제안하는방법과 AVG,, us간의대응 t검정결과를보여준다. 4.3 성능안정성평가분류기결합방법의성능안정성을평가하기위하여본논문에서는결합방법별로모든데이타셋에대한 0- fol ross valato실험분류결과의 CV(Coeffet of Varae 값을측정하였다. CV값은상호분산정도를측정하기위해많이사용되는통계적방법으로, 데이타 값의집중경향을나타낸다. 와 를각각분류율의표 준편차와평균이라고하였을때, CV값은다음과같이계산된다. σ CV = 00% (0 µ 이때 CV값은작을수록분류성능이안정적임을나타낸다. 분석결과그림 4와같이제안하는방법이기존의결합방법에비해가장안정적인성능을보임을확인하였다.
k- 최근접템플릿기반다중분류기결합방법 455 그림 4 분류기결합방법별성능안정성 (CV값이작을수록안정적임을나타냄 fuso obg lassfers: A experet," IEEE Tras. Systes, a, a Cyberets, Part B-Cyberets, Vol.32, No.2, pp. 46-56, 2002. [5] J.-K., J.-H. Hog, a S.-B. Cho, "Fgerprt lassfato usg ultple eso teplate wth SV," J. Korea Iforato See Soet Vol.32, No., pp. 36-46, 2005. [6] A.K. Ja a R.C. Dubes, Algorths for Clusterg Data, Prete Hall, 988. [7] U. aulk a S. Bayopahya "Perforae evaluato of soe lusterg algorths a valy es," IEEE Tras. Patter Aalyss a ahe Itellgee, Vol.24, No.2, pp. 650-654, 2002. 5. 결론 본논문에서는다중분류기를효과적으로결합하기위하여다중결정템플릿방법에 k-최근접이웃분류기법을적용한 k-최근접템플릿을제안하였다. 이는각클래스를여러개의템플릿으로모델링하며, 이들중가장유사한하나의템플릿과매칭하는대신 k개의모델을참조하기때문에기존의분류기결합방법에비해안정적이고높은분류성능을획득할수있다. 이때 k값은데이타셋의클래스내밀집도와클래스간분리도에따라적합한 k값을자동으로선택한다. 기존의분류기결합방법인투표기반, 최대값선택, 최소값선택, 평균선택, 결정템플릿방법등을이용하여 UCI와 EENA의 0가지데이타셋에대한비교실험을수행한결과제안하는방법이안정적이면서높은성능을보임을확인하였다. 추후연구로보다다양한데이타셋에대한성능평가를통해방법의일반성을검증하고, 데이타셋의특징과 k값과의상관관계를정량적으로분석하여 k값을보다정교하게선택해주는규칙을생성할계획이다. 참고문헌 [] D. Optz a R. al, "Popular eseble ethos: A epral stu" J. Artfal Itellgee Researh, Vol., pp. 69-98, 999. [2].I. Kuheva, "A theoretal stuy o sx lassfer fuso strateges," IEEE Tras. Patter Aalyss a ahe Itellgee, Vol.24, No.2, pp. 28-286, 2002. [3].I. Kuheva, J.C. Bezek, a R.P.W. Du, "Deso teplates for ultple lassfer fuso: A experetal oparso," Patter Reogto, Vol.34, No.2, pp. 299-34, 200. [4].I. Kuheva, "Swthg betwee seleto a