《知识网络中的关联推理.docx》由会员分享，可在线阅读，更多相关《知识网络中的关联推理.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、知识网络中的关联推理摘要网络大数据时代的到来使得知识网络中时空信息越来越丰富现有的知识网络描绘模型对知识的时空信息刻画缺乏研究证实，利用网络中知识的时空信息以及相关性，能够提高网络中知识间的关联推理的准确率针对以上问题，首先提出了一种包含时空信息的演化知识网络表示模型，然后研究在该网络模型上的关联推理问题，提出了一种基于背包问题的知识间关联推理方法在多个数据集上的实验证实了所提出的关联推理方法的有效性以及对大规模知识网络的适应性关键词关联推理；演化知识网络；背包问题；链接延展形式；知识库网络大数据时代，数据不再仅仅是简单的采集对象，其背后其实蕴含着大量丰富、复杂、关联的知识当前网络数据是广泛可
2、用的，所缺乏的只是从中提取知识的能力有效利用网络大数据价值的主要任务不仅仅是是获取越来越多的数据，也需要从已有的数据中挖掘更多有用的知识，构建成知识库，便于对知识更充分地利用，因而基于网络的大规模知识库的构建是近期流行的一个研究方向，现有的大规模知识库有，等基于大规模知识库的关联推理是从海量信息中挖掘知识实现知识库增长的有效手段之一，其主要目的是利用已有的大规模知识网络推理或者预测知识网络中隐含的关系目前，关联推理已经在个性化推荐、社区发现、知识问答等方面得到广泛应用现有的关于知识网络中关联推理的研究，采用的方法主要有有监督学习、半监督学习以及无监督学习等目前的研究更多的是基于异构信息网络的关
3、联推理，这里的异构信息网络包含多种不同类型的实体与关系，例如人物、地点、组织机构、电影、论文等，以及它们之间可能产生的各种类型的关系现实中典型的异构信息网络有计算机科学文献网络和互联网电影资料库研究证实，在含有时间信息的异构网络中进行关联推理时，考虑时间信息得到的推理结果比未考虑时间信息得到的结果更好，例如文献同样地，由相关研究工作证明，参加空间信息会对异构信息网络上的关联推理带来更大的提升例如，文献已证实，融合了空间信息的关联推理能够获得更好的推理结果，但是在文献中的研究，仅仅考虑了一种类型实体间的关联推理，并非异构信息网络目前，基于异构信息网络且对网络中的时空信息加以利用进行关联推理的相关
4、研究还很少针对知识网络中时空信息的不断丰富，而现有的一些知识网络模型无法很好地刻画这些信息的问题，我们首先提出一个融合时间与空间信息的演化知识网络表示模型与传统的异构信息网络不同，演化知识网络中的点和边都有相应的时间演化函数和空间演化函数，用于表示点和边上的时间信息和空间信息利用这些时空函数能够具体刻画出现实中的实体本身的时空演化特点以及实体间关系的时空演变例如在学术网络中，传统的异构信息网络只能推理多种类型的实体之间存在的不同类型的关系，却没有时序的概念，无法表达不同关系产生的先后顺序、关系存在的时间范围以及关系产生的地点等这些信息对于关系预测和推荐是不可或缺的重要因素，且对于关联推理也具有
5、重要意义基于演化知识网络提出了一种新的关联推理方法由于知识网络中的关联推理是知识挖掘的重要手段，而在知识挖掘中我们最关注的无疑是推理结果的正确性，因而我们提出新的关联推理方法旨在提高关联推理的准确率及对大规模数据的适应性总结起来，本文奉献可归纳为下面点：提出了一个演化知识网络表示模型，将知识的时空信息融入到整个知识网络中，为知识的演化和计算提供更多的信息研究了基于演化知识网络的关联推理方法详细讲，提出一种基于混合背包问题的关联推理方法，提高关联推理的准确率和推理效率实验证实，与当前流行的关联推理方法相比，我们提出的关联推理方法得到了更好的推理效果，在准确率上有的提高，且在千万规模的数据集上的实
6、验证实我们的方法仍然有效下面具体介绍关联推理的相关研究工作目前主流的关联推理方法是运用机器学习的算法进行关联推理，基本上可被分为类：有监督学习方法和无监督学习方法，其中文献是有监督学习方法的经典代表，它将关联推理问题当成一个分类问题，利用经典的逻辑回归方法训练模型实关联推理尽管有监督学习的方法比拟流行，但是它们也存在很多弊端，例如训练复杂度高、平衡性较差、难以选择适宜的特征等相反，无监督的方法不需要关于数据分布的先验知识，避免了有监督学习的训练复杂度高等问题，对于大规模数据具有更强的适应性无监督的方法主要是通过定义一些指标来刻画网络中实体间的类似度来实现关联推理，例如文献是最近无监督关联推理的
7、典型代表，它以经典的共同邻居，方法为基础，参加节点连通性、边连通性以及部分时间信息等信息进行关联推理，但该方法只利用了网络中的局部信息我们的提出的推理方法也是一种无监督学习方法，该方法定义了一个拓扑特征链接延展形式形式，将全图的构造特征以及网络中的时空间信息融入到背包问题的参数中，利用背包问题的求解对形式进行选择，再利用选出的形式实现关联推理另一方面，目前流行的关联推理方法大部分是应用于异构信息网络上的，即网络中的实体与边的类型是多种多样的，例如文献，等最近又有很多工作将时间信息融入了异构信息网络中，并利用这些信息来提高关联推理的准确性我们提出的演化知识网络模型既包含知识的时间信息也包含知识的
8、空间信息，并利用这些信息进一步提高了关联推理的准确率需要十分指出的是，中已经提出了一个基于时空信息知识网络的模型，但是这个模型主要解决了知识库上的知识检索与查询问题，并未将时空信息应用到关联推理问题上综上所述，由于现有的知识网络对于知识的时空信息的描绘能力有限，导致在进行关联推理时无法对时空信息进行充分地利用，限制关联推理准确率的提高，因而我们提出一种融合了时空信息的知识演化网络模型，并提出一种基于该网络的推理方法，提高关联推理的准确率演化知识网络模型本节我们主要提出一个演化知识网络模型和定义在该网络上的一种特殊的子网络链接延展形式演化知识网络演化知识网络是一个异构的演化的多重图，且图中的节点
9、和边都包含时间与空间信息详细定义如下：定义演化知识网络给定一个时间集合，空间集合，则演化知识网络，可定义为一个元组：，其中，是演化知识网络中节点的集合；有向边的集合，它的详细表示形式是一个元组，这里，其中是边的所有类型构成的集合；：是节点类型的计算函数，使得每个节点通过该计算函数，可得到唯一的类型，这里为顶点的所有类型构成的集合；：表示在边集合中某一条边的计算函数，且每一个实体对间最多有条边；表示图中边的时间属性信息，用来描绘一条边的发生以及存在的时间信息；是边的空间属性信息；是节点的时间属性信息，是节点的空间属性信息在这个演化知识网络模型中，我们记录了图中节点与边的时间和空间信息这里的时间信
10、息是一系列离散的时间戳，空间信息则是一系列离散的地理位置信息演化知识网络的可演化性主要体如今可通过感悟网络中产生的新变化与本身进行比拟，发现新知识，并实现自我更新网络中的节点和边都有时间戳信息，它们都会随着时间的变化而演变，例如对于当前国家元首这个节点，会随着节点任职期满而自动更新为前任领导人，这便体现了网络的时空可演化性链接延展形式基于我们提出的演化知识网络，本文着重研究在该网络上的关联推理问题关联推理的主要目的是，利用知识库中已有的知识作为基础推理出两实体间可能存在的新关系这里我们做的关联推理不仅仅要推理出新的边，还要给出边的类型推理的主要思路是：首先构造出所有可能存在的链接延展形式；然后
11、建立一个混合背包问题模型，将每一个形式看作背包问题中待选择的物品；通过背包问题的求解，选择出对于关联推理有意义的形式；利用这些形式在图中进行匹配，推理出新的关系首先引入演化知识网络中的链接延展，形式的定义，简称为形式定义链接延展形式已知一个关系集，知识网络，我们定义，上的一个子网络，在这个子网络中任意两节点都可通过一条边进行关联，假如这个子网络中有个节点，则称其为元形式，我们将这个子网络叫做链接延展形式由图可知，对于不同的形式的定义我们能够找到它相应的实例，且对于同一个形式能够有多个不同的实例在进行关联推理时，我们需要将形式进行分解，使其成为可用来实现关联推理的新的形式例如图表示的一个形式，我
12、们可将其拆解为个可用于关联推理的新的形式，如图所示：在图中，我们将相连的两条边作为关联推理的条件，单独的一条边作为推理的结论在进行关联推理时，若已知在个节点他们的类型知足图中的要求，且节点类型为和的节点对之间的关系分别为和，则我们可推出两节点间存在关系例如在图中，我们已知和类型为作者，的类型为论文，且已知引用了，写了，则根据图中的形式，我们可推理和之间存在引用关系需要指出的是，在网络中利用这些形式进行推理的结果并非全部正确，例如图所代表的形式的含义是，某一位作者写了篇文章，可得出这篇文章之间存在引用关系，而事实上这个引用关系可能不存在，因而，对于网络中包含的所有的形式构成的集合，我们需要利用背
13、包问题的思想，从中选出置信度较高且涵盖关系类型更广泛的形式子集，并用子集中的所有形式进行关联推理关联推理方法基于混合背包问题的关联推理方法为了实现基于某一演化知识网络，上的关联推理，首先需要找出网络中所有可能存在的可用于关联推理的形式，通过混合背包问题求最优解的思想对不同形式进行选择下面我们先扼要介绍一下背包问题背包问题是一种组合优化的完全问题，能够描绘为：给定一组物品，每种物品都有本人的重量和价值，在限定的总重量内，我们怎样选择才能使物品的总价值最高这里我们将不同的形式看作背包问题中要装进背包中的物品，因而每个形式需要有相应的重量和价值两个参数我们从不同形式在网络中匹配的实例个数以及正确的实
14、例个数的角度，给形式的个参数重量和价值做了下面定义为了求解上面的混合背包问题，我们将问题拆解成个背包问题：多重选择背包问题，即在约束为消耗小于条件下，从每个分类中选出一个结果，这个步骤主要是保证每个分类中都有一个形式被选择出来，即在后期做推理时，每种关系都可能被推理出来；常规的背包问题，在消耗小于约束下我们能够从剩下的所有形式中选择更多意义的形式，提高推理的召回率算法及分析实现关联推理的经过可主要分为下面个步骤：构造可能存在的形式已知演化知识网络，上的边的所有类型，则任意种类型的边的组合可构成一个候选形式背包问题实现形式选择遍历全图，找出不同形式相应的所有实例，计算得到不同形式的和，通过混合背
15、包问题的求解选出有意义的形式利用选出的形式在网络中进行匹配得到推理结果下面算法中给出我们提出的关联推理算法的实现一般的遍历全图找不同形式的实例的方法是，对于每一个形式，遍历图中的所有节点；对于某一个节点，遍历它所有的边，假如知足形式要求，则以该边的另一个端点为起点遍历其他所有的边，看能否知足形式要求，依此类推假设共有个不同实例，全图有个节点，且图中节点的平均出度入度和为，则该运算的复杂度为以上方法固然容易实现，运算复杂度却很高，效率低下，因而算法利用了一些技巧降低了时间复杂度首先，我们不针对每个形式遍历一遍全图来找实例，而是做一个映射表，在这个映射表中不同形式对应的值为到当前为止该形式匹配上的
16、实例个数，因而只需遍历一遍全图即可得到所有形式的实例个数由于这里我们采用的形式均为元形式，基于三角形的特殊构造，对于每个节点的详细匹配经过，我们不需要从一个节点出发，以广度优先的思想遍历层关系，只需要从一个节点出发，找出它本身的所有关系，任意个关系为一组，若这个关系对的终点之间也存在关系则可构成一个形式，将映射表中的相应形式的值加即可该算法经过优化后的时间复杂度为实验本节我们将具体介绍相关的实验结果，验证我们提出的基于混合背包问题的关联推理方法的合理性与有效性，以及方法对于大数据环境的适应性实验数据集及参数选择我们采用来自不同领域的数据构建成个演化知识网络进行关联推理实验这个演化知识网络的数据
17、分别来自于学术领域和电影领域，均包含了多种不同类型的节点和关系其中学术网中的数据是从知名的学术文章网站上用网络爬虫爬获得到的，在这个网络中包含：万个作者、万篇论文、万个杂志、万个会议和万个关键词我们选用论文的发表时间以及会议的召开时间作为网络中时间信息，选机构所在地构成网络中的空间信息对于电影网，它的数据主要来自于对知名电影网站上的电影信息的爬取该网主要包括：演员和导演共个，电影部，我们选取电影上映时间、拍摄地等信息作为电影知识网络的时间与空间信息在表和表中分别列举了学术网和电影网中所有的实体间的直接关系需要指出的是，表中罗列的是从元数据中抽取的直接关系对于学术网，已知边的类型数，则根据形式的
18、特点能够找出所有可能存在的模型，去掉一些不可能存在的形式，最终，对于学术网我们可得到了个不同的形式同理对于电影网，我们共得到个形式实验经过中，我们在图中随机隐藏掉占整个网络中所有关系数量的指定比例的关系以及它们所有的附加信息，实验经过中通过改变这个比例来比拟不同方法的推理能力，这里由于我们做的是关联推理，而不是关系预测或时序关联推理，因而在隐藏关系时不考虑关系的时间顺序为了验证我们提出的方法的有效性，在实验中我们将方法与种近期比拟流行的关联推理方法进行比拟，一个是经典的有监督算法的代表逻辑回归方法简称，另一个是文献中提出的方法简称，它是一种典型的无监督学习方法对于逻辑回归方法，我们是将每一个形
19、式作为一维特征，构造训练数据，通过逻辑回归算法进行学习，学出每个特征的系数，在进行关联推理时给出一个实体对，匹配不同的形式假如没有形式能够匹配上，则推理两节点间没有关系；假如有形式匹配上则不同的关系能够得到一个分数，当分数大于某一阈值时，我们推理这两节点间存在这种关系实验可得，当阈值选择为时，逻辑回归的推理效果最好，因而在后面的比拟实验中，我们选择阈值为而对于方法，在给出实体对后，针对每种关系可计算出一个得分同理我们选择一个阈值，当得分大于该阈值时，推理两实体间存在某一关系，实验可知当阈值选择时效果最好。为了确定和的详细值，我们首先固定的值、变更的值，来研究的值变化对于关联推理效果的影响，找出
20、推理结果最优时的值；然后固定的值，在，的范围内调节的值，找出推理结果最优的值，最终可通过实验确定出个参数的值图给出了对学术网进行参数调节的经过，其中图分别代表，时对的值进行调节得到的测试结果从图可知，当，时，对于学术网上的关联推理结果最好同理我们对电影网上的数据进行测试，得到当，时结果最优实验结果及分析本节我们会通过实验进行方面的比拟：比拟与和方法间的关联推理准确率；演化知识络网与传统的异构信息网络的比拟；算法对于大数据的适应性的性能测试不同关联推理方法的推理效果比拟在进行不同关联推理方法的比拟实验时，我们选择准确率作为评价指标，主要是由于基于大规模知识网络的关联推理，推理结果的正确与否具有决
21、定性作用，推理结果作为知识必需要保证其准确性，因而这里我们选准确率作为指标实验结果如表所示，主要比拟了种不同方法的准确率，在这里表示隐去的关系数量占全图关系总数量的比例随着的增加，方法的表现均优于其他种方法，与有监督算法相比，我们的方法在学术网上准确率获得了的提高；对于方法，我们的方法获得了的提高，平均提高量分别为和同理在电影网上，我们的方法分别获得了和和的提高，平均提高值分别为和综合以上结果可得出结论，方法在不同的数据集上，比当前比拟流行的种方法均获得更好的推理结果其主要原因是，我们的方法将不同形式的特点以及全图的背景知识信息融入到背包问题中，通过背包问题的求解，从形式集合中选出高质量的形式
22、进行关联推理；而采用了所有的形式，仅仅通过训练数据给不同的形式学习出不同的系数，既未将全部的背景知识信息加以利用，模型的好坏完全受训练数据好坏的影响，又未对形式进行挑选；而方法只考虑了待推理的个实体的相关关系，对图的构造信息利用不充分，因此它的准确率最低演化知识网络与传统网络的比拟在节中我们通过实验证实了与其他几个关联推理中的经典方法在准确率上有较大的提高，其功于我们提出的基于混合背包问题的形式选择策略色优越性，同时我们猜测演化知识网络模型本身也对与推理结果的准确率的提高有一定赵泽亚等：大规模演化知识网络中的关联推理的帮助因而，我们分别在演化知识网络和异构信息网络中采用方法进行关联推理，比拟个
23、网络中的推理效果在个网络中，我们分别隐掉一样的关系，再对这些关系类型进行推理，由于传统的异构信息网络中没有时间信息，因而只能采用弱化的方法进行形式选择，即形式价值的定义有所改变，改为与该形式所有匹配的实例的个数推理结果如图所示：由图可知，随着隐掉边的比例的变化，上的推理准确率始终比高，提高比例为由此可见，演化知识网络与异构信息网络相比对关联推理有一定的帮助，这主要是由于演化知识网络中包含点与边的时空信息，这些信息对于关联推理的准确率的提高具有重要意义值得注意的是，随着隐掉边的比例的增加，两者的推理准确率均呈下降趋势，这是由于隐掉边的比例越大，已有的可用于推理的知识越少，因而推理的准确率有一定的
24、下降的性能测试由于在大数据环境下，数据量急剧增长，能否适应大数据的挑战，也是衡量一个算法好坏的重要方面，因而，下面我们对方法的计算性能进行测试首先分别构造不同大小的知识网络，测试在不同规模的网络上进行关联推理的时间消耗，这里我们将网络中的点的数量从万逐步增加到万，并记录下推理时间的变化，如图所示由图可知，随着网络规模的迅速增加，我们提出的推理方法时间消耗的增长缓慢当网络规模扩大了倍，推理耗时仅从增加到在算法我们也对方法的时间复杂度进行了分析，该算法的主要时间消耗集中在遍历全图找不同形式实例的经过，复杂度为，这里代表网络中节点的个数，为节点的出入度，因而随着网络规模的增加，的变化较小，因而整个算
25、法的时间消耗主要遭到网络中节点的个数的影响，因此随着网络规模的增加算法的时间消耗呈线性增长综上所述，我们提出的关系不仅在推理准确率上获得了较好的结果，其计算成本也并没有对着网络规模的扩大而呈指数增长，因而的计算性能也能够知足大规模知识网络对关联推理性能与效率的要求总结与瞻望本文首先提出了一个融合了时间与空间信息的演化知识网络，基于该网络提出了一种关联推理方法实验证实我们的方法比当前流行的一些关联推理方法获得了更高的准确率，且在大数据的环境下仍然拥有较好适应性但该方法也存在一定的局限性，例如对于网络中已有的关系数量有一定的依靠性、无法很好地应对冷启动问题，且对于网络中的空间信息利用不够因而，关于这个工作，仍有下面个需要研究的方向：方法对知识网络中已有的关系数量的依靠性较强，当面对冷启动问题时，怎样保证推理的准确率有待进一步研究；对于演化知识网络中的空间信息的利用有限，下一步可研究怎样更充分地利用网络中的时空信息，进一步提高推理效果；从知识表示的角度，研究知识网络的演化性和关联推理，是近年来知识网络的关联推理研究的新方向，相关工作包括文献；研究时序关系的推理，即推理知识网络中关系产生的时间，是进一步研究知识网络演化性的又一重要方向，相关工作包括文献