学文网《计算机研究与发展杂志》2016年第二期
摘要
网络大数据时代的到来使得知识网络中时空信息越来越丰富．现有的知识网络描述模型对知识的时空信息刻画不足．研究证明，利用网络中知识的时空信息以及相关性，能够提高网络中知识间的关联推理的准确率．针对以上问题，首先提出了一种包含时空信息的演化知识网络表示模型，然后研究在该网络模型上的关联推理问题，提出了一种基于背包问题的知识间关联推理方法．在多个数据集上的实验证明了所提出的关联推理方法的有效性以及对大规模知识网络的适应性．
关键词
关联推理；演化知识网络；背包问题；链接延展模式；知识库
网络大数据时代，数据不再仅仅是简单的采集对象，其背后其实蕴含着大量丰富、复杂、关联的知识［1］．当前网络数据是广泛可用的，所缺乏的只是从中提取知识的能力．有效利用网络大数据价值的主要任务不仅仅是是获取越来越多的数据，也需要从已有的数据中挖掘更多有用的知识［2］，构建成知识库，便于对知识更充分地利用，因此基于网络的大规模知识库的构建是最近流行的一个研究方向，现有的大规模知识库有YAGO［3－4］，DBpedia［5］，Probase［6］等．基于大规模知识库的关联推理是从海量信息中挖掘知识实现知识库增长的有效手段之一［7］，其主要目的是利用已有的大规模知识网络推理或者预测知识网络中隐含的关系．目前，关联推理已经在个性化推荐、社区发现、知识问答等方面得到广泛应用［8］．现有的关于知识网络中关联推理的研究，采用的方法主要有有监督学习、半监督学习以及无监督学习等．目前的研究更多的是基于异构信息网络的关联推理，这里的异构信息网络包含多种不同类型的实体与关系，例如人物、地点、组织机构、电影、论文等，以及它们之间可能产生的各种类型的关系．现实中典型的异构信息网络有计算机科学文献网络DBLP和互联网电影资料库IMDB．
研究证明，在含有时间信息的异构网络中进行关联推理时，考虑时间信息得到的推理结果比未考虑时间信息得到的结果更好，例如文献［9－10］．同样地，由相关研究工作［11－12］证实，加入空间信息会对异构信息网络上的关联推理带来更大的提升．例如，文献［13］已证明，融合了空间信息的关联推理可以获得更好的推理结果，但是在文献［13］中的研究，仅仅考虑了一种类型实体间的关联推理，并非异构信息网络．目前，基于异构信息网络且对网络中的时空信息加以利用进行关联推理的相关研究还很少．针对知识网络中时空信息的不断丰富，而现有的一些知识网络模型无法很好地刻画这些信息的问题，我们首先提出一个融合时间与空间信息的演化知识网络表示模型．与传统的异构信息网络不同，演化知识网络中的点和边都有相应的时间演化函数和空间演化函数，用于表示点和边上的时间信息和空间信息．利用这些时空函数可以详细刻画出现实中的实体自身的时空演化特点以及实体间关系的时空演变．例如在学术网络中，传统的异构信息网络只能推理多种类型的实体之间存在的不同类型的关系，却没有时序的概念，无法表达不同关系产生的先后顺序、关系存在的时间范围以及关系产生的地点等．
这些信息对于关系预测和推荐是不可或缺的重要因素，且对于关联推理也具有重要意义．基于演化知识网络提出了一种新的关联推理方法．由于知识网络中的关联推理是知识挖掘的重要手段，而在知识挖掘中我们最关注的无疑是推理结果的正确性，因此我们提出新的关联推理方法旨在提高关联推理的准确率及对大规模数据的适应性．总结起来，本文贡献可归纳为以下2点：1）提出了一个演化知识网络表示模型，将知识的时空信息融入到整个知识网络中，为知识的演化和计算提供更多的信息．2）研究了基于演化知识网络的关联推理方法．具体讲，提出一种基于混合背包问题的关联推理方法KP－LIM，提高关联推理的准确率和推理效率．实验证明，与当前流行的关联推理方法相比，我们提出的关联推理方法得到了更好的推理效果，在准确率上有8％～37％的提高，且在千万规模的数据集上的实验证明我们的方法依然有效．下面详细介绍关联推理的相关研究工作．目前主流的关联推理方法是运用机器学习的算法进行关联推理，基本上可被分为2类：有监督学习方法［13－18］和无监督学习方法［10，19－21］．其中文献［13］是有监督学习方法的经典代表，它将关联推理问题当成一个分类问题，利用经典的逻辑回归方法训练模型实关联推理．尽管有监督学习的方法比较流行，但是它们也存在许多弊端，例如训练复杂度高、平衡性较差、难以选择合适的特征等．相反，无监督的方法不需要关于数据分布的先验知识，避免了有监督学习的训练复杂度高等问题，对于大规模数据具有更强的适应性．无监督的方法主要是通过定义一些指标来刻画网络中实体间的相似度来实现关联推理，例如文献［19］是近期无监督关联推理的典型代表，它以经典的共同邻居（commonneighbour，CN）方法为基础，加入节点连通性、边连通性以及部分时间信息等信息进行关联推理，但该方法只利用了网络中的局部信息．我们的提出的推理方法KP－LIM也是一种无监督学习方法，该方法定义了一个拓扑特征———链接延展模式（LE模式），将全***的结构特征以及网络中的时空间信息融入到背包问题的参数中，利用背包问题的求解对LE模式进行选择，再利用选出的模式实现关联推理．另一方面，目前流行的关联推理方法大部分是应用于异构信息网络上的，即网络中的实体与边的类型是多种多样的，例如文献［9，15，22］等．
近期又有许多工作将时间信息融入了异构信息网络中，并利用这些信息来提高关联推理的准确性．我们提出的演化知识网络模型既包含知识的时间信息也包含知识的空间信息，并利用这些信息进一步提高了关联推理的准确率．需要特别指出的是，YAGO2［4］中已经提出了一个基于时空信息知识网络的模型SPOTL，但是这个模型主要解决了YAGO2知识库上的知识检索与查询问题，并未将时空信息应用到关联推理问题上．综上所述，由于现有的知识网络对于知识的时空信息的描述能力有限，导致在进行关联推理时无法对时空信息进行充分地利用，限制关联推理准确率的提高，因此我们提出一种融合了时空信息的知识演化网络模型，并提出一种基于该网络的推理方法，提高关联推理的准确率．
1演化知识网络模型
本节我们主要提出一个演化知识网络模型和定义在该网络上的一种特殊的子网络———链接延展模式．
1．1演化知识网络演化知识网络是一个异构的演化的多重***，且***中的节点和边都包含时间与空间信息．具体定义如下：定义1．演化知识网络．给定一个时间集合T，空间集合S，则演化知识网络GT，S可定义为一个8元组：GT，S＝（V，E，，φ，θ，τ，λ，η），其中，V是演化知识网络中节点的集合；E有向边的集合，它的具体表示形式是一个3元组（u，v，r），这里u，v∈V，r∈R，其中R是边的所有类型构成的集合；：VA是节点类型的计算函数，使得每个节点通过该计算函数，可得到唯一的类型（v）∈A，这里A为顶点的所有类型构成的集合；φ：ER表示在边集合中某一条边的计算函数，且每一个实体对间最多有｜R｜条边；θ表示***中边的时间属性信息，用来描述一条边的发生以及存在的时间信息；τ是边的空间属性信息；λ是节点的时间属性信息，η是节点的空间属性信息．在这个演化知识网络模型中，我们记录了***中节点与边的时间和空间信息．这里的时间信息是一系列离散的时间戳，空间信息则是一系列离散的地理位置信息．演化知识网络的可演化性主要体现在可通过感知网络中产生的新变化与自身进行比较，发现新知识，并实现自我更新．网络中的节点和边都有时间戳信息，它们都会随着时间的变化而演变，例如对于当前国家***这个节点，会随着节点任职期满而自动更新为前任领导人，这便体现了网络的时空可演化性．
1．2链接延展模式基于我们提出的演化知识网络，本文着重研究在该网络上的关联推理问题．关联推理的主要目的是，利用知识库中已有的知识作为基础推理出两实体间可能存在的新关系．这里我们做的关联推理不仅仅要推理出新的边，还要给出边的类型．推理的主要思路是：首先构造出所有可能存在的链接延展模式；然后建立一个混合背包问题模型，将每一个模式看作背包问题中待选择的物品；通过背包问题的求解，选择出对于关联推理有意义的模式；利用这些模式在***中进行匹配，推理出新的关系．首先引入演化知识网络中的链接延展（linkextendable，LE）模式的定义，简称为LE模式．定义2．链接延展模式．已知一个关系集R，知识网络GT，S，我们定义GT，S上的一个子网络H＝（V′，E′），V′A，E′R，在这个子网络中任意两节点都可通过一条边进行关联，如果这个子网络中有n个节点，则称其为n元模式，我们将这个子网络叫做链接延展模式．由***2可知，对于不同的LE模式的定义我们可以找到它相应的实例，且对于同一个LE模式可以有多个不同的实例．在进行关联推理时，我们需要将LE模式进行分解，使其成为可用来实现关联推理的新的LE模式．例如***2（a）表示的一个LE模式，我们可将其拆解为3个可用于关联推理的新的模式，如***3所示：在***3（a）中，我们将相连的两条边作为关联推理的条件，单独的一条边作为推理的结论．在进行关联推理时，若已知在3个节点他们的类型满足***3（a）中Au—P—Au的要求，且节点类型为Au—P和P—Au的节点对之间的关系分别为cite和write，则我们可推出两节点间存在cite关系．例如在***2（a）中，我们已知Tom和Lily类型为作者，paper1的类型为论文，且已知Tom引用了paper1，Lily写了paper1，则根据***3（a）中的LE模式，我们可推理Tom和Lily之间存在引用关系．需要指出的是，在网络中利用这些模式进行推理的结果并非全部正确，例如***1（b）所代表的模式的含义是，某一位作者写了2篇文章，可得出这2篇文章之间存在引用关系，而事实上这个引用关系可能不存在，因此，对于网络中包含的所有的模式构成的集合，我们需要利用背包问题的思想，从中选出置信度较高且涵盖关系类型更广泛的模式子集，并用子集中的所有模式进行关联推理．
2关联推理方法
2．1基于混合背包问题的关联推理方法（KP－LIM）为了实现基于某一演化知识网络GT，S上的关联推理，首先需要找出网络中所有可能存在的可用于关联推理的模式，通过混合背包问题求最优解的思想对不同模式进行选择．下面我们先简要介绍一下背包问题．背包问题（knapsackproblem）是一种组合优化的NP完全问题，可以描述为：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量M内，我们如何选择才能使物品的总价值最高．这里我们将不同的模式看作背包问题中要装进背包中的物品，因此每个模式需要有相应的重量Weight和价值Value两个参数．我们从不同LE模式在网络中匹配的实例个数以及正确的实例个数的角度，给LE模式的2个参数重量Weight和价值Value做了以下定义．为了求解上面的混合背包问题，我们将问题拆解成2个0－1背包问题：1）多重选择背包问题，即在约束为耗费小于M＊（M＊＜M）条件下，从每个分类中选出一个结果，这个步骤主要是保证每个分类中都有一个LE模式被选择出来，即在后期做推理时，每种关系都可能被推理出来；2）常规的背包问题，在耗费小于M－M＊约束下我们可以从剩下的所有模式中选择更多意义的模式，提高推理的召回率．
2．2算法及分析实现关联推理的过程可主要分为以下3个步骤：1）构造可能存在的LE模式．已知演化知识网络GT，S上的边的所有类型，则任意3种类型的边的组合可构成一个候选LE模式．2）背包问题实现模式选择．遍历全***，找出不同模式相应的所有实例，计算得到不同模式的Weight和Value，通过混合背包问题的求解选出有意义的LE模式．3）利用选出的模式在网络中进行匹配得到推理结果．下面算法1中给出我们提出的关联推理算法的实现．一般的遍历全***找不同模式的实例的方法是，对于每一个模式，遍历***中的所有节点；对于某一个节点，遍历它所有的边，如果满足模式要求，则以该边的另一个端点为起点遍历其他所有的边，看是否满足模式要求，依此类推．假设共有m个不同实例，全***有n个节点，且***中节点的平均出度入度和为r，则该运算的复杂度为O（mnr3）．以上方法虽然容易实现，运算复杂度却很高，效率低下，因此算法2利用了一些技巧降低了时间复杂度．首先，我们不针对每个模式遍历一遍全***来找实例，而是做一个映射表，在这个映射表中不同模式对应的值为到当前为止该模式匹配上的实例个数，因此只需遍历一遍全***即可得到所有模式的实例个数．由于这里我们采用的模式均为3元模式，基于三角形的特殊构造，对于每个节点的具体匹配过程，我们不需要从一个节点出发，以广度优先的思想遍历3层关系，只需要从一个节点出发，找出它自身的所有关系，任意2个关系为一组，若这2个关系对的终点之间也存在关系则可构成一个LE模式，将映射表中的相应模式的value值加1即可．该算法经过优化后的时间复杂度为O（nr2）．
3实验
本节我们将详细介绍相关的实验结果，验证我们提出的基于混合背包问题的关联推理方法KP－LIM的合理性与有效性，以及KP－LIM方法对于大数据环境的适应性．
3．1实验数据集及参数选择我们采用来自不同领域的数据构建成2个演化知识网络进行关联推理实验．这2个演化知识网络的数据分别来自于学术领域和电影领域，均包含了多种不同类型的节点和关系．其中学术网中的数据是从知名的学术文章网站Soscholar①上用网络爬虫爬取得到的，在这个网络中包含：1000万个作者（A）、700万篇论文（P）、50万个杂志（M）、1．4万个会议（C）和5万个关键词（K）．我们选用论文的发表时间以及会议的召开时间作为网络中时间信息，选机构所在地构成网络中的空间信息．对于电影网，它的数据主要来自于对知名电影网站IMDB上的电影信息的爬取．该网主要包括：演员（Ac）和导演（D）共4530159个，电影（M）2132383部，我们选取电影上映时间、拍摄地等信息作为电影知识网络的时间与空间信息．在表1和表2中分别列举了学术网和电影网中所有的实体间的直接关系．需要指出的是，表中罗列的是从元数据中抽取的直接关系．对于学术网，已知边的类型数，则根据LE模式的特点可以找出所有可能存在的LE模型，去掉一些不可能存在的模式，最终，对于学术网我们可得到了124个不同的模式．同理对于电影网，我们共得到18个模式．实验过程中，我们在***中随机隐藏掉占整个网络中所有关系数量的指定比例的关系以及它们所有的附加信息，实验过程中通过改变这个比例来比较不同方法的推理能力，这里由于我们做的是关联推理，而不是关系预测或时序关联推理，因此在隐藏关系时不考虑关系的时间顺序．为了验证我们提出的方法的有效性，在实验中我们将KP－LIM方法与2种最近比较流行的关联推理方法进行比较，一个是经典的有监督算法的代表逻辑回归方法［14］（简称Logistic），另一个是文献［8］中提出的方法M－CN＋ANC＋OAWpress（简称CN），它是一种典型的无监督学习方法．对于逻辑回归方法，我们是将每一个LE模式作为一维特征，构造训练数据，通过逻辑回归算法进行学习，学出每个特征的系数，在进行关联推理时给出一个实体对，匹配不同的模式．如果没有模式可以匹配上，则推理两节点间没有关系；如果有模式匹配上则不同的关系可以得到一个分数，当分数大于某一阈值时，我们推理这两节点间存在这种关系．实验可得，当阈值选择为0．6时，逻辑回归的推理效果最好，因此在后面的比较实验中，我们选择阈值为0．6．而对于CN方法，在给出实体对后，针对每种关系可计算出一个得分．同理我们选择一个阈值，当得分大于该阈值时，推理两实体间存在某一关系，实验可知当阈值选择0．8时效果最好。为了确定M＊和M的具体值，我们首先固定M的值、变更M＊的值，来研究M＊的值变化对于关联推理效果的影响，找出推理结果最优时M＊的值；然后固定M＊的值，在（M＊，Mmax）的范围内调节M的值，找出推理结果最优的M值，最终可通过实验确定出2个参数的值．***4给出了对学术网进行参数调节的过程，其中***4（a）～（d）分别代表M＝6，7，8，10时对M＊的值进行调节得到的测试结果．从***4可知，当M＝7，M＊＝5时，对于学术网上的关联推理结果最好．同理我们对电影网上的数据进行测试，得到当M＝3，M＊＝2时结果最优．
3．2实验结果及分析本节我们会通过实验进行3方面的比较：1）比较KP－LIM与Logistic和CN方法间的关联推理准确率；2）演化知识络网与传统的异构信息网络的比较；3）KP－LIM算法对于大数据的适应性的性能测试．
3．2．1不同关联推理方法的推理效果比较在进行不同关联推理方法的比较实验时，我们选择准确率作为评价指标，主要是因为基于大规模知识网络的关联推理，推理结果的正确与否具有决定性作用，推理结果作为知识必须要保证其准确性，因此这里我们选准确率作为指标．实验结果如表4所示，主要比较了3种不同方法的准确率，在这里α表示隐去的关系数量占全***关系总数量的比例．随着α的增加，KP－LIM方法的表现均优于其他2种方法，与有监督算法Logistic相比，我们的方法在学术网上准确率获得了2％～62％的提高；对于CN方法，我们的方法获得了28％～70％的提高，平均提高量分别为29％和37％．同理在电影网上，我们的方法分别获得了和1％～22％和20％～30％的提高，平均提高值分别为8％和24％．综合以上结果可得出结论，KP－LIM方法在不同的数据集上，比当前比较流行的2种方法均取得更好的推理结果．其主要原因是，我们的方法将不同模式的特点以及全***的背景知识信息融入到背包问题中，通过背包问题的求解，从模式集合中选出高质量的模式进行关联推理；而Logistic采用了所有的模式，仅仅通过训练数据给不同的模式学习出不同的系数，既未将全部的背景知识信息加以利用，模型的好坏完全受训练数据好坏的影响，又未对模式进行筛选；而CN方法只考虑了待推理的2个实体的相关关系，对***的结构信息利用不充分，因而它的准确率最低．
3．2．2演化知识网络与传统网络的比较在3．2．1节中我们通过实验证明了KP－LIM与其他几个关联推理中的经典方法在准确率上有较大的提高，其功于我们提出的基于混合背包问题的模式选择策略色优越性，同时我们猜想演化知识网络模型自身也对与推理结果的准确率的提高有一定499赵泽亚等：大规模演化知识网络中的关联推理的帮助．因此，我们分别在演化知识网络（EKN）和异构信息网络（HIN）中采用KP－LIM方法进行关联推理，比较2个网络中的推理效果．在2个网络中，我们分别隐掉相同的关系，再对这些关系类型进行推理，由于传统的异构信息网络中没有时间信息，因此只能采用弱化的KP＿LIM方法进行模式选择，即模式价值的定义有所改变，改为与该模式所有匹配的实例的个数．推理结果如***5所示：由***5可知，随着隐掉边的比例的变化，EKN上的推理准确率始终比HIN高，提高比例为1．9％～87％．由此可见，演化知识网络与异构信息网络相比对关联推理有一定的帮助，这主要是因为演化知识网络中包含点与边的时空信息，这些信息对于关联推理的准确率的提高具有重要意义．值得注意的是，随着隐掉边的比例的增加，两者的推理准确率均呈下降趋势，这是由于隐掉边的比例越大，已有的可用于推理的知识越少，因此推理的准确率有一定的下降．
3．2．3KP－LIM的性能测试由于在大数据环境下，数据量急剧增长，能否适应大数据的挑战，也是衡量一个算法好坏的重要方面，因此，下面我们对KP－LIM方法的计算性能进行测试．首先分别构造不同大小的知识网络，测试在不同规模的网络上KP－LIM进行关联推理的时间消耗，这里我们将网络中的点的数量从100万逐渐增加到1000万，并记录下推理时间的变化，如***6所示．由***6可知，随着网络规模的迅速增加，我们提出的KP－LIM推理方法时间消耗的增长缓慢．当网络规模扩大了10倍，推理耗时仅从8．372s增加到15．726s．在算法2我们也对KP－LIM方法的时间复杂度进行了分析，该算法的主要时间消耗集中在遍历全***找不同模式实例的过程，复杂度为O（nr2），这里n代表网络中节点的个数，r为节点的出入度，因此随着网络规模的增加，r的变化较小，因此整个算法的时间消耗主要受到网络中节点的个数n的影响，因而随着网络规模的增加算法的时间消耗呈线性增长．综上所述，我们提出的关系KP－LIM不仅在推理准确率上取得了较好的结果，其计算成本也并没有对着网络规模的扩大而呈指数增长，因此KP－LIM的计算性能也能够满足大规模知识网络对关联推理性能与效率的要求．
4总结与展望
本文首先提出了一个融合了时间与空间信息的演化知识网络，基于该网络提出了一种关联推理方法．实验证明我们的方法比当前流行的一些关联推理方法取得了更高的准确率，且在大数据的环境下依然拥有较好适应性．但该KP－LIM方法也存在一定的局限性，例如对于网络中已有的关系数量有一定的依赖性、无法很好地应对冷启动问题，且对于网络中的空间信息利用不够．因此，关于这个工作，仍有以下4个需要研究的方向：1）KP－LIM方法对知识网络中已有的关系数量的依赖性较强，当面对冷启动问题时，如何保证推理的准确率有待进一步研究；2）对于演化知识网络中的空间信息的利用有限，下一步可研究如何更充分地利用网络中的时空信息，进一步提高推理效果；3）从知识表示的角度，研究知识网络的演化性和关联推理，是近年来知识网络的关联推理研究的新方向，相关工作包括文献［23］；4）研究时序关系的推理，即推理知识网络中关系产生的时间，是进一步研究知识网络演化性的又一重要方向，相关工作包括文献［24］．
作者：赵泽亚 贾岩涛 王元卓 靳小龙 程学旗 单位：中国科学院网络数据科学与技术重点实验室 信息工程大学 中国天绘卫星中心
转载请注明出处学文网 » 知识网络中的关联推理