基于后缀树模型的文本实时分类系统的研究和实现(

1、基于后缀树模型的文本实时分类系统的研究和实现作者简介：张吉，出生于1979，女，硕士，主要研究方向网络安全、数据流管理；谭建龙，1974，男，博士，主要研究方向网络安全、数据流管理；郭莉，1969，女，硕士，副研究员，主要研究方向网络安全、数据流管理。 张吉1, 郭莉1, 谭建龙1 1(中科院计算所,北京市 100084)(zhangji) 摘 要:本文在面向网络内容分析的前提下，提出了一种基于后缀树的文本向量空间模型(VSM)，并在此模型之上实现了文本分类系统。对比基于词的VSM，该模型利用后缀树的快速匹配，实时获得文本的向量表示，不需要对文本进行分词、特征抽取等复杂计算。同时，该模型能够保

2、证训练集中文本的更改，对分类结果产生实时影响。实验结果和算法分析表明，我们系统的文本预处理的时间复杂度为O(N)，远远优于分词系统的预处理时间复杂度。此外，由于不需要分词和特征抽取，分类过程与具体语种无关，所以是一种独立语种的分类方法。关键词:实时文本分类；向量空间模型；后缀树中图法分类号:TP391Resarch and Implementation of On-line Text Categorization System Based on Suffix TreeCHANG Ji1,GUO Li 1, TAN Jian-Long1 1(Institute of Computing Tech

3、nology, Chinese Academy of Sciences, BeiJing, 100084) (zhangji)Abstract: We propose a text vector space model(VSM) based on suffix tree and implement a text categorizing system on the model. The model can perform fast matching by the support of suffix tree, obtain the vector presentation of text and

4、 avoid the complex computation such as word segmentation or feature extraction of the text. In addition, this model can guarantee that the alteration of the training set can affect the result of classification in real time. Experiment and analysis of the algorithm show that, the time complexity of t

5、ext preprocessing in our system is O(N), which is much better than that of word segmentation method. Besides, the avoidance of word segmentation and feature extraction shows that the categorizing process is irrelevant to do with the concrete language and is a language independent method.Key words:On

6、line Text Categorization; Vector Space Model; suffix tree1 引言随着信息技术的发展，特别是Internet应用的普及，人们已经从信息缺乏的时代过渡到信息极为丰富的时代。如何从大量信息中迅速有效地提取出所需信息也就成为一项重要的研究课题。由于分类可以在较大程度上解决目前网络信息杂乱的现象，方便用户准确定位所需信息，因此分类尤其是文本分类的研究日益重要1。文本分类是指在给定分类体系下，根据文本的内容自动确定文本类别的过程。通常来说，文本分类是面向自然语言处理的。在这种分类中分类的正确性远比分类的速度更重要。但是在网络内容分析中，我们认为分类

7、的速度和分类的正确性都必须充分考虑。在实时内容分析中，目前技术尚不足以直接高效地利用大量语义特征，但是我们至少可以综合分析某些字结构在文本中出现的量化统计特征。因此我们在面向网络内容分析前提下，提出了基于后缀树模型的实时分类系统，并做了部分测试工作。本文主要探讨了新的文本表示模型和这种模型下的一个分类系统的实现，第一部分为引言，介绍了实时文本分类系统的应用需求和研究现状；第二部分探讨了基于后缀树的文本分类方法，着重介绍了文本表示；第三部分给出了我们的实时文本分类系统的实现；第四部分是该系统的实验结果和相关分析；第五部分进行总结，并展望下一步的工作。1.1 实时分类系统的应用随着因特网在全世界的

8、普及，网络传输技术的迅速发展，每天世界上有惊人数目的信息在互联网上流动。如何快速地从这个巨大的信息流中得到自己想要的信息、过滤掉无用的信息，成为一个重要的课题。这些实时性较强的需求包括：垃圾邮件判别、网络情报分析、实时新闻分类等等。但是由于自然语言处理算法的复杂度一般比较高，很多基于自然语言处理的信息处理技术（包括语法分析，组块分析）目前在实时内容分析的环境中，尚无法应用。垃圾邮件是互联网上一个日益严峻的问题，据科技日报报道：“去年垃圾邮件给美国公司带来了89亿美元的损失，给欧洲企业带来了25亿美元的损失。美国研究人员估计，2002年，美国人均收到2200封垃圾邮件，而2007年将会达到360

9、0封。”垃圾邮件的判断一般来说也是一个分类问题：新来的邮件是正常邮件还是垃圾邮件。实时分类系统还可以应用于实时新闻分类。在竞争日趋激烈的传媒界，第一时间报道突发性事件是所有的编辑梦寐以求的事情；实时分类系统将这些信息迅速判断其类别，一旦有用户感兴趣的信息，可以马上向用户反馈。实时分类系统对于新闻机构和情报系统的实时采编是非常有帮助的4。自有人类以来，情报分析一直是一项很重要的工作。传统的方法是对情报进行定性分析、推理，从而作出决策，整个过程需要大量的人力劳动。而且在日趋复杂化的当今世界，已经很难根据个人经验知识和对当前形式的分析、认识，作出准确、快速的判断和预测。实时分类系统对网络情报进行快速

10、分类，有利于提高情报分析的效率，并为进一步分析工作提供信息。1.2 分类方法研究现状文本分类方法主要有基于统计与基于规则两大类。基于规则的文本分类方法在一定范围内可以得到较好的分类效果，但是需要人为设定规则，从而介入大量的人力，无法满足实时、自动分类的要求。基于统计的分类主要算法有：k近邻(KNN)，朴素贝叶斯法，贝叶斯网络，神经网络算法，支持向量机，EM算法，SOM算法等。其中SVM分类器和KNN分类器是目前分类性能较好的两种分类器。但是，这两种分类器所采用的方法都需要较长的预处理时间，并不适用于训练集动态变化的情况。所以，我们提出了基于后缀树模型的文本分类方法，因为其线性增长的特性9,10

11、，能够满足训练集动态变化的情况。2 基于后缀树模型的分类方法2.1 问题描述简单地说，文本分类系统的任务是：在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是一一映射，也可以是一对多的映射，因为通常一篇文本可以同多个类别相关联。用数学公式表示如下：文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结出的判别规则，确定文本相关的类别。2.2 文本表示一个中文文本表现为一个由汉字和标点符号组成的字符串，由字组成词

12、，由词组成短语，进而形成句、段、节、章、篇等结构。直接使用整个字符串作为分类的原始输入是很不方便的，有必要寻找一种更精练的形式化表示方法。目前，在信息处理方向上，文本的表示主要采用向量空间模型 (VSM)。经典的向量空间模型（Vector Space Model，VSM）是Salton等人于60年代末提出的，并成功地应用于著名的SMART系统，已成为最简便高效的文本表示模型之一。我们系统的一个重要改进在于不需要分词或特征提取，即不是通过提取特征值来得到表示文本的向量，而是采用后缀树结构，为训练集中的每个文件建树，再通过后缀树匹配，从而得到以测试文本为基准的向量表示。在本章中，将依次介绍后缀树结

13、构，以及在此之上的向量化方法和权重计算。2.2.1 后缀树结构后缀树是一种基础的数据结构，它能快速解决很多字符串方面的问题。下面是和后缀树相关的一些定义。定义1.1（输入字符集）：字符串中可能出现的所有字符的集合。定义1.2（后缀）：假设字符串S s1s2.sisn，其中，si属于输入字符集，那么Si sisi1sn是S从位置i开始的后缀。定义1.3（后缀树）：一个有m个字符的串S，它的后缀树是一棵有根的有向树，共有m个叶子，分别标号为1到m。每一条边都用S的非空子串来表示。从任一节点出来的两条边，它们必须以不同的字符开始。从根节点到叶子节点i，顺序经过的树边的串联，恰好为S从i位置开始的后缀

14、，即Si。此外，为保证所有的后缀都结束在叶子节点，在字符串末尾添加不属于输入字符集的字符$。见图1。图1字符串abab$的后缀树2.2.2 向量化算法在已有的分词系统中，有些用词语作为特征项粒度，那么在分类时不得不对输入文档分词，而分词是个很复杂、很耗时的过程；另外一些系统，直接使用N元字串，以避免分词过程。但两者都需要再进行繁琐的特征提取过程，所以，我们提出针对给定文本的多元字串文本表示方法，即同时统计1元到N元子串在给定文本中的出现次数。例如：中华人民共和国1元汉字串叠加：中 华 人 民 共 和 国；3元汉字串叠加：中华人 华人民 人民共 民共和 共和国；那么，对于长度为L的文本，其N元子

15、串的个数为(L-N+1)个。在2.2.1节中我们已经将文档Di表示为后缀树Ti，令测试文本为D，对于文本中任意位置k，在树Ti中查找从k开始的1元到N元子串的出现频率，记录在ac1，ac2，acN中。然后，利用公式得到位置K的对应值。其中p是字符串长度权重因子。为了强调相匹配字符串长度越大，文本之间的相似度越高，一般取p大于6。例如，设文档Di=“abcaba$”，N=2，测试文本D=“abc”,对于D的文本位置k=0，1元子串为“a”，其在Di中出现频率为3；2元子串为“ab”, 其在Di中出现频率为2；所以tf(0,Di)=3*1p+2*2p。同理可得，tf(1,Di)=2*1p+1*2p

16、，tf(2,Di)=1*1p。通过上述步骤，后缀树Ti就转换为长度为（LN+1）的向量tf(0,Di) tf(1, Di) tf(L-N, Di)。2.2.3 权重计算算法在2.2.2节中，我们以测试文本为基准，得到了文档Di的初始向量tf(0,Di) tf(1, Di) tf(L-N, Di)，对文本向量化面临着怎样计算权重，即向量各个分量的值的问题。给每个项赋权重时，应使得文本中越重要的项权重越大4。在我们的系统中采用归一化的tf-idf公式计算权重，即TFC权重，但计算idf值稍有不同，公式如下：其中，w(t,Di) 为位置t开始的多元组（1元到N元子串）在文本 Di 中的权重， M 为

17、训练文本的总数，mt 为训练文本集中出现该多元组的文本数，分母为归一化因子。2.3 分类算法当文档被表示为文档空间的向量时，两个文档Di和Dj之间文本相似度Sim（Di，Dj）就可以借助于向量之间的某种距离来度量。我们用夹角余弦值来表示相似度。考虑到消除文本长度对生成向量的影响，采用归一化的tf-idf公式计算文本的向量，得到的都是单位向量。本文使用k-近邻决策方法，就是将最近邻法扩展成找测试样本的k个最近样本作为决策依据的方法，其基本规则是，在所有N个训练样本中找到与测试样本最近邻的k个样本，其中属于第i类的文本近似度之和表示成ki，i=1,c，则决策规则是：如果，则决策K-近邻算法的训练过

18、程十分简单，它仅仅存储文本向量和文本对应的类别，而不进行归纳和分析，即不从训练样本中发掘类别的含义。换句话说，它允许类中全部样本点都具有代表类的资格。综上所述，当新文本到达时，该算法计算新文本与所有样本点之间的距离，选择 K 个距离最近的样本点，然后检查这些样本点的类别，按公式计算每个类别的比重值，将新文本归入比重最大的一类中。3 系统实现和以前的分类系统一样，我们的基于后缀树的实时文本分类系统也分为训练部分和实时分类部分，其整体框架如图2：训练过程分类过程训练文本预处理向量化处理测试文本输入分类和输出测试文本预处理训练文本输入图2 实时分类系统整体框架图在训练过程中，为训练集中的所有文本建树

19、，完成预处理；在分类过程中，首先，采用后缀树中多元文本匹配，得到初始向量；然后根据一定规则，对初始向量进行权重处理；最后利用分类算法，得到测试文本所属的类别。3.1 预处理模块该模块主要为给定文本建立后缀树。若采用直接的方法，为长度为n的字符串构建后缀树，其算法的复杂度为O(n2)。1973年Weiner第一次提出了线性时间的建树算法。几年后，McCreight提出了更节约空间的算法。但是他们的算法都难以理解，因此限制了后缀树的广泛使用。直到Ukkonen提出了改进的线性时间建树算法，它易于理解，而且具有在线特性，即从左到右依次处理每个字符6。所以，Ukkonen的算法在应用中被广泛接收。此外

20、，本系统需要统计绝对词频，因此对后缀树算法略加改进，在树中的每个节点中记录其叶子节点的个数，即该子串在后缀树表示的整个文档中出现的次数。3.2 向量化模块在该模块中，需要将后缀树表示的文档转换成向量表示。主要利用后缀树匹配算法，得到初始向量；再对初始向量进行权重计算，得到归一化处理后的tf-idf向量。后缀树的匹配算法相对简单，设S= s1s2sism1sm，从根节点出发，依次匹配边上的每个字符。如果匹配成功，即sm已经匹配完成，那么匹配结束的那个节点（如果匹配结束在边上，则取该边指向的子节点）下的所有叶子节点的位置信息都是该节点出现的位置。图3中，从根节点出发匹配字符串ab，匹配结束在三角号

21、表示的节点上，那么ab字符串出现的位置为该节点的叶子节点的位置信息1,3。在本文中，为了统计绝对词频，后缀树的节点中记录了子节点的个数，所以可以直接得到ab字符串出现的次数为2。如果需要分类的文本长度为L，那么需要进行L次匹配，每次匹配的最大深度为N(1元到N元的多元匹配)，那么在训练集大小为M的情况下，得到初始向量的时间复杂度为O(L*N*M)。得到以绝对词频表示的向量后，再利用前面的tf-idf公式计算归一化后的向量。图3在表示字符串abab$的后缀树上查找字符串ab3.3 分类模块在我们的实现中，由于实时进行向量化，所以在分类开始前，需要调用文本向量化模块对文本进行向量化，得到归一化的t

22、f-idf向量。然后利用前面的夹角余弦公式计算文本向量和各个文档向量的距离，根据KNN方法对该文本归类。4 实验结果与分析4.1 实验说明我们在一个具有3043篇中文文本的语料库上测试上述基于后缀树模型的实时分类算法。语料库中的文档都是新闻电讯稿，绝大部分采自新华社，还有200余篇采自中国新闻社和人民日报。所有的新闻稿都由领域专家事先进行分类，分成政治、经济、军事等共47类。我们对这些分类文档进行开放测试。在测试中，我们把所有3043篇中文随机分成10份，每次抽取1份作为测试集，而剩余的9份作为训练集。我们主要从准确率和处理性能两方面评价文本分类系统。准确率即经过分类系统处理，正确判断为所属类

23、别的文本数占总文本的百分比。处理性能则指在训练集固定或者变动情况下，分类系统处理一个文本所需的平均时间。4.2 准确率测试下面是我们的测试结果：类别文件数正确率类别文件数正确率Agriculture11266.96%Auto2466.67%Biology944.44%Computer3278.13%Economy16659.04%Language4280.95%Law8870.45%LightIndust3275.00%Medical5868.97%CheIndustry2781.48%Military8141.98%OilGas2382.61%New21180.09%Mine3491.18%

24、New218192.27%nMetallurgy3170.97%New34372.09%Mechanic1283.33%New45673.21%Construct2986.21%New52360.87%Water4072.50%New64488.64%Material5392.45%New72875.00%Transpor1070.00%Other3330.30%Ltheory7766.23%Politics43586.44%Airport9873.47%Sport20278.71%Enviornment2968.97%Chemistry4564.44%Art8180.25%Space1952

25、.63%Literate4134.15%Earth4285.71%Education8962.92%nPsychology6282.26%Philosaphy5875.86%Service2445.83%History6081.68%Energy5078.00%nMaths837.50%Electrony4060.00%Physics2958.62%Commun3378.78%每类文档数范围0,3031,6061,500平均准确率67.69%73.36%76.21%表1 基于后缀树模型的分类系统的测试结果及统计结果测试结果显示，文本数较多的类结果比较好，因为从概率的角度来说，文本数多的类别入选

26、K个最近距离的概率要远大于文本数少的类别。当每类测试文本数相近时，即仅采用每类文本数在范围25，65的26个类时，实验得到平均分类正确率91%。在此语料上，基于分词和N元汉字的分类方法准确率如表2所示：分类方法准确率 特征项数目10002000300040005000N元语法54.9458%64.9359%70.5882%73.9402%76.3391%基于分词时间62.4712%68.978%72.3628%73.8745%78.1466%基于后缀树74.57%表2 不同分类方法准确率对比从准确率上看，基于后缀树的分类方法达到74.57%，基本等同于基于分词、N元语法抽取4000特征项的情况

27、。因为特征项数目越多，分类时的信息量也越大，有可能达到或者超过基于后缀树方法的信息量，从而得到更好的准确率。但是，准确率的增加是以分类速度为代价的，随着准确率的增加，分类所需要的时间也逐步增长。4.3 处理性能测试我们在内存为512M，处理器为AMD OpteronTM 1.6GHz的计算机上进行性能的对比测试，得到基于分词、N元语法和基于后缀树分类的预处理的时间分别为74s，155s，4s。这是由于基于分词与N元语法的方法在预处理阶段都进行了文本表示、特征提取和向量化，而基于后缀树的分类方法在预处理阶段只进行了文本表示，这是由该方法的特性决定的：对于不同的测试文本，训练集的向量化结果不同，需

28、要在分类阶段进行实时向量化。基于后缀树的分类方法在分类阶段需要进行向量化、分类输出，其处理时间约为7kb/s,在处理时间上要远多于基于分词、N元语法的方法。但当训练集变动的情况下，基于分词和N元语法都需要重新训练，而基于后缀树的分类方法只需要进行几乎不占用时间的后缀树增删。对于测试语料中的单个文本，处理平均时间如表3所示：分类方法处理时间（s）训练集固定的情况下训练集变动的情况下基于分词0.174N元语法0.1155基于后缀树55表3 不同方法的文本分类处理平均时间在基于后缀树的分类方法中，文本的预处理时间，即对所有文本的建后缀树时间，与文本总长度成线性关系。向量化时间为O(N*L*M)，其中

29、，N为最大元项，L为要分类的文本长度，M为训练集中文本个数。分类时间为O(m*L+logM)，即将向量转换成两个文档之间的距离值，然后对M个距离值进行排序，取最接近的K个距离的时间。此外，在训练集中添加或者删除长度为N的文本，所需时间为0(N)。通过实验对比和理论分析，我们认为基于后缀树模型的文本分类系统适用于训练集频繁变动的情况，例如邮件过滤、实时网页分类等。5 总结与展望本文提出了一种新的文本分类方法，在不需要特征提取和分词的前提下，基于后缀树模型对文本进行实时分类。其优越性在于，预处理时间较短；实时生成向量，适合于训练集需要经常进行添删的情况；没有分词过程，独立于具体语种。但是，该系统的分类效果不是非常理想，特别是在每类文本数差别较大的情况下。而且，由于没有经过特征提取过程，所以噪音对最终结果产生了比较大的影响，这也是导致分类结果不理想的原因之一。我们将在该系统的基础上进行改进，并继续保留其不需要特征提取和分词的优势。针对其不同于传统分类方式的特征，重点对向量化过程和分类过程进行优化。参 考 文 献1 李晓黎，刘继敏，史忠植：概念推理网机器在文本分类中的应用J. 计算机研究与发展,