《非度量方法课件》由会员分享，可在线阅读，更多相关《非度量方法课件（26页珍藏版）》请在金锄头文库上搜索。
1、模式识别非度量方法,mqy_,在模式识别中，每个样例都是用特征向量来表示。 前面介绍的算法，基本都涉及到了特征向量之间距离的度量。比如最近邻算法、神经网络，都是输入越相似，输出也越相似。这要求特征是能够度量不同取值之间的相似程度的，比如身高。 在模式识别中，有一些问题中样例的某些特征是无法度量不同特征值之间的相似程度的，比如：使用血型作为一个特征来判断一个人是否容易感染某种疾病，不同血型只是不同的标签，没有明显的概念能表示不同血型之间的相似度。,一 简单的决策树例子,这个决策树是通过归纳的方法建立的，它与上面那些样例是相符合的。它有推理能力，能够推理更多没见过的样例。虽然有些可能是错的。 每个
2、节点是一个特征(条件)。 每一个分支对应了这个特征的一个取值。 每个分支(节点)有一个对应的样例(规则)集合。比如天空节点是总分支对应了所有的规则，需要对所有的样例进行处理；晴分支对应了天空是晴的时候的所有规则，需要对所有天空是晴的样例进行处理。,二 决策树学习算法,这样的决策树是怎么形成的呢？思想：从树根递归：对于当前节点，选择一个特征放到节点上。列出它的所有值，作为分支。对于每个分支，看它是不是对应的所有样例集合都是正例或反例，如果是就标注出来，结束这个分支；如果不是，在这个分支上放一个节点，递归按照上面的过程进行处理。 具体算法如下： 1)令当前分支指向根节点。 2)选择一个未用的特征作
3、为当前分支指向的下一个节点。 3)根据选定特征的每个可能的取值生成一个分支，循环对每个分支如下处理： 如果这个分支对应的样例集合都为正或者都为反，标记正反。 否则对当前分支执行2。,这个算法有一个问题没有解决：选择一个特征作为当前分支指向的下一个节点。 比如如果不让天空作为根节点，这个树的形状变成：,选择原则：我们知道一个节点(分支)对应了一个样例集合。这里希望选取最有利于分类当前样例集合的特征。每一步都选取最有利于分类当前样例集合的特征，将会提高使用决策树进行推导的效率。那么怎么才能确定哪个特征对样例具有最强的分类能力呢？这就涉及到信息增益的概念。,三 信息增益(information ga
4、in) 1. 熵(entropy),1850年，德国物理学家鲁道夫克劳修斯首次提出熵的概念，用来表示任何一种能量在空间中分布的均匀程度，能量分布得越均匀，熵就越大。一个体系的能量完全均匀分布时，这个系统的熵就达到最大值。 一个封闭容器中中间有一个隔板，比如左边的能量很高(很热)，右边的能量很低。这个时候对于整个容器而言，能量分布最不均匀，最有序，熵最小。隔板拿掉以后，能量密度由高流向低达逐渐到平衡，稳定后最无序，熵最大。 可以说有序化和熵是成反比关系的。系统越有序，熵越低；系统越无序，熵越高。,下面看看怎么把熵的概念推广到样例集。 设样例集中正例的比率为p+，反例的比率为p-。那么，这个样例集
5、S的熵：,在有关熵的计算中，定义0log0=0。 举例。比如一个样例集合中有14个样例，其中9个正例，5个反例。那么这个样例集的熵：,如果这个样例集中14个正例。那么它的熵：,可以画出p+在0-1的范围内变化时样例集的熵的变化曲线：,更一般的，如果目标有c个取值，那么此时S的熵计算如下：,此时熵的最大可能值是log2c。,2. 期望熵,选择特征的基本思想：一个特征可以把样例集划分成几部分。每一部分的熵可以求出来。那么这些部分的平均熵也可以求出来。平均熵愈大，说明样例越无序。因此上面对一个特征计算出的平均熵越小，说明这个特征对分类越有利。那么就对每一个特征都计算出适用它划分样例集之后的平均熵，使
6、用平均熵最小的特征作为当前节点的特征。 其实计算平均熵不只是简单的平均，而是加权平均。使用样例集的大小作为权值。这样计算出的不叫平均熵，而叫期望熵。这与数学期望的概念是类似的。离散型随机变量的一切可能的取值xi与对应的概率P(xi)之积的和称为的数学期望，其含义实际上是随机变量的加权平均，概率是权。比如没带笔的同学1/10，带1只笔的同学有6/10，带2只笔的同学有3/10，平均带几只笔。,3. 信息增益,下面计算一个特征A的信息增益。 在决策树里，通常不直接使用期望熵来选取特征，而是引入另外一个概念：信息增益。一个特征划分集合之后可以计算出期望熵，用这个特征划分之前的集合也有一个熵，信息增益
7、就是划分之前的熵减去划分之后的期望熵。具体而言，特征A的信息增益计算如下：,一个特征A可能取几个值，那么任一个值v对应的子集标记为Sv。 换句话说：一个特征的信息增益就是由于这个特征分割样例后导致的期望熵降低。,在决策树学习算法中：可以对所有剩余特征计算出信息增益，使用最大的信息增益的特征作为分支的下一个节点。为什么？一个特征的信息增益越高，说明使用该特征导致样例集降低的熵越多，说明样例集会越有序。决策树从上到下决策就是使样例越来越有序的过程。,4. 举例：,因为湿度的信息增益最大，所以使用湿度作为决策树的根节点。 下面看湿度的第一个分支：高。剩下的样例有：,因为这个分支的所有样例结构都是否，
8、所以就将这个分支标记为否，然后继续处理湿度的下一个分支：正常。剩下的样例有：,因为天空的信息增益最大，所以使用天空作为这个节点的特征。天空的前两个分支的所有样例结构都是是，所以就将这两个分支标记为是。将风力最为最后一个分支指向的节点。最后生成的决策树如下：,5. 信息增益的问题,前面介绍的决策树有很多需要完善的地方。比如其中有一个问题，就是信息增益偏袒具有较多值的特征。举一个极端的例子，日期可能有大量的值，每个值只对应一个样例。那么此时日期的信息增益就是：,可见，日期具有最大的信息增益。,解决这个问题的一个办法是使用信息增益比率代替信息增益。信息增益比率通过引入分类信息来惩罚类似日期的特征。,在彻底分裂为n个样例时SplitInformation=log2n 信息增益比率计算如下：,在建立决策树过程中让其生长的太“枝繁叶茂”是没有必要的，这样使决策树本身对历史数据的依赖性增大，训练过度。为了使得到的决策树所蕴含的规则具有普遍意义，必须防止训练过度，同时也减少了训练的时间。因此需要有一种方法能让我们在适当的时候停止树的生长。常用的方法是设定决策树的最大高度（层数）来限制树的生长。还有一种方法是设定每个节点必须包含的最少记录数，当节点中记录的个数小于这个数值时就停止分割。,
