비선형 회귀 모델(상호작용모델)의 경우에는 만일 선형회귀식내에 다뤄야할 피쳐수가 너무 너무 많은경우에는 이러한 경우에 설명이 잘 되지 않는다. 비선형 회귀모델에서 이러한 방법을 대체할 수 있는 방법이 Partition이다. 이렇게 나누는 과정을 계속계속 나누다는 과정을 recursive partitioning이라고 부른다.
예측 나무는 나무를 이용하여 나누는 과정을 표현한다. 나무의 Terminal node와 leaves는 각 파티션의 한 부분을 의미한다. 위에서부터 각 x들이 어디에 속할지를 파악하기위해 root node부터 시작한다. 그리고 피쳐에 대해서 계속 질문을 해나가서면서 if else 형식으로 분류해 나간다. 또한 이러한 변수들은 모두가 같은 데이터타입의 형식이 아니어도된다. 어떤것은 연속형범수(비율척도)여도 되고, 어떠 것은 이산형이나, 순서형, 명목형이어도 상관이 전혀없다. 각 분류를 하기 위해 질문을 해나가는 과정만 잘 진행되면된다.
Decision trees
보통, 의사결정나무라고하면, Classification tree을 의미한다. 그러나, Regression tree을 의미하는 경우도 있는데, 두 차이를 이해할 필요도 있다. 첫번째 차이는 사용하는 변수의 척도에 따라서 나눌 수 있다. 회귀트리는 연속형 변수를 사용하는 반면, 분류트리는 연속형 변수를 사용할 떄 이용된다. 이 변수는 독립변수와 종속변수 둘 다 해당된다. 또한 사용하는 알고리즘에서도 차이가 있는데, 분류트리는 대표적인 ID3 알고리즘과 같이, 지니 지수와 엔트로피의 개념으로 분류를 양적으로 계산한다. 한편, 회귀트리는 연속형 변수이기 때문에, 클레스(Class)을 나눌 수 없는데, 따라서 관측한 값과 만든 예측모델에서의 RSS을 계산하여 모델링한다.
Classification tree이를 세부적으로 알아보기 위해 아래의 몇 가지를 알아보자.
ID3 Algorithm (decision tree에 적용할 수 있는 알고리즘)
Decision tree에서 ID3는 entropy를 이용한 알고리즘인데 다음과 같은 방식으로 모델이 작동한다.
1. 현 Node를 나눌 가장 적절한 피쳐A를 찾는다. (=Root Noded을 찾는다)회귀트리에서는 RSS가 가장 많이 감소할 수 있는 feature을 찾고, 분류트리에서는 Entropy와 Information Gain (in ID3)을 이용한다.
그러면, 어떤게 가장 적절한 피쳐A인지 궁금해할 것이다. 이를 위해, ID3 알고리즘에서는 metric을 만들어서 사용하는데 (측정할 수 있는 모델), entropy라는 개념을 이용해서 사용한다. 실제로는 entropy와 Information gain을 이용한다. 참고로 ID3는 leaf node가 pure한 상태가 되도록 알고리즘이 수행되기 때문에, 오버피팅 문제가 발생할 수 있다.
불순성을 측정하는 방법은 Entropy, Gini ,Classifcaion error로 계산 할 수 있다.
불순도의 측정
1. Entropy
복잡도. 열역학 2법직이란 자연현상은 항상 엔트로피가 증가하는 방향으로 일어난다. 예를 들어, 여러 과자를 봉투에 튿어서, 한 봉투에 넣고, 집까지에 돌아다니게되면, 과자가 다섞여있을 것이다. 이러한 개념이 복잡도이다. 이런 개념으로, 엔트로피가 높다는 것은 복잡도가 높다는 것이다.
(사진출처 : https://www.youtube.com/watch?v=9r7FIXEAGvs)
엔트로피의 정의는 아래의 식과 같다. 이거는 이항분포(Binary distribution)처럼 p2 = 1- p1 같은데, 즉 p1 (2가지로만 가정했을 때)
아래의 식을 보면, 엔트로피는 확률이 0.5일 때, 가장 높은데, 이 말은 그룹내에 종류가 50: 50으로 있다는 말이고, 종류가 1:0 혹은 0:1일 때, 가장 pure하여 엔트로피가 0인 것이다. (퓨어한 리프까지 갔다면, 엔트로피가 0이다. = 같은 속성인 요소끼리 놓았다). 즉 우리는 한 잎(leaves, region)안에는 동질성이 있는 그룹으로 나누길 원하기때문에, 엔트로피가 최소인 선택을 애햐한다. 분류트리에서는 이러한 엔트로피가 가장 크게 감소하는 속성을 베스트 속성으로 찾는다.
Information Gain
위의 엔트로피의 계산에서, 이렇게 엔트로피가 감소하는 정도를 측정하는 방법(Metric)이 있는데, 이 방법 중 하나가 information Gain이다 . Gain(S,A) 의 의미는 피쳐 A로 나눔으로써 얻게되는 엔트로피의 감소이다. 따라서, 엔트로피의 감소가 큰 피쳐를 찾아야하기 때문에, Gain이 큰 값을 찾아야 한다. (즉= 어떤 feature로 나눌건인지에 대해 계산을 해야하는데 Inforamtion gain으로 계산해볼 수있다.)
(S는 데이터세트, A는 나눌 속성, H(S) 나누지 않았을 때의 엔트로피, - Sv는 그룹에 속해있는 요소의 크기(수), S는 나누기전의 수)
따라서, 여러 속상에 대해서 information Gain을 다 계산해서, 가장 많은 Gain을 가져다 줄 수 있는 속성을 우리가 찾는 피쳐이다.
2. Gini index
또 다른 방법 중 하나는 지니 계수이다. 지니 계수는 엔트로피랑 유사하게 불순성(impurity)을 측정하는 방법이다. 즉 지니계수가 클수록 여러종류의 요소들이 한 노드에 있는 것이다. 이 말은, 제대로 분류가 안되었다는 말과 같다. 식은 아래와 같다. 작관적으로 이해하기위해서 아래 식에서, 1번 분류하는데 모두 같은 종류라고, 생각하면 지니는 0이다. 즉 완벽하게 분류되면 0, 점점 섞이면 섞일수록 커진다. (Pk는 각 인스턴스들이 k클레스에 속하는 비율이다. 50개중에 25개가 클레스 1에 속한다면 1/4에 해당한다)
2. A를 현재 Node(Region)의 decision attribute을 적용한다3. A의 가능한 값들에 대해, 현 node의 child node들을 각각 하나씩 만든다. (Split)4. 현 Node에 들어있는 training exmaple 들을 각 A값에 따라 child node에 넣는다. (Split)5. Child node에 대해 node가 Pure하면 멈추고(, 그렇지 않으면 child node부터 계속 반복한다
풀어서 예시를 들면, 독립변수에 대해서 변화할 수 있는 값들에 대해서 나눌 수 있는 지점?들을 찾고 나눈다(Split point라고 한다). 그러면 각 영역은 겹치지 않는 영역으로 생각할 수 있다. 그리고나서 그 분류지점에 따라, 모든 관측된 변수들을 각각의 영역에 배치시킨다. 예를 들어 수학점수라고 할 때, 보충반 의 수학평균이 60, 그리고 다른 심화반의 수학점수의 평균이 80인 클래스가 있다고하자. 그리고 어떠한 새로운 사람이 들어왔을때, 그 사람이 첫번째 반에 속한다면, 이 사람의 점수가 60점이라고 예측하고, 만일 심화반에 속한다면 80점에 속한다고 보는 것이다. 즉 구역에따라서 점수를 나누는 것이다.
회귀트리(Regression Trees)회귀트리는 계속 해서 2가지의 가지로 회귀적인 분할을 하는 과정의 방법이다. 이는 반복적으로 데이터를 2분류로 나누는 방법인데, 계속해서 2분류로 나누고 그 나눈 분류를 다시 2분류로 나누는 방법이다. 이런식으로 분할하여 분류모델을 만들어내서, 어떠한 변수들이 인스턴스를 설명할 때, 찾고자하는 종속변수를 예측할 수 있다. 즉, 선배들이 잘 만들어 놓은 길의 갈림길을 따라, 후배가 Root부터 leaves까지 쭉 따라가서 어느정도 종속변수를 예측하는 것이라고 생각하면 된다.
분할을 하면 잔차의제곱합(RSS, 예측값과 관측값의 차이를 제곱하여 더한 값)이 개선된다. 트리의 마지막까지 계속 둘로 분할한다. 나무를 뒤집어 놓은 형식(식물의 뿌리같은 느낌)의 방향으로 분할하는 방식을 Top-down 분할이라고하고, 이런 과정을 Greedy라고도 한다. 또한 비선형 예측모델이다. 또한 DT 는 회귀문제에도 적용할 수 있고, 분류문제에도 적용할 수 있다.
참고로
는 분류 결과의 왼쪽 branch를 의미하고,
는 분류 결과의 오른쪽 branch을 의미한다.
(외우기쉽게 이해하기엔, 등호 방향으로 만족한다라고 생각하면 된다.
Constructing the regions
이론상 region(예시에서의 반과 같은 구분할수 있는 공간)은 어떤모양이어도 되지만, 사람이 이해하기 쉬우러면 사각형이 편하다. 그렇기 때문에 2차원에서는 사각형, 고차원에서는 6각형이상의 고차원 박스가 나오는것이다. 이 모델의 목적은 그러면 어떻게 사격형(각 영역, 직사각형)을 구하냐는 것이다. 이는 아래의 식으로 구할 수 있다.아래의 식을 풀어해석하면은 각각의 yi에 대해서 j안에 있는 관측값들의 평균을 빼는 방식으로 모든 j개의 박스들을 다 계산을 하는 것이다. 그것의 값의 차이를 RSS라고 둔다. (회기식에서 RSS와 유사하다). 그러나 모든 J개의 분리가능한 파티션에 의해 계산하는 것은 거의 불가능하다. 처음부터 파티션을 어떻게 정하는지도 정해져있고, 생김도 모두 다르기 때문인 듯. 그러므로, 우리는 Top-down방식Greedy approach (=recursive binary splitting)의 방식을 이용하면. 가능하다. 처음 영역을 모두를 포함하는 영역이라고 하고, 변수에 따라 박스를 하나씩 그리면서(파티션을 두면서) 나눠가는 것이다. 파티션이 생기면 2개의 박스조각으로 나뉘는데 이게 tree의 branch가 된다. greedy라고 하는 이유는 각 스텝에서 최적의 파티션을 찾는 것은 특정 파티션을 찾을때까지 나누지 않기때문에 이렇게부른다)
1. 트리를 키우기 위해서, 계속 split을 하게되는데 recursive binary splitting을 한다. (즉 Numer of splitting이 큰게 large tree)
(관측수보다 트리의 말단노트가 적을 때까지 진행한다)
2. 그리고 너무 많은 subtree을 제거하기위해서 Cost complexity pruning을 진행한다. (= 최적의 subtree을 찾아서, 제거하기 위함이다)
3. K-fold cross-validation 을 진행한다.
1) K번째 fold를 빼본다음에 오류값을 계산하고 , 오류가 최소가되는 subtree을 찾는다
4. 다시 2번을 진행한다.
Overfitting in Decision tree
의사결정나무 중, ID3을 이용하면, 말단 노드들은 퓨어한 상태까지 분류가 이루어지게 된다. 사용되는 피쳐들이 몇개 없다면 상관 없지만, 피쳐들이 많다면, 이러한 방법은 문제가된다. 데이터의 수가 많은경우, 아웃라이어처럼 예외적인 데이터들도 있을 텐데, 이 경우의 수에 대해서 다 퓨어하게 분류를 하게되기 때문이다. 즉, 노드의 개수가 많아지면서 오버피팅 문제가 발생할 수 있다. 즉, 예외일 수도 있는데, 굳이 분류를 하게되는 것이다. 오버피팅을 줄이기 위한 방법은 아래의 두가지로 요약할 수 있다.
1. Stop splitting
A. Minimum n.이 방법은 쉽게말해서 마지막 노드들에 대해서 최소 이정도 갯수를 가지면 split을 멈추게 한다는 것이다.
B. Fraction of objects: 이 방법은 말단 노드들이 퓨어한 상태이거나 , 또는 본인이 지정한 수만큼, 노드안에 종류가 포함될 때 멈추는 것이다.
2. Pruning
트리의 크기가 너무 커지면, 해석하기도 어렵고 오버피팅이 생기기 때문에, 적당한 크기의 트리를 만드는게 중요하다. Pruning(가지치기)라는 방법은 가장 큰 Tree(number of split이 최대인 tree)을 그린다음에 서브트리를 하나씩 빼보는 것이다. 그러면 어떤 서브트리를 뺴야 가장 좋은 선택인지를 정해야한다. 즉, 서브트리를 뺴도 설명력이 흔들리지 않아야한다. 유사하게말하면, 빼도 괜찮은 트리는 에러가 크게 나지 않을 것이다. 있으나 마나한 그저그런 파티션일거니깐. 예를 들어, 한 서브트리를 정한다음에, 이걸 뺄지 말지를 고민할때는 Cross-validation을 해서 에러를 평가한다. 그렇기 때문에, 적어도 트리를 만들 때, 3그룹 이상이 필요하다. 즉 train, validation, test로 나눌 때 가능하다(Validation set가 있을 때 가능하다. 왜냐하면, train set와 비교하면서 프루닝해야되기 때문이다). 또한, 트리가 너무 큰 경우에는, 모든 서브트리에 대해서 계산을 해야되기때문에 시간이 오래걸린다. 그러므로 이 방법은 트리가 작은 경우에 사용한다.
해석(Interpretation)
트리구조에서 가장 상단에 있는 factor는 회귀트리에서 가장 중요한 변수임을 나타난다.
그리고 그 아래있는 internal node에 해당하는 변수들은 상대적으로 덜 중요한 변수라고 여겨진다.
Terminology
Terminal nodes (leaves): 각 영역R1, R2 등... 즉, 트리모양에서 가장아래에 해당하는 부분이다.
Internal nodes: 중간에 나뉘는 갈림길 (분지점)을 Internal nodes라고 한다. 예를들어 수학점수<80 ? 이렇게 쓰여져있는 지점들이다.
Branches: 각 노드들에 연결되어있는 tree의 일부를 branch라고 한다.
Complexity parameter(CP): 복잡도인자
nsplt : number of split. 즉 트리를 분할한 횟수
rel error: 상대오차. 분할횟수에 따른 RSS값을 분할하지 않았을 때의 RSS로 나눈 값
xerror: 10-fold cross validation을 토통해 나온 값으로 평균오차고
xstd: 교차검증과정의 표준편차
'Data science' 카테고리의 다른 글
| Reshape and Pivot table (0) | 2019.03.08 |
|---|---|
| SVM (Support Vector machine) (0) | 2019.02.23 |
| Pandas Dataframe Manipulation (0) | 2019.02.14 |
| Category data handling (0) | 2019.02.14 |
| kNN model (k-Nearest neighbor model) (0) | 2019.02.13 |