이번에는 의사 결정 트리에 대해 알아보자.
의사 결정 트리는 약간 flow chart와 비슷하다.
어떤 입력 값에 대해 '참', '거짓'으로 분기를 타는 로직을 거쳐서 정답을 찾아나가는 과정이다.
이전 포스팅에서 언급한 kNN과는 어떠한 차이가 있을까??
kNN 같은 경우에는 모든 데이터에 대한 학습 데이터가 필요하다. 왜냐하면 데이터 하나하나 마다의 거리를 구해야 하기 때문이다. 하지만 decision tree 같은 경우에는 트리 모양만 만들어 주게 되면 따로 input 데이터가 들어왔을 시 kNN 처럼 일일이 계산을 해줄 필요는 없다.
그럼 이제 어떻게 decision tree를 만들어야 할 것인지에 대해 알아보기로 하자.
decision tree를 설계하기 위해 엔트로피라는 단어가 나온다. 원래는 물리학쪽에서 나온 단어였던 것 같은데 아마도 그 의미는 비슷할 것 같다.
엔트로피를 가장 간단히 설명하자면, 주어진 집단이 혼잡한가 안혼잡한가를 나타내는 수치를 의미한다고 할 수가 있다. 만약 주어진 집단이 서로 다른 종들이 많이 섞여 있을 경우에는 엔트로피 수치가 높고, 비슷한 종류의 집단일 경우에는 엔트로피 수치가 낮다.
decision tree의 목적이 이러한 비슷한 종류의 집단을 최대한 분류해 내는 것이 목적이기 때문에 엔트로피를 잘 계산해서 설계를 해나가야 한다.
엔트로피 수식은 아래와 같다.
Pi는 전체 데이터 집합 중 해당하는 종류가 차지하는 비율을 나타내며, 이를 log2 함수로 한번 감싼 후, 다시 Pi를 곱한 값들의 합으로 표시해 주고 있다.
log2로 감싼 이유는 아무래도 정규화 작업 때문인 것 같다(?). 정규화 작업으로 0 ~ 1 사이 값을 만든 후 거기에 Pi라는 가중치 값을 곱해주는 것 같다. (확실히는 모르겠음)
마지막에 -부호를 붙여주는데 이 이유는 log2의 결과 값이 0 이하의 값이 나오기 때문에 부호를 반대로 취해주어야 양수가 발생한다. ( Pi의 범위가 0~1 사이 값인데, log2(1)이 0이기 때문에 결과 값이 음수가 나온다.)
코드를 간략히 살펴보자면 우선 createDataSet() 함수로 데이터 셋과 label을 생성한다. 그 후에 생성된 dataSet과 label을 파라미터로 createTree를 호출한다.
createTree에서는 입력된 dataSet에서 가장 마지막 항목들만 추출하여 리스트를 생성한다.
ex) ['yes', 'yes', 'no', 'no', 'no]
createTree 함수는 재귀 함수이기 때문에 종료 조건이 명시되어야 한다. 아래의 두 가지 조건이 종료 조건이 된다.
첫번째로 추출된 리스트의 첫번째 항목의 개수가 전체 리스트의 개수와 동일하다면 함수를 종료하고 첫번째 항목을 리턴해준다.
ex) 'yes'의 개수가 5이면 즉, ['yes', 'yes', 'yes', 'yes', 'yes] 란 데이터 셋이 들어왔을 경우에는 'yes'를 리턴해준다.
두번째 조건은 dataSet의 값이 1개뿐인 경우, 함수를 종료하고 majorityCnt를 호출한다. 여기서 dataSet의 값이 1개뿐이란 말은 더 이상 분류할 속성이 존재하지 않는다는 것을 뜻한다.
ex) dataSet이 [1, 2, 'yes'] 일 경우에는 분류할 속성이 존재하는 반면 dataSet이 [1] 하나만 존재할 경우에는 더 이상 분류할 속성 값이 존재하지 않는다.
majorityCnt는 과연 무슨 기능을 하길래 호출하는 걸까?? majorityCnt는 dataSet에서 추출한 리스트를 받아서, 가장 많은 빈도수의 값을 리턴해주는 역할을 한다.
ex) [[1],[1],[2],[1],[3]]이란 리스트가 들어왔을 경우 1을 리턴해줌
dataSet 값이 1개 이상이고, 리스트 자체에 동일한 속성 값만 존재하는게 아니라면, chooseBestFeatureToSplit을 호출하여 어떤 속성을 분할 했을 때 information gain이 가장 큰지를 찾는다.
information gain은 데이터를 분할하기 전의 엔트로피와 데이터를 분할한 후의 엔트로피의 변화량을 일컷는데, 이 값이 가장 컸을 경우가 분할 했을 시 가장 좋은 효과를 낸다고 한다.
chooseBestFeatureToSplit을 조금 살펴보자면, 우선 calcShannonEnt를 통해 분할하기 전의 엔트로피 값을 구한다.
그 후 각 속성에 대해 분할한 값들을 더한 엔트로피를 더한 후 차이가 큰 속성값을 찾아내야 한다.
예를 들어 만약 dataSet이 =[[1,0], [0,1], [1,1],[0,0],[0,1]] 이렇게 되어 있다고 가정하면, 총 계산해야 할 속성 값은 2개가 된다.
코드를 보면 featList에 dataSet에 대한 모든 속성 값을 저장한 후, set을 통해 중복 값을 가지는 속성 값을 제거한다. 위에서 예로든 dataSet을 살펴보면, featList는 결과적으로 [0,1] 값을 가진다.
그 후에 dataSet을 분해하는데, 첫번째 속성이 0인 값들을 찾아서 엔트로피를 더해주고, 그 다음으로 첫번째 속성이 1인 값들을 찾아서 엔트로피를 더해준 후 그 결과를 맨 처음 계산했던 분할하기 전 엔트로피 값에서 빼준다.
그 다음으로 두번째 속성이 0인 값들을 찾아서 엔트로피를 더해주고, 또 두 번째 속성이 1인 값들을 찾아서 엔트로피를 더해준 후 그 결과 값을 처음 엔트로피 값에서 빼준다.
이렇게 뺀 결과 차이가 큰 경우의 속성 값이 가장 최적으로 분할할 수 있는 속성 값이라고 할 수 있다.
코드에서는 엔트로피 계산시 가중치를 계산하는 부분이 있는데,
prob = len(subDataSet) / float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
만약 dataSet = [[1,0],[0,1],[1,1],[0,0],[0,1]] 중에 첫번째 속성이 0인 값을 찾을 때, [0,0],[0,1] 이렇게 두 항목을 찾을 수가 있고 그래서 가중치는 2/5가 된다. 이 값을 계산된 엔트로피에 추가로 더해주면 된다.
그 다음 코드부터는 찾은 속성 값의 index를 가지고 label을 찾아서 tree를 만드는 부분이다.
해당 코드를 실행한 결과는 아래와 같다.
