基于字符串核的免分词中文文本分类方法

基于字符串核的免分词中文文本分类方法　

游智李战怀张阳　

（西北工业大学计算机学院，西安７１００７２）　

摘　要　文本分类是获取文本信息的重要一步，现有的分类方法主要是基于统计理论和机器学习的，其中著名的有　Ｂａｙｅｓ【ｌｌ、ＫＮＮｔ２］、ＳＶＭｐｌ、神经网络等方法。实验证明这些方法对英文分类都表现出较好的准确性和稳定性　。对于中文文本　

分类．涉及对文本进行分词的工作。但是中文分词本身又是一件困难的事情　。论文尝试一种基于字符串核函数的支持矢　量机方法来避开分词对中文文本分类，实验表明此方法表现出较好的分类性能。　

关键词　核函数ＳＶＭ　字符串核　

文章编号１００２—８３３１一（２００６）２６—０１７０—０３　文献标识码Ａ　中图分类号ＴＰ３０１　

Ｃｈｉｎｅｓｅ　Ｔｅｘｔ　Ｃａｔｅｇｏｒｉｚａｔｉｏｎ　Ｗｉｔｈｏｕｔ　Ｗｏｒｄ　Ｓｅｇｍｅｎｔａｔｉｏｎ　

Ｕｓｉｎｇ　Ｓｔｒｉｎｇ　Ｋｅｒｎｅｌ　

ＹｏＵ　Ｚｈｉ　ＬＩ　Ｚｈａｎ－ｈｕａｉ　ＺＨＡＮＧ　Ｙａｎｇ　

（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｎｏｒｔｈｗｅｓｔｅｒｎ　Ｐｏｌｙｔｅｃｈｎｉｃａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ　７１００７２）　

Ａｂｓｔｒａｃｔ：Ｔｅｘｔ　Ｃａｔｅｇｏｒｉｚａｔｉｏｎ　ｉｓ　ｔｈｅ　ｆｉｒｓｔ　ｓｔｅｐ　ｔｏ　ｇａｉｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｆｒｏｍ　ｔｅｘｔｕａｌ　ｄａｔａ，ｅｘｉｓｔｉｎｇ　ｍｅｔｈｏｄｓ　ａｒｅ　ｍａｉｎｌｙ　ｂａｓｅｄ　

ｏｎ　ｓｔａｔｉｓｔｉｃａｌ　ｍｅｔｈｏｄ　ｏｒ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ，ｓｕｃｈ　ａｓ　Ｂａｙｅｓ，ＫＮＮ，ＳＶＭ，Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋ，ｗｈｉｃｈ　ｈａｖｅ　ｐｒｏｖｅｄ　ｔｏ　ｂｅ　ａｃｃｕｒａｔｅ　ａｎｄ　ｓｔａｂｌｅ　ｉｎ　ｅｘｐｅｒｉｍｅｎｔｓ　ｆｏｒ　ｃａｔｅｇｏｒｉｚｉｎｇ　Ｅｎｇｌｉｓｈ　ｔｅｘｔｓ．Ｈｏｗｅｖｅｒ，Ｃｈｉｎｅｓｅ　ｔｅｘｔ　ｃａｔｅｇｏｒｉｚａｔｉｏｎ　ｉｓ　ｍｕｃｈ　ｍｏｒｅ　ｄｉｆｉｃｕｌｔ　ｂｅ—　ｃａｕｓｅ　ｔｈｅｒｅ　ｉｓ　ｎｏ　ｓｐａｃｅ　ｂｅｔｗｅｅｎ　ｗｏｒｄｓ，ａｎｄ　ｗｏｒｄ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｈａｓ　ａｌｗａｙｓ　ｂｅｅｎ　ｕｓｅｄ　ｔｏ　ｓｏｌｖｅ　ｔｈｉｓ　ｐｒｏｂｌｅｍ．Ｔｈｉｓ　ｐａｐｅｒ　

ｄｅｌｉｖｅｒｓ　ａ　ｍｅｔｈｏｄ　ｕｓｉｎｇ　ｓｔｒｉｎｇ　ｋｅｒｎｅｌ　ｉｎ　ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅ　ｗｉｔｈｏｕｔ　ｗｏｒｄ　ｓｅｇｍｅｎｔａｔｉｏｎ　ａｎｄ　ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｒｅｐｏｒｔｓ　ａ　ｇｏｏｄ　ｒｅｓｕｌｔ．　

Ｋｅｙｗｏｒｄｓ：ｋｅｒｎｅｌ　ｆｕｎｃｔｉｏｎ，ＳＶＭ，ｓｔｒｉｎｇ　ｋｅｒｎｅｌ　

１　引言　

传统的学习系统把输入数据映射到一个ｍ维空间　上的　特征向量Ｄ。（Ｄ　…Ｄ　∈西），从而对特征向量ｄ。处理来实现各种　

学习和分类算法。但是在很多情况下，并不能直接从输入数据　直接获取特征向量，例如：生物基因特征，图像和文本。在这些　

复杂数据集上，特征提取方法决定着整个分类系统的性能。如　

果对这些数据简单的映射到一个ｍ维空间　会损失许多重要　的信息，如属性的顺序特征等。　

核函数方法（Ｋｅｒｎｅｌ　Ｍｅｔｈｏｄｓ）可以用作一种针对复杂数据　

集的有效特征提取方法，核函数计算的是映射到多维空间的特　征向量ｄ　（ｄ１．．・ｄ　∈Ｄ）间的中间值。著名的基于核函数的分类系　

统是支持向量机（Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅ，ＳＶＭ），它直接不依　赖于特征向量的维数，还可以针对不同的问题灵活的使用不同　

的核函数，目前越来越多的被文本分类领域研究和应用　

２相关知识　

支持向量机方法是统计学习、最优化方法和核函数方法的　

结合｛６１。对于线性可分的样品集（Ｘ。，ｙｉ），　１，２，…，／２，Ｘ　∈Ｒ　，ｙｉ∈　

卜１，１１，构造分类面：ＷＸ＋６＝０，使得Ｙ。（ＷＸ。＋６）一１≥０，ｉ＝１，２，　

…，／２，使得ｌｌ　ｌｌ最小。这样的　就叫做最优分类面，满足：Ｙ　（ＷＸ，＋ｂ）一１＝０的点　就称为支持向量（ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ）。　对于给定的训练数据集，从中学习得到参数Ｗ，ｂ的方法，　一般是利用拉格朗日优化方法。求解一个非负向量ｄ．与　的　

＾　关系是：　＝　ｄ　。　』：ｌ　核函数方法可以用于解决输入数据特征维数很高的情况　

下特征提取问题。它是一个对称的函数：Ｋ（Ｄ　，Ｄ，）＝　（ＤＪ，Ｄ　）其　中　√＝１，…，ｎ通过计算输入数据的核函数，得到一个对称的特　

征矩阵，这个矩阵就代表了所以输入数据的特征信息。核函数　

的计算方法目前有多种，如：线性核，多项式核，高斯核，Ｓｉｇ—　ｍｏｉｄ核等　

３字符串核函数　

首先，我们把每一个文本文档看成一个由文字、数字和标　

点构成的一个字符串。下面介绍如何求两个文档之间的字符串　核函数值。　

字符串核函数的思想是通过比较两个字符串共同包含的　

子串个数和连续程度来衡量两个字符串的相似程度。共同的子　串越多，两个文档就越相似。这里的子串不一定是连续的，但是　

它的连续程度被用来作为衡量的一个指标。　３．１　字符串核函数的形式化定义【９】　

定义１设∑是一个有限字母集合，Ｓ＝Ｓ　，Ｓ　，…，５　是∑上　的一个字母序列，其中Ｓ　∈∑，１≤　≤ＩＳＩ。设　，ｉ　，…，ｉ　】，且　

１≤ｉ＜ｉ　＜…＜　≤Ｉｓｌ是ｓ的下标的子集。则用ｓ［ｉ１∈∑　来表示字母　

作者简介：游智，硕士研究生，研究兴趣为文本数据挖掘。李战怀，博士生导师，研究方向为数据库理论与技术。张阳，博士，研究兴趣为数据挖掘与　知识发现。　‘　

１７０　２００６．

２６计算机工程与应用　维普资讯 http://www.cqvip.com 序列Ｓ　Ｓ　…，　．。这里的ｓ嘲并不一定是ｓ的连续子序列。例　

如：ｓ＝ＣＡＲＴ，　【２，４］，那么ｓ［ｉ］＝ＡＴ。设ｆ（　）表示ｓ嘲在ｓ中的跨　

度，那么：　

ｆ（ｉ）＝　一ｉ　＋１　（１）　则在∑上的两个字符串ｓ和ｔ的字符串核表示为：　

（　）＝∑∑∑　（２）　“∈∑　ｉ　５　ｌ　＝“』Ｉ　］＝“　其中Ａ∈ｆ０，１］是用来体现不连续情况下的衰减因子。第一　个求和符号代表所有长度为ｎ的字符序列。　

３．２字符串核函数举例　

例如：“中国人民银行”和“国民经济”都包含“国民”两字，　

但是这两个字在他们中的权值是不一样的。这里的权值决定于　

两个方面：出现的次数和子串在文档中的跨度。为了衡量子串　

在文档中的跨度，我们引入一个衰减因子Ａ　Ｅ（０，１）。　实例：我们以如下一组文档为例，假设四个文档分别包括：　

“中国人”，“中国魂”，“秦国人”，“秦国魂”。以子串长度Ｋ＝２为　

例，得到一个８维的特征空间。　

表１字符串核函数举例　

中国　国人　中国人　Ａ　Ａ　中国魂　Ａ　０　秦国人０　Ａ　秦国魂　Ａ　ｚ　０　国魂　秦国　中人　中魂　秦人　秦魂　０　０　Ａ　０　Ａ　０　０　Ａ　０　Ａ　０　０　Ａ　Ａ　０　０　

根据表１，“中国人”（Ａ）和“中国魂”（Ｂ）之间的核函数值　

为：Ｋ（Ａ，Ｂ）＝Ａ　，而Ｋ（Ａ，Ａ）＝　（Ｂ，Ｂ）＝２Ａ　＋Ａ　。对Ｋ（Ａ，Ｂ）定义　

如下的正规化：　

㈣＝—　２Ａ４＋Ａ６％／Ｋ（Ａ　Ａ　Ｂ　ＺＡ＝　２＋Ａ　，　）　（Ｂ，）　‘　

３＿３算法递归化［９１　

这个算法的时间和空间复杂度为０（Ｉ∑『　）。直接对两个文　本求字符串核．在文本包含字符多时，需要耗费很长的时间。为　

了降低算法复杂度，对算法进行递归化。　

由式（１）和（２）得：　

Ｋｉ＇（　，ｆ）：∑∑∑Ａ。　。　。一　】　Ｅ∑＿ｌ＿ｊ…　Ｊ：Ｉ　］　其中，ｉ＝１，…，ｎ一１。　

定义２递归计算字符串核函数值　（１）对于所有ｓ和ｔ，Ｋ０　（ｓ，￡）＝１。　

（２）如果ｓ或ｔ的长度小于ｉ，则Ｋ　（ｓ，￡）＝０。　

（３）如果ｓ或ｔ的长度小于ｉ，则　（ｓ，￡）＝０。　

（４）　（ｓ　，￡）＝Ａ　（ｓ，￡）＋　：　。（ｓ，￡【１：　一１］）Ａ　ｌ－ｊ＋２其中，ｉ＝　』：　＝　１，…，ｎ一１。　

（５）　（ｓ　，￡）＝Ｋ　（ｓ，￡）＋∑　。（ｓ，￡【１：　一１］）Ａ　递归化以后的　

』：垆　算法的时间复杂度为ｎ　ｌｌ　ｔｌ　。　４试验分析　

这里设计实验来验证字符串核在中文义本分类中的有效　

性．我们将把基于免分词字符串核方法和目前常用的基于分词　的线性核方法进行相同环境的对比。另外，还将讨论字符串核　

函数中参数ｋ（子串长度）和参数Ａ（衰减因子）对分类性能的　影响。　４．１试验数据集　

试验选择复旦大学计算机信息与技术系国际数据库中心　自然语言处理小组发布的《文本分类语料库（复旦）》…】。这个库　分为训练库和测试库两个部分，其中测试语料共９　８３３篇文　

档；训练语料共９　８０４篇文档，分为２０个类别。训练语料和测　试语料基本按照１：１的比例来划分。各类别分布如表２。　从中选出语料相对丰富的Ｃ１９，Ｃ３１，Ｃ３２，Ｃ３４，Ｃ３８，Ｃ３９　

六类作为试验数据集。其中Ｃ１９，Ｃ３１，Ｃ３２分为一组Ｇ　，Ｃ３４，　Ｃ３８，Ｃ３９分为一组Ｇ　。在Ｇ。和Ｇ　中分别依次选定二三类为正例　样本，其他两类为负例样本。正负样本比例大致控制在１：１。训　练数据集和测试数据集之间不包含重叠样本。训练数据集和测　

试数据集内也不包含重复样本。　线性核函数计算参数选用Ｊｓ　肘　的默认参数　，详细参见　参考文献【８］，单词权重使用ＴＦＩＤＦ方式给出。分词软件采用中　科院计算所汉语词法分析系统ＩＣＴＣＬＡＳ，详细参见参考文献　

【１０］。　４．２性能评价　

文本分类中普遍使用的性能评估指标有查全率（Ｒｅｃａｌ１．简　记为Ｒ）、查准率（Ｐｒｅｃｉｓｉｏｎ，简记为Ｐ）以及Ｆ。指标。二值分类　的评估一般使用列联表（Ｃｏｎｔｉｎｇｅｎｃｙ　Ｔａｂｌｅ）。表３为一个二值　

分类问题的列联表。　

表３二分类问题列联表　

真正属于该类的文档数真正不属于该类的文档数　

这时，Ｒ和Ｐ以及Ｆ。分别定义为：　

Ｒ：　，Ｐ＝　．　：　ａ＋ｃ　ａ＋ｂ　‘Ｒ＋Ｐ　本试验用以上三个指标来衡量系统分类性能。　

４＿３试验结果与评价　

图１分别表示：基于分词技术的线性核方法和基于免分词　

技术的字符串核方法两者的指标、查准率、查全率比较情况　其　中，ｓｔｒｉｎｇ代表基于免分词字符串核方法；ｌｉｎｅｒ代表基于分词的　线性核方法。　

图２表示了算法中子串长度ｋ对分类性能的影响（样本数　为５０）。可以看到对于中文文本，使字符串核对分类有效的取　值是Ｋ＝２，３，４，５。考虑到计算效率，在大量样本情况下（样本数　

大于３００），推荐使用Ｋ＝２，在小样本的情况下（样本数在１００　以下），推荐使用　＝５。　图３表示了算法中衰减因子Ａ对分类性能的影响。可以看　到对于中文文本，使字符串核对分类最有效的取值是Ａ＝０．９。　

从图３中可以看到对于Ａ＜Ｏ．９的情况，算法对于参数Ａ是　表２实验数据集中数据分布情况　

计算机工程与应用２００６．２６　１７１　０　０　０　＾　０　０　Ａ　

０　维普资讯 http://www.cqvip.com