1、第12讲 文本分类及朴素贝叶斯分类器Text Classification&Nave Bayes12019/08提纲2 上一讲回顾 文本分类朴素贝叶斯朴素贝叶斯理论文本分类评价提纲3 上一讲回顾 文本分类朴素贝叶斯 朴素贝叶斯理论文本分类评价统计语言建模IR模型(SLMIR)马萨诸塞大学(University of Massachusetts,UMass)大学Ponte、Croft等人于1998年提出。随后又发展了出了一系列基于SLM的模型。代表系统Lemur。查询似然模型查询似然模型：把相关度看成是每篇文档对应的语言下生成该查询的可能性 翻译模型翻译模型：假设查询经过某个噪声信道变形成某篇文
2、章，则由文档还原成该查询的概率(翻译模型)可以视为相关度 KL距离模型距离模型：查询对应某种语言，每篇文档对应某种语言，查询语言和文档语言的KL距离作为相关度度量 本讲义主要介绍查询似然模型4查询似然模型QLM QLM计算公式 于是检索问题转化为估计文档D的一元语言模型MD，也即求所有词项 w的概率P(w|MD)QwQwcDDmDDDmDMwPMqPMqPMqPMqqqPMQPDQPDQRSV),(2121)|()|().|()|()|.()|()|(),(QLM求解步骤 第一步：根据文档D(样本)，估计文档模型MD(总体)，在一元模型下，即计算所有词项 w的概率P(w|MD)第二步：计算在模
3、型MD下生成查询Q的似然(即概率)第三步：按照得分对所有文档排序6几种QLM中常用的平滑方法 Jelinek-Mercer(JM)，01，文档模型和文档集模型的混合 课堂提问，对于wD，折扣后的PDML(w|D)是不是一定小于PML(w|D)？Dirichlet Priors(Dir)，0，DIR和JM可以互相转化 Absolute Discounting(Abs)，01，|D|u表示D中不相同的词个数(u=unique)7基于翻译模型的IR模型)|()|()|()|(DijjjiiiMwPwqPDqPDQP8 基本的QLM模型不能解决词语失配(word mismatch)问题，即查询中的用词
4、和文档中的用词不一致，如：电脑 vs.计算机 假设Q通过一个有噪声的香农信道变成D，从D估计原始的Q 翻译概率P(qi|wj)在计算时可以将词项之间的关系融入。基于词典来计算(人工或者自动构造的同义词/近义词/翻译词典)基于语料库来计算(标题、摘要 vs.文本；文档锚文本 vs.文档)翻译概率生成概率KL距离(相对熵)模型(|)(|)*log(|)(|)(|)(|)*log(|)*log(|)(|)(,)(,)(,)(|)*log(|)(|)*log(|)(|)*logiiiiiiDiQqQiCiDiCiQiQqQqQiQiQQDQCQDiQiDiQiQqQqQiQP qMP qMP qMP
5、qMP qMP qMP qMP qMP qMKL MMKL MMKL MMP qMP qMP qMP qMP qMP (|)iiDqQqM9QqCiDiiiMqPMqPQqtfDQScore)|()|(log*),(),(QqQqtfiQqiCQqQqtfiQqiDiiiiiiCqPQqtfQMQPDqPQqtfQMQP),(),()|()!,(|!|)|()|()!,(|!|)|()|()|(log),(CDMQPMQPDQScore对同一Q，为常数负的交叉熵多项分布10本讲内容本讲内容 文本分类的概念及其与IR的关系 朴素贝叶斯分类器(朴素贝叶斯)文本分类的评价10提纲11上一讲回顾 文本
6、分类朴素贝叶斯朴素贝叶斯理论文本分类评价什么是分类？简单地说，分类(Categorization or Classification)就是按照某种标准给对象贴标签(label)12男女为什么要分类？人类社会的固有现象：物以类聚、人以群分 相似的对象往往聚集在一起(相对而言)不相似的对象往往分开 方便处理！13分类非常普遍 性别、籍贯、民族、学历、年龄等等，我们每个人身上贴满了“标签”我们从孩提开始就具有分类能力：爸爸、妈妈；好阿姨、坏阿姨；电影中的好人、坏人等等。分类无处不在，从现在开始，我们可以以分类的眼光看世界14课堂思考题 从如下叙述中找出“标签”经常加班，0点以前基本不睡觉，大多没有女
7、朋友，肚子大，爱生病，爱用谷歌，不用百度，必备双肩包15课堂思考题 从如下叙述中找出“标签”经常加班，0点以前基本不睡觉，大多没有女朋友，肚子大，爱生病，爱用谷歌，不爱用百度，必备双肩包16课堂思考题 从如下叙述中找出“标签”经常加班，0点以前基本不睡觉，大多没有女朋友，爱宅着，爱用谷歌，不爱用百度，必备双肩包 =程序员17加班，熬夜，单身，宅，用谷歌，双肩包分类是有监督机器学习的一种机器学习机器学习(Machine Learning)Supervised Learning Unsupervised Learning Semi-supervised Learning18文本分类 文本分类(Te
8、xt classification或者 Text Categorization)：给定分类体系(还有训练语料)，将一篇文本分到其中一个或者多个类别中的过程。分类体系：随应用不同而不同。比如：垃圾 vs.非垃圾、体育/经济/军事 等等 文本分类的类型：按类别数目：binary vs.multi-class：二类问题 vs.多类问题 按每篇文档赋予的标签数目：single label vs.multi label：单标签 vs.多标签问题1920一个文本分类任务：垃圾邮件过滤20From:Subject:real estate is the only way.gem oalvgkayAnyone
9、can buy real estate with no money downStop paying rent TODAY!There is no need to spend hundreds or even thousands for similar coursesI am 22 years old and I have already purchased 6 properties using themethods outlined in this truly INCREDIBLE ebook.Change your life NOW!=Click Below to order:*=如何编程实
10、现对上类信息的识别和过滤？21文本分类的形式化定义：训练21给定:文档空间X 文档都在该空间下表示通常都是某种高维空间 固定的类别集合C=c1,c2,.,cJ 类别往往根据应用的需求来人为定义(如,相关类 vs.不相关类)训练集 D，文档d用c来标记，X C利用学习算法，可以学习一个分类器?，它可以将文档映射成类别：?:X C22文本分类的形式化定义：应用/测试22 给定：d X 确定：?(d)C,即确定d最可能属于的类别23主题分类2324课堂练习 24 试举出文本分类在信息检索中的应用例子25搜索引擎中的文本分类应用25 语言识别(类别:English vs.French等)垃圾网页的识别
11、(垃圾网页 vs.正常网页)是否包含淫秽内容(色情 vs.非色情)领域搜索或垂直搜索 搜索对象限制在某个垂直领域（如健康医疗）(属于该领域 vs.不属于该领域)静态查询(如，Google Alerts)情感识别:影评或产品评论是贬还是褒(褒评 vs.贬评)26分类方法:1.手工方法26 Web发展的初期，Yahoo使用人工分类方法来组织Yahoo目录，类似工作还有：ODP,PubMed 如果是专家来分类精度会非常高 如果问题规模和分类团队规模都很小的时候，能否保持分类结果的一致性 但是对人工分类进行规模扩展将十分困难，代价昂贵 因此，需要自动分类方法27分类方法:2.规则方法27 Google
12、 Alerts的例子是基于规则分类的 存在一些IDE开发环境来高效撰写非常复杂的规则(如 Verity)通常情况下都是布尔表达式组合(如Google Alerts)如果规则经过专家长时间的精心调优，精度会非常高 建立和维护基于规则的分类系统非常繁琐，开销也大28一个Verity主题(一条复杂的分类规则)2829分类方法:3.统计/概率方法29 文本分类被定义为一个学习问题，这也是本书中的定义，包括：(i)训练训练(training)：通过有监督的学习，得到分类函数?，然后将其(ii)测试测试/应用应用/分类分类(test)：应用于对新文档的分类 后面将介绍一系列分类方法:朴素贝叶斯、Rocch
13、io、kNN和SVM 当然，世上没有免费的午餐：需要手工构建训练集 但是，该手工工作一般人就可以完成，不需要专家。提纲30 上一讲回顾 文本分类朴素贝叶斯 朴素贝叶斯理论文本分类评价31朴素贝叶斯(Nave Bayes)分类器31 朴素贝叶斯是一个概率分类器 文档 d 属于类别 c 的概率计算如下（多项式模型）：nd 是文档的长度(词条的个数)P(tk|c)是在类别c中文档抽样得到词项tk的概率，即类别c文档的一元语言模型！P(tk|c)度量的是当c是正确类别时tk 的贡献 P(c)是类别c的先验概率 如果文档的词项无法提供属于哪个类别的信息，那么我们直接选择P(c)最高的那个类别1(|)(|
14、)()/()(|)()()(|)dkk nP c dP d c P cP dP d c P cP cP tc 32具有最大后验概率的类别32 朴素贝叶斯分类的目标是寻找“最佳”的类别 最佳类别是指具有最大后验概率(maximum a posteriori-MAP)的类别 cmap:33对数计算33 很多小概率的乘积会导致浮点数下溢出 由于 log(xy)=log(x)+log(y),可以通过取对数将原来的乘积计算变成求和计算 由于log是单调函数，因此得分最高的类别不会发生改变 因此，实际中常常使用的是：34 朴素贝叶斯分类器34 分类规则:简单说明:每个条件参数 是反映tk 对c的贡献高低的
15、一个权重 先验概率 是反映类别c的相对频率的一个权重 因此，所有权重的求和反映的是文档属于类别的可能性 选择最具可能性的类别35 参数估计:极大似然估计35 如何从训练数据中估计 和？先验:Nc:类c中的文档数目;N:所有文档的总数 条件概率:Tct 是训练集中类别c中的词条t的个数(多次出现要计算多次)给定如下的 位置独立性假设位置独立性假设(positional independence assumption):36 MLE估计中的问题：零概率问题36P(China|d)P(China)P(BEIJING|China)P(AND|China)P(TAIPEI|China)P(JOIN|Ch
16、ina)P(WTO|China)如果 WTO 在训练集中没有出现在类别 China中:37MLE估计中的问题：零概率问题（续）37 如果 WTO 在训练集中没有出现在类别 China中，那么就会有如下的零概率估计：那么，对于任意包含WTO的文档d，P(China|d)=0。一旦发生零概率，将无法判断类别38 避免零概率:加一平滑38 平滑前：平滑后:对每个量都加上1 B 是不同的词语个数(这种情况下词汇表大小|V|=B)39避免零概率:加一平滑（续）39 利用加1平滑从训练集中估计参数 对于新文档，对于每个类别，计算 (i)先验的对数值之和以及 (ii)词项条件概率的对数之和 将文档归于得分最
17、高的那个类40 朴素贝叶斯:训练过程4041 朴素贝叶斯:测试/应用/分类4142 课堂练习42 估计朴素贝叶斯分类器的参数 对测试文档进行分类43 例子:参数估计43上述计算中的分母分别是(8+6)和(3+6)，这是因为textc 和 (分别代表两类文档集的大小)的大小分别是8和3，而词汇表大小是6。44 例子:分类44因此,分类器将测试文档分到c=China类，这是因为d5中起正向作用的CHINESE出现3次的权重高于起反向作用的 JAPAN和TOKYO的权重之和。45朴素贝叶斯的时间复杂度分析45 Lave:训练文档的平均长度,La:测试文档的平均长度,Ma:测试文档中不同的词项个数 训
18、练文档，V:词汇表，类别集合 是计算所有统计数字的时间 是从上述数字计算参数的时间 通常来说:测试时间也是线性的(相对于测试文档的长度而言)因此：朴素贝叶斯朴素贝叶斯 对于训练集的大小和测试文档的大小对于训练集的大小和测试文档的大小而言是线性的。这在某种意义上是最优的。而言是线性的。这在某种意义上是最优的。提纲46 上一讲回顾 文本分类朴素贝叶斯 朴素贝叶斯理论文本分类评价47 朴素贝叶斯:分析47 接下来对朴素贝叶斯的性质进行更深层次的理解 先形式化地推导出分类规则 然后介绍在推导中的假设48朴素贝叶斯规则48给定文档的条件下，我们希望得到最可能的类别应用贝叶斯定律le由于分母P(d)对所有
19、类别都一样，因此可以去掉，有:49 过多参数/稀疏性问题49 上式中存在过多的参数 ,每个参数都是一个类别和一个词语序列的组合 要估计这么多参数，必须需要大量的训练样例。但是，训练集的规模总是有限的 于是出现数据稀疏性数据稀疏性(data sparseness)问题50 朴素贝叶斯条件独立性假设50为减少参数数目，给出朴素贝叶斯条件独立性假设：假定上述联合概率等于某个独立概率P(Xk=tk|c)的乘积。前面我们提到可以通过如下方法来估计这些先验概率和条件概率：51 生成式(Generative)模型51生成过程：利用概率P(c)产生一个类 以该类为条件，（在各自位置上）基于概率P(tk|c)产
20、生每个词语，这些词语之间相互独立 对文档分类时，找出最有可能生成该文档的类别52 第二个独立性假设：位置独立性假设52 例如，对于UK类别中的一篇文档，在第一个位置上生成 QUEEN的概率和在最后一个位置上生成它的概率一样 上述两个独立性假设实际上是词袋模型词袋模型(bag of words model)53 另一个朴素贝叶斯模型：贝努利模型53 回想一下BIM模型，此时每个类别c生成文档d是基于贝努利模型的 此时，词项在文档中只有出现与不出现两种 词项的出现之间仍然相互独立，计算时要考虑词项不出现的概率54 朴素贝叶斯独立性假设不成立的情况54 自然语言文本中，上述独立性假设并不成立 条件独
21、立性假设:位置独立性假设:课堂练习 给出条件独立性假设不成立的例子 给出位置独立性假设不成立的例子 在这些假设都不成立的情况下，为什么朴素贝叶斯方法有用？55朴素贝叶斯方法起作用的原因55 即使在条件独立性假设严重不成立的情况下，朴素贝叶斯 方法能够高效地工作 例子 概率P(c2|d)被过低估计(0.01)，而概率P(c1|d)被过高估计(0.99)。分类的目标是预测正确的类别，并不是准确地估计概率 准确估计 精确预测 反之并不成立!56 朴素贝叶斯 并不朴素56 朴素贝叶斯在多次竞赛中胜出(比如 KDD-CUP 97)相对于其他很多更复杂的学习方法，朴素贝叶斯对不相关特征更具鲁棒性 相对于其
22、他很多更复杂的学习方法，朴素贝叶斯对概念漂移(concept drift)更鲁棒(概念漂移是指类别的定义随时间变化)当有很多同等重要的特征时，该方法优于决策树类方法 一个很好的文本分类基准方法(当然，不是最优的方法)如果满足独立性假设，那么朴素贝叶斯是最优的(文本当中并不成立，但是对某些领域可能成立)(训练和测试)速度非常快 存储开销少 NB分类是一种“线上”模型，测试样本生成概率需实时计算得到提纲57 上一讲回顾 文本分类朴素贝叶斯 朴素贝叶斯理论文本分类评价58Reuters语料上的评价5859 例子：Reuters语料5960 一篇Reuters文档6061 分类评价61 评价必须基于测
23、试数据进行，而且该测试数据是与训练数据完全独立的(通常两者样本之间无交集)很容易通过训练可以在训练集上达到很高的性能(比如记忆所有的测试集合)指标：正确率、召回率、F1值、分类精确率(classification accuracy)等等关于训练集和测试集62 给定一个已标注好的数据集，将其中一部分划为训练集(training set)，另一部分划为测试集(test set)。在训练集上训练，训练得到的分类器用于测试集，计算测试集上的评价指标。另一种做法：将上述整个数据集划分成k份，然后以其中k-1份为训练集训练出一个分类器，并用于另一份(测试集)，循环k次，将k次得到的评价指标进行平均。这种做
24、法称为k交叉验证(k-cross validation)有时，分类器的参数需要优化。此时，可以仍然将整个数据集划分成训练集和测试集，然后将训练集分成k份(其中k-1份作为训练，另一份称为验证集validation set，也叫开发集)，在训练集合上进行k交叉验证，得到最优参数。然后应用于测试集。关于训练集和测试集63训练集测试集训练+测试训练集开发集测试集k交叉测试参数确定64 正确率P 及召回率 R64P=TP/(TP+FP)R=TP/(TP+FN)65 F值65 F1 允许在正确率和召回率之间达到某种均衡 也就是P和R的调和平均值:66 微平均 vs.宏平均66 对于一个类我们得到评价指标
25、F1 但是我们希望得到在所有类别上的综合性能 宏平均宏平均(Macroaveraging)：以类别为单位：以类别为单位 对类别集合C 中的每个类都计算一个F1 值 对C个结果求算术平均 微平均微平均(Microaveraging)：以类别-文档对为单位 对类别集合C 中的每个类都计算TP、FP和FN 将C中的这些数字累加 基于累加的TP、FP、FN计算P、R和F167 朴素贝叶斯 vs.其他方法6768本讲小结本讲小结 文本分类的概念及其与IR的关系 朴素贝叶斯分类器(朴素贝叶斯)文本分类的评价6869 参考资料69 信息检索导论第13 章 Weka:一个包含了 朴素贝叶斯在内的数据挖掘工具包 Reuters-21578 最著名的文本分类语料(当然，当前已经显得规模太小)RCV1是更大的常用的分类数据集 一个著名的文本分类综述(引用5000多次)：F Sebastiani,Machine Learning in Automated Text Categorization,ACM Computing Surveys 34(1):1-47(2002)课后习题70
