本文实例讲述了Python决策树之基于信息增益的特征选择。分享给大家供大家参考,具体如下:
基于信息增益的特征选取是一种广泛使用在决策树(decision tree)分类算法中用到的特征选取。该特征选择的方法是通过计算每个特征值划分数据集获得信息增益,通过比较信息增益的大小选取合适的特征值。
一、定义
1.1 熵
信息的期望值,可理解为数据集的无序度,熵的值越大,表示数据越无序,公式如下:
其中H表示该数据集的熵值, pi表示类别i的概率, 若所有数据集只有一个类别,那么pi=1
,H=0
。因此H=0
为熵的最小值,表示该数据集完全有序。
1.2 信息增益
熵的减少或者是数据无序度的减少。
二、流程
1、计算原始数据的信息熵H1
2、选取一个特征,根据特征值对数据进行分类,再对每个类别分别计算信息熵,按比例求和,得出这种划分方式的信息熵H2
3、计算信息增益:
infoGain = H1 - H2
4、根据2,3计算所有特征属性对应的信息增益,保留信息增益较大的特征属性。
三、实例
海洋生物数据
被分类项\特征 | 不浮出水面是否可以生存 | 是否有脚蹼 | 属于鱼类 |
---|---|---|---|
1 | 是 | 是 | 是 |
2 | 是 | 是 | 是 |
3 | 是 | 否 | 否 |
4 | 否 | 是 | 否 |
5 | 否 | 是 | 否 |
3.1 原始数据信息熵
p(是鱼类) = p1 =0.4
p(非鱼类) = p2 =0.6
通过信息熵公式可得原始数据信息熵 H1 = 0.97095
3.2 根据特征分类计算信息熵
选择'不服出水面是否可以生存'作为分析的特征属性
可将数据集分为[1,2,3]与[4,5],分别占0.6和0.4。
[1,2,3]可计算该类数据信息熵为 h1=0.918295834054
[4,5] 可计算该类数据信息熵为 h2=0
计算划分后的信息熵 H2 = 0.6 * h1 + 0.4 * h2 = 0.550977500433
3.3 计算信息增益
infoGain_0 = H1-H2 = 0.419973094022
3.4 特征选择
同理可得对特征'是否有脚蹼'该特征计算信息增益 infoGain_1 = 0.170950594455
比较可得,'不服出水面是否可以生存'所得的信息增益更大,因此在该实例中,该特征是最好用于划分数据集的特征
四、代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
# -*- coding:utf-8 -*-
#! python2
import numpy as np
from math import log
data_feature_matrix = np.array([[ 1 , 1 ],
[ 1 , 1 ],
[ 1 , 0 ],
[ 0 , 1 ],
[ 0 , 1 ]]) # 特征矩阵
category = [ 'yes' , 'yes' , 'no' , 'no' , 'no' ] # 5个对象分别所属的类别
def calc_shannon_ent(category_list):
"""
:param category_list: 类别列表
:return: 该类别列表的熵值
"""
label_count = {} # 统计数据集中每个类别的个数
num = len (category_list) # 数据集个数
for i in range (num):
try :
label_count[category_list[i]] + = 1
except KeyError:
label_count[category_list[i]] = 1
shannon_ent = 0.
for k in label_count:
prob = float (label_count[k]) / num
shannon_ent - = prob * log(prob, 2 ) # 计算信息熵
return shannon_ent
def split_data(feature_matrix, category_list, feature_index, value):
"""
筛选出指定特征值所对应的类别列表
:param category_list: 类别列表
:param feature_matrix: 特征矩阵
:param feature_index: 指定特征索引
:param value: 指定特征属性的特征值
:return: 符合指定特征属性的特征值的类别列表
"""
# feature_matrix = np.array(feature_matrix)
ret_index = np.where(feature_matrix[:, feature_index] = = value)[ 0 ] # 获取符合指定特征值的索引
ret_category_list = [category_list[i] for i in ret_index] # 根据索引取得指定的所属类别,构建为列表
return ret_category_list
def choose_best_feature(feature_matrix, category_list):
"""
根据信息增益获取最优特征
:param feature_matrix: 特征矩阵
:param category_list: 类别列表
:return: 最优特征对应的索引
"""
feature_num = len (feature_matrix[ 0 ]) # 特征个数
data_num = len (category_list) # 数据集的个数
base_shannon_ent = calc_shannon_ent(category_list = category_list) # 原始数据的信息熵
best_info_gain = 0 # 最优信息增益
best_feature_index = - 1 # 最优特征对应的索引
for f in range (feature_num):
uni_value_list = set (feature_matrix[:, f]) # 该特征属性所包含的特征值
new_shannon_ent = 0.
for value in uni_value_list:
sub_cate_list = split_data(feature_matrix = feature_matrix, category_list = category_list, feature_index = f, value = value)
prob = float ( len (sub_cate_list)) / data_num
new_shannon_ent + = prob * calc_shannon_ent(sub_cate_list)
info_gain = base_shannon_ent - new_shannon_ent # 信息增益
print '初始信息熵为:' , base_shannon_ent, '按照特征%i分类后的信息熵为:' % f, new_shannon_ent, '信息增益为:' , info_gain
if info_gain > best_info_gain:
best_info_gain = info_gain
best_feature_index = f
return best_feature_index
if __name__ = = '__main__' :
best_feature = choose_best_feature(data_feature_matrix, category)
print '最好用于划分数据集的特征为:' , best_feature
|
运行结果:
初始信息熵为: 0.970950594455 按照特征0分类后的信息熵为: 0.550977500433 信息增益为: 0.419973094022
初始信息熵为: 0.970950594455 按照特征1分类后的信息熵为: 0.8 信息增益为: 0.170950594455
最好用于划分数据集的特征为: 0
希望本文所述对大家Python程序设计有所帮助。
原文链接:http://hareric.com/2016/05/19/%E5%86%B3%E7%AD%96%E6%A0%91%E4%B9%8B%E7%89%B9%E5%BE%81%E9%80%89%E6%8B%A9---%E4%BF%A1%E6%81%AF%E5%A2%9E%E7%9B%8A/