·368 智能系统学报 第11卷 若干个关键词向量来表征一篇文档，通过计算关键 则的变动形式，如同一个人酒后乱步，所形成的随机 词向量间的余弦相似度得出它们之间的关联程度， 过程记录6。它的基本思想是，从一个或一系列顶 进而得出文档之间的相似度。 点开始遍历一张图，在任意一个顶点，遍历者将以概 l.2 TextRank算法 率1-α游走到这个顶点的邻居顶点，以概率α随机 同一文档中的大多数词语都是为表达同一主题 跳跃到图中的任何一个顶点，称α跳转发生概率， 服务的，它们之间具有一定的语义关系。和词语W 每次游走后得出一个概率分布，该概率分布刻画了 有语义关系的词语越多，词语W越可能是表达文档 图中每一个顶点被访问到的概率，用这个概率分布 主题的重要词语，同时和词语W有语义关系的词语 作为下一次游走的输人并反复迭代这一过程，当满 的重要性也会影响词语W的重要性。根据这两个 足一定前提条件时，这个概率分布会趋于收敛，收敛 特性，本节引入基于图的排序算法用于抽取多文档 后，即可以得到一个稳定的概率分布。近年来，随机 关键词。基于图的排序算法是决定图中点重要性的 游走算法逐渐开始吸引机器学习研究者的目光，并 一种方法，它根据全局信息（图的结构）而不是局部 开始被应用于半监督学习.1】、聚类分析192】、图 信息来对节点排序。其基本理论是“投票”，当图中 像分割[]和图的匹配[]等问题上。与随机游走相 一个点A和另一个点B之间有连线时，那么点A就 关的扩散核也被应用于242)基于核的学习等方面。 给点B投票，点B获得的投票越多，点B就越重要； 由于实体间的关系错综复杂，可以将这种关系 更进一步，投票点A的重要性决定了其投票的重要 抽象为一种图模型，本文在这种图模型上运用随机 性，因此，点B的分数由其获得的投票和给B投票的 游走算法可以将实体间的关联程度准确地表征 点的分数共同决定。 出来。 Mihalcea14]将在自然语言处理领域中应用的 2领域实体消歧 基于图的排序算法称为TextRank,一般TextRank模 型可以表示为一个加权的有向图。TextRank的思想 2.1系统流程 来源于Google的PageRank算法，通过把文本分割 本文提出的方法由4个模块构成分别为关键词 成若干组成单元并建立图模型，利用投票机制对文 提取模块、词向量模块、图模型模块和空实体判断 本中的重要成分进行排序，仅利用单篇文档本身的 模块。 信息即可实现关键词抽取。本文采用该算法将文档 在关键词提取模块中，分别利用TextRank算法 表示为无向图G(V,E),由点集合V和边集合E组 提取出待消歧的实体指称所在的背景文本的若干关 成，E是V×V的子集，图中两点i,j之间边的权重为 键词和候选实体对应的知识库描述文本的若干关键 W。对于一个给定的点V:,n(V)为指向该点的点 词，这里提取的两组关键词用于后面的相似度计算。 集合，Out(V:)为点V指向的点集合，点V,的分数 在词向量模块中，抽取维基百科离线数据中旅 定义为式(2)： 游分类下的页面信息构建领域知识库，由于维基百 Ws(V)=(1-d)+d×∑ 10 科中包含大量的结构化信息，取该知识库的摘要信 —WS(V) a(∑ 0声 息作为语料对词向量模型进行训练，这时，领域实体 VeOu(V) 都能通过该模型表征为一个向量，从而实现关键词 (2) 之间的相似度计算。 式中：d为阻尼因数，取值范围为0~1，代表从图中 在图模型模块中，人工构建一个领域实体关系 某一特定点指向其他任意点的概率。通过这种算法 图谱，通过在该图谱上的随机游走算法实现关键词 我们可以获得每个词语在文档中的分数，从而可以 之间相似度的计算。 根据分数大小来进行关键词的排序。 在空实体判断模块中，从待消歧实体指称所在 本文利用该算法抽取文档中的关键词，分别用 的文本中抽取若干关键词和从候选实体所在文本中 抽取的关键词来表征待消歧实体指称项所在文本和 抽取的关键词分别用本文提出的图模型与词向量方 目标实体所在文本。 法相结合进行交叉相似度计算取平均值，选择其中 1.3随机游走算法 最大的相似度平均值，因为计算结果所对应的目标 随机游走模型是在1905年Karl Pearsonti]首 实体未必在我们的知识库中存在，这时通过比对该 次提出的一种数学统计模型，它是一连串的轨迹组 平均值与通过大量实验确定的空实体阈值入的大 成的，其中每一次都是随机的。它能用来表示不规 小，如果大于该阈值入，则该实体为目标实体，如果若干个关键词向量来表征一篇文档，通过计算关键 词向量间的余弦相似度得出它们之间的关联程度， 进而得出文档之间的相似度。 １．２ ＴｅｘｔＲａｎｋ 算法 同一文档中的大多数词语都是为表达同一主题 服务的，它们之间具有一定的语义关系。 和词语 Ｗ 有语义关系的词语越多，词语 Ｗ 越可能是表达文档 主题的重要词语，同时和词语 Ｗ 有语义关系的词语 的重要性也会影响词语 Ｗ 的重要性。 根据这两个 特性，本节引入基于图的排序算法用于抽取多文档 关键词。 基于图的排序算法是决定图中点重要性的 一种方法，它根据全局信息（图的结构） 而不是局部 信息来对节点排序。 其基本理论是“投票”，当图中 一个点 Ａ 和另一个点 Ｂ 之间有连线时，那么点 Ａ 就 给点 Ｂ 投票，点 Ｂ 获得的投票越多，点 Ｂ 就越重要； 更进一步，投票点 Ａ 的重要性决定了其投票的重要 性，因此，点 Ｂ 的分数由其获得的投票和给 Ｂ 投票的 点的分数共同决定。 Ｍｉｈａｌｃｅａ ［１ ４ ］将在自然语言处理领域中应用的 基于图的排序算法称为 ＴｅｘｔＲａｎｋ，一般 ＴｅｘｔＲａｎｋ 模 型可以表示为一个加权的有向图。 ＴｅｘｔＲａｎｋ 的思想 来源于 Ｇｏｏｇｌｅ 的 ＰａｇｅＲａｎｋ 算法，通过把文本分割 成若干组成单元并建立图模型，利用投票机制对文 本中的重要成分进行排序，仅利用单篇文档本身的 信息即可实现关键词抽取。 本文采用该算法将文档 表示为无向图 Ｇ（Ｖ，Ｅ），由点集合 Ｖ 和边集合 Ｅ 组 成，Ｅ 是 Ｖ×Ｖ 的子集，图中两点 ｉ，ｊ 之间边的权重为 Ｗｊ。 对于一个给定的点 Ｖｉ，Ｉｎ（Ｖｉ）为指向该点的点 集合，Ｏｕｔ（Ｖｉ ） 为点 Ｖｉ 指向的点集合，点 Ｖｉ 的分数 定义为式（２）： ＷＳ（Ｖｉ） ＝ （１ － ｄ） ＋ ｄ × Ｖ ∑ ｊ∈Ｉｎ（Ｖｉ ） ｗｊｉ Ｖ ∑ｋ∈Ｏｕｔ（Ｖｉ ） ｗｊｋ ＷＳ（Ｖｊ） （２） 式中：ｄ 为阻尼因数，取值范围为 ０ ～ １，代表从图中 某一特定点指向其他任意点的概率。 通过这种算法 我们可以获得每个词语在文档中的分数，从而可以 根据分数大小来进行关键词的排序。 本文利用该算法抽取文档中的关键词，分别用 抽取的关键词来表征待消歧实体指称项所在文本和 目标实体所在文本。 １．３ 随机游走算法 随机游走模型是在 １９０５ 年 Ｋａｒｌ Ｐｅａｒｓｏｎ ［１５］ 首 次提出的一种数学统计模型，它是一连串的轨迹组 成的，其中每一次都是随机的。 它能用来表示不规 则的变动形式，如同一个人酒后乱步，所形成的随机 过程记录［１６］ 。 它的基本思想是，从一个或一系列顶 点开始遍历一张图，在任意一个顶点，遍历者将以概 率 １－α 游走到这个顶点的邻居顶点，以概率 α 随机 跳跃到图中的任何一个顶点，称 α 跳转发生概率， 每次游走后得出一个概率分布，该概率分布刻画了 图中每一个顶点被访问到的概率，用这个概率分布 作为下一次游走的输入并反复迭代这一过程，当满 足一定前提条件时，这个概率分布会趋于收敛，收敛 后，即可以得到一个稳定的概率分布。 近年来，随机 游走算法逐渐开始吸引机器学习研究者的目光，并 开始被应用于半监督学习［１７⁃１８］ 、聚类分析［１９⁃２１］ 、图 像分割［２２］和图的匹配［２３］ 等问题上。 与随机游走相 关的扩散核也被应用于［２４⁃２８］基于核的学习等方面。 由于实体间的关系错综复杂，可以将这种关系 抽象为一种图模型，本文在这种图模型上运用随机 游走算法可以将实体间的关联程度准确地表征 出来。 ２ 领域实体消歧 ２．１ 系统流程 本文提出的方法由 ４ 个模块构成分别为关键词 提取模块、词向量模块、图模型模块和空实体判断 模块。 在关键词提取模块中，分别利用 ＴｅｘｔＲａｎｋ 算法 提取出待消歧的实体指称所在的背景文本的若干关 键词和候选实体对应的知识库描述文本的若干关键 词，这里提取的两组关键词用于后面的相似度计算。 在词向量模块中，抽取维基百科离线数据中旅 游分类下的页面信息构建领域知识库，由于维基百 科中包含大量的结构化信息，取该知识库的摘要信 息作为语料对词向量模型进行训练，这时，领域实体 都能通过该模型表征为一个向量，从而实现关键词 之间的相似度计算。 在图模型模块中，人工构建一个领域实体关系 图谱，通过在该图谱上的随机游走算法实现关键词 之间相似度的计算。 在空实体判断模块中，从待消歧实体指称所在 的文本中抽取若干关键词和从候选实体所在文本中 抽取的关键词分别用本文提出的图模型与词向量方 法相结合进行交叉相似度计算取平均值，选择其中 最大的相似度平均值，因为计算结果所对应的目标 实体未必在我们的知识库中存在，这时通过比对该 平均值与通过大量实验确定的空实体阈值 λ 的大 小，如果大于该阈值 λ，则该实体为目标实体，如果 ·３６８· 智 能 系 统 学 报 第 １１ 卷