python 决策树算法的实现决策树算法的实现
'''
数据集:Mnist
训练集数量:60000
测试集数量:10000
------------------------------
运行结果:ID3(未剪枝)
正确率:85.9%
运行时长:356s
'''
import time
import numpy as np
def loadData(fileName):
'''
加载文件
:param fileName:要加载的文件路径
:return: 数据集和标签集
'''
# 存放数据及标记
dataArr = [];
labelArr = [] # 读取文件
fr = open(fileName)
# 遍历文件中的每一行
for line in fr.readlines():
# 获取当前行,并按“,”切割成字段放入列表中
# strip:去掉每行字符串首尾指定的字符(默认空格或换行符)
# split:按照指定的字符将字符串切割成每个字段,返回列表形式
curLine = line.strip().split(',')
# 将每行中除标记外的数据放入数据集中(curLine[0]为标记信息)
# 在放入的同时将原先字符串形式的数据转换为整型
# 此外将数据进行了二值化处理,大于128的转换成1,小于的转换成0,方便后续计算
dataArr.append([int(int(num) > 128) for num in curLine[1:]])
# 将标记信息放入标记集中
# 放入的同时将标记转换为整型
labelArr.append(int(curLine[0]))
# 返回数据集和标记
return dataArr, labelArr
def majorClass(labelArr):
'''
找到当前标签集中占数目最大的标签
:param labelArr: 标签集
:return: 最大的标签
'''
# 建立字典,用于不同类别的标签技术
classDict = {}
# 遍历所有标签
for i in range(len(labelArr)):
# 当第一次遇到A标签时,字典内还没有A标签,这时候直接幅值加1是错误的,
# 所以需要判断字典中是否有该键,没有则创建,有就直接自增
if labelArr[i] in classDict.keys():
# 若在字典中存在该标签,则直接加1
classDict[labelArr[i]] += 1
else:
# 若无该标签,设初值为1,表示出现了1次了
classDict[labelArr[i]] = 1
# 对字典依据值进行降序排序
classSort = sorted(classDict.items(), key=lambda x: x[1], reverse=True)
# 返回最大一项的标签,即占数目最多的标签
return classSort[0][0]
def calc_H_D(trainLabelArr):
'''
计算数据集D的经验熵,参考公式5.7 经验熵的计算
:param trainLabelArr:当前数据集的标签集
:return: 经验熵
评论0