논문 정보

원문 파일
   
저자 Li, Ruey-Hsia
학위 Ph.D.
학위수여대학 University of Illinois at Urbana-Champaign.
수여년도 2001
페이지수 86 p.
지도교수/심사위원 Adviser: Geneva G. Belford.
언어 영어
주제어 Computer Science
초록
  Fundamental theorems are derived for the instability problem of decision tree classification algorithms. The instability problem of decision tree classification algorithms is that small changes in input training samples may cause dramatically large changes in the output tree classifiers. The past research emphasized the instability of the prediction but not the tree structure change, which is more important to provide consistent, stable, and insightful information to facilitate the process of decision making.
  We present theorems to prove the relationship between a data change and the resulting tree structure change (i.e., split change). The relative sensitivity between two splits is defined based on the theorems as the smallest change that may cause the superior split to become inferior. A split is defined to be almost as good as another split if the relative sensitivity of the two splits is small. The Instability Theorem provides the cause of the instability problem. Algorithms are presented to lessen the instability problem.
  Empirical results illustrate that the trees constructed by the proposed algorithm are more stable, noise-tolerant, informative, expressive, and concise. The proposed sensitivity measure can be used as a metric to evaluate the stability of splitting predicates. The tree sensitivity is an indicator of the confidence level in rules and the effective lifetime of rules.

사용자 삽입 이미지
신고
by 에이아이 2009.08.24 18:42
논문설명

대표적인 의사결정트리 알고리즘으로 널리 알려져 있는 C4.5 알고리즘의 책에 대한 Review 자료입니다.  
데이터마이닝을 연구하는 경우 읽어두면 도움이 될 유용한 자료라고 생각됩니다.

논문정보

 원본파일

 검색방법 

http://www.springerlink.com/content/v986m1562062hk51/

 출처정보

Quinlan, J. R. (1993). C4.5 programs for machine learning. Morgan Kaufman.  


                      Review : C4.5 programs for machine learning

1. Overview (개관) 

Algorithms for constructing decision trees are among the most well known and widely used for all machine learning methods. Among decision tree algorithms, J. Ross Quinlan's ID3 and its successor, C4.5, are probably the most popular in the machine learning community.
결정트리를 구축하는 알고리즘들은 기계학습 방법들 중에서도 가장 잘 알려져있고 널리 사용되는 있는 방법들에 속해있다. 결정트리 알고리즘 중에서도, J. Ross Quinlan 의 제안한 ID3와 그 후속 알고리즘인 C4.5 은 아마도 기계 학습 분야에서 가장 인기있는 방법들일 것이다.

These algorithms and variations on them have been the subject of numerous research papers since Quinlan introduced ID3. Until recently, most researchers looking for an introduction to decision trees turned to Quinlan's seminal 1986 Machine Learning journal article [Quinlan, 1986].
이 알고리즘과 이로부터 발전된 알고리즘들은 Quinlan 이 ID3 알고리즘을 소개한 이후로 수많은 연구논문들의 주제가 되어왔다. 대부분의 결정트리를 소개하는 연구들은 Quinlan 이 1986년 기계학습 저널의 논문을 참고하고 있다.

In this book, C4.5: Programs for Machine Learning, Quinlan has put together a definitive, much needed description of his complete system, including the latest developments. As such, this book will be a welcome addition to the library of many researchers and students.
이 책(C4.5 기계학습을 위한 프로그램)에서, 저자 Quinlan은 (가가 최근에 개발한 내용을 포함하여) 그의 완전한 시스템에 대한 명확하고 더욱 자세한 설명들을 종합하였다. 때문에, 이 책은 많은 연구자들과 학생들에게 환영받는 추가자료가 될 것이다.  

Quinlan discusses a wide range of issues related to decision trees, from the core alorithm for building an initial tree to methods for pruning, converting trees to rules, and handling various problems such as missing attribute values. For each of these issues, he gives a clear description of the problem, usually accompanied by an example, and he describes how C4.5 handles it. The detailed examples are usually drawn from real data sets, and they help greatly to illustrate each problem.
Quinlan은 결정트리에 관련된 (결정트리를 생성하는 중심 알고리즘부터 가지치기의 방법들, 나무를 규칙으로 변환하는 방법, 결측치와 같은 여러가지 문제들을 다루는 방법 등) 넓은 영역의 이슈들에 대해서 다룬다. 각각의 이슈들에 대해서 Quinlan은 주로 예제들을 사용하여 문제들을 명확하게 기술하고, C4.5에서 그 문제들을 처리하는 방법을 설명한다. 자세한 예제들은 주로 실 데이터에서 가져왔으며, 각 문제들을 설명하는데 많은 도움을 준다.  


2. Summary of contents (내용 요약) 

Decisioin tree algorithms begin with a set of cases, or examples, and create a tree data structure that can be used to classify new cases. Each case is described by a set of attributes (or features) which can have numeric or symbolic value. Associated with each training case is a label representing the name of class. Each internal node of a decision tree contains a test, the result of which is used to decide what branch to follow from that node.

For example, a test might ask "is x > 4 for attribute x?" If the test is true, then the case will processd down the left branch, and if not then it will follow the right branch. The leaf nodes contains class labelss instead of tests. In classification mode, when a test case (which has no label) reaches a leaf node, C4.5 classifies it using the label stroed there.

신고
by 에이아이 2009.07.31 22:17

대학졸업생들을 대상으로 설문하여 CHAID 분석을 수행한 논문입니다.

Answer Tree 프로그램을 사용하여 분석을 수행하였고,
자격증, 해외연수, 취업준비여부 등이 취업에 미치는 영향을 결정트리로 분석한 자료입니다.  

 
 

신고
by 에이아이 2009.07.29 18:30

의사결정트리에 대한 논문을 하나 소개합니다.
KISS 학술원문데이터베이스(kiss.kstudy.com)에서 검색하여 찾은 논문입니다.

1999년에 발표된 좀 오래된 논문이기는 하지만
CHAID 알고리즘과 CART 알고리즘을 자세하게 소개하고 있고,
두 방법의 차이점에 대해서도 이론 및 실제 데이터에 대한 적용 결과를 가지고 자세히 설명하고 있습니다.

논문 정보는 아래와 같습니다.

제목 : Data Mining : 의사결정트리 알고리즘의 성과 비교에 관한 연구 상세보기 
저자 : 김신곤(광운대학교 경영정보학과), 박성용(동양 Systemhouse)
년도 : 1999년
학회 : 한국경영정보학회 (춘계학술대회, Vol.1999, No.0,   Startpage 371, Endpage 383, Totalpage 13)
ECN : ECN-0102-2009-320-005682012  

원문 PDF 

 


신고
by 에이아이 2009.07.29 17:48

다중공선성의 효과와 해결책(회귀분석에서의)에 대한 논문입니다.
KISS 학술원문데이터베이스(kiss.kstudy.com)에서 검색하여 찾은 논문입니다.
(검색어는 "공선성" 으로 하여 검색하였습니다.)

1994년도에 발표된 논문으로
상호작용, 다중공선성에 대한 효과에 대해서 통계적, 수학적으로 자세하게 설명하고 있습니다.
또한 통계학 분야에서 다중공선성을 처리하는 여럭가지 방법들에 대해서 설명하고 있습니다.
(소집단 분석, 독립화 변환, 평균변환 등의 방법을 제시하고 이들을 비교하였습니다.)

논문 정보는 아래와 같습니다. 

제목 : 상호작용효과를 포함한 다중회귀분석에서 주효과의 검증에 대한 연구 상세보기
         Testing Main Effects in Interactive Multiple Regression
저자 : 이유재(서울대),  년도 : 1994년  
학회 : 한국경영학회
발행 : 경영학연구, Vol.23, No.4,   Startpage 183, Endpage 210, Totalpage 28
ECN : ECN-0102-2008-320-001032625
 

원문 PDF

 

 


 

신고
by 에이아이 2009.07.29 12:24

다중공선성의 효과와 해결책(회귀분석에서의)에 대한 참고 논문입니다.
KISS 학술원문데이터베이스(kiss.kstudy.com)에서 검색하여 찾은 논문입니다.
(검색어는 "공선성" 으로 하여 검색하였습니다.)

1993년도에 발표된 논문으로
다중공선성의 문제를 해결하는 하나의 방법은 Ridge Regression(능형회귀)에서의
k를 선택하는 방법에 대해서 설명하고 있습니다.
수식이 많고 통계지식이 부족하여 잘 이해를 못하겠네요. 나중에 다시 읽어봐야겠습니다. 

논문 정보는 아래와 같습니다.

 제목 : 능형회귀에서의 로버스트한 k 의 선택 방법 상세보기  
          Robust Selection Rules of k in Ridge Regression
 저자 : 임용빈(이화여대 통계학과),  년도 : 1993년  
 학회 : 한국통계학회
 발행 : 응용통계연구, Vol.6, No.2,   Startpage 371, Endpage 381, Totalpage 11
 ECN : ECN-0102-2008-310-002450607

원문 PDF



신고
by 에이아이 2009.07.29 12:19

다중공선성의 효과와 해결책(회귀분석에서의)에 대한 논문입니다.

KISS 학술원문데이터베이스(kiss.kstudy.com)에서 검색하여 찾은 논문입니다.
검색어는 "공선성" 으로 하여 검색하였습니다. "다중공선성"으로 검색하면 이상하게도 [다중공선성] 단어가 포함된 논문이 검색되지 않네요. 좀 문제가 있는듯...

2006년도에 발표된 논문으로
다중공선성으로 인한 해결방법으로 많이 사용되고 있는
능형회귀분석(OLS) 및 주성분회귀분석(PCR) 에 대해서 자세하게 설명한 자료입니다.  

논문 정보는 아래와 같습니다.

제목 : 자연과학편 : 다중공선성 상태의 주성분회귀와 능형회귀 상세보기  
          Principal components regression and ridge regression under the multicollinearity
저자 : 김진욱(고려대),  년도 : 2006년  
학회 : 한국체육학회
         (한국체육학회지-인문사회과학, Vol.45, No.4s,   Startpage 547, Endpage 556, Totalpage 10)
ECN : ECN-0102-2009-690-000419594


원문파일


 

신고
by 에이아이 2009.07.29 12:13
by 에이아이 2009.07.29 12:09

다중공선성에 견고한 결정트리를 연구하면서 참고한 논문이다.

ID3 계열의 결정트리 알고리즘들은 다중공선성에 견고하지 못한 문제가 있다.
반면, 신경망 알고리즘은 다중공선성에 영향을 받지 않는 유연함의 장점을 갖고 있다.


결정트리는 모델을 이해하기 쉽고 의사결정에 적용하기 쉬운 장점을 갖는다.
반면, 신경망은 일반적으로 결정트리 보다 높은 성능(예측/분류 정확도)의 장점을 갖는다.
본 논문에서는 이 두 장점을 모두 취하는 것을 목표로 한다. 

본 논문의 아이디어는
신경망 모델을 학습한 후 그 모델로 부터 결정트리를 생성해내는 방법에 대한 연구이다.
신경망 모델로 부터 생성된 결정트리 모델은
기존의 결정트리보다 다중공선성 등의 데이터 특성에 견고한 장점을 갖는다고 주장한다.

신고
by 에이아이 2009.07.29 12:03

논문설명

아래의 논문은 [다중공선성에 견고한 결정트리 연구]에 대한 참고 논문이다.

결정트리에서의 다중공선성의 영향과 해결책에 대한 기존 연구는 많지 않은 상황인데, 이 논문이 좋은 참고자료가 되었다. 이 논문에서는 다중공선성을 포함하여 4개의 특성이 결정트리에 미치는 영향을 실험을 통하여 검증하였다. 회귀분석에서 사용하는 다중공선성 해결방법이 결정트리에 동일하게 적용되지 않는 점을 보였다. (상관성이 높은 변수를 제거한다고 결과 모델이 더 좋아지지는 않았다.)

논문정보

 원본파일

 검색방법 

http://www.sciencedirect.com/science/journal/09574174검색어에 [Input Data for Decision Trees]를 입력검색

 저널정보

저널 : Expert Systems with Applications
상세 : 34권 (2008년) 1220-1226 페이지
자세히보기

 저자정보

저자 : Selwyn Piramuthu
대학 : Decision and Information Science University of Florida, Gainesville, FL 32611-7169, United States

 분석자료
 (2009/ 2/ 8)

제목

 Input Data for Decision Trees

0. Abstract (서론) 

Data Mining has been successful in a wide variety of application areas for varied purposes. Data Mining itself is done using several different methods. Decision Trees are one of the popular methods that have been used for Data Mining purposes. Since process of constructing these decision trees assume no distributional patterns in the data (non-parametric), characteristics of the input data are usually no given much attention. 데이터마이닝은 다양한 응용분야에서 다양한 목적으로 성공적으로 사용되고 있다. 데이터마이닝은 여러가지 다른 분석 방법들을 사용하고 있다. 특히 결정트리는 데이터마이닝 분석에서 사용되고 있는 인기있는 분석 방법 중의 하나이다.  결정트리를 생성하는 과정은 데이터의 분포에 대한 가정을 하지 않기 때문에 (즉, 비모수 분석이기 때문에) 입력 데이터의 특성에는 보통 주의를 기울이지 않는다.

We consider some characteristics of input data and their effect on the learning performance of decision trees. Preliminary results indicates that the performance of decision trees can be improved with minor modifications of input data. 본 연구에서는 입력 데이터의 몇 가지 특성들을 고려하고 이 특성들이 결정트리의 학습 성능에 어떠한 영향을 미치는지를 고려한다. 기존 연구의 결과에서는 결정트리의 성능이 약간의 입력 데이터의 수정을 통하여 향상될 수 있음을 보여준다.

* preliminary : http://endic.naver.com/endic.nhn?docid=896810&rd=s   준비의, 시초의  

1. Introduction

Data Mining has been successful in a wide variety of application areas, including marketing, for varied purposes (Adomavicius & Tuzhinlin, 2001; Kushmerick, 1999; van der Putten, 1999; Shaw, Subramaniam, Tan, & Welge, 2001; Thearling, 1999). Data Mining itself is done using several different methods, depending on the type of data as well as the purpose of Data Mining (Ansari, Kohavi, Mason & Zheng, 2000; Cooley & Tan, 2000). For example, if the purpose is classification using real data, feed-forward neural networks might be appropriate (Ragavan & Piramuth, 1991). Decision trees might be appropriate if the purpose is classification using nominal data (Quinlan, 1993). Further, if the purpose is to identify associations in data, association rules might be appropriate (Brijs, Swinnen, Vanhoof, & Wets, 1999).
데이터마이닝은 다양한 목적으로 마케팅을 포함한 여러 분야에서 널리 성공적으로 사용되어지고 있다. 데이터마이닝은 분석을 수행하는 목적과 데이터의 종류에 따라서 여러가지 다른 방법들을 사용하여 수행된다. 예를 들어, 수치형 데이터를 사용한 분류가 목적이라면, 신경망 알고리즘이 적합할 것이다. 결정트리는 범주형 데이터에 대한 분류를 목적으로 하는 경우에 적합하다. 더 나아가, 데이터의 연관성을 규명하는 것이 목적이라면 [연관규칙탐사 분석] 이 적합할 것이다.

Decision Trees are one of the popular methods that have been used for Data Mining purporses. Decision trees can be constructed using a variety of methods. For example, C4.5(Quinlan, 1993) uses information-theoretic measures and CART (Breiman, Friedman, Olshen, & Stone, 1984) uses statistical methods.
결정트리는 데이터마이닝 목적에서 인기있는 분석 방법 중의 하나이다. 결정트리는 다양한 방법들을 사용하여 생성될 수 있다. 예를 들어, 1993년 Quinlan에 의해 제안된 C4.5 알고리즘은 정보이론 측정법을 사용하고, 1984년 Breiman 등에 의해 제안된 CART 알고리즘은 통계적인 방법들을 사용한다.

The usefulness as well as classification and computional performance of Data Mining frameworks incorporating decision trees can be improved by (1) appropriate preprocessing of input data, (2) fine-tuning the decision tree algorithm itself, and (3) better interpretation of output. There have been several studies that have addressed each of these scenarios.
결정트리를 포함한 데이터마이닝 프레임워크에서 분류 및 계산 성능 뿐 아니라 유용성 등은 다음의 여러가지 방법들에 의해 개선될 수 있다. 아래의 각 시나리오를 주제로 하는 다양한 연구들이 이루어지고 있다.

(1) 입력데이터에 대한 적절한 전처리
(2) 결정트리 알고리즘 자체를 개선
(3) 분석 결과를 해석하는 방법의 개선

Input data can be preprocessed (1) to reduce the complexity of data for ease of learning, and(2) to reduce effects due to unwanted characteristics of data.
입력 데이터는 다음의 방법들을 전처리될 수 있다.
(1) 학습과정의 편리화를 위해, 데이터의 복잡도를 감소하는 것.
(2) 원하지 않는 데이터의 특성에 의한 효과를 감소시키는 것.

The former includes such techniques as feature selection and feature construction as well as other data modifications (see, for example, Brijs & Vanhoof, 1998; Kohavi, 1995; Ragavan & Piramuthu, 1991). The latter includes removal of noisy, redundant, and irrelavant data used as input to decision tree learning.
전자(1)는 변수의 선택, 변수의 생성 기술 그리고 그 외에 데이터를 변경하는 방법들을 포함한다. 후자(2)는 결정트리 학습을 위하여 노이즈 및 중복되었거나 부적합한 데이터를 제거하는 기술이 포함된다.  

We consider some characteristics of input data and its effect on the learning performance of decision trees. Specifically, we consider the effects on non-linearity, outliers, heteroschedaticity, and multicollinearity in data. These have been shown to have significant effects on regression analysis. However, there has not  been any published study that deals with these characteristics and their effects on the learning performance of decision trees. Using a few small data sets that are available over the Internet, we consider each of these characteristics and compare their effects on regression analysis as well as decision trees.
본 연구에서는 입력 데이터의 몇 가지 특성들과 그 특성들이 결정트리의 학습 성능에 미치는 영향에 대해서 고려한다. 특별히, 비선형성, 이상치, 등분산성, 다중공선성 특성에 대해서 고려할 것이다. 이들 특성들은 회귀분석에서 상당한 영향을 주는 특성들로 밝혀져있다.  그러나 이들 특성들이 결정트리의 학습 성능에는 어떠한 영향을 미치는 지에 대해 발표된 연구는 거의 없다. 본 연구에서는 인터넷에서 얻을 수 있는 몇개의 작은 데이터셋을 사용하여 언급한 특성들을 고려하고 결정트리에서 이들 특성들의 영향을 비교할 것이다. (?)  


The result from regression analysis are from the Internet. The contribution of this paper is in studying the effects of these characteristics on decision trees, specially See-5 (2001). Preliminary results suggest that the performance of decision trees can be improved with minor modification of input data.
회귀분석에서의 결과는 인터넷을 통해 얻었다. 본 연구의 다루는 내용은 결정트리(특히, See-5)에서 이들 특성들의 효과를 연구하는 것이다. 선행연구의 결과는 입력 데이터의 약간의 수정을 통하여 결정트리의 성능이 향상될 수 있다는 것을 보여준다.    

The rest of the paper is organized as follows : Evaluation of some input data characteristics and their effects on the learning performance of decision trees is provided in the next section. Experimental results are also included in Section 2. Section 3 concludes the paper with a brief discussion of the results from this study and their implications as well as future extensions to this study. 본 논문의 나머지 부분은 다음과 같이 구성되었다. 다음 장(2장)에서는 몇 개의 입력 데이터의 특성과 이들의 결정트리 학습 성능에 대한 효과를 평가할 것이다. 2장은 실험의 결과 또한 포함하고 있다. 3장에서는 본 연구의 결과에 대한 간단한 토의내용과 향후 연구에 대해서 제시한다.  


1장 정리

본 논문의 1장에서는 데이터마이닝 및 결정트리에 대한 개략적인 설명을 하고 있다. 다음의 4가지 데이터의 특성이 회귀분석 뿐 아니라 결정트리에도 영향을 미치는 것을 언급하고 있다.

(1) 비선형성 (2) 이상치 (3) 등분산성 (4) 다중공선성

이들 특성들이




2. Evaluation of input data charcteristics for decision trees

Traditional statistical regression analysis assumes certian distribution (e.g., Gaussian) of input data, as well as other characteristics of data such as the data being independent and identically distributed.
전통적인 통계학의 회귀분석 기법은 특정한 입력 데이터 분포(예를들어, 가우시안 분포)를 가정하고 있다.

In most real world data, some of these assumtions are often violated. And, there are several means to at least partially rectify some of the consequences that arise from these violations. We consider a few of these situations: non-linearity in the data, the presence of outliers in the data, the presence of heteroschedacity in the data, and the presence of multicolliearity in the data. The data sets used in this study are known to have these charateristics. The following subsections address each of these scenarios in turn. We use See-5 as the decision tree generator throughout this study.
그 외에도 변수들의 독립성, 균등분포 등의 데이터 특성들을 가정한다. 그러나 대부분의 실 세계의 데이터에서는 이러한 가정들은 위배된다. 그리고, 이러한 위배를 통해 발생되는 결과(문제)들을 수정하기 위한 여러가지 방법들이 존재한다. 본 연구에서는 이들 상황 중 다음의 4가지를 고려한다. 4가지는 입력데이터의 비선형성, 이상치데이터, 등분산성, 다중공선성 이다. 본 연구에서 사용한 데이터셋은 이들 특성들을 갖는 것으로 알려져있다. 본 장에 나머지 부분에서는 차례대로 이들 시나리오의 각각에 대하여 해결책을 다루고 있다.
본 연구에서는 See-5 결정트리를 사용할 것이다.

* identially distributed : 동일하게 분포됨 (균등분포)
* rectify : 수정하다. 조정하다.
* address : 다루다. 처리하다. 초점을 맞추다.

2.1 Non-linearity in input data

Non-linearity is a problem in linear regression simply because it is hard to fit a linear model on a non-linear data. Therefore, non-linear transformations are made to the data before runing regressions on these data. We consider the effects of non-linear data on decision trees both before and after the appropriate data transformations are made. 비선형성은 선형 회귀분석에서 나타나는 단순한 문제로써, 비선형 데이터를 선형 모델을 적합 시키기 어렵기 때문에 발생한다. 그러므로, 이 데이터를 회귀분석에 수행하기에 앞서 먼저 비선형 변형을 수행한다. 본 연구에서는 비선형 데이터에 대해 변형을 수행하기 전과 후 모두에 대하여 결정트리에 미치는 영향을 고려한다.

This data set contains four variables - the independent variables x1, x2, and x3 and the dependent variable y. Result using ordinary least squares(OLS) regression to predict y using x1, x2, and x3 are provided below. 이 데이터셋은 [x1, x2, x3]의 3개의 독립변수와 종속변수 y의 4개의 변수를 포함하고 있다. 결과는 OLS 회귀분석을 사용하여 x1, x2, x3를 사용하여 y를 예측한 회귀분석의 결과는 아래와 같다.  

The presence of higher order trend effects are indentified to be present in the data using the omitted varable test(ovtest with the rhs option in the stastistical analysis software Stata).
제거된 변수 실험을 통하여 높은 차수의 경향 효과가 존재할 때 이 존재할 때 변수를 제거하는 ...

Higher order trend effects are also present. On inspection of scatter plots of the data, the presence of non-linear trend patterns in the data in the variable x2 is confirmed. We substitute x2 with its centered (x2cent) value (i.e., substract its mean from every value) and the square (x2centsq) of the centered value.
높은 차수 경향 효과는 역시 존재한다. 데이터를 스케터 좌표에 표시해보면, 변수 x2 가 선형의 특성을 갖지 않는 것으로 보여진다. 우리는 x2를 x2cent 라는 변수와 x2centsq 라는 변수로 교체한다. x2cent 는 각 변수의 값에서 평균값을 뺀 값이고, x2centsq 변수는 중심값(centered value)의 제곱이다.    

The results from this regression are provoided below:
On further testing for higher order terms, the result turns out to be negative. Here, by including the squared term, it is shown that the new term is indeed statistically significant. The resulting model also fits the data better as shown by the increase in the R^2 value.
이 회귀분석의 결과를 아래에 제시하였다. 더 높은 차수에 대한 추가적인 실험에서 그 결과는 부정적인 것으로 밝혀졌다. 여기서, 제곱 항을 포함함으로, 새로운 항은 통계적으로 의미있다는 것을 보일 수 있었다. 또한 결과 모델은 R^2 값이 향상된 것을 볼 때 데이터에 더욱 잘 적합화된 것을 알 수 있다. 

Now, let us consider the same two sets of data, both before and after incorporating the squared term, and evaluate its effects on the performance of decision tree learned. We use 10-fold cross-validation in See-5 to reduce any bias due to sample selection. Both the mean values and the standard deviation values (in parentheses) are provoided for the resulting decision trees.  여기서 우리는 동일한 두 데이터를 고려하였다. 제곱 항을 추가하기 전과 후에 대해서, 학습된 결정트리의 성능에 어떠한 영향을 미치는 지를 평가하였다. 이 실험에서 실험 데이터 샘플을 선택하기 위하여 10-fold 교차검증의 방법으로 See-5 를 수행하였다. 평균이나 표준편차 값은 결정트리를 생성할 때 모두 사용하였다.  

Here (Table1), the addition of the two transformed x2 variables has resulted in a small reduction in the size of the decision trees and a significant decrease in the prediction error. The prediction error is the classification error on unseen (during generation of decision trees) examples.
표1 에서, 변형된 x2를 변형하여 추가한 방법이 결정트리의 크기를 축소하고 예측 에러를 감소시킨 결과를 가져온 것을 볼 수 있다. 예측 에러는 결정트리를 생성할 때 사용하지 않고 별도로 분리해두었던 테스트용 데이터에 대한 분류 에러이다.

2.2 Presence of outliers in input data


2.3 Heteroschedaticity in input data


2.4 Multicollinearity in input data  

Data where the independent variables are highly correlated is said to have multicollinearity. In regerssion analysis, multicollinearity is a problem when we are interested in the exact values of the coefficients of the independent valiables. 데이터의 종속변수들 간에 높은 상관관계가 존재할 때, 이 데이터에 대하여 다중공선성을 갖는다고 말한다. 회귀분석에서, 우리가 독립변수들의 회귀계수의 정확한 값에 관심을 가지고 있을 때 다중공선성이 문제가 된다.

When multicollinearity is present, this is not possible. Multicollinearity is identified by (1) the presence of high pairwise correlation among independent variables, (2) a high R^2 value with low t-statistics, and (3) the coefficients change when variables are added and dropped from the model.
다중공선성이 존재할 경우, 이것(회귀계수를 통해 해당 속성의 중요성을 찾는것)은 가능하지 않다. 다중공선성은 다음의 방법으로 확인될 수 있다.

(1) 독립변수들 사이에 두 변수들 간에 높은 상관성이 존재할 경우.
(2) R^2 값은 높은데 t-검정 값은 낮은 경우
(3) 모델에 변수들을 추가하거나 제거할 때 회귀계수의 변동이 크게 나타나는 경우

Multicollinearity is not a problem when the only poupose of regerssion analysis is forecasting. However, if the anlysis is to determine and evaluate the coefficients, multicollinearity is a problem.
회귀분석의 목적이 예측일 경우 다중공선성을 문제가 되지 않는다. 그러나 회귀계수의 값을 선정하고 평가하고자 할 때 다중공선성은 문제가 된다.

One of the ways to alleviate this problem is to drop the variable with highest pari-wise correlation values among the independent variables. We consider the effects of multicollinearity on decision trees both before and after the problem has been alleviated in the input data.
이 문제를 완화하는 하나의 방법은 서로 간에 상관성이 높은 독립 변수들 중에서 하나의 변수를 제거하는 것이다. 우리는 입력데이터에서 완화되기 전과 후에 대해서 결정트리를 생성할 때 다중공선성이 미치는 영향에 대해서 고려하고자 한다.

* alleviate : 덜다, 완화하다, 경감하다, 편하게 하다.

This data set contains five variables - the independent variables x1, x2, x3, and x4 and the dependent variable y. Result using OLS regerssion to predict y using x1, x2, x3, and x4 are provoided below.
이 데이터는 (x1, x2, x3, x4) 4개의 독립변수와 종속변수 y의 다섯 개의 변수로 구성되어 있다. 4개의 독립변수를 사용하여 y를 예측한 OLS 회귀분석의 결과를 아래에 제시하였다. 


Here, the R^2 value is significant while the t-statistics are not. We then consider the pair-wise correlations among the independent variables. The resulting matrix is given below:
여기서, R^2 값은 유의미하지만, t-검정값은 그렇지 않다. 우리는 독립 변수들 간의 (두 변수들 간의 쌍으로) 상관성을 고려하였다. 결과는 아래의 매트릭스에 제시하였다.

Clearly, x4 is highly correlated with the rest of the independent variables. This variable is then removed from the data. The result form the OLS regression run without x4 is given below: Here, all the varibales turn out to be significant.
명백하게, x4 는 다른 나머지 독립변수들(x1,x2,x3)와 높은 상관관계를 갖는 것을 볼 수 있다. 이 변수(x4)를 데이터에서 제거하였다. 제거한 후의 데이터를 OLS 회귀분석 수행한 결과를 아래에 제시하였다. 여기서, 모든 변수들이 유의미한 것으로 판명되었다.

Now, let us consider the same two of data, both before and after removing x4 form the data, and evaluate its effects on the performance of decision tree learned. Again, we use 10-fold cross-validation in See-5 to reduce any bias due to sample selection.
이제, x4 변수를 제거하기 전과 제거한 후 모두에 대하여 결정트리를 학습할 때 미치는 영향에 대해서 평가해보았다. 이전 실험과 같이 변수 선택으로 인한 편향(bias)를 제거하기 위하여 10-접기 교차검정 방법으로 See-5 분석을 수행하였다.  


Here (Table4), the transformation of the dependent varibale has resulted in a significant in the size of the decision trees and a significant increase in the prediction error. Here, removal of the variable does not seem to help the performance of decision trees.
표4 에서, 독립변수들의 변환은 결정트리의 크기를 증가시키고 예측 에러를 증가시킨다는 것을 보여준다. 이 실험의 결과는, 변수를 제거하는 것은 결정트리의 성능을 향상시키는데 도움을 주지 못한다는 것을 보여준다.  

2.5 Data reduction  


3. Discussion

Even though decision trees constructed using information-theoretic measures are considered non-parametic, the distribution of data does influence the classification performance of these decision trees. Preliminary results indecate that the performance of decision trees can be improved by considering the effects due to non-linearity, outliers, heteroschedacity, and multicollinearity in input data as well as data reduction.
정보이론 측정법을 사용하여 생성되는 결정트리 비모수적으로 고려됨에도 불구하고, 데이터의 분포는 결정트리를 사용한 분류의 성능에 영향을 미친다. 기존 연구에서는 입력데이터를 차원축소하는 등의 방법으로 비선형성, oulier, 비-등분산성, 다중공선성에 의한 영향을 고려하면 결정트리의 성능을 향상시킬 수 있다고 보고 있다.

Both non-linearity and the presence of outliers did affect the classification performance of decision trees. The Presence of heteroschedaticity did not affect the classfication performance of decision trees significantly. The attempt to remove multicollineartiy resulted in poor classification performance. Data reduction resulted in improved performance both in terms of the resulting tree-size and classification.
비선형성과 이상치의 존재는 결정트리의 분류 성능에 영향을 줬다. 반면, 등분산성의 존재는 결정트리의 분류 선능에 영향을 주지 않았다. 그리고 다중공선성의 존재는 결정트리에서 신경을 쓰지 않아도 된다. 다중공선성을 제거하고자하는 시도는 오히려 분류 성능을 낮추는 결과를 낳았다. 데이터 축소는 나무의 크기 및 분류의 측면에서 성능을 향상시키는 효과가 있었다.  
(회귀분석에서는 높은 상관성이 있는 변수 중 하나를 제거하여 해결하지만, 결정트리의 경우는 그것이 해결책이 되지 않는것으로 보여진다. 최소한 이 실험만으로 볼때는 그렇다.)

We are currently in the process of evaluating the results we have thus far using larger and more data sets. We are also in the process of studying why these data chacteristics affect the classification performance of decision trees. Also, in this study, we were only interested in the size of the decision tree and their classification accuracy. The computational cost of this process is also important, and that is left as an exercise of a future study. In addition to the characteristics presented in this paper, we are also evaluating other data characteristics including non-independent and non-normality of data.
우리는 더 크고 많은 데이터셋을 사용하여 얻은 실험 결과들을 평가하는 과정 중에 있다. 또한 제시한 데이터의 특성들이 왜 결정트리의 분류 성능에 영향을 주는지에 대해서 연구하는 과정 중에 있다. 본 연구에서 우리는 나무의 크기 및 분류 정확도에 대해서만 관심을 가졌었다. 이러한 작업의 계산 비용 또한 중요하며, 이 문제는 향후 연구에서 진행하고자 한다. 추가로 본 논문에서 제시한 데이터의 특성들 외에 결정트리 성능에 영향을 미치는 특성들(비독립성, non-normality를 포함한)도 평가를 하고 있다.  

We presented one possible means to improve the classification performance of decision trees. This, along with other pre-processing methods (such as feature selection and feature construction), methods for fine-tuning decision trees, and those that enhance interpretability of results, would help improve the overall performance of these decision support tools incorporating decision trees.
우리는 결정트리의 분류 성능을 향상 시키기 위한 방법들을 제시하였다. 결정트리 분석에 변수선택, 변수생성등의 전처리 방법들 그리고 결과에 대한 해석력을 강화하는 방법들을 결합하다면 결정트리의 전반적인 성능을 향상시킬 수 있을 것이다.  

4. References

[1] Adomavicius, G., & Tuzhilin, A. (2001). Using data mining methods to build customer profiles.
     IEEE Computer (Februray), 74-82.

[2] Anderson, E. (1935). The Irises of the Gaspe Peninsula. Bulletin of the American Iris Society,
     59, 2-5.  

[3] Ansari, S., Kohavi, R., Mason, L., & Zheng, Z. (2000). Integrating E-commerce and data mining:
     architecture and challanges. WEB-KDD'2000 workshop on Web mining for E-commerce -
     challanges and opportunities, August.  


신고
by 에이아이 2009.07.29 11:49
| 1 2 |