devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

机器学习——决策树之连续值处理_决策树连续值处理方法

作者：小小林熬夜学编程 | 2024-03-22 11:40:02

赞

踩

决策树连续值处理方法

一、连续属性离散化

连续属性就是像：0.697、0.774、0.634等的数字。 连续属性取值数目非有限，无法直接进行划分。这里采用二分法对连续属性进行处理。

我的数据集

 

 

第一步 

将连续属性a在样本集D上出现的n个不同的取值从小到大排列，记为a^{1},a^{2},\cdots ,a^{n}。基于划分点t，可将D分为子集D_{t}^{+}和D_{t}^{-}，其中D_{t}^{-}包含那些在属性a上取值不大于t的样本，D_{t}^{+}包含那些在属性a上取值大于t的样本。考虑包含n-1个元素的候选划分点集合

T_{a}=\left \{ \frac{a^{i}+a^{i+1}}{2} |1\leqslant i\leqslant n-1\right \}

即把区间[a^{i},a^{i+1})的中位点\left ( a^{i}+a^{i+1} \right )/2 作为 候选划分点

将连续属性绩点在样本集D上出现的17个不同的取值从小到大排序

2.801        2.998        3.169        3.184        3.190        3.318        3.373        3.425        3.462

3.789        3.893        4.009        4.151        4.238        4.312        4.413        4.423

计算候选划分点集合

2.900        3.083        3.176        3.187        3.254        3.346        3.399        3.444        

3.630        3.845        3.951        4.080        4.194        4.275        4.363        4.418 

 第二步

采用离散属性值方法，计算这些划分点的增益，选取最优的划分点进行样本集合的划分 ：

其中Gain(D,a,t)是样本集D基于划分点t二分后的信息增益，于是，就可以选择使Gain(D,a,t)最大化的划分点。

对于上面的数据集，有8个推荐，9个不推荐，信息熵为

Ent(D) = -\sum_{k-1}^{2}p_{k}log_{2}p_{k} = -(\frac{8}{17}log_{2}\frac{8}{17}+\frac{9}{17}log_{2}\frac{9}{17}) = 0.998 

 对属性绩点，取划分点t_{0} = 3.630，则：

D(t>t_{0}) = \left \{ 1,2,4,5,6,8,13,14 \right \}，其中推荐6个，不推荐2个

Ent(D(t>t_{0})) = -(\frac{6}{8}log_{2}\frac{6}{8}+\frac{2}{8}log_{2}\frac{2}{8}) = 0.811 

D(t<t_{0}) = \left \{ 3,7,9,10,11,12,15,16,17 \right \}，其中推荐2个，不推荐7个

Ent(D(t<t_{0})) = -(\frac{2}{9}log_{2}\frac{2}{9}+\frac{7}{9}log_{2}\frac{7}{9}) = 0.764

Gain(D,a,t) = 0.998-(\frac{8}{17}\times 0.811+\frac{9}{17}\times 0.764)=0.212 

计算每个划分点的信息增益，得到最大信息增益为：0.366，对应划分点为3.346

与离散属性不同，若当前结点划分属性为连续属性，该属性还可以作为其后代结点的划分属性 

 二、代码实现

这里只展现处理连续值相关代码，完整代码请点击百度网盘链接下载 

创建数据集

  1. def createDataSet():
  2.     dataSet = [
  3.                     ['班长',4.312,'党员','沿海','是']
  4.                     , ['其他',4.238,'党员','贫困县','是']
  5.                     , ['班长',3.373,'党员','山区','是']
  6.                     , ['班长',3.798,'党员','贫困县','是']
  7.                     , ['团支书',4.413,'党员','沿海','是']
  8.                     , ['团支书',4.009,'党员','山区','是']
  9.                     , ['班长',3.893,'党员','贫困县','是']
  10.                     , ['团支书',3.318,'党员','山区','否']
  11.                     , ['团支书',3.184,'团员','山区','否']
  12.                     , ['团支书',2.801,'党员','沿海','否']
  13.                     , ['其他',3.425,'党员','山区','否']
  14.                     , ['其他',3.169,'团员','贫困县','否']
  15.                     , ['其他',4.423,'党员','沿海','否']
  16.                     , ['班长',4.151,'团员','沿海','否']
  17.                     , ['班长',3.462,'党员','沿海','否']
  18.                     , ['班长',3.190,'团员','山区','否']
  19.                     , ['团支书',2.998,'党员','山区','否']
  20.     ]
  21.     labels = ['担任班委情况','绩点','政治面貌','生源地',]
  22.     # 特征对应的所有可能的情况
  23.     labels_full = {}
  24.  
  25.     for i in range(len(labels)):
  26.         labelList = [example[i] for example in dataSet]
  27.         uniqueLabel = set(labelList)
  28.         labels_full[labels[i]] = uniqueLabel
  29.  
  30.     return dataSet, labels, labels_full

 按照给定数值，将数据集划分为不大于和大于两部分

  1. def splitDataSetForSeries(dataSet, axis, value):
  2.     # 用来保存不大于划分值的集合
  3.     eltDataSet = []
  4.     # 用来保存大于划分值的集合
  5.     gtDataSet = []
  6.     # 进行划分，保留该特征值
  7.     for feat in dataSet:
  8.         if (feat[axis] <= value):
  9.             eltDataSet.append(feat)
  10.         else:
  11.             gtDataSet.append(feat)
  12.  
  13.     return eltDataSet, gtDataSet

计算连续值的信息增益 

  1. def calcInfoGainForSeries(dataSet, i, baseEntropy):
  2. #baseEntropy基础信息熵
  3.  
  4.     # 记录最大的信息增益
  5.     maxInfoGain = 0.0
  6.  
  7.     # 最好的划分点
  8.     bestMid = -1
  9.  
  10.     # 得到数据集中所有的当前特征值列表
  11.     featList = [example[i] for example in dataSet]
  12.  
  13.     # 得到分类列表
  14.     classList = [example[-1] for example in dataSet]
  15.  
  16.     dictList = dict(zip(featList, classList))
  17.  
  18.     # 将其从小到大排序，按照连续值的大小排列
  19.     sortedFeatList = sorted(dictList.items(), key=operator.itemgetter(0))
  20.     print(sortedFeatList)
  21.     # 计算连续值有多少个
  22.     numberForFeatList = len(dataSet)
  23.  
  24.     # 计算划分点，保留三位小数
  25.     midFeatList = [round((sortedFeatList[i][0] + sortedFeatList[i+1][0])/2.0, 3)for i in range(numberForFeatList - 1)]
  26.  
  27.     # 计算出各个划分点信息增益
  28.     for mid in midFeatList:
  29.         # 将连续值划分为不大于当前划分点和大于当前划分点两部分
  30.         eltDataSet, gtDataSet = splitDataSetForSeries(dataSet, i, mid)
  31.  
  32.         # 计算两部分的特征值熵和权重的乘积之和
  33.         newEntropy = len(eltDataSet)/len(sortedFeatList)*calShannonEnt(eltDataSet) + len(gtDataSet)/len(sortedFeatList)*calShannonEnt(gtDataSet)
  34.  
  35.         # 计算出信息增益
  36.         infoGain = baseEntropy - newEntropy
  37.         print('当前划分值为：' + str(mid) + '，此时的信息增益为：' + str(infoGain))
  38.         if infoGain > maxInfoGain:
  39.             bestMid = mid
  40.             maxInfoGain = infoGain
  41.  
  42.     return maxInfoGain, bestMid

选择最好的数据集划分特征

  1. def chooseBestFeatureToSplit(dataSet, labels):
  2.     
  3.     # 得到数据的特征值总数
  4.     numFeatures = len(dataSet[0]) - 1
  5.  
  6.     # 计算出基础信息熵
  7.     baseEntropy = calShannonEnt(dataSet)
  8.  
  9.     # 基础信息增益为0.0
  10.     bestInfoGain = 0.0
  11.  
  12.     # 最好的特征值
  13.     bestFeature = -1
  14.  
  15.     # 标记当前最好的特征值是不是连续值
  16.     flagSeries = 0
  17.  
  18.     # 如果是连续值的话，用来记录连续值的划分点
  19.     bestSeriesMid = 0.0
  20.  
  21.     # 对每个特征值进行求信息熵
  22.     for i in range(numFeatures):
  23.  
  24.         # 得到数据集中所有的当前特征值列表
  25.         featList = [example[i] for example in dataSet]
  26.  
  27.         if isinstance(featList[0], str):
  28.             infoGain = calcInfoGain(dataSet, featList, i, baseEntropy)
  29.         else:
  30.             print('当前划分属性为：' + str(labels[i]))
  31.             infoGain, bestMid = calcInfoGainForSeries(dataSet, i, baseEntropy)
  32.  
  33.         #print('当前特征值为：' + labels[i] + '，对应的信息增益值为：' + str(infoGain))
  34.  
  35.         # 如果当前的信息增益比原来的大
  36.         if infoGain > bestInfoGain:
  37.             # 最好的信息增益
  38.             bestInfoGain = infoGain
  39.             # 新的最好的用来划分的特征值
  40.             bestFeature = i
  41.  
  42.             flagSeries = 0
  43.             if not isinstance(dataSet[0][bestFeature], str):
  44.                 flagSeries = 1
  45.                 bestSeriesMid = bestMid
  46.  
  47.     #print('信息增益最大的特征为：' + labels[bestFeature])
  48.     if flagSeries:
  49.         return bestFeature, bestSeriesMid
  50.     else:
  51.         return bestFeature

创建决策树

  1. def createTree(dataSet, labels):
  2.  
  3.     # 拿到所有数据集的分类标签
  4.     classList = [example[-1] for example in dataSet]
  5.  
  6.     # 统计第一个标签出现的次数，与总标签个数比较，如果相等则说明当前列表中全部都是一种标签，此时停止划分
  7.     if classList.count(classList[0]) == len(classList):
  8.         return classList[0]
  9.  
  10.     # 计算第一行有多少个数据，如果只有一个的话说明所有的特征属性都遍历完了，剩下的一个就是类别标签
  11.     if len(dataSet[0]) == 1:
  12.         # 返回剩下标签中出现次数较多的那个
  13.         return majorityCnt(classList)
  14.  
  15.     # 选择最好的划分特征，得到该特征的下标
  16.     bestFeat = chooseBestFeatureToSplit(dataSet, labels)
  17.  
  18.     # 得到最好特征的名称
  19.     bestFeatLabel = ''
  20.  
  21.  
  22.     # 记录此刻是连续值还是离散值,1连续，2离散
  23.     flagSeries = 0
  24.  
  25.     # 如果是连续值，记录连续值的划分点
  26.     midSeries = 0.0
  27.  
  28.     # 如果是元组的话，说明此时是连续值
  29.     if isinstance(bestFeat, tuple):
  30.         # 重新修改分叉点信息
  31.         bestFeatLabel = str(labels[bestFeat[0]]) + '小于' + str(bestFeat[1]) + '?'
  32.         # 得到当前的划分点
  33.         midSeries = bestFeat[1]
  34.         # 得到下标值
  35.         bestFeat = bestFeat[0]
  36.         # 连续值标志
  37.         flagSeries = 1
  38.     else:
  39.         # 得到分叉点信息
  40.         bestFeatLabel = labels[bestFeat]
  41.         # 离散值标志
  42.         flagSeries = 0
  43.  
  44.     # 使用一个字典来存储树结构，分叉处为划分的特征名称
  45.     myTree = {bestFeatLabel: {}}
  46.  
  47.     # 得到当前特征标签的所有可能值
  48.     featValues = [example[bestFeat] for example in dataSet]
  49.  
  50.     # 连续值处理
  51.     if flagSeries:
  52.  
  53.         # 将连续值划分为不大于当前划分点和大于当前划分点两部分
  54.         eltDataSet, gtDataSet = splitDataSetForSeries(dataSet, bestFeat, midSeries)
  55.         
  56.         
  57.         # 得到剩下的特征标签
  58.         subLabels = labels[:]
  59.         
  60.         # 递归处理小于划分点的子树
  61.         subTree = createTree(eltDataSet, subLabels)
  62.         myTree[bestFeatLabel]['小于'] = subTree
  63.  
  64.         # 递归处理大于当前划分点的子树
  65.         subTree = createTree(gtDataSet, subLabels)
  66.         myTree[bestFeatLabel]['大于'] = subTree
  67.  
  68.         return myTree
  69.  
  70.     # 离散值处理
  71.     else:
  72.         # 将本次划分的特征值从列表中删除掉
  73.         del (labels[bestFeat])
  74.         # 唯一化，去掉重复的特征值
  75.         uniqueVals = set(featValues)
  76.         # 遍历所有的特征值
  77.         for value in uniqueVals:
  78.             # 得到剩下的特征标签
  79.             subLabels = labels[:]
  80.             # 递归调用，将数据集中该特征等于当前特征值的所有数据划分到当前节点下，递归调用时需要先将当前的特征去除掉
  81.             subTree = createTree(splitDataset(dataSet, bestFeat, value), subLabels)
  82.             # 将子树归到分叉处下
  83.             myTree[bestFeatLabel][value] = subTree
  84.         return myTree

运行结果

 

完整代码

链接: https://pan.baidu.com/s/1npNcg7EfQf49SwoGmXriog?pwd=f98b 提取码: f98b 

 

 

 

 

 

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/287883
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号