[논문]클래스 영역을 보존하는 초월 사각형에 의한 프로토타입 선택 알고리즘

백병현; 어성율; 황두성

doi:10.3745/ktsde.2020.9.3.83

초록
AI-Helper

프로토타입 선택은 훈련 데이터로부터 클래스 영역을 대표하는 최소 데이터를 선택하여 낮은 학습 시간 및 저장 공간을 보장하는 장점을 제공한다. 본 논문은 모든 분류 알고리즘에 적용할 수 있는 초월 사각형을 이용한 새로운 훈련 데이터의 생성 방법을 설계한다. 초월 사각형 영역은 서로 다른 클래스 데이터를 포함하지 않으며 클래스 공간을 분할한다. 선택된 초월 사각형 내 데이터의 중간값은 프로토타입이 되어 새로운 훈련 데이터를 구성하고, 초월 사각형의 크기는 클래스 영역의 데이터 분포를 반영하여 조절된다. 전체 훈련 데이터를 대표하는 최소의 프로토타입 집합 선택을 위해 집합 덮개 최적화 알고리즘을 설계했다. 제안하는 방법에서는 탐욕 알고리즘과 곱셈 연산을 포함하지 않은 거리 계산식을 이용하여 집합 덮개 최적화 알고리즘의 다항 시간을 요구하는 시간 복잡도 문제를 해결한다. 실험에서는 분류 성능의 비교를 위해 최근접 이웃 규칙과 의사 결정 트리 알고리즘을 이용하며 제안하는 방법이 초월 구를 이용한 프로토타입 선택 방법보다 우수하다.

Abstract ▼ AI-Helper

Prototype selection offers the advantage of ensuring low learning time and storage space by selecting the minimum data representative of in-class partitions from the training data. This paper designs a new training data generation method using hyper-rectangles that can be applied to general classifi...

Prototype selection offers the advantage of ensuring low learning time and storage space by selecting the minimum data representative of in-class partitions from the training data. This paper designs a new training data generation method using hyper-rectangles that can be applied to general classification algorithms. Hyper-rectangular regions do not contain different class data and divide the same class space. The median value of the data within a hyper-rectangle is selected as a prototype to form new training data, and the size of the hyper-rectangle is adjusted to reflect the data distribution in the class area. A set cover optimization algorithm is proposed to select the minimum prototype set that represents the whole training data. The proposed method reduces the time complexity that requires the polynomial time of the set cover optimization algorithm by using the greedy algorithm and the distance equation without multiplication. In experimented comparison with hyper-sphere prototype selections, the proposed method is superior in terms of prototype rate and generalization performance.

주제어

표/그림 (8)

그림 Fig. 1. Contour Plot for Distance Measure Equation (1)
그림 Fig. 2. The Number of Prototypes per θ
그림 Fig. 3. Prototype Selection Examples of a Toy Problem
그림 Fig. 4. The Comparison in Time of a Toy Problem
그림 Fig. 5. Performance Comparison using Nearest Neighbor
그림 Fig. 6. Performance Comparison using Decision Tree
표 Table 1. UCI Benchmark Problems
표 Table 2. Classification Performance for Benchmark Problems

AI 본문요약
AI-Helper

문제 정의

본 논문에서는 초월 사각형을 이용한 프로토타입 선택방법을 제안했다. 주어진 데이터에서 각 클래스를 대표할 수 있는 프로토타입을 선택하였고, 선택된 프로토타입이 새로운 훈련데이터로 사용된다.

가설 설정

분류 문제 X ={(x_i,y_i) | i = 1,...,n} 는 c개의 클래스y_i∈ {1,...,c}를 가지며 d차원의 입력 벡터 xⁱ ∈R ^d로 가정한다. 특정 클래스 l에 나타나는 데이터 집합은 X l ={( x_i,l)| i = 1,.

제안 방법

본 논문에서 제안하는 방법은 초월 사각형을 이용한 프로토타입 선택 알고리즘을 설계한다. 훈련 데이터 사이의 유사도와 클래스 정보를 이용하여 동일 클래스 데이터만을 포함하는 초월 사각형(hyper-rectangle)을 구성하고, 각 클래스를 대표하는 적은 수의 프로토타입을 결정한다. 2장에서는 관련 연구에 대해 토의하고, 3장에서는 제안하는 방법의 알고리즘을 기술한다.

대상 데이터

제안하는 방법과 고정 반지름 및 가변 반지름 초월 구의 성능 비교를 위해 13개의 UCI Machine Learning Repository[18] 데이터를 사용한다. 13개의 데이터 중 2개는 nominal 데이터이며 나머지는 numeric 데이터이다.

데이터처리

최근접 이웃 규칙 알고리즘은 클래스 경계면에 위치한 데이터들이 분류 성능에 영향이 미비한 반면에 의사 결정 나무 알고리즘은 클래스 경계면에 위치한 데이터들이 분류성능에 큰 영향을 준다. 따라서, 프로토타입 선택 알고리즘별 데이터 분포에 따른 분류 성능의 비교를 위해 두 학습 알고리즘을 사용하였고, 3-겹 교차 검증(3-way cross-validation)을 수행했다.

이론/모형

Equation (3)의 해는 비교적 낮은 계산이 필요한 탐욕 알고리즘(greedy algorithm)을 이용한다. 탐욕 알고리즘은 새롭게 포함되는 같은 클래스 데이터의 비율을 통해 프로토타입을 선택하며, 선택된 프로토타입은 각 클래스의 모든 데이터를 포함한다.

성능/효과

IPS는 선택된 프로토타입 영역 내 서로 다른 클래스를 포함하고 있어 프로토타입 선택 비율이 낮으며, PBL은 클래스경계면에 소규모 영역을 갖는 프로토타입이 빈번하게 선택되기 때문에 프로토타입 선택 비율이 높은 것으로 분석된다. 제안하는 방법은 기존 훈련 데이터에서 약 7.5%~42.9%를 사용하여 순수 최근접 이웃 규칙과 유사한 분류 성능을 얻었으며 높은 일반화 성능을 보였다.
그러나 초월 사각형의 영역이 축소되어 최근접 이웃규칙보다 프로토타입 선택 비율이 높다. 제안하는 프로토타입 선택방법은 기존 훈련 데이터에서 약 8.5%~66.6%를 사용하여 순수 의사 결정 나무 알고리즘과 유사한 분류 성능을 보였다.

후속연구

초월 사각형의 크기가 큰 경우, 프로토타입 선택 비율은 낮아지나 클래스 경계면의 정보가 축소된다. 추후, 클래스 경계면의 정보를 유지함과 동시에 낮은 프로토타입 선택 비율을 갖는 연구가 필요하다.

질의응답

핵심어	질문	논문에서 추출한 답변
	소수의 프로토타입선택의 장점은?	대용량 훈련 데이터의 경우 학습 모델의 복잡도를 증가시키는 중복 및잡음 데이터 등이 존재할 가능성이 높으며, 많은 학습 시간이 요구된다[1, 2]. 훈련 데이터를 대표하는 소수의 프로토타입선택은 불필요한 데이터의 제거, 학습 시간의 단축 그리고 기존 훈련 데이터와 유사한 분류 성능을 얻을 수 있으며 높은일반화 성능을 갖는다는 장점이 있다[3-8].
	프로토타입 선택이란?	프로토타입 선택은 훈련 데이터로부터 클래스 영역을 대표하는 최소 데이터를 선택하여 낮은 학습 시간 및 저장 공간을 보장하는 장점을 제공한다. 본 논문은 모든 분류 알고리즘에 적용할 수 있는 초월 사각형을 이용한 새로운 훈련 데이터의 생성 방법을 설계한다.
	PBL가 초월구를 구성하는 방법은 무엇인가?	PBL(prototype based learning, [13])은 프로토타입 영역 내 포함되는 데이터를 고려한다는 측면에서 RSC와 유사하다. 그러나 가장 근접한 서로 다른 클래스 데이터의 거리와가장 떨어져 있는 동일 클래스 데이터 거리의 중간을 반지름으로 설정하여 초월구를 구성한다.

참고문헌 (18)

N. Bhatia, Vandana, "Survey of Nearest Neighbor Techniques," International Journal of Computer Science and Information Security, Vol.8, No.2, 2010.
I. Triguero, J. Derrac, S. Garcia, and F. Herrea, "A Taxonomy and Experimental Study on Prototype Generation for Nearest Neighbor Classification," IEEE Transactions on Systems, Man, and Cybernetics Part C(Application And Reviews), Vol.42, No.1, pp.86-100, 2012.

상세보기
R. M. Cruz, R. Sabourin, and G. D. Cavalcanti, "Prototype selection for dynamic classifier and ensemble selection," Neural Computing and Applications, Vol.29, pp.447-457, 2016.
R. M. Curz, R. Sabourin, and G. D. Cavalcanti, "Analyzing different prototype selection techniques for dynamic classifier and ensemble selection," International Joint Conference on Neural Networks, pp.3959-3966, 2017.
E. Pekalska, R. P. W. Duin, and P. Paclik, "Prototype selection for dissimilarity-based classifier," Pattern Recognition, 39, pp.189-208, 2006.

상세보기
J. A. Olvera-Lopez, J. A. Carrasco-Ochoa, J. F. Martinez Trinidad, and J. Kittler, "A review of instance selection methods," Artif Intell Rev, Vol.34, No.2, pp.133-143, 2010.

상세보기
D. R. Wilson and T. R. Martinez, "Reduction techniques for instance-based learning algorithms," Machine Learning, Vol.38, No.3, pp.257-286, 2000.
S. Garcia, J. Derrac, J. Cano, and F. Herrera, "Prototype selection for nearest neighbor classification: taxonomy and empirical study," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.34, No.3, pp.417-435, 2012.

상세보기
S. Choi, S. Cha, and C. Tappert, "A Survey of Binary Similarity and Distance Measures," J. Systemics, Cybernetics and Informatics, Vol.8, No.1, pp.43-48, 2010.
J. Bien and R. Tibshirani, "Prototype selection for interpretable classification," The Annals of Applied Statistics, Vol.5, No.4, pp.2403-2424, 2011.

상세보기
D. Marchette, "Class cover catch digraphs," Wiley Interdisciplinary Reviews: Computational Statistics, Vol.2, No.2, pp.171-177, 2010.

상세보기
R. Younsi and A. Bagnall, "A randomized sphere cover classifier," International Conference on Intelligent Data Engineering and Automated Learning, pp.234-241, 2010.
S. Seyong and H. Doosung, "Prototype based Classification by Generating Multidimensional Spheres per Class Area," Journal of The Korea Society of Computer and Information, Vol.20, No.2, 2015.
S. Arora, D. Karger, and M. Karpinski, "Polynomial time approximation schemes for dense instances of NP-hard problems," Journal of Computer and System Sciences, Vol.58, pp.193-210, 1999.

상세보기
D. S. Hwang and D. W. Kim, "Near-boundary data selection ofor fast support vector machines," Malasian Journal of Computer Science, Vol.25, No.1, pp.23-37, 2012.
F. Angiulli, "Fast Nearest Neighbor Condensation for Large Data Sets Classification," IEEE Transactions on Knowledge and Data Engineering, Vol.19, No.11, pp.1450-1464, 2007.

상세보기
A. H. Cannon and L. J. Cowen, "Approximation algorithms for the class cover problem," Annals of Mathematics and Artificial Intelligence, Vol.40, No.3-4, pp.215-223, 2004.

상세보기
UCI Machine Learning Repository [Online]. Available: https://archive.ics.uci.edu/ml/.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

클래스 영역을 보존하는 초월 사각형에 의한 프로토타입 선택 알고리즘
Hyper-Rectangle Based Prototype Selection Algorithm Preserving Class Regions 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (8)

표/그림 (8)

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (18)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

클래스 영역을 보존하는 초월 사각형에 의한 프로토타입 선택 알고리즘 Hyper-Rectangle Based Prototype Selection Algorithm Preserving Class Regions 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (8) 모든 표/그림 보기

표/그림 (8) 슬라이드로 보기

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (18)

이 논문을 인용한 문헌

저자의 다른 논문 :

황두성 (22)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

클래스 영역을 보존하는 초월 사각형에 의한 프로토타입 선택 알고리즘
Hyper-Rectangle Based Prototype Selection Algorithm Preserving Class Regions 원문보기

초록
AI-Helper

표/그림 (8)

표/그림 (8)

AI 본문요약
AI-Helper