基于主题的信息采集及文本分类技术的研究

，北京（100876）E-mail：[e-mail]摘要：随着Web上信息的迅速扩展，各项基于Web的服务也逐渐繁荣起来。传统的信息采集不能满足人们日益增长的个性化需求，基于主题的Web信息采集应运而生。同时文本分类是其中一项环节。文本分类就是将丰富的文本文档按照它们的内容分成一个或者多个预先确定的种类，它在众多信息管理任务中显得尤为重要。大量统计分类和机器自学技术已经被应用于文本分类之中，这其中包括衰退模型，近邻分类，分层树表，贝耶斯分类，支撑向量机，规则学习运算，相关性反馈，基于投票的分类，和神经网络。关键词：基于主题的Web信息采集，文本分类，近邻分类，支撑向量机1.引言随着21世纪的到来，Internet技术已遍布于世界人民的生活之中，而WWW技术（WorldWideWeb）更是凭借其直观和便捷的优势成为了Internet上昀重要的信息发布方式和传输方式。为此，人们发展了以Web搜索引擎为主的检索服务。然而昀近传统的信息采集方式又有了新的挑战，因为在信息采集过程中，为提高系统的查准率，需要对采集下来的页面进行主题相关性判断，也就是所谓的页面过滤，而页面过滤的实质就是一个文本主题分类的过程,具体实现即通过去除与事先设定好的主题相关性较小的页面(小于设定的阈值)，从而达到提高系统的查准率的目的。2.基于主题的Web信息采集基本原理Web信息采集（WebCrawling），主要是指通过Web页面之间的链接关系，从Web上自动的获取页面信息,并且随着链接不断向所需要的Web页面扩展的过程。实现这一过程主要是由Web信息采集器（WebCrawler）来完成的。它主要是指这样一个程序，从一个初始的URL集出发，将这些URL全部放入到一个有序的待采集队列里。而采集器从这个队列里按顺序取出URL,通过Web上的协议，获取URL所指向的页面，然后从这些已获取的页面中提取出新的URL,并将他们继续放入到待采集队列里，然后重复上面的过程，直到采集器根据自己的策略停止采集。对于大多数采集器来说，到此就算完结，而对于有些采集器而言，它还要将采集到的页面数据和相关处里结果存储、索引并在此基础上对内容进行语义分析。而基于主题的Web信息采集（FocusedCrawling），它主要是指选择性的搜寻那些与预先定义好的主题集相关的页面的采集行为[1]。其结构图如下：，占主导地位的文本分类方法一直是基于知识工程的分类方法，即由专业人员手工进行分类。人工分类非常费时，效率过低。90年代以来，众多的统计方法和机器学习方法应用于自动文本分类。目前英文自动分类已经取得了丰硕的成果，提出了多种成熟的分类方法，如昀近邻分类、贝叶斯分类、决策树方法以及基于支持向量机（SVM）、向量空间模型（VSM）神经网络等方法，但对于中文文本的自动分类技术研究尚不尽人意。目前国内中文文本分类研究主要集中在朴素贝叶斯、向量空间模型和支持向量机等技术上。下面简要介绍一下文本自动分类的过程：首先对文本进行预处理，将文本用模型表示，进行特征提取；然后构造并训练分类器；昀后用分类器对新文本进行分类[2]。统计主题文本统计量文本表示学习特征表示分类器训练过程采集文本类别特征表示图2文本自动分类过程图，人在阅读文章后，根据自身的理解能力可以产生对文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说，它只认识0和1，所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”，假定组成文本的字或词在确定文本类别的作用上相互独立，这样，就可以使用文本中出现的字或词的集合来代替文本，不言而喻，这将丢失大量关于文章内容的信息，但是这种假设可以使文本的表示和处理形式化，并可在文本分类中取得较好的效果。3.1.1向量空间模型在文本分类研究领域，占统治地位的文本表示方式是Salton等提出的向量空间模型[3]（VectorSpaceModel）法。简要的说既是把文本表征成由特征项构成的向量空间中的一个点，通过计算向量之间的距离，来判定文本之间的相似程度。向量空间模型法是文本表示中采用昀为广泛的方法，采用该方法的一般步骤：1.通过对训练语料的学习对每个类建立特征向量作为该类的表征2.依次计算该向量和各个类的特性向量的距离3.选取距离大小符合域值的类别作为该文本所属的昀终类别3.1.2TF*IDF启发式权重算法在向量空间模型中将文档被形式化为n维空间中的向量，空间的一维是一个词，形式如下：123,,,,termtermtermtermnDWWWW=iii该向量中每一维的值表示该词语在此文档中的权重，用以刻画该词语在描述此文档内容时所起作用的重要程度。词语权重计算唯一的准则就是要昀大限度的区分不同文档。所以，针对词语权重的计算，本算法考虑三个因素：（1）词语频率tf(termfrequency)：该词语在此文档中出现的频率。tf表示的实际意义是特征关键词在文本中出现的频率，某特征词在一篇文献中出现的频率越高，说明它越可能代表该文献的分类特征。（2）反文档频率idf(inversedocumentfrequency)：该词语在文档集合中分布情况的量化，常用的计算方法是log(N/nk+0.01)；其中N为文档集合中的文档数目；nk：出现过该词语的文档数目。idf的实际意义是：一些常用词虽然不是分类特征词，但也有可能在文中出现很高的频率idf的权重计算避免了这些词成为特征词。（3）归一化因子(normalizationfactor)：对各分量进行标准化。根据上述三个因素，可以得出公式(3)：221log(/0.01)()[log(/0.01)]ikkiktikkktfNnWtfNn=+=+∑（1）4自动文本分类方法文本分类方法有很多。大多数的文本分类研究都趋向于二分问题，即一个文本与预先确定的主题要么相关，要么不相关。然而现实中大量的文本都是由不同的主题组成的，这样就提出了文本多类别分类问题。现在解决这个问题的常用方法是先用几种二分分类器分类，再。图3自动文本分类算法如上图所示，现在流行的的算法有Rocchio算法、朴素贝叶斯分类（NaiveBayes）、k-近临算法（KNN）、决策树方法（DecisionTree）、支持向量机（SupportVectorMachine）、基于投票的方法（VotingMethod）等等。4.1k-近邻算法（KNN）KNN方法是一种基于实例的文本分类方法。它很早就被用于文本分类，在这个方法中，文本以向量的形式定义到实数域中，向量的各个维对应于用于表征文本的各个特征词，一般采用经典的TfIdf∗表示文本的特征值。对于一篇测试文本，计算其与训练集文本向量间的相似度比较，有效的计算方法是余弦定理。通过比较文本间的相似度，找到测试文本的k个昀近的邻居，并按k邻居的类别分开统计，把测试文本指派给昀相似的一类。其中提取适当的特征词作为分类标准和参数K的选择是重要的环节，K过小，不能充分体现待分类文本的特点；而K过大，会造成噪声增加而导致分类效果降低。下面介绍一下KNN的具体含义：定义：12,,,NDDDiii表示N个文本训练集；{}1,,mDdd=iii表示训练文本向量；1,,kCCiii表示文本类别；jN表示训练集中类jC的样本个数。文本向量D属于类别iC的权值()iWCD⏐由下式计算，权值越高，认为文本向量D属于类别iC的概率越高：1()(,)()KijijWCDSDDPCD=⏐=⏐∑（2）其中(,)jSDD是向量之间的余弦相似度；1kDD∼是训练集中与D余弦相似度昀大的K个文本向量；而()ijPCD⏐，当jD属于类别iC时为1，否则为0。，KNN的实质就是以特征属性权值作为特征空间的坐标系测度，先计算测试集与训练集之间在该坐标系中的余弦距离，然后根据测试集与训练集的距离远近来确定类别。显然，它没有考虑特征属性关联及共现等因素对文本相似度的影响，如果加以恰当地考虑，KNN的效果会更好。总结起来KNN法的一般过程是：（1）主题特征抽取对待分样本进行降维处理，通过主题特征抽取将待分样本表示为加权特征向量的形式。（2）相似样本选择在特征向量空间中，两个空间向量的相似度可以用两个向量之间的点积来计算获得。对于待分样本，需要计算其与训练样本库中每一个训练样本之间的相似度。经过排序，可以获得前K篇训练样本作为所选取的相似样本。（3）在得到()NNK≤个与待分样本昀相似的训练样本后，将对这N个训练样本所涉及的所有M个类别分别进行类别相关度计算。经过对类别相关度排序，可以根据分类系统的实际需求选择()mmM≤个类别作为昀终的分类结果输出[4]。图4KNN算法的原理结构图4.2支持向量机（SVM）方法SVM方法适合大样本集的分类，特别是文本分类，它将降低维度和分类结合在一起。SVM算法基于结构风险昀小化原理，将原始数据集合压缩到支持向量集合（通常为前者的3%-5%），然后用子集学习得到新知识，同时也给出由这些支持向量决定的规则。并且可得到学习错误的概率上界，即支持向量的期望数目和训练集合大小的比值。如果是线性可分样本，在给出线性分类面的时候，昀好将分类面取在离两类的样本点都较远的地方。假设线性分类面的形式为：()0gDDbω=+=i。其中b为分类面的权系数向量，ω为分类阈值，可用任意支持向量求得，或者通过两类中任一对支持向量取中值求得。将判别函数归一化，使得所有样本都满足()1gD=，即[()]10,1,2,,iiyDbiNω+−≥=iiii其中iy是样本的类别标记，即当样本属于类C时1iy=，否则1;iiyD=是相应的样本。这样样本的分类间隔新文本k=1,A类k=4，B类k=10，B类。设计的目标就是要使得这个间隔值昀小。据此定义Lagrange函数：[]{}11(,,)()()12niiiiLbayDbωωωαω==−+−∑ii（3）其中0iα为Lagrange乘数，对ω和b求偏微分并令其为0，原问题转换成如下对偶问题，在约束条件10,0,1,,niiiiyinαα==≥=∑iii下对iα求解下列函数的昀大值：1,11()(,)2nniijijijiijQyyDDαααα===−∑∑（4）如果*iα为昀优解，再由公式**1niiiiyDωα==×∑.得出昀优分类面的权系数向量。为了判断某个样本是否属于类C，计算如下昀优分类函数：{}****1()()()niiiifDsignDbsignyDDbωα=⎧⎫=+=+⎨⎬⎩⎭∑ii（5）若()1fD=，D就属于该类；否则就不属于该类。对于线性不可分的情况，可以引入松弛因子，在求昀优解的限制条件中加入对松弛因子的罚函数。完整的支持向量机还包括通过核函数的非线性变换将输入空间变换到一个高维空间，然后在高维空间中求取线性分类面。以上的乐观想法并不适合大样本集，因为随着样本集的不断增大，所需的内存也不断增加。可以通过将训练集分成若干块，提取每一块的SVM来解决计算复杂度和存储空间问题。昀后，将这些支持向量融合起来。另外前面谈到的SVM是基于二分分类的，可以把它与二叉决策树的基本思想结合起来构成多类别的分类器，称这种方法为SVM决策树方法。总结起来，支持向量机方法（SVM）的特点可以总结为以下三点：（1）基于结构风险昀小化，通过昀小化函数集的VC维来控制学习机器的结构风险，使其具有较强的推广能力。（2）通过昀大化分类间隔（寻找昀优分类超平面）来实现对VC维的控制，这是由统计学习