斯坦福大学自然语言处理第六课“文本分类（Text Classification）”

本文主要是介绍斯坦福大学自然语言处理第六课“文本分类（Text Classification）”，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、课程介绍

斯坦福大学于2012年3月在Coursera启动了在线自然语言处理课程，由NLP领域大牛Dan Jurafsky 和 Chirs Manning教授授课：
https://class.coursera.org/nlp/

以下是本课程的学习笔记，以课程PPT/PDF为主，其他参考资料为辅，融入个人拓展、注解，抛砖引玉，欢迎大家在“我爱公开课”上一起探讨学习。

课件汇总下载地址：斯坦福大学自然语言处理公开课课件汇总

二、文本分类（Text Classification）

1）The Task of Text Classification

文本分类是机器对文本按照一定的分类体系自动标注类别的过程，其定义如下：

Input: a document d

a fixed set of classes C = {c₁, c₂,…, c_J}

Output: a predicted class ci

常见的分类任务有：

Assigning subject categories, topics, or genres：识别文本描述的主题；

Spam detection：典型的就是垃圾邮件的识别与过滤，如下图所示spam邮件：

Authorship identification：如1963年Mosteller and Wallace借助贝叶斯分类器对《Federalist papers》各章节的作者进行了准确识别。
Sentiment analysis：如对下面的电影评论进行褒贬分析(positive vs. negative)

unbelievably disappointing

Full of zany characters and richly applied satire, and some great plot twists

this is the greatest screwball comedy ever filmed

It was pathetic. The worst part about it was the boxing scenes.

Age/gender identification
Language Identification
…

常用的分类方法有：

Hand-coded rules：人工总结分类规则，如建立spam黑名单，又或者邮件文本中如果同时包含“dollars”和“have been selected”文本串就认为是spam邮件。显然，这种方法往往准确率非常高召回率很低，因为规则集需要人工精心撰写，也正因为如此，建立和维护规则集的过程比较费事费力。
Supervised Machine Learning：有指导的机器学习方法，或称有监督的机器学习方法，其过程形式化如下：

其中，γ为分类模型。常见的分类器有Naïve Bayes、Logistic regression、Support-vector machines、k-Nearest Neighbors等。

下面将以Naïve Bayes为例进行介绍，更多更详细的机器学习方法分享请参见：http://52opencourse.com/activity/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0

2）Naïve Bayes (I)

Naïve Bayes，即朴素贝叶斯分类器，号称“数据挖掘十大经典算法”之一，有着坚实的理论基础——贝叶斯定理。

在分类过程中，文本通常被表示成bag of words的形式（即假设文本中每个词汇的出现相互独立，并且不考虑出现的先后顺序）。如下图所示，通过对文本中包含的情感类词汇判断文本的极性（文本由情感词集表示）：

又如下图所示，通过度量测试文本与训练文本之间的相似度（下图中仅列出了按重要性排序后的Top-k words），标记测试文本分类。

3）Formalizing the Naïve Bayes Classifier

p(c|d)表示文档d属于某类别c的概率，那么：

则文档d的类别为，即后验概率最大的类别，计算过程如下：

其中，p(c)为先验概率，p(d|c)=p(x1,x2,…,xn|c)为条件概率，条件概率分布有着指数级数量的参数，后验概率计算时间复杂度为O(|X|ⁿ•|C|) ，随着文档长度增长也呈指数级增长，且稀疏性非常严重，需要庞大的语料库支持统计，实际中，估计条件概率参数是不可行的。

所以，朴素贝叶斯方法对条件概率分布作了条件独立性的假设，朴素贝叶斯也因此得名。条件独立性假设是：

即用于分类的文档特征（词xi）在类别确定的条件下都是条件独立的，与其出现顺序等均无关。此假设使得朴素贝叶斯法变得非常简单，但有时会牺牲一定的分类准确率。

朴素贝叶斯形式化表示为：

4）Naïve Bayes: Learning

在对新文档预测之前，需要先学习朴素贝叶斯模型，或称模型的参数估计。我们面对的主要任务就是估计p(c)和p(x|c)。

首先，最直接的方法就是在训练语料库基础上，应用极大似然估计法（maximum likelihood estimates）估计相应的概率。先验概率p(c)的极大似然估计是：

条件概率p(x|c)的极大似然估计是：

但是，用极大似然估计可能会出现所要估计的概率值为0的情况。比如，我们在正例训练集中未看到词条“fantastic ”，那么，只要文档中出现了该词条，肯定会有：

显然，这是不合理的。解决这一问题的方法是采用贝叶斯估计。条件概率的贝叶斯估计为：

其中，>= 0。当=0时就是极大似然估计，当=1时称为拉普拉斯平滑（Laplace smoothing，或称add-1 smoothing），更多平滑技术请见第四课“语言模型（Language Modeling）”。

最后，朴素贝叶斯法学习过程伪代码如下：

不难发现，朴素贝叶斯法是一个典型的生成模型，其通过数据学习联合概率分布p(x, c)=p(x|c)p(c)，然后通过求出条件概率分布p(c|X)作为预测结果。典型的生成模型还有隐马尔可夫模型HMM和LDA。这里不妨再多说一句，与生成模型相对的是判别模型，它是由数据直接学习决策函数f(X)或p(c|X)作为预测的模型。典型的判别模型包括：k近邻法KNN，感知器Perceptron，决策树Decision Tree，逻辑回归LR，最大熵模型MaxEnt，支持向量机SVM和条件随机场CRF等，后续章节会有涉及。

5）Naïve Bayes: Relationship to Language Modeling

朴素贝叶斯分类器和语言模型有着许多类似的地方，由“语言模型”章节可知，语言模型主要计算一个句子的生成概率大小p(s)。如果将类别融入几种，则转化为求一个句子属于某类别c的概率p(s|c)= 。示例如下所示：

那么，如果现在已经有两类pos和neg的条件概率分布，就可以为句子s标识一个合适的类别，如下：

条件概率p(word|c)是语言模型中的unigram model，由于朴素贝叶斯法基于条件独立性假设，所以，无法表示更高阶的语言模型。但是，相比语言模型仅使用词法信息，朴素贝叶斯法可以融入更多的特征，如url、email address，dictionaries, network features。

6）Multinomial Naïve Bayes: A Worked Example

接下来，通过一个toy example感受下朴素贝叶斯简单的分类过程。假如我们有如下表所示的Training 和 Test data。

先验概率为：p(c)=3/4, p(j)=1/4

条件概率为（采用add-1 smoothing）：

则有：

即测试文档d5的类别为c。

通过以上介绍，总结朴素贝叶斯分类器的特性如下：

Very Fast, low storage requirements
Robust to Irrelevant Features： Irrelevant Features cancel each other without affecting results
Very good in domains with many equally important features：Decision Trees suffer from fragmentation in such cases – especially if little data
Optimal if the independence assumptions hold: If assumed independence is correct, then it is the Bayes Optimal Classifier for problem
A good dependable baseline for text classification：But we will see other classifiers that give better accuracy

7）Evaluation：Precision, Recall, and the F measure

Precison、Rrecall和F-measure是文本分类任务最常用的评价方法。对于二元分类任务，用“selected”和“not selected”分别表示自动预测的正例和反例，“correct”和“not correct”分别表示分类结果的正确与否，如下表所示（contingency table）：

那么，Precision P = true positive / (true positive + false positive)，

Recall R = true positive / (true positive + false negative)

为了协调P和R的重要性，给出一个加权调和平均值（weighted harmonic mean）F-measure，公式为：

实际中，最常用的是F1-measure，即=1，此时认为P和R拥有相同的重要性。

当我们面临的任务非二元分类，而是多元分类时，如何进行评价呢？

定义cij为有多少篇ci的文档被自动分类到cj类别下，则有：

其中，accuracy也是常用的性能指标，其定义为：对于给定的测试数据集，分类器正确分类的样本数与总样本数之比。

在多元分类的P和R基础上，为了得到一个综合的评价指标，引入宏平均（Macro-averaging）和微平均（Micro-averaging）的概念，定义如下：

Macro-averaging: Compute performance for each class, then average.
Micro-averaging: Collect decisions for all classes, compute contingency table, evaluate.

如下例所示：

模型评估的目的就是得到最优的参数，为了避免过拟合现象（overfitting），往往在训练集（Training set）和测试集（Test Set）之外，还会引入开发集（Development Test Set，又称为验证集，Validation Test Set）。训练集用来训练模型，开发集用于模型的选择，而测试集用于最终对学习方法的评估。在学习到的不同复杂度的模型中，选择对开发集有最小预测误差的模型。当开发集有足够多的数据时，用它来对模型进行选择也是有效的。但是，在许多实际应用中，数据是不充足的。为了选择好的模型，还可以采用交叉验证（Cross-validation）的方法，其基本想法是重复地使用数据，把给定的训练数据进行切分，将切分后的数据集组合为新的训练集和开发集，在此基础上反复地训练、测试以及模型的选择。如下图所示：