적응형 재귀 분할 평균법을 이용한 메모리기반 추론 알고리즘 = A Memory - based Reasoning Algorithm using Adaptive Recursive Partition Averaging Method

국문 초록 (Abstract)

메모리 기반 추론에서 기억공간의 효율적인 사용과 분류성능의 향상을 위하여 제안되었던 RPA(Recursive Partition Averaging)알고리즘은 대상 패턴 공간을 분할 한 후 대표 패턴을 추출하여 분류 기준 패턴으로 사용한다. 이 기법은 메모리 사용 효율과 분류 성능 면에서 우수한 결과를 보였지만, 분할 종료 조건과 대표패턴의 추출 방법이 분류 성능 저하의 원인이 되는 단점을 가지고 있었다.
여기에서는 기존 RPA의 단점을 보안한 ARPA(Adaptive RPA) 알고리즘을 제안한다. 제안된 알고리즘은 패턴 공간의 분할 종료 조건으로 특징별 최빈 패턴 구간(FPD: Feature-based population densimeter) 추출 알고리즘을 사용하며, 학습 결과 패턴의 생성을 대표패턴 추출기법 대신 최빈 패턴 구간을 이용하여생성한 최적초월평면(OH: Optimized Hyperrectangle)을 사용한다.
제안된 알고리즘은 k-NN분류기에서 필요로 하는 메모리 공간의 40%정도를 사용하며, 분류에 있어서도 RPA보다 우수한 인식 성능을 보이고 있다. 또한 저장된 패턴의 감소로 인하여, 실제 분류에 소요되는 시간 비교에 있어서도 k-NN보다 월등히 우수한 성능을 보이고 있다.

다국어 초록 (Multilingual Abstract)

We had proposed the RPA(Recursive Partition Averaging) method in order to improve the storage requirement and classification rate of the Memory Based Reasoning. That algorithm worked not bad in many area, however, the major drawbacks of RPA are it's partitioning condition and the way of extracting major patterns.
We propose an adaptive RPA algorithm which uses the FPD(feature-based population densimeter) to stop the ARPA partitioning process and produce, instead of RPA's averaged major pattern, optimizing resulting hyperrectangles.
The proposed algorithm required only approximately 40% of memory space that is needed in k-NN classifier, and showed a superior classification performance to the RPA. Also, by reducing the number of stored patterns, it showed an excellent results in terms of classification when we compare it to the k-NN.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. ARPA 학습 기법
• 4. 실험 및 분석
• 5. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 "재귀 분할 평균기법을 이용한 새로운 메모리 기반 추론 알고리즘" 6 (6): 1849-1857, 1999.

2 "수량적 연관규칙탐사를 위한 효율적인 고빈도 항목열 생성기법" 6 (6): 2597-2607, 1999.

3 "고정 분할 평균알고리즘을 사용하는 새로운 메모리 기반 추론" 6 (6): 1563-1570, 1999.

4 "Weighted k-NN versus Majority k-NN A Recommendation : German National Research Center for Information Technology" 1995.

5 "On Comparing Classifiers: Pitfalls to Avoid and a Recommended Approach" 1 : 1-11, 1997.

6 "Learning vector quantization for pattern recognition Helsinki University of Technology Department of Technical Physics" 1986.

7 "Learning about speech sounds: The NEXUS project" Morgan Kaufmann 1-11, 1987.

8 "Induction of Decision Trees" 81-106, 1986.

9 "An Experimental Comparison of the Nearest- Neighbor and Nearest-Hyperrectangle Algorithms" 19 (19): 1-25, 1995.

10 "Advances in Neural Information Processing Systems 6" Morgan Kaufmann pp.184-191ca.1994.

11 "A study on the optimization of binary decision tree" 16 : 104-112, 1997.

12 "A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features" 10 (10): 57-78, 1993.

13 "A Study of Instance-Based Algorithms for Supervised Learning Tasks University of California" 1990.

14 "A Study of Distance-Based Machine Learning Algorithms" Oregon State University 1995.

15 "A Review and Empirical Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms" 1996.