面向大规模信息检索的中文分词技术研究.ppt

面向大规模信息检索的中文分词技术研究 王小飞指导教师 王斌前瞻研究中心2006 6 6 提纲 一 引言二 面向大规模中文信息检索的分词算法三 基于双数组Trie树优化算法的词典四 歧义消除五 未登录词识别六 查询扩展层面的覆盖歧义处理七 实验结果和分析八 总结 一 引言 研究意义信息检索简介中文分词简介常用评测指标 研究意义 分词技术的广泛应用 信息检索 人机交互 信息提取 文本挖掘等 目前对分词的研究 大都集中于通用的分词算法 以提高分词准确率为目的 目前的分词算法中 一些切分精度比较高的算法 切分的速度都比较慢 而一些切分速度快的算法 因为抛弃了一些繁琐的语言处理 所以切分精度都不高 速度 每秒几十k 几M切分正确率 80 98 研究意义 针对一项具体的上层应用来研究相关的分词技术 这样便于有一个比较确定的分词规范和目标 然后可以有针对性的在分词算法方面有所突破 信息检索 目前跟人们生活最接近 应用最频繁而且技术发展也最成熟的一项信息处理技术 信息检索简介 信息检索 InformationRetrieval IR 对收集的信息进行标引 Index 在接收到用户提交的查询请求以后在标引过的数据中进行查找 然后将查找到的相关结果信息返回给用户 图1检索过程示意图 中文分词简介和困难 中文分词 ChineseWordSegmentation 将一个汉字序列切分成一个一个单独的词 比如将 组合成分子时 切分成 组合 成 分子 时 困难分词规范 词的概念和不同应用的切分要求分词算法 歧义消除和未登录词识别 分词规范方面的困难 汉语中词的界定 教育局长 教育 局长 教育局 长 教育 局 长 核心词表如何收词 词的变形结构问题 看 没 看见 相不相信 不同应用对词的切分规范要求不同输入法 这是 每一 并不 不多 不在 就是 信息检索 中国 科学院 计算 语言学 分词算法上的困难 切分歧义的消除交集型歧义 交叉歧义 组合成 我们 小组 合成 氢气了 组合 成 分子 组合型歧义 覆盖歧义 马上 他 从 马 上 下 来 我 马上 就 来 了 学生会组织义演活动 学生 会 组织 义演 活动 or 学生会 组织 义演 活动 分词算法上的困难 未登录词识别命名实体 数词 人名 地名 机构名 译名 时间 货币缩略语和术语 超女 非典 去离子水 新词 酱紫 星盘 先识别已知词还是先识别未登录词先识别已知词 内塔尼亚 胡说 先识别未登录词 胜利取决 于勇 气 常用评测指标 召回率 Recall 分词 检索 准确率 Precision 分词 检索 常用评测指标 TREC TextRetrievalConference 的评测指标InterpolatedRecall PrecisionAverages 用插值法计算在11个召回点 0 0 1 0 下相对的准确率 Averageprecision non interpolated 表示平均每篇相关文档被检索出来时的准确率 表示对于Queryj检索出的所有相关文档数 表示对于Queryj 在第i篇相关文档被检索出时总共检索出的结果文档数 常用评测指标 TREC TextRetrievalConference 的评测指标Precision 在检索到x篇文档时的准确率 x为5 10 15 20到1000不等 例如Precision At30docs 通常用P 30表示 的值为0 5784就是表示前30篇文档中检索的准确率是0 5784 R Precision 一个查询检索到R篇文档时的准确率 R为该查询真正相关的文档数 如果一个查询的相关文档数为30 在检索系统检索出的前30篇文档中相关文档数为18 则该查询的R Precision为18 30 0 6 二 面向大规模中文信息检索的分词算法 分词方面的相关研究成果分词和大规模中文信息检索之间的关系探讨适用于大规模中文信息检索的分词算法 分词方面的相关研究成果 基于词典和规则的方法基于大规模语料库的统计方法规则和统计结合的方法基于字的切分法 基于词典和规则的方法 最大匹配正向最大匹配 反向最大匹配和双向最大匹配实现简单 而且切分速度快 但无法发现覆盖歧义 对于某些复杂的交叉歧义也会遗漏 全切分利用词典匹配 获得一个句子所有可能的切分结果 时空开销非常大 基于理解的分词算法模拟人的理解过程 在分词过程中加入句法和语义分析来处理歧义问题 难以将各种语言信息组织成机器可直接读取的形式 还处在试验阶段 基于词典和规则的方法 基于规则的消歧和未登录词识别规则消歧CONDITIONFIND R NEXT X X ccat w SELECT1CONDITIONFIND L NEAR X X yx 听 相信 同意 SELECT1CONDITIONFIND L NEAR X X yx 假如 如果 假设 要是 若 SELECT2OTHERWISESELECT1用规则识别未登录词LocationName PersonNameLocationNameKeyWordLocationName LocationNameLocationNameKeyWordOrganizationName OrganizationNameOrganizationNameKeyWordOrganizationName CountryName D DD OrganizationNameKeyWord 基于大规模语料库的统计方法 N元语法 N gram 模型隐马尔可夫模型 HMM 对于一个随机事件 有一个状态序列 X1X2 Xn 还有一个观察值序列 Y1Y2 Yn 隐马模型可以形式化为一个五元组 S O A B 其中 S q1 q2 qn 状态值的有限集合O v1 v2 vm 观察值的有限集合A aij aij p Xt 1 qj Xt qi 转移概率B bik bik p Ot vk Xt qi 输出概率 p X1 qi 初始状态分布 基于大规模语料库的统计方法 互信息 MI MutualInformation MI越大 表示两个字之间的结合越紧密 反之 断开的可能性越大 当x与y关系强时 MI x y 0 x与y关系弱时 MI x y 0 而当MI x y 0时 x与y称为 互补分布 最大熵模型 ME MaxEntropy 在已知条件下选择一个合适的概率分布来预测事件 规则和统计结合的方法 通常利用词典进行初切分 然后用其它的概率统计方法和简单规则消歧和进行未登录词识别 比如 利用词典匹配进行初切分得到一个切分词图 然后利用词频信息求词图N条最短路径的N 最短路径法 最大匹配算法 state of the art分类器和支持向量机的结合 通过词典匹配找出所有交叉歧义 利用Bigram语言模型或其变形来消除歧义 基于字的切分方法 N元切分法 N gram 对一个字符串序列以N为一个切分单位进行切分 如二元切分法 ABCDEFG AB CD EF G 交叉二元切分法 OverlappingBigram ABCDEFG AB BC CD DE EF FG 简单快速 但会产生大量无意义的标引词 导致标引产生的索引文件的空间 以及检索和进行标引的时间都大大增加 同时 因为它的切分单位并非语言学意义上的词语 所以也会导致检索的查准率下降 分词和大规模中文信息检索之间的关系探讨 在当前的信息检索技术中 中文切分是必要的 问题是否需要按语言学意义上的词进行切分 文档和查询二者的切分方法是否需要一致 是否检索系统使用的分词算法切分精度越高其检索结果就越好 分词和大规模中文信息检索之间的关系探讨 表1 TREC5和TREC6中文信息检索实验比较 分词和大规模中文信息检索之间的关系探讨 基于字的切分 单字切分 二元切分和交叉二元切分基于词的切分 基于词典的匹配和基于统计的方法7组关于切分方法的实验比较结论 字比词好 3组 词比字好 3组 二者差不多 1组3组关于切分一致的实验比较结论 切分方法一致更好 1组切分方法不一致的更好 2组查询是基于字的切分时 文档是最大匹配切分的结果更好 查询是基于词的切分时 文档是基于字的切分的结果更好 分词和大规模中文信息检索之间的关系探讨 两组实验 1 基于单字切分 交叉二元切分和利用ICTCLAS系统切分的检索性能比较 文档和查询采用同一种切分方法 2 基于单字切分 交叉二元切分和利用ICTCLAS系统切分的检索性能比较 查询采用人工切分的方法 实验环境 数据 北大提供的中文网页测试集CWT部分数据 检索系统 麻州大学和卡内基梅隆大学合作开发的检索工具包Lemur 分词和大规模中文信息检索之间的关系探讨 表2实验1的结果 分词和大规模中文信息检索之间的关系探讨 表3实验2的结果 分词和大规模中文信息检索之间的关系探讨 分词精度与检索性能的实验比较 FuchunPeng等 2002 测试数据 TREC 5和TREC 6的中文测试集检索系统 OKAPI系统三种分词算法 基于词典的前向最大匹配 71 和85 基于文本压缩的PPM算法 90 和95 基于EM的自监督算法 44 49 53 56 59 70 75 77 分词和大规模中文信息检索之间的关系探讨 图2Kd 10时的12组检索结果比较 分词和大规模中文信息检索之间的关系探讨 原因 查询切分和文档切分采用相同的分词算法 有一些文件切分错误的词 在查询时也遇到相同的切分错误 所以即使切分阶段错误 但最后相同错误匹配 使得仍然可以正确检索到 有些词被错误的切分成几个部分 尽管这样会导致分词正确率下降 但对于检索来说 最后可以通过结果合并得到正确的结果 分词的错误并不影响检索的性能 分词测得的准确率高低并不是绝对的 有时跟用标准答案有关 这涉及到对词的定义问题 有些标准答案认为是该切分的词 实际上不切分用于检索更加准确一些 如 国 内 vs 国内 民进党团 vs 民进 党团 vs 民进党 团 适用于大规模中文信息检索的分词算法 分词算法的时间性能要比较高 尤其是现在的web搜索 实时性要求很高 所以作为中文信息处理基础的分词首先必须占用尽可能少的时间 分词正确率的提高并不一定带来检索性能的提高 分词到达一定精度之后 对中文信息检索的影响不再会很明显 虽然仍然还是有一些影响 但是这已经不是CIR的性能瓶颈 所以片面的一味追求高准确率的分词算法并不是很适合大规模中文信息检索 在时间和精度之间存在矛盾无法兼顾的情况下 我们需要在二者之间找到一个合适的平衡点 切分的颗粒度仍然可以依照长词优先准则 但是需要在查询扩展层面进行相关后续处理 在信息检索中 分词算法只需要集中精力考虑如何消除交叉歧义 对于覆盖歧义 我们可以利用词典的二次索引和查询扩展来解决 未登录词识别的准确率要比召回率更加重要 要尽量保证未登录词识别时不进行错误结合 避免因此切分出错误的未登录词 如果将单字错误的结合成未登录词了 则有可能导致无法正确检索到相应的文档 适用于大规模中文信息检索的分词算法 待切分文本 初切分结果 核心词典 消除交叉歧义 未登录词识别 新词词典 切分结果 交叉歧义检测 图3面向大规模中文信息检索的分词算法流程图 三 基于双数组Trie树优化算法的词典 图4 传统的Trie树结构转换成两个线性数组 三 基于双数组Trie树优化算法的词典 s t c base check s t c 图4 双数组Trie树的状态转移示意图 三 基于双数组Trie树优化算法的词典 数组构造的基本思想 对6763个常用汉字根据其内码相应的赋予从1 6763的序列码 放入base 1 base 6763 若首字序列码是i的词语有n个 设所有第二个字的序列码依次为a1 a2 a3 an 则这n个第二字在base数组中的位置依次为base i a1 base i a2 base i an 依次类推第三字 第四字 第k字的位置 如果base i 和check i 同为0 表示位置i为空 如果base i 为负值 表示该状态为一个词语 三 基于双数组Trie树优化算法的词典 以前的处理顺序 S A B C D E F G H I J K L加入优化策略之后的处理顺序 S A C B F D E G H I J K L 三 基于双数组Trie树优化算法的词典 实验环境 CPU1 5G 内存512M 操作系统为WindowsXP词典词条总数 75784所有算法均用c 实现 实验一分别用未加入优化策略的双数组Trie树 Double ArrayTrie 算法与优化后的双数组Trie树 Double ArrayTrie 算法生成词典的双数组文件 比较空间利用率 结果 未加入优化策略生成的数组长度为140438 加入优化策略后生成的数组长度为114624 数组长度减少了2万5千多 数组的空间利用率由85 44 提高到91 27 三 基于双数组Trie树优化算法的词典 实验二比较双字Hash索引机制算法和优化的双数组Trie树 Double ArrayTrie 算法查找词语的速度 三 基于双数组Trie树优化算法的词典 实验三比较普通Trie树算法和双数组Trie树优化算法用于正向最大匹配自动分词的速度 语料库文本均为未切分的人民日报98年语料 文本1 98年1月语料大小为4 092 478字节文本2 98年2月语料大小为4 153 811字节文本3 98年4月语料大小为4 666 292字节 四 歧义消除 交叉歧义检测基于双字耦合度和t 测试差消歧实验结果 四 歧义消除 图5 交叉歧义图 四 歧义消除 双字耦合度 求两个字的结合强度和互信息比较 字间位置切分正确率PSeg 正确切分的位置数 切分文本字间位置总数训练集 98年1至6月的人民日报语料库测试集 SIGHAN03香港城市大学测试语料 四 歧义消除 图6双字耦合度和互信息的字间位置切分正确率比较 四 歧义消除 双字耦合度的缺点 只是独立的计算两个连续汉字的结合强度 并没有考虑到上下文的信息 比如 Couple 对 比 0 75 Couple 比 方 1 0 Couple 方 法 0 97 四 歧义消除 t 测试 t test t 测试差总体来说 0时 yz的字间位置倾向于判断为连接 反之判断为断开 四 歧义消除 双字耦合度和t 测试差结合消歧 四 歧义消除 利用词典扫描 找出句子中所有的交叉歧义 标记相关的歧义位置 计算歧义位置的双字耦合度和t 测试差的线性叠加值CDT 按值的大小顺序依次判断歧义位置的切分与否 其中并不需要每个位置都进行判断 因为有一个歧义位置确定之后 该歧义位置相关的其它歧义位置就不需要再判断 可以直接选择是切分还是连接了 消歧过程 四 歧义消除 实验训练语料库 已经切分过的人民日报98年1 6月语料封闭测试 人民日报98年1月语料开放测试 SIGHAN05年北京大学和微软研究院语料四组实验结果比较 1 单独用双字耦合度判断歧义位置 2 用t 测试差判断歧义位置 3 互信息和t 测试差结合判断歧义位置 4 双字耦合度和t 测试差结合判断歧义位置 四 歧义消除 实验结果 表4三种歧义判断算法的准确率比较 五 未登录词识别 采用各种命名实体和新词一体化识别策略正确的合并被错误切分成单字的汉字 单字的成词位置概率对于连续的单字串 c1 c2 c3 cn 其中汉字ci的各位置概率分别为 P ci B ci出现在词首的概率P ci I ci出现在词中的概率P ci E ci出现在词尾的概率P ci S ci单独成词的概率 五 未登录词识别 表5基于位置成词概率的单字合并规则 五 未登录词识别 局部二元串频统计 预先统计待切分文档中二元字对的共现次数如果字串 cici 1 在被切分文档中重复出现次数超过某个数时 P ci S P ci 1 S 2的阈值可以增大为s 五 未登录词识别 实验实验环境 同上一章歧义消除的环境 一共2组实验 根据字的位置成词概率识别未登录词 用字的位置成词概率结合局部二元串频统计识别未登录词 五 未登录词识别 表6未登录词识别实验结果 六 查询扩展层面的覆盖歧义处理 目的 解决切分粒度过大问题 提高召回率 方法 基于词典的二次索引进行查询扩展 在查询扩展时将相应的覆盖词加入到查询表达式中去 这里覆盖词是指词典中包含了查询词的其他词 六 查询扩展层面的覆盖歧义处理 图7词典的二次索引示意图 六 查询扩展层面的覆盖歧义处理 实质 简单的词语切分过程 将分词中的覆盖歧义处理部分放到词典预处理阶段 优点 节省切分的时间 减少了索引数据的冗余度 图8分词中覆盖歧义省略示意图 六 查询扩展层面的覆盖歧义处理 缺点 有可能将一些语义上无关联的词加入到查询扩展中去 导致检索准确率降低 为了避免检索时将过多的不相关文档排到结果集的前面 我们根据切分位置互信息的大小赋予两个词不同的权重 权重计算方法 如果W是由一次索引得到的词 则W的权重为1 如果W是由词W 的二次索引得到的词2 1若W 在W中未引起交叉歧义 则W的权重 2 2若W 在W中是交叉歧义的一种结果 则W的权重 其中W 是W中和W 引起交叉歧义的另一个词 七 实验结果和分析 分词测试 硬件环境 CPU3 2G 内存512M三种算法 IRSEG ICTCLAS 前向最大匹配 词典 75784个词条测试集 SIGHAN05年北大和微软研究院提供的语料库 七 实验结果和分析 分词测试 评测指标 未登录词识别准确率 未登录词识别召回率 登录词识别召回率 七 实验结果和分析 分词测试结果 表7分词算法切分速度比较 七 实验结果和分析 分词测试结果 表8pku语料库测试结果 七 实验结果和分析 分词测试结果 表9msr语料库测试结果 七 实验结果和分析 分词测试结果 图9三种算法平均的切分准确率和召回率 七 实验结果和分析 分词测试结果相关说明测试集切分标准不同 比如人名 时间 数量词等未登录词的切分标准 语料库本身就存在一些切分不太合理或者可以说错误的地方 相当大军区级单位的正职首长 语料库切分结果 相当 大军 区级 单位 的 正职 首长IRSeg切分结果 相当 大 军区 级 单位 的