오늘은 트리를 직접 만들어 보는 실습을 하기로 했다. 트리는 의사결정 기술이라고 해서 분류 기술 중 가장 일반적으로 사용되는 기술이라고 한다. 의사결정 트리의 기초가 되는것은 바로 프로그래밍을 하게 되면 종종 보게 되는 플로우차트(flowchart)이다. 얼마 전 내가 토론대회에서 논제결과를 발표했을 때 반론으로 "플로우차트가 비전문가들이 알아보기 힘드니 풀어서 설명해라"라고 나왔는데, Flowchart는 소스코드를 디자인화시킨 것이지 비전문가들에게 완벽하게 코드를 이해시키기 위한 그림이 아니다. 혹시나 헷갈리는 일이 없었으면 한다.

-------------------------------------------------------------------------------------------

* Numpy 기계학습의 모든 문서는 제가 머신러닝을 공부하고, 제 프로젝트에 필요한 알고리즘을 찾기 위해 정리하는 일종의 '요점정리 노트' 입니다. 혹여나 오해 없으시기 바랍니다. (2016.03.14 추가)

-------------------------------------------------------------------------------------------

(출처 : Wikipedia, 문제가 될 경우 다른 사진으로 대체)

플로우차트가 왜 머신러닝에서 언급되냐 하면 데이터 집합을 구분하기 위해 필요하기 때문이다. 의사결정 트리, 즉 플로우차트를 만들기 위해서는 하나의 최초 의사결정을 만들어야 한다. 의사결정의 구조는 다음과 같다.

최초 의사결정은 데이터를 분할하는데 영향을 주는 속성으로 결정되게 되고, 이러한 결정은 모든 속성에 대해 측정을 하면서 얻어지며, 결정된 속성으로 분할하는 경우 가장 좋은 결과를 얻게 되는 것이다. 

그런 다음 데이터 집합을 하위 집합으로 분할한다. 하위 집합은 최초 의사결정의 가지로 모이게 된다. 가지에 있는 데이터가 모두 같은 분류에 속하면 계속 반복하지 않아도 되지만, 만약 그렇지 않다면 그 과정을 다시 반복해야 할 것이다.

이렇게 생기는 데이터 집합을 분할하기 전과 후의 변화를 정보 이득이라고 하며, 데이터 집합에 대한 정보 측정 방법을 섀넌 엔트로피, 줄여서 엔트로피라고 한다. 아마도 정보 이득과 엔트로피라는 용어가 혼란스럽게 들릴 수도 있다. 하지만 이 단어들이 혼란스러운 것은 당연한 이야기이다. 이에 대한 답은 이 글을 읽는 독자들이 알아서 찾아 나가기를 바란다.

우선, 나는 데이터 집합의 엔트로피를 계산하는 함수를 만들어 보기로 하였다. 예제에 나온 소스코드는 다음과 같다.

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2) #log base 2
    return shannonEnt

그 다음 집합을 분할하는 함수를 만들어 보았다. 소스코드는 아래와 같다.

def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1  
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):       
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)   
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)     
        infoGain = baseEntropy - newEntropy  
        if (infoGain > bestInfoGain):     
            bestInfoGain = infoGain     
            bestFeature = i
    return bestFeature         

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 

최근 Github에 내가 만든 머신러닝 소스코드를 올려 공유하고 있다. 주소는 아래와 같다.

https://github.com/itsss/machinelearning

오늘은 여기까지 하기로 하고, 내일 실제로 동작해보는 것으로 했다.