Data Mining 笔记Classification之决策树属性选择方法

一、概述

在decision tree的分类算法中提到了要从多个训练集的样本属性中选择一个属性作为测试条件,将记录划分为多个子集。如何从多个属性中选择一个属性呢。这就需要有一种指标来对属性在待划分的结果集上进行度量。

二、信息增益:Information Gain (ID3)

在信息增益中,重要性的衡量标准就是看特征能够为分类系统带来多少信息,带来的信息越多,该特征越重要。信息熵参照

数学之美系列四:怎样度量信息中的介绍:信息熵”(shāng) 是对信息的量化度量,一条信息的信息量大小和它的不确定性有直接的关系。

 

从信息论知识中我们知道,期望信息越小,信息增益越大,从而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择,选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。我们希望选择的是最有利于分类实例的属性,信息增益(Information Gain)是用来衡量给定的属性区分训练样例的能力,而ID3算法在增长树的每一步使用信息增益从候选属性中选择属性。

首先引用数据挖掘 – 分类算法比较中关于ID3的几个基本概念定义.

ID3 算法是由 Quinlan 首先提出的。该算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。

以下是一些信息论的基本概念:

定义 1:若存在 n 个相同概率的消息,则每个消息的概率 p 是 1/n,一个消息传递的信息量为 Log2(n)

定义 2:若有 n 个消息,其给定概率分布为 P=(p1,p2 … pn),则由该分布传递的信息量称为 P 的熵,记为

entropy-formula

意思就是一个变量可能的变化越多(反而跟变量具体的取值没有任何关系,只和值的种类多少以及发生概率有关),它携带的信息量就越大

定义 3:若一个记录集合 T 根据类别属性的值被分成互相独立的类 C1C2..Ck,则识别 T 的一个元素所属哪个类所需要的信息量为 Info (T) =I (p) ,其中 P 为 C1C2 … Ck 的概率分布,即 P= (|C1|/|T| … |Ck|/|T|)

定义 4:若我们先根据非类别属性 X 的值将 T 分成集合 T1,T2 … Tn,则确定 T 中一个元素类的信息量可通过确定 Ti 的加权平均值来得到,即 Info(Ti) 的加权平均值为:

Info(X, T) = (i=1 to n 求和 ) ((|Ti|/|T |) Info (Ti))

定义 5:信息增益度是两个信息量之间的差值,其中一个信息量是需确定 T 的一个元素的信息量,另一个信息量是在已得到的属性 X 的值后需确定的 T 一个元素的信息量,信息增益度公式为:

Gain(X, T) =Info (T)-Info(X, T)

引用特征选择方法之信息增益一文中关于信息增益的推导:

对分类系统来说,类别C是变量,它可能的取值是C1,C2,……,Cn,而每一个类别出现的概率是P(C1),P(C2),……,P(Cn),因此n就是类别的总数。此时分类系统的熵就可以表示为:

entropy-classification

分类系统的作用就是输出一个表示属于哪个类别的值,而这个值可能是C1,C2,……,Cn,因此这个值所携带的信息量就是上式中的这么多。

信息增益是针对一个一个的特征而言的,就是看一个特征t,系统有它和没它的时候信息量各是多少,两者的差值就是这个特征给系统带来的信息量,即增益。系统含有特征t的时候信息量很好计算,就是刚才的式子,它表示的是包含所有特征时系统的信息量。

问题是当系统不包含t时,信息量如何计算?我们换个角度想问题,把系统要做的事情想象成这样:说教室里有很多座位,学生们每次上课进来的时候可以随便坐,因而变化是很大的(无数种可能的座次情况);但是现在有一个座位,看黑板很清楚,听老师讲也很清楚,于是校长的小舅子的姐姐的女儿托关系(真辗转啊),把这个座位定下来了,每次只能给她坐,别人不行,此时情况怎样?对于座次的可能情况来说,我们很容易看出以下两种情况是等价的:(1)教室里没有这个座位;(2)教室里虽然有这个座位,但其他人不能坐(因为反正它也不能参与到变化中来,它是不变的)。

对应到我们的系统中,就是下面的等价:(1)系统不包含特征t;(2)系统虽然包含特征t,但是t已经固定了,不能变化。

我们计算分类系统不包含特征t的时候,就使用情况(2)来代替,就是计算当一个特征t不能变化时,系统的信息量是多少。这个信息量其实也有专门的名称,就叫做“条件熵”,条件嘛,自然就是指“t已经固定“这个条件。

但是问题接踵而至,例如一个特征X,它可能的取值有n多种(x1,x2,……,xn),当计算条件熵而需要把它固定的时候,要把它固定在哪一个值上呢?答案是每一种可能都要固定一下,计算n个值,然后取均值才是条件熵。而取均值也不是简单的加一加然后除以n,而是要用每个值出现的概率来算平均(简单理解,就是一个值出现的可能性比较大,固定在它上面时算出来的信息量占的比重就要多一些)。

因此有这样两个条件熵的表达式:

condition-entropy

这是指特征X被固定为值xi时的条件熵,

condition-entropy2

这是指特征X被固定时的条件熵,注意与上式在意义上的区别。从刚才计算均值的讨论可以看出来,第二个式子与第一个式子的关系就是:

condition-entropy3

具体到我们文本分类系统中的特征t,t有几个可能的值呢?注意t是指一个固定的特征,比如他就是指关键词“经济”或者“体育”,当我们说特征“经济”可能的取值时,实际上只有两个,“经济”要么出现,要么不出现。一般的,t的取值只有t(代表t出现)和condition-entropy4(代表t不出现),注意系统包含t但t 不出现与系统根本不包含t可是两回事。

因此固定t时系统的条件熵就有了,为了区别t出现时的符号与特征t本身的符号,我们用T代表特征,而用t代表T出现,那么:

condition-entropy5

与刚才的式子对照一下,含义很清楚对吧,P(t)就是T出现的概率,condition-entropy-p就是T不出现的概率。这个式子可以进一步展开,其中的

condition-entropy7

另一半就可以展开为:

condition-entropy8

因此特征T给系统带来的信息增益就可以写成系统原本的熵与固定特征T后的条件熵之差:

condition-entropy9

公式中的东西看上去很多,其实也都很好计算。比如P(Ci),表示类别Ci出现的概率,其实只要用1除以类别总数就得到了(这是说你平等的看待每个类别而忽略它们的大小时这样算,如果考虑了大小就要把大小的影响加进去)。再比如P(t),就是特征T出现的概率,只要用出现过T的文档数除以总文档数就可以了,再比如P(Ci|t)表示出现T的时候,类别Ci出现的概率,只要用出现了T并且属于类别Ci的文档数除以出现了T的文档数就可以了。

从以上讨论中可以看出,信息增益也是考虑了特征出现和不出现两种情况,与开方检验一样,是比较全面的,因而效果不错。但信息增益最大的问题还在于它只能考察特征对整个系统的贡献,而不能具体到某个类别上,这就使得它只适合用来做所谓“全局”的特征选择(指所有的类都使用相同的特征集合),而无法做“本地”的特征选择(每个类别有自己的特征集合,因为有的词,对这个类别很有区分度,对另一个类别则无足轻重)。

公式定义:

选择有最高的Information Gain的属性。

pi:

pi 是集合D中属于分类Ci的概率,用|Ci, D|/|D|来估计。

分类所需的期望信息Expected information (entropy):

原始数据分类所需的期望信息Expected information (entropy):

info(D)

按照属性分A类所需的期望信息:

infoA(D)

信息增益:按照属性A分支后获得的信息增益。

info_gain

示例:

id 年龄 收入 学生 信用 购买
1
2
3
4
5
6
7
8
9
10
11
12
13
14

两个目标分类:

  • Class P: 购买电脑= “yes”
  • Class N:?购买电脑 = “no”
age pi ni I(pi, ni) formula
青年 2 3 0.971 -2/5*LOG2(2/5) -3/5*LOG2(3/5) = 0.971
中年 4 0 0 -4/4*LOG2(4/4) -0/4*LOG2(0/4) = 0
老年 3 2 0.971 -3/5*LOG2(3/5) -2/5*LOG2(2/5) = 0.971

原始数据分类所需的期望。? info(D)-example 因为训练集中14个样本,9个是Class P,5个是Class N

按照属性分age类所需的期望信息infoA(D)-age-example其中,5/14表示按照青年占的比重,I(2,3)表示青年中2个Class P,3个Class N的样本:

按照属性age分支后获得的信息增益:info_gain-age

同样的,选择其他几个属性来计算信息增益分别为:

infoA(D)-othters-example

比较够选择增益最大的age属性来建立建立分支分裂节点。

?二、信息增益:Gain Ratio for Attribute Selection (C4.5)

和ID3基本相同,只是采用比率来对ID3的指标进行normalize。优先选择比率最高属性。

公式:

infor-normalize

? GainRatio(A) = Gain(A)/SplitInfo(A)

如考虑收入属性:

infor-normalize-example-age

训练集的14个样本中4个是低收入,4个高,6个中等。

我的注解:这个时候不用考虑多少记录属于哪个目标分类。只是考察该属性在整个集合的分布情况。

gain_ratio(income) = 0.029/1.557 = 0.019

C4.5 算法一种分类决策树算法 , 其核心算法是 ID3 算法。C4.5 算法继承了 ID3 算法的优点,并在以下几方面对 ID3 算法进行了改进:

  1. 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
  2. 在树构造过程中进行剪枝;
  3. 能够完成对连续属性的离散化处理;
  4. 能够对不完整数据进行处理。

C4.5 算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。

四、Gini Index (CART, IBM IntelligentMiner)

选择最大的

公式:

  • gini(D)?? pj表示是目标分类在集合中出现的概率。
  • giniA(D)A将训练集分成两部分,D1和D2,对着两部分分布计算gini,然后结合其在总记录数中的比重,合计出该属性分隔记录后得到的gini index。
  • gini(A)

选择最小的ginisplit(D)或者最大的?gini(A)的属性来分支节点。

示例

  • gini(D)-example???????????????????????????? 总共14个样本中9个落入Class P,5个落入Class N
  • gini-income-(D)-example按照收入分隔,10个是属于D1,收入下和中,4个属于D2高。在D1的10个样本中7个是ClassP, 3个是Class N;在D2的4个样本中2个是ClassP, 2 个是ClassN。

Gini{low,high} = 0.458;

Gini{medium,high}= 0.450.

所以选择{low,medium} (and {high})来分裂数据,因为比较其他两种分裂具有最小的gini index。

五、三种指标比较

Information gain:

  • biased towards multivalued attributes

Gain ratio:

  • tends to prefer unbalanced splits in which one partition is much smaller than the others

Gini index:

  • biased to multivalued attributes
  • has difficulty when # of classes is large
  • tends to favor tests that result in equal-sized partitions and purity in both partitions

五、其他指标

  • CHAID: a popular decision tree algorithm, measure based on χ2 test for independence
  • C-SEP: performs better than info. gain and gini index in certain cases
  • G-statistic: has a close approximation to χ2 distribution
  • MDL (Minimal Description Length) principle (i.e., the simplest solution is preferred):
??????????????????? The best tree as the one that requires the fewest # of bits to both (1) encode the tree, and (2) encode the exceptions to the tree
  • Multivariate splits (partition based on multiple variable combinations)
??????????????????? CART: finds multivariate splits based on a linear comb. of attrs.
???????? Which attribute selection measure is the best? ? Most give good results, none is significantly superior than others

详细参照:

[slideonline id=9269]

原创文章。为了维护文章的版本一致、最新、可追溯,转载请注明: 转载自idouba

本文链接地址: Data Mining 笔记Classification之决策树属性选择方法


, , ,

Trackbacks/Pingbacks

  1. Data Mining 笔记&实践 | 学而时习之 - 2016年4月6日

    […] Data Mining 笔记Classification之决策树属性选择方法 […]

发表评论