使用增益率划分属性的决策树（C4.5）

当使用信息增益大小作为划分依据时会遇到一个问题：

当使用编号这个属性进行划分时，会将数据划分为17个分组，并且每个分组的纯度都是1，这样的样本不具有泛化能力，不能预测 新数据 ——西瓜书

同时由于我们在计算信息增益时给每个分支增加了权重，这样本数多的分支结点影响更大。因此（ID3）就有点偏向数量多样本的趋势。于是昆兰在1993年 在C4.5中使用增益率代替了信息增益。 增益率说白了就是在原有的信息增益的基础上，比上属性A的’固有值‘ $$增益率=\frac{Gain(D,a)}{IV(a)}$$ 其中，IV(a)就是a的‘固有值’ $$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}log2\frac{|D^v|}{|D|}$$ 其实这个比例，我们之前计算，我们拿出Gian(D,a) 这个公式然后整合一下就会有 $$增益率=\frac{Gain(D,a)}{IV(a)}=\frac{Ent(D)-{\sum }_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)}{-{\sum }_{v=1}^V\frac{|D^v|}{|D|}log2\frac{|D^v|}{|D|}}$$ 好吧，并不能化简，那就这样吧，我们先拿出来上一期西瓜书中的决策树算法实现（ID3） 的Gian的函数

def Gain(D,a): G=Ent(D) index = static_attr.index(a) lis=attr_dict[a] temp_dict=split_data(D,a) sum=0 for x in lis: d=np.array(temp_dict[x]) sum+=(d.shape[0]/D.shape[0])*Ent(d) return G-sum

改造后

def Gain_ratio(D,a): G=Ent(D) index = static_attr.index(a) lis=attr_dict[a] temp_dict=split_data(D,a) sum,vi=0,0 for x in lis: d=np.array(temp_dict[x]) p=d.shape[0]/D.shape[0]#剥离出来进行复用 vi-=p*np.log2(p)#计算a的固有值 sum+=(p)*Ent(d) return G-sum,(G-sum)/vi # 以增益和增益率的形式返回

看了上面的代码，和开始分析的一样，就是两个公式的合并，但这就完美了吗？答案是否定的！基于增益率的解决方案，对取值较少的属性有所偏好 【注】这个偏好，究竟体现在哪里，我也不太清楚，以后补充吧 西瓜书：采用一种启发式：先选择高于平均水平的增益率，然后在其中挑选增益率最高的。这个方案可操作性也很强，直接求两个列表，一个存放增益，一个存放增益率，选择一下就可以了。 只需要再修改下选择最优属性的函数

原函数：

def select_opt_attr(D,d_attr): li=[] for x in d_attr: li.append(Gain(D,x)) return d_attr[li.index(max(li))]

做修改：

def select_opt_attr(D,d_attr): gains,gain_ratios=[],[] for x in d_attr: gain,gian_ratio=Gain_ratio(D,x) gains.append(gain) gain_ratios.appnd(gain_ratio) # 求一个平均值，然后作为分界线 ，然后找到增益率最高的 average=np.mean(gains) new=[x for x in gains if x>=average] if len(new)==1:return sort(gain_ratio,reverse=True) sort(new,key=gain_ratio.index,reverse=True) return new[0]

源代码：

from math import fabs import pandas as pd import numpy as np df=pd.read_csv("./ml2.0.csv") # 属性集合 attr=df.columns.values.tolist()[1:] data_org=np.array(df[attr[0:]]) static_attr=df.columns.values.tolist()[1:]#这里的属性 不改变，仅仅作为索引 attr_dict={}#用于记录每一个属性的取值 for x in attr: temp=np.array(df[x]) attr_dict[x]=set(temp) def label_is_same(D): l=[D[i][-1] for i in range(len(D))] return len(list(set(l)))==1 def all_attr_is_same(D,d_attr): if D.shape[0]==0:return True #如果是空集 for x in d_attr: index=static_attr.index(x) for i in D[0:] : if i[index]!=D[0][index]: return False return True # 统计某个属性中，正样本和负样本的比例： def collect(D): if D.shape[0]==0: return 0.0000000001 count= 0 for i in D: count=count+1 if i[-1]=='是' else count return count /(D.shape[0]) def Ent(D): p=collect(D) if (fabs(1.0 - p) < 0.000001) or (fabs(0.0 - p) < 0.000001): return 0 #表示完全分割开了 return -p*np.log2(p)-(1-p)*np.log2(1-p) def split_data(D,a): index = static_attr.index(a) lis=attr_dict[a] temp_dict={} for i in lis: temp_dict[i]=[] for i in D: for at in lis: if i[index]==at: temp_dict[at].append(i) break; return temp_dict def Gain_ratio(D,a): G=Ent(D) index = static_attr.index(a) lis=attr_dict[a] temp_dict=split_data(D,a) sum,vi=0,0 for x in lis: d=np.array(temp_dict[x]) p=(d.shape[0]/D.shape[0])+0.000000001#剥离出来进行复用 vi-=p*np.log2(p)#计算a的固有值 sum+=(p)*Ent(d) return G-sum,(G-sum)/vi # 以增益和增益率的形式返回 def select_opt_attr(D,d_attr): gains,gain_ratios=[],[] for x in d_attr: gain,gain_ratio=Gain_ratio(D,x) gains.append(gain) gain_ratios.append(gain_ratio) # 求一个平均值，然后作为分界线 ，然后找到增益率最高的 average=np.mean(gains) #使用index的方式可能会有重复的啊，这是一个大问题 new=[d_attr[gains.index(x)] for x in gains if x>=average] if len(new)==1:return new[0] static_ratios=gain_ratios[:] sorted(gain_ratios,reverse=True) new_ratios=[d_attr[static_ratios.index(x)] for x in gain_ratios] sorted(new,key=new_ratios.index,reverse=True) print(new[0]) return new[0] node={} def TreeGenerate(D,d_attr,node,father):#ID3算法 if D.shape[0]==0: return if label_is_same(D): node['final']=D[-1][-1] return if len(d_attr)==0 or all_attr_is_same(D,d_attr):# 属性集为空 或者所有样本在说有属性上取值相同 node['final']='是' if collect(D)>0.5 else '否' return #选择最优的划分属性： opt_attr=select_opt_attr(D,d_attr) d_attr.remove(opt_attr) #根据最优属性划分集合： attr_dict=split_data(D,opt_attr) node[opt_attr]={} for i in attr_dict: d1=np.array(attr_dict[i]) node[opt_attr][i]={} TreeGenerate(d1,d_attr[:],node[opt_attr][i],i) TreeGenerate(data_org,attr[:-1],node,"root") print(node)

但是使用这个方法之后，稍糊部分下的分类明显变多，应该是冗余，这个问题，可能是触感它的信息增益很高，但是增益率不高，所以被淘汰了，取而代之的是更复杂的分类方式，那么这个改进到底是好还是不好呢?