"Это 9-й день моего участия в ноябрьском испытании обновлений, ознакомьтесь с подробностями события:Вызов последнего обновления 2021 г."
Принцип дерева решений
Дерево решений — это модель, которая изучает древовидную структуру на основе обучающих данных. Эта модель является дискриминационной моделью. Дерево решений — это древовидная структура, которая разделяет данные путем принятия ряда решений, аналогично выбору ответов на ряд вопросов. Процесс принятия решений в дереве решений начинается с корневого узла, проверяет соответствующие атрибуты признаков элементов, подлежащих классификации, и выбирает выходную ветвь в соответствии с ее значением до конечного узла и, наконец, использует категорию, хранящуюся в конечном узле. узел как результат решения.
Алгоритм дерева решений — это алгоритм индуктивной классификации, который извлекает полезные правила для прогнозирования новых данных путем изучения обучающей выборки. Основным алгоритмом построения дерева решений является жадный алгоритм, который строит дерево решений сверху вниз. На каждом шаге берется лучший алгоритм в текущем состоянии. Во время генерации дерева решений мера выбора атрибута отключается.
Один из алгоритмов дерева решений (алгоритм ID3)
Алгоритм поддерживает модели классификации, древовидную структуру имеет несколько разветвлений, а выбор признаков осуществляется за счет получения информации.Он не поддерживает непрерывную обработку значений и отсутствующих значений, а также не поддерживает сокращение и многократное использование атрибутов признаков.
Общий алгоритм работы ID3 выглядит следующим образом:
Алгоритм ID3 также имеет дефекты: ID3 не имеет стратегии сокращения и легко поддается переобучению, критерий прироста информации предпочитает признаки с большим количеством возможных значений, а прирост информации признаков, подобных «числу», близок к 1; его можно использовать только для функций Handles дискретных распределений, пропущенные значения не учитываются.
Реализация кода алгоритма ID3
Выбранный набор данных, чтобы увидеть, будет ли сегодня погода.После завершения обучения рисуется дерево решений.
from math import log
import pandas as pd
import numpy as np
import operator
from matplotlib.font_manager import FontProperties
import matplotlib.pyplot as plt
path = 'D:\MachineL\TreeTest.csv'
df = pd.read_csv(path)
dataSet=[]
dataSet= np.array(df.loc[:,:])
print(dataSet)
labels = list(df.columns.values)
labels.pop()
print(labels)
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
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)
return shannonEnt # 返回经验熵
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec
retDataSet.append(reducedFeatVec)
return retDataSet
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
print("第%d个特征的增益为%.3f" % (i, infoGain))
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
def createTree(dataSet, labels, featLabels):
# 取分类标签（yes or no）
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]
featLabels.append(bestFeatLabel)
myTree = {bestFeatLabel: {}}
featValues = [example[bestFeat] for example in dataSet]
uniqueVls = set(featValues)
for value in uniqueVls:
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),
labels, featLabels)
return myTree
def getNumLeafs(myTree):
numLeafs = 0
firstStr = next(iter(myTree))
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
numLeafs += getNumLeafs(secondDict[key])
else:
numLeafs += 1
return numLeafs
def getTreeDepth(myTree):#获取决策树的层数
maxDepth = 0
firstStr = next(iter(
myTree))
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
thisDepth = 1 + getTreeDepth(secondDict[key])
else:
thisDepth = 1
if thisDepth > maxDepth: maxDepth = thisDepth
return maxDepth
def plotNode(nodeTxt, centerPt, parentPt, nodeType):#绘制图像结点
arrow_args = dict(arrowstyle="<-")
font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args, FontProperties=font)
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
def plotTree(myTree, parentPt, nodeTxt):#生成决策树
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
numLeafs = getNumLeafs(myTree)
depth = getTreeDepth(myTree)
firstStr = next(iter(myTree))
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)
plotMidText(cntrPt, parentPt, nodeTxt)
plotNode(firstStr, cntrPt, parentPt, decisionNode)
secondDict = myTree[firstStr]
plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
plotTree(secondDict[key], cntrPt, str(key))
else:
plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD
def createPlot(inTree):#绘制决策树图像
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
plotTree.xOff = -0.5 / plotTree.totalW;
plotTree.yOff = 1.0
plotTree(inTree, (0.5, 1.0), '')
plt.show() # 显示绘制结果
featLabels = []
myTree = createTree(dataSet, labels, featLabels)
print(myTree)
createPlot(myTree)
Визуализация окончательного дерева решений выглядит следующим образом:
Прирост собственных значений следующий: