机器学习算法--决策树与随机森林
决策树的算法比较简单
主要分为以下部分：
一、决策树基本概率以及计算（ID3）
1、决策树定义
决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的预测分析模型。比如我们会问‘今天出去玩吗’，那么室外的温度，天气都会影响我们做决策的过程，如果‘温度适中’，我们就再看‘天气如何’。
决策树学习的目地：产生一颗泛化能力强，处理未见示例强的决策树
2、决策树优缺点
决策树学习的优点：速度快，准确率高，对中间缺失值不敏感
决策树学习的缺点：对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征，容易过拟合，忽略属性之间的相关性
3、需要掌握熵和信息增益两个概念和计算公式
熵：对样本集合纯度的一种度量，k指的是样本类别个数
以表4.1为例：样本类别个数为2，即好瓜和坏瓜，好瓜8个概率为8/17，坏瓜9个概率为9/17。
那么可以计算根节点的熵为H=Ent(D)：
信息增益：
1、假定离散属性a有V个取值{a1，…aV}， 比如表4.1中，第一个属性色泽有3个取值，分别是青绿、乌黑、浅白，v=3。
2、若使用a色泽对样本集D进行划分，会产生V（3）个分支，其中第v个包含了D中在a属性上取值为av的所有样本，记为Dv。比如D1（色泽=青绿），D2（色泽=乌黑），D3（色泽=浅白）
3、再根据不同分支结点包含的样本数不同来给与权重：|Dv|/|D|，比如属性（色泽）=6/17
信息增益公式：
以色泽为例，计算3个分支的信息熵：
计算（属性=色泽）的信息增益：
类似地：我们计算其他属性的信息增益：
Gain（D，根蒂）=0.143
Gain（D，敲声）=0.141
Gain（D，根蒂）=0.381
Gain（D，根蒂）=0.289
Gain（D，根蒂）=0.006
其中纹理的信息增益最大，把纹理选为属性划分：
依照上述步骤再分类对纹理的三个属性进行划分，得到最后的划分结果。
这是我自己根据书上步骤写的程序：
import math
import pandas as pd
import operator
import numpy as np
def data():
dataSet = [
['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],
['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],
['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],
# ----------------------------------------------------
['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],
['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],
['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],
['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],
['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],
['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],
['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']
]
# 特征值列表
labels = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']
return dataSet,labels
###################################################################################
#信息熵
def Ent(df):
dic={}
EntD=0
#df = pd.DataFrame(dataset)
datalabel = df[df.shape[1] - 1] #获取最后一列的数据
for i in set(datalabel): #统计好瓜和坏瓜个数
dic[i]=sum(datalabel==i)
for i in dic.values(): #计算信息熵
EntD -=(i/len(df))*math.log(i/len(df),2)
return EntD
###################################################################################
#去除标签那一列的数据
def remove(df,i):
dicall = []
#df=pd.DataFrame(dataset)
lei=set(df[i]) #属性类别
for yangben in lei: #获取去除标签那列的数据
aa=df[(df[i]==yangben)]
aa=np.array(aa.drop([i], axis=1)).tolist() #删除标签列，转化为list保存
aa=pd.DataFrame(aa) #重新转化为dataframe格式
dicall.append(aa)
return dicall,lei
###################################################################################
#计算信息增益
def Gain(dataset,labels):
dic={}
for i in range(len(labels)): #遍历每个标签
ENtall = Ent(dataset) #得到信息熵
dataset1,shuxing=remove(dataset,i)
for j in range(len(shuxing)): #计算每个属性每个类别的信息熵
size=Ent(dataset1[j])
ENtall-= (len(dataset1[j])/len(dataset))*size #得到信息增益
dic[i] = ENtall #将属性和信息增益存在字典中
largelabels = sorted(dic.items(),key=operator.itemgetter(1), reverse=True) #将信息增益排序
return largelabels[0][0] # 返回最大的信息增益
###########################################################################
#返回最后类别中比较多的那一类[好瓜，好瓜，坏瓜]，返回好瓜
def largedata(dataset):
dic = {}
setnum=set(dataset[dataset.shape[1]-1])
for i in setnum:
dic[i]=sum(dataset[dataset.shape[1]-1]==i)
aa=sorted(dic.items(),key=operator.itemgetter(1),reverse=True)
return aa[0][0]
######################################################################
#生成决策树
def TreeGenerate1(dataset, labels):
df=pd.DataFrame(dataset)
if len(df)==1 : #第一个返回条件
return np.array(df[len(df.ix[0])-1]).tolist()[0]
labelset=set(df[len(labels)])
if len(labels) == 0 or len(labelset) == 1: #第二个返回条件
return largedata(dataset)
dic={}
dicall=[]
bestlabel=Gain(df,labels) #获取最好标签
dataset1,shu=remove(df,bestlabel) #去除最好标签的数据集和属性类别
#pdb.set_trace()
linedata1 = labels[:bestlabel]
linedata1.extend(labels[bestlabel + 1:]) #在列表中删除最好标签
#pdb.set_trace()
for i,aa in enumerate(shu): #遍历属性类别
dic1 = {}
dic1[aa]=TreeGenerate1(dataset1[i], linedata1) #生成字典dic1={清晰：？，模糊：？，稍糊：？}
dicall.append(dic1)
dic[labels[bestlabel]]=dicall #再将上边的字典放入大字典中{纹理：dic1}
return dic
########################################################################
dataset, labels = data()
regr_1=TreeGenerate1(dataset, labels )
print(regr_1)
程序结果：
{'纹理': [{'清晰': {'根蒂': [{'稍蜷': {'色泽': [{'青绿': '好瓜'}, {'乌黑': {'触感': [{'软粘': '坏瓜'}, {'硬滑': '好瓜'}]}}]}}, {'硬挺': '坏瓜'}, {'蜷缩': '好瓜'}]}}, {'稍糊': {'触感': [{'软粘': '好瓜'}, {'硬滑': '坏瓜'}]}}, {'模糊': '坏瓜'}]}
程序讲解：
以下是整个程序的流程图：
二、信息增益率
著名的C4.5算法就提出不使用信息增益，而使用信息增益率来划分最优属性。信息增益率的出现是因为信息增益不够好，信息增益对可取值数目较多的属性有所偏好，这样会造成决策树分支多，深度浅。举例：比如表4.1中，将编号也划为属性。那么编号中有17个取值。Ent(Di)=0,Gain（编号）=0.998。这时候就会变成：
可见由编号作为划分条件虽然可以直接判断西瓜的好坏，但是这样的分支属性太多，并不一定是最好的。
信息增益率公式：
Gain(D,a)我们通过第一节已经求出来了，信息增益率就是用信息增益除以IV（a）。v就是属性的类别数目，比如色泽（青绿，乌黑，浅白）v=3。
得到IV（色泽）=1.580（v=3）
增益率准则对属性类别较少的属性（触感V=2）有所偏好，所以C4.5不直接使用增益率最大的候选划分属性，而是先选出信息增益高于平均值的属性，再从中选择增益率最高的一个。
三、CART基尼指数
数据集D的纯度可以用基尼值来度量
表4.1中，以属性色泽为例
基尼系数越小，属性越优。
Gini 指数的计算不需要对数运算，更加高效；
Gini 指数更偏向于连续属性，熵更偏向于离散属性。
四、决策树的过拟合
决策树的对训练数据集有很好的分类能力，但是对未知的测试书籍未必有很好的分类能力，泛化能力弱，容易发生过拟合。剪枝是处理过拟合问题的重要手段。剪枝分为预剪枝和后剪枝。
随机森林是一种比较好的处理决策树过拟合的方法。
1、随机森林来源
Bagging策略
（从样本中重采样（有重复）选出n个样本。
在所有属性上对n个样本建立分类器（ID3、C4.5、CART、SVM、logistic回归））
重复以上m次，得到m个分类器
根据这m个分类器的结果，决定数据属于哪一类
2、随机森林在Bagging基础上做了修改
随机森林策略
（从数据集中用Bootstrap采样选出n个样本；
从所有属性中随机选出k个属性，选择最佳分割属性作为节点建立CART决策树）
重复以上步骤m次，就得到m棵CART决策树
这m个决策树就是随机森林，通过投票表决结果
3、随机森林/Bagging/决策树的关系
- 随机森林和Bagging可以使用决策树为基本分类器
- 也可以使用SVM、Logistic回归等其他分类器，习惯上，这些分类器组成总的“分类器”，仍然叫随机森林