使用决策树算法预测隐形眼镜类型

简介: 使用决策树算法预测隐形眼镜类型

谷歌笔记本(可选)

from google.colab import drive
drive.mount("/content/drive")

output

Mounted at /content/drive


编写算法:决策树

from math import log
import operator
 
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
  for key in labelCounts:
    prob = float(labelCounts[key]) / numEntries
    shannonEnt -= prob * log(prob, 2)
  return shannonEnt

这段代码是用于计算给定数据集的香农熵(Shannon Entropy)的Python实现。香农熵在信息论中是一个度量不确定性或信息混乱程度的重要概念,在机器学习领域,特别是在决策树算法中,用于评估特征对于划分数据集纯度的贡献。


1. `calcShannonEnt`函数接收一个名为dataSet的数据集作为输入,该数据集通常是由特征向量构成的列表,每个特征向量最后一个元素为其对应的类别标签。


2. 首先统计数据集中样本的数量:`numEntries = len(dataSet)`。


3. 初始化一个字典`labelCounts`,用于存储各类别标签出现的次数。通过遍历整个数据集,对每一个特征向量(featVec),提取其类别标签(currentLabel),并将其计数加到字典对应键值上。


4. 计算香农熵:初始化`shannonEnt`为0,然后遍历`labelCounts`字典,对于每个类别标签key,计算其概率(通过其出现次数除以总样本数得到),然后用公式 `- prob * log(prob, 2)` 计算其熵值,并累加到`shannonEnt`上。这里的log是以2为底的对数,因为熵的单位通常是比特(bits)。


5. 最后返回计算得出的香农熵值`shannonEnt`。


总结:这个函数的主要目的是衡量给定数据集中各类别的不确定性或分布均匀性,熵值越大表示不确定性越高,越需要进行划分以提高模型的纯度。

def splitDataSet(dataSet, axis, value):
  retDataSet = []
  for featVec in dataSet:
    if featVec[axis] == value:
      reducedFeatVec = featVec[:axis]
      reducedFeatVec.extend(featVec[axis+1:])
      retDataSet.append(reducedFeatVec)
  return retDataSet
def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1   # 2
  baseEntropy = calcShannonEnt(dataSet)  # 0.9709505944546686
  bestInfoGain = 0
  bestFeature = -1
  for i in range(numFeatures):
    featList = [example[i] for example in dataSet]
    uniqueVals = set(featList)
    newEntropy = 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

这段代码是用于选择数据集中最佳特征进行划分的函数,通常在决策树构建过程中使用。其主要目的是通过计算信息增益(Information Gain)来确定最优分割特征。


1. numFeatures 计算特征的数量,等于数据集中每个样本向量元素的个数减1(因为最后一个元素通常是类别标签)。


2. 初始化基本熵(baseEntropy),通过调用之前定义的 calcShannonEnt(dataSet) 函数计算整个数据集的香农熵。


3. 初始化最佳信息增益(bestInfoGain)为0,以及最佳特征索引(bestFeature)为-1,分别用于存储找到的最大信息增益和对应的特征编号。


4. 遍历所有特征(i从0到numFeatures-1):


       a. 通过列表推导式提取出当前特征i的所有取值,存入featList。


       b. 将featList中的唯一值转化为一个集合(uniqueVals),这将作为当前特征可能的划分依据。


       c. 对于uniqueVals中的每一个value,利用splitDataSet函数根据特征i和该value划分数据集得到subDataSet。


       d. 计算划分后子数据集的概率(prob),即子数据集大小除以原数据集大小。


       e. 计算划分后的子数据集的香农熵,并乘以对应概率得到加权平均熵(newEntropy)。


       f. 使用公式计算信息增益:infoGain = baseEntropy - newEntropy。


       g. 如果当前信息增益大于已记录的最佳信息增益,则更新bestInfoGain和bestFeature。


5. 循环结束后返回最佳特征索引(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):
  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:{}}
  subLabels = labels[:]
  del(subLabels[bestFeat])
  featValues = [example[bestFeat] for example in dataSet]
  uniqueVals = set(featValues)
  for value in uniqueVals:
    myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
  return myTree

这段代码是用于创建决策树的函数,名为`createTree`。它递归地构建决策树直到满足停止条件。


1. 首先计算数据集classList中最后一个元素(类别标签)的唯一值数量,如果所有样本的类别标签都相同,则说明当前节点下的样本已经足够纯,无需继续划分,直接返回这个唯一的类别标签作为叶子节点的预测结果。


2. 检查是否所有特征已经被用尽(即每个样本只有一个特征),如果是,则返回该节点下出现次数最多的类别标签(通过调用`majorityCnt(classList)`实现)。


3. 使用`chooseBestFeatureToSplit`函数选择最优特征进行划分,并获取其对应的标签名称(bestFeatLabel)。


4. 初始化一个新的字典结构myTree,以表示当前节点以及其子节点。字典的键为最优特征的标签,值为另一个字典,后续将填充各个特征取值对应的子树。


5. 创建一个子标签列表subLabels,它是原标签列表labels的一个副本,然后删除最优特征对应的标签,这样在构建子节点时不会重复考虑此特征。


6. 提取数据集中最优特征的所有取值并转化为一个集合uniqueVals。


7. 遍历uniqueVals中的每一个特征取值value:

  a. 调用`splitDataSet(dataSet, bestFeat, value)`对数据集进行划分,得到该特征取值对应的新子数据集。

  b. 以最优特征的取值value作为键,递归调用`createTree`生成对应的子树,并将其添加到myTree[bestFeatLabel]中。


8. 当所有子树构造完成后,返回整个决策树结构myTree。整个过程按照信息增益最大原则自顶向下构建决策树,直至达到终止条件。


准备数据:拆分数据集

fr = open('/content/drive/MyDrive/MachineLearning/机器学习/决策树/使用决策树预测隐形眼镜类型/lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
lensesTree = createTree(lenses, lensesLabels)
lensesTree, lensesLabels
output

({'tearRate': {'normal': {'astigmatic': {'no': {'age': {'presbyopic': {'prescript': {'myope': 'no lenses',
         'hyper': 'soft'}},
       'pre': 'soft',
       'young': 'soft'}},
     'yes': {'prescript': {'myope': 'hard',
       'hyper': {'age': {'presbyopic': 'no lenses',
         'pre': 'no lenses',
         'young': 'hard'}}}}}},
   'reduced': 'no lenses'}},
 ['age', 'prescript', 'astigmatic', 'tearRate'])

测试算法:构造注解树

import matplotlib.pyplot as plt
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
  createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
                          xytext=centerPt, textcoords='axes fraction',
                          va='center', ha='center', bbox=nodeType, arrowprops=arrow_args)
def getNumLeafs(myTree):
  numLeafs = 0
  firstStr = list(myTree.keys())[0]
  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 = list(myTree.keys())[0]
  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 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):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    firstStr = list(myTree.keys())[0]
    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()
createPlot(lensesTree)

output

使用算法:预测隐形眼镜类型

def classify(inputTree, featLabels, testVec):
  firstStr = list(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
classify(lensesTree, lensesLabels, ['pre', 'myope', 'yes', 'normal'])

output

'hard'

目录
相关文章
|
4天前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
13 4
|
4天前
|
算法 Java 机器人
Java数据结构与算法:AVL树
Java数据结构与算法:AVL树
|
2天前
|
机器学习/深度学习 算法
梯度提升树GBDT系列算法
在Boosting集成算法当中,我们逐一建立多个弱评估器(基本是决策树),并且下一个弱评估器的建立方式依赖于上一个弱评估器的评估结果,最终综合多个弱评估器的结果进行输出。
|
4天前
|
存储 算法 Python
python常用算法(5)——树,二叉树与AVL树(一)
python常用算法(5)——树,二叉树与AVL树
|
6天前
|
算法 数据可视化 Python
Python中的决策树算法探索
Python中的决策树算法探索
|
13天前
|
机器学习/深度学习 算法 前端开发
决策树与随机森林算法在分类问题中的应用
本文探讨了决策树和随机森林两种监督学习算法,它们在分类任务中表现出强大的解释性和预测能力。决策树通过特征测试进行分类,构建涉及特征选择、树生成和剪枝。随机森林是集成学习方法,通过构建多棵决策树并汇总预测结果,防止过拟合。文中提供了Python代码示例,展示如何使用sklearn构建和应用这些模型,并讨论了参数调优和模型评估方法,如交叉验证和混淆矩阵。最后,强调了在实际问题中灵活选择和调整模型参数的重要性。
37 4
|
4天前
|
存储 算法 Shell
python常用算法(5)——树,二叉树与AVL树(三)
python常用算法(5)——树,二叉树与AVL树
|
4天前
|
算法 Python
python常用算法(5)——树,二叉树与AVL树(二)
python常用算法(5)——树,二叉树与AVL树
|
5天前
|
机器学习/深度学习 算法 数据可视化
决策树算法:从原理到实践的深度解析
决策树算法:从原理到实践的深度解析
10 0
|
7天前
|
人工智能 算法 Java
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。

热门文章

最新文章