（模式识别与智能系统专业论文）基于支持向量机的一体化分词聚类研究.pdf

摘要 摘要 本文研究的目的是建立一个统一的分词，聚类，语义空间模型。我们使用了 面向对象的方法，有利于本系统的结构的升级和修改。 本文主要的工作由三部分组成：分词，聚类，使用分词、聚类的结果建立语 义空间。分词，聚类统一使用统计学习的方法进行处理。 分词技术是进行高级自然语言理解，检索，等工作的前提。本文通过统计学 习理论，着重研究在小样本情况下的统计规律及学习方法性质。它为机器学习问 题建立了一个较好的理论框架，也应用发展了一种新的通用学习算法：支持向量 机( s ) 。本文从支持向量机理论、方法和应用结合的角度出发，研究了支持向 量机在中文分词中的应用。 然后对于分词结果建立倒排索引的同时，进行词聚类。这同样也使用到了支 持向量机。对于分词时用到的统计信息可以在聚类时继续使用，降低了程序的代 价。这是一种提高效率的方法。 最后，研究了语义空间建立的问题，使用分词，聚类的结果，使用p l s i 方 法建立语义空间矩阵，对文章进行浅层次的理解。 经过调试和运行，本论文研究设计的一体化分词聚类，建立语义空间方法能 够达到设计要求，改善了语义空间建立耗费巨大资源的局面。 关键词：支持向量机分词聚类算法语义空间词频统计互信息 a b s t r a c t a b s t r a c t s e g m e n t a t i o nt e c h n o l o g yi sa d v a n c e dl a n g u a g eu n d e r s t a n d i n g , r e t r i e v a l ，a n ds oo n t h ep r e m i s e t h i sa r t i c l ep a s so fl e a r n i n gt h e o r y , f o c u s i n go ns m a l ls a m p l e si nt h ec a s e o ft h es t a t i s t i c a ll a w so fn a t u r ea n dl e a r n i n gm e t h o d s m a c h i n el e a r n i n gp r o b l e m si t c r e a t e dab e t t e rt h e o r e t i c a lf r a m e w o r k ，b u ta l s ot h ed e v e l o p m e n to fan e wu n i v e r s a l l e a r n i n ga l g o r i t h m s ：s u p p o r tv e c t o rm a c h i n e ( s v m ) t h i sa r t i c l ef r o mt h es u p p o r t v e c t o rm a c h i n et h e o r y , m e t h o da n da p p l i c a t i o no fc o m b i n a t i o no ft h ep o i n to fv i e wt o s t u d y t h es u p p o r tv e c t o rm a c h i n ei nt h ec h i n e s ew o r ds e g m e n t a t i o na p p l i c a t i o n t h er e s u l t sf o rt h ew o r da n dt h e nt h ee s t a b l i s h m e n to fi n v e r t e di n d e xa tt h es a m e t i m e ，t h ew o r dc l u s t e r i n g t h es a m ei sa l s ou s e dt os u p p o r tv e c t o rm a c h i n e s t h ew o r d w h e nu s e di nt h ec l u s t e r i n go fs t a t i s t i c a li n f o r m a t i o nc a nc o n t i n u et ou s e ，r e d u c i n gt h e c o s to ft h ep r o c e d u r e t h i si saw a yt oi m p r o v e e f f i c i e n c y f i n a l l y , t h ea r t i c l es t u d i e d t h ei s s u eo ft h ee s t a b l i s h m e n to fs e m a n t i cs p a c e ，t h eu s eo fs e g m e n t a t i o n ，c l u s t e r i n g r e s u l t s ，t h eu s eo fm e t h o d st oe s t a b l i s ht h es e m a n t i cs p a c ep l s im a t r i xo fa r t i c l e s l o w e ru n d e r s t a n d i n g k e yw o r d s ：s v m ，c h i n e s ew o r ds e g m e n t a t i o n ，c l u s t e r i n ga l g o r i t h m ，s e m a n t i c m o d e l ，s t a t i s t i ct h ef r e q u e n c yo ft h ew o r d ，m u t u a li n f o r m a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究：r 作和取得的研究成果， 除了文中特别加以标注和致谢之外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得丞洼三些太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名新武，签字嗍年月日 学位论文版权使用授权书 本学位论文作者完全了解云洼王些太堂有关保留、使用学位论文的规定。特授权云 洼王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩 印或扫描等复制手段保存、汇编以供夯阅和借阅。同意学校向国家有关部门或机构送交论文 的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 讳氐 i 签字日期：年月 日 导师签名： 签字胁1 年二月砷同 学位论文的主要创新点 一，使用互信息作为分词和聚类的方式统一分词聚类过程，降低程序的代价。 二，使用聚类后的结果用于建立语义空间，提高系统的运行效率。 三，用j a v a 语言，面向对象构件的方式实现，提高程序的内聚性和扩展性。并 且构件的方式适合集成到目前的应用环境。用j a v a 实现也容易通过网络获得数 据。 第一章绪论 第一章绪论 本文所研究的内容是自然理解中比较普遍的要解决的问题，即：分词，聚类。 和之后的建立语义空间。在分词，聚类和建立语义空间方面，国内外有了很多的 研究。 分词方面的研究成果有中国科学院研制的基于层叠隐马尔可夫模型的分词 模型( c a s c a d e dh i d d e nm a r k o vm o d e l ，h m m ) 。1 1 j 并且有了一个基于上述理论的 产品i c t c l a s 。还有其他的一些分词模型。比如基于互信息的分词模型，等等。 在自然语言处理的研究中词聚类算法也是被广泛研究的课题。由一些语义相 近的词组成的词类或词聚簇可以看成是纷繁的个别词现象到语言的一般概念的 映射。而这些概念是更加本质的，更具有一般性和稳定性。词聚类对语音识别智 能检索等许多自然语言处理领域均有实用价值。其理论也比较多，包括互信息聚 类，最小近邻聚类方法等。 由于分词是聚类的前提，所以程序的分词是在聚类之前完成，但是由于他们 互不相关，所以前文分词的统计信息在后面的聚类中无法使用。而且聚类的效果 很大程度上取决于分词的好坏。这其实是一个统一的过程。因此如果模型相似则 可以统一这两个过程。 本文的主要工作是选择一种合适的方式统一分词聚类过程，并且用聚类后的 词表建立语义空间。其中主要工作是分词，聚类的处理方法选择。因为，分词是 个分类的过程，聚类刚好相反。本文选择互信息作为统计信息进行分词聚类，统 一了统计信息的选择，使用支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) i l j 作为 分词聚类的主要工具，解决了这个统一解决的难题。 1 1 项目研究的背景和意义 在针对中文的自然语言理解中，首先要解决的问题就是分词，因为和符号语 言不同，汉语是基于语义的语言，在理解的过程中分词，而计算机目前只能独立 的进行分词，然后做后续的理解工作。分词在语言理解中占有重要的地位，也为 后续的词聚类，语义理解等应用做好铺挚。基于统计的分词方式是一种快速的分 词方式，不依赖于大语料词典，其实质是一种模式识别问题：即根据词的互信息 1 1 j 进行模式识别。 汉语自动分词是中文信息处理的“瓶颈”问题，它的最终解决依赖于汉语的 分词结构、句法结构、语义等语言知识的深入系统的研究：依赖于对语占与思维 的本质的揭示；同时，在很大程度上还依赖于神经网络、专家系统、知识工程等 天津。1 i 业人学硕十学位论文 人工智能技术的研究进展。计算机技术是汉语自动分词的技术基础，计算机技术 发展的每一次巨大飞跃都是汉语自动分词的福音。因为自然语言理解既是人工智 能研究领域需要解决的重大课题，也是汉语自动分词研究的重要内容。因此，汉语 自动分词研究的发展同时也寄希望于人工智能技术的突破。 如果说分词是自然语言理解的前提那么词聚类就是分词后的一个最首要的 应用。因为分词的结果只是对文章的一个粗分的过程，只有将相同类的词进行合 并，才能更好的继续使用。这就更接近于我们人类的思维方式和对于词语的使用 方式。词语的聚类对于分词后的排岐有着很大的帮助，再精确的分词也会有歧义， 因为分词只是对于文章的初步理解，而聚类后，则大大解决了这个理解歧义问题。 在分词，聚类后建立语义空问则减小了语义空间的维数1 2 j ，提高了语义空间 模型对于语义理解的准确性。既降低了程序的运算代价也提高了运算精度，取得 了不错的效果。 1 2 分词聚类理论的理论基础 分词聚类的方法目前主要是通过统计方法进行。因为词语尤其是汉语的一次 多义现象，单纯的使用词典是不会太多帮助。如果对于每个词都查词典进行切分， 则歧义的切分需要将这些不同的词义组合起来考虑，在没有对文章有一个比较深 入的理解前，这是不可能做到的。统计信息则在此时能够起到很大帮助，因为一 个词在一个解释下的上下文应该是比较稳定的。因此通过信息论和模式识别的方 法，就可以进行分词聚类。 模式识别、函数拟合及概率密度估计等都属于基于数据学习的问题，现有方 法的重要基础是传统的统计学，前提是有足够多样本，当样本数目有限时难以取 得理想的效果。v a p n i k 等人提出的一种小样本统计理论：统计学习理论( s t a t i s t i c a l l e a r n i n gt h e o r y ) ( s l t ) ，着重研究在小样本情况下的统计规律及学习方法性质。 s l t 为机器学习问题建立了一个较好的理论框架，也发展了一种新的通用学习算 法：支持向量机( s v m ) 。 概括地 兑，s v m 就是首先通过用内积函数定义的非线性变换，即核函数方 式，将输入空问变换到一个高维空间，将在原空间中线性不可分的问题变成线性 可分，在这个空间中求( 广义) 最优分类面。s v m 分类函数形式上类似于一个神经 网络，输出是中间节点的线性组合，每个中间节点对应一个支持向量。它在解决 小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用 到函数拟合等其它机器学习问题1 2 1 。目前，s v m 已经成为困际上机器学习领域 的新的研究热点并已经被应用于人脸识别、文本分类、手写识别等领域。 本文正是通过对s v m 的研究，根据s v m 的分类特征，对样本输入的要求， 2 第一章绪论 核函数与参数进行选择。并且在对支持向量机分类时出错样本点的分布进行研究 的基础上，考虑将支持向量机与其它分类方法进行结合，如与最近邻分类( 州) i j j 等分类算法进行结合，形成一种具有更高分类准确率的分词器。同时可以较好的 解决应用支持向量机分类时核函数参数的选择问题，能较广泛的应用在各个不同 类型的文章中，取得较好的分词效果。本文建立了分词聚类一体化模型，对分词 时生成的统计信息进行保留，用于聚类。因为汉语中类的数量远远小于词的数量。 比如：“然而一，“但是”，都是表示转折，在语义理解中他们表述的意义相同，上 下文的结构也相同。这时，通过统计互信息的方法将它们聚类，作为一个元素建 立语义空间，这样不仅语义空间的维数会有很大的降低，建立速度会快很多，更 重要的是，这已经对文章有了一个初步的理解，对于查询会有很大的帮助。本文 中聚类的方法也是使用支持向量机，降低了系统的复杂度，而且分词时的信息继 续可以使用，提高了效率。 本文中，我们将分词，聚类的结果应用到全文检索中。全文检索是目前新出 现的一种精确检索方式，即先根据分词，聚类的结果，建立语义空间。将文中的 出现的词和文章建立相关矩阵，用于对外部查询的匹配。对于外部的查询方式进 行全文语义空间匹配，以求浅层次的理解文章，获得比较好的查询结果。由于分 词系统的不成熟，一般在没有分词的条件下只能按字建立索引进行查询，这样的 匹配度很差，只能按照关键字索引，如何输入的查询语句增加则对于查询结果没 有太多的帮助，有时候反而会起到反作用。在分词后，就可以根据分词建立词索 引( 如果聚类就更好) ，语义空间的建立会更加准确，全文检索的准确率会有大 的提升。 1 3 分词聚类的研究应用现状 1 3 1 分词聚类研究应用现状 关于中文分词技术的研究，虽然海内外已有十年的研究历史，付诸的努力很 大，取得的成绩也很多( 己建立的分词系统，中国大陆、台湾、香港及新加坡合 计2 0 个以上1 ，但迄今为止并无真正成熟的实用系统面世，成为，哐重制约中文信 息处理发展的瓶颈之一。因此也迫切需要中文分词技术有进一步深入的研究。汉 语分词是中文信息处理系统的基础，有着极其广泛的实际应用。比如在输入系统 中的应用，我们目前的输入法输入中文的速度在有了分词的帮助后有了巨大的提 高。再比如在搜索中的应用，目前我们使用的搜索引擎就是基于关键词的查询， 匹配，返回需要的结果。 词的聚类的应用不像分词那么醒目，但是它在以下的很多方面都有重要的作 3 天津l ：业人学硕+ 学位论文 用。 1 ，在统计语言模型中，词的聚类是解决数据稀疏问题的主要方法之一，由 于类的数量远远小于汉语中词的数量，因此基于类的n 元模型大大缓解了基于词 的模型所遇到的数据稀疏问题。更进一步，因为类的数量少，使得统计n 大于3 的高阶模型成为可能1 4 1 。 2 ，在语义理解中，不管是统计方法进行语义理解，还是采用逻辑的方式进 行语义理解，词聚类都可以减小分词的数量，提高语义模型的效率和准确性。 因此，几乎所有使用分词的领域都要对分词的结果进行聚类分析或者处理。 聚类的方法主要有： 1 ，基于贪婪原则传统的统计聚类方法，以语料的似然函数或困惑度作为判 别函数。这种传统方法的主要缺点是聚类速度慢，初值对结果影响大，易陷入局 部最优。 2 ，目前比较新的算法有分层聚类算法，它基于词的相似度，词集合的相似 度，自下而上，能得到全局最优的结果。实验证明它的聚类效果明显好于传统的 聚类算法。 1 3 2 分词聚类使用的数据结构 建立语义空间时用到的数据结构是倒排索引1 4 l 。根据索引方法的不同，倒排 索引可以分字索引和词索引。这两种不同的索引方法适用于不同的场合，字索引 的优点是不用分词，建立速度快，维护方便，一般用于查找，或者简单的关键字 匹配搜索。本文选择的是词索引，它的建立依赖于分词结果，正好可以和分词结 合使用以验证和查看分词的效果。 一个完整的倒排表通常由两部分组成，如图1 - 1 所示： ( 1 ) 索引头：是一个一维数组，以字符内码为下标，记录各个字符的索引在 索引体中的开始位置。 ( 2 ) 索引体：图中的索引体示意图仅为方便理解，实际的索引体是示意图中 的各行数据一次首位链接形成的一维数据流。 图1 2 中的每一行存放一个字符c i 的索引数据，其结构为： d o c i l ，n u m i l , p i 1 1 ，p i l 2 9o 9 p i l t ， d o c i 2 ，n u m i 2 ， p i 2 1 ，p i 2 2 ，p i 2 t ， d o c i j ，n u m i j ， p i j l ，p i j 2 ，p i j t 。 其中假设有m 个文档，d o c i j 表示含有字符c i 的文档号( 0 j m ) ，n u m 日表示在文 档d o c i i 中字符c i 出现的次数，即字频，表示在文档d o c i j 中字符c i 出现的第 t 个位置，构成一个位置序列。 由于每个字符的索引数据的长度是不同的，因此需要索引头中的指针来指出 丌始位置。 4 第一章绪论 倒排索引的建立除了用来建立语义空间外，其主要是建立一个以关键词为搜 索元素的搜索程序。然后用这个检索程序和语义空间的检索程序比较，或者和用 字建立的倒排索引比较，对他们的性能进行有比较的评测。 检索时，设待查字符串为c 1 ；c 2 ；c i ；g ，首先通过索引头定位各字符 的索引数据，然后对数据进行分析：若c l c r 的索引数据中均含有文本t 的索 引记录，在r 个关于文本t 的索引记录中又含有p i ，p 2 ，p r ( p i 属于字符c i 的索 引数据) 。且p i 和p i + l ( o 啦n 】 b ，a ) = 丢w w - a 嘲w x i - b ) _ 1 ) 公式( 2 1 2 ) 公式( 2 5 ) 对拉格朗r 函数关于w ，b 求其最小值和a ；求其最大值。根据鞍点满足的优 化条件； 丝! 坐：垒：尘：0 ， c o b 。c o l ( w i , b , a ) ：0 撕 1 3 公式( 2 6 ) 天津r ：业大学硕士学位论文 可得： a i y i = 0 ，w = a j y i x i ，a i 0 ，i = l r l 公式( 2 - 7 ) 根据k t 条件，最优超平面的充分必要条件： a i ( y f ( 6 ) 一1 ) = 0 ，i = 1 ，2 1 由上面公式( 2 6 ) ( 2 7 ) ( 2 - 9 ) ，优化问题转化为下面对偶问题： 缈p ) = 吩一去哆口y i y “_ ) i = 1 oi = 1 公式( 2 8 ) 公式( 2 9 ) ， s t q y i = o ，口f o ，i = 1 2 一l i = 1 求解上述二次规划问题，可得系数a ii = 1 n 。所以由公式( 2 5 ) ，( 2 9 ) 得最 优超平面： y i ：e y i a i ( x ；x ) 一b 公式( 2 1 0 ) 由于大部分a ；等于零，只有少数a 。不等于零。不等于零的a ；，所对应的x ；被称 为支持向量。所以基于最优超平面的分类器为指示函数： f ( x ) = s g n ( z y i a i ( x t x ) 一b ) 公式( 2 一i i ) 2 3 2 支持向量机 支持向量机的实现是基于如下的思想：通过一个非线性映射皿( ) 把n 维样本 向量映射到高维特征空间。在这个高维特征空间中，维数足够大，使得原空间数 据的像具有线性关系。这样可以在这个空间中构造线性最优决策函数。在构造最 优决策函数时，利用结构风险最小化原则。构造最优决策函数时，要计算内积。 而支持向量机巧妙的利用原空间的核函数取代了高维特征空间中的内积运算， 即： k ( x 。，x 。) = l l ，( x ；) v ( x 。) ( 也被称为内积的回旋) ，避免了维数灾难。这样用核 实现了输入输出之间的非线性关系。所以构造支持向量机由构造线性最优决策函 数和内积的回旋两个过程组成n 1 。在这两个过程中，我们其至可以不知道映射 皿( 的具体形式。 图2 3 为特征空问中的线性学习机器结构，图2 4 为支持向量机的结构。 1 4 第二章支持向餐机 图2 3 特种空间中的学习机器结构 2 3 3 支持向量机的优点 图2 4 支持向量机结构 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理基 础上的。根据有限的样本信息，在模型的复杂性( 即对特定训练样本的学习精度) 和学习能力( 即无错误地识别样本的能力) 之间寻求最佳折衷，以期获得最好的推 广能力m 1 。支持向量机集优化分类面和最佳推广能力等特点于一身。支持向量机 方法的主要特点有： 1 支持向量机专门针对小样本情况，其目标是得到现有信息下的最优解而不仅 仪是样本数趋于无穷大时的最优值。它有坚实的数学和理论基础。 2 支持向量机算法最终将转化成为一个二次型寻优问题。从理论上说，得到的 解将是全局最优解，解决了在神经网络方法中无法避免的局部极值问题。 3 支持向量机巧妙地解决了维数问题，其算法复杂度与样本维数无关。在支持 向量机方法中，只要选取不同的核函数，就可以实现多项式逼近、径向基函数( r b f ) 方法、多层感知器网络等许多现有学习算法。支持向量机非常适合于处理非线性 问题。 1 5 天津一l ：业人学硕十学位论文 4 由于结构风险最小化原则的应用，支持向量机具有非常好的推广能力。 2 4 支持向量机算法 2 4 1 支持向量机算法 支持向量机得到了非常成功的应用。然而，训练支持向量机需要求解一个二 次规划的优化问题。对于大数据量的优化问题，二次规划的求解几乎是不可能的。 为了降低计算资源、提高算法效率、扩大应用，目前已经提出了许多支持向量机 训练算法。本节将对目前主要的支持向量机算法进行说明和讨论。 1 分割算法 2 工作集算法 3 序列最小优化算法 4 增量式支持向量机 5 p s v m 算法 其中我们重点说明的是3 ，4 ，5 3 序列最小优化算法： 对于分割算法，需要求解一个q p 问题。众所周知，得到一个数值q p 解的问 题是复杂的，并且还有很多数值精度问题需要处理。j o h n c p 1a t 提出了训练 支持向量机的一个新方法：序列最小优化算法，即s m o ( s e q u e n t i a lm i n i m a l o p t i m i z a t i o n ) 算法。其基本思想是把一个大数据量的q p 分解为一系列的最可能 小的q p 子优化问题。s m o 算法采取了一种极端的情况，即每次只对两个拉格朗 日乘子进行优化。s m o 算法可以分为两个组成部分：内环和外环。外环根据k k t 优化条件，采用启发式方法从数据集中挑选出每次要优化的数据，内环则对 l a g r a n g e 乘子进行分析求解。s m o 算法解决了对于大数据量的二次规划问题，其 优点是针对2 个样本的二次规划问题可以有解析解的形式，从而避免了多样本情 形下的数值解不稳定及耗时问题。同时在s m o 算法中，内存的需求与训练数据的 大小呈线性关系，不需要额外矩阵存储。这样，它可对非常大的数据进行训练。 由于在s m o 中没有使用矩阵算法，其对于数值精度问题不太敏感。s m o 算法要比 c h u n k 算法快很多倍。s m o l a 等人提出了s m o 回归算法。s s ke e r t h i 等人对 s m o 算法提出了改进，即在判别最优条件时用两个阐值代替一个阐值，从而使算 法更加合理，收敛更快。 4 增量式支持向量机： 对于比较大的数据集，实际的解决技巧是将问题分解为可处理的小问题来 解决。这些处理方法得到解需要多次遍历数据集。在某些情况下，样本是不断加 1 6 第二章支持向鼙机 入的，样本的数量不确定。最典型的应用是系统的在线辨识。这种情况与s m o 方 法的区别是训练样本总的个数是未知的。c a u w e n b e r g h s 提出了一种增量式支持 向量机训练算法，即考虑增加一个训练样本或减少一个样本对l a g r a n g e 系数和 支持向量机的影响，实验表明算法是有效的。增量式支持向量机学习方法的基本 思想是首先在1 个样本上对支持向量机进行训练，当一个新的样本加入时，对支 持向量机进行训练，同时保留支持向量样本，去掉非支持向量样本。增量式的学 习算法为支持向量机的训练提供了新思路。s u y k e n s 提出了一种周期最d , - 乘支 持向量机用于时间序列的预测。c a r o z z a 和x i a o 等人也分别提出了一些增量式 学习的支持向量机训练算法。 5 p s v m 算法 f e n g 提出了p s v m 算法，在p s v m 中，样本被分配到数据空间中最近的两个 平行平面，这种方法被称为正规化最小二乘。也可看作更广泛的正规化网络的推 广。其优点是：导致了非常快速和简单的算法。最后的分类器是非线性分类器的 组合，而求解这些非线性分类器只需求解一个简单的线性方程组。相比之下，支 持向量机求解二次规划，求解过程需要非常耗时的计算时间。 2 4 2 支持向量机模型选择的研究 在支持向量机方法中，选择优化的支持向量机参数是支持向量机设计的非 常关键而且不可省略的步骤。这些参数决定着支持向量机的性能，这些参数主要 有： 1 ) 正规化参数。正规化参数控制着最小训练误差和最小化模型复杂度的某种 折衷。 2 ) 核参数。核参数从某种程度上定义了高维特征空间，反映了数据的先验知 识。核参数的选取过程也是模型比较的过程。 参数的调整和模型选择是支持向量机研究领域的一个公开问题。目前已有多种 方法，各种方法各具特色。最简单的方法是借助设计者的经验进行手工调整。这 种方法虽然简单，但是过多的依赖于设计者的经验，缺乏理论基础，且得到的结 果缺乏可靠性1 。更加规则化的方法可分为三类：交叉验证和确认集的方法，基 于界的方法和统计的方法。下面对主要方法进行说明。 1 确认集，交叉验证的方法 确认集，交叉验证是一种被广泛应用的技术。确认集方法是首先定义训练集、 确认集和测试集。然后选取几组不同的j 下规化参数和核参数。用训练集的数据进 行训练，把训练好的支持向量机在确认集上进行验证，选出误差最小的支持向量 机，通过测试集进行测试。交叉验证方法是估计泛化误差的一种常用技术。在交 1 7 天津l = 业大学硕十学位论文 叉验证中，数据集被随机地分割为互相不重叠的。 k 个子集，应用k - 1 个子集进行训练，在剩下的一个子集上进行测试，这个 过程要重复k 次，每个子集都作一次测试集。交叉验证方法需要多次的重复计算， 计算量大。 l o o 方法( l e a v eo n eo u t ) 是一种极端的交叉验证方法。在l o o 中，每次只留 一个样本用于测试。其余样本用于训练，所以训练和测试的次数就是样本数。l o o 方法可以给出对期望泛化误差的几乎无偏估的估计。但这种方法计算代价比较 大。己有一些研究者做了一些工作，以提高该算法的效率。 2 vc 维界的方法 v c 维可作为函数族f 复杂度的度量，函数的v c 维表征了学习机的最大学习 能力，是学习机容量的一种度量。所以，要使训练好的学习机器具有较好的泛化 能力，需要在v c 维与训练集规模之间取得某种较好的折衷。统计学习理论对于 1 给定的样本提出推广能力的界有如下形式r ( a ) 1 + 1 时，h 直接取值l + 1 。 3 支持向量跨距的方法 v a p n i k 提出了一个新的概念：支持向量跨距。基于这个新的概念，提出了一 种新的方法来逼近l o o 方法误差的估计。这种方法的优点是，不仅提供了支持向 量机参数选择的方法，而且这种方法能反应真实的误差。 一卫一 vs m a x ( d ，1 4 c 口f + 肌) 对于l o o 方法存在着误差上界华s i 丝一上式的右边 ， l 1 称为跨距边界。s 是支持向量跨距，由于s 的计算代价较大，可用s v d 代替s ， 由于s v s d ，所以上式的右边称为逼近跨距边界。通过求上界对支持向量机的 模型参数的极值，可计算出最佳参数值。 4 统计的方法 统计的方法为模型选择提供了一种新的方法。首先，统计的方法能通过定义 输入空间上函数的先验，清晰地解释核的作用。其次，统计理论为数据建模提供 了统一的框架。s m o l a 指出支持向量机中不同核的应用可以解释为对函数空问定 义的不同先验分布。m a c k y 提出了一种贝时斯证据框架，应用于神经网络的设计， 进行网络结构参数的选择。k w o k 用证据框架讨论了支持向量机分类问题。本论 1 8 第二章支持向量机 文应用证据框架进行标准支持向量机和最小二乘支持向量机回归算法、分类算法 的模型选择和参数的调整。 2 5 支持向量机的应用 支持向量机在理论上具有很突出的优势，但与其理论研究相比，应用研究尚 相对比较滞后。随着理论的不断完善，支持向量机的应用逐渐成为各国研究者的 研究重点。目前，支持向量机算法在模式识别、回归估计、概率密度函数估计等 方面己都有应用。 支持向量机最早在模式识别中应用，因为它对于分类问题有着不同于神经网 络的解决方式，虽然它的结构和神经网络很类似。由于s v m 获得的最佳超平面能 很好的解决过学习问题，而且从理论上讲获得的是全局极点，所以它获得了很大 的关注。在分词方面的应用还刚刚开始，因为分词还没有一个很精确的描述方式， 分词的结果很大程度上有随意性，一篇文章的分词结果没有一个权威的评判标 准。目前在应用中取得比较好的结果的分词方式有基于隐马尔可夫( h m m ) 的分 词方法，它通过将分词，切分排歧，未登录词识别，词性标注等词法分析任务统 一到一个统一的分词程序中，互相协作，取得很好的效果。本文使用的向量机分 词方法可以和隐马尔可夫方式互为补充，因为h m m 方法的程序比较复杂，程序代 价较高，在歧义切分时，通过增加h m m 的层数解决切分问题。不如向量机只通过 互信息进行分词简单。 2 6 补充分类算法 通过支持向量机分词的优点是不需要包含所有语言词汇的词典，但是在分词 中，会取出一些频率很高但是并不是词的短语，比如：“这个、“之一 ，等等。 而且在检索中，真正对检索提供比较大帮助的是这样的词：一个出现频率很低的 词一旦出现在文档中，其价值应该大于其他普遍出现的词。所以，需要一个停用 词词典作为补充，将“这个”、“之一 ，之类的词从文章中去除。在根据分词结 果建立倒排词索引表的时候不需要这些高频而无用的词。因此，本文的分词检索 系统额外需要个停用词表。 1 9 第二章支持向量机在中文分词聚类中的应用 第三章支持向量机在中文分词聚类中的应用 3 1 中文分词技术 中文分词技术做为中文信息处理中最重要的预处理，是词聚类，语义理解等 其它后续语言处理的基础。而且，在全文检索，搜索引擎等领域也有重要的现实 应用。 3 1 1 中文分词的作用 词作为表达意思的最小语言单位在自然语言处理中有着重要的作用，与英文 不同的是，英语文本是已充分分隔开的词串，而汉语文本是连续字串，在书面汉 语中词与词之间没有明显的切分标志。于是在中文信息处理中中文分词这一研究 领域应运而生，并成为中文信息处理中的基础课题。把字串分隔成词串，就是中 文分词系统需要做的工作。自动识别词边界，将汉字串切分为正确的词串的中文 分词技术问题无疑是实现中文信息处理的各项任务的首要问题。 信息检索和信息摘录、自然语言理解、文本分类、机器翻译、文本校对等中 文信息处理系统同样都首先需要分词作为其最基本的预处理。中文分词系统可在 汉语分析与理解、全文信息检索、搜索引擎等各个方面起到重要的作用。但是， 关于中文分词技术的研究，虽然海内外已有十年的研究历史，付诸的努力很大， 取得的成绩也很多( 己建立的分词系统，中国大陆、台湾、香港及新加坡合计2 0 个以上1 ，但迄今为止并无真正成熟的实用系统面世。( 其主要原因是汉语理解的 特殊性：在分词的同时已经进行对文章的理解，但在目前的处理中只能先分词后 理解，分词是理解的前提条件，这导致了理解的困难) 成为严重制约中文信息处 理发展的瓶颈之一。因此也迫切需要中文分词技术有进一步深入的研究。 3 1 2 中文分词技术的应用 汉语分词是中文信息处理系统的基础，有着极其广泛的实际应用。计算机的 所有语言知识都来自机器词典( 给出词的各项信息) 、句法规则( 以词类的各种组 合方式来描述词的聚合现象) 以及有关词和句子的语义、语境、语用知识库。汉 语信息处理系统只要涉及句法、语义( 如检索、翻译、文摘、校对等应用) ，就 需要以词为处理的基本单位。例如汉字的拼音字转换、简体繁体转换、汉字的 2 1 天泮：i ：业人学硕十学位论文 印刷体或手写体的识别、汉语文章的自动朗读( 即语音合成) 等，都需要使用词 的信息。通过分词以后，在词的层面上再做转换或识别，处理的确定性就能大大 提高了。 下面就本文相关的检索领域进行说明： 在搜索引擎中，为了进行中文信息小型化，需要提取关键知识，也就是洗首 先要分隔出单个的中文词语，然后进行词频统计得到关键词。然后针对关键词建 立倒排索引。要开发中文搜索引擎，快速的汉语分词算法和可靠的分词方式是至 关重要的。尤其是目前以词为基础的，关键字匹配搜索方式的第二代搜索引擎， 比如g o o g l e ，百度纠。 搜索引擎通常由信息收集和信息检索两部分组成。对于英文，由于英文中词 与词之间是用空格隔开，检索起来很方便，故计算机采用了词处理的方式，大大 减轻了用户与计算机的工作量。相对来讲，中文的情形就复杂得多。中文的词与 词之间是没有分隔符的，因此若想建立基于词的索引，就需要专门的技术，这种 技术就是本文所研究的“中文分词技术 。例如，如果不进行分词( 按字检索) ， 当检索德国货币单位“马克”时，就会把“马克思”检索出来，而检索“华人 时会把“中华人民共和国 检索出来。如果进行了分词，就会大大提高检索的准 确率。虽然建立词索引表要比按字建立索引要慢，因为他涉及分词的代价，但是 在检索或匹配时却可以大大提高检索的效率，在进行词聚类后建立的倒排索引将 有更好的检索性能。虽然前期进行分词，聚类的代价要花一些，但是对于一个搜 索程序而言，用户的体验和最终的检索效率更重要。 3 1 3 中文分词技术的方法 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一 个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配 成功( 识别出一个词) 。 按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照 不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配；按照 是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一 体化方法。常用的几种机械分词方法如下： ( 1 ) 正向最大匹配：按照从左到右的顺序，每次从中文字符串罩取出长度为 m a x l 的子串和词典罩的词条进行匹配，如果成功则分词成功，否则，则字符 串长度减一，再与词典匹配，直到匹配成功或字符串只剩余一个汉字。 ( 2 ) 讵向最小匹配：按照从左到右的顺序，丌始从字符串晕取出2 个汉字匹 第三章支持向量机在中文分词聚类中的应用 配，如果匹配成功，则切分这个词，否则，字符串长度加一再匹配，直到匹配成 功或字符串长度超过最大匹配长度。 ( 3 ) 逆行匹配：逆行匹配也可以分为逆行最大匹配和逆行最小匹配，但是切 分汉字时，是从字符串的尾部开始进行。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向 最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹 配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹 配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为 1 1 6 9 ，单纯使用逆向最大匹配的错误率为1 2 4 5 1 6 1 ( 这可能是因为汉语的中心语靠 后的特点。) 但这种精度还远远不能满足实际的需要。 由于分词是一个智能决策过程，机械分词方法无法解决分词阶段的两大基本 问题：歧义切分问题和未登录词识别问题1 6 j 。实际使用的分词系统，都是把机械 分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的 准确率。 2 基于词频统计的分词技术 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的 次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好 的反应成词的可信度。这种技术发展到今已经有许多不同的统计原理，例如其中 的互信息原理就是可以对语料中相邻共现的各个字的组合的频度进行统计，计算 它们的互现信息。定义两个字的互现信息为：i = l o g i p ( x ) p ( y ) p ( x y ) 】，其中p ( x y ) 是汉字x ，y 的相邻共现概率，p ( x ) ，e 0 0 分别是x y 在语料中出现的概率。 互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时， 便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统 计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。基于词频的统 计分词的最大优点是不需要词典直接利用统计信息就可以分词，省去了词典的维 护；但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的 常用字组，例如“这一”、“之一、“有的”、“我的 、“许多的等，并且对常用 词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分 词词典( 常用词词典) 进