(머신러닝) 3장 의사결정 트리: 한 번에 하나의 속성으로 데이터 분할하기
1. 트리 구조
장점: 계산 비용이 적다. 학습된 결과를 사람됙이 이해하기 쉬우며 누락된 값(missing value) 이 있어도 처리할 수 있다. 분류와 관련이 없는 속성이 있어도 처리할 수 있다.
단점: 과적합(Overfitting)되기 쉽다.
적용: 수치형값, 명목형 값
1. 정보이득
데이터를 분할하기 전과 후의 변화를 정보 이득이라고 한다.
어떤 속성으로 데이터를 분할할 때 가장 높은 정보 이득을 취할 수 있는지를 모든 속성에 대해 확인하면서 분할할 수 있게 된다. 정보 이득이 가장 높은 속성을 가지고 분할하는 것이 가장 좋은 선택이다.
분할하기에 가장 놓은 속성을 측정하고 데이터를 분할하기 전에 정보이득을 계산하는 방법을 알아야 한다. 데이터 집합에 대한 정보 측정 방법을 엔트로피라고 한다.
엔트로피는 정보에 대한 기대 값으로 정의 된다. 우리는 정보라는 것부터 알아야 한다.
만약에 다양한 값을 가질 수 있는 어떤 데이터를 분류하고자 한다면, 정볼르 xi로 표시하고 다음과 같이 정의할 수 있다.
l(xi)=log2p(xi)
여기서 p(xi)는 xi라는 분류 항목이 선택될 확률이다.
엔트로피를 계산하기 위해서는 분류 항목의 가능한 모든 값에 대해 모든 정보의 기대 값이 필요하다. 이것은 다음식에서 얻을 수 있다.
H=-∑p(xi)log2p(xi)
위 식의 n은 분류 항목의 개수이다.
<데이터 집합의 새넌 엔트로피를 계산하는 함수>
def calcShannonEnt(dataset):
numEntires=len(dataset)
labelCounts={}
for featVec in dataSet:
currentLabel=featVec[-1]
if currentLabel not in labelCount.keys():
labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1
shannonEnt=0.0
for key in labelCounts:
prob= float(labelCounts[key])/numEntries
shannonEnt-=prob*log(prob,2)
return shannonEnt
*여러 속성 중 정보 이득이 가장 큰 속성을 가지고 데이터 집합을 분할하도록 하자. 실질적으로 데이터 집합을 분할하고 정보이득을 측정해 보지 않고는 정보 이득이 가장 큰 속성이 어떤 것인지 알 수 없다.
1.2 데이터 집합 분할하기
*<주어진 속성으로 데이터 집합 분할하기>
def splitDataSet(dataSet, axis, value):
retDataSet=[]
for featVect in dataSet:
if featVec[axis] == value:
reducedFeatVec=featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
***파이썬 에서는 리스트 자료형을 처리하는 메소드가 2가지 있는데 extend()와 append두가지가 있다.
a=[1,2,3]
b=[4,5,6]
a.append(b)
-->[1,2,3,[4,5,6]]
a.append(b)를 실행하면 4개의 원소를 가지는 하나의 리스트를 가지게 된다. 이 중 네 번째 원소는 하나의 리스트이다.
그러나
a=[1,2,3]
a.extend(b)
-->>[1,2,3,4,5,6]
<데이터 분할 시 가장 좋은 속성 선택하기>
가정:
1. 데이터는 다중리스트이다.
2. 모든 리스트의 크기는 똑같다.
3. 마지막 칼럼 또는 각각의 사례에서 마지막 아이템이 사례에 대한 분류 항목 표시를 가지고 있다는 것이다.
def chooseBestFestureToSplit(dataSet):
numFeatures=len(dataSet[0])-1
baseEnthropy=calcShannonEnt(dataSet)
bestInfoGain=0.0; bestFeature=-1
for i in range(numFeature):
featList=[example[i] for example in dataSet]<-------- 1. 분류 항목표시에대해
uniqueVals=set(festList) <-------- 중복이없는 리스트 생성
newEntropy=0.0
for value in uniqueVals:
subDataSet=splitDataSet(dataSet,i,value) <------------2. 각각의 분할을
prob=len(subDataSet)/float(len(dataSet)) <----------- 위해 엔트로피
newEntropy+=prob*calcShannonEnt(subDataSet) <---- 계산
infoGain=baseEntropy-newEntropy
if (infoGain>baseInfoGain):
baseInfoGain=infoGain
baseFeature=i
return bestFeature
-->위 코드는 어떤 분할도 일어나기 전에 데이터 집합 전체에 대한 새넌 엔트로피를 계산한다. 이 값은데이터의 어수선한 정도를 표현한 것으로, 데이터 분할 후의 어수선한 정도와 비교하는데 사용한다.
처음에 나오는 for문은 데이터 집합에 있는 모든 속성을 대상으로 반복한다. 그런 다음 집합을 사용한다. 하나의 리스트로 부터 하나의 집합을 생성하는 것은 리스트에 유일한 값을 부여하기 위함이다.
그런다음 해당 속성의 유일한 값을 모두 추출하고 각 속성별로 데이터를 분할한다. 해당 속성의 유일한 값 모두에 대해서 새로 엔트로피를 계산하고 이들을 모두 더한다.
정보이득은 엔트로피를 줄이거나 혼잡도를 줄이는 것이다.
마지막으로, 모든 속성에 대한 정보이득을 비교하여, 데이터 집합을 분할하기 가장 좋은 속성의 색인을 반환한다.
1.3 재귀적으로 트리 만들기
데이터 집합을 가지고 시작해서, 데이터 집합을 분할하는 데 가장 좋은 속성을 기반으로 데이터 집합을 분할한다. 이것은 바이너리 트리가 아니기 때문에, 데이터 집합을 분할하는 방법이 두 가지보다 많다.
이 알고리즘이 더 이상 분할할 속성이 없거나 하나의 가지에 있는 모든 사례가 전부 같은 분류 항목일 때 멈추게 할 것이다. 만약 모든 사례가 같은 분류항목을 갖는다면, 단말노드(leaf node)또는 마지막 영역을 생성하게 된다.
나중에 C4.5와 CART같은 다른 의사결정 트리 알고리즘을 만나게 될 것이다. 이 알고리즘들은 분할을 할 때마다 사용된 속성을 제거하지 않는다. 이러한 방법은 데이터를 분할하는 데 문제가 된다. 왜냐하면, 속성의 개수가 각 분할을 결정하지 않기 떄문이다.
하지만 걱정할 필요없다. 속성을 다 썻는지 어떤지를 확인하기 위해 데이터 집합에 있는 칼럼개수를 간단하게 셀수 있다. 만약에 데이터 집합에 있는 속성을 다 썻는데도 분류 항목표시의 개수가 같지않다면, 우리는 단말노드를 불러야 할지를 결정해야한다. 이떄 다수결을 사용하게 된다.
def majorityCnt(classList);
classCount={}
for vote in classList:
if vote not in classCount.keys(): classCount[vote]=0
classCount[vote]+=1
sortedClassCount=sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
---> 이 딕셔너리의 대상은 classList에서 각각의 분류항목에 대한 발생 빈도이다. 마지막으로 사전을 정렬하고 발생빈도가 가장 큰 분류항목을 반환한다.
<트리 만들기 코드>
def createTree(dataSet, labels):classList=[example[-1] for example in dataSet]
if classList.count(classList[0])==len(classList):
return classList[0]
if len(dataSet[0])==1:
return majorityCnt(classList)
bestFeat=chooseBestFeatureToSplit(dataSet)
bestFeatLabel=labels[bestFeat]
myTree={bestFeatLabel:{}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
-->처음에는 데이터 집합에 있는 모든 분류 항목 표시의 리스트를 생성하고 classList를 호출한다. 첫번째 멈춤 조건은 모든 분류 항목표시가 같다면 그 분류 항목 표시를 반환하는 것이다.
두 번째 멈춤 조건은 더 이상 분류할 속성이 없는 경우이다. 만약에 멈춤 조건을 만나지 않는다면 chooseBestFeatureToSplit()으로 가장 좋은 속성을 선택하도록 한다
여기서는 트리를 저장하기 위해 파이썬 딕셔너리를 사용한다. myTree 딕셔너리는 트리를 저장하는데 사용하게 되며, 곧 이를 확인하게 될 것이다.
우리는 속성을 선택하기 위해 데이터 집합으로 부터 유일한 모든 값을 구하여 bestFeat에 넣는다.
uniqueVals코드는 집합 유형을 사용한다.
마지막으로 선택한 속성의 유일한 모든 값을 반복 처리하며, 데이터 집합을 분할할 때마다 재귀적으로 createTree()를 호출한다. 이 값은 myTree딕셔너리로 삽입되고 그 결과 많이 중첩된 딕셔너리를 트리로 표현하게 된다.
subLabels=labels[:]는 중첩이 이루어지기 전에 labels의 복사물을 만들고, 새롭게 생성된 리스트에서 subLabels를 호출한다는 것에 주의해야한다.
이렇게 해야 파이썬이 참조 방식으로 리스트를 처리하게 되며 createTree()를 호출할 때마다 원본 리스트와 같은 값을 유지할 수 있게 된다.
2. 매스플롯라이브러리 주석으로 파이썬에서 트리 플롯하기
2.1 매스플롯라이브러리 주석
이 도구에서는 텍스트를 표현하기 위해 데이터에 없는 일정 거리의 화살표를 사용하여 데이터가 무엇을 이야기하는지 설명한다.
<텍스트 주석을 가진 트리 노드 플롯하기>
import matplotlib.pyplot as plt
decisionNode=dict(boxstyle="sawtooth", fc="0.8")
leafNode=dict(boxstyle="round4", fc="0.8")
arrow_args=dict(arrowstyle="<-")
---->위 코드는 노드의 서식을 설정하는데 사용될 몇가지 상수를 정의 한다.
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.ax1.annotate(nodeTxt, xy=parentPt,
xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="ceneter", bbox=nodeType,
arrowprops=arrow_args)
def createPlot():
fig = plt.figure(1, facecolor='white')
fig.clf()
createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
plotNode('a decision node', (0.5, 0.1), (0.1, 0.5), decisionNode)
plotNode('a leaf node', (0.8, 0.1), (0.3, 0.8), leafNode)
plt.show()
<주석 트리 구축하기>
이제 모든 노드를 어디에 배치해야 할 것인가? 일단, 단말노드가 얼마나 있는지 알아야 X축 방향에서 적당한 크기로 화살표를 그릴 수 있게 될 것이며, 단계가 얼마나 있는지 알아야 Y축 방향에서 적당한 크기로 화살표를 그릴 수 있게 될 것이다.
이 함수 둘은 getNumLeafs()와 getTreeDepth()이다.
def getNumLeafs(myTree):
numLeafs=0
firstStr=myTree.keys()[0]
secondDict=myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':
numLeafs+=getNumLeafs(secondDict[key])
else: numLeafs+=1
return numLeafs
--->첫번째 키는 최초로 분할할 분류 항목 표시이고, 이 값음 처음 노드의 자식 노드와 연결된다. 우리는 첫번째 키와 값을 구한다음, 모든 자식 노드 만큼 반복한다. 그런다음 파이썬이 type()메소드를 사용하여, 자식 노드가 딕셔너리인지 확인하기 위한 검사를 한다.
만약 딕셔너리라면 getNumLeafs()를 재귀적으로 호출하여 모든 트리를 순회하며 단말 노드의 갯수를 세고 그 갯수를 반환한다.
def getTreeDepth(myTree):
maxDepth=0
firstStr=myTree.keys()[0]
secondDict=myTree[firstStr]
for key in secondDist.keys():
if type(secondDict[key]).__name__=='dict':
thisDepth=1+getTreeDepth(secondDict[key])
else: thisDepth=1
if thisDepth > maxDepth : maxDepth=thisDepth
return maxDepth
3. 분류기 검사와 저장
이 주제는 트리를 사용하여 분류기를 구축하는 것이다. 그런 다음, 실제 응용 프로그램에서 분류기를 디스크에 장기간 저장해 놓을 수 있는 방법을 알아볼 것이다.
3.1 검사: 분류를 위한 트리 사용
<기존의 의사결정 트리를 위한 분류함수>
def classify(inputTree,featLabels,testVec):
firstStr=inputTree.keys()[0]
secondDict=inputTree[firstStr]
featIndex=featLabels.index(firstStr) <<-색인을 위한 분류 항목 표시 문자열 변환
for key in secondDIct.keys():
if testVec[featIndex]==key:
if type(secondDict[key]).__name__=='dict':
classLabel=classify(secondDict[key], featLabels, testVec)
else: classLabel=secondDict[key]
return classLabel
--> 위 코드는 다른 재귀함수들과 같은 형태이다. 속성 식별자처럼 분류 항목 표시가 있는 데이터를 저장하는 데에는 한 가지 문제가 있다. 그것은 데이터 집합 내에 해당 속성이 어디에 있는지 알 수 없다는 것이다. 이러한 문제를 없애기 위해서 구하고자 하는 속성을 분리해 내면 되겠지만 그 속성은 집합내에 어디에 있을까? 첫번쨰? 두번쨰? Labels목록은 이를 알려 줄 것이다.
이 목록에서 우리는 첫 번째 firstStr과 일치하는 아이템을 알아내기 위해 index방법을 사용한다. 이러한 방법을 재귀적으로 사용하여 트리를 탐색하면서 , testVec에 있는 값을 트리에 있는 값과 비교한다. 그리고 단말 노드에 도달하면 분류를 만들게되고 종료하게 된다.
3.2 사용: 의사결정 트리 계속 유지하기
트리를 구축하는 것은 분류 작업의 대부분을 차지한다. 작은 데이터 집합을 가지고는 몇초밖에 걸리지 않겠지만, 큰 데이터 집합에는 오랜시간이 걸린다. 떄문에 분류를 할 때마다 매번 트리를 구축하는 것은 시간낭비이다.
이것을 해결하기 위해, 즉 객체를 계속해서 사용할 수 있도록 'pickle'이라는 파이썬 모듈을 사용할 것이다.
<pickle을 가지고 의사결정 트리를 유지시키는 방법>
def storeTree(inputTree, filename):
import pickle
fw=open(filename,'w')
pickle.dump(inputTree,fw)
fw.close()
def grabTree(filename):
import pickle
fr=open(filename)
return pickle.load(fr)
댓글
댓글 쓰기