Python 의사 결정 트 리 C 4.5 알고리즘 구현 예시

왜 C 4.5 알고리즘 으로 개선 해 야 합 니까?
의 원리
C 4.5 알고리즘 은 ID3 알고리즘 에서 개 선 된 것 으로 ID3 알고리즘 과 가장 큰 차이 점 은 특징 선택 에 있어 다르다 는 것 이다.하 나 는 정보 이득 비 를 바탕 으로 하 는 것 이 고 하 나 는 정보 이득 을 바탕 으로 하 는 것 이다.
이렇게 하 는 이 유 는 정보 이득 이 수치 가 비교적 많은 특징(특징 이 많 을 수록 조건 엔트로피(특징 구분 후의 유형 변수의 엔트로피)가 작 을 수록 정보 이득 이 크다)을 선택 하 는 경향 이 있 기 때문이다.따라서 정보 이득 에 분 모 를 추가 합 니 다.이 분 모 는 현재 선택 한 특징의 엔트로피 입 니 다.주의:여 기 는 분류 변수의 엔트로피 가 아 닙 니 다.
이렇게 하면 새로운 특징 선택 준칙 을 구성 하여 정보 이득 비 라 고 한다.왜 이런 분 모 를 추가 하면 ID3 알고리즘 이 수치 가 많은 특징 을 선택 하 는 경향 을 없 앨 수 있 습 니까?
특징 수치 가 많 을 수록 이 특징의 엔트로피 가 커지 고 분모 도 커지 기 때문에 정보 이득 비 는 줄 어 들 것 이다.정보 이득 처럼 커지 는 것 이 아니 라 어느 정도 에 알고리즘 이 특징 수치 범위 에 미 치 는 영향 을 없 앨 것 이다.
이루어지다
알고리즘 실현 에 있어 C 4.5 알고리즘 은 정보 이득 계산 함수 calcShannonEntOfFeature 와 최 적 특징 선택 함수 choose BestFeatureToSplit 만 수정 하 였 습 니 다.
calcShannonEntOfFeature 는 ID3 의 calcShannonEnt 함수 에 매개 변수 feat 를 추 가 했 습 니 다.ID3 에서 이 함 수 는 유형 변수의 엔트로피 만 계산 하고 calcShannonEntOfFeature 는 지정 한 특징 이나 유형 변수의 엔트로피 를 계산 할 수 있 습 니 다.
choose BestFeatureToSplit 함 수 는 정보 이득 을 계산 한 후에 현재 특징의 엔트로피 IV 를 계산 한 다음 에 정보 이득 비 를 제외 하고 최대 정보 이득 비 를 최 우선 특징 으로 한다.
데 이 터 를 구분 할 때 특징 이 같은 값 을 취 할 수 있 습 니 다.그러면 이 특징의 엔트로피 는 0 이 고 정보 이득 도 0(유형 변 수 는 앞 뒤 를 나 누 는 것 과 같 습 니 다.특징 은 하나의 수치 만 있 기 때 문 입 니 다)이 며 0/0 은 의미 가 없 기 때문에 이 특징 을 뛰 어 넘 을 수 있 습 니 다.

#coding=utf-8
import operator
from math import log
import time
import os, sys
import string

def createDataSet(trainDataFile):
 print trainDataFile
 dataSet = []
 try:
 fin = open(trainDataFile)
 for line in fin:
  line = line.strip()
  cols = line.split('\t')
  row = [cols[1], cols[2], cols[3], cols[4], cols[5], cols[6], cols[7], cols[8], cols[9], cols[10], cols[0]]
  dataSet.append(row)
  #print row
 except:
 print 'Usage xxx.py trainDataFilePath'
 sys.exit()
 labels = ['cip1', 'cip2', 'cip3', 'cip4', 'sip1', 'sip2', 'sip3', 'sip4', 'sport', 'domain']
 print 'dataSetlen', len(dataSet)
 return dataSet, labels

#calc shannon entropy of label or feature
def calcShannonEntOfFeature(dataSet, feat):
 numEntries = len(dataSet)
 labelCounts = {}
 for feaVec in dataSet:
 currentLabel = feaVec[feat]
 if currentLabel not in labelCounts:
  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

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 #last col is label
 baseEntropy = calcShannonEntOfFeature(dataSet, -1)
 bestInfoGainRate = 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 *calcShannonEntOfFeature(subDataSet, -1) #calc conditional entropy
 infoGain = baseEntropy - newEntropy
 　　 iv = calcShannonEntOfFeature(dataSet, i)
 if(iv == 0): #value of the feature is all same,infoGain and iv all equal 0, skip the feature
 continue
 　　 infoGainRate = infoGain / iv
 if infoGainRate > bestInfoGainRate:
  bestInfoGainRate = infoGainRate
  bestFeature = i
 return bestFeature
  
#feature is exhaustive, reture what you want label
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): #all data is the same label
 return classList[0]
 if len(dataSet[0]) == 1: #all feature is exhaustive
 return majorityCnt(classList)
 bestFeat = chooseBestFeatureToSplit(dataSet)
 bestFeatLabel = labels[bestFeat]
 if(bestFeat == -1): #    ，      ，         ，             
 return classList[0] 
 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():
 if(len(sys.argv) < 3):
 print 'Usage xxx.py trainSet outputTreeFile'
 sys.exit()
 data,label = createDataSet(sys.argv[1])
 t1 = time.clock()
 myTree = createTree(data,label)
 t2 = time.clock()
 fout = open(sys.argv[2], 'w')
 fout.write(str(myTree))
 fout.close()
 print 'execute for ',t2-t1
if __name__=='__main__':
 main()

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.