[Data Mining] 의사 결정 트리

1. 의사 결정 트리(Decison Tree)

---

아키네이터라는 게임해보셨나요?? 이상한 요술 램프 지니같이 생긴 캐릭터가 여러 가지를 물으면서 사용자가 생각하는 내용을 맞추는 게임인데요. 짜증 날 정도로 잘 맞춰서 나중에는 엄청 말도 안 되는 걸 생각해서 정신 승리를 추구하려는 주변인+나 자신을 많이 봤습니다. (저도 그러면서 컴퓨터 따위가 감히 내 생각을 맞출 수가 없지 하고 만족했지만...)

저의 조심스러운 추측이지만 아키네이터는 의사 결정 트리를 사용한 게 아닐까 생각이 듭니다. 의사 결정 트리는 일종의 분류기인데 트리를 내려가면서 다양한 질문을 받게 됩니다. 그리고 그 질문의 응답에 따라 어떤 분류에 속하는지를 결론을 내려줍니다. 의사 결정 트리의 장점은 분류 결과를 사람이 쉽게 이해할 수 있다는 겁니다. 왜냐하면 의사 결정 트리는 사람이 생각하는 과정과 매우 유사하기 때문이죠. 예를 하나 봅시다.

 

만약 여러분이 소개팅 주선자이고 소개팅 상대를 물어보는 친구가 있다고 생각합시다. 소개팅을 받는 친구는 아주 설렌 마음에 자기의 이상형에 맞는지 여러분께 계속 물어볼 겁니다. 키는 큰지 돈은 많은지 차는 있는지 잘 생겼는지 성격이 어떤지 말이죠. 질문과 답이 오가는 과정에서 친구는 내 이상형이다 또는 내 이상형이 아니라고 결정을 내리게 됩니다. 그 결정과정을 보여주는 것이 위의 그림입니다. 그림을 보았을 때 어떠한 과정으로 분류를 해나가는지를 쉽게 알 수 있습니다.

의사 결정 트리의 단점은 과적합(Overfitting)이 되기 쉽다는 점입니다. 과적합은 훈련 데이터 내에서는 완전 딱 들어맞는 형태를 보여주지만 새로운 데이터에 대해서 예측 결과가 현저히 떨어지는 현상을 의미합니다.

2. 정보 이득(Infomation Gain)

---

정보 이득은 어떤 순서로 트리를 구성하는 것이 효과적인지를 선정하는 지표로 사용합니다. 위에 소개팅의 예를 들어서 정보 이득의 간단한 개요를 설명해 보겠습니다.

다시 여러분의 친구에게 주변에 좋은 사람을 소개팅하려고 합니다. 위에서 예를 들었던 거와 다른 순서로 질문을 합니다. 키가 큰지 노래를 잘 하는지 말이죠. 전부 다 마음에 드는 상황에서 마지막으로 남자냐고 물었더니 아니라고 대답해 버린 주선자.. 제 친구였으면 아마 반 죽여 버렸을 겁니다. 처음에 남자인지 물어봤으면 그 아래의 내용은 질문할 필요조차 없었는데 말입니다. 이처럼 질문들이 어떤 것이 더욱 결정적이고 변별력 있는지를 수치적으로 계산하는 것이 정보 이득입니다.

정보 이득을 계산하기 위해서는 섀넌 엔트로피라는 개념이 필요합니다. 일반적으로 물리나 수학을 공부하신 분이라면 엔트로피라는 개념이 무질서도를 의미한다는 것을 의미한다는 걸 알고 있을 겁니다. 만약 엔트로피가 크다면 무질서한 정도가 크다는 걸 의미합니다. 이해가 안 된다면 여러분이 지금 제멋대로 막 흩어 놓은 책상을 보시면 됩니다.(정말 지저분하죠?? 엔트로피가 크다는 겁니다.) 

섀넌 엔트로피는 비슷한 의미로 생각하시면 됩니다. 섀넌 엔트로피가 크다는 것은 데이터가 정렬이 아주 안 된 상태를 의미하고 반대로 작다면 데이터가 정렬이 잘 되어 있는 상태를 의미합니다. 살짝 멀미가 나시겠지만 수식으로 섀넌 엔트로피를 확인해 봅시다.

새넌 엔트로피는 위의 식으로 정의합니다. 그림에도 나와 있지만 p(x) 값이 크면 클수록 로그 함수의 결과가 작아짐을 알 수 있습니다. l(x) 값은 항상 음수이기 때문에 H(x)를 구할 때에 부호를 변경하기 위해 음수를 곱해주는 모습도 볼 수 있습니다. 이어서 정보 이득을 구하는 수식도 한꺼번에 계산하는 식을 살펴봅시다.

간단한 예제도 같이 만들어 보았습니다. 한 사람을 대상으로 이상형의 조건에 따라 질문을 하고 그에 대한 답을 얻는 과정입니다. 우선 전체 엔트로피 H(S)를 구하는 과정입니다. 최종 결과인 이상형인 확률과 이상률이 아닐 확률을 구합니다. 각각 4개 중에 2개씩 차지하니까 확률 p(x)는 1/2, 위의 섀넌 엔트로피 공식에 집어넣으니 1이 됩니다. 

이제는 정보 이득을 한번 구해 보겠습니다. 어떤 질문을 먼저 할까 고민하다가 "잘 생겼어?"라는 질문을 먼저 했을 경우에 얼마나 정보이득을 보는지 볼까요?

간단히 설명하면 잘생겼다는 속성을 가진 데이터는 총 3개이며 그중에 이상형인 확률과 아닐 확률을 통해 섀넌 엔트로피를 구합니다. 못생겼다도 마친가지로 진행하면 되겠죠?? 그럼 이번엔 노래를 잘하는가에 대한 질문을 먼저 했을 때 정보 이득을 구해 봅시다.

똑같은 방법을 적용해서 계산을 했더니 잘 생겼다에 대한 질문의 결과보다 정보 이득이 크다는 것을 알 수 있어요. 그 말은 "노래 잘해?"라는 질문이 "잘 생겼어?"라는 질문보다 변별력이 크다는 것을 의미해요. 따라서 트리를 작성할 때 제일 먼저 "노래 잘해?"를 먼저 물어보는 것이 좋겠네요.. 이처럼 정보 이득을 사용하면 질문의 순서를 정하는데 근거가 되어 줄 수 있어요.

3. 구현(python)

---

블로그를 방문하신 분들은 위의 이론들보다 그래서 어떻게 구현하는데? 가 더욱 중요할 겁니다.

구현 순서는 섀넌 엔트로피와 정보 이득을 계산하여 트리를 구성하는 것까지 진행해보겠습니다.

섀넌 엔트로피 계산

from math import log
 
def shannonEntropy(dataSet):
    # 확률 계산할 때 분모로 들어가는 부분
    dataSize = len(dataSet)
    
    # 라벨별로 몇 개씩 있는 지 저장
    labelCount = {}
    entropy = 0.0
    
    # 데이터 집합 중 라벨 별로 몇 개씩 있는지 계산
    for dataLine in dataSet:
        curLabel = dataLine[-1]
        if curLabel not in labelCount.keys():
            labelCount[curLabel] = 0
        labelCount[curLabel] += 1
 
    # 확률 계산 및 섀넌 엔트로피 계산
    for key in labelCount:
        prop = float(labelCount[key]) / dataSize
        entropy -= prop * log(prop, 2)
    
    return entropy    
        

정보이득 계산

"""
    잘 생김, 노래 잘부름 등등 속성 중에서 하나를 선택합니다.
    그 속성 값을 제외한 나머지 값들을 결과로 반환하는 함수입니다.
    (정보이득을 계산하기 위함)
"""
def pickResult(dataSet, index, value):
    result = []
    for dataLine in dataSet:
        if dataLine[index] == value:
            tempVec = dataLine[:index]
            tempVec.extend(dataLine[index+1:])
            result.append(tempVec)
 
    return result
 
# 어떤 질문을 먼저 해야 효율적일지 선별하는 과정
def getBestInfoGainFeat(dataSet):
    baseEntropy = shannonEntropy(dataSet)
    bestInfoGain = 0.0
    index = 0
    numOfFeat = len(dataSet[0]) - 1
    for i in range(numOfFeat):
        featValueSet = set([value[i] for value in dataSet])
        newEntropy = 0.0
        
        # 정보이득을 구하는 과정
        for element in featValueSet:
            subDataSet = pickResult(dataSet, i, element)
            prop = len(subDataSet) / float(len(dataSet))
            newEntropy += prop * shannonEntropy(subDataSet)
        
        infoGain = baseEntropy - newEntropy
        
        if bestInfoGain < infoGain:
            bestInfoGain = infoGain
            index = i
    
    return index      

트리 생성

# 다수결 
def majority(dataSet):
    classCount = {}
    for data in dataSet:
        if data not in classCount.keys():
            classCount[data] = 0
        classCount[data] += 1
    sortedClassCount = sorted(classCount,key=operator.itemgetter(1), reversed=True)
    return sortedClassCount[0][0]
 
 
 
def createTree(dataSet, labels):
    classifyList = [data[-1] for data in dataSet]
 
    # 정지조건 1. 모든 라벨 값이 동일한 경우
    if classifyList.count(classifyList[0]) == len(classifyList):
        return classifyList[0]
 
    # 정지조건 2. 더 이상 분류할 속성이 없는 경우 -> 다수결로 결정
    if len(dataSet[0]) == 1:
        return majority(classifyList)
 
    bestIndex = getBestInfoGainFeat(dataSet)
    bestIndexLabel = labels[bestIndex]
    Tree = {bestIndexLabel : {}}
    del(labels[bestIndex])
    featValue = set([example[bestIndex] for example in dataSet])
    for value in featValue:
        subLabels = labels[:]
        Tree[bestIndexLabel][value] = createTree(pickResult(dataSet, bestIndex, value), subLabels)
        
    return Tree