유전자 알고리즘 기반의 불완전 데이터 학습을 위한 속성값계층구조의 생성 = Genetic Algorithm Based Attribute Value Taxonomy Generation for Learning Classifiers with Missing Data

국문 초록 (Abstract)

부부분불완전 데이터(Partially Missing Data) 또는 데이터의 속성 값이 표현되는 정도의 깊이가 서로 다른 데이터를 학습하는데 있어서 속성값계층구조(Attribute Value Taxonomy, AVT)를 기반으로 학습하면 기존의 학습 알고리즘을 통해 얻은 결과보다 정확하고 간결한 분류기를 얻을 수 있다는 사실이 밝혀졌다. 하지만 이러한 속성값계층구조는 처음부터 전문가 또는 데이터 도메인에 대한 지식을 가지고 있는 사람에 의해 만들어져 제공되어야 한다. 이러한 수작업을 통한 속성값계층구조를 생성하기 위해서는 많은 시간이 걸리며 생성과정에서 오류가 발생할 수 있다. 또한 데이터 도메인에 따라서 속성값계층구조를 제공할 전문가가 부재한 경우가 있다. 이러한 배경 아래 본 논문은 유전자 알고리즘을 통해 자동으로 근 최적의 속성값계층구조를 생성하는 알고리즘(GA-AVT-Learner)을 제안한다. 본 논문의 실험은 다양한 실제 데이터를 가지고 GA-AVT-Learner로 생성한 속성값계층구조를 다른 속성값계층구조와 비교하였다. 따라서 GA-AVT-Learner에 의해 생성된 속성값계층구조가 정확하고 간결한 분류기를 제공함을 보이고, 불완전데이터 처리에 있어서도 높은 효율을 보임을 실험적으로 증명하였다.

다국어 초록 (Multilingual Abstract)

Learning with Attribute Value Taxonomies (AVT) has shown that it is possible to construct accurate, compact and robust classifiers from a partially missing dataset (dataset that contains attribute values specified with different level of precision). Yet, in many cases AVTs are generated from experts or people with specialized knowledge in their domain. Unfortunately these user-provided AVTs can be time-consuming to construct and misguided during the AVT building process. Moreover experts are occasionally unavailable to provide an AVT for a particular domain. Against these backgrounds, this paper introduces an AVT generating method called GA-AVT-Learner, which finds a near optimal AVT with a given training dataset using a genetic algorithm. This paper conducted experiments generating AVTs through GA-AVT-Learner with a variety of real world datasets. We compared these AVTs with other types of AVTs such as HAC-AVTs and user-provided AVTs. Through the experiments we have proved that GA-AVT-Learner provides AVTs that yield more accurate and compact classifiers and improve performance in learning missing data.

참고문헌 (Reference)

1 Duda, "Pattern Classification second edition" Wiley-interscience, Inc. 8 : 409-413, 2000.

2 Mitchell, "Machine Learning" McGraw-Hill Companies Inc. 3 : 52-80, 1997.

3 Zhang, "Learning Decision Tree Classifiers from Attribute Value Taxonomies and Partially Specified Data" 880-887, 2003

4 Fuglede, "Jensen-Shannon Divergence and Hilbert Space Embedding" 31-, 2004

5 Mitchell, "Introduction to Genetic Algorithms" MIT Press 1996.

6 Quinlan, "Introduction of Decision Trees" 1 (1): 81-106, 1986.

7 Gen, "Genetic Algorithms and Engineering Optimization" John Wiley & Sons, Inc. 3 : 97-141, 2000.

8 Goldberg, "Genetic Algorithm in Search, Optimization, and Machine Learning" Addison-Wesley 1989.

9 Kang, "Generation of Attribute Value Taxonomies from Data for Data-Driven Construction of Accurate and Compact Classifiers" 130-137, 2004

10 Joo, "Generating AVTs Using GA for Learning Decision Tree Classifiers with Missing Data" 347-354, 2004.

11 Yang, "Feature Subset Selection Using A Genetic Algorithm" Kluwer Academic Publishers 3 : 117-136, 1998.

12 Quinlan, "C4.5 : Programs for Machine Learning" Morgan Kaufmann 27-33, 1992.

13 Zhang, "AVT-NBL: An Algorithm for Learning Compact and Accurate Naive Bayes Classifiers from Attribute Value Taxonomies and Data" 289-296, 2004