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: 经验熵
资源评论
