基尼不纯度也可度量集合的无序程度
香农熵的计算公式如下:
\[H=-\sum_{i=1}^{n}p(x_{i})log_{2}p(x_{i})
\]
xi是目标变量的某个取值,
H是一个数学期望
因为p(xi)<1,所以最后结果是正数
def calcShannonEnt(dataSet):
"""计算香农熵"""
labelCounts={}
numEntries = len(dataSet) # 数据集的总数,用于计算比例P
# 1. 计算出每个label对应的数量
for line in dataSet:
label = line[-1]
if label not in labelCounts.keys():
labelCounts[label] = 0
labelCounts[label] += 1
# 2. 使用labelCounts计算prob和H
shannonEnt = 0.0 # 熵的初值
for label, count in labelCounts.items():
prob = float(count) / numEntries
shannonEnt -= prob * log(prob, 2)
return shannonEnt
splitDataSet(dataSet,0,1)
表示先选出满足条件"第0个标签的值等于0"的数据,再把数据中的第0个标签剔除掉。
>>> dataSet
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> splitDataSet(dataSet, 0, 1)
[[1, 'yes'], [1, 'yes'], [0, 'no']]
>>> splitDataSet(dataSet, 0, 0)
[[1, 'no'], [1, 'no']]
def splitDataSet(dataSet, axis, value):
"""划分数据集。python使用引用传递列表,因此创建一个新的结果列表"""
returnDataSet = []
for line in dataSet:
if line[axis] == value:
newline = line[:axis]
newline.extend(line[axis+1:])
returnDataSet.append(newline)
return returnDataSet
数据必须满足两点要求:
对每个特征进行划分,找到划分后,信息增益最大的特征
需要遍历所有特征,计算每次的信息增益
特征i可能有很多取值,会产生很多分支,对每个分支计算香农熵。最后的熵取所有分支熵的数学期望。
信息增益=原始熵-按特征i划分后各个分支熵的数学期望
def chooseBestFeatureToSplit(dataSet):
"""寻找最好的分类特征==> 寻找分类后,信息增益最大的特征"""
numberOfFeature = len(dataSet[0]) -1 # 最后一位不要,因为他是分类结果
numberOfDataSet = len(dataSet)
baseEntropy = calcShannonEnt(dataSet) # 原始香农熵
bestInfoGain = 0.0 # 用于记录最大信息熵
bestFeature = -1 # 用于记录最大信息熵对应的特征下标
# 对每个特征进行划分,找到划分后,信息增益最大的特征
for i in range(numberOfFeature):
# 1. 找到该特征的所有可能取值,去重
values = [example[i] for example in dataSet]
uniqueValue = set(values)
# 2. 计算香农熵。需要对于每一个取值计算一次。香农熵本身就类似一个数学期望(这一部分可以封装成一个香农熵函数)
newShannonEnt = 0.0
for value in uniqueValue:
splitedDataSet = splitDataSet(dataSet, i, value)
prob = float(len(splitedDataSet)) / numberOfDataSet
newShannonEnt += prob * calcShannonEnt(splitedDataSet)# 3. 寻找最大信息增益
infoGain = baseEntropy - newShannonEnt
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
# 寻找最大的数学期望,返回该特征
return bestFeature
递归创建决策树,递归终止的条件有两个:
遍历完所有划分数据集的属性(每次划分会消耗一个属性,属性已经用完)
该分支下所有实例都是相同的分类
def createTree(dataSet, labels):
"""创建决策树。labels 是对每个特征值的含义的解释,方便建立决策树"""
# 递归终止条件
classList = [example[-1] for example in dataSet]
# (1)属性已经用完
if len(dataSet[0]) == 1:
majorithCnt(classList)
# (2)所有分类已经一致
if classList.count(classList[0]) == len(classList):
return classList[0]
# 1. 寻找最优特征
bestFeature = chooseBestFeatureToSplit(dataSet)
bestFeatureLabel = labels[bestFeature] # 只是标签,用于建树
mytree = {bestFeatureLabel: {}} # 初始化树
subLabels = labels[:] # 复制该列表,因为labels是引用。避免值被改变
del subLabels[bestFeature] # subLabels
# 2. 当前最优特征的所有取值,去重
totalValues = [example[bestFeature] for example in dataSet]
uniqueValues = set(totalValues)
# 3. 每个value一个分支,确定每个分支的值。因为是递归,所以分支下可能还有分支(字典里可能嵌套字典),如果该分支已经可以结束,则返回返回classList中的一个(分类结果)
for value in uniqueValues:
subDataSet = splitDataSet(dataSet, bestFeature, value)
mytree[bestFeatureLabel][value] = createTree(subDataSet, subLabels)
return mytree
这部分很简单,将数据集按照树的结构从上往下查找即可。数据集如下:
no surfacing
flippers
fish(目标变量)
1
1
yes
1
1
yes
1
0
no
0
1
no
0
1
no
将构建的决策树用图形表示:
def classify(inputTree, featureLabels, testVec):
"""
:param inputTree: 构建好的决策树
:param featureLabels: 标签列表,也就是每个分类的属性名
:param testVec: 测试数据
"""
firstStr = list(inputTree.keys())[0] # 其实根元素只有一个
secondDict = inputTree[firstStr] # 第二层
featureIndex = featureLabels.index(firstStr) # 当前属性的下标
for key in secondDict.keys():
if testVec[featureIndex] == key:
if type(secondDict[key]).__name__ == "dict":
classLabel = classify(secondDict[key], featureLabels, testVec)
else:
classLabel = secondDict[key]
return classLabel
将决策树保存到文件中。python使用pickle
模块序列化对象
pickle.dump(obj, file)
: 将obj写入到file中。file=open(filename,"bw")
pickle.load(file)
: 读取file中的内容,转换为obj。file=open(filename, "rb")
def storeTree(inputTree, fileName):
import pickle
with open(fileName, "wb") as file:
pickle.dump(inputTree, file)
def grabTree(fileName):
import pickle
with open(fileName, "rb") as file:
return pickle.load(file)
准备训练数据集。该数据集有5项,4个特征变量和一个目标变量。 各个属性名分别是:
['age', 'prescript', 'astigmatic', 'tearRate']
部分数据集:
young myope no reduced no lenses
young myope no normal soft
young myope yes reduced no lenses
young myope yes normal hard
young hyper no reduced no lenses
young hyper no normal soft
young hyper yes reduced no lenses
......
createTree(dataSet, labels)
生成决策树 myTree
classify(myTree, labels, testVec)
简而言之:
准备dataSet
和labels
,通过createTree(dataSet, labels)
==> mytree
准备测试数据test
,通过 classify(myTree, labels, testVec)
==> 结果
def lense():
with open("dataset/lenses.txt") as file:
fileContent = file.readlines()
dataSet = [example.strip().split("\t") for example in fileContent]
labels = ['age', 'prescript', 'astigmatic', 'tearRate']
myTree = createTree(dataSet, labels)
print("计算出的决策树是:", myTree)
result = classify(myTree, labels, ['young', 'myope', 'no', 'reduced'])
print("预测的结果是:", result)
计算出的决策树:
{'tearRate': {'normal': {'astigmatic': {'no': {'age': {'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}}, 'young': 'soft', 'pre': 'soft'}}, 'yes': {'prescript': {'hyper': {'age': {'presbyopic': 'no lenses', 'young': 'hard', 'pre': 'no lenses'}}, 'myope': 'hard'}}}}, 'reduced': 'no lenses'}}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章