决策树中的连续值与缺失值处理的实现思路

连续值处理

由于连续数据不能划分，所以要使用连续属性离散化技术，其中最简单的方法就是二分法（bi-partition）。 首先要构造一个候选划分点集合：从数据集中取相邻两个元素的平均值，然后构成一个待选的节点，假设一个数据集共有n个元素，则可以生成n-1个 候选分割点。 以西瓜数据集3.0为例的密度为例：

编号,色泽,根蒂,敲声,纹理,脐部,触感,密度,含糖率,好瓜 1,青绿,蜷缩,浊响,清晰,凹陷,硬滑,0.697,0.46,是 2,乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,0.774,0.376,是 3,乌黑,蜷缩,浊响,清晰,凹陷,硬滑,0.634,0.264,是 4,青绿,蜷缩,沉闷,清晰,凹陷,硬滑,0.608,0.318,是 5,浅白,蜷缩,浊响,清晰,凹陷,硬滑,0.556,0.215,是 6,青绿,稍蜷,浊响,清晰,稍凹,软粘,0.403,0.237,是 7,乌黑,稍蜷,浊响,稍糊,稍凹,软粘,0.481,0.149,是 8,乌黑,稍蜷,浊响,清晰,稍凹,硬滑,0.437,0.211,是 9,乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,0.666,0.091,否 10,青绿,硬挺,清脆,清晰,平坦,软粘,0.243,0.267,否 11,浅白,硬挺,清脆,模糊,平坦,硬滑,0.245,0.057,否 12,浅白,蜷缩,浊响,模糊,平坦,软粘,0.343,0.099,否 13,青绿,稍蜷,浊响,稍糊,凹陷,硬滑,0.639,0.161,否 14,浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,0.657,0.198,否 15,乌黑,稍蜷,浊响,清晰,稍凹,软粘,0.36,0.37,否 16,浅白,蜷缩,浊响,模糊,平坦,硬滑,0.593,0.042,否 17,青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,0.719,0.103,否

说一下思路：以密度这个属性为例，首先，取出来这一列的数据，然后用一个for循环遍历一遍 循环的终止条件是n-1 ，使用这个式子生成一个candidate_set 备选划分点数据集

for x in range(density.shape[0]-1): candidate_sets.append((density[x]+density[x+1])/2)

大概就是上面描述的样子。有了这个备选集合，我们就要拿着这个集合给数据集进行划分，备选元素中每一个都要作为标准进行划分，并求出来划分前后的信息增益【不清楚出怎么求得可以看这一篇文章 西瓜书中的决策树算法实现（ID3） 】然后选择信息增益最大是分割点 。下面用到一些函数split_data（）将数据集划分，Ent（）求数据集得信息熵，是上述链接中建立得，要想知其所以然得话，还是看上述链接。

def find_opt_discretization(D,candidate_sets): origin_entry=Ent(D)# 计算原始得信息熵 gains=[]# 建立列表 用于保存这些信息增益数据 for element in candidate_sets: d_dict=split_data(D,element)# 将数据集根据所给出的密度值划分为两个集合 set_1,set_2=np.array(d_dict['D1']),np.array(d_dict['D2']) proportion=set_1.shape[0]/D.shape[0]#计算分割后子数据集对原有数据集的比例 new_entry=proportion*Ent(set_1)+(1-proportion)*Ent(set_2)# 求出新的信息熵 gains.append(origin_entry-new_entry) return max(gains),candidate_sets[gains.index(max(gains))] # 这一句candidate_sets[gains.index(max(gains))] ，需要拆分来看，先找到gains中得最大值，继而找到最大值得索引，然后在根据索引找到对应得划分点。

这个连续数据得划分系统全部代码如下：

from numpy.ma import fabs import pandas as pd import numpy as np df=pd.read_csv("ml3.0.csv") density=np.array(sorted(np.array(df['密度']))) D=np.array(df[['密度','好瓜']]) candidate_sets=[] for x in range(density.shape[0]-1): candidate_sets.append((density[x]+density[x+1])/2) def collect(D): D=np.array(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)+0.0000000000001 if (fabs(1.0 - p) < 0.000001) or (fabs(0.0 - p) < 0.000001): return -1 #表示完全分割开了 return -p*np.log2(p)-(1-p)*np.log2(1-p) def split_data(D,density): temp_dict={"D1":[],"D2":[]} for i in D: if i[0]<density: temp_dict['D1'].append(i) else: temp_dict['D2'].append(i) return temp_dict #然后计算每一个划分点的信息增益 def find_opt_discretization(D,candidate_sets): origin_entry=Ent(D) gains=[] for element in candidate_sets: d_dict=split_data(D,element) set_1,set_2=np.array(d_dict['D1']),np.array(d_dict['D2']) proportion=set_1.shape[0]/D.shape[0] new_entry=proportion*Ent(set_1)+(1-proportion)*Ent(set_2) gains.append(origin_entry-new_entry) return max(gains),candidate_sets[gains.index(max(gains))] print(find_opt_discretization(D,candidate_sets))

运行结果：

(0.4977333780516909, 0.38149999999999995)

只要将其嵌入到原来得决策树函数中就可以了。

缺失值处理

大部分数据都是有缺失项得，所以确实值得处理很重要。 【】在此时 突然想到 根据聚类 进行缺失值的补充。嘿嘿，不过现在还没有开始学习数据挖掘，在这里挖一个坑吧！ 等以后学过数据挖掘后过来填坑（2020/10/8）

编号,色泽,根蒂,敲声,纹理,脐部,触感,好瓜 1,,蜷缩,浊响,清晰,凹陷,硬滑,是 2,乌黑,蜷缩,沉闷,清晰,凹陷,,是 3,乌黑,蜷缩,,清晰,凹陷,硬滑,是 4,青绿,蜷缩,沉闷,清晰,凹陷,硬滑,是 5,,蜷缩,浊响,清晰,凹陷,硬滑,是 6,青绿,稍蜷,浊响,清晰,,软粘,是 7,乌黑,稍蜷,浊响,稍糊,稍凹,软粘,是 8,乌黑,稍蜷,浊响,,稍凹,硬滑,是 9,乌黑,,沉闷,稍糊,稍凹,硬滑,否 10,青绿,硬挺,清脆,,平坦,软粘,否 11,浅白,硬挺,清脆,模糊,平坦,,否 12,浅白,蜷缩,,模糊,平坦,软粘,否 13,,稍蜷,浊响,稍糊,凹陷,硬滑,否 14,浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,否 15,乌黑,稍蜷,浊响,清晰,,软粘,否 16,浅白,蜷缩,浊响,模糊,平坦,硬滑,否 17,青绿,,沉闷,稍糊,稍凹,硬滑,否

下面使用书中介绍的方法, 定义时间： 数据集D ， 属性a， D中在属性a上没有缺失的样本子集D1， 属性a中无缺失样本的比例$\rho$ 属性a无缺样本中第k类所占的比例 ${\rho }_k$ 属性a无缺样本中属性a取值为v的比例 $r_v$ 定义完毕。

有几个显然： 属性a无缺样本中第k类所占的比例之和，肯定是1 属性a无缺样本中属性a取值为v的比例 之和，肯定是1

有了上面的定义，我们来分析下有缺失值下的信息增益公式。 $$Gain(D,a)=\rho \ast (Ent(D)-\sum _{v=1}^V{r}_{v}Ent(D^v))$$

【】写道这里，我感觉只是用了未缺失的a属性取值，直接对缺失值视而不见啊。像极了用不缺失的值构建一个集合，然后用这个新的集合进行运算。可是这个也隐藏着许多问题，比如如果数据集中a的一个属性的取值全部丢失了，但是测试集中包含有该属性，怎么办？这些都是以后要考虑的

下面就是解决方案啦，如果对于一个样本进行属性划分， 如果样本在属性a上的取值已知，那很好办，只要将该样本划分给对应的分支就可以了。 并保持x的权值不变。 但是，如果样本在属性a上的取值未知，那将a 划分到所有的子节点，但权值要根据所在属性在属性a中所占的比例，对没错，就是$r_v$, 就是将$w_x修正为r_v\ast w_x$

下面写写具体的实现步骤： 在以前的基础上，现在需要一个过滤器，过滤到那些有缺失值的样本，不如就叫他 null_filter 吧，这个函数肯定需要一个数据集D ，就是原始数据集，并且还需要一个属性，因为你是要过滤某个属性的缺失值。综上所述，可以得到一个函数

def null_filter(D,a): return D1 #返回过滤后的数据集

下面考虑下，这个函数要如何操作： 查看一条记录，如果对应的属性不空，就复制一份留下来， 如果为空，就跳过。 然后查看下一条 这明显是for循环啊

def null_filter(D,a): #首先要拿到a的索引,这个是直前定义的一个列表 static_arrt 记录了各个属性在样本中的位置 index = static_attr.index(a) D1=[] for i in D： if i[index]!=NAN: D1.append(i) return np.array(D1)#返回过滤后的数据集

下面对这个功能做一个单元测试吧；

import pandas as pd import numpy as np df=pd.read_csv("ml2.0a.csv") static_attr=df.columns.values.tolist()[1:]#这里的属性 不改变，仅仅作为索引 df = df.fillna("-")# 使用"-" 去代替空值。 D=np.array(df[static_attr]) def null_filter(D,a): index=static_attr.index(a) D1=[] for i in D: if i[index]!='-': D1.append(i) return np.array(D1) print(null_filter(D,"色泽"))

输出结果：

[['乌黑' '蜷缩' '沉闷' '清晰' '凹陷' '-' '是'] ['乌黑' '蜷缩' '-' '清晰' '凹陷' '硬滑' '是'] ['青绿' '蜷缩' '沉闷' '清晰' '凹陷' '硬滑' '是'] ['青绿' '稍蜷' '浊响' '清晰' '-' '软粘' '是'] ['乌黑' '稍蜷' '浊响' '稍糊' '稍凹' '软粘' '是'] ['乌黑' '稍蜷' '浊响' '-' '稍凹' '硬滑' '是'] ['乌黑' '-' '沉闷' '稍糊' '稍凹' '硬滑' '否'] ['青绿' '硬挺' '清脆' '-' '平坦' '软粘' '否'] ['浅白' '硬挺' '清脆' '模糊' '平坦' '-' '否'] ['浅白' '蜷缩' '-' '模糊' '平坦' '软粘' '否'] ['浅白' '稍蜷' '沉闷' '稍糊' '凹陷' '硬滑' '否'] ['乌黑' '稍蜷' '浊响' '清晰' '-' '软粘' '否'] ['浅白' '蜷缩' '浊响' '模糊' '平坦' '硬滑' '否'] ['青绿' '-' '沉闷' '稍糊' '稍凹' '硬滑' '否']]

【思考开始 错误内容可以忽略 】 应该这个样子就可以了。 但是如何把它安装到决策树中，也是比较复杂。还有权重的问题，加在哪里，怎么加这些都是问题啊！ 先来考虑权重吧，每个样本都要加，对吧？ 那麽说 每一个样本就会与一个对应的列表存放权重对吧？ 比如

['乌黑' '蜷缩' '沉闷' '清晰' '凹陷' '-' '是'] #对应的矩阵就应该是 [ 1, 1, 1, 1, 1, 1, 1 ]

也就是说会有一个同维的系数矩阵与之对应。通过原矩阵的序号进行匹配。那是都要有一个函数，我们叫他get_weight() 用于获得一个样本的权重。然后并可以修改这个权重，那说，这个矩阵应该是一个全局属性，定义在函数之外。

#crate a weight matrix weight= np.ones(D.shape)#创建一个同维的矩阵用于记录权重。 def getweight(i): #这里i是一条记录 # 现在要将每条记录加上一个编号，用于联系样本和权重。 index=i[0]-1# 序号和索引差一 return weight[index]

【思考结束 下面内容可以继续收看 】 不对不对，不是只维护一个权重矩阵，是这样的，每一条记录都会有一个自己的 权重，然后默认是1，但是如果碰到一个缺失属性，那么它就会被复制三份，然后被分配到三个组中，这样的继续划分 所以说媒体条记录都会多一列，用来存档权重。不如就用第一行的编号来存储。嗯，这些都做到了，代码上已经实现了，但是做出来的决策树和书本上的有点不一样。我在去检查一下。现在差不多搞定了：第一轮的信息增益如下，和西瓜书上一致。

色泽信息增益: 0.25196581765610376 根蒂信息增益: 0.17117826469169223 敲声信息增益: 0.14480291082659255 纹理信息增益: 0.42356026795367896 脐部信息增益: 0.2888253235152557 触感信息增益: 0.005713029850070782

现在还是从权重开始说起，原来每个样本没有属性缺失，所以等我们算一个数据集正负样本的时候，”是“就是正样本，“否”就是负样本 。但是有了权重之后，一切都不一样了，比如

[[1 '-' '稍蜷' '浊响' '稍糊' '凹陷' '硬滑' '否'] [0.3'乌黑' '稍蜷' '浊响' '-' '稍凹' '硬滑' '是']]

这种情况下，正负样本的比例就变成了 $$p=\frac{0.3\ast 1}{1\ast 1}$$ 所以，在计算正负样本比例的时候，要注意这一点。 下面是修正之后的collect 函数

def collect(D): D=np.array(D) if D.shape[0]==0:# 一个小平滑 return 0.0000000001 count= 0 for i in D:# 就是在这里乘了i[0]这个系数 count=count+1*i[0] if i[-1]=='是' else count return count /(D.shape[0])

然后信息熵的计算并没有什么新的修改

def Ent(D): p=collect(D)+0.0000000000001 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 Gain(D,a): old_size=D.shape[0] D=null_filter(D,a) new_size=D.shape[0] G=Ent(D) index = static_attr.index(a) lis=attr_dict[a] temp_dict=try_split_data(D,a) sum=0 for x in lis: d=np.array(temp_dict[x]) t=(d.shape[0]/D.shape[0])*Ent(d) # print(Ent(d)) sum+=t return (new_size/old_size)*(G-sum)

对于集合的划分，做了较大的改动，而且还拆分为两个了，原因如下： 当我们计算信息增益的时候，缺失值是不参与的，但是当我们进行划分的时候，缺失值需要参与。 于是我用try_split_data表示原来的split_data 只是进行计算信息增益时的假划分。用real_split_data 表示真正的划分，也就是带权重的划分；

def real_split_data(D,a): index = static_attr.index(a) lis=attr_dict[a] temp_dict={} count={}# 用于记录每种属性所占的个数 for i in lis: temp_dict[i]=[] count[i]=0 total=0 #记录共有多少个非空的数据 for i in D:# 这个数据集只处理不缺失的值 for at in lis: if i[index]==at: temp_dict[at].append(i) count[at]+=1 total+=1 break; #等常规值处理完之后处理下缺失值： for i in D:#处理缺失值，修改权重 并添加到每一个分支 if i[index]=='-': for at in lis: i[0]=count[at]/total# 修改权重 temp_dict[at].append(i)#添加到每一个分支 return temp_dict

还有一处需要修改，因为当时我们创建属性字典的时候，默认没有缺失文件的，现在有缺失值，如果不除去缺失值，那么分类会出问题。所以修改为这样

attr_dict={}#用于记录每一个属性的取值 for x in attr: temp=np.array(df[x]) t=list(set(temp)) t.remove('-') attr_dict[x]=t

嗯哼？ 到这里就差不多了。下面看源代码

from numpy.ma import fabs import pandas as pd import numpy as np df=pd.read_csv("ml2.0a.csv") static_attr=df.columns.values.tolist()[0:]#这里的属性 不改变，仅仅作为索引' df['编号'] = 1# 将编号哪一列全部初始化为1 ，df 操作起来真好，真方便。 df = df.fillna("-")# 使用"-" 去代替空值。 data_org=np.array(df[static_attr]) attr=static_attr[1:-1]# 此处记录的是备选属性 weight= np.ones((data_org.shape[0],len(attr)))#创建一个同维的矩阵用于记录权重。 attr_dict={}#用于记录每一个属性的取值 for x in attr: temp=np.array(df[x]) t=list(set(temp)) t.remove('-') attr_dict[x]=t #到这里，准备工作应该差不多了。 # 下面把信息熵那些搬过来 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): D=np.array(D) if D.shape[0]==0: return 0.0000000001 count= 0 for i in D: count=count+1*i[0] if i[-1]=='是' else count return count /(D.shape[0]) def Ent(D): p=collect(D)+0.0000000000001 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 null_filter(D,a): index=static_attr.index(a) D1=[] for i in D: if i[index]!='-': D1.append(i) return np.array(D1) def real_split_data(D,a): index = static_attr.index(a) lis=attr_dict[a] temp_dict={} count={} for i in lis: temp_dict[i]=[] count[i]=0 total=0 for i in D: for at in lis: if i[index]==at: temp_dict[at].append(i) count[at]+=1 total+=1 break; #等常规值处理完之后处理下缺失值： for i in D: if i[index]=='-': for at in lis: i[0]=count[at]/total temp_dict[at].append(i) return temp_dict def try_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(D,a): old_size=D.shape[0] D=null_filter(D,a) new_size=D.shape[0] G=Ent(D) index = static_attr.index(a) lis=attr_dict[a] temp_dict=try_split_data(D,a) sum=0 for x in lis: d=np.array(temp_dict[x]) # print("____________________start_________________") # print(d) # print("____________________end_________________") t=(d.shape[0]/D.shape[0])*Ent(d) # print(Ent(d)) sum+=t return (new_size/old_size)*(G-sum) 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))] tree={} def TreeGenerate(D,d_attr,node,father):#ID3算法 if type(D)==dict:return if D.shape[0]==0: node['final']="undefind" 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) #根据最优属性划分集合： attr_dict=real_split_data(D,opt_attr) d_attr.remove(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,tree,"root") print(tree) # for i in static_attr[1:-1]: # print(i+"信息增益:",Gain(data_org,i))

运行结果 ：

D:\PYTHON\python.exe C:/Users/dell/Desktop/python/DecisionTree/Missing_value.py {'纹理': {'清晰': {'根蒂': {'稍蜷': {'色泽': {'青绿': {'final': '是'}, '浅白': {'final': 'undefind'}, '乌黑': {'触感': {'硬滑': {'final': '是'}, '软粘': {'final': '否'}}}}}, '硬挺': {'final': '否'}, '蜷缩': {'final': '是'}}}, '稍糊': {'敲声': {'沉闷': {'final': '否'}, '清脆': {'final': '否'}, '浊响': {'触感': {'硬滑': {'脐部': {'稍凹': {'final': '是'}, '平坦': {'final': 'undefind'}, '凹陷': {'final': '否'}}}, '软粘': {'final': '是'}}}}}, '模糊': {'色泽': {'青绿': {'final': '否'}, '浅白': {'final': '否'}, '乌黑': {'final': '是'}}}}} Process finished with exit code 0

就这样，一篇文章写了一天，现在是21：42 分 。差不多可以收拾下回宿舍了。 今天是国庆假期的最后一天，祝大家复工快乐！