決定ツリー:ID 3アルゴリズム

クラスタリングアルゴリズム(一)では,K-meansアルゴリズムは多くの分類タスクを遂行できるが,最大の欠点はデータの内在的な意味を与えることができず,決定ツリーの主な形式はデータ形式が非常に理解しやすいことである.
利点:計算の複雑さは高くなく、出力結果は理解しやすく、中間値の欠落に敏感ではなく、関連しない特徴データを処理することができる.
欠点:過剰なマッチングの問題が発生する可能性があります.
≪データ型の使用|Use Data Type|emdw≫:数値型と公称型.
疑似コードは次のとおりです.

                  ：
	if so return    
	else:
		            
		     
		      
			for          
				  creatBranch               
		return     

データセットを分割する大きな原則は、無秩序なデータをより秩序化することです.ID 3アルゴリズムは情報利得値を用いてどの種類のラベルで分類されるかを判断し、情報利得という言葉は20世紀で最も賢い数人の一人であるシャノンによって発明された.
エントロピーは情報の期待値として定義され,この概念を明確にする前に,情報の定義を知らなければならない.エントロピーを計算するには、すべてのカテゴリのすべての可能な値に情報の期待値が含まれていることを計算する必要があります.次の式で得られます.
ここでp(xi)はその分類を選択する確率を表し,log関数曲線からHは必ず正数であることが分かる.Hをシャノンエントロピーと呼び,このエントロピーに基づいてカテゴリごとにエントロピーを求め,差演算を行うことで情報利得を得ることができる.最後に、分類ラベルとして、情報利得の大きいものをラベルとして選択します.(データ・マイニング・ブックと全く同じ考え方)
私はもともとMatplotlibで木の図を描くつもりでしたが、試験がきついので描きません.試験が終わったら、時間があれば補充します.
ソース(Python):

<span style="font-size:14px;">#coding:utf-8

__author__ = 'ChiXu_15s103144_HIT'

from math import log #   log  
import operator

#----------------------------------------------------------#
#                                                      #
#----------------------------------------------------------#
def calcShannonEnt(dataset):
    numEntries = len(dataset) #      
    labelCounts = {}
    #-------------           -------------#
    for featVec in dataset:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): #     key    ,       key 0
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1 #   key    ,key   +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): #    ,        ,        
    recDataSet = [] #     list  
    #----          ,              ----#
    for featVec in dataset:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            recDataSet.append(reducedFeatVec)
    #-------------------------------------------------#
    return recDataSet


#----------------------------------------------------------#
#                                                  #
#----------------------------------------------------------#
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 #  bestFeature                 


#----------------------------------------------------------#
#                                                  #
#----------------------------------------------------------#
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 creatTree(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] = creatTree(splitDataSet(dataset, bestFeat, value), subLabels)
    return myTree


f = open('/Users/John/Documents/dataset/CarEvaluationDataSet/car.data.txt','r')
dataset = []
labels = ['buying', 'maint', 'doors', 'persons', 'lug_boot', 'safety']
line = f.readline()
while line:
    lines = line.split(',')
    lines[-1] = lines[-1][:-1] #     
   
    dataset.append(lines)
    line = f.readline()
print creatTree(dataset, labels)</span><span style="font-size:24px;">
</span>

データセットソース:http://archive.ics.uci.edu/ml/右側にcar evaluationのデータセットがあります