分类 IRLAB

大纲 自然语言中的重要技术 决策树 最大熵模型 K近邻

自然语言中的分类问题

分类的一般过程 训练集 数学模型 训练过程 测试集 评价 精确率，宏平均，微平均

本课介绍的几种方法 决策树 最大熵模型 K近邻

决策树 简介 决策树表示法 决策树学习的适用问题 基本的决策树学习算法 决策树学习中的假想空间搜索 决策树学习的常见问题

简介 决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant。 是应用最广的归纳推理算法之一 一种逼近离散值目标函数的方法 对噪声数据有很好的健壮性且能学习析取表达式

决策树的表示法 决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值

图

表达式

决策树学习的适用问题 实例是由属性-值对表示的 目标函数具有离散的输出值 可能需要析取的描述 训练数据可以包含错误 训练数据可以包含缺少属性值的实例

属性选择 构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。

用熵度量样例的均一性（纯度） 熵的定义 举例

用信息增益度量期望熵最低

举例

ID3算法 创建树的Root结点 如果Examples都为正，那么返回label=+中的单结点Root 如果Examples都为反，那么返回lable=-单结点树Root 如果Attributes为空，那么返回单节点树Root，lable=Examples中最普遍的目标属性值 否则开始 AAttributes中分类能力最好的属性 Root的决策属性A 对于每个可能值 在Root下加一个新的分支对应测试A=vi 令Example-vi为Examples中满足A属性值为vi的子集 如果Examples-vi为空 在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的 目标属性值 否则在这个新分支下加一个子树ID3(example-vi,target- attribute,attributes-|A| 结束 返回 Root

C4.5 C4.5是对ID3的改进算法 对连续值的处理 对未知特征值的处理 对决策树进行剪枝 规则的派生

决策树学习中的假设空间搜索 假设空间 ID3算法中的假设空间包含所有的决策树 当遍历决策树空间时，ID3仅维护单一的当前假设。

决策树学习的常见问题(1) 避免过度拟合数据 基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练例子拟合。有噪声情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很好的预测性能。

解决方法 剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。 向前剪枝（forward pruning） 向后剪枝（backward pruning） 理论上讲，向后剪枝好于向前剪枝，但计算复杂度大。剪枝过程中一般要涉及一些统计参数或阈值，如停机阈值；有人提出了一种和统计参数无关的基于最小描述长（MDL）的有效剪枝法

决策树学习的常见问题（2） 合并连续值属性 属性选择的其他度量标准 信息增益比（gain ratio）、Gini-index、距离度量（distance measure）等。不同的度量有不同的效果，特别是对于多值属性。

决策树学习的常见问题（3） 处理缺少属性值的训练样例 处理不同代价的属性

决策树的优点 可以生成可以理解的规则； 计算量相对来说不是很大； 可以处理连续和离散字段； 决策树可以清晰的显示哪些字段比较重要

不足之处 对连续性的字段比较难预测 当类别太多时，错误可能会增加的比较快 一般的算法分类的时候，只是根据一个属性来分类。 不是全局最优。

举例：利用决策树进行文本分类

最大熵模型 熵定量的描述事物的不确定性 设随机变量 ，它有A1，A2，…，An共n个可能的结局，每个结局出现的机率分别为p1,p2 ，...，pn，则 的不确定程度，即信息熵为: 熵越大，越不确定 熵等于0，变量是确定的

最大熵思想 最大熵思想由来已久，Occam在他著名的Occam剃刀理论中即体现了这种思想，对最大熵理论的系统论述出现在上世纪50年代中期，由E.T. Jaynes提出，其原理的基本思想是：我们从全部相容的分布预测中挑选这样的预测，它是在某些约束条件下（通常是给定的某些随机变量的分布）使信息熵达到极大值。这是因为信息熵取得极大值时对应的一组概率分布出现的概率占绝对优势。

在自然语言中的应用 S.Pietra、V.Pietra等人提出了一种基于最大熵原理的单词聚类方法，首次将最大熵理论应用于自然语言处理。 A.L.Berger、S.Pietra、V.Pietra等人比较详细地介绍了最大熵的理论框架，并介绍了其在基于统计的机器翻译领域的一些应用。 S.Abney在统计属性--值文法(Attribute-value Grammars)中使用最大熵进行参数估计。 李涓子、黄昌宁改进了最大熵的特征选择策略，并将其应用于汉语的词义消歧，取得了较好的效果 A.Borthwick研究了基于最大熵的名实体(Named Entity)的识别

最大熵模型 已知训练样本集(x1,y1),(x2,y2),…,(xN,yN),其中x为输入，y为输出 指x出现的情况下，y的经验概率，也就是y在样本集中的概率。 指x出现的情况下，y的实际概率。 随机事件的不确定性可以用条件熵来衡量： 特征指x与y之间存在的某种特定关系，可以用一个输出为0或1的特征函数表示。

最大熵模型 特征的经验概率为所有满足特征要求的(x,y)的验概率之和,即： 特征的期望概率,也就是特征在我们所学习的随机事件中的真实分布为：

最大熵模型 选定的特征的重要性可通过下式体现： 上 式表示，特征f的经验概率与期望概率一致，当样本足够多时，可信度高的特征的经验概率与期望概率是一致的

约束集 根据随机事件的情况，约束等式可以有多组，约束等式的集合叫约束集，可表示为

最大熵模型 最大熵模型，是满足约束集条件的所有模型中熵最大的模型，即： 其中p为满足约束集C条件的某一统计模型。 因为约束集中的每一个特征的分布是最大似然估计，所以约束集中元素越多，统计模型从训练样本中学得的越多，其做出的预测也越依赖于样本集。选择特征较多时，满足约束集要求的统计模型个数较少，当把样本中的所有(x,y)都作为特征时，模型唯一，为用极大似然估计求p(y|x)所建立的模型。

最大熵模型求解 最大熵模型求解问题，实质是一个约束条件下求极值的问题。此类问题通常用拉格朗日乘子法确定。 其中：

求导后变换得 其中 最大值可通过求

没有解析解，Danroch 和Rateliff于1972年提出了一个称为GIS(Generalized Iterative Scaling Algorithm)算法[133]。D.Pietra等改进了原有的最大熵模型求解算法，降低了求解算法的约束条件，提出了IIS(Improved Iterative Scaling Algorithm)算法，增加了算法的适用性，IIS算法是目前最大熵参数求解中的常用算法。

IIS算法 IIS算法如下： 输入：约束集， x，y的经验概率分布 输出： 1、 初始令， 2、 for i=1 to n 循环 1、            初始令， 2、            for i=1 to n 循环 a)        令 为下面方程的解 其中， 由(3-3)对f的定义可知在本文中为某一实例(x,y)包含的特征数量。 b)        c)        重复 a)至 收敛 3、            算法结束

这里求解使用牛顿迭代法

迭代算法 1 初始令 i=0, ai=0 2 3   当 , i++, 循环至2， 4   算法结束, 为方程解， = 。

最大熵统计模型的优点 最大熵统计模型获得的是所有满足约束条件的模型中信息熵极大的模型。 其次最大熵统计模型可以灵活地设置约束条件。通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度。 另外最大熵模型还自然地解决了统计模型中参数平滑的问题。

K近邻（KNN） 最近邻分类规则 最近邻规则的一个推广- KNN 没有好的相似度矩阵不能用 KNN 对于测试样本点x，在集合中距离它最近的的x1。最近邻分类就是把x分为x1 所属的类别 最近邻规则的一个推广- KNN 没有好的相似度矩阵不能用 KNN

方法 目标：基于训练集N的对y分类 确定在N中与y最相似的元素x 得到k个最相似的集合 设n1,n2分别为集合中属于c1,c2的个数 如果p(c1|y)>p(c2|y),判为c1,否则判为c2

特点 其性能依赖于相似度矩阵 效率问题

Thanks!