第 6 章 文本分类、聚类

分类和聚类都是数据挖掘领域非常重要的任务,在文本数据分析过程中也有重要的应用。文本分类可以预测文本的类别,用于垃圾邮件的过滤、网页分类、个性化新闻提供等;文本聚类对结构内容相近的文本进行归类,用于实现文档集合的自动整理、搜索信息定位、用户兴趣模式识别等。 本章内容主要从文本分类和文本聚类两个角度出发,分别介绍了两种技术在文本数据分析过程中的应用流程、常见算法以及 Python 实现等,具体安排如下:前两节重点介绍文本分类和聚类的算法,6.1 节为文本分类算法,除分类思想及一般分类步骤外,主要介绍了朴素贝叶斯、最邻近、支持向量机、决策树、神经网络等常用分类算法;6.2 节为文本聚类算法,包括 K-means、BIRCH、GMM、GAAC 等,已经掌握了算法原理的读者可以忽略这两部分直接阅读后面的章节;6.3 节和 6.4 节重点介绍各种算法的实现方式,涉及到的工具库有 scikit-learn、NLTK、TextBlob、Pattern 等,此外还特别对部分聚类效果评价指标进行了说明;6.5 节将之前的内容加以整合,以实际分析案例的形式展示了文本分类、聚类的一般流程。

6.1 文本分类算法简介

6.1.1 分类思想

分类和聚类最重要的区别在于训练样本是否有类别标注。分类模型的构建基于有类别标注的训练样本,属于有监督学习,即每个训练样本的数据对象已经有对应的类标识,一般形式可以表示为:(v1,v2,...,vn; c),其中,vi表示样本属性或特征,c表示对应的类别。通过分类学习可以形成一个分类函数或分类模型,也就是常说的分类器,该分类器能把数据项映射到给定类别中的某一个类中,进而预测测试数据的类别。 文本分类,就是根据提取到的文本属性或特征,以及人工分标注的文本类别,构建分类器,将文本划分到已有的类别中。

一般的分类方法都可用于文本分类,常用的文本分类算法包括:决策树、神经网络、朴素贝叶斯(naïve bayes)方法、支持向量机(SVM)等等。

6.1.2 文本分类一般步骤

典型的文本分类过程可以归纳为文本类型标注、文本数据结构化处理、分类器构建和分类效果评价三个步骤。文本类型标注一般指利用人工对一批文档进行准确分类的过程,标注的结果作为训练集;文本数据结构化处理是为了把文本表示成分类器能够处理的形式,如上一章介绍的三种文本数据结构化的方式;分类器的构建涉及分类特征的筛选和构建方法的选择,需要根据实际问题的特点来选择相应的特征和方法,在训练集上构建分类器;将基于训练集构建的分类器应用于测试集数据,得到预测的分类结果,并对该结果进行评价,即所谓的分类效果评价,评价指标一般包括查全率、查准率、F1值等等。

6.1.3 常用文本分类算法

为了帮助大家更好的利用各类工具实现对于文本数据的分析,接下来我们将向大家介绍几种最为常用的文本分类算法,这些算法虽然基础,但对于初学者来说也是最为实用的。

6.1.3.1 朴素贝叶斯分类(Naive Bayes)

托马斯·贝叶斯(Thomas Bayes,1701—1761),是18世纪一位广受爱戴的英格兰长老会牧师。为了证明上帝的存在,贝叶斯全身心地投入到了概率与统计的研究之中,尽管他美好的初衷至死都未能实现,但其研究极大地推进了概率论与数理统计的发展,成为了概率统计学原理的奠基。贝叶斯所采用的许多术语被沿用至今,而贝叶斯分类器,正是基于其提出的贝叶斯公式而产生的机器学习分类方法。

贝叶斯公式:设 D1,D2,...,Dn 为样本空间中的划分,以 P(Di) (i=1,2,...,n) 表示事件 Di 发生的概率,且有 P(Di)>0。则对于任意事件 x , P(x)>0 ,有:

在贝叶斯分类大家庭中,朴素贝叶斯分类是最为简单的,但同时也十分的常见与实用,广泛地被应用于一些业界基础的文本分类场景中。我们可以顾名思义,朴素贝叶斯的方法思想真的很朴素:对于一个待分类的样本,我们依次求出在它的对应特征条件下每个分类出现的概率,那个分类的概率最大,我们就认为这个样本属于哪个分类。在文本数据分析中,我们样本的分类特征通常对应于文本数据结构化处理后的文本特征项,运用朴素贝叶斯分类的过程可以简单分为以下几个步骤:

1.准备工作:根据处理后的文本数据训练集,确定分类划分 D={y1,y2,...,yn} 与文本特征项 x={a1,a2,...,am} ;

2.分类器训练:计算训练集中所有特征情况的先验概率 P(a1),P(a1),...,P(am) ,每个分类出现条件下各个文本特征情况的条件概率 P(a1|y1),P(a2|y1),...,P(am|yn) ;

3.分类器应用:对于一个新的文本样本 x'={a1',a2',...,am'} ,我们根据贝叶斯公式,计算得在其文本特征出现的条件下每个分类出现的条件概率 P(yi|x')=P(x'|yi)P(yi)/P(x'),这个概率也被称为后验概率,比较每个分类对应的后验概率大小,进而得到新文本样本所属的分类 y'。

简单的朴素贝叶斯分类中包含了一个最重要的假设,那就是假设样本的特征之间是相互独立的,这个假设是也是整个朴素贝叶斯分类的基础,在我们日常的生活中,文本中字词的前后关联是显而易见的,并非完全的相互独立,因此在进行朴素贝叶斯分类器的应用前,准备工作阶段的文本特征提取是尤为重要的,如果能够提取得文本中相互独立的特征项,那么朴素贝叶斯分类的效果将会有显著的提高。

6.1.3.2 最邻近分类(Nearest Neighbors)

最邻近分类,或称 K 最邻近分类(K-Nearest Neighbor Classification),也是机器学习分类中最为简单的算法之一。1973年,高德纳·克努特(Donald Ervin Knuth)在其经典巨著《计算机程序设计艺术》中首次提及了最邻近分类算法,并将它称为“邮局问题”,即将其比喻为市井居民去寻找离家最近的邮局。值得一提的是,正是凭借这本书在计算机科学理论与技术方面的贡献,高德纳于1974年成功荣获了万众瞩目的图灵奖。

“近朱者赤,近墨者黑”是 K 最邻近分类的指导思想,其中的逻辑便是通过观察你的邻居,来推断你所属的类别。进一步来说,在 K 最邻近分类算法中,我们通常要进行以下几个步骤:

1.测量距离:这里所谓的“距离”,指的是对样本点之间相似程度的刻画,根据不同的样本特征,常用的距离度量包括欧氏距离(Euclidean metric)、马氏距离(Mahalanobis distance)、夹角余弦(Cosine)等。而对于文本分类来说,在最邻近分类中使用夹角余弦值来计算文本数据样本点相似程度会比直接计算欧式距离来得更为合适;

2.确定邻近点:在计算了新样本点与所有原始样本点之间的相似度之后,我们要做的便是确定其中几个与新样本点最为相似的样本,作为“邻居”。在最邻近分类中,样本点的个数通常由英文 K 表示,这也是为什么该类算法会被成为“K 最邻近分类”的原因。在一般的最邻近分类算法中,邻近点个数 K 都作为一个由人为设定的参数—— K 太小,分类结果易受噪声点影响; K 太大,近邻中又可能包含太多的其它类别的点。我们可以通过反复多次的交叉验证来确定 K 的最优值(因训练集而异),而从经验来看, K 的值一般低于训练样本数的平方根。

3.判断分类:由于样本的邻近点可能属于不同的类别,我们需要根据一定的规则来确定样本的类别,通常情况下,最邻近分类的分类判别基于加权或等权的投票。

作为一个看似十分“懒惰”的算法,最邻近分类算法的优点在于简单且易于实现,在算法运行过程中,我们无需估计任何的参数,所以也可以说,这是一种“无需训练”的分类算法。在文本数据分析中,最邻近分类算法适用于那些分类类别数繁多,且存在一些稀有类别(如不常见的特殊文本种类)时的场景。但同时,它也存在计算量大、内存开销大、效率较低的缺点,不适用于样本量规模过大的文本数据集。

6.1.3.3 支持向量机(Support Vector Machines)

支持向量机算法,简称SVM算法,是当下数学方法和最优化技术在机器学习分类中的最典型、最直接的应用。1995年,由俄罗斯统计学家万普尼克(Vldimir Vapnik)领导的 AT&T Bell 实验室研究小组首先提出了这一种十分具有潜力的分类技术,但由于当时研究本身不够完善,且数学上比较艰涩,一直没有得到学界充分的重视。不过 SVM 算法的寒冬不算太久,随着神经网络等当时新兴的机器学习方法在研究中开始遇到局部极小点问题等重要的困难, SVM 便迎来了迅速发展的春天,于90年代末在生物信息学、文本和手写识别等方面取得了一系列成功的应用。

与我们之前谈及的几种分类器算法不同,支持向量机从一开始便瞄准了不同类别样本点之间可能存在的分类边界,其解决分类问题的逻辑为构造一个用于分割样本类别的超平面,并以规划的思维来解决对样本类别的判断。简单来说,支持向量机有以下三大组成部分:

1.线性分类器:解决最优化问题——以函数间隔大于1为条件,最大化样本点至分类平面的几何间隔

2.核函数:低维空间向量集通常难于划分,解决的方法是将它们映射到高维空间。但这个办法带来的困难就是计算复杂度的增加,而核函数正好巧妙地解决了这个问题。也就是说,只要选用适当的核函数,就可以得到高维空间的分类函数。

3.软间隔:允许一些点游离并在在模型中违背限制条件(函数间隔大于1),处理规则化与不可分情况

@todo 详细补充(最优化问题理解+公式;核函数通俗意义+常用例子;软间隔说明)

支持向量机算法所构造的超平面就像一把超越维度的利剑,如果在低维的空间中无法划分黑白,那么它就会上升到更高维度的空间,将这混沌一分为二。这把利剑的优势在于相比于其他分类算法有着更稳定的性能与判断效率,但在文本分类问题中,由于文本特征向量具有稀疏性大、维数高、特征之间有较大的相关性的特点,文本数据中的噪音可能对支持向量机的训练速度、分类准确度产生较大影响。

6.1.3.4 决策树(Decision Tree)

作为一种常见且典型的分类方法,决策树算法产生于上个世纪的70年代,罗斯昆(J. Ross Quinlan)于1975年在悉尼大学提出的 ID3 算法象征着决策树算法的正式成型。简单来说,决策树算法的核心思路类似于我们日常生活中的判断与选择,例如某毕业生寻找工作,在个人逻辑上将可能会思考以下问题:该单位工作地点在哪?如果地点不错,那该单位工资水平如何?如果工资可接受,那么我在该单位有多少晋升的空间?如果还有不错的晋升空间的话,那这就是我想要的工作了。决策树算法分类的内核就是这样的一套策略逻辑,唯一不同的是,决策树算法的模型为特定的树结构(可以是二叉树或非二叉树),并且在所有的判定条件上都进行了量化。

一颗决策树由决策结点、分支和叶子组成。决策树中最上面的结点为根结点,每个分支是一个新的决策结点,或者是树的叶子。每个决策结点代表一个问题或决策,通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。

沿决策树从上到下遍历的过程中,在每个结点都会遇到一个测试,对每个结点上问题的不同的测试输出导致不同的分支,最后会到达一个叶子结点,这个过程就是利用决策树进行分类的过程,利用若干个变量来判断所属的类别。

决策树的构建主要基于逼近离散函数值的方法,常用的算法为 ID3 、 C4.5 与 CART 等。其基本步骤如下:

1)树以代表训练样本的单个结点开始;

2)如果样本都在同一个类,则该结点成为叶子,并用该类标记,否则在该结点上分裂;

3)算法选择最有分类能力的属性作为决策树的当前结点的分裂属性,其目标是让各个分裂子集尽可能地“纯”,即尽量让一个分裂子集中待分类项属于同一类别。在这一步骤上,不同算法所使用的划分准则指标不同,例如 ID3 算法评价的是不同特征属性分裂的信息增益(Information Gain),而其后继算法 C4.5 则考虑使用增益率(gain ratio)指标;

4)对于离散值类型的属性,决策树的构建过程会根据当前决策结点属性取值的不同,将训练样本数据集分为若干子集,每个取值形成一个分枝,有几个取值形成几个分枝;而对于连续值类型的属性,构建过程将会根据自身的划分准则确定合适的分裂点,从而确定划分的子集。针对上一步得到的一个子集,重复进行先前步骤1至3,形成每个划分样本上的决策树。同时,在一般的决策树构建过程中,一旦一个属性出现在一个结点上,就不必在该结点的任何后代考虑它;

5)递归划分步骤仅当下列条件之一成立时停止:

①给定结点的所有样本属于同一类。

②没有剩余属性可以用来进一步划分样本。在这种情况下,使用多数表决,将给定的结点转换成叶子,并以样本中元组个数最多的类别作为类别标记,同时也可以存放该结点样本的类别分布。

③如果某一分枝tc,没有满足该分支中已有分类的样本,则以样本的多数类创建一个叶子。

另外,在实际构造决策树时,我们通常要考虑对决策树进行剪枝,用于处理有数据中的噪声或离群点导致的过拟合问题,常用的剪枝逻辑有以下两种:

1)先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。

2)后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。

决策树优点其分类精度较高,且能够生成易于理解的分类模式,对于噪声数据,决策树算法的稳健性较好,在文本分类中能够有效减少对训练集样本过拟合的可能性。

6.1.3.5 神经网络(Neural Network)

神经网络算法,也称人工神经网络(Artificial Neural Network,ANN),是如今在人工智能广受追捧的深度学习的算法基础,也是文本数据分析常用的一类分类算法。神经网络的构筑理念是受到生物(人或其他动物)神经网络功能的运作启发而产生的。1943年,沃伦·麦卡洛克(Warren Sturgis McCulloch)和沃尔特·皮茨(Walter Pitts)运用数学技巧对阈值逻辑的算法进行改进,从而创造了最初的神经网络的计算模型,这项创举使得被注明为“神经网络”一词的研究从此分裂为完全不同的两个方向——一种关注大脑中的生物学过程,而另一种则主要关注机器学习与人工智能里的应用。

在人工神经网络中最简单的人工节点被称作神经元(neurons),神经元相互连接从而形成一个类似生物神经网络的网状结构。在上图中,a1~an为神经元输入向量的各个分量,w1~wn为神经元各个突触的权重值,b为偏置,f为神经元的传递函数,t为神经元输出。在数学上,一个神经元的功能可以理解为求得输入向量与权重向量的内积后,经一个非线性传递函数得到一个标量结果。同时,输入向量至输出标量的映射也被称为激励函数(Activity Rule)。

一般来说,最基础的神经网络模型可以被划分为以下三层: 1)输入层(Input layer):众多神经元(Neuron)接受大量特征输入,这些输入的特征被称为输入向量。文本数据分析中,这些特征可以等同于文本数据样本的特征项。 2)隐层(Hidden layer):神经网络的隐层由相互连接的神经元构成,一个神经网络模型中可以拥有多个隐层,每个隐层中的神经元数目不定,但数目越多神经网络的非线性越显著,从而增加神经网络的稳定性。在习惯上,我们通常将单个隐层的神经元个数设置为输入层结点的1.2至1.5倍。 3)输出层(Output layer):即神经网络模型结果的输出层,输出的结果也被称为输出向量,向量的每一个维度对应具体数据的分类划分可能性。

神经网络模型的训练过程也是对所有网络中每一层所有神经元权重及偏置的参数估计过程。常用的神经网络训练方法有梯度下降法等,该类方法需要我们规定网络中的权重如何随着时间推进而调整的学习规则(Learning Rule)。在规则的设定下,根据逐条或批量样本估计结果的误差损失,模型在训练过程中将逐步调整每一个神经元的权重与偏置参数,最终实现模型拟合。

作为广泛应用于人工感知领域的算法,神经网络在文本数据方面的应用相对来说在学术界较受重视。由于特殊的神经元权重结构,神经网络在对文本数据进行分析的同时体现了对文本知识的提取过程。但由于神经网络算法中的参数繁多,相对来说更容易出现过拟合的情况,因此在使用该类模型时应合理运用交叉验证等分类器评价技术。

results matching ""

    No results matching ""