（计算机应用技术专业论文）基于粒子群算法的web文本信息过滤研究.pdf

?蕈，j浮ilji j毒擎薹_ 1 ， i 声，明尸，明 l i i ii l lii i l l l l l l l l l1 1 1 1 1 1 1 1 1i i i 哪 y 17 8 5 5 7 1 本人郑重声明：此处所提交的硕士学位论文基于粒子群算法的w e b 文本信息过 滤研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和 取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：三圭日期：竺! 丝：! ：7 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：王圣导师签名： 日期：丝! ! ：! ：2日期：垫! q ：兰：! o 弋 生 b丫 、 、 t；ilt7l，#譬o譬，p詹嚣黔 盘0 、 | ， 、 ，。l怎 ： ，。l j 、 i l f r 、 、 a b s t r a c t p a r t i c l es w a r mo p t i m i z a t i o ni san e wk i n do fe v o l u t i o n a r yc o m p u t a t i o n i nt h i s p a p e rw ef i r s ts t u d yt h ec h i n e s ew o r ds e g m e n t a t i o na n dt e x t f e a t u r e ss e l e c t i o n t e c h n o l o g i e s ，a n da n a l y z et h ep r i n c i p l e sa n db a s i cs t e p so ft h e s et e c h n o l o g i e s a s w e l la ss o m ec o m m o na l g o r i t h m s m o r e o v e r ，s o m er e l a t e da l g o r i t h m sa r ei m p r o v e d a c c o r d i n gt ot h ec h a r a c t e r i s t i co ft h i sp a p e r t h e nw ea n a l y z et h ep s oa l g o r i t h m ， i n c l u d i n gt h ei n t r o d u c t i o n 、p r i n c i p l e s 、b a s i cs t e p s 、a p p l i c a t i o np r o c e d u r e sa n d p a r a m e t e rs e t t i n g ，e t e i n e r t i a lf a c t o ra n dc o n v e r g e n c ef a c t o ra r ei n t r o d u c e dt ot e s t t h eo p t i m a lc a p a c i t yo ft h ea l g o r i t h mi nt h ee x p e r i m e n ta n dt h ee x p e r i m e n t a lr e s u l t s a r ea l s oa n a l y z e d w ed e s i g nap s oc l a s s i f i e ra c c o r d i n gt ot h ec h a r a c t e r i s t i co fp s o a n dt h e m i n i n g m e t h o do fc l a s s i f i c a t i o n r u l e s ，a n da p p l y t h ec l a s s i f i e rt o i n f o r m a t i o nf i l t e r i n g r e s u l t ss h o wt h a tt h i sp r o p o s e dc l a s s i f i e rp e r f o r m sw e l lw h e n f i l t e r i n gi n f o r m a t i o n t h u sw ec a np r o v et h a tp s oi sp r o m i s i n gi nt e r m so f f e a s i b i l i t ya n dv a l i d i t yo fi n f o r m a t i o nf i l t e r i n g w a n gd o n g ( c o m p u t e ra p p l i e dt e c h n o l o g y ) d i r e c t e db yp r o f c h e n gx i a o r o n g k e yw o r d s ：p s o ，c h i n e s ew o r ds e g m e n t a t i o n ，t e x tf e a t u r e ss e l e c t i o n ， c l a s s i f i e r , i n f o r m a t i o nf i l t e r i n g - v 0 、静 华北电力人学硕十学位论文目录 目录 中文摘要 英文摘要 第一章引言l 1 1 课题背景及意义1 1 2 国内外研究动态“2 1 2 1 文本信息过滤的国内外研究动念2 1 2 2 粒子群算法应用的国内外研究动态3 1 3 本文主要研究工作3 第二章关键技术研究4 2 1 中文分词技术4 2 i 1 当| j i r 中文分词中遇到的问题4 2 1 2 常见分词算法一4 2 1 3 本文所用的分词算法6 2 2 文本特征选择1 0 2 2 1 词语抽取l o 2 2 2i q 断词处理一1 0 2 2 3 特征选择算法1 1 2 2 4 常用特征选择算法1 3 2 2 5 特征权值的选取1 8 2 2 6 一种特征权值的计算方法2 0 2 3 粒子群算法2 1 2 3 1 群智能概述：2 1 2 3 2 群智能计算：2 2 2 3 3 基本粒予群算法：2 3 第三章基本粒子群算法的改进2 9 3 1 引入惯性因子2 9 3 2 引入收敛因子2 9 3 3 中值粒子群算法3 0 3 4 基于科一群模式结构的方法3 1 华北电力人学硕十。何论文日录 3 5 基于种群熵的白适应粒子群算法3 2 3 6 离散粒子群算法3 3 3 7 粒子群算法改进以及实验分析3 4 3 7 1 时变权值的变化对优化效果的影向3 7 3 7 2 时变权值递减率对优化效果的影响一3 7 3 7 3 种群大小对惯性权值选择的影响3 8 第四章改进粒子群算法在文本w e b 信息过滤中的应用4 1 4 1 信息过滤总体流程4 l 4 2 粒子群算法的分类规则挖掘4 2 4 3 粒子群分类器设计4 4 4 4 粒子群分类器在w e b 文本信息过滤中的应用一4 6 4 5 实验以及数扒分析4 8 第五章总结与展望5 0 5 1 论文的总结5 0 5 2 工作展望一5 0 参考文献5 2 致访j 5 7 在学期间发表的学术论文和参加科研情况5 8 华，i l 电力人。：硕十学位论文 1 1 课题背景及意义 第一章引言 随着网络的同益普及和信息化技术的发展，因特网已经成为我们学习和工作中 必不可少的工具，在我们的社会生活中扮演着越来越重要的角色。快速发展的网络 规模和网络技术一方面给计算机用户带来了丰富的信息资源和便利通信服务；另一 ，方面也使计算机用户经常被淹没在浩瀚的信息海洋中而无所适从。另外，由于缺乏 传统媒体对网络中信启、发布的有效监控，本应受到严格管制的信息大量泛滥，从而 导致广大计算机用户被信息过载、信息污染等问题严重困扰着。 目前解决这个矛盾的方法一般有两种，信息检索和信息过滤。信息检索技术是 根据用户的查询返回合适的信息，它在一定程度上解决了信息过载的问题，但由于 其通用的性质，不能满足不同背景、不同目的和不同时期的查询请求。而信息过滤 技术能够根据用户个人一贯的兴趣向用户主动提供与其兴趣相关的w e b 信息，屏蔽 那些不为用户喜欢的信息或过滤掉敏感性信息( 如国家安全、暴力、色情和反动信 息等) ，从而节约用尸。获取信息的时间。信息过滤技术既能实现有用信息推荐，又 能实现有害信息的过滤，因而是帮助用户从信息过载和信息污染中解脱出来的最有 效的方法。 文本信息过滤属于信息过滤的一个分支，它主要是根据因特网上信息表现形式 大多为文本的方式，将信息过滤技术应用于其上，依据用户的信息需求模型，在动 态的文本流中，搜索j ：日户感兴趣的文本。文本信息过滤包括将用户感兴趣的信息从 动念文本流中抽取出来或者将用户不感兴趣的信息从中剔除。文本分类作为信息过 滤等领域的技术基础，有着广泛的应用前景。 粒子群优化( p a r t jc a ls w a r mo p t i m i z a t i o n p s o ) 算法是近年来发展起来的 一种新的进化算法( g v o l u t i o n a r ya 1 9 0 r i t h m e a ) 。p s o 算法属于进化算法的 一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适 应度来评价解的品质。但是它比遗传算法规则更为简单，它没有遗传算法的“交叉” ( c r o s s o v e r ) 和“变异”( m u t a t i o n ) 操作，它通过追随当自，j 搜索到的最优值来寻 找全局最优。 因此，本文尝试迎过将粒子群算法应用到w e b 文本信息过滤中，提高对文本信 息的过滤准确性和适应性，提高网络的安全与稳定性，以及丁f 常使用有着非常重大 的意义。 华北电力人学硕十学位沦文 1 2 国内外研究动态 1 2 1 文本信息过滤的国内外研究动态 近年来，信息过滤理沦的研究与技术应用不断成熟与完善，其他领域中的许多 技术，比如自然语言处理技术，信启、检索中的相关反馈和查询扩展优化技术，文本 分类和聚类技术以及机器学习、粒子群算法和神经网络技术都被用的信息过滤与识 二 ， 别的研究中来，并且也取的了良好的效果。 国内学者通过一螳研究巧把自然语言，人工智能技术，语言学等方面原理引 入到文本过滤中以提高过滤系统的性能和精度。 但是，国内文本数据分类研究起步较晚，始于2 0 世纪8 0 年代初期。我国文本 分类的研究大体上经历了可行性探讨、辅助分类、自动分类系统三个发展阶段。早 期对中文文本的分类研究较少，采用的技术也主要是把英文文本分类的技术应用到 中文文本分类当中。自一h 世纪9 0 年代后期刁丌始着重于对中文文本分类的研究， 结合中文文本的特点，形成中文文本数据分类研究体系。 而国外对文本信息过滤研究技术却很早就丌始了。s t a n f o r d 大学的t a kw y a n 和h e c t o rg a r c i a - m o l i n 3 丌发的基于内容的过滤系统s i f t ，使用向量空间模型来 实现用户信息需求与新闻资料之i 日j 的匹配。n e w s w e e d s ( 新闻组过滤系统) 。”用机器 学习算法创建用户兴趣模型，使用评估过的文档训练识别与过滤系统。c l f s 、 i n t e l i a g e n t 1 等采用遗传算法( g a ) 和分类系统加强过滤系统的学习能力，通过尽 可能多地学习有关用户模型的新数据，在用户尽可能少直接参与的情况下优化用户 模型。新闻组阅读过滤系统b r o w s e m l 采用神经网络模型来对文章的相关性进行等级 划分，然后根据阈值进行识别与过滤。 在文本数据分类的研究方面，l u h n 在2 0 世纪5 0 年代术就对这一领域进行了开 创性的研究，他首先将词频统计的思想用于文本数据分类中 1 。1 9 6 0 年m a r o n 、k u h n 在j o u r n a lo fa c m 上发表了有关文本数据分类的第一篇论文“o nr e l e v a n e e ， p r o b a b i1 i s t i ci n d e x jn ga n di n f o r m a t i o nr e t r i e v a l ”1 。1 9 6 3 年b o r k o 等人提 出了利用因子分析法进行文献的自动分类m 1 。其后许多学者在这一领域进行了卓有 成效的研究。目的所说的文本分类主要是指基于机器学习的文本分类，本文也主要 是对基于机器学习的自动文本分类技术进行研究。所谓机器学习是指由计算机代替 人辣学习关于认识世界、改造世界的知识。 目的，文本分类方【 的文献也非常丰富，常见于信息检索、机器学习、知识挖 掘与发现、模式彭i 别、人工智能、计算机科学与应用等各种国际会议及相关的期刊 或杂志。目前至少有两种国际杂志出版文本分类方面的专辑州引。比较有代表性的 2 华北电力人学硕十学位论文 综述文章有s e b a s t i a n i 的“m a c h i n el e a r n i n gi na u t o m a t e dt e x tc a t e g o r i z a t i o n 和a a s 的“t e x tc a t e g o r i z a t i o n ：as u r v e y ”n 引。另外，j o a c h i m s 还出版了文本 分类方面的第一本专著“l e a r n i n gt oc l a s s i f yt e x tu s i n gs u p p o r tv e c t o rm a c h i n e ， m e t h o d s ，t h e o r ya n da l g o r i t h m s n 引。国内也于2 0 0 5 年召开了第一届中国分类 技术及应用学术会议。 t 1 2 2 粒子群算法应用的国内外研究动态 在文本信息过滤领域中，有应用b p 神经网络的，遗传神经网络的，近年来应 用遗传神经网络的较多，但是，遗传算法的编程实现比较复杂，首先需要对问题进 行编码，找到最优解之后还需要对问题进行解码，另外三个算子的实现也有许多参 数，如交叉率和变异率，并且这些参数的选择严重影响解的品质，而目前这些参数的 选择大部分是依靠经验。1 9 9 5 年e b e r h a r t 博士和k e n n e d y 博士提出了一种新的 算法：粒子群优化( p a r t i c a ls w a r mo p t i m i z a t i o n p s o ) 算法。目前国内已经将粒 子群算法应用到了许多领域。 同遗传算法比较，粒子群算法的优势在于简单容易实现并且没有许多参数需要 调整。目前己广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算 法的应用领域。利用神经网络与粒子群算法的学习与进化的能力，提高信息识别与 过滤的准确度和适应性。 1 3 本文主要研究工作 本文研究的内容是粒子群算法在信息过滤中的应用问题。根据w e b 信息过滤的 一般过程及其特点和粒子群算法的应用领域，在对信息过滤的过程进行分析与研究 后，对粒子群算法进行一定的改进，将其应用在信息过滤中。 因此本文的主要研究内容有： ( 1 ) 文本分词的分析与研究，歧义词识别的研究。 ( 2 ) 特征提取得分析与研究。 ( 3 ) p s o 算法原理、基本步骤及特性分析。 ( 4 ) 对惯性权值使用测试测试进行试验，分析其改变对算法寻优的影响。 ( 5 ) 将p s o 算法应用在兴趣模型的优化。 3 华北电力人学硕十学位论文 2 1 中文分词技术 第二章关键技术研究 现在很多信息的交流都是以文字形式进行，在中文的文本中，都是由一个个字 所组成，字是组成文本的一个最小单位，但很多字并不能表征太多的语义。词是由 组组成的，有一个个具体的实意，由一个个词组成句子，再由句子组成段落，最后 构成了文章。但是句子都是字符串，每个词之间并没有明显的分隔符，所以需要对 其进行分词，将字符串分隔成一个个词串。 2 1 1 当前中文分词中遇到的问题 尽管现在中文分词技术相比原来有了很大进步，但是仍然面临一些问题。 1 歧义问题 这类问题主要是因为汉语词意表达的多样性，以及字和字之间搭配的灵活性， 还有现在网络技术的不断发展，新词语层出不穷，一部分旧有的词语有了新的含义， 这都造成了词语的歧义问题。 现如今构成形式上，歧义字段可以有以下的两种形式啪1 ： 交集型歧义字段：在一个字段a b c 中，若a b d 且b c e d ，那么a b c 就是交集型 歧义字段，其中的a 、b 、c 为字串，d 为词表。 组合型歧义字段：给定任意的字符串a b ，它满足：a b d 、a d 、b d ，其中 d 为词表；切分词a b 和i a ii b i 在文本中出现过，则为组合型歧义字段。 2 未登录词识别 未登录词是指在分词系统中词表所未收集的词。现在不断涌现的新词语，以及 老词新用，还有新出现的一些人名，地名，以及各种各样的衍生词等等，在建立词 表时很容易有疏漏，而分词系统主要是依靠词表来进行分词，所以很容易带来分词 错误，造成严重后果，而且容易造成一些新的歧义。 2 1 2 常见分词算法 1 逐词遍历分词算法 这个算法可以描述为：首先将字段切分，然后把每一个切分段与词库中的词进 行比较，如果匹配则分词成功，否则重新对字段进行切分。 在一些文本挖掘的分词技术中，这属于基于词库的分词算法，它的萨确性更多 4 华北电力人学硕十学位论文 的依赖于所建立的词库。这就要求词库应具有较高的完备性和完全性，但是现实中 建立一个满足这两个条件的词库有很大的难度。所以，在中文分词中，由于词库对 某些重要词汇收集的疏漏而很容易导致分词效果的不理想，分词内容的不准确乜。 2 基于字符串匹配的分词方法2 2 1 这种方法就是机械分词方法，它是按照一定的策略将那些待分析的汉字串与词 库中的词条进行匹配，若词库中有这个字符串，则匹配成功，可认为识别出一个词。 按照扫描方向的不同，有正向匹配和逆向匹配；按照不同长度优先匹配，可以分为 最大( 最长) 匹配和最小( 最短) 匹配；按照是否与雌性标注过程相结合，又可以分为 单纯分词方法和分词与标注相结合的一体化方法。 目前常用的分词方法主要有下面几种： ( 1 ) 正向最大匹配( m m ) ( 2 ) 逆向最大匹配( r m m ) ( 3 ) 最大概率法 但是机械匹配法的精度不能满足实际的需要，无法有效的解决分词阶段的两个 基本的问题：歧义切分词和未登录词识别问题。在实际使用的分词系统中都是将机 械分词作为一种补充手段，需要进一步对算法进行改进或者利用其他的一些方法来 提高分词的准确率。 3 基于理解的分词方法 在分词系统中，一部分是在分词阶段消除分词歧义现象，而另一部分是在后续 过程中解决分词的歧义问题。基于理解分词方法的基本思想就是在分词的同时进行 句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分： 分词子系统、句法语义子系统和总控部分。在总控部分的协调下，分词子系统可以 获得有关词、句子等的句法和语义信息来对分词歧义进行判断，类似于人对句子的 理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼 统、复杂性，难以将各种语言信息组织成机器可直接读取的方式，因此这种方法还 处在试验的阶段。 4 基于统计的分词方法 这种方法先建立一些训练语库，然后利用上下文中相邻字同时出现的次数，次 数越多，则越有可能是一个词，根据字与字相邻出现的频率或概率，设定一个阈值， 从而反映它们构成词的紧密度。但是这种方法一方面是依赖于训练词库，绝大部分 是通过组合一些句段啥的来构成训练语库，不具有广泛性，另一方面，较多的依赖 于算法，而没有考虑一些语义等信息，过分的强调统计结果，而且有可能抽出一些 s 华北电力人学硕十学位论文 共现频度高但并不是词的组合，例如“那些个”、“它的 等等。所以在实际应用中 经常会使用一些常用的分词词典，然后利用统计的方法来识别一些新的词。 5 基于神经网络的分词方法 这种方法主要是利用网络的输入和输出对应的关系，进行网络训练、学习，然 后对输出结果进行解释。 可以利用神经网络进行分词的目的就是要使网络能够学习到歧义字段所包含 的各种不同的语法规则，当句子中再次出现符合同样语法规则歧义字段时，网络能 够做出正确响应。 但是这种方法利用神经网络b p 学习算法进行分词，b p 算法存在收敛速度慢、 易陷入局部最小等缺点，严重妨碍了分词速度。 2 1 3 本文所用的分词算法 1 使用的算法 鉴于对上面各种算法的综合考虑，选用最大正向匹配算法，对其进行改进，使 其能够找到句子中未被匹配的字数最少的单词组合，也就是句子，若未被匹配的字 数相等时，则观察匹配单词数最多的句子，若同样数最多，则取顺序上考前的组合。 2 使用此算法的目的 在平时对资料阅读的过程中，有一些字段有不同的歧义，因个人理解的差异， 导致人们对其理解的偏差。前面也已经提到，歧义字段主要有交集型歧义字段和组 合型歧义字段，其中已交集型歧义字段较为常见1 2 2 1 。比如“学生会工作 ，因为“学 生会一、“会 、“工作 在词库中均有。还有“骑马上坡 ，其中“骑马 、“马上 、 “上坡 也在词库中均有。它们均属于交集型歧义字段。当出现歧义时，用逆向最 大匹配法来解决。 在分词中还有一个需要注意的地方是未登录词的识别。未登录词一般是指词库 中未收录的词，一般经常较多见得是人名、地名、专有名词，如“皇家马德里 、“曼 联 、“湖人 。还有一些新兴出现的网络词语，比如“打酱油等等。由于词库的 更新不可能时时刻刻保持，总是一段时白j 整理一次，所以需要对这些词语利用相关 算法进行未登录词的识别。 3 分词的实现 。 分词系统的目的虽然是以分词为主，但是，它的结果应该也是为某个具体的服 务来应该用的。根据本文的目的主要是查找那些有害的信息资源，所以主要是要找 到文档中决定文章主题和些表达确切含义的词语是否违禁，因此主要是切分出那 6 华北电力人学硕+ 学位论文 些主题词和可能的违禁词。根据这个前提，对切分的精度要求也就不可能非常高。 在本文中，采取逆向最大匹配法进行句子的扫描，利用基于词典和统计的方法进行 分词，所以词典的选择很重要。参考了能搜集到得众多资料，包括从网上找到的一 些常用词库，加上了一些自认为现在比较流行的网络词汇，综合建立了一个词库。 因为有些词是英文的，也相应的建立了英文词库，但是由于这方面的词库资源有限， 仅仅是将一些现成的词库进行归类整理。 1 ) 预处理 在一个句子中j 有一些固有名词，如何在句中找到所有可能的固有名词，比如 专有名词，特殊组合词语等，特别是中文名，由于中文博大精深，单是姓就有好多 好多，而且名中也有很多意思迥异的组合，特别是放在文中，更是与前后词语形成 了各种可能的歧义，所以，需要对这些词语进行预处理。本文采取姓氏匹配的方法， 先找到姓氏，然后根据常见的单字中文名和双字中文名来进行匹配。由此本文收集 了一些字典，有s i n g l e n a m e t x t ，d o u b l e n a m e t x t ，其中，s i n g l e n a m e t x t 是指一些常见 的单字名、姓以及复姓，比如，李，张，诸葛，慕容等等。d o u b l e n a m e t x t 是指名 中的双字名。 比如乔峰韦小宝，其中，“乔”、“韦”是姓，而“峰 以及“小宝”是名，其 中的“峰”是一元单字名，而小宝是双字名。 这样处理后的结果就是乔峰韦小宝。 2 ) 歧义字段的处理 歧义字段在文本中普遍存在，是不可避免的现象。歧义是由于一个词具有多个 意义，在不同场合的时候体现不同的意思。对歧义切分字段的处理能力，会直接对 最终分词的精度产生影响。因此，如果只是机械的进行分词，其精度很有限，不能 满足中文信息处理高标准的要求。 根据前面的叙述，歧义字段主要分为交集型和组合型，这是从待切分字段的构 成形式上看的。另一方面，由于词的划分是根据词典来识别与区分，所以又可以分 成具有确定分法的歧义字段和具有不确定分法的歧义切分字段。 例如，“开发出”，这是个交集型字段，有两种切分的方法，一种是“开发出 ， 还有就是“开发出9 9 9 很明显第二种是不合逻辑的，所以只能唯一的切分成“开发 出 。还有很多类似的词语，它们属于第一类，具有确定分发的歧义字段。再如，“学 生会采取行动 ，这个既可以切分为“学生会采取行动”，又可以切分为“学生会 采取行动”，这两种切分的方法在语义上，还是在语法上均正确，所以不能确定出 哪一种分词形式正确，因而它属于不确定分法的歧义切分字段。 7 华北电力人学硕十学位论文 本文中，一方面，增加歧义词表和规则等知识库，另一方面，对于歧义字段采 用逆向最大匹配法进行扫描，对未匹配数进行统计，选出最优组合，改进分词结果。 通过大量的语句分析，发现一个歧义切分字段进行分词时，如果被拆开的词语 尽量少的话，往往分词后会更为准确。 比如，“文化工作者”，可以切分为“文化工作者 ，也可以“文化工作者 ， 还有“文化工作者 ，很显然，第三种的切分词是准确的。由于一个句子有很多切 分的方法，如何找出最优的组合对于切分是否准确是十分重要的。 本文中，引用了统计的方法，对所有可能切分结果进行统计，利用博弈树的方 法，选出最优结果。首先参考未匹配字数，选取未匹配字数最少的切分组合，若未 匹配字数相同，则选取匹配单词数最少的组合。若匹配单词数也相同，则选取切分 组合更靠前的组合。 在此，用例子“山西省山西药店 利用逆向最大匹配法进行扫描，得到几种不同的切分结果。 切分组合1山西省山西药店匹配单词数3 ，未匹配字数0 切分组合2山西省西药店匹配单词数2 ，未匹配字数1 切分组合3山西省药店匹配单词数2 ，未匹配字数2 很显然，第一个组合中，它的未匹配字数最少，选取切分组合1 作为最终结果。 其中，使用博弈树主要是为了找出句子中未被匹配的字数最少的单词组合。从根节 点遍历树中的节点，在每个节点判断这个节点可能产生的路径并生成其下一节点直 到叶子为止，遍历所有组合后按规则统计理想的路径。 使用逆向最大匹配扫描的方法，是根据众多文献得知，逆向最大匹配成功的概 率要高于正向最大匹配。 3 ) 未登录词的处理 未登录词泛指词组合并未出现在词典中的“新词”，包括各类专名，比如地名， 企业名，商标名，以及一些新出来的流行词语和某些术语、缩略词和新词等等。比 如，莱昂纳多将在纽约州饰演新电影，这里既有美国的人名，还有地名，等等，这 样的例子有很多。未登录词的识别处理对于各种汉语处理系统不仅有直接的实用意 义，而且是j 下确分词的基础。现如今，对于未登录词的处理主要是利用词频统计的 方法进行处理，但是若对未登录词识别不对，则会使得统计到得信息有很大误差。 就像在分词中，对地名以及人名不进行识别，就会发现一些姓，如“刘 等的频率 可能会比“如 等的频率要高，用这样的统计结果做处理结果，就大大降低了分词 的准确率。 8 另 剩 4 ) 利用博弈树，进行最终组合的选取。 将些未被词库所收录的词语碎片进行未登录词识别，将其存入l 临时词表 输出切分的结果 5 ) 试验以及分析 对以上的方法进行验证，选取网上的一些新闻片段，进行分词。与s h a r p l c t c l a s 的分词结果进行比对。 原文如下 本报9 月6 日讯山钢与同钢之间持续了近一年之久的并购大戏终于尘埃落定。 今天，山东钢铁集团有限公司与日照钢铁控股集团有限公司在同照签订资产重组与 合作协议，这标志着经历了一波三折之后，山钢终于如愿将日钢“迎娶过门”。 利用i c t c l a s 分词后的结果为 桃谨；讯l i l 南知n 郜日l f 6 之弼l f 糯7 址弛响钒蛐他的触1 并购l f 9 n 撬终于f j2 埃藩锏喇y 、谂，f _ 4 主j 囊；： 衄有限公日h 铀，。瑰茬爰| ：9 n 集卧有忪8 m 枷；湘栅赉舳重毓合作l | i i n 批，脯跏标志血着他 经砌7 l | i c 祛三蜘狮，脯垂栅终于j 燧l f 9 i 苷l6 击。锄蜘过1 舡”切硒 而用这个方法分词后的结果为 8 也晌山艄日铆拥翩了魔h 之久j 9 掬臌辫爪埃榭今天山东黼集嗍炯与日鄹黜控l i 集窭有肱 暇躺瞥谶连黼诚| 黼椭 甄1 1l 础溅ll 螅附t 碾隅蹴避籼1l tl 9 华北电力人学硕十学位论文 从上面这两个分析的结果看，均可以很好的处理。但是第一种在一些常用词上， 比如“一年一，它将其分成了“一年 。但是，在对钢铁集团这个整词的处理上，第 一种明显要分的更精确一些。还有“资产重组”，第二种方法要比第一种切分的更 精确。 可见，本文提出的算法有着一定的实际实用价值，其分词速度和准确率还比较 可以。 2 2 文本特征选择 特征选择是指从n 个特征中选择m ( m o ，由 ，竹+ 刀 + 刀 i+r 此知，其为增函数，符合设想。所以对其赋予较高的权值，使得特征项i 能够代表 类m 的特征。 对于t f i d f 方法在此类方面的不足，也有将一些特征评估函数与其进行乘积， 从而对其进行改善，这些方法可以参考文献 3 4 】 2 3 粒子群算法 2 3 1 群智能概述 群智能是一种基于生物群体行为规律的计算技术。其中的群体，是指一组相互 之间可以进行直接通信或者间接通信( 通过改变局部环境) 的主体，这些主体能够 通过合作方式进行分布式问题的求解。群智能指的是无智能主体通过合作表现出的 智能行为的特性。比如，鱼群的迁徙，蚂蚁的觅食等等。这种自然系统解决问题的 能力，要优于彼此分离的个体所组成的系统。群智能在没有集中控制并且不提供全 局模型的前提下，为寻找复杂分布式问题的解决方案提供了新的途径。 目前，群智能的应用领域已经扩展到多目标优化、数据分析、数据聚类、模式 识别、电信q o s 管理、生物系统建模、决策支持以及仿真和系统辨识等领域。群智 能方法主要有以下优点 ( 1 ) 群体中相互合作的个体是分布的，这样更能够适应目前网络环境下的工作状 态 ( 2 ) 没有中心的控制与数据，这样的系统更具有鲁棒性，不会由于某一个或者某 几个个体的故障而影响真个问题的求解 ( 3 ) 可以不通过个体之间直接通信，而是通过非直接通信进行合作，这样的系统 具有更好的扩展性 ( 4 ) 由于系统中个体的增加而提高的系统通信开销在这里很小，系统中每个个体 的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简 单性 2 l 华北电力人学硕十学位论文 采用群智能理论解决工程优化问题的过程易于实现，算法中仅涉及一些基本的 参数操作。群智能方法是一种能够有效解决大多是全局优化问题的新方法。更重要 的是，群智能潜在的并行性分析和分布式特点，为处理大量分布式存储的数据提供 了技术保证。无论是从理论研究还是从应用研究的角度分析，群智能研究都具有重 要的学术意义和现实的价值。 2 3 2 群智能计算 1 蚁群算法 蚁群世界已为人类学者和社会学者所关注，它们的组织体系和快速灵活的运转 能力始终是人类学习的楷模。蚂蚁有严格的组织分工和由此形成的组织框架，但它 们的组织框架在具体的工作情景中有相当大的弹性。比如它们在工作场合的自组织 能力特别强，不需要任何首领的监督，就可以形成一个很好的团队而能够有条不紊 的完成工作任务。 蚁群算法包括两种方法，一种是对蚂蚁群落食物采集过程的模拟，已经成功运 用在很多离散优化问题上。另一种是对蚁群聚集废弃尸体过程的模拟，主要用于数 据分析。 2 0 世纪9 0 年代，d o r i g o 提出蚁群优化算法( a c o ) 来解决一些离散优化问题臼钉n 5 1 。 蚁群优化算法设计虚拟的“蚂蚁 将摸索不同路线，并留下会随时间逐渐消失的虚 拟“信息素 ，虚拟的“信息素 也会挥发。每只蚂蚁每次随机选择要走的路径， 它们倾向于选择比较短的、信息素比较浓的路径。根据“信息素较浓的路线更近 的原则，可选择出最佳路线。由于此算法利用了正反馈机制，所以使得较短的路径 能够有较大的概率得到选择。采用概率算法，能够一定程度跳出局部最优解。蚁群 算法也曾经被成功的应用于电信路由啪删。 还有蚁群聚类算法。在蚂蚁世界里，蚂蚁能够将死亡的蚂蚁自动聚集成几堆。 d e n e u b o u r g 等人对上述现象作出了解释，并建立了基本模型h p “1 。l u m e r 和f a i e t a 将d e n e u b o u r g 等人的基本模型应用到数据分析h 2 叫引。主要思想是将待聚数据初始随 机散放在一个二维平面内，然后在这个平面上产生一些虚拟的“蚂蚁”。这些蚂蚁 的行为和基本模型中所描述的蚂蚁行为相似。不同之处在于，它们不是观察当前所 背负的物体与周围的物体是否相同，而是判断是否相似，最终能够将相似的数据聚 为一类。 2 粒子群算法 粒子群优化算法是由k e n n e d y 和e b e r h a r t 在1 9 9 5 年提出的一种基于群智能的 演化计算技术，实在鸟群和人类社会的行为规律启发下提出的。 2 2 华北电力人学硕十学位论文 粒子群优化算法通过群体中粒子间的合作与竞争产生的群体智能来指导优化搜 索。与演化计算相比，p s o 保留了基于种群的全局搜索策略，它采用的速度一一位移 模型操作简单，避免了复杂的遗传操作。粒子群算法特有的记忆，使其可以动态跟 踪当前的搜索情况，调整其搜索策略。与演化计算相比，粒子群优化算法是一种更 高效的并行搜索算法。由于算法收敛速度快，设置参数少，近年来受到学术界的广 泛重视，并且提出了许多针对控制参数的改进方案和其他改进方案，来增强算法逃 出局部极值的能力。 基本粒子群算法中，粒子群由n 个粒子组成，每个粒子的位置x ；代表优化问题 在d 维搜索空间中潜在的解。每个粒子根据它的位置，通过优化函数计算出一个适 应值f ( x 。) ，而且还有一个速度来决定其飞行方向和距离。粒子会根据三条原则来 更新自身的状态： ( 1 ) 保持自身惯性 ( 2 ) 按自身的最优位置来改变状态 ( 3 ) 按群体的最优位置来改变状态 这几条原则其实就是对应着粒子的位置和速度更新公式，如下面的公式所示： v i d = r i d + c i ( p 讨一勤) + c 2 吃( p 耐一勘) ( 2 1 ) = 劫+ i = l ，2 ，3 ，n ，d = l ，2 ，d ( 2 2 ) 其中，每个粒子i 包含一个d 维的位置向量x _ ( x ，x 渤，x ；。) 和速度向量 v i = ( v v m ，v ；。) 。粒子i 在搜索解空间时，保存其搜索到得最优位置p 。，在每次迭 代中，粒子i 根据自身惯性、自身经验p i = ( p “，p m ，p 。) 和群体最优经验 p 。= ( p 。bp 。：，p 。) 调整自己的速度向量，进而调整自身位置。学习因子c 。和c ：是非 负常数；r - 和r z 是取值介于( 0 ，l 之间均匀分布的随机数。，q 吒( p a 一嘞) 和 c 2 眨一) 分别对应保持惯性、依据自身经验和依据种群经验三条原则。先分别 计算目前位置到种群经验位置和自身经验位置的距离，再根据学习因子随机的在原 有的速度上进行调整。 2 3 3 基本粒子群算法 1 粒子群算法的发展 粒子系统是由w i l l i a mt r e e v e s 在1 9 8 3 年提出的，是一种对模糊物体的建模 方法引。这里的模糊物体是指逻辑结构难以表达，且存在动态变化的物体。例如， 火箭飞行拖着的浓烟，爆炸产生的大量碎片等等。是由多个粒子组成的集合来表达 在g a 的一种算数交叉编码中，假设两个父个体的实数编码x 。和x ：要进行算数交叉 2 4 鼍 华北电力大学硕十学位论文 操作，产生子代个体x 。和x ! ，具体交叉过程如下式所示： = 丑+ a 2 x x lx 22 + x j = 九】x 2 + 九2 x 1 ( 2 3 ) ( 2 4 ) 这里的，九：( 0 ，1 ) ，算数交叉操作通过两父代的线性混合产生两个子代。 在粒子群算法的粒子速速更新公式( 2 - 1 ) 中，若不考虑等式右侧的速度分量v 。项， 则公式( 2 1 ) 就可变成 一 v 村= c 1 1 0 耐一砀) + c 2 吃0 一x i d ) ( 2 - 5 ) 此式在某种程度上相当于遗传算法的算数交叉操作，产生唯一的子代。 再次，粒子群算法的状态更新公式( 2 - 1 ) 也与遗传算法的变异操作存在一定的 相似之处。在遗传算法中，非均匀变异，如公式( 2 - 6 ) 和( 2 7 ) 2 副，对于给定的 父代x ，若它的元素x 。被选来变异，则生成的后代的对应元素x 。= x bx 2 ，“，x 。 。 其中，x 。如下两种可能的机会变化： 吱= x + 够，u 一稚) ( 2 6 ) 或t - - x k a ( t ，吒u 一砭l ) ( 2 7 ) 上式中，磁u 和分别是x 。的下界。函数a ( t ，y ) 输出e o ，y 间的一个值，使得a ( t ，y ) 随 着t 的增加而趋于0 ( t 是代数) 。可取a ( t ，y ) 为 ( 2 8 ) 这里的r 是( 0 ，1 ) 之间均匀分布的随机数，t 为最大迭代数，b 是确定的非均 匀度的参数。将公式( 2 5 ) 与公式( 2 - 2 ) 合并，得到 x 玎= 砀+ c 1 _ ( p 耐一x 耐) + c 2 吃( p 鲥一x i d ) ( 2 9 ) 从公式( 2 - 8 ) 和公式( 2 - 9 ) 可以看出，粒子位置的更新操作在某种程度上， 可被看作是遗传算法中的变异操作，粒子根据与“两个父代”之间的距离来产生变 异操作。 粒子群算法与演化算法相比较，一个最重要的区别就是粒子的速度向量。这也 是粒子群算法的重要创新。从信息的角度看，粒子群算法通过位置和速度这两个向 量来存储信息，而传统的演化计算仅仅保留位置信息。另一个重要区别就是粒子群 2 5 华北电力大学硕十学位论文 算法的速度更新模式。在浮点编码的遗传算法中，存在着一种基于方向的交叉模式， 它采用目标函数值来确定遗传搜索的方向n6 。采用两个父代x 。和x ：交叉产生一个子 代x ( x 。和x ：编码为实数) ，如下式所描述 x = x 2 + 九( x 2 一x j ) ( 2 1 0 ) 其中，入是( 0 ，1 ) 之间均匀分布的随机数。该算子同时假设父代x ：不差于x 。， 即对最大化问题来说，f ( x 。) f ( x 。) ，对于最小化问题来说，f ( x 。) f ( x ：) 。 粒子群算法的交叉模式是根据自身的经验位置、群体最优经验位置和自身目前 位置来调整自身状态。按以上描述，可将粒子群算法的交叉模式描述为 = 一 ( p ， 九：p g )( 九2 ) ( 2 - 1 1