CWYAlpha

Just another WordPress.com site

Thought this was cool: 信息增益(IG,Information Gain)的理解和计算

leave a comment »


可能理解的不对。

决策树构建中节点的选择靠的就是信息增益了。

信息增益是一种有效的特征选择方法,理解起来很简单:增益嘛,肯定是有无这个特征对分类问题的影响的大小,这个特征存在的话,会对分类系统带来多少信息量,缺了他行不行?

既然是个增益,就是个差了,减法计算一下,谁减去谁呢?

这里就用到了信息熵的概念,放到分类系统里面,信息熵如何计算呢?

分类系统里面无非是样本xi以及样本的分类结果yi,假设这个分类系统有k类,那么作为训练集来说,分类情况基本就定了,是按照样本的各个特征定的。那么在这些样本的信息的前提下,分类器有个结果,就自然包含了一种信息量在里面,可以用信息熵E(S)计算出来。

当然大家都知道熵表达的是不确定度,分布约均匀,越不确定,熵越大。

那么当把特征f引入的时候,会不会对系统的信息量有所影响呢?也就引入f之后的系统不确定度E(S|f)是多少呢?其实是个条件熵。也就是加入条件f之后,不确定度减少了多少?信息熵的有效减少量是多少?

为了计算条件熵,我们可以固定f的值,也就是根据f在训练集中呈现的值,计算条件熵E(S|f)。简单的说就是,把根据f划分的各个小系统的信息熵加权求和,权重就是各个小系统占系统S的比例(假设f有两个值0、1,选0的时候有a个样本,样本当然有类别y;f是1的时候有b个样本;a+b=n(样本总数);那么权重就是a/n和b/n了;每个小系统的信息当然跟大系统求法一样了)。

那么增益IG(f)=E(S)-E(S|f).

选择  f*=argmax(IG(f))的f作为第一个根节点,然后递归下去吧。

Traditionally, decision trees have been created manually.

您可能也喜欢:


MaxEnt: 最大熵模型(Maximum Entropy Models)(一)


通过WSDM2011论文录用情况分析目前信息检索趋势


2010信息检索数据挖掘机器学习相关国际会议


数据集-用于数据挖掘、信息检索、知识发现等


计算广告学(Computational Advertising)CA

无觅

相关文章

from 丕子: http://www.zhizhihu.com/html/y2012/4066.html

Written by cwyalpha

十一月 13, 2012 在 3:09 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: