English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
1. Prinzip des Entscheidungsbaums
Der Entscheidungsbaum ist eine Baumstruktur, bei der die Attribute der Beispiele als Knoten und die Werte der Attribute als Zweige verwendet werden.
Der Wurzelknoten des Entscheidungsbaums ist das attribut mit der höchsten Informationsmenge in allen Beispielen. Der Mittelpunkt des Baums ist das attribut mit der höchsten Informationsmenge in der Untergruppe der Beispiele, die von diesem Knoten abgeleitet wird. Der Blattknoten des Entscheidungsbaums ist der Klassenwert der Beispiele. Der Entscheidungsbaum ist eine Form der Wissensdarstellung, die eine hohe Zusammenfassung aller Beispieldaten darstellt. Der Entscheidungsbaum kann die Klassen der gesamten Beispieldaten genau identifizieren und auch die Klassen neuer Beispiele effektiv identifizieren.
Entscheidungsbaum-Algorithmus ID3Grundgedanke:
Zunächst wird das attribut mit der höchsten Diskriminierungskraft gefunden, die Beispiele in mehrere Untergruppen aufgeteilt, und für jede Untergruppe wird das attribut mit der höchsten Diskriminierungskraft gewählt, um zu trennen, bis alle Untergruppen nur Daten desselben Typs enthalten. Am Ende erhalten wir einen Entscheidungsbaum.
Die Arbeit von J.R. Quinlan besteht hauptsächlich darin, den Informationsgewinn aus der Informationstheorie einzuführen, den er Informationsgewinn (information gain) nennt, als Maß für die Diskriminierungsfähigkeit der Attribute und die rekursiven Algorithmen zur Konstruktion eines Entscheidungsbaums zu entwerfen.
Ein Beispiel ist leicht zu verstehen:
Für das Problem der Klimaklassifizierung ist das Attribut:
Wetter (A1Wert ist: Sonnig, bewölkt, regnerisch
Temperatur (A2Wert ist: Kalt, gemäßigt, heiß
Feuchtigkeit(A3) Wert ist: Hoch, Normal
Wind (A4) Wert ist: Wind, Kein Wind
jedes Beispiel gehört zu einer anderen Kategorie, in diesem Beispiel gibt es nur zwei Kategorien, P und N. Die Beispiele der Kategorien P und N werden positiv und negativ Beispiele genannt. Eine Sammlung bekannter positiver und negativer Beispiele ergibt das Trainingsset.
von ID3Der Algorithmus ergibt ein Decision Tree, das jeden Beispiel im Trainingsset korrekt klassifiziert, siehe Abbildung unten.
Die Blätter des Decision Trees sind die Namen der Kategorien, d.h. P oder N. Andere Knoten bestehen aus den Eigenschaften der Beispiele, jede verschiedene Wertung einer Eigenschaft entspricht einem Zweig.
Wenn ein Beispiel klassifiziert werden soll, wird von der Wurzel des Baumes ausgehend getestet, die Zweige werden nach den Werten der Eigenschaften weitergeleitet, bis zum Blattknoten, der das Beispiel in die Kategorie der Blattknoten markiert.
Verwenden wir das Diagramm, um einen konkreten Beispiel zu klassifizieren:
Die Klimabeschreibung am Morgen eines bestimmten Tages ist:
Wetter: Bewölkt
Temperatur: Kalt
Feuchtigkeit: Normal
Wind: Kein Wind
Zu welcher Klimaklasse gehört es?-------------kann aus dem Diagramm die Kategorie des Beispiels als P-Klasse bestimmen.
ID3Also muss ein solches Decision Tree aus dem Trainingsset der Tabelle konstruiert werden. Tatsächlich gibt es mehrere Decision Trees, die das Trainingsset korrekt klassifizieren können. Quinlans ID3Der Algorithmus kann ein Decision Tree mit dem fewsten Knoten erzeugen.
ID3Algorithmus:
1. Berechne den Informationsgewinn jeder Eigenschaft für die aktuelle Beispielmenge;
2. Wähle das Attribut Ak mit dem höchsten Informationsgewinn;
3. Die Beispiele mit dem gleichen Wert von Ak werden in eine Untergruppe zusammengefasst, Ak hat mehrere Werte, es gibt mehrere Untergruppen;
4. Für Untergruppen, die sowohl positive als auch negative Beispiele enthalten, wird der Baualgorithmus rekursiv aufgerufen;
5. Wenn die Untergruppe nur positive oder negative Beispiele enthält, wird auf die Zweige P oder N gezeichnet und zurück zum Aufrufort zurückgekehrt.
Wenn es sich um Bäume handelt, wird oft Rekursion verwendet.
Für die spezifische Berechnung des Klimaklassifizierungsproblems gibt es:
1und die Berechnung der Informationssumme: wobei S die Sammlung der Beispiele ist, P(ui) ist die Wahrscheinlichkeit der Kategorie i:
|S| bedeutet die Gesamtzahl der Beispiele im Beispielset S, |ui| bedeutet die Anzahl der Beispiele der Kategorie ui. Für9positive Beispiele und5Es gibt
P(u1)=(9/14
P(u2)=(5/14
H(S)=(9/14)=log(14/9)+（5/14)=log(14/5)=0.94Bit
2und die Berechnung des Informationsgewinns:
dabei ist A das Attribut, Value(A) ist die Wertekombination des Attributs A, v ist ein bestimmter Wert des Attributs A, Sv ist die Sammlung der Beispiele in S mit dem Wert v, | Sv | ist die Anzahl der Beispiele in Sv.
mit dem Attribut A1als Beispiel, gemäß dem Berechnungsalgorithmus des Informationsgewinns, das Attribut A1hat den Informationsgewinn
S=[9+,5-] //Die ursprüngliche Beispielegruppe enthält14Beispiele9positive Beispiele,5negative Beispiele
S Sonnig=[2+,3-]//Attribut A1Beispiele mit dem Wert 'sonnig' gibt es5Stück2positiv,3umgekehrt
S Bewölkt=[4+,0-] //Attribut A1Beispiele mit dem Wert 'bewölkt' gibt es4Stück4positiv, 0 negativ
SRegen=[3+,2-] //Attribut A1Beispiele mit dem Wert 'sonnig' gibt es5Stück3positiv,2umgekehrt
daher
3und das Ergebnis ist
Attribut A1hat den höchsten Informationsgewinn, daher wird er als Wurzelknoten ausgewählt.
4und den Wurzel- und Blattknoten
ID3Das Algorithmus wählt den Attribut 'Wetter' mit dem höchsten Informationsgewinn als Wurzel des Baumes, in14个例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是:
其中S2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。
5、递归建树
分别对S1和S3子集递归调用ID3算法，在每个子集中对各属性求信息增益.
（1）对S1，湿度属性信息增益最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。
（2）对S3，风属性信息增益最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。
二、PYTHON实现决策树算法分类
本代码为machine learning in action 第三章例子，亲测无误。
1、计算给定数据shangnon数据的函数：
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. 数据创建函数
def createDataSet():
dataSet = [[1,1']
[1,1, 'yes'],
[1,0,'no'],
[0,1']
[0,1']
labels = ['no surfacing','flippers']
return dataSet, labels
3.Teilen des Datensatzes, gemäß der angegebenen Eigenschaft
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.Wählen der besten Methode zur Aufteilung des Datensatzes
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.Erstellen des Baumes rekursiv
Funktion zum Finden des am häufigsten vorkommenden Klassennamens
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]
Funktion zum Erstellen eines Baumes
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
#der Typ ist der gleiche, also beenden Sie die Klassifizierung
if classList.count(classList[0]) == len(classList):
return classList[0]
#durchsuchen Sie alle Merkmale und wählen Sie das häufigste Merkmal
if (len(dataSet[0]) == 1)
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
#erhalten Sie die Liste, die alle Eigenschaften erfüllt
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
Dann geben Sie im Python-Prompt die folgenden Befehle ein:
myDat, labels = trees.createDataSet() myTree = trees.createTree(myDat, labels) print myTree
Ergebnis ist:
{'no surfacing': {0: 'nein', 1: {'flippers': {0: 'nein', 1: 'ja'}}}}
6.Funktion zum Klassifizieren mit einem praktischen Entscheidungsbaum
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
Geben Sie im Python-Befehlszeilen-Protokoll ein:
trees.classify(myTree, labels,[1,0])
Ergebnis erhalten:
'nein'
Herzlichen Glückwunsch. Oh ja. Sie haben es geschafft.!!!
Das ist der gesamte Inhalt dieses Artikels. Wir hoffen, dass er Ihnen bei Ihrem Lernen hilft und dass Sie die呐喊教程大力支持.
Erklärung: Der Inhalt dieses Artikels wurde aus dem Internet übernommen und gehört dem Urheber. Der Inhalt wurde von Internetbenutzern selbstständig beigesteuert und hochgeladen. Diese Website besitzt keine Eigentumsrechte und hat den Inhalt nicht manuell bearbeitet. Sie übernimmt auch keine Haftung für die juristischen Folgen. Wenn Sie Inhalte finden, die möglicherweise urheberrechtlich geschützt sind, freuen wir uns über eine E-Mail an: notice#oldtoolbag.com (Bitte ersetzen Sie # durch @, wenn Sie eine Meldung senden, und fügen Sie relevante Beweise bei. Sobald nachgewiesen wird, dass der Inhalt urheberrechtlich geschützt ist, wird diese Website den涉嫌侵权的内 容立即删除。)