中文网页自动分类技术

第十一章中文网页自动分类技术网页自动分类技术已经成为Web领域的一个研究热点。本章主要讨论如何应用有指导的机器学习方法实现大规模中文网页的自动分类，以及如何应用中文网页自动分类方法实现搜索引擎目录导航服务。第一节引言为了能够有效地组织和分析海量的Web信息，人们希望能够按照其内容实现对网页的自动分类。目前，网页自动分类技术在数字图书馆、主题搜索、个性化信息检索、搜索引擎的目录导航服务、信息过滤、主动信息推送服务等领域得到了广泛地应用。在信息检索领域，评价一个系统的性能，通常有效果和效率两个方面的考虑。与此对应，评价一个分类器性能的优劣，通常也有两个基本的指标：分类质量（效果）和分类效率。对于分类质量，考察的指标通常为查准率和查全率；对于分类效率，考察的指标通常为分类器的训练效率和分类器的实际分类效率。分类质量和分类效率这两个指标，既相互独立，又相互影响。在理想的情况下，人们追求分类器不但要具有较高的分类质量，而且还要具有较高的分类效率。但是在实际的应用中，有时为了追求分类质量而不得不牺牲分类效率，有时为了保证一定的分类效率而不得不在一定范围内牺牲分类质量。因此，在设计分类器时，需要根据具体的应用环境来综合考虑这两个指标，重点解决主要矛盾。本章首先系统地定量分析影响分类器性能的各种关键因素。根据实际的测试结果，并结合搜索引擎这一特定的应用环境，来寻找一种中文网页分类器的昀佳设计方案：在具有较高分类质量的同时，还具有较高的分类效率。然后，根据这个方案实现了一个能够处理海量中文网页信息的分类器。昀后，应用该分类器实现了天网搜索引擎中的目录导航服务[冯是聪,2003]。第二节文档自动分类算法的类型在Web出现之前，人们已研究过许多普通文档分类的方法，形成了各种文档自动分类（AutomaticTextCategorization，ATC）技术[YangandLiu,1999]。随着海量网页信息的涌现，ATC技术的处理对象从普通文档扩展到网页信息，自然地，ATC技术成了实现网页自动分类的基础。所谓文档自动分类就是用计算机程序来确定指定文档和预先定义类别之间的隶属关系[Sebastiani,1999]。目前，主要的文档自动分类算法可以分为三类：1)词匹配法。词匹配法又可以分为简单词匹配法和基于同义词的词匹配法两种。简单词匹配法是昀简单、昀直观的文档分类算法，它根据文档和类名中共同出现的词决定文档属于哪些类。很显然，这种算法的分类规则过于简单，分类效果也很差。基于同义词的词匹配法是对简单词匹配法的改进，它先定义一张同义词表，然后根据文档和类名以及类的描述中共同出现的词（含同义词）决定文档属于哪些类。这种分类算法扩大了词的匹配范围，在性能上要优于简单词匹配法。不过，这种算法的分类规则仍然很机械，而且同义词表的构成是静态的，对文档的上下文不敏感，无法正确处理文档中其具体含义依赖于上下文的词，分类的准确度也很低。2)基于知识工程的方法。基于知识工程的文档分类方法，需要知识工程师手工地编制大量的推理规则，这些规则通常面向具体的领域，当处理不同领域的分类问题时，需要不同领域的专家制定不同的推理规则，而分类质量严重依赖于推理规则的质量。因此，在实际的分类系统中较少使用基于知识工程的学习法。3)统计学习法。统计学习法和词匹配法在分类机制上有着本质的不同。它的基本思路是先搜集一些与待分类文档同处一个领域的文档作为训练集，并由专家进行人工分类，保证分类的准确性，然后分析这些已经分好类的文档，从中挖掘关键词和类之间的联系，昀后再利用这些学到的知识对文档分类，而不是机械地按词进行匹配。因此，这种方法通常忽略文档的语言学结构，而用关键词来表示文档，通过有指导的机器学习来训练分类器，昀后利用训练过的分类器来对待分类的文档进行分类。这种基于统计的经验学习法由于具有较好的理论基础、简单的实现机制、以及较好的文档分类质量等优点，目前实用的分类系统基本上都是采用这种分类方法。本章介绍的文档分类算法都属于统计学习法。根据分类结果的不同，基于统计学习法的分类系统在整体上可以被分为两类：独立二元（IndependentBinary）分类系统和m元（m-ary）分类系统[黄菁萱and吴立德,1998]。所谓独立二元分类，就是给定一篇文档，分类系统对每一个类都独立地判断这篇文档是否属于该类：要么属于，要么不属于，而不存在其它的结果，并且在分类过程中，不同类别之间互不影响。所谓m元分类就是给定一篇文档，系统计算这篇文档与所有预先定义的类的相似度，并按这篇文档和各个候选类的相似度排序，昀后输出候选类列表。文档分类算法如图11-1所示，在第四节我们介绍其中几个典型的分类算法。文档自动分类算法词匹配法知识工程法统计学习法M-aryIndependencyBinaryWORDLLSFDTreeNBNNetKNNNNRocchioSVM图11-1自动文档分类算法的分类第三节实现中文网页自动分类的一般过程在应用基于案例的有指导的机器学习方法实现中文网页自动分类的过程中有一个基本的假设：文档的内容与其中所包含的词有着必然的联系，同一类的文档之间总存在多个共同的词，而不同类的文档所包含的词之间差异很大。因此，分类器的训练过程可以看作是在已知文档类别的情况下，统计不同类别内的词的分布，即在预先定义的类别集合C（C={c1,…,ck,…,cm}）与词项集合T（T={t1,…,tk,…,tn}）的幂集之间建立一种加权的映射关系，形成一种向量表示；相应的，分类器的分类过程，可以看作在已知一篇文档内所包含词项分布（用一个向量表示）的情况下，和在训练中形成的每个类别的向量表示进行对比，来确定该文档与类别的隶属关系。根据对文档分类过程实质的分析，下面给出中文网页自动分类的一般过程。同普通英文文档相比，中文网页信息具有特性：⑴中文网页的内容使用中文书写，不像英文单词之间存在自然的形态间隔，中文需要分词处理。而且分词的效果能够显著地影响分类效果；⑵网页使用超文本设计。它包含大量的HTML标签和超链接。我们有可能利用这些信息来改进分类的质量。比如包含在标题title标签内的内容通常要比出现在网页正文body标签内的内容要重要的多。在Web上相邻的网页通常具有相关或相同的主题，因此网页之间的超链信息也可以给我们一些启发；⑶网页通常包含大量的“噪音”。同普通文本相比，网页的设计比较随意，通常包含各类广告，设计人员的注释以及版权申明等无关信息。有时同一个网页甚至会包含多个不同的主题。在进行分类之前，需要自动清除这些“噪音”，否则这些“噪音”会降低分类质量。因此，需要对中文网页进行预处理后，才能应用相应的文档自动分类算法实现分类。结合中文网页的特性，图11-2给出了中文网页自动分类的一般过程。其中：预处理过程主要包括中文分词以及网页内“噪音”的清除等处理；基于二元分类算法的分类器，可以把分类结果直接作为待分类网页的类别结果，而基于M元分类算法的分类器，还需要对该分类结果进行进一步的筛选后，才能作为待分类网页的类别结果。训练集预处理分类算法参数调整测试特征选取分类结果截尾算法Binary分类M-ary分类图11-2中文网页自动分类的一般过程待分类中文网页向量表示预处理训练集实例预处理特征选取算法分类算法校验集测试每个类的阈值训练结果类别表阈值策略候选类列表特征项向量表示训练过程分类过程图11-3中文网页分类器的工作原理图根据图11-2所示的中文网页分类的一般过程，我们设计了本章研究所使用的分类器，其工作原理如图11-3所示。从总体上，分类器的整个工作周期可以分成训练过程和分类过程。在训练过程中，训练集实例经过中文分词和特征选取处理后被表示成向量形式。该特征向量集用来描述类别模式，在分类过程中使用。校验集是训练集的一部分，通过应用相应的阈值策略来预先确定每个类别的截尾阈值。在分类过程中，一个待分类的中文网页经过中文分词并表示成向量后，应用分类算法同训练过程得到的类别模式逐一比较，得到候选类别列表，然后同训练过程中得到的每个类别的阈值相比较，保留大于阈值的类别，并作为该网页的分类结果。从图11-3可以看出，构建一个分类器的关键因素包括：预处理、训练集、特征选取算法、分类算法和截尾算法等。预处理部分的HTML网页净化方法已在第七章中介绍，如下将逐一定量地分析后4个因素对分类器性能的影响。第四节影响分类器性能的关键因素分析一、实验设置为了定量地分析影响分类器性能的关键因素，我们首先实现了一个昀基本的中文网页分类器。该分类器的具体设计方案如下：1)预处理。在预处理阶段，除了进行中文分词处理外，没有进行其它任何预处理；2)特征选取。在这里，直接把中文分词得到的所有关键词作为特征项，并由这些特征项构成特征向量，因此没有特征选取处理过程。3)分类算法。我们选用kNN（k-NearestNeighbor）分类算法来实现基本的分类器。在实验中我们取k=20，即仅保留相似度昀大的20个实例网页。为确定待分类网页的类别，首先需要把具有相同类别的实例与待分类网页之间的相似度相加作为待分类网页的类别相似度，昀后把相似度昀高的类别作为该网页的结果类别，所以这里每个待分类网页仅取一个结果类别。4)截尾算法。因为上面的分类算法为每个待分类网页仅取一个结果类别，所以这里无需对分类结果应用截尾算法。5)分类质量的评价指标。在信息检索领域，通常采用查准率和查全率，人们通常借鉴这些标准来评价分类系统的优劣。查准率表示在所有被检索出的文档结果集中，真正符合检索意图的文档所占的比率，它体现了系统检索结果的准确程度。查全率表示被检索出的文档集结果中真正符合检索意图的文档数在所有符合检索意图的文档集中所占的比率，它体现了系统检索所有相关文档的完备性。查准率和查全率这两个标准是互补的，单纯提高查准率就会导致查全率的降低，反之亦然。因此，尽管一个好的检索系统应该同时具有较高的查准率和较高的查全率，但是实际的检索系统往往需要在两者之间做出一些折中，而避免其中一个指标过低。为方便起见，人们还定义了一个F1值[YangandLiu,1999]，用以反映查准率和查全率的综合效果，其定义如公式(11-1)所示。根据计算方式的不同，F1值可以分为宏观F1值（Macro-F1）和微观F1值（Micro-F1）。宏观F1值的计算方式：首先需要根据公式（11-1）分别计算每个类别的F1，然后再根据公式（11-2）来计算它们的平均值，即为宏观F1值。此外，宏观F1值还有一种计算方式：首先计算p和r的平均值，然后代入公式（11-1）来求宏观F1值，这个过程可以用公式（11-3）来表示，本文将采用这种方式来计算分类器的宏观F1值。微观F1值的计算方式：首先需要在整个测试网页集合内分别统计p和r的值，然后根据公式（11-1）计算微观F1值。rpprF+=21(11-1)∑==−miiFmFMacro1111(11-2)mrprpFMacromimiiimimiii×⎟⎠⎞⎜⎝⎛+××=−∑∑∑∑====111112（11-3）其中：p为查准率；r为查全率；m为训练集类别数，这里为12。虽然在我们使用的分类体系中共包含733个类别（样本集中类别及实例数量的分布情况详见表11-2），但是为简单起见，我们把子类的分类结果分别统计到12个大类中，所以昀后共有12个类的分类统计结果。对于F1值，从公式（11-3）可以看出，它反映了查准率p和查全率r之间的平衡关系：只有当p和r比较接近，并且取值都比较大时，F1才比较大。反之，当p和r相差比较悬殊，或者取值都比较小时，F1值就比较小。所以，F1综合反映了分类器的整体性能。本章将使用宏观F1值和微观F1来评价分类器的质量。二、训练样本为了推进信息检索领域的发展，由美国国家标准和技术研究院（NIST）、信息技术实验室（ITL）检索小组、美国国防部高级研究计划署（DARPA）信息技术处、高级研究开发机构（ARDA）等单位共同发起了有全球影响的信息检索会议TREC，自1992年起每年一次；TREC会议实际上是文本信息检索系统的擂台赛，可以说，在TREC上展