名词聚类在自然语言处理系统中的应用


CN431258/ T P ISSN 1007130X 计算机工程与科学 COMPUTER ENGINEERING & SCIENCE 2009 年第 31 卷第 8 期 Vol 31, No 8, 2009 文章编号: 1007130X( 2009) 08013304 名词聚类在自然语言处理系统中的应用* Application of Noun Clustering in NLP Systems 费小栋1 , 赵 克2 , 李亚涛3 , 刘 靖4 FEI Xiaodong1 , ZHAO Ke2 , LI Yatao3 , LIU Jing4 (西安电子科技大学机电科学与技术研究所, 陕西 西安 710071) (Research Institute of Mechatronics, Xidian University, Xi an 710071, China) 摘 要: 本文主要介绍了自然语言处理系统中名词聚类的处理方法及其思想研究; 对名词按照内涵知识进行聚类, 对 聚类中出现的问题进行了细致的分类, 并对不同种类的问题给出了不同的解决方案。在建立了完整的领域知识库的情况 下, 本文提供的聚类方法在中学智能辅导系统中对提取篇章核心意思具有很高的成功率。 Abstract: This paper presents an approach of noun clustering and its ideological research in natural language processing systems. Noun is clust ering in accordance w ith the content know ledge. A detailed classification of the problems w hich ap pear during the clustering is made, and different solut ions t o different t ypes of problems are given. Under the circumstances of a complete know ledge base area, the novel clustering method has a high success rate in t he int elligent guidance systems for secondary schools to extract the core meaning of a chapter. 关键词: 名词; 聚类; 自然语言处理; 静态知识库; 概念从属树 Key words: noun; clustering; natural language processing; stat ic know ledge base; concept dependence tree 中图分类号: T P391 文献标识码: A 1 引言 语言的层次结构可分为篇章、段落、句群和单句。篇章 由段落构成, 段落由句群构成, 句群由单句构成, 而单句又 是由一个个的词组成的。词是语言学研究的对象, 也是自 然语言处理的基本单位。但是, 在一篇文章中, 需要理解的 重点往往不是句子的意思, 也不是单个词语的意思, 而是篇 章的总体意思。要研究整篇文章的意思, 关键是找出这篇 文章的核心意思和分析清楚该文的线索。研究发现, 通过 聚类可以方便地实现这些要求。所谓聚类, 就是一个将数 据集划分为若干组或类的过程, 并使得同一个组内的数据 对象具有较高的相似度, 而不同组内的数据对象则是不相 似的。相似或不相似的度量是基于数据对象描述属性的取 值来确定的[1] 。结合本文讲述的领域, 聚类里把初中数学 领域具有相关性的名词按照静态知识、概念从属等理论汇 聚到一起的操作。 在我们所做的 网络智能辅导系统! 中, 聚类对提取题目 意思的成功率已经高达 85%, 通过对名词的聚类, 篇章的中 心意思最终归结为一个名词或者该名词所发生的事件。 2 理论分析 2. 1 静态知识库 2. 1. 1 建立静态知识库的必要性 在自然语言理解中, 分辨事件的相关性是需要静态知 识做支持的。例如, 三角形 A BC 中, 角 A BC 等于 60 度, 面积为 50, 四边形 A BCD 的面积为 90, 周长为 35, 三角形 的周长为 27。这个例子中 三角形 A BC 中, 角 A BC 等于 60 度, 面积为 50, 三角形的周长为 27! 是相关的, 而 四边 形 ABCD 的面积为 90, 周长为 35!也是相关的。 我们判断一系列事件是否相关的依据是我们人类所拥 有的知识, 计算机要判断事件的相关性同样也需要静态知 识作基础。所以, 要把一系列事件按照相关性进行聚类, 建 立合理完善的静态知识就尤为重要。 2. 1. 2 建立静态知识库的方法∀ 本体 (Ontology) 在客观世界里, 本体被用来描述存在的各个概念以及 概念之间的各种关系[ 2] , 是一个关于特定领域共享的理解, 133 * 收稿日期: 20080704; 修订日期: 20081002 基金项目: 科技部科技型中小企业创新基金资助项目( 01c26226111002) 作者简介: 费小栋( 1983) , 男, 陕西蓝田人, 硕士生, 研究方向为人工智能、知识工程和创新技术。 通讯地址: 710071 陕西省西安市唐延南路 10 号中兴通讯; T el: 13991287393; Email: f_xd2008@ yahoo. cn Address: ZTE, 10 Yantang Rd South, Xi an, Shaanx i 710071, P. R. China 被认为是一些类( 概念) 、关系、函数、公理和实例的集合。 概念和概念之间的关系是本体的两个非常重要的组成 元素。 ( 1) 概念( Concepts) 。概念是物体或事件的模型知识。 例如, 线段和延长分别是物体和事件的模型知识, 它们都是 知识。 ( 2) 关系( Relations) 。在领域中概念之间的交互作 用, 形式上定义为 n 维笛卡儿积的子集: R: C1 # C2 # ∃# Cn 。 从语义上讲, 基本的关系有四种, 如表 1 所示。 表 1 基于本体的概念之间的关系 关系名 关系描述 Partof 概念之间部分与整体的关系 Kindof 概念之间的继承关系, 类似于面 向对象中父类与 子类的关系 Instanceof 概念的实例与概念之间的关系, 类似于面向对象 中对象与类的关系 Attributeof 某个概念是另一个概念的属性, 如 边!是三角形 的属性 在实际的建模过程中, 概念之间的关系不限于上面四 种关系, 可以根据领域的具体情况定义相应的关系[3] 。概 念包括内涵和外延, 概念的内涵反映的是事物的本质特征, 如三角形的定义; 概念的外延反映的是事物所指的范围, 如 三角形的角、边等。例如, 对 三角形! 这个概念的描述如 下: 概念模型: ( 名词( 词名 三角形) ( 属性 点 线 角 中心 重心 ∃∃) ) 。 实例模型: ( 动态名词( 词名 三角形) ( 对象 ABC) ( 属 性 ( A B C) ( AB BC AC) ∃∃) ) 。 2. 2 概念从属理论 概念之间有不同的关系, 其中包括概念的从属关系。 从属关系是指一个概念的外延包含另一个概念的所有外 延。引入从属关系后, 知识被划分为一系列结点, 知识结点 之间呈现树状联系。利用从属关系对特定领域的知识块进 行抽象化处理, 使其形成由具有不同抽象层次的知识结点 构成的树状层次结构, 这种从属关系的树模型就被称为概 念从属树( CDT) 。图 1 是对三角形的知识结构进行细化之 后的概念从属树。 图 1 知识细化后的三角形概念从属树 概念从属树体现了概念之间的属性继承关系。每个名 词概念都是一个抽象程度不同的具体概念, 即抽象具体概 念树上的一个子结点。上层概念为下层概念的父类概念, 下层概念继承上层概念的所有属性, 并具有自己特有的属 性。概念从属树上的每个结点通过爬树来理解概念的内涵 和外延, 从而进行深层语义理解。在向知识库中添加概念 时, 只需填写与其父概念不同的内涵和外延, 这就大大缩减 了知识库的容量且便于管理。 3 名词概念的聚类分析 在自然语言理解中, 篇章是理解文本语义的关键一步, 对篇章中的词语按照相关性进行聚类, 可以提取出文本的 中心意思。 3. 1 中心理论 中心是一个或几个句子所要表现和说明的问题或者是 一个主体, 通过不断地描述说明这个主体的某些状态或与 这个主体相关的事件; 它或者是某一事件, 通过不断刻画说 明该事件的条件、原因、结果、时间、地点等因素, 以及与该 事件相关的所有主体状态的变化。中心的变迁是指当前描 述的主题发生了转变, 新的问题成为关注的焦点。中心的 变迁是划分片段的主要依据。 根据中心的变迁, 可以划分整个语篇为一些相对内聚 的片段, 每个片段说明一个中心, 理解出这些中心和它们之 间的层次结构, 我们就可以在语篇层次上把握语篇所表现 的主题和段落大意, 进而把握整个语篇的意图。 3. 2 核心词理论 在中心理论的基础上, 引申出核心词理论。与中心理 论不同, 核心词不止一个, 而是多个。对整个篇章确立的多 个带权值的核心词排序, 权值最高的就是篇章的中心, 其它 权值较高的一般也是局部篇章上下文的中心。依据篇章中 主体的出现次数以及概念间的直接或间接的关系确立核心 词的权值, 最终形成一个按核心词权值排序的列表。 3. 3 核心词分析和提取 核心词分析是聚类分析的延伸。当篇章中的概念达到 了一定的局部集中, 篇章成为了一个由多个局部内聚的单 元组成的集合体时, 篇章的结构还不明显, 在此基础上进行 进一步的核心词分析, 可以得到一个比较明显的篇章结构。 核心词的确定可以考虑以下方面: ( 1) 同一关系: 在多个单句中的多个主体实际是同一个 主体, 这个主体在不同的地方重复出现, 以第一个为基准, 它或者直接以相同形式出现, 或者在概念的抽象层次上发 生了改变, 或者出现了一定程度的省略, 例如, 线段 A B! 在篇章其它句子中可能以相同的 线段 A B! 出现, 也可能 以不同概念层次的 中线 AB! 、 边 A B! 等形式出现, 也有 可能省略 线段!直接以 AB! 的形式出现。诸如此类情况, 每出现一次就将增加相应核心词的权值。 ( 2) 属性关系: 在多个单句中的不同主体存在着属性关 系, 即一个主体是另外一个主体的属性。例如, 三角形 A BC! 有属性 线段 AB! 、 线段 AC! 、 角 A BC!、 角 B!、 点 A! 等属性。在其它句子中每出现它的属性, 就增加其 相应核心词的权值。 ( 3) 外延关系: 外延是指概念的相关方面, 是概念有关 方面的向外延伸。例如, 我的衣服上的扣子掉了! , 衣服! 属于 我!, 但 衣服! 不是 我! 的属性, 它是一种外延关系, 而 衣服!和 扣子! 则是比较明显的属性关系。这里, 我们 为层次较高的主体加权。 ( 4) 事件的主体: 事件的主体是指事件的参与者, 即事 134 件的施事者和受事者。例如, 上例 我的衣服上的扣子掉 了! 所描述的是 扣子掉了! , 扣子! 才是关注的重点, 我! 和 衣服! 都是附加说明。所以, 我们应为事件的主体增加 权值, 以体现其核心作用。 (5) 领域的关注重点: 前面讲述的主要是从主体的直接 和间接关系来研究, 没有放入特定语境之中。实际上不同 的语境有其不同的关注重点, 该重点往往是该语篇的核心。 例如, 在一般数学领域, 要求解或求证的对象就是重点。 通过以上几个主要方面的处理, 最后会在一个篇章中 得到很多带权值的核心词, 去掉一些影响不大的核心词( 一 般权值等于初始权值) , 为剩余核心词建立一个排序, 这样 就得到了核心词的排序列表。 4 名词聚类的实现 名词聚类是围绕着名词概念的内涵和外延展开的, 内 涵和外延对应着本体的各个属性, 依据本体间的属性关系、 继承关系、整体部分关系等我们把一些相关的概念汇聚到 一起。我们使用 概念从属树! 记录概念间的抽象层次关系 ( 继承关系) , 使用名词的属性槽记录概念的内涵和外延。 名词所有的内涵和外延属性均记录在属性槽里, 定义名词 的概念本体模型如下: (名词( 词名 直角三角形) (树根 三角形) (父 三角形) ( 属性 角 边∃∃) ) 这些知识连同概念从属树均以概念本体模型保存在静 态知识库中, 实际处理时通过各个概念实例与这些模型对 比, 触发相应的推理规则便可进行相应的聚类处理。 4. 1 名词聚类的步骤 名词聚类是围绕名词概念的关系展开的, 其基本步骤 如下: (1) 根据名词概念与属性关系聚类。例如, 三角形和 角, 把角这个三角形的属性汇聚进三角形的关系模板中。 (2) 根据概念与外延的关系, 将若干内涵较大的离散概 念汇聚到内涵较少的抽象的概念关系模板里, 如四边形、平 行四边形、菱形, 把平行四边形、菱形汇聚进四边形的关系 模板中。 (3) 根据概念之间的动态关系, 将知识库中不存在静态 关系的概念用动态关系联系起来。例如, 桌子和水杯, 通过 水杯放在桌子上! 这个事件将原本不相关的两个概念联系 起来。名词概念之间最大的关系框架是概念从属框架, 它 表示的是概念与外延的关系。名词按照属性聚类的离散概 念结果往往还要利用概念之间的继承关系, 汇聚到更高一 级的概念。 4. 2 具有属性关系的名词聚类 这种具有属性关系的名词聚类分为两种情况: (1) 句群中只有一个核心词时, 所有的名词均是该核心 词的属性。例如, 三角形 A BC 中, 角 A BC 等于 30 度, 三 角形 ABC 的面积为 20, 三角形的周长为 17。核心词是三 角形 ABC, 角、面积、周长都是它的属性, 属性词都是对核 心词的描述。对这个例子中的核心词进行聚类, 聚类的结 果储存在句子关系模板, 表示形式如下: 图 2 篇章中名词聚类整体流程 ( 句子关系 (核心词 三角形 A BC) (类型 名词) ( 相 关属性值 角 ABC 面积 周长) ) ( 2) 在句群中有多个核心词, 每个核心词都有描述它的 属性名词。例如, 三角形 ABC 中, 角 ABC 等于 30 度, 三 角形 ABC 的面积为 20; 四边形 A BCD 的面积为 30, 四边 形的周长为 25, 三角形的周长为 17。核心词 是三角形 A BC 和四边形 ABCD, 描述三角形的属性名词分别是角 A BC、三角形 ABC 的面积、三角形的周长; 描述四边形 A BCD 的属性名词分别是四边形 A BCD 的面积和四边形 的周长。这个例子在进行核心词的汇聚时, 会生成两个句 子关系, 其结果如下: ( 句子关系 (核心词 三角形 A BC) (类型 名词) ( 相 关属性值 角 ABC 面积 周长)) ( 句子关系 ( 核心词 四边形 A BCD ) ( 类型 名词) ( 相关属性值 面积 周长)) 4. 3 利用概念间继承关系的名词聚类 句群 三角形 ABC 中, 角 A BC 等于 30 度, 三角形 A BC 的面积为 20, 四边形 ABCD 的面积为 30, 四边形的周 长是三角形周长的 1. 5 倍, 三角形的周长为 17。! 中, 有表 述两个主体之间关系的句子 四边形的周长是三角形周长 的 1. 5 倍! , 所以在聚类完毕后还要通过主体之间的关系模 板把它们串起来。 4. 4 核心词没有继承关系的名词聚类 为了使知识库简便, 在建立知识库时采用了概念从属 树的形式, 概念从属树描述的是不同概念间的从属关系。 树顶是最抽象的概念, 越往下概念越具体, 概念的内涵逐渐 增加, 外延逐渐减少。概念从属树是一棵与或树, 在不同的 分类标准下, 内涵相近的概念聚成一个集合。例如, 三角形 的概念从属树可以表示成以下的形式: ( 概念从属树 ( 树名 三角形) ( 当前结点 三角形) ( 子结点 锐角三角形 直角三角形 钝角三角形 等腰三角形 等边三角形 内接三角形 圆内接三角形 外切三角形 圆外 切三角形) (分类标准 按角分 按角分 按角分 按边分 按 边分 按与圆位置关系 按与圆位置关系 按与圆位置关系 135 按与圆位置关系)) 在句群 等腰三角形 A BC 中, 角 A BC 等于 30 度, 腰 AB 等于 4, 边 BC 等于 6, 三角形 A BC 的面积为 20, 三角 形的周长为 17! 中, 等腰三角形 A BC 和三角形 ABC 指同 一主体。在进行名词的汇聚时是根据名词的内涵和外延关 系进行汇聚的, 等腰三角形的外延并不包含角、边等外延, 它只包含腰这一外延, 但它会继承其父节点三角形的所有 外延。所以, 在对等腰三角形进行聚类时, 首先找其父节点 三角形, 在三角形的外延中查找角、边的信息是否存在, 然 后进行聚类。聚类的结果应该如下: (句子关系 ( 核心词 等腰三角形 ABC) ( 类型 名词) ( 相关属性值 角 A BC 腰A B 边BC 面积 周长)) 。 5 结束语 聚类问题是指由于对某一概念的离散性描述所引起 的, 如对某一概念不同层面的描述或对概念各个属性的描 述, 收集此概念的描述和此概念相关属性的描述, 我们就可 以比较全面地得到该概念所包含的信息。在自然语言理解 中, 聚类对提取篇章中心意思具有很重要的作用。不仅如 此, 通过聚类还可以确定事件发生的领域。经过后期知识 库的进一步完善, 这个成功率还会稳步上升。而且, 聚类的 思想在机器翻译、信息检索方面还有不可估量的应用前 景[4,5] 。 参考文献: [ 1] 朱 明. 数 据 挖掘 [ M] . 合 肥: 中 国 科学 技 术 大 学 出版 社, 2002. [ 2] 吴中 兴, 赵克, 胡钢伟, 等. 概念从属 树 ∀ ∀ ∀ 一种新的 树模型 设计[ J] . 计算机应用, 2004, 24( S1) : 99100. [ 3] 余以胜, 张玉峰. 基于本体论的 知识库系 统研究[ J] . 情报杂 志, 2003, 22( 7) : 23. [ 4] van Eijck J, Kamp H . Representing Discourse in Context[ M] %Johan B, Aliceeds Meds. H andbook of Logic and Lan guage. MIT Press, 1997: 178237. [ 5] Dean T, Allen J, Alomonos Y, et al. Artificial Intelligence: T heory and Practice [ M ] . Publishing House of Electr onics Industry, 2002: 489 537. [ 6] [ 美] Allen J. 自然语言理解[ M] . 第二版. 刘群, 张华平, 骆卫 华, 等译. 北京: 电子工业出版社, 2005. [ 7] 石纯一, 黄昌宁, 王家钦. 人工智能 原理[ M ] . 北京: 清 华大学 出版社, 1993. [ 8] [ 美] Jurafsky D, Martin J H . 自然 语言 处理综 论[ M ] . 冯志 伟, 孙乐译. 北京: 电子工业出版社, 2005. ( 上接第 88 页) 低和 Cache 失效率增高, 但同时多线程体系结构有很强的 分支误预测容忍能力。研究表明[ 8] , 当分支预测器的误预 测率上升 2 到 3 倍时, 同时多线程处理器性能只下降 2% 。 而且同时多线程体系结构对存储系统的延时也不敏感[9] , 只要有效控制发生 Cache 失效的线程对队列类共享资源的 占用, 使其不会影响队列类共享资源的利用效率, 那么 Cache 失效的增加并不会导致处理器性能降低。 5 结束语 本文从同时多线程处理器体系结构模型出发, 深入分 析了同时多线程处理器中的三类共享资源: 槽类、队列类和 存储类。对于槽类共享资源, 由于线程对该类资源的占用 在一个周期内即可完成, 线程之间的干扰非常小, 因此对处 理器性能不会造成太大的影响; 对于存储类共享资源, 由于 其属于可抢占式资源, 也不会导致资源阻塞; 而控制各个线 程对队列类共享资源的使用是关键, 通过提高队列类共享 资源的利用效率可以提高槽类共享资源的利用率, 从而提 高处理器性能。因此, 队列类共享资源的分配对每个线程 执行的性能和处理器的性能至关重要。 参考文献: [ 1] Tullsen D, Eggers S, Levy H M. Simultaneous Multithreading: Maximizing OnChip Parallelism[ C] %Proc of the 22nd Annual Int l Symp on Computer Architecture, 1995: 392403. [ 2] Lo J L, Eggers S J, Emer J S, et al. Converting T hreadLevel Parallelism into Instruction Level Parallelism via Simultane ous Multithr eading[ J] . ACM Trans on Com puter System s, 1997, 15( 3) : 322354. [ 3] Eggers S J, Emer J S, Levy H M, et al. Simultaneous Mul tithreading: a Platform for NextGeneration Processors[ J] . IEEE Micro, 1997, 17( 5) : 1219. [ 4] Seungryul C. H illclimbing SMT Processor Resource Distri bution: [ Ph D Thesis] [ D] . University of Maryland, 2006. [ 5] Tullsen D. Simulation and Modeling of a Simultaneous Mul tithreading Processor[ C] %Proc of the 22nd Annual C om put er Measurem ent Group Conf, 1996: 819828. [ 6] Tullsen D, E ggers S J, Emer J S, et al. Exploiting Choice: Instruction Fetch and Issue on an Im plem entable Simultane ous Multithr eading Pr ocessor[ C ] %Proc of the 23rd Annual Int l Symp on Com puter Architecture, 1996: 191202. [ 7] Seungryul C, Yeung D. LearningBased SMT Processor Re source Distr ibution via HillClimbing [ C ] %Proc of the 33rd Int l Symp on Com puter Architecture, 2006: 239251. [ 8] Ramsay M, Feucht C, Lipasti M. Exploring Efficient SMT Branch Predictor Design[ C] %Proc of Workshop on Com plexityEffective Design, 2003. [ 9] Baboescu F, Tullsen D. M emory Subsystem Design for Mul tithreaded Processors[ R] . T echnical Report UCSD, 1997. ( 上接第 132 页) [ 2] 周志新, 刘雪立. 科技 期刊在 线投稿 系统应 用中的 问题分 析 及对策[ J] . 编辑学报, 2006, 18( 6) : 435436. [ 3] 孙卫秦. 精通 Struts: 基于 MVC 的 JAVA Web 设计 与开 发 [ M] . 北京: 电子工业出版社, 2005: 915. [ 4] Liu V, Gorton I, Fekete A. DesignLevel Performance Predic tion of C om ponentBased Aplications [ J] . IEEE Trans on Software Engineering, 2005, 31( 11) : 928931. [ 5] 曾亮, 齐欢, 王小平, 等. 基于 J2EE 核心模 式的 组合 Web 框 架研究[ J] . 华中科技大 学学报( 自然科学 版) , 2007, 35( 6) : 4346. [ 6] T ed Husted Struts in Action[ M] . Or eilly & Associates Inc, 2005: 4149. 136
还剩3页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 2 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

suny6wang

贡献于2014-05-15

下载需要 2 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf