web文本分类中的几种阈值策略分析与比较

_ 作者简介：李晓黎(1979- ) 女 硕士研究生，研究领域：网上数据挖掘。 Web文本分类中的几种阈值策略分析与比较 李子久 摘 要 本文主要针对中文网页,分析比较了文本分类中的关于类别阈值的几种策略 ,分别是: 位置截尾 法（RCut）、比例截尾法（PCut）、最优截尾法（SCut）以及改进型截尾法（RTCut）,主要实验结果有: RTCut的效果最佳；PCut 具有一定的复杂度，不适合在线文本处理；SCut 具有一定的不稳定性；而 Rcut 性能最差, 并且使用英文文本和中文文本评测这几种阈值策略的结果是一致的。 关键词 文本分类 阈值 分类算法 特征选取 中图分类号 TP18 文献标识码 A 1. 引言 随着 web信息量的激增，人们需要自动的文本分类技术来实现对 web信息资源的规划 及利用。目前，文本分类是信息检索和数据挖掘领域的热门话题，它通过训练一定的文本 集合得到类别与未知文本的映射规则，即计算出文本与类别的相关度，再采取一定的阈值 策略决定文本的类别归属。不同的分类算法以及阈值策略都会对分类的结果产生一定的影 响。但是，目前文本分类的研究热点主要集中在 KNN、贝叶斯、支持向量机等分类算法上， 人们往往忽视了分类中阈值策略的重要性。阈值的确定是文本分类中的一个重要的步骤， 文献1提出了 4种阈值策略：位置截尾法（RCut）、比例截尾法（PCut）、最优截尾法 （SCut）以及改进型截尾法（RTCut），并且针对英文文本比较了上述四种阈值策略的优劣。 实验结果表明：RTCut 的效果最佳；PCut 具有一定的复杂度，不适合在线文本处理；SCut 具有一定的不稳定性；而 Rcut性能最差。 与英文网页不同的是，中文网页使用汉字，词与词之间没有间隔，不像英语单词之间 存在空格符，所以需要在文本分类之前对中文文本进行切词处理，并且切词的准确与否将 很大程度的影响分类的效果。所以，本文采用了一个中文网页数据集，对 RTCut、RCut、PCut、SCut 这四种阈值策略在中文网页上的性能进行评测。 2. 阈值策略 首先介绍一下文本分类中常用的阈值策略，然后依据分类器的性能，讨论一下各个策略 的优劣。 2.1位置截尾法（RCut） RCut方法将文本与每个类别的相似度排序，然后将文本指定给前 t个类别。参数 t即 可以由用户指定，也可以通过预定初始值，然后给出测试文本，使用分类器进行分类，再 根据分类的准确程度调整初始值。这种策略考虑到了分类器全局的性能，当 t=1时，多用 这种方法来将文本指定到单一类别当中 2。 2.2比例截尾法（PCut） PCut通过将所有测试文本与某一类别的相似度按照由高到低的顺序排序，然后将前kj个 文本确定为该类别，这里 （1）mxcPkjj)( 2 （2）训 练 文 本 总 数的 训 练 文 本 数 量类 别 jjcP)( 是类别数量， 代表类别 ， 是类别 的先验概率，可以通过公式（2）计算得mjj)(jPjc 到。 PCut考虑到了全局的分类性能，主要以x为参数，它的值可以通过分类的准确程度来调 整，这种确定方法类似于RCut中t值的确定方法。目前，一些分类器，如：贝叶斯、 DTree、kNN和 LLSF等方法采用了PCut阈值策略 3。 2.3最优截尾法（SCut） SCut针对某一类别，计算所有测试文本与该类别的相似度。根据最优化该类别分类器的 性能来调整相应的阈值，然后将确定的阈值应用到新的待分类文本上。RCut和PCut阈值策 略是平均所有分类器的性能，采用t或x作为参数；而SCut只优化某一类别的性能，并不保 证所有类别分类结果达到最优。SCut多被用于Ripper、FOIL、Winnow、EG、kNN、LLSF和 Rocchio等分类算法 4。 2.4改进型截尾法（RTCut） 文献1中提出了一种新的阈值策略，即改进型截尾法，这种方法修改了RCut和SCut的 不足，并将二者结合起来确定类别的阈值，使查全率和查准率达到一定的平衡。在RTCut中， 需要预先确定每个类的最优截尾阈值，新的阈值通过公式（3）计算： （3） 1)|(max)|()|( dcsdcrf C 这里， 是待分类文本， 是RCut中类别c的排列位置， 是类别c的最优截尾d| )|(s 阈值，而 是类别c的新阈值。)|(f 3. 实验结果及其分析 3.1实验设置 为了系统的比较RCut、PCut、SCut以及RTCut这四种阈值策略，作者设计了一个中文网 页分类系统，方案如下： （1）数据集 中文网页数据集是实现中文文本分类的前提和基础，为此，作者从中央财经网上人工获 取了一个新闻网页语料库，通过中文文本分类器将各新闻信息分门别类，以用于在网上发 布。该语料集包括5180个训练文本和615个测试文本，分为财政、经济、贸易、证券、科技 5个大类，每个类别平均有1000个训练文本。 （2）数据抽取 利用netspider获取目标网页以后，需要对Html文件进行解析，按照一定的抽取规则抽 取需要的数据项，系统中主要使用的抽取方法是将Html文本转换为一棵具有层次结构的 HTML树，利用树结构来表示网页中的标记关系。 （3）特征选取 DF即文本频度，它表示在训练集中包含某个特征项t的文本数。这种衡量特征项重要程 度的方法基于这样一个假设：DF较小的特征项对分类结果的影响较小。这种方法优先取DF 较大的特征项，而DF较小的特征项将被剔除。即特征项按照DF值排序。DF是最简单的特征 3 项选取方法，而且该方法的计算复杂度低，能够胜任大规模的分类任务 5,所以该文本分类 系统采用DF作为特征选取的标准。 （4）分类算法 系统中分类器所使用的分类算法为kNN，通过如下公式计算： （4）kNd jjiiji bcdyxSmcxp),(,),( 其中， 为新文本的特征向量， 表示 属于类 的权重， 为经过kNN方法训练、已归pjid 类的文本特征向量， 为类别属性函数，即，如果 属于类 ，那么函数值为1，),(jicy ijc 否则为0， 为预先计算得到的 的最优截尾阈值， 为 与 的相似度，通过jbj ),(ixSmi 公式（5）计算： （5）dxCos),( （5）评估指标: 分类系统的基本评测指标是准确率和查全率。 准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率。如公式（6）所 示： 实 际 分 类 的 文 本 数分 类 的 正 确 文 本 数准 确 率 )(precison （6） 查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率。如公式（7） 所示： 应 有 文 本 数分 类 的 正 确 文 本 数查 全 率 )(recal （7） 准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可偏废， 因此，存在 F1 测试值 6，其数学公式如下： 查 全 率准 确 率 查 全 率准 确 率测 试 值 21F （8） 系统中采用微平均（Micro-avg）和宏平均(Macro-avg)作为分类器的评估标准，其 中 微平均主要是考察单一类别的性能，而宏平均则是考察分类器的整体性能。 3.2实验结果及其分析 图 1显示了采用 kNN分类方法得到的 RCut、PCut、SCut 以及 RTCut的微平均 recall- precision曲线图，图 2是相应的宏平均指标曲线。其中，RCut 中 t取值为 1，2，3，Pcut 中 x=0.5,1,2,3，而 RTCut则利用精度的提高来调整阈值，并且 Scut 在图中以点的形式描述。图中画出了一条平衡线，线上准确率和查全率得到等值，并且平 衡线的附近可以得到最优的 F1值。 4 图 1 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1Micro-avg Recall Mic ro- avg Pre cis ion PCut RTCut RCut break-even-line SCut 图 2 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1Macro-avg Recall Mac ro- avg Pre cis ion PCut RTCut RCut break-even-line SCut 从图1和图2可以看出：1）Scut具有一定的不稳定性；2）Pcut由于考虑了分类器的全 局类别信息，所以具有较好的性能，但是并不适合在线处理；3）Rcut性能要弱于RTCut 和 Pcut，而RTCut由于综合了Scut和Rcut的优点，所以在文本分类的过程中，较好的提高了分 类的精度。论文得到的实验结果同文献1的实验结果基本一致。因此，这几种阈值策略在 普通英文文本和中文网页下表现出的性能是一致的。 参考文献 1.Yiming Yang.A Study on Thresholding Strategies for Text CategorizationC.In:Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR01),2001 2.T.Joachims.Text Categorization with Support Vector Machines:Learning with Many Relevant Features.In European Conference on Machine Learning(ECML),pages 137- 142,Berlin,1998.Springer. 3.D.Lewis.An evaluation of phrasal and clustered representations on a text categorization task.In 15th Ann Int ACM SIGIR Conference on Research and Development in Information (SIGIR92),page 37-50,1992. 4.WHersh,C.Buckley,T.Leone,and D.Hickman.Ohsumed:an interactive retrieval evaluateon and new large text collection for research.In Proceedings of ACM SIGIR94,pages 192-201,1994. 5.单松巍,冯是聪,李晓明. 几种典型特征选取方法在中文网页分类上的效果比较.计算机工程与应用 2003.22 6.冯是聪，单松巍，张志刚等$一个中文网页数据集及其分类体系C.见：海峡两岸技术交流会，南京， 2002-10:121-129 An Analytical and Comparative Study on Several Thresholding Strategies for Web Text Categorization Abstract: This paper reports a study with several thresholding strategies for Chinesetext categoryization,including rank-based thresholding(Rcut),proportion-based assignments(Pcut) and score-based local optimization(Scut).The main experimental results are:1) RTCut performs best; Pcut has more complexity and is not suitable for online response; Scut