概念
根据特征值划分数据集
举例
1.根据特征值判断是否属于鱼类
| id | 不浮出水面是否可以生存 | 是否有脚蹼 | 属于鱼类 |
|---|---|---|---|
| 1 | 是 | 是 | 是 |
| 2 | 是 | 是 | 是 |
| 3 | 是 | 否 | 否 |
| 4 | 否 | 是 | 否 |
| 5 | 否 | 是 | 否 |
转成数据格式如下
dataSet = [
[1,1,'yes'],
[1,1,'yes'],
[1,0,'no'],
[0,1,'no'],
[0,1,'no'] ]
2.邮件划分
决策树.png
算法
整体结构(createBranch)
检测数据集中的每个子项是否属于同一分类：
If so return 类标签：
Else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for每个划分的子集
调用函数createBranch并添加返回结果到分支节点中
return 分支节点
香浓熵和信息增益
python实现
1)计算数据集的香浓熵
from math import log
def calShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts[currentLabel]:
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
#计算完目标列每个分类的个数，以字典形式保存
shannoEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannoEnt -= prob*log(prob,2)
return shannoEnt
- 按照给定特征划分数据集
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
