반응형
목차
의사결정나무
1.의사결정나무란
2.불순도와 확실성
3.여러 가지 의사결정나무 알고리즘
4.의사결정나무 분석 과정
5.의사결정나무 생성 함수
6.의사결정나무 예시
1.의사결정나무란
우리가 관심을 가지는 분류 문제를 해결하기 위해 매우 강력하고 유용한 데이터 마이닝 알고리즘이다. 이 알고리즘은 분류를 하기 위한 목표 변수에 영향을 줄 수 있는 입력 변수들을 이용해 최적의 분류를 위한 의사결정 규칙을 생성하는데, 의사결정 규칙을 트리 구조로 나타내준다. 즉, 의사결정 규칙을 나무 구조로 나타내어 전체 자료를 몇 개의 소집단으로 분류(classification)하거나 예측(prediction)을 수행하는 분석방법이다.(범주, 연속형 수치 모두 예측 가능)
트리구조는 연속적으로 발생하는 의사결정 문제를 시각화해 의사결정이 이뤄지는 시점과 성과를 한 눈에 볼 수 있게 한다.
1)분류 분석(classification)과 예측 분석(prediction)
-공통점
: 레코드(튜플)의 특정 속성의 값을 미리 알아 맞힌다.
-차이점
--분류 : 레코드의 범주형 속성의 값을 알아 맞한다.
--예측 : 레코드의 연속형 속성의 값을 알아 맞힌다.
2)의사결정나무 구성
-뿌리마디(root node) : 시작되는 마디로 전체 자료를 포함
-자식마디(child node) : 하나의 마디로부터 분리되어 나간 2개 이상의 마디들
-부모마디(parent node) : 주어진 마디의 상위 마디
-끝마디(terminal node) : 자식마디가 없는 마디
-중간마디(intermediate node) : 부모마디와 자식마디가 연결된 마디들
-가지(branch) : 뿌리마디로부터 끝마디까지 연결되 마디들
-깊이(depth) : 뿌리마디부터 끝마디까지의 중간마디들의 수
3)의사결정나무의 특징
: 결과를 누구에게나 설명하기 용이하다.
: 모형을 만드는 방법이 계산적으로 복잡하지 않다.
: 대용량 데이터에서도 빠르게 만들 수 있다.
: 비정상 잡음 데이터에 대해서도 민감함이 없이 분류할 수 있다.
: 한 변수와 상관성이 높은 다른 불필요한 변수가 있어도 크게 영향 받지 않는다.
: 모형 분류 정확도가 높다.
장점 | 단점 |
해석의 용이성 - 나무구조로 표현되어 모형을 사용자가 쉽게 이해할 수 있다. | 비연속성 - 연속형 변수를 비연속적 값으로 취급하기 때문에 분리의 경계점 부근에서 예측오류가 클 가능성이 있다. |
교호작용효과의 해석 - 두 개 이상의 변수가 결합하여 목표변수에 어떻게 영향을 주는지 쉽게 알 수 있다. | 선형성 또는 주효과의 결여 - 선형모형에서는 주효과는 다른 예측변화와 관련시키지 않아도 각 변수의 영향력을 해설 할 수 있는데 의사나무는 그렇지 않다. |
비모수적 모형 - 선형성(linearity), 정규성(normality) 또는 등분산성(equal variance) 등의 가정이 필요하지 않다. | 비 안정정 - 분석용 자료(training data)에만 의존하므로 새로운 자료의 예측에서는 불안정(unstabile)할 가능성이 높다. |
4)가지치기(pruning)
나무가 너무 커지면 학습데이터에 과적합(overfitting)할 염려가 생긴다. 즉, 새로운 사례에 대해서 분류의 정확도가 훼손될 수 있다. 따라서 나무의 크기를 줄여주는 가지치기를 한다.
가지치기는 데이터를 버리는 것이 아니라 합치는 과정이다.
5)의사결정나무 모형
목표변수가 이산형인 경우의 분류나무(classification tree)와 목표변수가 연속형인 경우의 회귀나무(regression tree)로 구분된다.
2.불순도와 불확실성
의사결정나무는 한 번 분기 때마다 변수 영역을 두 개로 구분하는 모델인데, 이 영역을 나누는 기준은 순도로 결정한다. 즉, 나무 모형이 분류한 뒤 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertaionty)이 최대한 감소하도록 하는 방향으로 학습을 진행한다. 불순도 측도의 기준은 분류나무와 회귀나무에 따라 다르다.
1)분류나무
목표변수가 이산형인 분류나무의 경우 상위노드에서 가지분할을 수행할 때, 분류변수와 분류 기준값의 선택 방법으로 카이제곱 통계량(Chi-square statistic)의 p값, 지니 지수(Gini index), 엔트로피 지수(entropy index) 등이 사용된다.
선택된 기준에 의해 분할이 일어날 때, 카이제곱통계량의 p값은 그 값이 작을수록 자식노드 간의 이질성이 크고, 자식노드에서의 지니 지수와 엔트로피 지수는 그 값이 클수록 자식노드 내의 이질성이 큼을 의미한다. 이질성이 크다는 것은 순수도가 낮다는 의미다.
2)회귀나무
목표변수가 연속형인 회귀나무의 경우에는 분류변수와 분류 기준값의 선택방법으로 F-통계량의 F-값, 분산의 감소량 등이 사용된다.
F-통계량은 등분산성을 검정하는데 사용하는 통계량으로, F-통계량의 p값이 크면 등분산성이 있으므로 낮은 이질성을 보인다. 따라서 F-통계량의 p값이 커지는 방향으로 가지분할을 한다. 분산의 감소량도 최대화 되는 방향으로 수행된다.
3.여러 가지 의사결정나무 알고리즘
1)CART(Classification and Regression Tree)
: 가장 많이 활용되는 의사결정나무 알고리즘으로 불순도의 측도로 출력 변수가 범주형일 경우 지니지수를 이용, 연속형인 경우 분산을 이용한 이진분리(binary split)를 사용한다.
2)C4.5와 C5.0
: CART와는 다르게 각 마디에서 다지분리(multiple split)가 가능하며 범주형 입력변수에 대해서는 범주의 수만크 분리가 일어난다. 불순도의 측도로는 엔트로피지수를 사용한다.
3)CHAID(CHi-squared Automatic Interaction Detection)
: 가지치기를 하지 않고 적당한 크기에서 나무모형의 성장을 중지하며 입력변수가 반드시 범주형 변수이어야 한다.
: 분순도의 측도로는 카이제곱 통계량을 사용한다.
이산형 목표변수 | 연속형 목표변수 | |
CHAID | 카이제곱 통계량 | ANOVA F-통계량 |
CART | 지니지수 | 분산감소량 |
C4.5 | 엔트로피지수 |
4.의사결정나무의 분석 과정
성장 > 가지치기 > 타당성 평가 > 해석 및 예측
1)성장 단계
: 각 마디에서 적절한 최적의 분리규칙을 찾아서 나무를 성장시키는 과정으로 적절한 정지규칙을 만족하면 중단
-정지규칙(stopping rule) : 더 이상 분리가 일어나지 않고 현재의 마디가 끝마디가 되도록 하는 여러가지 규칙
2)가지치기 단계
: 오차를 크게 할 위험이 높거나 부적절한 추론규칙을 가지고 있는 가지 또는 불필요한 가지를 제거하는 단계
3)타당성 평가 단계
: 이익도표, 위험도표 혹은 시험자료를 이용하여 의사결정나무를 평가
4)해석 및 예측 단계
: 구축된 나무모형을 해석하고 예측모형을 설정한 후 예측에 적용
5.의사결정나무 생성 함수
함수 | 특징 |
tree()함수 {tree} | binary recursive partitioning 방법을 사용. 불순도의 측도롤 엔트로피 지수를 사용한다. 엔트로피는 0~1 사이의 값을 가지며 1에 가까울수록 혼잡도가 높다. tree()는 엔트로피가 높은 상태에서 낮은 상태가 되도록 나무 모양을 생성한다. |
rpart()함수 {rpart} | CART방법을 사용. 지니지수가 작아지는 방향으로 움직이며, 지니 지수를 가장 많이 감소시켜 주는 변수가 영향을 갖아 많이 끼치는 변수가 된다. |
ctree()함수 {party} | Unbiased recursive partitioning based on permutation test 방법을 사용. p-test를 거친 significance를 기준으로 가지치기를 할 변수를 결정하기 때문에 biased될 위험이 없어 별도로 가지치기할 필요가 없다. 하지만 입력 변수의 레벨이 31개까지로 제한되있다. |
위 3개 함수로 나무 성장 시킨 후, plot()함수로 그림을 나타낸다.
6.의사결정나무 예시
#데이터 불러오기
data(iris)
str(iris)
## 'data.frame': 150 obs. of 5 variables:
## $ Sepal.Length: num 5.1 4.9 4.7 4.6 5 5.4 4.6 5 4.4 4.9 ...
## $ Sepal.Width : num 3.5 3 3.2 3.1 3.6 3.9 3.4 3.4 2.9 3.1 ...
## $ Petal.Length: num 1.4 1.4 1.3 1.5 1.4 1.7 1.4 1.5 1.4 1.5 ...
## $ Petal.Width : num 0.2 0.2 0.2 0.2 0.2 0.4 0.3 0.2 0.2 0.1 ...
## $ Species : Factor w/ 3 levels "setosa","versicolor",..: 1 1 1 1 1 1 1 1 1 1 ...
levels(iris$Species)
## [1] "setosa" "versicolor" "virginica"
iris(붓꽃 데이터셋)
-Sepal.Length: 꽃받침 길이
-Sepal.Width: 꽃받침 너비
-Petal.Length: 꽃잎 길이
-Petal.Width:꽃잎 너비
-Species: 붓꽃의 종
levels(iris$Species)
## [1] "setosa" "versicolor" "virginica"
붓꽃의 종은 세 가지다
#train/test 데이터 분할
set.seed(1234)
idx <- sample(2,nrow(iris),replace = TRUE,prob = c(.7,.3))
train.data <- iris[idx==1,]
test.data <- iris[idx==2,]
str(train.data)
## 'data.frame': 112 obs. of 5 variables:
## $ Sepal.Length: num 5.1 4.9 4.7 4.6 5.4 4.6 5 4.4 4.9 5.4 ...
## $ Sepal.Width : num 3.5 3 3.2 3.1 3.9 3.4 3.4 2.9 3.1 3.7 ...
## $ Petal.Length: num 1.4 1.4 1.3 1.5 1.7 1.4 1.5 1.4 1.5 1.5 ...
## $ Petal.Width : num 0.2 0.2 0.2 0.2 0.4 0.3 0.2 0.2 0.1 0.2 ...
## $ Species : Factor w/ 3 levels "setosa","versicolor",..: 1 1 1 1 1 1 1 1 1 1 ...
str(test.data)
## 'data.frame': 38 obs. of 5 variables:
## $ Sepal.Length: num 5 4.3 5.7 5 5.2 5.2 5 4.4 5.1 5 ...
## $ Sepal.Width : num 3.6 3 4.4 3 3.5 3.4 3.2 3 3.4 3.3 ...
## $ Petal.Length: num 1.4 1.1 1.5 1.6 1.5 1.4 1.2 1.3 1.5 1.4 ...
## $ Petal.Width : num 0.2 0.1 0.4 0.2 0.2 0.2 0.2 0.2 0.2 0.2 ...
## $ Species : Factor w/ 3 levels "setosa","versicolor",..: 1 1 1 1 1 1 1 1 1 1 ...
sample함수를 이용해 1,2 숫자를 복원추출로, 7대 3 비율로, iris 관측치 수 만큼 생성한다. train데이터에는 70%, test데이터에는 30%를 준 것이다.
1)tree()함수
library(tree)
iris.tree1 <- tree(Species~. , train.data)
plot(iris.tree1)
text(iris.tree1)
tree()함수는 plot으로 가지를 그려준 후, text로 나타낸다.
2)Conditional Inference Tree(조건적 추론 나무)
ctree()함수
library(party)
iris.tree2 <- ctree(Species~. , data = train.data)
plot(iris.tree2)
총 7개의 node가 생성되었다. n은 표본의 수를 의미하고 각 끝마디에 나타다는 막대그래프는 세 가지 붓꽃 종의 비율을 의미한다. 비율은 type인자로 바꿀 수 있는데, 아래와 같이 막대그래프를 숫자로 표현할 수 있다. 비율의 순서는 levels에서 본 순서(“setosa” “versicolor” “virginica”)와 같다.
plot(iris.tree2, type ="simple")
ctree()함수는 가지치기 단계가 없다.
#예측된 데이터와 실제 데이터 비교
table(train.data$Species,predict(iris.tree2), dnn = c('Actual','Predicted'))
## Predicted
## Actual setosa versicolor virginica
## setosa 40 0 0
## versicolor 0 37 1
## virginica 0 3 31
만들어진 나무모형(iris.tree2)를 predict함수로 예측한 후, 실제 데이터와 비교한다. 4개 관측치를 제외하고 모두 동일하다. 즉, 오차율이 약 3.5%이다.
#test data로 정확성 검정
test.pre <- predict(iris.tree2,newdata=test.data)
table(test.data$Species,test.pre, dnn = c('Actual','Predicted'))
## Predicted
## Actual setosa versicolor virginica
## setosa 10 0 0
## versicolor 0 12 0
## virginica 0 2 14
정확도가 약 94.7%이다.
3)Classical Decision Tree(전통적인 의사결정 나무)
rpart()함수
#1.성장단계
library(rpart)
iris.tree3 <- rpart(Species~. , data = train.data,method = 'class', parms = list(split='informative'))
iris.tree3$cptable
## CP nsplit rel error xerror xstd
## 1 0.5277778 0 1.00000000 1.15277778 0.06438675
## 2 0.4166667 1 0.47222222 0.55555556 0.07042952
## 3 0.0100000 2 0.05555556 0.08333333 0.03309688
-nsplit: 나무의 크기를 나타낸다.(n분기수, 터미널 노드수=n+1)
-cp(complexity parameter):복잡성 파라미터
-rel error:나무오류률
-xerror:교차검증오류률
-xstd:교차오차의 표준오차
-xerror+xstd의 범위 내에서 있는 값 중 가장 오류의 값의 나무를 선택한다.
plotcp(iris.tree3)
xerror가 점선 안쪽에 들어온 것 중에 가장 작은 xerror 혹은 가장 큰 cp를 지닌 나무를 선택
#2.가지치기 단계
pruned.iris.tr <- prune(iris.tree3, cp = 0.01000)
library(rpart.plot)
type = 2, #표시되는 것이 다르다.(조건, 이름...)
extra = 104,
fallen.leaves = TRUE, #터미널 노드 그릴지 말지
box.palette = 'auto',
main = '- The Best Classical Decision Tree -',
snip = TRUE)
type은 0~5까지 있으며 나무 그래프 모형을 변경하는 인자다. extra는 100,104,106이 있고 붓꽃 종의 비율이 표시되는 것을 변경하는 인자이다. rpart.plot() 대신 prp()함수를 써도 똑같다.
#3.해석 및 예측 단계
#예측된 데이터와 실제 데이터 비교
## Predicted
## Actual setosa versicolor virginica
## setosa 40 0 0
## versicolor 0 37 1
## virginica 0 3 31
#test data로 정확성 검정
table(test.data$Species, test.pre2, dnn = c('Actual','Predicted'))
## Predicted
## Actual setosa versicolor virginica
## setosa 10 0 0
## versicolor 0 12 0
## virginica 0 2 14
정확도가 약 94.7%이다.
반응형
댓글