python으로 구현된 분류 트리

이 문서는 python으로 의사결정 트리를 구현하는 구체적인 코드를 공유하여 참고하였습니다.

알고리즘의 장단점:

점점: 계산 복잡도가 낮고, 출력 결과가 이해하기 쉽습니다. 중간 값이 부족하지 않으며, 불관련 특징 데이터를 처리할 수 있습니다

단점: 과적합 문제가 발생할 수 있습니다

적용 가능한 데이터 유형: 숫자型和 이름형

알고리즘 원칙:

1. 의사결정 트리 구성의 전체적인 원칙:

의사결정 트리는 단순히 if-else 구조는 같지만, 결과는 뿌리에서 시작하여 끝까지 지속적으로 선택할 수 있는 트리를 생성하겠다는 것입니다. 하지만 이곳의 if-else는 우리가 설정하려고 생각하는 것이 아닙니다. 우리가 해야 할 것은 컴퓨터가 이 방법을 통해 우리가 필요로 하는 의사결정 트리를 얻을 수 있는 방법을 제공하는 것입니다. 이 방법의 중요한 부분은 많은 특징 중에서 가치가 있는 특징을 선택하고, 뿌리에서 끝까지 최선의 순서로 선택하는 것입니다. 이를 완료하면 재귀적으로 의사결정 트리를 구성할 수 있습니다.

2. 정보 증가

데이터 집합을 구분하는 가장 큰 원칙은 비정리된 데이터를 더 정리된 데이터로 만드는 것입니다. 이는 정보의 정리된 비정리된 문제와 관련이 있으므로, 자연스럽게 정보 엔트로피를 생각하게 됩니다. 여기서 계산하는 것도 정보 엔트로피입니다. (다른 방법은 기니 불순도입니다.) 공식은 다음과 같습니다:

데이터가 만족해야 할 요구사항:

1 데이터는 목록 요소로 구성된 목록이어야 하며, 모든 열의 요소는 동일한 데이터 길이를 가져야 합니다.
2 데이터의 마지막 열이나 각 예시의 마지막 요소는 현재 예시의 카테고리 태그여야 합니다.

함수:

calcShannonEnt(dataSet)

데이터 집합의 셰놀린 엔트로피를 계산하는 것은 두 단계로 이루어져 있습니다. 첫 번째 단계는 빈도를 계산하고, 두 번째 단계는 공식에 따라 셰놀린 엔트로피를 계산합니다.

splitDataSet(dataSet, aixs, value)

데이터 집합을 구분하며, X[aixs] == value를 만족하는 값들을 모두 하나의 집합에 묶어서 반환합니다. (구분을 위해 사용된 aixs 속성은 포함하지 않습니다.)

chooseBestFeature(dataSet)

最好의 속성을 선택하여 구분하는 방법은 간단합니다. 각 속성에 대해 구분하여 보고 어느 것이 좋은지 확인하는 것입니다. 이곳에서는 독립적인 요소를 선택하기 위해 set을 사용하며, 이는 매우 빠른 방법입니다.

majorityCnt(classList)

우리가 재귀적으로 결정 트리를 구축할 때는 특성의 소모를 계산하기 때문에, 마지막으로 특성이 소모되었지만 분류가 아직 완료되지 않은 경우, 많은 표결 방식으로 노드 분류를 계산할 수 있습니다.

createTree(dataSet, labels)

기반으로 재귀적으로 구축된 결정 트리. 여기서 label은 주로 분류 특성 이름을 의미하며, 더 나은 시각적 효과와 이해를 위해 사용됩니다.

#coding=utf-8
import operator
from math import log
import time
def createDataSet():
  dataSet=[[1,1,'yes'],
      [1,1,'yes'],
      [1,0,'no'],
      [0,1,'no'],
      [0,1,'no']]
  labels = ['no surfaceing','flippers']
  return dataSet, labels
#计算香农熵
def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {}
  for feaVec in dataSet:
    currentLabel = feaVec[-1]
    if currentLabel not in labelCounts:
      labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
  shannonEnt = 0.0
  for key in labelCounts:
    prob = float(labelCounts[key])/numEntries
    shannonEnt -= * log(prob, 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 += * calcShannonEnt(subDataSet)
    infoGain = baseEntropy -newEntropy
    if infoGain > bestInfoGain:
      bestInfoGain = infoGain
      bestFeature = i
  return bestFeature
#因为我们递归构建决策树是根据属性的消耗进行计算的，所以可能会存在最后属性用完了，但是分类
#还是没有算完，这时候就会采用多数表决的方式计算节点分类
def majorityCnt(classList):
  classCount = {}
  for vote in classList:
    if vote not in classCount.keys():
      classCount[vote] = 0
    classCount[vote] += 1
  return max(classCount)     
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
def main():
  data,label = createDataSet()
  t1 = time.clock()
  myTree = createTree(data,label)
  t2 = time.clock()
  print myTree
  print 'execute for ',t2-t1
if __name__=='__main__':
  main()

이것이 이 문서의 전체 내용입니다. 여러분의 학습에 도움이 되길 바라며, 또한 다음에도 지지해 주시기를 바랍니다.呐喊 교본을 많이 지지해 주세요.

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