基于统计的中文词自动分类研究

《基于统计的中文词自动分类研究》由会员分享，可在线阅读，更多相关《基于统计的中文词自动分类研究（5页珍藏版）》请在金锄头文库上搜索。

1、基于统计的中文词自动分类研究 赵石顽 夏莹 马少平智能技术与系统国家重点实验室 清华大学计算机系 100084E-mail: Tel: 010-62782266一、引 言基于统计的中文词分类在自然语言处理领域有着重要的应用。机器自动生成的词类可以取代文法的词类；在分类基础上建立的基于类的语言模型可以应用于语音识别、OCR、汉字智能输入等许多领域。众所周知，基于词的语言模型在自然语言处理的许多方面取得了巨大的成功。然而，基于词的语言模型也存在着许多的问题，如参数空间庞大，训练数据不足，数据稀疏等。词的分类可以在一定程度上解决上述问题。在计算语言学方面的应用中，不管是采用统计的方法，还是采用文法

2、的方法，对词类进行处理都比对单个的词进行处理时问题的复杂度要小得多。我们用基于类的语言模型取代基于词的语言模型，可以减小模型的参数空间，减少系统对存储空间的要求。从而可以在小型的系统如掌上电脑、移动电话上建立基于类的语言模型，实现智能输入等。词的分类是建立基于类的语言模型的基础。无论是针对中文，还是别的语言，人们对词的类算法已经做了许多的研究。Brown 等人提出了两个词的自动分类算法。在他们实现的两个分类算法中，都是利用平均互信息作为评价函数。 算法 I (1) 首先将每一个词都当成一个单独的类，然后计算所有相邻类的互信息；(2) 将互信息损失最少的两个类合并；(3) 经过 VC 次合并得到

3、 C 个类；(4) 在得到 C 个类以后，把词汇表中的每一个词移到一个使得平均互信息最大的类中，重复该步骤直到互信息不再增加为止。然而，他们认为，当词汇表的大小超过 5,000 时，这个算法是不可行的。 算法 II 对一个大的词汇表，(1) 将 C 个频度最高的词作为 C 个单独的类；(2) 将未被分配的词中频度最高的一个词作为第 C+1 类，然后将这 C1 个类中互信息损失最 wenjian-3 少的两个类合并；(3) 经过 VC 步后，词汇表中的 V 个词被分成C 个类。用这个方法，一个有 260,741 个英文单词的词表被分成了 1,000 类。Chang 和 Chen 在他们的论文中，

4、以混乱度作为全局最优评价函数，提出了一个模拟退火的词分类算法：(1) 初始化：将每个词随机分配到一个类中，类的总数是事先定义好的。(2) 移动：随机地选取一个词，将该词重新分配到一个随机选取的类中。 (3) 接受或者返回：如果混乱度的改变在控制的范围之内，则接受新的分配，否则，撤销刚才 2 的操作。(4) 循环：重复上述两个步骤，直到混乱度收敛为止。该算法试图找出一个全局最优的分类方案，但是在训练集比较大的时候，算法的时间复杂度太大。Gao 和 Chen 提出了一个自顶向下的二叉树分裂的方法，他们利用词的上下文的方向性，同时得到两个分类二叉树。McMahon 在他的论文中，提出了一个类似退火的

5、分类算法。李涓子在她的博士论文中，提出了一种聚类的算法。她认为聚类过程主要由三个部分组成：聚类时词分布的描述方法，聚类采用的控制策略以及控制聚类过程的目标函数。她在聚类时是采用自顶向下的方法，词的分布信息用的是词的二元同现关系，利用信息论中的熵作 973 国家重点基础研究项目、国家自然科学基金项目。为聚类时的目标函数。上面描述的自顶向下分裂的方法和从下而上合并的方法，两者具有一定的互补性。在自顶向下的方法中，上层的失误在下层是无法纠正的，而且下层的分类结果精确度较低。因此，在本文中，我们采用自顶向下分裂和从下而上合并相结合的方法。我们使用平均互信息作为分类的全局评估函数，分类过程分为两个步骤，

6、首先，我们采用合并的方法将词表中的一些词聚在一起，形成一些小的词类。在第二个阶段，我们把第一步得到的词类作为一个单独的词来加以考虑，然后采用自顶向下的方法，对整个词表进行分类。在实际的工作中，我们首先对大规模语料文本进行了统计和计算工作，得到词的一元和二元信息，在这个基础上，我们进行了词的分类。我们对实现的系统进行了一系列实验，实验结果是令人满意的。本文第二节介绍了我们采用的分类算法，第三节给出了分类的结果及其在基于类的语言模型中的应用，第四节给出了我们的一些结论。二、中文词分类算法（一）互信息的计算公式词分类算法的实现跟采用的评价函数密切相关。本文采用平均互信息作为全局评价函数对汉字进行分类

7、。根据信息学原理，熵的定义如下： XxxpH)(1log)(其中 是一个离散的随机变量，其概率分布为 p(x)， Xx。熵 )(H是一个描述随机变量 的不确定性的统计量，一个随机变量的熵越大，它的不确定性也就越大。我们通过上面的公式导出两个随机变量之间的互信息公式。 )|(),(YHYM从上面的公式中我们可以看出，在已知 的情况下，随机变量 X的不确定度程度会减小，而两者之间的互信息表明了这个减少的程度。在自然语言中，词类NC,321的分布显然也满足随机分布，我们同样可以得到词类的互信息计算公式如下： ijC jijia CPPf )(,log),()(其中 ， 及 ,ji分别表示词类 i、

8、j出现的概率及它们之间的同现概率。在本论文中，我们对 200 兆的语料进行了统计，在统计的基础上，我们用下面的公式来进行计算： toalCwiNPi)(toalCwjiij12)(),(21其中 wN表示词 w 在统计的语料库中出现的次数，而 toalN是所有词在整个语料库中出现的次数。 )(21表示词对 21在语料库中出现的次数。（二）分类算法的实现算法的流程分为两个阶段，第一阶段，采用合并的方法。 （1）我们将词汇表 V里的每一个词都当成一个单独的类；（2）对任意的两个类 iC和 j，计算 ),(jiCM；（3）将互信息损失最少的两个类合并成一个类；（4）经过 1V次合并得到 1个类。如图

9、 1 所示：.图 1. 对 词 汇 表 V进 行 合 并 得 到 C1个 类第二阶段，将前面得到的 1C个类当成 个单独的词，我们给每一个词引进一个整数结构5，让每个结构代表一个词。这样就得到一棵二叉树，整个词汇表是根节点，整数的每一位将词汇表分成两棵子树，0 代表左子树，1 代表右子树。开始的时候，所有的整数都是随机生成的。分类的过程是处理每个结构的第一位，然后依次是第二位，第三位等等。每一位的处理流程可以分为以下的六个步骤。 （1）评估：计算当前分布下的类的平均互信息；（2）试探性移动：将一个词移动到它所在子树相对的子树；（3）重新评估：计算在新的分布下互信息的增加值；(4)恢复：撤销刚才

10、的词的移动，恢复原来的分布；（ 5）按上面的步骤，遍历整个词汇表，找到使互信息增加最大的词，进行移动；（6）循环上述步骤，直到互信息不再增加为止。下图给出了对第二层进行分类时的情形。. . .wi.图 2.对 第 二 层 进 行 分 类 时 的 情 形三、实验结果及分析（一）对语料库的统计在实验中，我们总共使用了 200 兆的语料，包括 95、96 年的人民日报和 90、91、92年的新华社报导。在进行统计前，我们先对语料进行分词，我们采用最大长度匹配的分词方法。分词后，我们把不同的字母（A-Z） ，数字（0-9 ）和其他同类的符号分别归为一个标记。主要是考虑到：首先它们有着一致的同现搭配范围

11、；其次它们对一确定的标记有一致的同现信息；把它们合并为同一个标记，使得该标记与其他标记的同现概率更可信，还可以有效地减少标记个数和减小参数空间。如上所述，当词汇表的大小为 N时， 个标记的统计需要一个 N的矩阵来存储任意两个标记的同现信息。由于我们要用 4 个字节来存储同现信息，因此需要4N的存储空间。不过，二元同现概率矩阵是一个稀疏矩阵，矩阵中的非零元很少，因而我们可以采用压缩存储的方法。如果用链表的结构来存储数据的话，每个元素要占用额外的 4 个字节来存储指针，而且，在查找时，要沿着一条指针链查找，时间开销也比较大，因此，链表的结构也是不可取的。我们在统计中采用了可变长度的数组来存储二元同

12、现概率，对于每个标记还需花费 4 个字节存储数组长度。（二）分类结果在统计完语料库后，我们对频度最高的 10,000 个词进行了分类。在第一阶段，我们先将这 10,000 个词合并成 5,000 个小的词类，然后再将这 5,000 个词类当成一个整体进行分类，最后得到 512 个类。表 1 列出了部分的分类结果。（三）基于类的语言模型在词的二元语言模型中，我们用下面的公式来预测下一个词的出现概率： )(|()(122wPwP如果我们采用基于类的语言模型，我们采用如下的公式： )(| 12CCwcN)|(， 121,2|CwN四、结 论在本文中，我们提出了一个新的分类算法，本算法将自顶向下分裂和

13、从下而上合并两种方法结合起来，综合了两者的优点。在自顶向下的算法中，越是二叉树的底层，分类结果越不精确。而且一旦上层出现错误，后面就没法纠正。因此，我们在采用自顶向下的方法前，先采用合并的方法将词聚成小的词类。在分类的基础上，我们实现了一个基于类的语言模型，并将它和基于词的语言模型进行了比较，取得了比较好的结果。参考文献P. F. Brown and V. J. Della Pietra 1992 Class-based n-gram Models of Natural Language. Computational Linguistics, 18(4): 467-469C-H Chang,

14、C-D Chen 1995 A Study on Corpus-Based Classification of Chinese WordsJun Gao, XiXian Chen 1997 Probabilistic Word Classification Based on Context-Sensitive Binary Tree Method.McMahon, J. Statistical language processing based on self-organising word classification. Ph.D. thesis, The Queens University

15、 of Belfast. 1994.McMahon, J. and Smith, F.J 1995 Improving Statistical Language Model Performance with Automatically Generated Word Hierarchies. Computational Linguistics李涓子 1999 汉语词义排歧方法研究，清华大学博士论文。C-H Chang 1994 Word class discovery for contextual post-processing of Chinese handwriting recognitio

16、n. In Proc. Class 56： 干部 群众 党员 时候 外资 官兵 党组织 员工 敌人 乡亲 人家 银牌Class 119： 他们 双方 人们 一切 老人 有人 分钟 那些 你们 患者 百姓 顾客 病人 儿子 对方 老师 同学 父母 本人 否则 丈夫 也许 乘客 将来 眼睛Class 124： 苏联 全体 埃及 西亚 瑞典 波兰 约旦 荷兰 奥地利 八一 印尼 捷克 西德 议院 Class 125： 北京 美国 法国 中共 南非 印度 泰国 拿大 越南 安理会 芬兰 长春 港澳 秘鲁 三国 海口 挪威 缅甸Class 126： 今年 年来 由于 世纪 因为 周年 对于 月份 然而 如今 明年 当年 那么 多数 年间 可是 直到 比如 不论 昔日 Class 127： 其中 现在 有的 如果 但是 尽管 当时 针对 百万 国会 另外 无论 除了 十万 千万 今日