English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Primeiro, princípio da árvore de decisão
A árvore de decisão é uma estrutura em forma de árvore usada onde os atributos dos exemplos são usados como nós e os valores dos atributos são usados como ramos.
O nó raiz da árvore de decisão é o atributo com a maior quantidade de informação entre todos os exemplos. O nó intermediário da árvore de decisão é o atributo com a maior quantidade de informação entre os subconjuntos de exemplos que o nó raiz governa. O nó folha da árvore de decisão é o valor da classe do exemplo. A árvore de decisão é uma forma de representação de conhecimento, que é uma alta abstração de todos os dados de exemplo. A árvore de decisão pode identificar com precisão todas as classes dos exemplos e também pode identificar eficazmente as classes de novos exemplos.
Algoritmo de árvore de decisão ID3A ideia básica é:
Primeiro, encontrar o atributo com a maior capacidade discriminativa, dividir os exemplos em múltiplos subconjuntos, e para cada subconjunto escolher o atributo com a maior capacidade discriminativa para a divisão, continuando até que todos os subconjuntos contenham apenas dados do mesmo tipo. Finalmente, obter uma árvore de decisão.
O trabalho de J.R. Quinlan consistiu principalmente em introduzir o conceito de增益 (information gain) da teoria da informação, que ele chamou de增益 (information gain), como uma medida da capacidade discriminativa, e projetou um algoritmo recursivo para construir árvores de decisão.
Um exemplo é mais fácil de entender:
Para problemas de classificação climática, o atributo é:
Clima (A1) Valores possíveis: Claridade, Nublado, Chuva
Temperatura (A2Os valores são: Frio, Moderado, Quente
Umidade (A3) Valores: Alto, Normal
Vento (A4) Valores: com vento, sem vento
Cada exemplo pertence a uma classe diferente, neste exemplo há apenas duas classes, P e N. Exemplos de P e N são chamados de exemplos positivos e negativos. Colocar alguns exemplos positivos e negativos conhecidos juntos forma o conjunto de treinamento.
De ID3O algoritmo gera uma árvore de decisão correta para cada exemplo no conjunto de treinamento, como mostrado na figura a seguir.
As folhas da árvore de decisão são nomes de classes, ou seja, P ou N. Outros nós são compostos por atributos do exemplo, cada valor diferente de um atributo corresponde a uma ramificação.
Para classificar um exemplo, comece pelo nó raiz e faça testes nas ramificações de valores de atributos, vá para o nó inferior até o nó folha, e o exemplo será classificado como pertencente à classe do nó folha;
Agora use a imagem para classificar um exemplo específico:
A descrição climática de uma manhã em determinado dia é:
Clima: Nublado
Temperatura: Frio
Umidade: Normal
Vento: Sem vento
Então, qual é o clima a que ele pertence?63;-------------Pode ser determinado a classe do exemplo como P classe.
ID3Para construir a árvore de decisão a partir do conjunto de treinamento da tabela, na verdade, existem várias árvores de decisão que podem classificar corretamente o conjunto de treinamento. O ID de Quinlan3O algoritmo pode gerar a árvore de decisão com o menor número de nós.
ID3Algoritmo:
1. Para o conjunto atual de exemplos, calcule o ganho de informação de cada atributo;
2. Escolha o atributo Ak com o maior ganho de informação;
3. Coloque exemplos com valores iguais no A no mesmo subconjunto, quantos valores A tenha, quantas subconjuntos teremos;
4. Para subconjuntos que contêm tanto exemplos positivos quanto negativos, chame recursivamente o algoritmo de construção de árvore;
5. Se o subconjunto contiver apenas exemplos positivos ou negativos, insira P ou N na ramificação correspondente e retorne ao chamador.
Geralmente, sempre que envolve a estrutura de árvore, frequentemente é necessário usar recursão.
Para calcular especificamente o problema de classificação climática, temos:
1e cálculo da entropia da informação: onde S é o conjunto de exemplos, P(ui) é a probabilidade de ocorrência da classe i:
|S| representa o número total de exemplos no conjunto S, |ui| representa o número de exemplos da classe ui. Para9exemplos positivos e5exemplos negativos:
P(u1)=(9/14
P(u2)=(5/14
H(S)=(9/14)=log(14/9)+(5/14)=log(14/5)=0.94bit
2e cálculo do ganho de informação:
onde A é o atributo, Value(A) é o conjunto de valores do atributo A, v é um valor de atributo A, Sv é o conjunto de exemplos em S onde o valor de A é v, | Sv | é o número de exemplos no Sv.
com base no atributo A1Por exemplo, com base na fórmula de cálculo do ganho de informação, o atributo A1a informação de ganho é
S=[9+,5-] //No conjunto de exemplos originais há14exemplos，9exemplos positivos，5exemplos negativos
S_ensolarado=[2+,3-]//e resultado é1Exemplos de tempo ensolarado são5个，2，3正
S_nublado=[4+,0-] //e resultado é1Exemplos de tempo nublado são4个，4正，0反
S_chuva=[3+,2-] //e resultado é1Exemplos de tempo ensolarado são5个，3，2正
反
3Portanto
e resultado é1Atributo A
4e constrói a raiz e as folhas da árvore de decisão, cujo ganho de informação é o maior, então é escolhido como nó raiz.
ID3O algoritmo escolhe o atributo de ganho de informação maior, 'weather', como a raiz da árvore de decisão, em14examples to weather's3branches are made for3 corresponding branches3 subsets are:
where S2All examples in S belong to P class, so the corresponding branch is marked as P, and the other two subsets contain both positive and negative examples, and the recursive tree construction algorithm is called.
5Recursive tree construction
respectively for S1and S3Subset recursive call ID3The algorithm calculates the information gain of each attribute in each subset.
(1) for S1The humidity attribute has the maximum information gain, so it is used as the root node of this branch, and further branching. High humidity examples are all N classes, and this branch is marked as N. Normal value examples are all P classes, and this branch is marked as P.
(2) for S3The wind attribute has the maximum information gain, so it is used as the root node of this branch. Further branching, wind takes all N classes when there is wind, and this branch is marked as N. When there is no wind, all are P classes, and this branch is marked as P.
Two, implement the decision tree algorithm classification in PYTHON
This code is an example from chapter 3 of machine learning in action, tested and proven correct.
1Function to calculate the shannon value of the given data:
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. Function to create data
def createDataSet():
dataSet = [[1,1']
[1,1, 'yes']
[1,0,'no']
[0,1']
[0,1']
labels = ['no surfacing','flippers']
return dataSet, labels
3.dividir o conjunto de dados, dividindo o conjunto de dados com base no caractere específico
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.escolha do melhor método de divisão de conjunto de dados
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) novaEntropia = 0.0 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i , value) prob = len(subDataSet)/float(len(dataSet)) novaEntropia +=prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - novaEntropia if(infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature
5.criação recursiva de árvores
função usada para encontrar o nome da classe que ocorre mais vezes
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]
função de código usada para criar árvores
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
#o tipo é o mesmo, então pare de classificar
if classList.count(classList[0]) == len(classList):
return classList[0]
#traverse todas as características e escolher a característica mais frequente
if (len(dataSet[0]) == 1)
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
#obter a lista que atingiu todas as propriedades
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
Então, na entrada de comando de prompt de nome e sinal do python, insira o seguinte:
myDat, labels = trees.createDataSet() myTree = trees.createTree(myDat, labels) print myTree
O resultado é:
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
6.função prática para classificação de árvores de decisão
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
No prompt de comando do Python, digite:
trees.classify(myTree, labels,[1,0])
Obter resultado:
'no'
Parabéns. Oh yeah. Você acertou.!!!
Isso é tudo o que há no artigo. Espero que ajude no seu aprendizado e que você apóie o tutorial Grito.
Declaração: o conteúdo deste artigo é de internet, pertencente ao respectivo proprietário. O conteúdo é contribuído e carregado voluntariamente pelos usuários da internet. Este site não possui direitos autorais, não foi editado manualmente e não assume responsabilidades legais relacionadas. Se você encontrar conteúdo suspeito de direitos autorais, por favor, envie um e-mail para: notice#oldtoolbag.com (ao enviar e-mail, substitua # por @ para denunciar e forneça provas relevantes. Caso seja confirmado, o site deletará imediatamente o conteúdo suspeito de infringir direitos autorais.)