机器学习算法13——决策树2

浏览: 1147

特征选择

特征选择的目的是为了筛选出对训练数据具有分类能力的特征,提供决策树学习的效率。通常特征选择的准则是信息增益信息增益率(信息增益比)

entropy

在信息论和概率统计中,熵entropy表示的是随机变量不确定性的度量,即不纯度。设X是一个取有值的随机离散变量,其概率分布为:P(X=x_i)=p_i, i=1,2,...,n则随机变量X的熵定义为H(X)=-\sum_{i=1}^{n}p_ilogp_i;若果p_i=0,则定义0log0=0.。上式中的对数以2或者自然数e为底数,此时熵的单位是比特(bit)或者纳特(nat)。根据上式得知:熵和X的取值没有关系,值依赖于其分布,将X的熵记作H(p),即:H(p)=-\sum_{i=1}^{n}p_ilogp_i熵越大,随机变量的不确定就越大,根据定义得到:0\leq H(p) \leq log(n)

当随机变量只取0和1的时候,X的分布是P(X=1)=p, P(X=0)=1-p, 0 \leq p \leq 1,那么对应的熵H(p)H(p)=-plog_2p-(1-p)log_2(1-p)

  • p=0或1时,H(p)=0,此时随机变量完全没有不确定性。
  • p=0.5时,熵取值最大,此时不确定最大

image.png

条件熵

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。此时,条件熵H(Y|X),定义为X给定条件下Y的条件概率分布的熵对X的期望:H(Y|X)= \sum _{x=1}^{n}p_iH(Y|X=x_i)在这里,p_i=P(X=x_i), i=1,2,3,...,n

规定:由数据统计(特别是极大似然估计)得到的熵和条件熵,分别称之为经验熵empirical entropy 和经验条件熵 empirical conditional entropy,并且规定0log0=0。

信息增益 information gain

信息增益表示的是:得知X的信息而是的类Y的信息的不确定性较少的程度。信息增益定义如下:

特征A对训练数据集D的信息增益为g(D,A),定义为集合D的经验熵H(D)与给定条件下D的经验熵H(D|A)之差,记为g(D,A)= H(D)-H(D|A)一般情况下,熵和条件熵的差称之为互信息mutual information。决策树模型中学习的信息增益 == 训练数据中类与特征的互信息。

  • 决策树学习应用信息增益来选择特征
  • 信息增益就是表示由于特征使得对训练数据集的分类的不确定减少的程度
  • 信息增益依赖于特征,不同的特征往往具有不同的信息增益
  • 信息增益大的特征具有更强的分类能力
  • 根据信息增益来选择特征的方法:
    • 对于训练数据集,计算每个特征的信息增益
    • 比较每个信息增益的大小
    • 选取信息增益最大的特征进行分类

信息增益算法

假设训练数据集为D,|D|表示样容量即本数。数据集中总共有K个类C_k, k=1,2,3,...,K,|C_K|为样本C_k的个数,则\sum _{k=1}^{K}|C_k|=|D|设特征A有n个不同的取值:\{a_1,a_2,...a_n\},根据特征A将数据集D分成n个不同的子集D_1, D_2, ...,D_n,其中|D_i|表示D_i的样本数,\sum _{i=1}^{n}|D_i| =|D|。记子集D_i中属于类C_k的样本的集合为D_ik,即:D_{ik}=D_i \cap C_k|D_{ik}|D_{ik}的样本个数。

  • 训练数据集:D
  • 样本容量:|D|
  • 数据中类的总数:K个类,C_k, 其中k=1,2,3,...,K
  • 所有类Y的总数满足:\sum _{k=1}^{K}|C_k|=|D|
  • 训练数据总特征X数:n,\{a_1,a_2,...a_n\}
  • 根据某个类A将数据集D划分为n个不同的子集:D_1, D_2, ...,D_n
  • 所有子集之和满足:D_{ik}=D_i \cap C_k
推荐 0
本文由 皮大大 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册