English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Primo: principio dell'albero decisionale
L'albero decisionale è una struttura ad albero in cui l'attributo del campione è il nodo e il valore dell'attributo è il ramo.
Il nodo radice dell'albero decisionale è l'attributo con la maggiore quantità di informazione tra tutti gli esempi. Il nodo intermedio dell'albero decisionale è l'attributo con la maggiore quantità di informazione tra i sottoinsiemi di campioni che hanno come radice il nodo. Il nodo foglia dell'albero decisionale è il valore della categoria del campione. L'albero decisionale è una forma di rappresentazione della conoscenza, che è una高度概括 di tutti i dati di campione. L'albero decisionale può identificare accuratamente la categoria di tutti i campioni e può anche identificare efficacemente la categoria dei nuovi campioni.
L'idea fondamentale dell'algoritmo ID3 dell'albero decisionale:
Prima si trova l'attributo con la maggiore capacità di discriminazione, si dividono i casi in più sottoinsiemi, ogni sottoinsieme sceglie l'attributo con la maggiore capacità di discriminazione per la divisione, e si continua fino a quando tutti i sottoinsiemi contengono solo dati dello stesso tipo. Alla fine si ottiene un albero decisionale.
Il lavoro di J.R.Quinlan ha introdotto il concetto di informazione di增益 dall'informatica delle informazioni, che ha chiamato informazione di增益(information gain), come una misura della capacità di discriminazione dell'attributo, e ha progettato un algoritmo ricorsivo per costruire alberi decisionali.
Esempi concreti sono più facili da capire:
Per il problema di classificazione climatica, le proprietà sono:
Meteo (A1) Valori: soleggiato, nuvoloso, pioggia
Temperatura (A2) Valori: fredda, media, calda
Umidità (A3) Valori: alta, normale
Vento (A4) Valori: con vento, senza vento
Ogni esempio appartiene a una categoria diversa, in questo esempio ci sono solo due categorie, P e N. Gli esempi delle categorie P e N sono chiamati esempi positivi e negativi. Mettendo insieme alcuni esempi positivi e negativi noti si ottiene il set di addestramento.
Un albero decisionale corretto per ogni esempio nel set di addestramento è calcolato dall'algoritmo ID3, come mostrato nella figura sottostante.
Le foglie dell'albero decisionale sono i nomi delle categorie, ovvero P o N. Gli altri nodi sono composti dalle proprietà degli esempi, ogni valore diverso di una proprietà corrisponde a un ramo.
Se si deve classificare un esempio, si inizia dal tronco del albero e si testano i rami in base ai valori delle proprietà, si entra nel nodo inferiore, si testano i nodi, il processo continua fino al nodo foglia, l'esempio viene classificato come appartenente alla categoria del nodo foglia.
Usiamo immagini per giudicare un esempio specifico:
Una descrizione della climate del mattino di un giorno specifico è:
Meteo: nuvoloso
Temperatura: fredda
Umidità: normale
Vento: senza vento
A quale tipo di clima appartiene?---------------------Dal grafico si può distinguere che la classe dell'esempio è P.
ID3 costruisce un albero decisionale come questo da un set di addestramento di tabelle. In realtà, ci sono più alberi decisionali che possono classificare correttamente il set di addestramento. L'algoritmo ID3 di Quinlan può produrre un albero con il minor numero di nodi.
Algoritmo ID3:
1. Per il set di esempi corrente, calcola il guadagno informativo di ciascun attributo;
2. Scegli l'attributo Ak con il guadagno informativo maggiore;
3. Assegna gli esempi con lo stesso valore di Ak a uno stesso sottoinsieme, il numero di valori di Ak determina il numero di sottoinsiemi;
4. Per i sottoinsiemi che contengono sia esempi positivi che negativi, si chiama ricorsivamente l'algoritmo di costruzione dell'albero;
5. Se il sottoinsieme contiene solo esempi positivi o negativi, contrassegna la ramificazione con P o N e torna alla chiamata.
In generale, quando si tratta di alberi, si utilizza spesso la ricorsione.
Per il problema di classificazione climatica, i calcoli specifici sono:
1. Calcolo dell'entropia informativa: dove S è l'insieme degli esempi, P(ui) è la probabilità di apparizione della classe i:
|S| rappresenta il numero totale di esempi nel set di esempi S, |ui| rappresenta il numero di esempi della classe ui. Per 9 esempi positivi e 5 esempi negativi:
P(u1) = 9/14
P(u2) = 5/14
H(S) = (9/14)log(14/9) + (5/14)log(14/5) = 0.94bit
2. Calcolo del guadagno informativo:
Dove A è l'attributo, Value(A) è l'insieme dei valori dell'attributo A, v è un valore dell'attributo A, Sv è l'insieme degli esempi in S con il valore dell'attributo A v, | Sv | è il numero di esempi nel Sv.
Prendendo l'attributo A1 come esempio, secondo la formula di calcolo del guadagno informativo, l'informazione di guadagno dell'attributo A1 è
S=[9+,5-] // Il set di esempi originale contiene in totale 14 esempi, 9 esempi positivi, 5 esempi negativi
Chiaro=[2+,3-]// Gli esempi con valore del属性A1 chiaro sono in totale 5, 2 positivi, 3 negativi
Nuvoloso=[4+,0-] // Gli esempi con valore del属性A1 nuvoloso sono in totale 4, 4 positivi, 0 negativi
Spioggia=[3+,2-] // Gli esempi con valore del属性A1 chiaro sono in totale 5, 3 positivi, 2 negativi
Quindi
3. Il risultato è
L'informazione di guadagno dell'attributo A1 è maggiore, quindi è scelto come nodo radice.
4. Costruzione della radice e delle foglie della decisione dell'albero
L'algoritmo ID3 seleziona l'attributo della temperatura con il guadagno informativo maggiore come nodo radice dell'albero, ramifica i tre valori della temperatura in 14 esempi, e le tre ramificazioni corrispondono a tre sottoinsiemi, rispettivamente:
Tutti gli esempi in S2 appartengono alla classe P, quindi la ramificazione corrispondente è contrassegnata con P, mentre gli altri due sottoinsiemi contengono sia esempi positivi che negativi, pertanto si chiama ricorsivamente l'algoritmo di costruzione dell'albero.
5. Costruzione ricorsiva dell'albero
Si chiama ricorsivamente l'algoritmo ID3 per i sottoinsiemi S1 e S3, e si calcola l'informazione di guadagno per ciascun attributo in ciascun sottoinsieme.
(1) Per S1, l'informazione di guadagno della proprietà dell'umidità è maggiore, quindi è scelta come il nodo radice di questa ramificazione e si ramifica ulteriormente. Gli esempi con umidità alta appartengono tutti alla classe N, la ramificazione è contrassegnata con N. Gli esempi con valore normale appartengono tutti alla classe P, la ramificazione è contrassegnata con P.
（2）对S3，风属性信息增益最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。
二、PYTHON实现决策树算法分类
本代码为machine learning in action 第三章例子，亲测无误。
1、计算给定数据shangnon数据的函数：
def calcShannonEnt(dataSet):
#calcolare il valore shannon
numEntries = len(dataSet)
labelCounts = {}
per featVec in dataSet: #creare il dizionario per tutti i dati
currentLabel = featVec[-1]
se currentLabel non è in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
per key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob*log(prob,2) #ottenere il valore logaritmico
ritorna shannonEnt
2. Funzione per creare dati
def createDataSet():
dataSet = [[1,1,'sì'],
[1,1, 'sì'],
[1,0,'nessuna'],
[0,1,'nessuna'],
[0,1,'nessuna']]
labels = ['nessuna emersione','pinne']
ritorna dataSet, labels
3. Dividere il set di dati, secondo il caratteristica fornita per dividere il set di dati
def splitDataSet(dataSet, axis, value): retDataSet = [] per featVec in dataSet: segnalato che featVec[axis] == value: #estrarre la caratteristica reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
4. Scegliere il modo migliore per dividere il set di dati
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. Creazione ricorsiva dell'albero
funzione utilizzata per trovare il nome della categoria che si ripete di più
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]
funzione per creare un albero di codice
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
#lo stesso tipo, quindi fermati con la classificazione
if classList.count(classList[0]) == len(classList):
return classList[0]
#esplora tutte le caratteristiche e scegli la più frequente
if (len(dataSet[0]) == 1):
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
#ottieni l'elenco delle proprietà complete
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
Poi, nel prompt Python, inserisci il comando seguente:
myDat, labels = trees.createDataSet() myTree = trees.createTree(myDat, labels) print myTree
Risultato:
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
6. Funzione pratica per la classificazione con albero decisionale
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
In prompt Python, inserisci:
trees.classify(myTree, labels, [1, 0])
Risultato ottenuto:
'no'
Congratulazioni. Oh yeah. Hai fatto.!!!
Questo è tutto il contenuto dell'articolo, speriamo che sia utile per la tua apprendimento e che tu supporti fortemente la guida Yell.
Dichiarazione: il contenuto di questo articolo è stato tratto da Internet, di proprietà del rispettivo autore. Il contenuto è stato contribuito e caricato autonomamente dagli utenti di Internet, il sito web non detiene i diritti di proprietà, non è stato editato manualmente e non assume responsabilità legali correlate. Se trovi contenuti sospetti di violazione del copyright, ti preghiamo di inviare una e-mail a notice#oldtoolbag.com (al momento dell'invio dell'e-mail, sostituisci # con @) per segnalare il problema e fornire prove pertinenti. Una volta verificata, il sito eliminerà immediatamente il contenuto sospetto di violazione del copyright.