基于数据驱动的中文分词方法研究

1、现 代 计 算 机 (总 第 二 七 三 期 研究与开发*基金项目 :安徽省自然科学基金 (No.050420204收稿日期 :2007-09-27修稿日期 :2007-11-21作者简介 :李知兵 (1982- , 男 , 安徽舒城人 , 硕士研究生 , 研究方向为智能信息检索0引 言随着信息的飞速增长和互联网的迅猛发展 , 搜索引擎已成为人们查找信息的首选工具 。 然而对于搜索引擎来说 , 最重要的并不是找到所有结果 , 因为在上百亿的网页中找到所有结果没有太多的意义 , 没有人能看得完 , 最重要的是把最相关的结果排在最前面 ,这也称为相关度排序 。 这里就涉及到的一个关键技术就是中文分

2、词 。 中文分词的准确与否 , 常常直接影响到对搜索结果的相关度排序 1。中文分词把输入的计算机汉语语句自动切分为词的序列的过程 。 中文分词对于中文页面检索有重要的意义 , 对它的评价不应依据人的主观看法 , 而应该考察其是否有助于提高信息检索的准确度 。 中文分词目前主要技术难点体现在两个方面 : 对新词识别 ; 歧义解决 1。面对着这些中文分词问题 , 目前的解决方法主要有 :基于字符串匹配的分词方法 、 基于理解的分词方法和基于统计的分词方法 1。 这 3种方法都有各自的优缺点 , 本文介绍一种基于数据驱动的中文分词方法 , 经过实验证明 , 本算法具有比较良好的中文分词性能 。1基于

3、数据驱动的中文分词方法所谓数据驱动是指在系统处理的每一步 , 当考虑下一步该做什么时 , 需要根据此前所掌握的数据内容(也称事实 来决定 4。 这里所说的数据内容就是样本语料库 。1.1基本分词算法给定一个词典和一个句子 , 基本分词方法即根据 词典找出该句子的所有可能的切分 , 并计算出每一种 切分的概率 , 然后选择概率最高的切分作为最后的结 果 。例如 , 假设一个包含 n 个字符的句子 :S=C 1C 2 C n , 有一种包 含 m 个词的切分 :S=W 1W 2 W n , 那 么 这种切分的概率约为 P (S , T =P (W1, W 2, , W n = m i =1 ! P

4、 (W i , 这里 T 代表一个句子的一个划分 。 每个词出现的概率可以从训练语料库中估算出 P (W =N (W , N (W 表示词 W 出现在训练语料库中的次数 , N 是训 练语料库中词的数目 。 当一个词不在词典中时 , 即出 现一个新词时 , 可指定这个新词的出现次数为 0.5。 这 里采取了动态规划技术找出最大概率切分 , 而没有事 先根据词典列举出一个句子的所有可能的切分 。 例如 考虑如下文本段 :玫瑰花开 。 根据词典 , 包含了如下词 语 :玫瑰 、 玫瑰花 、 花开 、 花及开 。 因此有 3种切分 : 玫瑰 /花开 ; 玫瑰花 /开 ; 玫瑰 /花 /开 。 这 3

5、种切分的 概率分别计算如下 : P (玫瑰 *P (花开 ; P (玫瑰 花 *P (开 ; P (玫瑰 *P (花 *P (开 。 其中每个词的 概率可以从它在训练语料库中的相对频率估算出来 。 假定第一种切分概率最高 , 那么这个文本段就被切分 成玫瑰 /花开 。基于数据驱动的中文分词方法研究 *李知兵 1, 李龙澍 2(1. 安徽大学计算机学院 , 合肥 230039; 2. 安徽大学计算智能与信号处理重点实验室 , 合肥 230039摘 要 :关键词 :中文分词 ; 数据驱动 ; 新词识别 ; 组合歧义中文自动分词是计算机中文信息处理中的难题 。 介绍一种基于数据驱动的中文分词方法 ,

6、 开发了基于该方法的分词系统 , 此系统在北大 人民日报 标注语料库中进行封闭测试 , 取得较好的效果 。 系统包含了一个新词识别器 、 一个基本分词算法和实现单字构词 、词缀构词以及一致性检验的程序 。!MODE R N COMP UTE R 2007.12现代 计 算 机 (总 第 二 七 三 期 MODE R N COMP UTE R 2007.12研究与开发1.2由字构词新词通常是由两个或两个以上字构成 , 又经常被 切分成单字 。 例如 “ 空阔 ” 一词 , 当不在词典中时 , 就会 被切分成 “ 空 /阔 ” 。 一个句子在利用基本算法切分后得 到的若干单字后 , 如果这时单字的

7、组词概率超过某一 经验阈值的话 , 这样的连续单字就可以构成一个词 6。 一个字符组词概率是该字符出现在含两个或以上字 符的词中的概率 。有一些汉字如 “ 的 ” 、 “ 了 ” , 它们单独出现的频率 远大于出现在包含两个或两个以上词中的概率 。 例如 在北京大学训练语料库中 , “ 了 ” 单独出现 12634次 , 而在一个词中出现的次数为 876次 ; 另外 , 一些汉字 通常不单独作为词出现 , 而是作为多字词的一部分 。 例如 , 在北京大学训练语料库中 , “国 ” 在多字词中出 现的次数为 17812次 , 而单独出现仅 804次 。 对于训 练 集 中 每 个 字 , 可 计

8、 算 其 成 词 概 率 :P (C in -w ord =N (C in-w ord , N (C 是 字 符 C 出 现 在 训 练 集 中 的 次 数 , 而 N (C in-w ord 是字符 C 出现在两个或以上字构成的词 中的概率 。 可把训练集分成两部分 , 2/3用于训练 , 1/3用于系统开发 , 结果发现把组词概率阈值设为 0.85左右效果最佳 。 这样经过初始切分后 , 如果这些连续 单字符组词概率超过 0.85的话 , 就认为是一个词 。 例 如 “ 人人身着迷彩服 ” 这句包含的 “ 迷彩服 ” 一词不在 北大训练语料库中 。 通过初次切分 , 此句被切成 “ 人 人

9、 /身着 /迷 /彩 /服 /” , 然而正确划分需要把后 3个连续 字符结合起来构成一个词 , 即得到 “ 人人 /身着 /迷彩 服 ” 。 其中 “ 迷 ” 、 “ 彩 ” 、 “ 服 ” 3个字各自的成词概率分 别为 0.94、 0.98、 0.99。1.3后缀构词汉语中有少量文字 , 例如 “ 者 ” 、 “ 性 ” 、 “ 化 ” 等在词 中经常以后缀形式出现 。 从北大训练语料库中选择145个这样的字符 , 如果检查发现该字符前面的词长 度至少为两个字符的话 , 可把这个字符和它的前驱词 结合起来 。 例如 “ 城市化 ” 。1.4一致性检查算法的最后一步是一致性检查 , 一个已切

10、分好的 句子 , 经过前面 3个步骤后 , 再代入到训练集中检查 , 以保证测试的句子和训练集中的相同短语部分切分 一致 。 根据北大训练语料库 , 可创建了一个短语分词 表 , 其中包含四字词 、 三字词 、 双字词和 单 字 词 的 切分 。 例如从训练文本 “ 明天就是除夕 ” 中 , 可做如下切 分 :表 1短语分词表表 1中一个新句子在经过前 3步的切分后 , 检查 每一个四字词 , 当发现该四字词在短语分词表中有不 同的切分时 , 用短语分词表中的切分代替原来切分 。 这个过程可进一步用于三字词 、 双字词 、 单字词 。 总 之 , 基本思想就是如果一个新句子中的某个短语出现 在

11、训练库中 , 那么它就必须和训练集的切分一致 。 例 如 , 测试集中有这样一句 “ 明天就是农历猪年的大年 初一 。 ” 在经过前面 3个步骤后 , 该句被切分成 “ 明天 /就是 /农历 /猪 /年 /的 /大年初一 。 /”(“ 猪年 ” 本 应该是一个词 , 但根据我们的由字构词方法 , “ 猪 ” 和 “年 ” 的 组 词 概 率 0.72, 低 于 事 先 定 义 的 构 词 标 准 0.85, 所以在此不认为一个词 。“明天就是 ” 这一短语 在短语分词表中出现 , 并且切分成 “ 明天 /就 /是 ” , 因此 “ 明天 /就是 ” 被替换成 “ 明天 /就 /是 ” 。 2新

12、词识别我们也开发了几个小程序用来识别测试集中出现的新词 。 第一个程序用来识别数字 、 日期 、 百分比 、 时间 、 外来词等 。 我们定义一系列特殊字符 , 包含例如 数字 “ 0” 到 “ 9” , 字母 “ a ” 到 “ z ” , “ A ” 到 “ Z ” , “ 零一二三 四五六七八九十百千万亿 , 点分之第年 %” 等 。 一旦发 现由若干连续预定义字符组成的短语成分 , 就将其抽 出进行二次处理 。 在二次处理过程中应用到了一系列 规则 。 其中一个规则就是如果一个被抽取的文本段以 “年 ” 结尾 , 而且包含 “ 十百千万亿第 ” 等字 , 那么删除 末尾的字符 “ 年

13、” , 剩下的部分将被认为是一个新词 。 例如根据新词识别器可自动抽取 “ 五百八十年 ” 和 “ 第 六年 ” 等 , 因为这些字符均在预定义的范围之内 。 接下 来经过二次处理将删去尾部字符 “ 年 ” , 返回 “ 五百八 十 ” 和 “ 第六 ” 作为新词 。 对于人名识别 , 我们也开发了 一个程序 , 用来抽取姓名前缀文本 , 例 如 “ 布 依 族 ” 、 “女 ” 等 。 另外还开发一个程序用来检测被中文标点符 号 “ 、 ” 相隔的姓名序列 , 例如 “ 出席领导有胡俊华 、 王 明方 、 杜世平 、 张月 ” 。 一个程序用来抽取在头衔职称!现 代 计 算 机 (总 第 二

14、 七 三 期 研究与开发后面的人名 , 例如 “ 著名相声演员侯宝林 ” 中的 “ 侯宝林 ” 。 一个根据前缀和后缀抽取人名的程序 , 例如 “ 正在忙碌中的孙建军说 ” 中的 “ 孙建军 ” 一词极有可能是一个人名 , 因为 “ 孙 ” 在汉语中是一个姓 , 而且在此处连接的字符串的长度是 3(正好符合汉语中姓名长度一般是两至三个字符 。 此外 , 前缀词 “ 的 ” 及后缀词“ 说 ” 均不可能出现在人名中 。 对于地名 , 我们也开发了一个简单程序抽取城市名 、 镇名 、 村名 、 街道名等 。具体思想是抽取相邻两个指定地名单位 (例如镇和村 之间的两三个字符 。 例如 , 从 “ 安

15、徽省舒城县阙店镇雨岭村 ” , 我们程序将能抽出 “ 阙店镇 ” 和 “ 雨岭村 ” 。3实验与结果在 Windows 环境下 , 用 Java (JDK1.5 开发了基于该思想的中文分词平台系统 (图 1 。 表 2的最后一行(粗体 给出在北大语料库中封闭测试的结果 。 其中“ 步骤 ” 一列是我们的中文分词算法的执行步骤 。 步骤1利用基本算法进行切分 , 步骤 2连接单字词 , 步骤 3给某些词加上后缀 , 步骤 4进行一致性检查 。 这 4个步骤第 1节中详细阐述过 。 表格第 2列为实验步骤中用到的词典 。 dict1仅包含北大训练语料库 , dict2包含dict1中所有词及用第

16、2节中描述的方法从北大测试文本中抽取的词 。 R 、 P 、 F 列分别表示召回率 、 查准率和 F 值 。 Roov 和 Riv 分别表示未登录词的召回率和已录入词的召回率 。 结果显示 , 新词识别和单字构词等程序大大提高了查准率 , 而一致性检查程序大大提高了查全率 。图 1中文分词平台系统4讨 论这一部分我们进一步检查训练集内 、 测试集内以及训练集和测试集之间分词不一致的情况 。 尽管不可能完全消除不一致现象 , 但是可以研究导致不一致的 原因并采取措施改善解决 。 例如 “ 极大地 ” 有 “ 极大 /地 ” 和 “ 极 /大 /地 ” 两种切分 。“ 最新 ” 有 “ 最新 ”

17、和 “ 最 /新 ” 两种切分 , “ 才能 ” 有 “ 才能 ” 和 “ 才 /能 ” 两种切分 。 “ 黄金周 ” 被切分成 “ 黄金 /周 ” , “ 乌鸦嘴 ” 被切分成 “ 乌 鸦 /嘴 ” 。 这其中有些是因为本身就存在歧义 , 需要抽 出来重新校正 , 例如 “ 才能 ” 2,5。 而另外则是因为是新 词 , 例如 “ 黄金周 ” 、 “ 乌鸦嘴 ” 等 。表 2在北大语料库下封闭测试的结果5结 语本文阐述了基于数据驱动的中文分词思想 , 设计 了对应的中文分词系统 , 并在北大标注的 人民日报 语料库上进行封闭测试 , 得到了良好的效果 。 此系统 中新词识别 、 由字构词 、

18、 一致性检查等几个部分是对 基本分词算法的一个有效补充 。 在提高查准率和召回 率方面都起到很大作用 , 这一点优于最大匹配算法 。 在封闭语料库实验中 , 发现 67%的错切分都是因为新 词 , 所以有关未登录词的更准确切分将是下一步继续 改进的地方 。参考文献1黄昌宁等 . 中文分词十年回顾 . 中文信息学报 , 2007,21 (3 :8192秦颖 , 王小捷 . 汉语分词中组合歧义字段的研究 . 中文信 息学报 , 2007, 21(1 :383T. Emerson. The Second International Chinese Word Seg-mentation Bakeoff

19、, SIGHAN-05R, 20054Dong-Hee Lim, Seug-Shik Kang , Data-Driven Language Independent Word Segmentation Using Character-Level Information, Proceedings of the 2nd SIGHAN Workshop on Chinese Language Processing , 2003:1481515翟凤文 , 赫枫龄 , 左万利 . 字典与统计相结合的中文分词方 法 . 小型微型计算机系 ,2006,.27(9 :176617716孙茂松 , 黄昌宁等 .

20、 信息处理用现代汉语分词词表 . 语言 文字应用 , 2001(4 :8489(下转第 19页 ! "MODE R N COMP UTE R 2007.12现 代 计 算 机 (总 第 二 七 三 期 MODE R N COMP UTE R 2007.12研究与开发Research on Chinese Word Segmentation Based onData-Driven ApproachLI Zhi-bing 1,LI Long-shu 2(1. School of Computer Science &Technology, Anhui University, Anh

21、ui 230039; 2. Key Lab of IC&SP at Anhui University , Ministry of Education , Hefei 230039Abstract:Keywords:Chinese Word Segmentation; Data-Driven; New Words Recognition; Combinational AmbiguityChinese automatic segmentation is one of the most difficult problems in computer Chineseinformation dis

22、posal. Introduces a data-driven Chinese word segmentation, develops a word segmentation system based on this approach. Closed tests conducted on PKU-ICL-PD-Corpus perform well. It consists of a new words recognizer, a base segmentation algorithm, and proce-dures for combining single characters, suff

23、ixes, and checking segmentation consistencies.第四步 :计算 (red , D , =0.75=r (C , D , 结束 。 所以 :最后的约简为 red=outlook, temperature,windy , 与文献 4中在无噪声情况下的约简结果是一 致的 。5结 语本文结合胡可云的算法对属性重要性的描述 , 提出了一种基于变精度粗糙集模型的属性约简算法 。 该 算法是以条件属性在可辩识矩阵中出现的频率及可 辨识矩阵中项的长度为启发信息的 , 与传统计算属性 重要性的方法 47相比 , 无需逐个计算属性的近似依赖 度 , 降低了算法的复杂性

24、。并通过 的取值 , 允许有一 定的分类错误率存在 。 实例表明该方法能够有效地对 决策表进行属性约简 , 并具有一定的抗噪声能力 。参考文献1Pawlak Z. Rough Sets. International Journal of Informationand Computer Science , 1982, 11(52W.Ziarko,Variable Precision Rough Set Model, Journal of Computer and System Sciences, 1993,46(1 :39593张文修 , 吴伟志 , 梁吉业 , 李德玉 . 粗糙集理论与方法 . 北 京 :科学出版社 , 2001:1231314王国胤 . Rough 集理论与知识获取 . 西安 :西安交通大学 出版社 ,2001:133138,1481525胡可云 . 基于概念格和粗糙集的数据挖掘方法研究 . 清 华大学博士生论文 , 20016李祝平 , 冯秀芳 ,