Lucene和Nutch解决问题查询的软件知识图谱

这篇论文提出并实现了软件项目知识图谱的自然语言问题接口。它提取软件知识库的元模型，构造与问题相关的推理子图，然后自动将自然语言问题转换为结构化的Cypher查询并返回相应的答案。利用开源软件项目Lucene和开源软件项目Nutch的知识图来评估该方法。结果表明，这种方法能够有效地回答开发人员提出的自然语言问题，从而实现软件重用。在未来，作者及其团队也将尝试通过增加人机交互来解决更复杂的自然语言问答问题。

2 摘要

研究人员在不同的领域建立了各种知识库，这些知识库通常使用图形数据库（Neo4j）来管理异构和联系较为宽泛的领域数据，提供结构化查询接口，比如Cypher。然而，构造一个结构化查询是非常耗时和消耗人力的，特别是当查询非常复杂或知识图谱的规模很大时。这篇论文提出了一种面向软件知识图谱的自然语言问题接口。它提取软件知识库的元模型，构造与问题相关的推理子图，然后自动将自然语言问题转换为结构化的Cypher查询并返回相应的答案。该项目在两个著名的开源软件项目上进行了实验，建立了它们的知识图，验证了其所采用的方法确实能够准确地回答相应知识图谱上的几乎所有问题。

3 介绍

软件重用是一种避免软件开发重复效应的解决方案，它可以提高软件工程的效率和质量。近年来，随着开源软件的迅速发展，互联网上出现了大量可重用的软件项目，如Apache Lucene、Apache POI、jfreeChart等，这些软件项目除了源代码外，还经常包含不同类型的自然语言文本资源，如用户手册、邮件列表等，问题报告、用户论坛讨论等。为了利用和分析这些文档和源代码，研究人员提出并构建了各种领域专用的软件知识库和知识图谱。典型地，北京大学提出了特定领域的软件项目知识图谱，复旦大学提出了软件项目API知识图谱等等。

这些知识库或知识图谱通常使用Neo4j和其他支持形式查询（即Cypher）的图形数据库存储，要求用户熟悉Cypher语法，并由用户手动将其查询意图转换为Cypher查询语句。同时，手工构造Cypher查询语句需要对知识图谱的元模型有一个清晰的认识，比如知识图谱中的知识实体类型。当元模型规模很大时，构造Cypher查询的成本也很大。因此，有必要提供一个基于自然语言的知识库或知识图谱查询接口，能够自动将用户的自然语言问题转化为形式化的查询语句。

图 1查询问题和相关推理子图（ISG）

为了解决这一问题，现有的自然语言问题解析过程中的工作往往依赖于Internet上的大型通用领域知识库（如WordNet、DbPydia、FrutBASE、Yago等），其计算非常复杂。典型地，Percy Liang等人利用Lambda-DCS（Dependency-Based Composition Semantics）获得自然语言问题的逻辑表示，并基于其逻辑表示构造知识库或知识图谱的形式化查询。然而，所有这些方法都面临着自然语言描述精确转换的挑战。在我们的研究中，我们发现由于特定领域软件的特性，软件知识图谱中的概念与一般开放领域知识库中的概念有很大的不同。因此，匹配特定的谓语短语并不重要。相反，我们应该更加注重对问题整体语义的精确分析。上面图1给出了一个来自开发人员的自然语言问题及其相应的结构化Cypher查询语句的构造过程。当软件开发人员重用ApacheLucene的开源项目时，他们会提出这样的问题：“Alex写的哪个问题修改了IndexWriter调用的方法?“，此语句中包含的关键字是issue、Alex、modify、method、call、IndexWriter等。每个关键字在知识图上都有几个概念与之对应。例如，Alex可以匹配到知识图谱上具有name属性的Person实体，但是知识图谱有两个相似的概念实体，即gitAuthor:Alex developers和SoUser:Alex（stackOver flow users）。类似地，IndexWriter可以与知识图谱上实体的软件项目源代码知识相匹配，但它可以与类、方法和字段这三个级别的实体相匹配。那么开发人员想要传达的概念是什么呢？哪些概念对应于知识图谱实体？为了解决自然语言标记与知识图谱实体之间的精确匹配问题，我们提出了一种在自然语言问题对应的知识图谱中推理和定位子图的方法，称为推理子图。推理子图是从自然语言问题到Cypher查询语句的中间桥梁：推理子图的生成需要深入分析，需要利用知识图谱信息和知识图谱元模型来“匹配”自然语言问题中的语义。

在此基础上，提出了一种基于软件知识图谱的自然语言查询方法。通过提取软件知识图谱元模型，构造推理子图，将自然语言问题精确地转化为结构化的Cypher查询，并在知识图谱上显示相应的答案。与当前工作相比，本文的主要贡献有两点：

\1. 提出了一种将自然语言问题转化为形式Cypher查询的新方法。与传统的语义分析不同，该算法生成一个推理子图作为自然语言和形式查询之间的转换桥梁，能够更准确地表达自然语言的深层含义。另一方面，通过测量推理子图可以显著地解决自然语言的歧义问题；

\2. 实现了一个自然语言问题接口，并在Apache Lucene和Apache Nutch的开源项目的软件项目知识图谱上验证了该方法。在软件使用过程中，对于每一个知识图谱提供了66个真实的自然语言问题，准确率为93.9%。

4 综述：

在这篇论文中提出并实现了一种基于软件知识图谱的自然语言问答方法和系统：提出了推理子图的概念，并通过生成和度量推理子图，在自然语言问题和形式查询语句之间建立了一个转换桥梁。一方面，与传统的语义分析逻辑形式系统相比，子图转换方法更容易表达自然语言的语义信息。另一方面，推理子图的生成和度量可以解决自然语言的歧义问题。图2显示了本文所述方法的工作流程。该方法主要包括四个部分：（1）提取知识图谱元模型；（2）自然语言问题的解析与匹配；（3）推理子图的生成与度量；（4）构造Cypher查询语句。

图 2自然语言问答解决方案的工作流

4.1提取软件项目知识图谱元模型

为了适应不同的软件项目知识图谱，该方法定义了以下概念：（1）实体类型：知识图谱中的每个实体都有一个类型。它定义为：{Entity Type}={Entity.Type}。（2）关系类型：知识图谱中的每种关系类型由关系本身的名称和关系两端的实体类型决定。它定义为：{Relation Type}={（Relation.start.Type，Relation.end.Type，Relation.name）}。（3）属性类型：知识图谱中每个属性的类型由其关联的实体类型和属性名决定。它定义为：{Attribute Type}={（Attribute.entity.Type，Attribute.name）}。（4）元模型：实体类型为节点，关系类型为边，属性类型为实体类型属性的模式图。它定义为：元模型={实体类型}，{关系类型}。基于上述概念，遍历软件项目知识图谱，存储其中的所有实体，并将所有实体类型记录为元模型的实体，然后遍历软件项目知识图谱，将所有关系存储在其中，并将所有关系类型记录为元模型的关系。

4.2分析和匹配自然语言问题

在本小节中，使用斯坦福NLP工具分析自然语言问题，包括标记段、词性和过滤停用词，然后将这些标记与知识图谱中的元素进行匹配，提出了一种基于优先级的匹配算法，即将每个令牌（即自然语言问题的解析）与来自知识图谱或知识图谱元模型的元素进行分层匹配。每个令牌可以匹配到知识图谱的任何元素，包括：实体、实体类型、属性、属性类型以及关系、关系类型等，基于软件工程特定领域的知识手动构造同义词表，例如，自然语言问题是：“何时Yonik Seeley更改了调用updatependingmerge方法的类？”显然，我们可以将类与知识图谱中的实体类型—类匹配，同样，也可以将updatependingmerge与知识图谱中的实体—名为updatependingmerge的方法匹配。但是，因为不能直接使用call和changd来匹配任何元素，所以使用同义表来匹配某些同义词（例如，使用关系“call method”调用匹配，使用关系“commit”匹配changed等等），显然，一个令牌可能匹配多个元素。为了解决这个问题，使用了最小编辑距离算法来计算令牌和元素之间的相似度，这样就可以过滤一些不相关的元素。但是，该方法仍然保留了一些模糊匹配对，在后一种方法中可以消除这种模糊。最后如上文图1所示，得到一个{tokens，elements}匹配图。

4.3生成和度量推理子图

由于自然语言的模糊性和复杂性，基于自然语言处理的令牌可以与不同的知识图形元素相匹配，从而得到具有多种语义的候选子图。为了保证候选子图的质量，提出了一种扩展隐节点和隐边的推理子图生成算法，并计算了每个候选推理子图的特征值。测量特征包括三个方面：文本相似度、结构相似度和推理子图结构复杂度，然后根据测量结果向开发者推荐最优推理子图。在这个过程中，一方面，建立了自然语言与形式查询语句之间的中间转换桥梁，另一方面，通过测量最优子图来解决自然语言的歧义问题。最后，将最优推理子图转换为Cypher查询语句并返回查询结果。为了防止可能的语义理解偏差，还支持交互过程中推理子图的可视化。在下一节中，将详细介绍推理子图的生成和度量。

4.4构造Cypher查询语句

将推理子图转换为一个Cypher查询语句。构造Cypher的过程可以分为三个部分，分别对应于Match、Where和Return语句。–Match语句对应于推理子图的图结构。然而，推理子图表示二维结构信息，一个Match语句只描述一维结构信息—链。因此，我们采用启发式的方法将推理子图上的路径划分为若干个链和集合。–Where语句对应于推理子图中节点的所有属性值，每个属性值是实体的过滤条件，因此属性被添加到Where语句中。–Return语句由返回的节点属性确定。返回的节点属性由问题中的疑问词确定。

5 生成和度量推理子图

在第2.2节中，解析自然语言问题后，它们的标记可以匹配到多个知识图谱元素。为了保证句子整体意义的正确性，提出了推理子图的概念，并给出了相应的推理子图生成和度量算法。推理子图：推理子图是知识图谱中的一个子图，包括：实体和边，该子图是由自然语言问题和知识图谱中的{tokens，elements}对推断出来的，因此该子图包含与自然语言问题相似的语义。

5.1生成推理子图

推理子图是知识图谱元模型上的一个子图。由于自然语言的模糊性，自然语言的语义往往是不完整的。如图1所示，在自然语言问题“Alex编写的修改IndexWriter调用方法的问题”的例子中，我们需要在实体类（即IndexWriter）和IndexWriter调用的实体方法之间扩展一个隐藏的方法实体节点（即method）和一个隐藏的关联关系（即have_method）。也就是说，自然语言问题的完整语义应该是：由于Alex提出的问题而修改方法，并且该方法由类IndexWriter中的方法成员方法调用。为了解决这个问题，我们提出了一种新的方法，称为推理子图。算法1说明了推理子图的生成过程。输入是一组断开连接的子图，根据{tokens，elements}匹配图从知识图谱中提取（第2.2节）。输出是一组连通的推理子图。首先，如第2-6行的算法所示，通过解析自然语言问题和知识图谱中的匹配元素，得到一个匹配图。由于自然语言的模糊性，每一个自然语言标记可能对应于多个知识图相关元素。我们在前一个过程中保留了这些含糊不清之处。使用Bean搜索算法连接所有可能的{token，elements}匹配图，从而获得一组候选的断开子图，即Sdisconnect=Gdisconnect。每个集合表示与自然语言问题相对应的知识图谱元素集合的可能性。然后，在算法1的第7-11行中，通过推理知识图来扩展断开子图的隐藏节点，得到具有隐藏节点和隐藏边的图，即Shidden=Ghidden。最后，在算法1的第12-17行中，使用最小生成树算法连接这些断开的子图，从而得到一组连接的推理子图，即Sconnect。

图 3-算法1

5.2测量推理子图

在上述步骤中，生成了一组推理子图，必须从中选择最优推理子图作为带有Cypher查询语句的桥。

文中提出了一系列启发式规则来计算被测特征：（1）第2.2节中推理子图与NL问题的文本相似度，如图1所示，保留了一些与令牌匹配的候选元素，即每个令牌都有一个候选元素列表，此列表中的每个元素都有一个与令牌相似的秩，因此，我们可以计算推理子图与自然语言问题之间的相似性，如下所示：

在上面的公式中，t表示解析自然语言问题（第4.2节）中的标记，t.mapping.rank表示候选列表中元素的秩，k表示匹配图中所有元素的数目，ωt-similar表示特征集中文本相似性的权重，可以手动指定权重值。

（2）推理子图与自然语言问题的结构相似性

计算推理子图与自然语言问题的结构相似性，我们将推理子图中节点对之间的相对距离与自然语言问题中对应词的相对距离之差作为度量因子。结构相似性计算如下：

6 实验与评价

基于上述解决方案，设计并实现了一个软件项目知识图的自然语言问答系统SnowSearch（software knowledge Search）。该实验用于回答以下研究问题：

研究问题1：SnowSearch是否有效地回答了自然语言问题？

当开发人员输入一个自然语言问题时，该方法是否能够有效地返回正确的查询结果。

研究问题2：推理子图解决了自然语言和Cypher查询之间的转换吗？

提出了一种基于知识图的推理子图方法，作为自然语言与形式化查询语句之间的桥梁。该方法关心的是推理子图能否更有效、更准确地表达自然语言。

研究问题3:推理子图的三个度量特征是否合理？

提出了文本相似度、结构相似度和推理子图复杂度的三个度量指标来度量推理子图，从而得到最优子图。

6.1软件项目知识图谱

以下工作是基于Lin等人提出的软件项目知识图谱。软件知识图谱被定义为表示软件领域、项目和系统中相关知识的图。在软件知识图谱中，节点表示软件知识实体（例如类、问题报告和业务概念），有向边表示这些实体之间的各种关系（例如方法调用和可追溯性链接）。基于他们的工具，可以自动构建一个软件项目知识图谱。为了评估所用方法，构建了两个著名的开源软件项目Apache Lucene和Apache Nutch的知识图谱。开源项目Lucene是一个Java实现的信息检索程序库；开源项目Nutch是一个Java实现的开源搜索引擎。我们在互联网上的Lucene和Nutch上收集了大量的多源异构数据，包括软件源代码、邮件列表、问题报告和StackOver-flow帖子。相关资源统计见下面的表1。例如，开源项目Lucene是一个用Java语言实现的广为人知的信息检索库。我们在互联网上收集了超过8GB的Lucene项目数据，包括67个版本、80多万行源代码、24.4万封电子邮件、7500多份问题报告以及大量相关的StackOver Flow帖子。最后构造了Apache-Lucene的知识图谱，图的统计如下面表2所示。

表 1--Apache-Lucene的资源统计表

表 2--软件项目知识图谱的元模型

6.2问题示例

邀请了四位熟悉Apache Lucene和Nutch的开发人员来问一些与这两个项目相关的自然语言问题。这些问题主要涉及事实问题，如谁、什么、何时和列表。最后，四位开发人员提出了关于Lucene项目的66个问题和关于Nutch项目的66个问题。如下表3所示，随机选择了22个开发人员向Lucene开源项目提出的示例问题。其中，推理子图中与What或Which类型、Who类型和When类型相关的实体数平均约为4个，推理子图中的边数平均约为3个。列表型问题对应的推理子图中的实体数平均约为97个，推理子图中的边数平均为96左右，22个自然语言问题实例的数据分析结果表明，软件重用过程中开发人员提出的自然语言问题客观存在，对知识库查询具有一定的推理复杂度和问答能力。

表3--使用Lucene知识图谱搜索的问题

表 4--Lucene and Nutch项目的132个精确结果展示

6.3 研究问题1：问答效果评估

仅需考虑TOP-1和TOP-2的每一项精度，即可进行问答效果评估。也就是说，生成的正确的Cypher查询在所有可能的Cypher候选集中排名在前k位，因此问答结果是正确的。实验结果见上表4。由此可见，Lucene项目知识图的66个问题中，有62个问题返回了正确的Cypher queryintop-1，64个问题返回了正确的Cypher queryintop-2。Nutch项目知识图谱的66个问题得到了相同的实验结果，这表明不同软件项目的大多数自然语言问题都可以返回正确的Cypher queryintop-1回答正确。实验结果表明，本文提出的基于软件项目知识图谱的自然语言问答方法的正确率达到93.3%以上。考虑到列表型问题的自然语言语法比较复杂，推理子图中对应的实体比较复杂，自然语言问题的解析和匹配可能会产生一定的错误。例如：在自然语言问题“列出所有提到IndexWriter的JiraIssue”中，由于JiraIssue和IndexWriter涉及大量实体，导致自然语言问题的回答失败。对于其他问题，比如什么或哪一个，什么时候，谁，这种方法都有很好的问答效果。

6.4 研究问题2：推理子图有效性评价

推理子图是自然语言和形式查询语句之间的桥梁。为了更好地表达自然语言问题的完整语义，在生成推理子图的过程中，我们必须扩展隐藏节点和隐藏边，例如，在自然语言问题示例中，如图1所示“Alex编写的修改IndexWriter调用的方法的问题”，需要添加三个隐藏节点，即method、gitAuthor和Commit，以及两个隐藏边，即方法和代码说明。为了验证推理子图在自然语言到形式查询转换中的作用，该方法统计分析了推理子图中添加的隐藏节点元素的数量。如图3所示，Apache Lucene中64%的问题需要在推理子图中添加隐藏节点，如图4所示，Apache Lucene中55%的问题需要在推理子图中添加隐藏边。Apache Nutch项目中也提供了相同的统计数据。这说明在将自然语言问题转换为形式化查询语句的过程中，超过一半的自然语言问题需要扩展。如果不使用推理子图来扩展隐藏的节点和边，而只是简单地组合自然语言标记并构造形式化查询，那么一半以上的自然语言问题就无法得到正确的答案。因此，本文提出的推理子图可以有效地解决自然语言与Cypher查询之间的转换问题。

图3 Lucene搜索问题时推理子图中隐藏节点和边的分布

图4 Nutch搜索问题时推理子图中隐藏节点和边的分布

6.5 研究问题3：测量策略比较评价

该方法设计了一系列的比较实验，以比较三个度量的测量结果：“文本相似度+结构相似性”、“文本相似度+结构复杂性”、“结构相似性+结构复杂性”，从而验证了度量中的每个度量。下图5实验结果表明：如下图图5所示，考虑到top-1中正确的Cypher，仅两个测量特征的精度就约为50%，而本方法（三个测量特征的组合）的精度高达94%，考虑到top-2中正确的Cypher，“文本相似度+结构相似性”、“文本相似度+结构复杂度”和“结构复杂性+结构相似性”的测量策略的准确率分别为55%、63%和59%，而本方法的准确率可以达到97%。这意味着，如果我们放弃任何度量特征，问题回答的准确性将急剧下降。这也证明了我们提出的三个指标是合理的。

图 5三种测量方法比较分析的精确结果

7 相关工作

许多工作试图为图形数据库或知识构建一个自然语言查询接口，该接口大多采用NoSQL数据库。现有的研究主要包括：（1）基于句法分析的方法；（2）基于机器学习的方法。基于句法分析的方法的基本过程是：首先对自然语言查询进行解析，构造自然语言查询的句法依赖树，然后通过节点匹配、规则扩展等方法进行查询转换，得到最终的形式化查询语句。通常，Berant等人提出训练一个语义解析器，用于在知识库上进行自然语言问答。其基本过程是：利用经过训练的语义分析器将输入的自然语言问题解析成一个逻辑形式系统，然后基于结构化逻辑表达式从知识库中搜索答案；基于DCS-L、Yao等的工作。在知识库中定位候选实体，构建主题图作为候选答案，为自然语言问题和候选答案实体建立特征向量，并将原始问题转化为候选答案的二元分类。这种方法的优点之一是基于形式化查询结果，用户可以确定查询结果的可靠性。但是在这些研究工作中，用户在自然语言查询中输入的单词仍然需要与数据库表中的某个信息（表名、属性名、记录等）显式对应，否则语法树不完整，无法得到正确的答案。

在基于机器学习方法的自然语言查询应答库的研究中，早期的工作主要是在用户进行查询时记录信息，并根据历史查询信息辅助下一次查询。Freitas等人利用交互式算法优化查询结果，设计用户反馈方法，提高查询精度。其基本思想是在用户输入查询时记录反馈信息，然后利用历史查询辅助下一次查询输入。此方法可以优化大多数方法，但需要更频繁地使用它来累积用户的使用历史。Tunstall Pedoe等人在生成模板的过程中利用人的因素，从雅虎和其他社区的现有问题中提取正确的自然语言问题模板。最近的其他代表性工作主要依赖于机器学习，包括序列模型、神经网络模型、注意机制等。尤其是深度学习已经成为知识库自然语言问答的主要技术之一。 Wen-tauYih 等人定义了一种查询子图方法，查询子图可以直接从知识库转换为逻辑形式系统，语义解析的任务是生成查询子图，利用知识库进行物理前链索引，并用Deep-CNN计算问题与逻辑谓词的匹配度，得到显著效果。