汉字分词技术

!
""#$#计算机工程与应用%引言随着因特网在全世界的普及,网络传输技术的迅速发展,每天世界上有惊人数目的信息在互联网上流动.
如何快速地从这个巨大的信息流中得到自己想要的信息、过滤掉无用的信息,成为一个重要的课题.
这些实时性较强的需求包括:网络有害信息的判别、垃圾邮件的判断、实时新闻分类等等.
这些需求除了要求分类的正确性,更重要的是分类过程的快速实时性,但是由于处理的复杂度,很多基于内容的信息处理技术目前尚无法应用到实时环境.
对比传统的使用词语特征的文本向量空间模型,使用!
元汉字串特征的模型由于使用了快速的多关键词匹配技术,因此不必使用分词等复杂计算就可以实现实时文本分类.
另外,由于这些应用面临的是海量数据,必须能自动从样本中提取!
元串特征,笔者设计了!
元汉字串特征的自动提取和特征项选取算法.
该文主要探讨了基于!
元汉字串的文本表示模型和这种模型下的一个分类系统的实现:探讨了基于!
元汉字串的文本表示模型以及本分类系统采用的关键技术;给出了实时文本分类系统的实现;以及该系统的实验结果和计算复杂度分析.
!
实时分类系统的关键技术!
$%向量空间模型的文本表示目前,文本的表示主要采用向量空间模型/*0'1,&,/).
经典的向量空间模型是,.
1)*2等人于3"年代末提出的,并成功地应用于著名的,/456系统,已成为最简便基于!
元汉字串模型的文本表示和实时分类的研究与实现王映%,!
常毅%,!
谭建龙%白硕%%(中国科学院计算技术研究所软件研究室,北京%"""7")!
(中国科学院研究生院,北京%"""89):;.
2@=2AB*C)2摘要该文提出了一种基于!
元汉字串特征的文本向量空间表示模型,用这个表示模型实现了一个文本实时分类系统.
对比使用词语做为特征的文本向量空间模型,这种新的模型由于使用快速的多关键词匹配技术,不使用分词等复杂计算,可以实现实时文本分类.
由于!
元汉字串的文本表示模型中的特征抽取中不需要使用词典分词,从而可以提取出一些非词的短语结构,在特殊的应用背景,如网络有害信息判别中,能自动提取某些更好的特征项.
实验结果表明,使用简单的多关键词匹配和使用复杂的分词,对分类系统的效果影响是很小的.
该文的研究表明!
元汉字串特征和词特征的表示能力在分类问题上基本是相同的,但是!
元汉字串特征的分类系统可以比分词系统的性能高出好几倍.
该文还描述了使用这种模型的自动文本分类系统,包括分类系统的结构,特征提取,文本相似度计算公式,并给出了评估方法和实验结果.
关键词文本分类中文信息处理向量空间模型!
元汉字串关键词匹配文章编号%""!
;788%;(!
""#)"#;""77;"D文献标识码4中图分类号6E89%$%!
01)123)4.
0)#5#6/7%/#81&09%/01)1)!
48&%,7(0)#$#7(=%)8>0)8,@7(%)8>0,@5%)A0%).
1)8.
+'F.
G,H2B)=)I)'*CJ*)'(K2=OI')*B-''0)'P)Q=2$H)IB'B!
;+.
*+0*+-K+.
B',.
B=2)+.
0=)=*2.
1B@B)'=)K*I)JK=2'B'>*+0B'*+0B'*+0分词技术,分类系统以词作为特征项要优于以字作为特征项7/8.
短语特征:用中频的短语特征代替高频的词特征,同时和简单的词汇相比,短语的表现能力更强,更能反映文档的主题.
概念特征:词汇之间存在着同义关系、近义关系、从属关系、关联关系等丰富的语言现象,解决这些问题常用概念标注的办法,把同义的或相仿的项合并为相应的概念类.
%元字符特征:中文中的%元字符(9-:;:>@AB=CDE;CFBCDAG),互信息量('H:'BEB公式,一种比较普遍的L-H>公式:-(#,.
!
)"#,(#,.
!
)MI@:(%/0#N"$"()"#!
.
!
#,(#,.
!
)MI@:(%/0#N"$"(#$)!
%(!
)其中,-(#,.
!
)为特征项#在文本.
!
中的权重,而#,(#,.
!
)为特征项#在文本.
!
中的频率,%为训练文本的总数,0#为训练文本集中出现#的文本数,分母为归一化因子.
实时分类系统在文本向量化时,使用L-H>公式(!
).
!
$!
多关键词匹配算法一般而言,多关键匹配算法从单关键匹配算法派生.
单关键词的匹配算法的主要求解途径可分为前缀和后缀两种,分别对应O'P和+@GC;-'@@;C两种算法.
多关键词常用匹配算法QR@-J@;公司计算文本的向量表示.
对向量进行分类,存在多种分类算法.
设样本空间一共分为%类,则中心向量最近距离分类方法的时间复杂度为1(%),一般说来%值都不大,中心向量最近距离分类方法是非常快的分类方法,因此实时分类系统采用中心向量距离最近分类算法.
关于分类算法的准确率70,.
8,都实现了文本分类的中心距离最近分类算法,对于具有!
.
,"篇中文文本的语料库的测试结果是:中心向量最近距离方法效果稍逊于6-近邻方法,但好于贝叶斯方法.
,系统的实现实时分类系统共分为6个模块:%元汉字串提取模块、%元汉字特征选择模块、文本向量化模块和分类模块.
,$(%元汉字串提取模块先提取全部文档的所有可能%元汉字串.
因为在后续的特征抽取时,需要利用串的词频计算%元汉字串在各个分类中的比重以及在整个训练集中的比重,从而计算汉字串和各个分类的互信息量,因此提取%元汉字串时必须记录下来每个%元汉字串在训练集的各个分类中的词频,然后累加可以得到每个%元汉字串在全部训练集中的词频;在确定了特征项后,对训练文本或者待分类文本用L-H>.
5万方数据!
""#$#计算机工程与应用公式进行向量化时,需要特征项的%&'值,即前面的(')%&'公式中的*+,项,因此还必须统计!
元汉字串在所有训练集中出现过的文本数.
串提取程序对于!
(!
一般取!
、/或0)元汉字串,在每个分类的子目录下生成词频统计文件,文件的每一项为三元组(!
元串在本分类中出现的次数本分类中出现的文档数目),输出文件按!
元汉字串在分类中出现的次数(即词频)排序.
程序中利用折叠散列函数来加快!
元串的查找过程,利用标准模板库中的映射类模板123来处理散列冲突.
由前面的分析,需要记下!
元串的词频和文档数,因此123的456为!
元串,7282为结构(词频,文档数).
具体的算法如下:(.
)初始化,对!
元汉字串建立散列表,散列表的元素为123对象,对训练文本集合下的每个分类(对应于训练根目录下的各个子目录),应用下面的步骤(!
),(/).
(!
)从每个文本中切取!
元汉字串,加入散列表(/)将散列表按!
元汉字串的词频排序,以(!
元串词频文档数)元组形式输出到词频文件.
通过这个算法,得到了全部文档中的全部#元汉字串.
但是这些#元汉字特征数量是相当大的,因此,表示文本的基于这种特征的向量空间维数相当大,可以达到几万维,因而需要去掉某些不重要的特征.
/$!
!
元汉字串特征选择模块结合使用文档频次方法和互信息量方法的特征选择方法来选择!
元汉字串的特征.
其中!
为全部训练文档总数,#为串$出现的文档数.
具体算法如下:(.
)读取各个类的词频统计文件,累计全部训练文本的所有9元汉字串的词频和文档数,对各个分类应用步骤(!
),(/).
(!
)再次扫描分类下的词频统计文件,利用上面的公式计算各个!
元汉字串的权重及:7;值.
(/)利用12@5的自动机,从而可以对任何文档进行关键词扫描.
统计出任何一个关键词词(!
元汉字串)在文档中出现的绝对频率,从而得到以绝对词频表示的向量.
然后利用前面的(')%&'公式计算归一化后的向量.
系统中在训练时和实时分类时都要调用文本向量化接口.
训练时,系统调用文本向量化接口向量化所有训练文本并保存到文件中;实时分类程序启动时加载训练文本向量文件,生成各类的中心向量,然后就可以接收外部输入文本,用中心向量最近距离分类器对文本实时分类.
/$0分类模块在训练时,把所有训练文本都向量化保存在文件中就是为了初始化分类器作准备.
之所以保存所有训练文本的向量而不是各个类的中心向量,主要为了便于向其它分类器扩展.
在中心向量最近距离分类器初始化时,加载所有训练文本的向量,然后计算每个分类的中心向量.
分类开始后,调用文本向量化模块对文本进行向量化,得到归一化的(')%&'向量.
然后利用前面的夹角余弦公式计算文本向量和各个分类中心向量的距离,把本文本的分类判断为离中心向量最近的那个分类.
/$#系统的结构框架整合了上述模块后的整体结构如图.
所示.
图.
实时文本分类图图中,把分类过程分为了训练和分类两大部分.
0测试数据和实验结果在一个具有0A个分类、/"0/篇中文文本的语料库上测试上述基于!
元汉字串的实时分类算法,并和基于分词的分类系统进行了比较.
语料库中的文档都是新闻电讯稿,绝大部分采自新华社,还有!
""余篇采自中国新闻社和人民日报.
所有的新闻稿都由领域专家事先进行分类.
首先对这些分类文档进行封闭测试,以选择"!
元汉字串"中适当的!
值,以及适当的特征项个数,然后进行了开放测试.
0$.
各个参数对分类结果的影响表.
给出了!
取不同值、特征项个数从.
"""B#"""变化时,所有测试文本封闭测试下的准确率.
表.
分类准确率随!
和特征项个数变化表表.
中最后一行是分别平均取!
为!
,/,0的!
元汉字串混合起来作为特征项的结果.
从上表可以看出,在!
值确定以后,准确率随特征项个数增大而提高,但特征项个数越大准确率提高逐渐变慢;在特征项个数确定的情况下,!
值较小准确率比较高,选用混合!
元汉字串作为特征项不能提高准确率.
但是从上表可以看出,当!
取.
时,也就是退化为单字特征时,准确率比较低.
因为使用的多关键词匹配算法的时间复杂度为%(#"&),其中#为输入文本长度,&为最短关键词的长度,因此当!
比较小时可能匹配速度比较慢.
表!
给出了当特征项个数取#"""时耗时随!
的变化:因此,综合起来说!
取/,特征项个数取#"""以上能够达到很快的速度并且准确率降低较少.
特征项个数0"""#""".
#"$!
.
C#"$D.
C#.
$/DC#!
$/#C#/$"0C!
DE$AECA!
$#DCA/$FACA#$##CAA$.
FC/#0$F#CD0$F0CA"$#FCA/$F0CAD$/0C0#.
$#DCD.
$"!
CDA$"0CA!
$"/CA#$.
!
C!
,/,0D!
$!
ACDE$!
DCA"$F#CA!
$A!
CA0$#/C9值F"万方数据计算机工程与应用!
""#$#(上接%%页)该检测算法不需要原始图像.
实验结果表明:该文算法在保证图像具有良好的可视性的同时,对诸如&'()压缩、噪声、几何剪切、模糊等攻击均具有很好的鲁棒性;另外,该算法还具有计算简单、容易实现等优点,具有一定的应用价值.
(收稿日期:!
""*年+月)参考文献,$-.
/01,&231$/4556754849:;:=0474>:860@&A$B(((.
=:7C0:D94E70E7B>:86'=ED600478,,FFF;+(,):#+G%+!
$黄继武,HI4J17K,姚若河$基于块分类的自适应图像水印算法@&A$中国图像图形学报,,FFF;(*):%*"G%*LL$黄继武,HI4J17K,程卫东$M-.
域图像水印:嵌入对策和算法@&A$电子学报,!
""";!
+(*):#NG%"*$OP:=7469:;$QM-.
C5E>:470R096>SE==ET1094>:86:=478@&A$H487:;'=ED600478,,FF+;%%(L):L#NGLN!
#$QU:T46769:;$B7SE=>:94E7I45478::01=V6R@-A$B7:'=ED665478ES9I6B(((,,FFF:,"%!
G,"N+%$K410I6783:78,HI678I6H17$(>T65V401:;;R=6DE874W:T;6:=0479E4>:860@-A$B7:'=ED665478ESU4=09B796=7:94E7:;-E7S6=67D6E7B>C:86:75)=:XI4D0,.
4:7Y47-I47:,!
""":,#,G,#*!
值,!
L*耗时(0)L!
表!
当特征项数目取#"""时耗时随!
变化表这里的测试环境:'67941>BBB##"O/W,L+*OHMZQO,3475E0E7H9=4780,.
=660:75H6\167D60:-E>X196=HD467D6:75-E>X19:94E7:;P4E;E8R@OA$]74V6=049RES-:;4SE=74:'=600,,FFN!
$34;;4:>3-EI67,JE=:>H4786=$-E796^9C0670494V6;6:=7478>69IE50SE=96^9D:968E=4W:94E7@&A$Q-O.
=:70:D94E70E7B7SE=>:94E7HR096>0(.
_BH),,FFF;,N(!
):,*,G,NLL$_0>:=Z':4:76,O:=4:C214W:Q79E746$-;:004SR47896^95ED1>6790TR:00ED4:947896=>0X196=HD467D6-E>>174D:94E70,!
""!
;!
*(!
):!
,#G!
!
!
*$J4>478J:78$Q76V:;1:94E7ES09:94094D:;:XX=E:DI609E96^9D:968E=C4W:94E7@&A$&E1=7:;ESB7SE=>:94E7Z69=46V:;,,FFF;,(,a!
):%NG++#$J4>478J:78,b47241$Q=6C6^:>47:94E7ES96^9D:968E=4W:94E7>69IE50@-A$B7:'=ED6654780ESQ-OHB)BZ-E7S6=67D6E7Z606:=DI:75M6CV6;EX>67947B7SE=>:94E7Z69=46V:;(HB)BZ),,FFF:*!
G*F%$卜东波,白硕,李国杰$文本聚类中权重计算的对偶性策略@&A$软件学报,!
""!
;,L(,,)N$黄萱菁,夏迎炬,吴立德$基于向量空间模型的文本过滤系统@&A$软件学报,!
""L;,*(L)+$庞剑锋$基于向量空间的自反馈的文本分类系统的研究与实现@MA$硕士论文$中国科学院计算技术研究所,!
"",C"#F$张鑫$一种快速的多模式串匹配算法及其在实时汉语文本分类系统中的应用@MA$硕士论文$中科院计算技术研究所,!
""LC"L速度对比特征项数目(单位:秒)L"c元汉字时间,%!
#L**L#,准确率#*$F#[%*$F*[N"$#F[NL$F*[N%$L*[基于分词时间,!
FL!
"N准确率%!
$*N[%+$F+[N!
$L%[NL$+N[N+$,#[表*基于!
元汉字串的系统和基于分词的系统运行速度对比特征项个数L"N"""+"""准确率#*$F#[%*$F*[N"$#F[NL$F*[N%$L*[NN$%!
[N+$**[NF$,L[耗时(0),%!
#L**L#,#N%NNL指标F,万方数据