赞
踩
该实验主要利用ID3算法和已有的数据建立决策树和随机森林,并利用决策树和随机森林来预测未知数据的值。本实验使用Python实现。
下面介绍几个基础但很重要的概念:
决策树:决策树是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。
随机森林:随机森林是一种包含很多决策树的分类器,既可以用于处理分类和回归问题,也适用于降维问题。其对异常值与噪音也有很好的容忍,相较于决策树有着更好的预测和分类性能。
ID3算法:该算法是本实验的重点。ID3 算法的核心是根据信息增益来选择进行划分的特征,然后递归地构建决策树。它的思想并不复杂,步骤也比较简单。下面简单介绍一下ID3算法的步骤。
从根节点开始,计算所有可能的特征的信息增益,选择信息增益最大的特征,来划分节点。
按该特征的不同取值建立子节点。
如果没有特征可以选择或类别完全相同,则得到决策树,该算法结束。否则转向第4步。
对子节点递归1、2步。
说明:因为屎山代码比较长,所以这里部分只给出函数名,函数具体实现请见附录。
学习完算法的基本原理后,现在开始真正实现该算法。实现该算法就没有理解算法思想那么容易了。这里运用面向对象的思想,把决策树和随机森林分开来写,这样不至于混淆。
首先实现决策树,按照算法步骤首先需要计算信息增益,而想要计算信息增益首先需要计算熵和条件熵。这里把它们分到三个方法里:
def entropy(self, condition=None):
def entropy_condition(self, condition=None):
def information_gain(self, condition):
关于实现的具体过程,就是按照相关的数学表达式实现即可。比如说信息增益,等于最终特征本身的熵,减去给定A的条件下该特征的条件熵。
接着实现信息增益最大的节点进行分裂,方法很简单,就是计算出所有节点的信息增益,然后选择信息增益最大的节点即可。
def find_best(self, condition=None):
然后就可以使用递归的方法建立决策树,每走一步就算一遍信息增益,然后建立一个子节点。最后结果返回整棵决策树。
def create_tree(self, condition=None):
最后,也就是最重要的一步,那就是预测值,因为构建决策树是为了把数据分类,最终目的就是预测未知数据的值。因为在Python中我使用字典套字典的数据类型来存储树,具体代码就是每到一个key就识别一次,如果value是最终结果的话就返回,如果还是字典的话就递归下去,直到获取到最终的值。
def predict(self, info, t={}):
到这里决策树建立完毕,接下来就要建立随机森林了。一般来说,随机森林有很多棵树,但是这里因为数据和个人能力的原因,就只分了两棵树。具体步骤也不难,就是把数据集均分成两个,分别建立各自的决策树,然后按各自的预测结果汇总,数量最多的结果作为最终的预测结果。如果两种决策结果一样多,就返回结果不确定。
在这里,代码实现的主要难点在于数据集的划分,以及对应预测数据的划分,因为是随机选择的划分方法,很容易出现两者划分方法不一致,这样预测过程就会出问题,代码就会经常报错。最后处理的方法就是在划分数据集的时候把划分方式记录下来,来适配预测数据的划分模式。具体代码比较繁琐,就不展示了。
下面是使用的主要函数。
def build_forest(self, info=None):
def predict(self, info):
def split_dict_by_key(dictionary, keys, result):
def split_dict_by_key2(dictionary, keys, result):
在写完代码后,最重要的就是进行测试,来分析其正确性与性能。
这里的数据量比较小,只有28条数据和5个特征,但也足够用来简单实现决策树和随机森林了。
首先测试决策树,先输出决策树:
然后测试两条数据,分别是[‘rain’, ‘mild’, ‘normal’, ‘no’]和[‘sunny’,‘hot’,‘high’,‘no’],然后给出预测结果。
与真实结果相吻合,这说明这棵决策树具备了一定的预测能力。
然后测试随机森林,先输出随机森林:
用元组来存储了这两棵树,然后就上面两条数据来进行预测,给出预测结果。
出现了两种不同的结果,分析具体的原因,是因为每棵树只分到了两个特征,而有可能这两个特征的信息增益比较低,不能很好地预测或者说预测效果很差。但当森林里有很多棵树时,这个问题可以大大缓解,并提升预测准确性。
下面给出总程序的预测结果:
测试完算法后,来分析它的性能和优劣。首先分析ID3算法,ID3算法作为决策树算法较早出现的一个算法,在设计上有着它的瓶颈和缺陷。比如说ID3并没有考虑连续特征,对可取值数目较多的属性有倾向性,没有考虑过拟合的问题等。在ID3算法之后出现的决策树算法中,也借鉴了它ID3算法的思想。比如说C4.5算法,只不过把信息增益改为了信息增益比,就解决了倾向性问题和不能处理连续型数据的问题。又比如CART算法,生成二叉树,能同时处理连续型和离散型数据,还能处理数据缺失的问题,无疑是对以前算法的较大改进。
再来分析随机森林,虽然我程序里的随机森林比较低效,但事实上随机森林是有着比单棵决策树更好的预测能力,有着比决策树更加卓越的性能。比如说它可以判断特征的重要程度、不容易过拟合、实现简单、平衡误差等优势。这些优点使得随机森林成为机器学习中十分重要的算法。但即使如此,它也跟其他算法一样,有它本身的缺陷。其中最大的两个缺陷是1、随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。2、对于有不同取值的属性的数据,取值划分较多的属性会对随机森林产生更大的影响,所以随机森林在这种数据上产出的属性权值是不可信的。因此,在使用不同的机器学习算法时,要充分考虑不同数据和算法的特点。没有最好的算法,只有最合适的算法。
# 决策树和随机森林(Python实现) import time import math import random import pandas as pd # 实现ID3算法 class ID3: # 初始化 def __init__(self, data, label, d): self.data = data self.condition_data = [] self.tree = None self.label = label self.Dict = d self.black = set() self.queue = [] def entropy(self, condition=None): """ 计算熵 :param condition: 条件 :return: """ if not condition: numEntries = len(self.data) Labels = dict() for value in self.data: currentLabel = value[self.label[-1]] if currentLabel not in Labels.keys(): Labels[currentLabel] = 1 else: Labels[currentLabel] += 1 shang = 0.0 for Label in Labels.keys(): p = float(Labels[Label]) / numEntries shang -= p * math.log2(p) return shang else: self.condition_data.clear() for j in range(len(self.data)): if self.data[j][condition[0]] == condition[1]: self.condition_data.append(self.data[j]) numEntries = len(self.condition_data) Labels = dict() for value in self.condition_data: currentLabel = value[self.label[-1]] if currentLabel not in Labels.keys(): Labels[currentLabel] = 1 else: Labels[currentLabel] += 1 shang = 0.0 for Label in Labels.keys(): p = float(Labels[Label]) / numEntries shang -= p * math.log2(p) return shang def entropy_condition(self, condition=None): """ 计算条件熵 :param condition:条件 :return: """ shang = 0.0 d = dict() for value in self.data: if value[condition] not in d.keys(): d[value[condition]] = 1 else: d[value[condition]] += 1 for value in d.keys(): p = float(d[value]) / len(self.data) shang += self.entropy((condition, value)) * p return shang def information_gain(self, condition): """ 计算信息增益 :param condition: 第几个条件 :return:信息增益 """ return self.entropy() - self.entropy_condition(condition) def find_best(self, condition=None): """ 寻找信息增益最大的一项 :param condition: 条件 :return: 最大项,以及最大项具体各个值的信息 """ Max = 0 lab = None dic = {} # 字典,如{'sunny':[1,1],...} 第一项为pos,第二项为neg for i in self.label[:-1]: if i in self.black: continue if self.information_gain(i) > Max: Max = self.information_gain(i) lab = i self.queue.append(lab) num = self.label.index(lab) for value in self.Dict[num][lab]: dic[value] = [0, 0] for value in self.data: if condition and value[condition[0]] != condition[1]: continue if value['playtennis'] == 'positive': dic[value[lab]][0] += 1 else: dic[value[lab]][1] += 1 return lab, dic def create_tree(self, condition=None): """ 建立决策树 :param condition:条件 :return: 返回决策树 """ my_tree = {} if len(self.black) <= len(self.label) - 2: lab, dic = self.find_best(condition) my_tree = {lab: {}} for value in dic.keys(): if dic[value][1] <= 1: # 基本全为pos my_tree[lab][value] = 'positive' elif dic[value][0] <= 1: # 基本全为neg my_tree[lab][value] = 'negative' else: self.black.add(lab) my_tree[lab][value] = self.create_tree((lab, value)) if my_tree[lab][value] == {}: if dic[value][0] > dic[value][1]: my_tree[lab][value] = 'positive' else: my_tree[lab][value] = 'negative' return my_tree def predict(self, info, t={}): """ 根据信息预测最有可能的值 :param info: 信息 :param t: 辅助参数 :return: 预测结果 """ self.black.clear() if t == {}: tree = self.create_tree() else: tree = t for i in tree.keys(): num = self.label.index(i) if tree[i][info[num]] == 'positive': return 'positive' elif tree[i][info[num]] == 'negative': return 'negative' else: return self.predict(info, tree[i][info[num]]) # 扩展:随机森林(两颗决策树) class Forest: # 初始化 def __init__(self, data, Dict): self.data = data self.forest = [] self.Dict = Dict self.information = [] def build_forest(self, info=None): """ 建立随机森林(基于决策树) :param info: 条件 :return: 随机森林 """ labels = list(self.data[0].keys())[:-1] one = random.sample(labels, len(labels) // 2) two = list(set(labels) - set(one)) if info: l = [] r = [] for j in info: for i in self.Dict[:-1]: if j in list(i.values())[0] and list(i.keys())[0] in one: l.append(j) break if j in list(i.values())[0] and list(i.keys())[0] in two: r.append(j) break for i in self.Dict[:-1]: if one[0] == list(i.keys())[0]: if l[0] in list(i.values())[0]: break else: l.reverse() break for i in self.Dict[:-1]: if two[0] == list(i.keys())[0]: if r[0] in list(i.values())[0]: break else: r.reverse() break self.information = [l, r] one.append(list(self.data[0].keys())[-1]) two.append(list(self.data[0].keys())[-1]) one_dict = split_dict_by_key(self.data, one, list(self.data[0].keys())[-1]) two_dict = split_dict_by_key(self.data, two, list(self.data[0].keys())[-1]) one_dict2 = split_dict_by_key2(self.Dict, one[:-1], list(self.data[0].keys())[-1]) two_dict2 = split_dict_by_key2(self.Dict, two[:-1], list(self.data[0].keys())[-1]) one_tree = ID3(one_dict, one, one_dict2) two_tree = ID3(two_dict, two, two_dict2) o = one_tree.create_tree() t = two_tree.create_tree() self.forest.append(one_tree) self.forest.append(two_tree) return o, t def predict(self, info): """ 随机森林预测 :param info: 条件 :return: 预测值 """ if not self.forest: print("随机森林为", self.build_forest(info)) else: self.forest.clear() self.build_forest(info) a = self.forest[0].predict(self.information[0]) b = self.forest[1].predict(self.information[1]) if a == b: return a else: return '不确定' # 字典分裂的两个函数 def split_dict_by_key(dictionary, keys, result): sub_dict = [{keys[0]: i[keys[0]], keys[1]: i[keys[1]], result: i[result]} for i in dictionary] return sub_dict def split_dict_by_key2(dictionary, keys, result): sub_dict = [] keys.append(result) for i in keys: for j in dictionary: if i == list(j.keys())[0] and j not in sub_dict: sub_dict.append(j) break return sub_dict if __name__ == '__main__': begin = time.time() # 读取数据以及准备数据 data = pd.read_csv("data.csv") data = data.to_dict(orient='records') label = ['outlook', 'temperature', 'humidity', 'wind', 'playtennis'] Dict = [{'outlook': ['sunny', 'overcast', 'rain']}, {'temperature': ['hot', 'mild', 'cool']}, {'humidity': ['high', 'normal']}, {'wind': ['yes', 'no']}, {'playtennis': ['positive', 'negative']}] print("以下是单纯的决策树算法:") # 实例化对象 a = ID3(data, label, Dict) # 输出决策树 print('决策树为', a.create_tree()) # 给定一组值,预测结果 info = ['rain', 'mild', 'normal', 'no'] info2=['sunny','hot','high','no'] print(f'[rain,mild,normal,no]预测结果为{a.predict(info)}') print(f'[sunny,hot,high,no]预测结果为{a.predict(info2)}') # 随机森林 print("----------------------------\n以下是引入随机森林的算法:") f = Forest(data, Dict) print(f'[rain,mild,normal,no]预测结果为{f.predict(info)}') print(f'[sunny,hot,high,no]预测结果为{f.predict(info2)}') # 运行时间 print("本次运行共花费了%.3f秒" % (time.time() - begin))
outlook,temperature,humidity,wind,playtennis
sunny,hot,high,no,negative
sunny,hot,high,yes,negative
overcast,hot,high,no,positive
rain,mild,high,no,positive
rain,cool,normal,no,positive
rain,cool,normal,yes,negative
overcast,cool,normal,yes,positive
sunny,mild,high,no,negative
sunny,cool,normal,no,positive
rain,mild,normal,no,positive
sunny,mild,normal,yes,positive
overcast,mild,high,yes,positive
overcast,hot,normal,no,positive
rain,mild,high,yes,negative
sunny,hot,high,no,negative
sunny,hot,high,yes,negative
overcast,hot,high,no,positive
rain,mild,high,no,positive
rain,cool,normal,no,positive
rain,cool,normal,yes,negative
overcast,cool,normal,yes,positive
sunny,mild,high,no,negative
sunny,cool,normal,no,positive
rain,mild,normal,no,positive
sunny,mild,normal,yes,positive
overcast,mild,high,yes,positive
overcast,hot,normal,no,positive
rain,mild,high,yes,negative
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。