看懂代码的前提需要理解样本空间分布，概率密度，香农熵，条件熵，信息增益等概念，
否则代码看不懂，不理解的可以看以前博客~
1.说明
1.1要实现的类
class CSamplesTool(object)
1.2输入的样本集
输入的样本集，样例由下面的方法提供：
def create_samples():
'''
提供训练样本集
每个example由多个特征值+1个分类标签值组成
比如第一个example=['youth', 'no', 'no', '1', 'refuse'],此样本的含义可以解读为：
如果一个人的条件是：youth age，no working, no house, 信誉值credit为1
那么此类人会被分类到refuse一类中，即在相亲中被拒绝
每个example的特征值类型为：
['age', 'working', 'house', 'credit']
每个example的分类标签class_label取值范围为：'refuse'或者'agree'
'''
data_list = [['youth', 'no', 'no', '1', 'refuse'],
['youth', 'no', 'no', '2', 'refuse'],
['youth', 'yes', 'no', '2', 'agree'],
['youth', 'yes', 'yes', '1', 'agree'],
['youth', 'no', 'no', '1', 'refuse'],
['mid', 'no', 'no', '1', 'refuse'],
['mid', 'no', 'no', '2', 'refuse'],
['mid', 'yes', 'yes', '2', 'agree'],
['mid', 'no', 'yes', '3', 'agree'],
['mid', 'no', 'yes', '3', 'agree'],
['elder', 'no', 'yes', '3', 'agree'],
['elder', 'no', 'yes', '2', 'agree'],
['elder', 'yes', 'no', '2', 'agree'],
['elder', 'yes', 'no', '3', 'agree'],
['elder', 'no', 'no', '1', 'refuse']]
feat_type_list = ['age', 'working', 'house', 'credit']
return data_list, feat_type_list
1.3输出的样本集的特征分布、概率密度、香农熵、条件熵、信息增益组成的字典
对于样例的样本集，通过类的计算，输出如下目标字典，字典内部包含了样本集的香农熵、特征分布、特征概率密度、条件熵、信息增益等信息：
1.3.1运行结果截图
1.3.2运行结果log
feat_dict = {
house :{
condition_entropy : 0.5509775004326937
cnt : 15
info_gain : 0.4199730940219749
yes : {'cnt': 6, 'refuse': 0, 'shannon_entropy': 0.0, 'p_agree': 1.0, 'p_refuse': 0.0, 'p_house': 0.4, 'agree': 6}
no : {'cnt': 9, 'refuse': 6, 'shannon_entropy': 0.9182958340544896, 'p_agree': 0.3333333333333333, 'p_refuse': 0.6666666666666666, 'p_house': 0.6, 'agree': 3}
}
credit :{
condition_entropy : 0.6079610319175832
cnt : 15
3 : {'cnt': 4, 'refuse': 0, 'p_credit': 0.26666666666666666, 'shannon_entropy': 0.0, 'p_agree': 1.0, 'p_refuse': 0.0, 'agree': 4}
1 : {'cnt': 5, 'refuse': 4, 'p_credit': 0.3333333333333333, 'shannon_entropy': 0.7219280948873623, 'p_agree': 0.2, 'p_refuse': 0.8, 'agree': 1}
info_gain : 0.36298956253708536
2 : {'cnt': 6, 'refuse': 2, 'p_credit': 0.4, 'shannon_entropy': 0.9182958340544896, 'p_agree': 0.6666666666666666, 'p_refuse': 0.3333333333333333, 'agree': 4}
}
working :{
condition_entropy : 0.6473003963031123
cnt : 15
info_gain : 0.32365019815155627
yes : {'cnt': 5, 'refuse': 0, 'shannon_entropy': 0.0, 'p_working': 0.3333333333333333, 'p_agree': 1.0, 'p_refuse': 0.0, 'agree': 5}
no : {'cnt': 10, 'refuse': 6, 'shannon_entropy': 0.9709505944546686, 'p_working': 0.6666666666666666, 'p_agree': 0.4, 'p_refuse': 0.6, 'agree': 4}
}
age :{
condition_entropy : 0.8879430945988998
cnt : 15
info_gain : 0.08300749985576883
elder : {'cnt': 5, 'refuse': 1, 'p_age': 0.3333333333333333, 'shannon_entropy': 0.7219280948873623, 'p_agree': 0.8, 'p_refuse': 0.2, 'agree': 4}
youth : {'cnt': 5, 'refuse': 3, 'p_age': 0.3333333333333333, 'shannon_entropy': 0.9709505944546686, 'p_agree': 0.4, 'p_refuse': 0.6, 'agree': 2}
mid : {'cnt': 5, 'refuse': 2, 'p_age': 0.3333333333333333, 'shannon_entropy': 0.9709505944546686, 'p_agree': 0.6, 'p_refuse': 0.4, 'agree': 3}
}
}
2.话不多说，直接上代码
# -*- coding: utf-8 -*-
"""
@author: 蔚蓝的天空Tom
Talk is cheap,show me the code
Aim:样本集中每种类型特征的变量分布、概率分布、香农熵、条件熵
Aim:每种类型特征都分别有多种特征值，请萃取出每个特征值的样本数据
Aim:求每种特征值被分类的概率分布
"""
import numpy as np
import math
'''Tool Function'''
varnamestr = lambda v,nms: [ vn for vn in nms if id(v)==id(nms[vn])][0]
#============================================
class CUtileTool(object):
'''
提供有用的方法
比如dump_list方法，可以打印给定的list的相关信息
'''
def dump_list(self, src_list, src_list_namestr):
'''
逐行打印list
:param self:类实例自身
:param src_list:被打印的源list
:return 无
'''
print('\n============',src_list_namestr,'================')
list_len = len(src_list)
list_shape = np.shape(src_list)
print('type(',src_list_namestr,'):',type(src_list)) #<class 'list'>
print('np.shape(',src_list_namestr,'):',np.shape(src_list))
if 1 == len(list_shape):
print(src_list)
elif 2 == len(list_shape):
for i in range(list_len):
if 0 == i:
print('[',src_list[i])
elif (list_len - 1) == i:
print(src_list[i],']')
else:
print(src_list[i])
else:
print(src_list)
print('======\n')
return
def dump_array(self, src_a, src_dict_namestr):
'''
逐行打印array
:param self:类实例自身
:param src_a:被打印的源array
:return 无
'''
print('\n===============',src_dict_namestr,'===================')
a_len = len(src_a)
a_shape = np.shape(src_a)
print('type(',src_dict_namestr,'):',type(src_a)) #<class 'list'>
print('np.shape(',src_dict_namestr,'):',np.shape(src_a))
if 1 == len(a_shape):
print(src_a)
elif 2 == len(a_shape):
for i in range(a_len):
if 0 == i:
print('[',src_a[i])
elif (a_len - 1) == i:
print(src_a[i],']')
else:
print(src_a[i])
else:
print(src_a)
print('======\n')
return
def print_dict(self, src_dict, level, src_dict_namestr=''):
'''
逐行打印dict
:param self:类实例自身
:param src_dict:被打印的dict
:param level:递归level，初次调用为level=0
:param src_dict_namestr:对象变量名称字符串
'''
if isinstance(src_dict, dict):
tab_str = '\t'
for i in range(level):
tab_str += '\t'
if 0 == level:
print(src_dict_namestr,'= {')
for key, value in src_dict.items():
if isinstance(value, dict):
has_dict = False
for k,v in value.items():
if isinstance(v, dict):
has_dict = True
if has_dict:
print(tab_str,key,":{")
self.print_dict(value, level + 1)
else:
print(tab_str,key,':',value)
else:
print(tab_str,key,': ',value,)
print(tab_str,'}')
def dump_dict(self, src_dict, src_dict_namestr):
'''
逐行打印dict
:param self:类实例自身
:param src_dict:被打印的dict对象
:return 无
'''
print('\n===============',src_dict_namestr,'===================')
dict_len = len(src_dict)
dict_shape = np.shape(src_dict)
dict_type = type(src_dict)
print('len(',src_dict_namestr,'):',dict_len)
print('type(',src_dict_namestr,'):', dict_type) #<class 'dict'>
print('np.shape(',src_dict_namestr,'):', dict_shape)
print('len(dict_shape):', len(dict_shape))
self.print_dict(src_dict, 0, src_dict_namestr)
print('======\n')
return
def dump(self, src_thing, src_thing_namestr):
'''
逐行打印变量(list, array, matrix等)
:param self：类实例自身
:param src_things：被打印者
:return 无
'''
if isinstance(src_thing, list):
return self.dump_list(src_thing, src_thing_namestr)
elif isinstance(src_thing, np.ndarray):
return self.dump_array(src_thing, src_thing_namestr)
elif isinstance(src_thing, dict):
return self.dump_dict(src_thing, src_thing_namestr)
else:
print(src_thing_namestr,':', src_thing)
return
#===========================================
def create_samples():
'''
提供训练样本集
每个example由多个特征值+1个分类标签值组成
比如第一个example=['youth', 'no', 'no', '1', 'refuse'],此样本的含义可以解读为：
如果一个人的条件是：youth age，no working, no house, 信誉值credit为1
那么此类人会被分类到refuse一类中，即在相亲中被拒绝
每个example的特征值类型为：
['age', 'working', 'house', 'credit']
每个example的分类标签class_label取值范围为：'refuse'或者'agree'
'''
data_list = [['youth', 'no', 'no', '1', 'refuse'],
['youth', 'no', 'no', '2', 'refuse'],
['youth', 'yes', 'no', '2', 'agree'],
['youth', 'yes', 'yes', '1', 'agree'],
['youth', 'no', 'no', '1', 'refuse'],
['mid', 'no', 'no', '1', 'refuse'],
['mid', 'no', 'no', '2', 'refuse'],
['mid', 'yes', 'yes', '2', 'agree'],
['mid', 'no', 'yes', '3', 'agree'],
['mid', 'no', 'yes', '3', 'agree'],
['elder', 'no', 'yes', '3', 'agree'],
['elder', 'no', 'yes', '2', 'agree'],
['elder', 'yes', 'no', '2', 'agree'],
['elder', 'yes', 'no', '3', 'agree'],
['elder', 'no', 'no', '1', 'refuse']]
feat_type_list = ['age', 'working', 'house', 'credit']
return data_list, feat_type_list
class CSamplesTool(object):
'提供样本集的摘取目标数据的方法'
def __init__(self, data_list, feat_type_list):
'''
初始化函数
:param data_list:数据集
:param feat_type_list:数据的特征类型列表
:return 无
'''
'''
self.data_list 样例：
[['youth', 'no', 'no', '1', 'refuse'],
['youth', 'no', 'no', '2', 'refuse'],
……
]
'''
self.data_list = data_list
'''
self.feat_type_list 样例：
['age', 'working', 'house', 'credit']
'''
self.feat_type_list = feat_type_list
'''self.data_cnt 就是样本集中样本的总数'''
self.data_cnt = len(data_list)
'''self.feat_type_cnt 就是每个样本的特征值类型总数'''
self.feat_type_cnt = len(feat_type_list)
'''
self.feat_value_list 每种类型特征的取值列表, 样例:
[
['youth', 'youth', 'youth', 'youth', 'youth', 'mid', 'mid', 'mid', 'mid', 'mid', 'elder', 'elder', 'elder', 'elder', 'elder']
['no', 'no', 'yes', 'yes', 'no', 'no', 'no', 'yes', 'no', 'no', 'no', 'no', 'yes', 'yes', 'no']
['no', 'no', 'no', 'yes', 'no', 'no', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'no', 'no', 'no']
['1', '2', '2', '1', '1', '1', '2', '2', '3', '3', '3', '2', '2', '3', '1']
]
'''
self.feat_value_list = []
'''
self.class_value_list 样本集的分类标签取值列表，长度为样本总数，样例：
['refuse', 'refuse', 'agree', …… ,'agree', 'agree', 'refuse']
'''
self.class_value_list = []
'''
self.feat_dict 样本集的特征字典，样例：
{
house :{
condition_entropy : 0.5509775004326937
cnt : 15
info_gain : 0.4199730940219749
yes : {'cnt': 6, 'refuse': 0, 'shannon_entropy': 0.0, 'p_agree': 1.0, 'p_refuse': 0.0, 'p_house': 0.4, 'agree': 6}
no : {'cnt': 9, 'refuse': 6, 'shannon_entropy': 0.9182958340544896, 'p_agree': 0.3333333333333333, 'p_refuse': 0.6666666666666666, 'p_house': 0.6, 'agree': 3}
}
credit :{
condition_entropy : 0.6079610319175832
cnt : 15
3 : {'cnt': 4, 'refuse': 0, 'p_credit': 0.26666666666666666, 'shannon_entropy': 0.0, 'p_agree': 1.0, 'p_refuse': 0.0, 'agree': 4}
1 : {'cnt': 5, 'refuse': 4, 'p_credit': 0.3333333333333333, 'shannon_entropy': 0.7219280948873623, 'p_agree': 0.2, 'p_refuse': 0.8, 'agree': 1}
info_gain : 0.36298956253708536
2 : {'cnt': 6, 'refuse': 2, 'p_credit': 0.4, 'shannon_entropy': 0.9182958340544896, 'p_agree': 0.6666666666666666, 'p_refuse': 0.3333333333333333, 'agree': 4}
}
working :{
condition_entropy : 0.6473003963031123
cnt : 15
info_gain : 0.32365019815155627
yes : {'cnt': 5, 'refuse': 0, 'shannon_entropy': 0.0, 'p_working': 0.3333333333333333, 'p_agree': 1.0, 'p_refuse': 0.0, 'agree': 5}
no : {'cnt': 10, 'refuse': 6, 'shannon_entropy': 0.9709505944546686, 'p_working': 0.6666666666666666, 'p_agree': 0.4, 'p_refuse': 0.6, 'agree': 4}
}
age :{
condition_entropy : 0.8879430945988998
cnt : 15
info_gain : 0.08300749985576883
elder : {'cnt': 5, 'refuse': 1, 'p_age': 0.3333333333333333, 'shannon_entropy': 0.7219280948873623, 'p_agree': 0.8, 'p_refuse': 0.2, 'agree': 4}
youth : {'cnt': 5, 'refuse': 3, 'p_age': 0.3333333333333333, 'shannon_entropy': 0.9709505944546686, 'p_agree': 0.4, 'p_refuse': 0.6, 'agree': 2}
mid : {'cnt': 5, 'refuse': 2, 'p_age': 0.3333333333333333, 'shannon_entropy': 0.9709505944546686, 'p_agree': 0.6, 'p_refuse': 0.4, 'agree': 3}
}
}
'''
self.feat_dict = {}
'''
样本集的香农熵,H(Y={refuse, agree})
'''
self.samples_shanon_entropy = 1000
#计算
self.pickout_feat()
self.pickout_class()
self.pickout_samples_shannon_entropy()
self.pickout_feat_dict()
return
def shan_ent_ele(self, p):
if 0 == p:
return 0
else:
return -1 * p * math.log2(p)
def shannon_entropy(self, P):
func = np.frompyfunc(self.shan_ent_ele, 1, 1)
ent_ele_list = func(P)
entropy = ent_ele_list.sum()
return entropy
def get_data_cnt(self):
'''
样本总数
'''
return self.data_cnt
def get_feat_type_cnt(self):
'''
特征类型总数
'''
return self.feat_type_cnt
def get_feats(self):
'''
每种类型特征的特征值列表
'''
return self.feat_value_list
def get_classes(self):
'''
样本集的分类列表
'''
return self.class_value_list
def get_samples_shannon_entropy(self):
'''
样本集的香农熵，H(Y={refuse, agree})
'''
return self.samples_shanon_entropy
def get_feat_dict(self):
'''
特征分布以及概率分布
'''
return self.feat_dict
def pickout_feat(self):
'''
摘取每种类型特征的特征值
:return 无
'''
self.feat_value_list = []
for dim in range(self.feat_type_cnt):
curtype_feat = [example[dim] for example in self.data_list]
''' 这一句等效下面三句
curtype_feat = []
for i in range(self.data_cnt):
curtype_feat.append(self.data_list[i][dim])
'''
self.feat_value_list.append(curtype_feat)
return
def pickout_class(self):
'''
摘取分类列表，大小一定是m×1
'''
self.class_value_list = []
self.class_value_list = [example[-1] for example in self.data_list]
'''这一句等效下面两句
for i in range(self.data_cnt):
self.class_value_list.append(self.data_list[i][-1])
'''
def pickout_samples_shannon_entropy(self):
'''
计算样本集的香农熵，H(Y={refuse, agree})
'''
#统计样本集的分类标签分布
label_set = set(self.class_value_list)
label_cnt_list = []
for label in label_set:
label_cnt_list.append(self.class_value_list.count(label))
#统计样本集分类标签概率密度
n_samples = len(self.class_value_list)
label_prob_list = [label_cnt/n_samples for label_cnt in label_cnt_list]
#计算样本集的香农熵
self.samples_shanon_entropy = self.shannon_entropy(label_prob_list)
return
def pickout_feat_dict(self):
'''
摘取特征分布以及特征概率分布
'''
self.feat_dict = {}
class_label_set = set(self.class_value_list)
print(class_label_set)
for i in range(self.feat_type_cnt):
#依次加入特征类型字典:age:{}, house:{}, working:{}, credit:{}
feat_type = self.feat_type_list[i]
self.feat_dict[feat_type] = {}
#初始化feat_type时的条件熵， 即增加age:{'condition_entropy':0.0}
self.feat_dict[feat_type]['condition_entropy'] = 0.0
#初始化feat_type时的信息增益， 即增加age:{'inf_gain':0.0}
self.feat_dict[feat_type]['info_gain'] = 0.0
#填充feat_type的取值范围总数，如feat_type是age时，总数为3，可取值={youth, mid, elder}
self.feat_dict[feat_type]['cnt'] = len(self.feat_value_list[i])
#填充特征类型字典的key,例如age:{'youth':{}, 'mid:{}, 'elder':{}}
#为具体特征值的字典填充内容
#例如age:{elder:{填充此内容}} 填充为 age:{elder:{'cnt':5, 'p_age':5./15, 'refuse':4, 'agree':1, 'p_refuse':3./5, 'p_agree':2./5}}
#填充具体特征值的总样本数cnt
feat_value_set = set(self.feat_value_list[i])
for feat_value in feat_value_set:
#填充{'age':{'elder':{}}}其中的elder:{}
self.feat_dict[feat_type][feat_value] = {}
#填充'age':{'elder':{'cnt':5}}其中的'cnt':5
self.feat_dict[feat_type][feat_value]['cnt'] = self.feat_value_list[i].count(feat_value)
#填充'ag'e:{'elder':{'p_age':5./15}}其中的p_age:5./15
value_prob_key = 'p_' + str(feat_type)
self.feat_dict[feat_type][feat_value][value_prob_key] = self.feat_value_list[i].count(feat_value)*(1.0)/len(self.feat_value_list[i])
#填充'age':{'elder':{'refuse':4, 'agree':1}}其中的'refuse':4, 'agree':1,
for n in range(self.data_cnt):
for class_label in class_label_set:
if class_label not in self.feat_dict[feat_type][feat_value].keys():
self.feat_dict[feat_type][feat_value][class_label] = 0
if feat_value == self.feat_value_list[i][n] and class_label == self.class_value_list[n]:
self.feat_dict[feat_type][feat_value][class_label] += 1
#填充'age':{'elder':{'p_refuse':3./5, 'p_agree':2./5}}其中的'p_refuse':3./5, 'p_agree':2./5
self.feat_dict[feat_type][feat_value]['shannon_entropy'] = 0.0
for class_label in class_label_set:
prob_key = 'p_'+str(class_label)
class_label_cnt = self.feat_dict[feat_type][feat_value][class_label]
value_cnt = self.feat_dict[feat_type][feat_value]['cnt']
self.feat_dict[feat_type][feat_value][prob_key] = float(class_label_cnt) / value_cnt
#填充'age':{'elder':{'shannon_entropy':2.3}}其中的'shannon_entropy':2.3
prob = self.feat_dict[feat_type][feat_value][prob_key]
if 0 != prob:
self.feat_dict[feat_type][feat_value]['shannon_entropy'] += -1 * prob * math.log2(prob)
#填充feat_type时的条件熵， 即增加age:{'condition_entropy':1.0}中的'condition_entropy':1.0
feat_value_prob = self.feat_dict[feat_type][feat_value][value_prob_key]
feat_value_sEnt = self.feat_dict[feat_type][feat_value]['shannon_entropy']
self.feat_dict[feat_type]['condition_entropy'] += feat_value_prob * feat_value_sEnt
#填充feat_type时的信息增益，即计算age:{'info_gain':0.345}中的'info_gain':0.345
print('self.samples_shanon_entropy:',self.samples_shanon_entropy)
self.feat_dict[feat_type]['info_gain'] = self.samples_shanon_entropy - self.feat_dict[feat_type]['condition_entropy']
if __name__=='__main__':
#创建样本集
train_data_list, feat_type_list = create_samples()
#创建样本集工具类实例
samples = CSamplesTool(train_data_list, feat_type_list)
#创建通用工具类实例
tool = CUtileTool()
tool.dump(samples.get_feats(), 'feat_value_list')
tool.dump(samples.get_classes(), 'class_value_list')
tool.dump(samples.get_feat_dict(), 'feat_dict')
3.如何使用类输出的字典?
不懂字典结构的，需要学习下python中dict的语法，很容易的，类似Json的数据结构~
3.1从输出样本集的字典，可以很容易汇总信息增益
根据类输出的样本集的字典，很容易得到，每个特征的信息增益，如下所示：
样本集的香农熵baseEntropy: 0.9709505944546686 house: info_gain : 0.4199730940219749 credit: info_gain : 0.36298956253708536 working: info_gain : 0.32365019815155627 age: info_gain : 0.08300749985576883
3.2使用信息增益来找决策树的根节点
如果以此样例样本集为训练集，其决策树的根节点应该是，信息增益最大的特征。
通过样本集的字典可以知道，条件样本空间为house时，信息增益H(Y|X=house)=0.4199730940219749是最大的。
所以选取特征house为训练集的决策树的根节点~，此时的决策树最简洁有效。
note：如果这个代码搞定了，其实决策树的生成代码，差不多已经完成一半了。
enjoy it ~
(end)