인스턴스 기반 학습의 대표적인 알고리즘인 k-NK(K-Nearest Neighbors)은 단순히 전체 학습패턴을 메모리에 저장한 다음, 분류할 때 학습 패턴들과의 거리를 계산하여 가장 가까운 학습패턴의 클래스로 테스트 패턴을 분류한다. K-NN 기법은 만족할 만한 분류성능을 보여주지만, 학습패턴의 개수가 늘어나면 메모리와 분류 시간이 증가하는 문제점을 가지고 있다. 그러므로, 메모리의 효율적 사용과 분류 시간을 단축시키기 위한 다양한 연구들이 발표되었으며, 그 대표적인 예로 NGE(Nested Generalized Exemplar) 이론을 들 수 있다. 본 논문에서는 학습패턴의 집합으로부터 대표패턴을 생성하는 RPA(Recursive Partition Averaging)기법과 점진적으로 대표패턴을 추출하는 IRPA(Incremental RPA)기법을 제안하였다. RPA기법은 전체 학습패턴의 공간을 재귀적으로 분할하면서 대표패턴을 생성하며, IRPA 기법은 RPA 기법의 특성상 패턴의 특징 개수가 많은 경우, 과도한 분할로 인하여 생성되는 많은 개수의 대표패턴을 줄이기 위하여 점진적으로 대표패턴을 추출하는 알고리즘이다. 본 논문에서 제안한 기법은 기존의 k-NN 기법과 비교하여 현저하게 줄어든 대표패턴을 이용하석 유사한 분류 성능을 보여주며, NGE 이론을 구현한 EACH 시스템과 비교하여 탁월한 분류 성능을 보여준다.
인스턴스 기반 학습의 대표적인 알고리즘인 k-NK(K-Nearest Neighbors)은 단순히 전체 학습패턴을 메모리에 저장한 다음, 분류할 때 학습 패턴들과의 거리를 계산하여 가장 가까운 학습패턴의 클래스로 테스트 패턴을 분류한다. K-NN 기법은 만족할 만한 분류성능을 보여주지만, 학습패턴의 개수가 늘어나면 메모리와 분류 시간이 증가하는 문제점을 가지고 있다. 그러므로, 메모리의 효율적 사용과 분류 시간을 단축시키기 위한 다양한 연구들이 발표되었으며, 그 대표적인 예로 NGE(Nested Generalized Exemplar) 이론을 들 수 있다. 본 논문에서는 학습패턴의 집합으로부터 대표패턴을 생성하는 RPA(Recursive Partition Averaging)기법과 점진적으로 대표패턴을 추출하는 IRPA(Incremental RPA)기법을 제안하였다. RPA기법은 전체 학습패턴의 공간을 재귀적으로 분할하면서 대표패턴을 생성하며, IRPA 기법은 RPA 기법의 특성상 패턴의 특징 개수가 많은 경우, 과도한 분할로 인하여 생성되는 많은 개수의 대표패턴을 줄이기 위하여 점진적으로 대표패턴을 추출하는 알고리즘이다. 본 논문에서 제안한 기법은 기존의 k-NN 기법과 비교하여 현저하게 줄어든 대표패턴을 이용하석 유사한 분류 성능을 보여주며, NGE 이론을 구현한 EACH 시스템과 비교하여 탁월한 분류 성능을 보여준다.
K-NN (k-Nearest Neighbors), which is a well-known instance-based learning algorithm, simply stores entire training patterns in memory, and uses a distance function to classify a test pattern. K-NN is proven to show satisfactory performance, but it is notorious formemory usage and lengthy computation...
K-NN (k-Nearest Neighbors), which is a well-known instance-based learning algorithm, simply stores entire training patterns in memory, and uses a distance function to classify a test pattern. K-NN is proven to show satisfactory performance, but it is notorious formemory usage and lengthy computation. Various studies have been found in the literature in order to minimize memory usage and computation time, and NGE (Nested Generalized Exemplar) theory is one of them. In this paper, we propose RPA (Recursive Partition Averaging) and IRPA (Incremental RPA) which is an incremental version of RPA. RPA partitions the entire pattern space recursively, and generates representatives from each partition. Also, due to the fact that RPA is prone to produce excessive number of partitions as the number of features in a pattern increases, we present IRPA which reduces the number of representative patterns by processing the training set in an incremental manner. Our proposed methods have been successfully shown to exhibit comparable performance to k-NN with a lot less number of patterns and better result than EACH system which implements the NGE theory.
K-NN (k-Nearest Neighbors), which is a well-known instance-based learning algorithm, simply stores entire training patterns in memory, and uses a distance function to classify a test pattern. K-NN is proven to show satisfactory performance, but it is notorious formemory usage and lengthy computation. Various studies have been found in the literature in order to minimize memory usage and computation time, and NGE (Nested Generalized Exemplar) theory is one of them. In this paper, we propose RPA (Recursive Partition Averaging) and IRPA (Incremental RPA) which is an incremental version of RPA. RPA partitions the entire pattern space recursively, and generates representatives from each partition. Also, due to the fact that RPA is prone to produce excessive number of partitions as the number of features in a pattern increases, we present IRPA which reduces the number of representative patterns by processing the training set in an incremental manner. Our proposed methods have been successfully shown to exhibit comparable performance to k-NN with a lot less number of patterns and better result than EACH system which implements the NGE theory.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 불필요한 대표패턴의 생성을 방지하여 메모리 사용 효율을 높이고 분류 시간을 단축시키기 위해서 점진적으로 대표패턴을 추출하는 LRPA 기법을 제안하며, 다음의는 IRPA 기법의 알고리즘을 보여주고 있다.
제안 방법
본 논문에서 제안한 RPA, IRPA 기법은 테스트 패턴을분류하기 위하여 대표패턴들과 수식 (6)으로 거리 계산을하며, 가장 가까운 대표패턴의 클래스를 출력으로 결정한다. 따라서 기존의 k-NN 기법과는 달리 사전에 최적의 k 값을구할 필요가 없다.
본 논문에서는 IBL(Instance-Based Learning) 기법을 기반으로 한 새로운 학습 방법인 RPA(Recursive Partition Averaging) 기법과, 점진적으로 대표패턴을 추출하는 IRPA (Incremental RPA) 기법을 제안하였으며, UCI Machine Learning Repository에서 벤치마크 데이터를 발췌하여 제안한 기법과 k-NN 기법, EACH 시스템의 분류 성능과 메모리 사용 효율을 실험적으로 검증하였다.
본 논문에서는 테스트 패턴의 정확한 분류를 위하여 패턴 간의 거리를 계산할 때, 특징 가중치를 이용하며, 특징 가중치는 학습이 완료되면, 분할된 패턴공간의 학습패턴 분포를 이용하여 계산한다.
우선, 특징 가중치를 구하기 위하여 각 특징의 분할영역의 개수를 검사한다. (그림 3)은 RPA 기법으로 학습했을 경우, 분할된 패턴 공간의 예제이며, 이때 실제 분할된 분할영역의 경계선에서 가상의 분할선을 연장하여 각 특징에 대한분할 개수를 결정한다.
대상 데이터
본 논문에서는 기계 학습의 벤치마크 자료로 많이 사용되는 UCI Machine Learning Database Repository 에서 6개의데이터셋을 발췌하여 사용하였다[12]. 이들 데이터셋의 모든특징은 실수 값으로 구성되며, 다음의<표 5>는 실험자료의분포를 나타낸다.
데이터처리
본 논문에서 제안한 RPA, IRPA 기법의 성능을 k-NN 기법, WeightVote k-NN 기법, 그리고 EACH 시스템과 비교검증하였으며, 실험 방법은 Stratified 10-fold Cross-validation 기법을 사용하였다.
이론/모형
본 논문에서 제안하는 RPA기법은 전체 학습패턴 공간을 (그림 1)과 같이 재귀적으로 분할하면서 대표패턴을 생성하며, 대표패턴은 인스턴스 평균(Instance Averaging)법을 이용하여 계산한다[10].
분류 성능 실험에서 k-NN 기법은 Leave-one-out Cross-vaHdation기법으로 계산한 최적의 k값을 사용하였으몌 10], EACH 시스템은 시드 개수 5, 가중치 변화량 0.2를 초기값으로 설정하여 실험하였다. 다음<표 6>은 각 데이터셋에서사용된 k-NN 기법의 k값과 k값을 계산하기 위하여 사용된 시간을 나타낸다.
성능/효과
EACH 시스템이 Ionosphere에서 저조한 성능을 보이는 것은 무작위로 설정한 초기 시드(seed) 의 영향으로 볼 수 있으몌9], 에 나타난 바와 같이본 논문에서 제안한 기법이 EACH 시스템보다 모든 데이터셋에서 안정적인 성능을 보여준다.
(그림 5)는 메모리에 저장되는 패턴의 개수를 보여주고있다. RPA 기법은 k-NN 기법보다 작은 개수의 예제로 구성되며, IRPA 기법의 경우에는 k-NN 기법보다 Breastcancer 90%, Glass 77%, Ionosphere 53%, Iris 89%, New-Thyroid 91%, Wine 69% 정도 줄어드는 것을 볼 수 있다. EACH 시스템과 비교할 때, RPA, IRPA 기법의 대표패턴 개수가 전반적으로 많이 생성되며, 특히 다른 데이터셋에비하여 특징의 개수가 많은 Ionosphere(34)의 경우 두 배 이상 많은 것을 볼 수 있다.
다음의 (그림 4)는 분류 성능을 보여주고 있다. 본 논문에서 제안한 RPA, IRPA 기법은 k-NN 기법, EACH 시스템과비교하여 유사한 성능 또는 향상된 분류 성능을 보여주고있으며, Ionosphere의 경우, EACH 시스템보다 높은 분류성능을 보여주고 있다. EACH 시스템이 Ionosphere에서 저조한 성능을 보이는 것은 무작위로 설정한 초기 시드(seed) 의 영향으로 볼 수 있으몌9], <표 7>에 나타난 바와 같이본 논문에서 제안한 기법이 EACH 시스템보다 모든 데이터셋에서 안정적인 성능을 보여준다.
본 논문에서 제안한 RPA, IRPA 기법은 k-NN 기법보다적은 개수의 대표패턴을 이용하여 유사한 성능을 보여주고 있으며, 데이터셋이 달라질 때마다 최적의 k값을 따로 구할 필요가 없다는 장점을 가진다. 또한, IRPA 기법은 학습패턴 집합으로부터 점진적으로 대표패턴을 추출하는 방법을 이용하여 보다 적은 패턴개수로 k-NN, RPA 기법과 유사하거나 향상된 분류 성능을 보장한다.
또한, IRPA 기법은 학습패턴 집합으로부터 점진적으로 대표패턴을 추출하는 방법을 이용하여 보다 적은 패턴개수로 k-NN, RPA 기법과 유사하거나 향상된 분류 성능을 보장한다. 한편, EACH 시스템은 초기시드에 따라서 분류 성능의 편차가 심하지만, 본 논문에서 제안한 기법은 모든 데이터 셋에서 안정적인 분류 성능을 보장한다.
후속연구
그러므로, 향후 연구로 이러한 데이터셋에서 불필요한 분할을 방지할 수 있는 방법과 학습에 필요한 특징의 개수를 줄일수 있는 방법에 대해서 연구할 예정이며, 또한, RPA나 IRPA기법을 기반으로 IF-THEN형태의 규칙을 생성하는 방법을 현재 연구중에 있다.
참고문헌 (13)
T. Dietterich, 'A Study of Distance-Based Machine Learning Algorithms', Ph. D. Thesis, computer Science Dept., Oregon State University, 1995
D. Wettschereck and T. Dietterich, 'Locally Adaptive Nearest Neighbor Algorithms', Advances in Neural Information Processing Systems 6, pp.184-191, Morgan Kaufmann, San Mateo, CA. 1994
D. Wettschereck, 'Weighted k-NN versus Majority k-NN A Recommendation'. German National Research Center for Information Technology, 1995
D. Aha, 'A Study of Instance-Based Algorithms for Supervised Learning Tasks: Mathematical, Empirical, and Psychological Evaluations', Ph. D. Thesis, Information and Computer Science Dept., University of California, Irvine, 1990
D. Wettschereck and T. Dietterich, 'An Experimental Comparison of the Nearest-Neighbor and NearestHyperrectangle Algorithms', Machine Learning, Vol.19, No. 1, pp.1-25, 1995
S. Salzberg, 'A Nearest hyperrectangle learning method, Machine Learning', No.1, pp.251-276, 1991
D. Wettschereck, et al., 'A Review and Empirical Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms', Artificial Intelligence Review Journal, 1996
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.