Python 기계 학습의 결정 트리 알고리즘

1. 결정 트리 원리

결정 트리는 샘플의 속성을 노드로 사용하고, 속성의 값을 분기로 사용하는 트리 구조입니다.
결정 트리의 루트 노드는 모든 샘플 중 정보량이 가장 큰 속성입니다. 트리의 중간 노드는 이 노드가 루트로 사용된 자식 트리가 포함하는 샘플 자집에서 정보량이 가장 큰 속성입니다. 결정 트리의 잎 노드는 샘플의 범주 값입니다. 결정 트리는 모든 샘플 데이터를 극도로 요약한 지식 표현 형식입니다. 결정 트리는 모든 샘플의 범주를 정확하게 인식할 수 있으며, 새 샘플의 범주를 효과적으로 인식할 수 있습니다.　

결정 트리 알고리즘 ID3의 기본 아이디어는:

먼저 가장 판별력 있는 속성을 찾아서 예제를 여러个子집으로 나누고, 각个子집은 다시 가장 판별력 있는 속성을 선택하여 나누어서 진행하고, 모든个子집이 동일한 유형의 데이터만을 포함하는까지 계속합니다. 결국 결정 트리를 얻습니다.

J.R.Quinlan의 주요 업적은 정보 이론의 정보 이득을 도입했으며, 이를 정보 이득(information gain)이라고 불렀고, 속성의 판별 능력을 측정하는 데 사용하여 결정 트리를 구성하는 재귀 알고리즘을 설계했습니다.

예시를 들어 이해하기 쉽다:

기후 분류 문제에 대해, 속성은:
날씨(A1값은: 맑음, 구름 많음, 비
기온(A2값은: 추운, 중간, 더운
湿度(A3습도(A
) 값이 있습니다: 높음, 정상4바람 (A

) 값이 있습니다: 바람이 있는 경우, 바람이 없는 경우
각 예제는 다른 분류에 속합니다. 이 예제에는 두 가지 분류가 있습니다. P과 N입니다. P류와 N류의 예제는 각각 참예제와 반대예제라고 합니다. 몇 가지 알려진 참예제와 반대예제를 모아 훈련 집합을 구성합니다.3ID

알고리즘은 훈련 집합에서 각 예제를 올바르게 분류하는 결정 트리를 생성할 수 있습니다. 다음 그림을 참조하세요.
결정 트리의 잎은 분류 이름입니다. 즉 P 또는 N입니다. 다른 결점은 예제의 속성으로 구성되며, 각 속성의 다른 값은 하나의 분기를 나타냅니다.
예제를 분류하려면 트리 뿌리에서 시작하여 속성의 값에 따라 분기하여 하위 결점으로 내려가며, 결점을 테스트하여 과정을 계속합니다. 예제는 해당 결점에 표시된 분류에 속하게 됩니다.
이제 그림을 사용하여 특정 예제를 판단해 보겠습니다;
그날 아침 기후 설명은:
날씨: 구름많음
기온: 추운
습도: 정상

바람: 무바람63그렇다면 이 예제가 어느 기후류에 속하는지 알 수 없습니다.-------------;　

ID3Quinlan의 ID를 사용하여 그림에서 해당 예제의 분류를 P류로 판단할 수 있습니다.3결점이 가장 적은 결정 트리를 얻을 수 있습니다.

ID3알고리즘:

　　　　　1. 현재 예제 집합에 대해 각 속성의 정보수득을 계산합니다;
　　　　　2. 정보수득이 가장 큰 속성 Ak을 선택합니다;
　　　　　3. Ak에서 값이 같은 예제를 동일한 자식 집합에 분류합니다. Ak이 몇 가지 값을 가르면 몇 가지 자식 집합이 됩니다;
　　　　 4. 참예제와 반대예제를 모두 포함한 자식 집합에 대해 재귀적으로 결정 트리 구축 알고리즘을 호출합니다;
　　　　　5. 자식 집합이 참예제나 반대예제만 포함되면, 해당 분기에 P나 N을 표시하고 호출된 위치로 반환합니다.

기후 분류 문제에 대해 구체적으로 계산하면 다음과 같습니다:　

S는 예제 집합입니다. P(ui)는 분류 i가 나타나는 확률입니다:
1정보entropy 계산:

|S|는 예제 집합 S의 총 수를 나타냅니다. |ui|는 분류 ui의 예제 수를 나타냅니다.9개 참예제와5개 반대예제가 있습니다:
P(u1)=9/14
P(u2)=5/14
H(S)=(9/14)=log(14/9)+（5/14)=log(14/5)=0.94비트　

2정보수득 계산:

A는 속성입니다. Value(A)는 속성A의 값을 가진 집합입니다. v는 A의 일정한 속성 값입니다. Sv는 S에서 A의 값이 v인 예제 집합입니다. |Sv|는 Sv에 포함된 예제 수입니다.

속성A를1예를 들어, 정보수득 계산 방정식에 따라, 속성A1의 정보수득은

S=[9+,5-] //원본 예제 집합에 총14개 예제가 있습니다.9개 참예제,5개 반대예제
S맑음=[2+,3-]//속성A1맑음의 값이 있는 예제는 총5개2참3반대
S구름많음=[4+,0-] //속성A1구름많음의 값이 있는 예제는 총4개4참, 0반대
S우산=[3+,2-] //속성A1맑음의 값이 있는 예제는 총5개3참2반대
따라서　

3결과가

속성A1의 정보수득이 가장 큰 것으로 선택되었습니다.

4빌드 결정 트리의 뿌리와 잎을

ID3알고리즘은 정보수득이 가장 큰 속성 날씨를 트리 뿌리로 선택하고,14각 예제에서 날씨의3각 값에 대해 분기합니다.3 각 분기점에 대해3 각각은:

서브셋2서브셋에서 모든 예제가 P류에 속하므로, 해당 분기점을 P으로 표시합니다. 나머지 두 서브셋에는 양성 예제와 음성 예제가 모두 포함되어 있어, 트리 구성 알고리즘을 재귀적으로 호출합니다.

5에 대해 재귀적으로 트리를 구성합니다.

에 대해 각각1와 S3서브셋에 대해 ID를 재귀적으로 호출합니다.3알고리즘은 각 서브셋에서 각 속성에 대해 정보 증가율을 계산합니다.
（1）S에 대한1에 대한 풍속 정보 증가율이 가장 크므로 그것을 분기점의 뿌리로 사용합니다. 그런 다음, 풍속이 높은 예제는 모두 N류로, 해당 분기점을 N으로 표시합니다. 값이 평범한 예제는 모두 P류로, 해당 분기점을 P으로 표시합니다.
（2）S에 대한3，풍속 정보 증가율이 가장 크므로 그것을 분기점으로 사용합니다. 그런 다음, 풍속이 바람이 있을 때 모두 N류로, 해당 분기점을 N으로 표시합니다. 바람이 없을 때 모두 P류로, 해당 분기점을 P으로 표시합니다.

2. PYTHON으로 구현된 결정 트리 알고리즘 분류

이 코드는 machine learning in action 第三章 예제로, 직접 테스트된 결과 무결성이 있습니다.
　1、지정된 데이터셋의 shannon 정보를 계산하는 함수:

def calcShannonEnt(dataSet): 
 # calculate the shannon value 
 numEntries = len(dataSet) 
 labelCounts = {} 
 for featVec in dataSet:  # create the dictionary for all of the data 
  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) # get the log value 
 return shannonEnt 

　2. 데이터 생성 함수

def createDataSet(): 
 dataSet = [[1,1'] 
    [1,1, 'yes'], 
    [1,0,'no'], 
    [0,1'] 
    [0,1'] 
 labels = ['no surfacing','flippers'] 
 return dataSet, labels 

3.按照给定的特征划分数据集

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

4.选择最好的数据集划分方式

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 

5.递归创建树

用于找出出现次数最多的分类名称的函数

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] 

트리를 생성하는 함수 코드

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 

그런 다음 python 명령표시 프롬프트에 다음과 같은 명령을 입력합니다：

myDat, labels = trees.createDataSet() 
myTree = trees.createTree(myDat, labels) 
print myTree 

결과는 다음과 같습니다：
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

6. 실용적인 의사결정 트리를 분류하는 함수

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 

파이썬 명령 프롬프트에서 입력하십시오：
trees.classify(myTree, labels,[1,0])　

결과를 얻었습니다：
'no'
축하합니다. 아하. 당신이 그것을 했습니다.!!!

이것이 이 문서의 전부입니다. 여러분의 학습에 도움이 되길 바랍니다. 또한, 노래教程에 많은 지지를 부탁드립니다.

선언: 이 문서의 내용은 인터넷에서 가져왔으며, 저작권은 원작자에게 있으며, 인터넷 사용자가 자발적으로 기여하고 업로드한 내용으로, 이 사이트는 소유권을 가지지 않으며, 인공적인 편집 처리를 하지 않았으며, 관련 법적 책임도 부담하지 않습니다. 저작권 침해 내용이 있음을 발견하면 notice#w 이메일로 보내 주시기 바랍니다.3codebox.com에 이메일을 보내서 신고해 주시면 (#을 @으로 변경해 주세요) 관련 증거를 제공하시면, 사실이 확인되면 이 사이트는 즉시 저작권 침해 내용을 삭제합니다.