의사결정나무 기반 알고리즘 논문 리딩자료

Decision Tree와 Random Forest 에 대해 다룹니다.

 

 

 

[Tree-based model 논문 리딩자료]

 

Induction of Decision Trees

J.R. QUINLAN, South Wales Institute of Technology, 1985

 

Random Decision Forest

Tin Kam Ho, AT&T Bell Laboratories, 1995

 

 

 

 

Contents:

Decision Tree와 Random Forest 창안자의 논문 중 Abstract, Introduction, Conclusion 부분의 영/한 번역입니다.

 

Why:

이 자료는 알고리즘의 근본을 파악하기 위해 제작하였습니다. 모든 논문의 Abstract & Introduction 에는 해당 업계의 전반적인 역사와 고민거리 / 연구개발 방향성과 연구진이 왜 이 연구를 진행했는지에 대한 당위성이 들어있습니다. 그리고 Conclusion 은 해당 논문을 통해 구현한 산출물을 요약하고 있습니다.

 

 

 

Decision Tree: 의사결정 나무.

 

 

Abstract

The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications.

지금까지(80년대 기준) 귀납적 추론을 통해 지식 기반 시스템을 구축하는 기술은 여러 실사례에서 성공적으로 입증되었습니다.

 

This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail.

이 논문에서는 다양한 사용처에서 의사결정나무를 만드는 방법을 요약하고, 이러한 방안 중 ID3 방식을 상세히 기술하였습니다.(ID3, C4.5, C5.0, CART 라는 방식이 있고, 저자 J.R. QUINLAN은 상업용도로 현재 C5.0을 판매중입니다.)

 

Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete.

최근 연구(80년대 기준)에서 나온 결과는 노이즈(잡음)가 들어있거나 데이터 셋이 분완전한 경우를 대처하기 위한 방법론을 다룹니다.

 

A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared.

의사결정 나무를 만들기 위한 기본 알고리즘의 잘 알려진 단점을 논의하고 이를 극복하는 두 가지 방법을 비교할 것입니다.

 

The paper concludes with illustrations of current research directions.

이 논문은 현재(80년대 기준) 이 분야의 연구방향을 제시한 삽화로 마무리합니다.

 

 

Introduction

 

 

Since artificial intelligence first achieved recognition as a discipline in the mid 1950's, machine learning has been a central research area.

인공지능이 1950년대 중반에 처음으로 학문으로서 인정받고 나서 지금까지(80년대 기준) 기계학습은 핵심 연구 분야이었습니다.

 

Two reasons can be given for this prominence.

핵심 연구분야가 된 이유는 두 가지입니다.

 

The ability to learn is a hallmark of intelligent behavior, so any attempt to understand intelligence as a phenomenon must include an understanding of learning.

학습을 할 수 있다는 것은 지능적인 행동의 특징입니다. 따라서 지능이라는 현상을 이해하려면 반드시 학습에 대한 이해 또한 이루어져야 합니다.

 

More concretely, learning provides a potential methodology for building high-performance systems.

더 구체적으로는, 학습은 잠재적으로 고성능 시스템을 구축할 수 있는 방법론을 제공합니다.

 

Research on learning is made up of diverse subfields.

학습에 대한 연구분야는 다양한 하위 분야로 이루어져 있습니다.

 

At one extreme there are adaptive systems that monitor their own performance and attempt to improve it by adjusting internal parameters.

한 쪽 극단에서는 자체 성능을 모니터링하고 내부 파라미터를 조정하여 자체 성능을 개선하려고 하는 적응형 시스템이 있습니다.

 

This approach, characteristic of a large proportion of the early learning work, produced self-improving programs for playing games (Samuel, 1967), balancing poles (Michie, 1982), solving problems (Quinlan, 1969) and many other domains.

이 접근방식은 초기 학습량이 많은 부분을 차지한다는 특징이 있고, 게임(Samuel, 1967), 폴(Michie, 1982), 문제 해결(Quinlan, 1969) 등 다양한 분야에서 자가-성능향상을 꾀하는 프로그램을 만들었습니다.

 

A quite different approach sees learning as the acquisition of structured knowledge in the form of concepts (Hunt, 1962; Winston, 1975), -discrimination nets (Feigenbaum and Simon, 1963), or production rules (Buchanan, 1978).

이와는 다른 접근법으로는 학습을 개념의 형태로 구조화된 지식을 습득하는 것으로 봅니다.(Hunt, 1962; Winston, 1975). -descrimination nets(Feigenbaum and Simon, 1963) 또는 생산규칙(Buchanan, 1978)의 예가 그렇습니다.

 

The practical importance of machine learning of this latter kind has been underlined by the advent of knowledge- based expert systems.

이 후자의(구조화된 지식 습득) 실질적인 중요성은 지식 기반 전문가 시스템의 출현으로 인해 강조되어 왔습니다.(80년대 기준)

 

As their name suggests, these systems are powered by knowledge that is represented explicitly rather than being implicit in algorithms.

이 이름에서 알 수 있듯, 이러한 시스템(구조화된 지식 습득)은 알고리즘에 명시적으로 표현되는 지식을 기반으로 하여 동작합니다.

 

The knowledge needed to drive the pioneering expert systems was codified through protracted interaction between a domain specialist and a knowledge engineer.

전문가 시스템을 구축하는 데 필요한 지식은 도메인 전문가(전공자 + 경력자)와 지식 엔지니어 간의 장기간의 상호 작용을 통해 성문화(법전으로 만들다, defined/derived 와 유사)되었습니다.

 

While the typical rate of knowledge elucidation by this method is a few rules per man day, an expert system for a complex task may require hundreds or even thousands of such rules.

이 방식으로 지식을 표현하는 것은 1인당 하루에 몇 개의 규칙만 적용하면 되는 반면, 복잡한 작업을 위한 전문가 시스템에서는 수백 ~ 수천 개의 규칙이 필요할 수 있습니다.

 

It is obvious that the interview approach to knowledge acquisition cannot keep pace with the burgeoning demand for expert systems; Feigenbaum (1981) terms this the 'bottleneck' problem.

인터뷰로 지식을 수집하여 전문가 시스템을 만든다는 접근법은 증가하는 지식 수요에 발 맞춰 뒤따라갈 수 없습니다; Feigenbaum(1981)은 이것을 '병목' 문제라고 부릅니다.

 

This perception has stimulated the investigation of machine learning methods as a means of explicating knowledge (Michie, 1983).

이러한 인식은(전문가 시스템으로는 미래가 보이지 않음) 지식의 설명 수단으로서의 기계학습 방법론에 대한 조사가 활발하게끔 만들었습니다.(Michie, 1983).

 

This paper focusses on one microcosm of machine learning and on a family of learning systems that have been used to build knowledge-based systems of a simple kind.

이 논문은 하나의 작은 기계학습 분야(Decision Tree, ID3 알고리즘)와 단순 지식기반 시스템을 구축하는 데 사용하는 학습 방법론들에 초점을 맞추고 있습니다.

 

 

Conclusion

 

 

The aim of this paper has been to demonstrate that the technology for building decision trees from examples is fairly robust.

본 연구의 목적은 여러 사례를 통해 의사결정나무를 만드는 기술이 상당히 강건하다는 것(overfit 잘 없게 만드는 것 가능)을 증명하는 것입니다.

 

Current commercial systems are powerful tools that have achieved noteworthy successes.

현재의(80년대 기준) 상업적 시스템(회사에서 사용하는 알고리즘)은 주목할 만한 성공을 거둔 강력한 도구들입니다.

 

The groundwork has been done for advances that will permit such tools to deal even with noisy, incomplete data typical of advanced real-world applications.

현실세계의 응용처(real-world application) 에서 일상으로 만나는 전형적인 노이즈(잡음, 데이터에 정확하지 않은 값이 있는 경우 포함)가 있거나 불완전한(빈 값) 데이터가 있습니다. 본 연구에서는 상업적 시스템(회사에서 사용하는 알고리즘) 이러한 데이터들을 잘 처리할 수 있는 근간을 마련합니다.

 

Work is continuing at several centers to improve the performance of the underlying algorithms.

기본 알고리즘의 성능을 향상시키기 위해 여러 센터(분야)에서 작업을 이어나가고 있습니다.

 

Two examples of contemporary research give some pointers to the directions in which the field is moving.

현대 연구(80년대 기준)의 두 가지 예를 들어 업계(머신러닝 분야) 동향이 발전하게 되는 방향성을 짚어봅니다.

 

While decision trees generated by the above systems are fast to execute and can be very accurate, they leave much to be desired as representations of knowledge.

위 시스템(상업적)에 의해 생성된 결정 트리는 매우 빠르고 정확하지만 지식을 표현한다는 관점에서는 아쉬움이 있습니다.

 

Experts who are shown such trees for classification tasks in their own domain often can identify little familiar material.

특정 분야에 대해 의사결정나무 알고리즘 내부 해석결과가 전문가가 알고있는 전문지식과 다른 경우가 종종 발생합니다.(예시 : 알고리즘 해석결과 a센서가 기준치 이하이면 위험하다고 판별했는데 엔지니어 관점에서는 a센서를 상한선 관리하고 있는 경우(기준치 이상일 때 위험))

 

It is this lack of familiarity (and perhaps an underlying lack of modularity) that is the chief obstacle to the use of induction for building large expert systems.

대규모 전문가 시스템 구축을 유도하기에 가장 큰 장애물은 친숙함의 부족(그리고 아마도 모듈성의 근본적인 부족)입니다.

Recent work by Shapiro (1983) offers a possible solution to this problem.

Shapiro(1983년)의 최근 연구는 이 문제를 해결할만한 가능성을 제시합니다.

 

In his approach, called Structured Induction, a rule-formation task is tackled in the same style as structured programming.

구조화된 유도라고도 하는 Shapiro의 방법에 따르면, 규칙을 만드는 작업은 구조화된 프로그래밍과 같은 방식으로 다룹니다.

 

The task is solved in terms of a collection of notional super-attributes, after which the subtasks of inducing classification rules to find the values of the super-attributes are approached in the same top-down fashion.

분류 규칙을 유도하는 것과 동일한 하향식으로 super-attribute를 찾는 하위 작업(규칙 만드는 작업의 하위)이 끝마고 나면, 이 규칙을 만드는 작업은 개념적 super-attribute의 집합으로 해결됩니다,(super-attribute는 앙상블과 유사한 개념입니다.)

 

In one classification problem studied, this method reduced a totally opaque, large decision tree to a hierarchy of nine small decision trees, each of which 'made sense' to an expert.

한 분류 문제에서 이 방법은 완전히 불투명하고(해석 어려움, 블랙박스의 개념) 큰 하나의 의사 결정 트리를 9개의 작은 의사 결정 트리를 계층으로 만들어 축소했으며, 각각의 작은 의사 결정 트리는 전문가가 결과를 보았을 때 ‘말이 된다’는 평을 받았습니다.

 

ID3 allows only two classes for any induction task, although this restriction has been removed in most later systems.

ID3 알고리즘은 원래 이진분류(0 또는 1)만 가능했지만 최신 버전에서는 다양한 분류가 가능합니다.

 

Consider, however, the task of developing a rule from a given set of examples for classifying an animal as a monkey, giraffe, elephant, horse, etc.

동물을 원숭이, 기린, 코끼리, 말 등으로 분류하는 문제에서 머신러닝 알고리즘 규칙을 개발하는 경우를 예로 들어 생각해보겠습니다.

 

A single decision tree could be produced in which these various classes appeared as leaves.

다양한 클래스(분류하고자 하는 경우의 수, 지금은 동물의 종류)가 잎으로(Leaf node) 나타나는 하나의 의사결정 나무를 생성할 수 있겠습니다.

 

An alternative approach taken by systems such as INDUCE (Michalski, 1980) would produce a collection of classification rules, one to discriminate monkeys from non-monkeys, another to discriminate giraffes from non-giraffes, and so on.

INDUCE(Michalski, 1980)와 같은 시스템이 취하는 또 다른 접근법은 다음과 같습니다. 분류 규칙의 집합(머신러닝 알고리즘 여러 개)을 만들어 내는데, 하나는 원숭이와 비원숭이를 구별하는 것이고, 다른 하나는 기린과 비기린을 구별하고, 다른 하나는 ... 인 식입니다.

 

Which approach is better?

어떤 접근법이 더 나을까요?

 

In a private communication, Marcel Shoppers has set out an argument showing that the latter can be expected to give more accurate classification of objects that were not in the training set.

사적인 자리에서 Marcel Shoppers라는 분은 후자(큰 의사결정나무 딱 하나 있는 것 대신 여러 개의 집합)가 훈련 세트에 없는 물체에 대해 더 정확한 분류를 할 것으로 기대할 수 있다는 주장을 펴고 있다.(이 부분은 overfitting과도 연관이 있습니다.)

 

The multi-tree approach has some associated problems - the separate decision trees may classify an animal as both a monkey and a giraffe, or fail to classify it as anything, for example - but if these can be sorted out, this approach may lead to techniques for building more reliable decision trees.

의사결정 나무를 여러 개 만드는 접근법은 조금 문제가 있습니다. 별도의 의사결정 나무는 동물을 원숭이와 기린으로 분류하거나, 아니면 그 어느것으로도 분류할 수 없을 수도 있습니다(머신러닝 결과가 하나가 아니라 여러개 또는 0 개 일수도 있다는 이야기). 하지만 만약 이 상황을 해결할 수 있다면, 이 접근법은 더 신뢰할 수 있는 의사결정 나무를 만드는 기술로 이어질 수 있습니다. -> (bagging 에 대한 내용이 없기 때문에 Random Forest 보다는 label(class)를 서로 다르게 학습한 의사결정 나무 여러개를 의미하는 것으로 보입니다.)

 

 

 

 

Random Forest: Bagging 방식의 알고리즘.

 

 

Abstract

 

Decision trees are attractive classifiers due to their high execution speed.

의사결정나무는 빠른 것이 강점인 분류기입니다.

 

But trees derived with traditional methods often cannot be grown to arbitrary complexity for possible loss of generalization accuracy on unseen data.

그러나 전통적인 방법으로 만든 의사결정 나무는 추상적인 복잡도를 가지게끔 만들 수 없어서

새로운 데이터에 대한 정확도의 손실(일반화 불가능) 가능성이 있다.

 

The limitation on complexity usually means suboptimal accuracy on training data.

(모델이 갖는) 복잡성의 한계는 보통 훈련 데이터에 대한 좋은 정확도(학습점수)를 의미한다. (학습 데이터에 대해서는 좋은 점수, 검증 데이터로는 안좋은 점수.)

 

Following the principles of stochastic modeling, we propose a method to construct tree-based classifiers whose capacity can be arbitrarily expanded for increases in accuracy for both training and unseen data.

의사결정 나무를 확률적 모델링의 원칙에 따라 만드는 새로운 방법을 제안합니다. 이 방안은 학습 데이터와 검증 데이터 모두에 대해 정확도를 올릴 수 있게 처리량(capacity)를 임의적으로 올릴 수 있습니다.

 

The essence of the method is to build multiple trees in randomly selected subspaces of the feature space.

그 방안이라 함은 모델을 만들 때 column과 row를 랜덤으로 다르게 선택해 여러 개의 의사결정나무를 만드는 것입니다.

 

Trees in different subspaces generalize their classification in complementary ways, and their combined classification can be monotonically improved.

다른 column, row로 학습한 의사결정나무 모델들은 서로 보완하여 일반화 가능한 결과를 내고 통합 성능 또한 개선할 수 있습니다.

 

The validity of the method is demonstrated through experiments on the recognition of handwritten digits.

이 방법은 손글씨 데이터 셋으로 여러 실험을 진행함으로써 유효성 확인을 진행하였습니다.

 

 

 

Introduction

 

Decision-tree classifiers are attractive because of their many advantages

- the idea is intuitively appealing, training is often straight-forward, and best of all, classification is extremely fast.

의사결정나무 모델은 다음과 같은 장점이 있습니다.

- 직관적이기 때문에 해석하기 용이합니다, 학습 시키는 것이 단순합니다. 그리고 무엇보다도 속도가 빠릅니다.

 

They have been studied extensively in the past two decades and used heavily in practical applications.

지난 20년 간 광범위하게 연구되고 실용적인 분야에 많이 쓰였습니다.(95년도 기준)

 

Prior studies include many tree construction methods [3] [14] [15] and, recently, relationship to other classifiers like HMM methods [8] and multi-layer perceptrons [la].

기존 연구에서는 의사결정 나무를 만드는 다양한 방법이 논의되었고[3] [14] [15], 최근에는

HMM[8] 이나 딥러닝[la]과 같은 다른 예측모델과의 관계가 활발히 연구됩니다.(95년도 기준)

 

Many studies propose heuristics to construct a tree for optimal classification accuracy or to minimize its size.

많은 연구에서 정확도를 높이거나 용량을 줄이기 위해 제안하는 방법은 나무를 만들기 위해 이용할 수 있는 직관적인 판단기준(휴리스틱, 대충 어림짐작)입니다.

 

Yet trees constructed with fixed training data are prone to be overly adapted to the training data.

하지만 훈련 데이터 하나로만 만든 의사결정 나무 모델은 과적합(overfit, 학습 정확도와 검증 정확도의 큰 차이 발생)되기 쉽습니다.

 

Pruning back a fully-grown tree may increase generalization accuracy on unseen data, often at the expense of the accuracy on the training data.

pruning(가지치기) 방법을 이용하면 일반화를 달성(학습, 검증 데이터 예측 정확도 차이가 낮다) 할 수 있겠으나 보통은 학습 데이터에 대한 예측 정확도를 희생해야 합니다.

 

Probabilistic methods that allow descent through multiple branches with different confidence measures also do not guarantee optimization of the training set accuracy.

branch 만들 때 신뢰도 수치로 확률적 경사하강법을 적용하는 경우도 있는데 이 방법 또한 검증 데이터 셋에 대한 최적화를 보장할 수 없습니다.

 

Apparently there is a fundamental limitation on the complexity of tree classifiers - they should not be grown too complex to overfit the training data.

의사결정나무의 복잡성에는 근본적인 제한이 있는 것으로 보입니다. - 훈련 데이터에만 과적합이 되기 때문에 너무 복잡도가 올라가면 안됩니다.

 

No method is known that can grow trees to arbitrary complexity, and increase both training and testing set accuracy at the same time.

의사결정 나무 모델의 복잡성을 임의로 지정하거나 훈련/검증 데이터 셋에 대한 정확도를 동시에 올리는 방안은 알려져 있지 않습니다.

 

Our study shows that this difficulty is not intrinsic to tree classifiers.

이 연구에서 우리는 이러한 문제점이 순수하게 알고리즘 자체에 있는 것이 아님을 보였습니다.

 

In this paper we describe a method to overcome this apparent limitation.

본 논문에서는 이러한 명백한 한계를 극복하기 위한 방안을 기술합니다.

 

We will illustrate the ideas using oblique decision trees which are convenient for optimizing training set accuracy.

우리는 이 개념 설명을 위해 oblique 방식의 의사결정나무를 사용할 것인데 이 방식은 학습 데이터 예측 정확도를 올리기 용이하기 때문입니다.

 

We begin by describing oblique decision trees and their construction, and then present the method for increasing generalization accuracy through systematic creation and use of multiple trees.

oblique 방식 의사결정 나무와 이를 어떻게 만들지 설명하는 것으로 시작할 것입니다. 그리고 이를 통해 의사결정 나무를 체계적으로 여러 개 만들어 사용해 일반화 정확도를 높이는 방법을 제시할 것입니다.

 

Afterwards, experimental results on handwritten digits are presented and discussed.

그 후, 손글씨 데이터 셋에 대한 이 예측 모델의 결과를 제시하고 논의합니다.

 

 

 

Conclusion

 

We have proposed a method for increasing generalization accuracies of decision tree-based classifiers without trading away accuracy on training data.

이 연구에서는 훈련 데이터에 대한 정확성을 낮추지 않으면서 일반화 정확도를 올릴 수 있는 (학습 정확도와 검증 정확도의 차이가 작고 평균치가 높으면 일반화 정확도가 높다고 합니다. overfit 발생하지 않았다는 말과 동일합니다.) 방법을 제안하였습니다.

 

Experiments on handwritten digits proved the validity of the idea and indicated many opportunities for further improvements.

손글씨 분류 데이터 셋에 대한 실험을 통해 연구에서 다룬 아이디어의 타당성을 입증했으며 더욱 개선할 여지 또한 확인하였습니다.

 

The method we have presented here is another variant of the methodology of stochastic modeling that has been studied in both theory and experimentation recently [l] [7] [9] [lo] [ll].

이 연구에서 제시하는 방법은 최근 이론과 실험 분야 모두에서 연구중인 확률적 모델링 방법론을 약간 변형한 것입니다. [l] [7] [9] [lo] [ll].

 

The current method is in closest resemblance with the method of multiple LVQbased classifiers studied in [7].

현재 논문에서 다루는 방법론은 [7]에서 연구된 여러 LVQ 기반 분류기와 가장 유사합니다.

 

Both methods involve creating (with certain application of randomization) and combining multiple ways of partitioning the feature space.

두 가지 방법 모두 특징 공간(feature 조합)을 분할하는(조합을 찾는) 여러 가지 방법을 결합하는(랜덤으로 feature 추출) 개념을 공유하고 있습니다.

 

The decision regions determined by these partitions are stochastic models, the subject of study in [l] and [lo].

이러한 파티션에 의해(feature 조합이 다르면 다른 partition) 결정된 결정 영역은 확률적 모델(랜덤으로 조합을 추출하므로)이며 [l] 및 [lo]의 연구 대상이기도 합니다.

 

One of the main conclusions from the theory is that the apparent conflict between optimizing training set accuracy and maintaining generalization accuracy is not intrinsic.

이 연구이론의 주요 결론 중 하나는 학습 정확도가 올라가면 보통 검증 정확도가 낮아지는 상황은 의사결정나무 알고리즘 자체적으로 근본적인 문제가 아니라는 것입니다.

 

We have given another piece of empirical evidence of this finding.

이 발견에 대해 또 다른 경험적 증거를 제시하였습니다.

 

Our experimentation has also revealed great potential of applying the concepts of stochastic modeling to conventional methods for classifier design.

우리 연구는 또한 기존의 분류 알고리즘 설계 방법에 확률적 모델링의 개념을 적용할 수 있는 가능성을 제시합니다.

 

 

 

기업 출장강의 문의 : 1990ykm@gmail.com

 

강의분야 :

파이썬 기초

데이터 분석을 위한 파이썬

데이터 사이언스

 

 

역자 약력:

(전) 영어 어학병

2010.08, 2011.08 UFG 한미연합훈련 통번역

2011.02, 2012.02 KR/FE 한미연합훈련 통번역

 

(전) ASML(HMI)

반도체 전자현미경 엔지니어 

 

(현) E사

데이터 사이언스 연구원

 

(현) KGITBANK

파이썬 / 데이터 사이언스 강사

 

자격 / 시험:

Dell Proven Professional - EMCDS Data Scientist - Specialist

Huawei H13-731 - HCIE Big Data - Data Mining

Huawei H13-311 - HCIA-AI